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

1、1,第5章 网络层,5.1 背景与相关问题 5.2 路由选择算法概述 5.3 几种路由算法及原理 5.4 拥塞控制与流量控制 5.5 网络互联,2,5.1 背景与相关问题,5.1.1 背景 5.1.2 网络层提供的服务 5.1.3 网络层的功能 5.1.4 网络层的内部结构,3,5.1.1 背景,网络层的核心任务： 为端系统的传输层提供穿越网络的服务 端到端的网络连通性 将分组从源端传送到目的端 网络层环境 在相连点提供的可靠传输之上（链路层的服务） 通信网络中有很多节点、节点之间的链路情况差别很大 可能还有不同的通信子网类型 分组将如何穿越网络从源端到达目的端？,中间节点： 如何知道目的地在

2、何处？ 多条路径该选哪条路？ 选好的路故障怎么办？ 网络拥塞怎么办？,4,5.1.2 网络层提供的服务,向传输层提供穿越网络的、端到端的服务，并屏蔽网络的具体细节 向传输层提供的服务与具体的网络环境和技术无关 传输层不必也不需要了解具体的网络情况 对传输层而言，对等实体的通信就像直接通信一样 服务类别 面向连接的服务 通常由面向连接的协议提供 面向无连接的服务 通常由面向无连接的协议提供,5,5.1.3 网络层提供的功能,寻址： 标识节点，节点定位 路由选择： 传播路径信息、形成路径 在路径中选择 存储转发： 接收数据并存储，并按选择的路由转发（逐段转发） 拥塞控制 网际互连 穿越多个网络 穿

3、越异种网络 可能涉及分段与重组 记帐,6,5.1.4 网络层的内部结构,针对网络层究竟应该提供何种服务,两大阵营产生了激烈的冲突 争论的焦点： 通信子网应承担什么样的任务？ 面向连接还是面向无连接的服务和技术？ 以电信公司为代表认为 网络层应提供面向连接的服务 以IETF（Internet工程任务组）为代表认为 网络层应提供无连接的服务,7,5.1.4 网络层的内部结构,以电信公司为代表的理由 100年来电信系统的成功经验就是典范，认为： 通信子网应采用面向连接的服务与技术 网络层应该提供可靠的服务 尽量简单的终端 建立连接后，通信更容易受到控制,可在连接上限制用户流量 以IETF为代表的理由

4、 通信子网应采用无连接的服务与技术，因为： 通信注定不可靠 需要终端自行解决差错等问题复杂终端 终端的复杂性与终端的成本不一定成比例上升 用户不必支付过时的、高额的通信费用 网络的适应性更强、带宽利用率更高 更自由,8,5.1.4 网络层的内部结构,两种不同的观念形成了两种不同的通信子网构成方式 面向连接的通信子网虚电路 无连接的通信子网数据报 典型的面向连接的网络层： ATM的网络层 X.25网的网络层 典型的无连接的网络层 Internet的网络层,9,5.1.4 网络层的内部结构,知识回顾 电路交换与分组交换 虚电路 数据报,10,电路交换与分组交换,电路交换 通信双方通信之前建立专用连

5、接，通信结束拆除连接 一旦连接建立 通信是端到端的（透明通道） 中间节点转发延时很小，主要是传播延时 独占资源 适合流式业务（如话音） 分组交换 以分组为单位、逐站寻径、存储转发 资源不独占、统计复用 两种形式：虚电路和数据报 虚电路：面向连接 数据报：无连接 信道利率高,电路交换的透明性强，分组交换的适应性强，带宽利用率高,11,电路交换与分组交换,12,电路交换与分组交换,电路交换与分组交换在延时上的表现 电路交换透明 分组交换存储转发,分组,分组,数据,分组,内存,内存,分组,电路交换,分组交换,13,电路交换与分组交换效率,14,虚电路,虚电路的概念 每条线路上有多条“虚”电路（VC，

6、Virtual Circuit），用虚电路号标识（VCI） 分组在线路上传输时，带上虚电路号 虚电路不一定与具体信道资源有关 分组可不必携带源、目的地址,1,2,3,4,5,虚电路,15,虚电路,虚电路是基于分组交换的 虚电路是面向连接的 端系统通信之前，与对端建立连接，形成一条端到端的虚电路VC 所有的分组都将沿着该虚电路到达目的地 面向连接并不独占信道 统计复用资源,16,虚电路交换,每个网络节点都有一张虚电路表（路由表） 内容：虚电路号、入线 虚电路号、出线 得到：在呼叫连接建立时 虚电路标识号：代表分组的路径 每个虚电路号只具有本地（局部的含义） 逐段的虚电路标识(VCI)序列组成一条

