计算机通信网第5章 网络层

11第5章网络层5.1背景与相关问题5.2路由选择算法概述5.3几种路由算法及原理5.4拥塞控制与流量控制5.5网络互联225.1背景与相关问题5.1.1背景5.1.2网络层提供的服务5.1.3网络层的功能5.1.4网络层的内部结构335.1.1背景网络层的核心任务：为端系统的传输层提供穿越网络的服务端到端的网络连通性将分组从源端传送到目的端网络层环境在相连点提供的可靠传输之上（链路层的服务）通信网络中有很多节点、节点之间的链路情况差别很大可能还有不同的通信子网类型分组将如何穿越网络从源端到达目的端？SiSiSiSiSiSi相连端到端SiSiSiSiSiSiSiSi中间节点：如何知道目的地在何处？多条路径该选哪条路？选好的路故障怎么办？网络拥塞怎么办？★445.1.2网络层提供的服务向传输层提供穿越网络的、端到端的服务，并屏蔽网络的具体细节向传输层提供的服务与具体的网络环境和技术无关传输层不必也不需要了解具体的网络情况对传输层而言，对等实体的通信就像直接通信一样服务类别面向连接的服务通常由面向连接的协议提供面向无连接的服务通常由面向无连接的协议提供★555.1.3网络层提供的功能寻址：标识节点，节点定位路由选择：传播路径信息、形成路径在路径中选择存储转发：接收数据并存储，并按选择的路由转发（逐段转发）拥塞控制网际互连穿越多个网络穿越异种网络可能涉及分段与重组记帐★665.1.4网络层的内部结构针对网络层究竟应该提供何种服务,两大阵营产生了激烈的冲突争论的焦点：通信子网应承担什么样的任务？面向连接还是面向无连接的服务和技术？以电信公司为代表认为网络层应提供面向连接的服务以IETF（Internet工程任务组）为代表认为网络层应提供无连接的服务775.1.4网络层的内部结构以电信公司为代表的理由100年来电信系统的成功经验就是典范，认为：通信子网应采用面向连接的服务与技术网络层应该提供可靠的服务尽量简单的终端建立连接后，通信更容易受到控制,可在连接上限制用户流量以IETF为代表的理由通信子网应采用无连接的服务与技术，因为：通信注定不可靠需要终端自行解决差错等问题－－复杂终端终端的复杂性与终端的成本不一定成比例上升用户不必支付过时的、高额的通信费用网络的适应性更强、带宽利用率更高更自由885.1.4网络层的内部结构两种不同的观念形成了两种不同的通信子网构成方式面向连接的通信子网——虚电路无连接的通信子网——数据报典型的面向连接的网络层：ATM的网络层X.25网的网络层典型的无连接的网络层Internet的网络层★995.1.4网络层的内部结构知识回顾电路交换与分组交换虚电路数据报1010电路交换与分组交换电路交换通信双方通信之前建立专用连接，通信结束拆除连接一旦连接建立通信是端到端的（透明通道）中间节点转发延时很小，主要是传播延时独占资源适合流式业务（如话音）分组交换以分组为单位、逐站寻径、存储转发资源不独占、统计复用两种形式：虚电路和数据报虚电路：面向连接数据报：无连接信道利率高★电路交换的透明性强，分组交换的适应性强，带宽利用率高1111电路交换与分组交换1212电路交换与分组交换电路交换与分组交换在延时上的表现电路交换－－透明分组交换－－存储转发分组分组数据SiSiSiSiSiSiSiSiSiSiSiSi分组内存内存分组电路交换分组交换1313电路交换与分组交换效率1414虚电路虚电路的概念每条线路上有多条“虚”电路（VC，VirtualCircuit），用虚电路号标识（VCI）分组在线路上传输时，带上虚电路号虚电路不一定与具体信道资源有关分组可不必携带源、目的地址12345虚电路data2data5data4data2虚电路号★1515虚电路虚电路是基于分组交换的虚电路是面向连接的端系统通信之前，与对端建立连接，形成一条端到端的虚电路VC所有的分组都将沿着该虚电路到达目的地面向连接并不独占信道统计复用资源★1616虚电路交换每个网络节点都有一张虚电路表（路由表）内容：虚电路号、入线→虚电路号、出线得到：在呼叫连接建立时虚电路标识号：代表分组的路径每个虚电路号只具有本地（局部的含义）逐段的虚电路标识(VCI)序列组成一条端到端的虚电路虚电路交换节点为每个呼叫建立一个虚电路号，实现入/出的虚电路映射换言之：就是逐段交换虚电路号SiSiSiSiSiSiSiSi245132413351SiSi虚电路表表项只需要保持当前的连接，规模小，查表速度快data5312data4data3SiSi★1717虚电路交换与电路交换都是面向连接的，具有连接的所有特点建立连接、通信、拆除连接三过程通信是按序的但电路交换是独占资源的，端到端透明、转发延时很短一个用户通常只能与一个用户建立连接虚电路交换基于分组交换，不独占资源，逐站存储转发，有一定延时一个用户可以同时与多个用户建立虚连接（虚电路）★1818数据报与虚电路项目类型数据报虚电路都是以分组为单位，存储转发、逐站寻径建链与拆链NOYES地址源、目地址虚电路号保存状态信息NOYES（虚电路映射表）路由选择每个分组独立选路所有分组沿已建好的路径转发节点或线路损毁的影响影响不大，可立即重新选路所有经过的虚电路被终止，须重新建立连接拥塞控制较难较易灵活性更好稍差★1919数据报与虚电路虚电路方式节点寻径速度快数据报方式健壮性强重新建立连接，重新开始20205.2路由选择算法概述5.2.1路由的基本概念5.2.2路由选择算法的特征（要求）5.2.3路由选择的最优化原则5.2.4实现路由功能的要素5.2.5路由选择的方法与技术21215.2.1路由的概念路由的基本概念源到目的节点之间，由节点和线路组成的一条通路路由选择面临的问题存在多条路径选择一条最优路径：如何选择？节点需掌握所有的路径：表项规模？最优路径随网络拓扑变化而变化路由需要及时更新，但要避免路由振荡避免出现路由环路.网络结构一般是逐层汇聚的避免网络阻塞：负载均担？★22225.2.2路由选择算法的特征（要求）正确性：目的地存在且可达简单性：计算简单，实现容易健壮性：路由算法能适应节点故障、增减造成的拓扑结构的变化，及时调整路由，并不影响全网工作稳定性：路由更新后会有过渡期，路由算法应使过渡期尽量短，具有快的收敛性（避免路由震荡）公平性：节点地位平等最优化：一定策略下的最优（有时也称策略性）低开销：路由控制信息尽可能少，开销尽可能低。★23235.2.3路由选择的最优化原则什么是最优路径？源、目节点间存在多条路径1到5的路径有多条：1-2-5，1-3-5，1-4-5，1-2-3-5……寻求一条最优路径，需求不同会有不同的最优路径·以距离为度量：最短距离以时延为度量：最小延时以跳数为度量：最少节点数以价格为度量：最少费用以带宽为度量：最大吞吐量……实际网络中，可能考虑一项，也可能需要考虑多项参数，进行选择145235通常称这些度量参数为Cost或Metric★24245.2.3路由选择的最优化原则最优化原则如果存在着一条最佳路径从I经J到K，那么其IJ段和JK段都是最佳的。用途：当I计算最优路由后将分组交给J，J所选择的最优路由与I选择的是一致的！是存储转发、逐站寻径的基础，是分布式路由算法的基础IJKAB★25255.2.4实现路由功能的要素编址与寻址全网唯一的地址（站点的唯一性）地址结构有规律，便于寻址如：电话网：国家号+城市号+局号+终端号又如：Internet：网络号+子网号+主机号路由表：记录到达目的地的路径信息Routing：计算到目的节点的最佳路径，生成并维护路由表Routed：查表方法及转发策略Routing+Routed由路由协议实现★26265.2.5路由表与转发策略路由表（RoutingTable）通过路由协议计算出某个节点到目的节点的最佳路由，形成的路径信息有时也与转发表同义（ForwardingTable）注意：有时分为路由信息表和转发表两种表，而转发表由路由信息表得到路由表的组成ABCED121122目的下一站出口度量B直连21EC13……A节点的路由表27275.2.5路由表与转发策略路由表中使用缺损路由（默认路由）以节点A和节点B为例目的下一站出口B直连2DC1EC1ABCED121122213A节点的路由表目的下一站出口A直连1CD2ED2B节点的路由表目的下一站出口B直连2默认C1目的下一站出口A直连1默认D2默认路由用于代替有相同的下一跳的表项路由表更简短当找不到明确转发路径时，才使用默认路由28285.2.5路由表与转发策略（扩）转发策略查路由表（转发表），根据转发路径进行转发转发之前如何查表？最短适配：从高地址部分开始适配即从最大的范围开始例：8602883202528最长适配：从低地址部分开始适配即从最接近主机的路由开始例：202.115.12.0高地址－－网络号低地址－－主机号其它查找算法：顺序、折半、Hash……不考虑地址的结构性，可提高查找效率与以上两种方法配合以提高效率完整适配：要求路由表规模太大，一般不用29295.3路由算法5.3.1路由算法的基本原理5.3.2路由算法的分类与特点5.3.3几种静态路由算法扩散法（洪泛法）随机路由烫土豆法5.3.4几种动态路由算法中心路由算法逆向学习法分布式路由算法（关、重点）距离矢量法链路状态法5.3.5分级路由5.3.6一些特殊的路由30305.3.1路由算法的基本原理事先计算所有最优路由，形成路由表(转发表）各节点根据路由表进行PDU的转发213456目的节点出口下一节点★31315.3.2路由选择的类型及特点非自适应算法（静态路由算法）根据网络拓扑先计算好路由，网络启动时由网管中心分配到各节点路由表内容不变，如网络结构有变，进行人工更改算法简单，可靠性高，适应于网络变化小的网络，但不灵活自适应算法（动态路由算法）根据网络的变化计算路由路由表内容随网络的变化自动更新动态路由需在节点间交换信息算法较复杂，但更能反映网络实际情况适用于网络拓扑变化★32325.3.3几种静态路由算法固定路由算法扩散法（洪泛法）随机路由烫土豆法3333固定路由算法基本思想事先计算所有节点的最佳路径，形成中心路由表各节点根据中心路由表，形成自己的路由转发表转发表的更新与维护只能人工进行特点：适应于拓扑基本不变的小网★3434-12-23242424固定路由算法节点1目的节点下一节点223242526212453617232211331142856385654321654321-655425-554254-542535-325424-254151-源节点目的节点下一个节点中心路由表节点2目的节点下一节点1133445464形成转发表3535扩散法（洪泛法）基本思想节点将收到的分组沿本节点各出线（收分组的线除外）转发出去总有一条路径最优特点不需要网络结构信息—网络结构无关性总能送达目的地—高度稳健性所有节点都能收到信息，特别适用于广播目的节点会收到多个重复的分组应用领域军用网:节点随时都有被毁的可能，此路由算法可最大限度地将信息传输到目的地树形和星形结构网络或小型网★3636扩散法（洪泛法）存在的问题可能会出现扩散风暴，大量分组被转发，造成拥塞可能形成环路，来回转发改进措施：站点记数法（设置生命周期－TimeToLive，TTL）分组携带站点数，初值最大为网络的站点数，每经过一个站点，站点数减1，直至为0时，将分组丢弃首次登录法分组携带分组序号，首次到达站点时记下此序号，如该分组再次到达此站时不再扩散（需定期清除记录