7、端到端的虚电路 虚电路交换 节点为每个呼叫建立一个虚电路号，实现入/出的虚电路映射 换言之：就是逐段交换虚电路号,2,4,5,1,3,2,4,1,3,3,5,1,虚电路表表项只需要 保持当前的连接， 规模小，查表速度快,data,5,3,1,2,17,虚电路交换与电路交换,都是面向连接的，具有连接的所有特点 建立连接、通信、拆除连接三过程 通信是按序的 但 电路交换 是独占资源的，端到端透明、转发延时很短 一个用户通常只能与一个用户建立连接 虚电路交换 基于分组交换，不独占资源，逐站存储转发，有一定延时 一个用户可以同时与多个用户建立虚连接（虚电路）,18,数据报与虚电路,19,数据报与虚电路

8、,虚电路方式 节点寻径速度快 数据报方式 健壮性强,重新建立连接，重新开始,20,5.2 路由选择算法概述,5.2.1 路由的基本概念 5.2.2 路由选择算法的特征（要求） 5.2.3 路由选择的最优化原则 5.2.4 实现路由功能的要素 5.2.5 路由选择的方法与技术,21,5.2.1路由的概念,路由的基本概念 源到目的节点之间，由节点和线路组成的一条通路 路由选择面临的问题 存在多条路径 选择一条最优路径：如何选择？ 节点需掌握所有的路径：表项规模？ 最优路径随网络拓扑变化而变化 路由需要及时更新，但要避免路由振荡 避免出现路由环路. 网络结构一般是逐层汇聚的 避免网络阻塞：负载均担？

9、,22,5.2.2 路由选择算法的特征（要求）,正确性： 目的地存在且可达 简单性： 计算简单，实现容易 健壮性： 路由算法能适应节点故障、增减造成的拓扑结构的变化，及时调整路由，并不影响全网工作 稳定性： 路由更新后会有过渡期，路由算法应使过渡期尽量短，具有快的收敛性（避免路由震荡） 公平性： 节点地位平等 最优化： 一定策略下的最优（有时也称策略性） 低开销： 路由控制信息尽可能少，开销尽可能低。,23,5.2.3 路由选择的最优化原则,什么是最优路径？,源、目节点间存在多条路径 1到5的路径有多条： 1-2-5，1-3-5，1-4-5，1-2-3-5 寻求一条最优路径，需求不同会有不同的

10、最优路径 ,以距离为度量：最短距离 以时延为度量：最小延时 以跳数为度量：最少节点数 以价格为度量：最少费用 以带宽为度量：最大吞吐量 实际网络中，可能考虑一项，也可能需要考虑多项参数，进行选择,通常称这些 度量参数为Cost或Metric,24,5.2.3 路由选择的最优化原则,最优化原则 如果存在着一条最佳路径从I经J到K，那么其IJ段和JK段都是最佳的。 用途： 当I计算最优路由后将分组交给J，J所选择的最优路由与I选择的是一致的！ 是存储转发、逐站寻径的基础，是分布式路由算法的基础,I,J,K,A,B,25,5.2.4 实现路由功能的要素,编址与寻址 全网唯一的地址（站点的唯一性） 地

11、址结构有规律，便于寻址 如：电话网：国家号+城市号+局号+终端号 又如：Internet：网络号+子网号+主机号 路由表：记录到达目的地的路径信息 Routing：计算到目的节点的最佳路径，生成并维护路由表 Routed：查表方法及转发策略 Routing+ Routed由路由协议实现,26,5.2.5路由表与转发策略,路由表（ Routing Table） 通过路由协议计算出某个节点到目的节点的最佳路由，形成的路径信息 有时也与转发表同义（Forwarding Table） 注意：有时分为路由信息表和转发表两种表，而转发表由路由信息表得到 路由表的组成,A,B,C,E,D,1,2,1,1,2

12、,2,A节点的路由表,27,5.2.5 路由表与转发策略,路由表中使用缺损路由（默认路由） 以节点A和节点B为例,A节点的路由表,B节点的路由表,默认路由用于代替有相同的下一跳的表项 路由表更简短 当找不到明确转发路径时，才使用默认路由,28,5.2.5路由表与转发策略（扩）,转发策略 查路由表（转发表），根据转发路径进行转发 转发之前如何查表？ 最短适配：从高地址部分开始适配 即从最大的范围开始 例：86 028 8 320 2528 最长适配：从低地址部分开始适配 即从最接近主机的路由开始 例：202.115.12.0 高地址网络号 低地址主机号 其它查找算法：顺序、折半、Hash 不考虑

13、地址的结构性，可提高查找效率 与以上两种方法配合以提高效率 完整适配：要求路由表规模太大，一般不用,29,5.3 路由算法,5.3.1 路由算法的基本原理 5.3.2 路由算法的分类与特点 5.3.3 几种静态路由算法 扩散法（洪泛法） 随机路由 烫土豆法 5.3.4 几种动态路由算法 中心路由算法 逆向学习法 分布式路由算法（关、重点） 距离矢量法 链路状态法 5.3.5 分级路由 5.3.6 一些特殊的路由,30,5.3.1 路由算法的基本原理,事先计算所有最优路由，形成路由表(转发表） 各节点根据路由表进行PDU的转发,2,1,3,4,5,6,31,5.3.2路由选择的类型及特点,非自适

14、应算法（静态路由算法） 根据网络拓扑先计算好路由，网络启动时由网管中心分配到各节点 路由表内容不变，如网络结构有变，进行人工更改 算法简单，可靠性高，适应于网络变化小的网络，但不灵活 自适应算法（动态路由算法） 根据网络的变化计算路由 路由表内容随网络的变化自动更新 动态路由需在节点间交换信息 算法较复杂，但更能反映网络实际情况 适用于网络拓扑变化,32,5.3.3 几种静态路由算法,固定路由算法 扩散法（洪泛法） 随机路由 烫土豆法,33,固定路由算法,基本思想 事先计算所有节点的最佳路径，形成中心路由表 各节点根据中心路由表，形成自己的路由转发表 转发表的更新与维护只能人工进行 特点： 适

15、应于拓扑基本不变的小网,34,固定路由算法,6,5,4,3,2,1,6,5,4,3,2,1,源节点,目的节点,下一个节点,中心路由表,35,扩散法（洪泛法）,基本思想 节点将收到的分组沿本节点各出线（收分组的线除外）转发出去 总有一条路径最优 特点 不需要网络结构信息网络结构无关性 总能送达目的地高度稳健性 所有节点都能收到信息，特别适用于广播 目的节点会收到多个重复的分组 应用领域 军用网:节点随时都有被毁的可能，此路由算法可最大限度地将信息传输到目的地 树形和星形结构网络或小型网,36,扩散法（洪泛法）,存在的问题 可能会出现扩散风暴，大量分组被转发，造成拥塞 可能形成环路，来回转发 改进

16、措施： 站点记数法（设置生命周期Time To Live，TTL） 分组携带站点数，初值最大为网络的站点数，每经过一个站点，站点数减1，直至为0时，将分组丢弃 首次登录法 分组携带分组序号，首次到达站点时记下此序号，如该分组再次到达此站时不再扩散（需定期清除记录，以免占用大量存储空间） 选择性转发 有选择地转发分组，减少扩散范围,37,随机路由,基本思想 节点将收到的分组根据概率随机选取一个出口将分组转发出去 特点 不需要网络信息网络结构无关性 每次路径随机变化 可能会出现欲东传西的情况 算法简单 应用领域 小网，星形、树形网,38,烫土豆法,基本思想 节点将收到的分组尽快出手，选择队列最短的

17、出口转发（考虑了通信量） 其他与随机路由相同特点,39,5.3.4 几种动态路由算法,动态路由算法 根据网络动态变化计算路由，形成路由表 路由表自动形成并根据拓扑变化自动更新 适应于网拓扑变化的网络、大网 如广域网、互联网 涉及的问题 节点之间交换路由信息 快速适应拓扑变化 感知拓扑变化 快速传递变化信息 快速形成新的稳定的路由（无环路、不震荡，快速收敛）,40,5.3.4 几种动态路由算法,中心路由算法 逆向学习法 分布式路由算法（重点） 距离矢量法 链路状态法,41,中心路由算法（集中路由）,原理 各个节点定期将本节点的信道及 相邻节点信息报告给中心路由计算机 由中心路由计算机计算出各节点

18、到其他节点的最佳路由，然后分配到各个节点 特点 理论上讲可以得到全网最优路由（因算法考虑了流量、节点等全网信息） 但实现困难，很难在大网中使用，适应于小网，原因有三： 信息上传困难（各节点定期上传信息会造成中心路由计算机附近节点及线路的拥塞） 同步困难（节点很多，中心反馈新路由时，各节点接收时间不同，可能会导致同一网里有的节点使用新路由，有的使用老路由） 路由更新过时（可能会出现路由更新到达时，节点情况已变）,42,逆向（反向）学习法,原理 根据接收分组中的源地址和接收端口号，形成转发表，以便下次作为目的节点时的转发路径 特点 能动态适应新节点的加入 对线路故障、节点损坏反应迟钝 适应拓扑结构

19、相对稳定、小网,C,A,收到从A送来的分组,路由表中记录从该接口可以到达A,43,分布式动态路由算法,基本原理 节点之间需相互交换路由信息 节点单独计算路由 基本特点 局部最优，全局不一定最优 相互交换信息越具体、越频繁，路由优化越好，但造成的额外开销也越大。 需要在额外开销和路由更新的频率之间进行折中 优点 动态反映网络变化，路由表自动形成与更新（不需人工干预） 局部最优，路由开销少 缺点 局部最优路由，不是全局最优路由 可能出现不一致（矛盾）的路由 可能出现路由震荡（路由表变化太快） 可能出现路由发散（不能收敛）,44,分布式路由算法要点,交换路由信息：,分布式计算：节点根据交换的路由信息

20、，采用最优路由计算 方法计算最佳路由,哪些信息？,与谁交换？,边交换信息边计算,可达、距离、费用、负载、延时,与邻居、与所有节点,何时交换？,定时、拓扑变化时,45,两种典型的分布式路由算法,基于网络距离的分布式路由算法-矢量距离法 基于信道状态的分布式路由算法-链路状态法,46,链路状态算法（L-S：link-state）,基本思想 一般以时延作为度量的参数 发现邻居并测量与邻居的时延（延迟，链路状态） 与所有节点交流与邻居的链路状态信息 独立计算出到其他节点的最佳路径 注意影响时延的可能因素 线路的速率 当前负载节点处理能力 互联网中普遍使用的OSPF算法采用L-S法,链路状态：理解为 链

21、路的开销 链路的质量 延迟等度量,47,矢量距离法（V-D：Vector Distance）,根据协议的设计者命名，也称为 Bellman-Ford路由算法 Ford-Fulkerson路由算法 基本思想 每个节点都保持一张到其他节点的路由表 （目的节点，下一节点，距离） “距离”的度量标准可以是跳数或时延等 邻居之间交换路由信息（目的节点，距离） 根据收到相邻节点的信息，判断并决定是否更新路由 算法涉及的内容 初始的路由表如何建立？ 邻居交换哪些信息? 如何根据邻居信息计算并更新自己的路由表？,48,矢量距离法,算法的几个步骤 初始化 建立初始路由表 扩散 向邻居扩散自己的路由表信息 计算

22、根据收到相邻节点的信息，计算最短路径，更新路由表 再扩散、再计算 这样就逐渐形成了全网的拓扑结构 使每个节点都计算出了到其他节点的路径信息 值得注意的是：何时向邻居扩散路由信息？ 定期 拓扑发生变化时,49,距离矢量算法,1）初始路由表建立 （目的节点，下一节点，距离）=（V0，G0，D0） 2）路由表向邻居扩散,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,注意： 度量值可以是节点跳数、时延等度量参数,50,距离矢量算法,各节点的初始路由表：直接相连节点的路由信息,2,1,3,4,5,6,1,1,1,1,1,1,1,1,2,目的 节点,下一 节点,距离,1,1,1,3,3,1,

23、4,4,1,目的 节点,下一 节点,距离,1,1,1,2,2,1,4,4,1,5,5,1,目的 节点,下一 节点,距离,2,2,1,3,3,1,5,5,1,6,6,2,51,距离矢量算法,3）节点计算并更新本节点的路由表 相邻节点定期交换信息（目的节点，距离）=（V，D） 当某节点A收到相邻节点j的信息（Vx，DjX）时 （Vx表示目的地为X节点，Djx为j到X节点的距离） A节点更新情况如下： 如A路由表中无此项，则添加表项（Vx，j， D0+ DXj） （D0为A与邻居j的距离） 如A路由表中有Vx项，（Vx，k，DAx） 若kj DAx D0 + Djx，则表项更新为（Vx，j， D0

24、+ DjX ）（新、短路径） DAx D0 + Djx，则此表项保持不变 若k=j 无论DAx大小如何，都应更新为（Vx，j，D0 + DjX） （原路径可能变化，需更新）,52,距离矢量算法,节点1路由表初始值,收到节点3路由信息,更新后,收到节点2路由信息,距离更新=到邻居节点的距离+邻居节点到目的节点的距离,更新后,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,4,2,2,5,3,2,关,53,距离矢量算法,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,关,54,距离矢量算法,2,

25、1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1路由表更新,距离更新= 到邻居节点的距离+ 邻居节点到目的节点的距离,收到节点2路由信息,更新后,6,2,4,更新后,6,2,4,3,3,关,55,距离矢量算法,4）各节点将更新后的路由表分别向自己的邻居扩散，然后计算并再次更新路由表 当每个节点的路由表包含了所有其他节点的路由时，就形成了一个稳定的路由，只要拓扑不变化，路由表就保持不变，否则会重新计算。,56,距离矢量算法,相关问题 水平分割 节点没有必要将从某节点收到的信息再传回给该节点 无穷计数 距离矢量算法会出现路由环路 设计最大路径长度（跳数），以减轻环路出现时带来的损害

26、用毒性反转方法，破坏路由环路,57,水平分割,2,1,3,4,5,6,1,1,1,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,节点没有必要将从某节点 收到的信息再传回给该节点,58,无穷计数,在某种情况下，距离矢量算法可能出现路由环路，其现象是路由表项随路由信息更新，不断增加。,A,C,B,D,正常情况：,A认为到D经过B,C认为到D经过B,B认为到D经过D,路由环路：,A认为到D经过B,C认为到D经过A,B认为到D经过C,59,A,C,B,D,平时： A收到C告知：D有两跳 A收到B告知：D有一跳,选B,C收到A告知：D有两跳,C收

27、到B告知：D有一跳,选B,当B到D的链路断掉后，一种可能的情形：,B告诉A、C：D不可达,A重新选路，正好收到C告知D有两跳（C还没收到B的更新信息）,A选择到D经过C，距离为三跳,A告知B：D有三跳,B选择到D经过A，距离为四跳,C收到B先前的D不可达更新，重新选路,B告知C：D有四跳,C选择到D经过B，距离为五跳,出现路由环路， 并计数到无穷大,60,毒性反转解决路由环路,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,节点将从某节点收到的信息再传回给该节点时，告诉对方不能从我这里过,无穷大,无穷大

28、,无穷大,61,距离矢量算法小节,特点： 只与邻节点交换路由信息 各节点独立计算最优路径（但依赖邻居的计算结果） 能适应网络拓扑的变化 稳定后，形成最短路径 算法简单 缺点： 网络变化扩散到全网速度慢 扩散速度：所有节点都发现变化的速度 路由收敛慢 收敛速度：大家分别计算，结果达到统一的速度 存在路由环在网络变化未扩散完全时。,小网,62,链路状态算法,算法的基本步骤，每个节点都进行以下工作： 发现邻居 探寻邻居，得到邻居的唯一地址 测量链路开销 测量到各邻居节点的延迟（链路质量） 交换路由信息 形成链路状态分组，向所有节点扩散 充实路由信息库 根据收到各节点的链路状态信息，进而得出全网拓扑

29、计算路由表 根据自己掌握的路由信息，独立计算本节点到其他节点的最佳路由（最小时延） 特别注意：链路状态算法 交流的路由信息：链路状态信息（本节点到邻居的延迟） 交流的对象：向所有的节点 交流的方法：扩散法 路由的计算：只根据自己掌握的路由信息，独立计算最佳路由（不依赖别人的计算）,63,链路状态算法,发现邻居节点 初始时，每个节点都向每个出口（点到点线路）发送“Hello”分组，告知自己的地址 收到分组的节点则回应一个分组告知自己的地址 特别强调：每个节点的地址必须唯一,A,B,Hello，I am A,Hello，I am B,64,链路状态算法,测量链路开销（链路延迟） 向邻居发送“Ech

30、o”分组（对方必须应答） 对方发送应答 计算来回延时除以2，得到时延（可计算几次得平均值） 计算链路开销时值得讨论的问题 是否考虑负荷？ 两种观念 考虑负荷，从进入发送队列排队开始算 忽略负荷，从发送开始算 正反方向延时是否一样？ 可能不一样 为分析简便，通常忽略差异，用平均值,A,B,T,“Echo”,“Echo”Response,65,链路状态算法,通过测试计算出到邻居的开销 假设各节点测得的开销如下所示,A节点,B节点,4,C,3,B,开销,邻居,6,C,5,D,3,A,开销,邻居,2,D,6,B,1,E,4,A,开销,邻居,3,E,2,C,2,F,5,B,开销,邻居,3,D,2,F,1

31、,C,开销,邻居,2,E,2,D,开销,邻居,C节点,D节点,F节点,E节点,66,链路状态算法,创建链路状态分组 根据测得的到所有邻居的的延时，形成链路状态分组 链路状态分组的内容 发布者：发布信息的节点名称 序号：序号的大小表示信息的新旧 时间：一个分组在网络中的存活时间,67,链路状态算法,发布链路状态分组 发布对象：所有节点 发布时间：定期，链路状态发生改变时 发布方法：扩散法（洪泛） 采用扩散法一定可以到达全网各节点 节点可能收到多个相同的分组 可根据序号判别，相同的序号则丢弃重复的 节点也可能收到同一个发布者不同序号的分组 根据发布时间判别，丢弃老的，处理新的 为避免分组可能在网中

32、循环 通过时间（年龄）字段避免（按时间递减，到0时将被丢弃） 各节点根据逐步收到的链路分组，充实路由信息库，逐步“绘出”拓扑图,68,链路状态算法,计算到各节点的最佳路由 计算方法： 把本节点作为源节点，计算到其他节点的路由 采用著名的Dijkstra算法（最短路径算法） 计算的依据 只根据自己掌握的路由信息库（拓扑） 独立计算最佳路由（不依赖别人的计算）,69,链路状态算法,如何计算最佳路由 最短路径算法Dijkstra算法,A1,A2,A4,A3,A5,2,6,5,1,2,1,5,1）初始化时，设A1到其它不直连节点距离为,寻找A1到所有节点的最短路径,A2,A3,A4,A5,顶点,距离,

33、路径,2）选择距离A1最短的节点及其路径,3）观察通过新选择的路径是否能更短到达其它顶点,4）已选择出的节点和最短路径将不参加下一轮比较,5）反复2 - 4步，直到不剩有节点,2,6,5,A2,A3,A4,A1 A2 A33,更新,A1 A2 A3,3,A1 A2 A4 ,A1 A2 A5 4,A1 A2 A3 A44,更新,A1 A2 A3 A4,4,A1 A2 A3 A58,A1 A2 A5,4,A1 A2 A3 A4 A5,更新,70,链路状态算法,最短路径算法的计算思想 每一步都取出当前最短的路径，计算该路径对其它路径的改变 从最近开始逐步计算到最远,2,1,3,4,5,6,71,链路

34、状态算法小结,特点 与全网节点交换路由信息路由信息的扩散 各节点独立计算最优路径一致性、准确性有较好的保证 不是建立在别人的计算结果上（如距离矢量算法） 能适应网络拓扑的变化，稳定后能形成最短路径 收敛速度快可在大网中使用 不是计算之后再扩散 算法复杂，存储空间需求大 需要记录全网所有的链路状态,72,链路状态算法与距离矢量算法比较,到其他节点的路由（路由表信息）,到相邻节点的链路开销,仅向邻居,向所有节点扩散,定期或发生变化时,定期或链路发生变化时,各点自己计算，但依赖邻居的计算结果,各点自己计算，不依赖其他节点的计算,小网,大网,73,作业5,1、根据不同的要求设计协议（假设信道传播延时可

35、忽略）（选作两问） （提示：面向连接与否、PDU格式，PDU交换时序） 1）要求1： PDU可以乱序，丢弃有错的PDU，上交无差错的SDU 2）要求2： PDU可以乱序到达，但接收方必须按序上交SDU，并恢复有错的PDU 3）要求3 PDU必须按序到达，接收方必须按序上交SDU，并恢复有错的PDU,74,作业5,2、简述在距离矢量算法（D-V）和链路状态算法（L-S）中，各节点计算路由转发表时，各以什么为依据？并以此分别说明采用D-V和L-S算法的节点对网络拓扑的了解情况。,75,作业6,1、下图中以延迟为代价，请用D-V算法和L-S算法分别计算C点的路由转发表 （要求答题步骤：初始表，收到中

36、间信息后，路由的变化过程，以及稳定后C点的路由表）,A,B,E,D,C,5,3,1,1,2,2,1,76,5.3.5 Hierarchical Routing,Our routing study thus far - idealization all routers identical network “flat” not true in practice scale: with 200 million destinations！ cant store all dests in routing tables! routing table exchange would swamp links!

37、administrative autonomy internet = network of networks each network admin may want to control routing in its own network,77,5.3.5分级路由体系,网络规模大巨型网络,建设结构、管理机构等众多,网络结构复杂,各自进行各自的路由,网间设定网间的路由方式,分级路由体系,屏蔽网内路由细节,考虑网间路由的一些管理性特点,网间路由,78,Hierarchical Routing,Aggregate routers into regions “autonomous systems”

38、(AS) Routers in same AS may run same routing protocol “intra-AS” routing protocol routers in different AS can run different intra-AS routing protocol Gateway router Direct link to routers in other ASes,79,Interior & Exterior Routing,Autonomous system（自治系统，AS） A group of networks and routers under th

39、e authority of a single administration Each AS typically represents an independent organization and applies its own unique routing and security policies AS number An identifying number that is assigned by an Internet registry or a service provide Range: 165535 Private AS number: 6451265535,80,路由存在一种

40、层次结构的概念 IGP： Interior Gateway Protocol EGP：Exterior Gateway Protocol,小网路由,小网路由,小网路由,网间路由,小网路由,小网路由,小网路由,网间路由,外部路由,IGP,EGP,81,Intra-AS Routing,Also known as Interior Gateway Protocols (IGP) Most common Intra-AS routing protocols: RIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP:

41、Interior Gateway Routing Protocol (Cisco proprietary),82,EGP,EGP：外部网关协议 为外部网络间的通信提供路由 没有义务为外网提供内部的路由信息 没有义务提供如何得到最佳路由的信息 体现和满足网络所有者之间的约定 向外部网络提供的路由信息只包括 可达性，可以到达哪些目的地 Internet上，BGP是一种EGP BGP：Border Gateway Protocol,83,5.3.6 一些特殊的路由,广播路由 多播路由 移动主机的路由 Ad Hoc网络中的路由,84,广播数据的路由,广播数据需要发送给所有目的地的分组 实现方法类型 向

42、每个目的发送一份拷贝 洪泛 多目的分组路由 广播分组带有所有希望的目的 路由器选择适当线路 生成树 按树的路径转发分组 没有回路,85,多点播送路由选择,多播数据向一个组发送的数据，Multicast 多播路由：向一个组发送的路由算法称多播路由 多播路由的实现：播送树（多播树） 信源树路由算法 核心树路由算法（共享树）,生成树,小组1的多点播送树,小组2的多点播送树,86,多点播送路由选择,信源树 组播组里，每个发送源都形成一棵组播树有源树 组播节点在转发数据时，根据分组源地址和相应的树表，决定转发的路径 共享树核心基本树 在组播组里，大家遵循同一颗组播树共享树 组播源站先想办法将数据发送到共

43、享树的根节点，由根节点再延着树转发数据 减少树表所占空间 组播树的形成协议,1,1,1,1,1,源,源,87,组播标准,组播地址 IP组播地址：224.0.0.0239.255.255.255（D类） （11100000）（11101111） MAC组播地址：0 x0100.5Exx.xxxx 映射：IP地址的后28位MAC地址的后23位（25:1） 组播路由协议 密集模式（SPT）：DVMRP、PIM-DM 稀疏模式（RPT）：PIM-SM、CBT 链路状态协议（SPT）：MOSPF 组播组管理协议 IGMP：v1、v2、v3,88,移动主机的路由,固定主机 永远不移动的主机（接入点固定）

44、移动主机 接入点变化仍希望接入网络的主机 接入点变化的方式 搬移到其他网络的接入点接入（迁移主机） 离开原始网络漫游到了外地（漫游主机） 寻径与移动的矛盾 节点的网络地址一般具有定位性 当节点移动后，无法通过节点的地址对节点定位，也就无法将数据路由到节点。,89,移动主机的路由策略,目标： 一个主机无论在哪里上网，保持其网络地址不变 实现方法 引入本地代理HA（Home Agent）、外地代理FA（Foreign Agent） HA：记录移动主机在原始地的主地址以及现在移动地的转交地址的映射关系 FA：记录所有正在访问该域的主机，并为他们提供转交地址和转发数据,90,移动主机的路由策略,实现原

45、理 当主机移动到外地后，自己感知已移出本地网 通过代理发现协议找到一个FA，并向该FA请求注册 告知主机的网络地址，硬件地址以及HA FA向HA发起对该移动主机的认证，认证通过，则 FA给移动主机分配一个转交地址，并在FA中记录该条信息 同时HA得到移动主机的转交地址，并记录其转交地址与主地址之间的映射 移动主机主动呼叫时直接通过FA发出 目的为移动主机的数据先到HA，HA将数据转发到FA，最后转给移动主机 HA也可直接告诉发送者，目前移动主机的转交地址，以后可直接发送到FA，而后到达移动主机,本地代理,A,B,外地代理x,注册,通知A在我这里,A在x处,91,无线多跳网络的路由技术,无线多跳

46、网络Ad Hoc网络 特点 节点移动，拓扑复杂，多变，变化速度快 路由技术 先应式：表驱动式，先建立路由表 反应式：按需路由，只有当需要时才去发现路由,92,5.3.7 路由算法的应用,网间路由（大型网络） 链路状态算法 网络拓扑结构复杂,网间路由,93,路由算法的应用,网间路由（中小型网络园区网） 距离矢量算法 简单,Router,Router,Router,94,路由算法的应用,以太网桥中的路由： 洪泛路由+自学习路由,95,5.4 拥塞控制与流量控制,5.4.1 什么是拥塞及拥塞控制？ 5.4.2 如何理解拥塞控制与流量控制？ 5.4.3 拥塞控制的通用原则和方法 5.4.4 影响拥塞控

47、制的策略 5.4.5 虚电路子网中的拥塞控制 5.4.6 数据报子网中的拥塞控制 5.4.7 负载丢弃 5.4.8 服务质量,96,5.4.1什么是拥塞及拥塞控制？,什么是网络拥塞？ 设：X为网络的输入网络所有主机单位时间（t）发出的分组 Y为网络的输出所有主机在（t）收到的分组 由于单位时间发出的分组增加，造成网络中存在大量分组，导致单位时间收到的分组急剧降低，甚至网络完全瘫痪的这种情况叫做拥塞（congestion）。,网络Cmax,y,理想,拥塞控制,x,y,X,无拥塞控制,x,网,络,0,拥塞控制会牺牲小通信量时的吞吐量，保证大通信量时的吞吐量,97,5.4.1 什么是拥塞及拥塞控制？

48、,造成网络拥塞的原因 网络流量过于集中到某节点，超过节点处理能力（缓冲区有限，造成拥塞，分组丢弃) 局部线路或整体容量小，加快拥塞的产生,链路： 分组太多，超过我的能力了！,节点： 分组太多，受不了了！,98,拥塞,一个点的拥塞会向全网蔓延,99,5.4.2 拥塞控制与流量控制,拥塞控制不同于流量控制 控制对象不同 流控：局部于两点之间 拥控：全局控制，拥塞点附近节点全网范围 控制结果不同 流控：两点之间发送方降速 拥控：拥塞点得到缓解 控制方法不同 流控：降低发送速度 拥控：预分配资源，更改路径，丢弃分组等,100,5.4.2 拥塞控制与流量控制,拥塞控制与流量控制之间有联系，易混淆 网络拥

49、塞后，吞吐量下降，节点响应慢，感觉象对方收不下来，从而误判为需要流量控制 流量控制的不好是造成拥塞的原因之一 在拥塞控制机制中，可能用到流量控制手段 但拥塞控制事关全局，仅在个别节点的个别链路上进行流量控制，并不能有效解决网络拥塞问题,101,5.4.3 拥塞控制的基本方法,拥塞控制的方法就是寻找下式成立的条件，即 对网络资源的需求网络的可用资源 资源: 节点的缓冲区，线路的容量，处理机的处理能力等 控制方法分为两类：开环、闭环,检测和解除闭环 如何检测拥塞 检测丢失、延时、队列长度 出现拥塞后的解决方法 拥塞后不许可，如不给拨号音 另选路径 设警告位 抑制分组 载荷脱落,预防和避免开环 不使

50、拥塞出现的方法 缓冲区预分配 分组丢弃 网络分组定额控制,102,5.4.4 影响拥塞控制的策略,相关方面很多,103,5.4.5虚电路子网的拥塞控制,许可/准入控制（Admission Control） 拥塞时不再建立新的链路 拥塞时选择绕道建立虚电路,104,5.4.6 数据报子网的拥塞控制,基本思想 当线路利用率超过阈值，路由器通知源站减速 相关技术 警告位 拥塞时，节点（路由器）在确认分组头部设置警号位 源通过收到带警告确认的个数调整发送速率 抑制分组 拥塞路由器通过抑制分组直接通知源站降速 逐跳抑制 源太远时，通过从拥塞点向外逐跳抑制（中间节点减速，最后源站减速）,105,5.4.7

51、 负载丢弃(Load Shedding),基本思想 拥塞路由器根据一定策略丢弃分组 相关策略 葡萄酒策略：老酒更醇，即丢弃新分组 文件传输 牛奶策略：新鲜更重要，丢弃老分组 流媒体 其它“智能”策略,106,5.4.8 服务质量,如何描述一个流的质量需求？ 获得好的服务使用的技术 综合服务 区分服务,107,5.4.8 服务质量(QoS),如何描述一个流的质量需求？ 流（flow）的描述： 从一个源到一个目的的分组流（stream） 流的质量需求描述 通常由四个基本参数描述 可靠性（可由误码率表征） 延迟 抖动(Jitter) 带宽,如： 话音业务： 延迟和抖动要求相对高 文件传输： 可靠性要

52、求相对高,108,5.4.8 服务质量,获得好的服务使用的技术 提供足够的资源（容量、缓冲区） 提供足够缓冲能力 虽有一定延迟，但可较好消除抖动 （第四版p337图5.31） 流量整形 用户与网络运营商之间协商控制参数 允许传输速率、突发特性、丢失允许情况 漏桶算法： 可以任意速率接收用户数据 但以匀速间隔向网络送入数据，,109,5.4.8 服务质量,综合服务采用资源预留协议RSVP RSVPResource reSerVation Protocol 适合电视会议，视频点播的多点播送拥塞控制 多源对多组接收 接收者可自由切换“频道” 基本思想： 接收方向发送方提前建立流，并申请预留资源 允许

53、一个接收向多个发送方建立不同的流 避免造成拥塞 基于多点播送生成树 由接收者向源及路径上的路由器申请带宽（预留资源） 同源接收者可利用同一路径及带宽 尽量减少源发出的数据,110,RSVP多点播送树,主机1和主机2为多播发送方，主机3、4、5为多播接收方 图（b）为主机1的多播树 图（c）为主机2的多播树,111,RSVP资源保留,图（a）：主机3向主机1申请的预留资源 图（b）：主机3向主机1、2申请的预留资源 图（c）：主机5向主机1申请预留带宽时，H到主机1的资源可利用主机3已申请的,112,5.4.8 服务质量,区分服务: Differentiated Service 粗分类（两大类）

54、 快速转发类别 常规转发类别 细分类 多种优先级 定义每个分组在拥塞是的丢弃概率（高、中、低） 根据优先级和丢弃级别决定转发策略 MPLS: Multi-Protocol Label Switching 多协议标签交换,113,5.5 网络互联,5.5.1 网络互联背景 5.5.2 网络互联面临的问题 5.5.3 协议实体与互联 5.5.4 网络互联技术 5.5.5 网络互联设备 5.5.6 网络层子层 5.5.7 互联与路由 5.5.8 两种不同的互联思想 5.5.9 面向连接的互联与无连接的互联 5.5.10互联的相关技术 5.5.11现有网络互联结构分析 5.5.12数据传递与转发,11

55、4,5.5.1 网络互联背景,多种网络并存 多种线路 多种协议 多种协议体系 多种技术及技术路线 面向连接与无连接 固定帧长与可变帧长 ,115,5.5.1 网络互联背景,多种网络 WAN：x.25 、 Frame Relay 、ATM 、TCP/IP LAN：IPX、IEEE802、SNA、DECnet MAN：ADSL、ISDN、广播电视网 多种互联环境与需求 LANWAN LANLAN LANWANLAN WANLANWAN WANWAN,同构网络之间的互联 具有相同协议的网络 异构网络之间的互联 具有不同协议、不同层次的网络,116,5.5.2 网络互联面临的问题,操作方式与服务质量的

56、不同 协议不同 帧格式不同 操作过程、处理方式不同,虚电路数据报,沿同一路径,沿不同路径,按序到达,可能不按序到达,可靠、有差错处理,不可靠、无差错处理,117,5.5.2 网络互联面临的问题,寻址方式不同 地址结构不同 最大可传输分组大小不同 不同的安全机制，计费策略等,+86 028 8320 2528,中国 成都 电子科技大学 通信学院,202.115.12.5,网A,网B,？,118,5.5.2 网络互联面临的问题,P355图5-43（第4版）网络如此不同,119,5.5.2 网络互联面临的问题,几个典型的互联环境 以太网互联,PSTN,协议实体不匹配，如何实现通信？,120,网络互联面临的问题,以太网与X.25的互联,层次不匹配、协议不匹配，如何互联？,X.25,121,5.5.3 协议实体与互联,对等实体间才能实现通信 对等实体是实现相同协议的实体 每一个实体，一定有一个对等实体存在,122,？,实体C,实体C,实体C,实体B,实体