计算机网络自顶向下方法(第四版)ppt第4章课件.ppt

《计算机网络自顶向下方法(第四版)ppt第4章课件.ppt》由会员分享，可在线阅读，更多相关《计算机网络自顶向下方法(第四版)ppt第4章课件.ppt（148页珍藏版）》请在三一办公上搜索。

1、1,第4章 网络层,运输层：接受网络层提供的主机到主机的通信服务。为主机上的两个进程之间提供通信服务。 运输层只在网络的主机中出现；网络层在网络的主机和路由器中出现。 本章主要讨论网络层如何实现主机到主机的通信服务。,2,主要内容,网络层功能和服务：虚电路和数据报；路由器结构：分组转发；网络层的选路：决定分组从源到目的地所经路径的一些选路算法。4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP 协议4.5 选路算法4.6 因特网的选路4.7 广播和多播小结,3,4. 1 概述,发送方主机网络层的作用：将来自运输层的每个报文段封装成一个数据报（网络层分组）；将数据报向目的地

2、发送，即向相邻的路由器R1发送。,H1,H2,R1,R2,4,接收方主机网络层的作用：接收来自相邻的路由器R2的数据报；解封出报文段，并交付给其运输层。,H1,H2,R1,R2,路由器的主要作用： 将数据报从输入链路“转发”到输出链路。 通常路由器只实现下三层部分,4.1.1 转发和选路4.1.2 网络服务模型,5,1、网络层功能,将分组从发送主机移动到接收主机。主要包括：转发： 当一个分组到达某个路由器的输入链路时，该路由器必须将其移动到合适的输出链路。 与路由器的内部结构有关。选路： 确定分组从发送方流向接收方时所经过的路由或路径。 通过选路算法计算路径。,6,两者区别：,转发：将分组从路

3、由器的一个输入链路接口转移到一个合适的输出链路接口的本地动作。 只涉及分组在路由器中从入链路到出链路的传送选路：指分组从源到目的地的端到端路径的网络范围动作。 涉及网络中的所有路由器，集体经选路协议交互，决定分组从源到目的地的路径。类比汽车旅行:选路: 从起点到目的终点计划行程的过程。转发: 通过单个立交桥的过程,7,2、路由器如何转发分组,转发表：每台路由器有一张。分组首部（目的地址或某个连接标识）和相应输出链路的对照表。 转发表的内容由选路算法决定（集中式或分布式）。,8,1,2,3,0111,到达分组首部的值,选路算法,转发方法：,路由器根据到达分组的首部值在转发表中查询，找到相应的输出

4、链路接口，并将分组转发出去。,9,3、术语,分组交换机：一台通用分组交换设备，根据分组首部值，从输入链路接口到输出链路接口传送分组。链路层交换机：根据链路层字段值作转发决定的分组交换机。路由器：根据网络层字段值作转发决定的分组交换机。,10,4、连接建立,运输层连接：如TCP协议，在数据实际传输之前，需要发送方和接收方经过三次握手建立所需的状态信息。网络连接：指网络层数据分组开始传输前，在所选择的从源到目的地路径上的各路由器之间相互握手，建立连接状态。 如ATM、帧中继的网络层。 因特网网络层不执行连接建立。使用IP协议！,11,4.1.2 网络服务模型,问题：发送主机的运输层是否能依靠网络层

5、将分组交付到目的地；多个分组是否能按发送顺序交付给接收主机的运输层；传输两个连续分组的时间间隔是否与接收到的时间间隔相同；网络层是否能提供网络拥塞的反馈信息；连接发送与接收主机的运输层通道的抽象视图（特性）是什么？ 由网络层提供的服务模型来确定。,12,网络服务模型 ：,定义在网络的一侧“边缘”到另一侧“边缘”之间（即在发送与接收端系统之间）端到端的数据运输特性。,13,1、网络层可能提供的服务,确保交付：确保分组到达目的地。具有时延上界的确保交付：主机到主机的时延。有序分组交付：按发送顺序到达。确保最小带宽：当发送主机以低于特定比特率的速率发送比特，分组不会丢失，在一定时延到达。确保最大时延

6、抖动：发送方发送两个连续分组的时间间隔与接收到的间隔相同。,14,2、因特网网络层提供的服务,单一的服务，即尽力而为服务(best-effort service)，类似于“根本无服务”。分组间的定时不能被保证；分组的接收顺序与发送顺序不一定相同；传送的分组不能保证最终交付，即网络可能未向目的地交付分组。,15,3、ATM服务模型,提供多重的服务模型，即在同一网络中为不同的连接提供不同类别的服务。恒定比特率CBR (Costant bit rate)服务： 标准的ATM服务模型。适用于实时、恒定比特率的音频和视频流。服务目标：使网络连接看起来就像在发送主机和接收主机之间有一条专用的固定带宽的传输

7、链路。ATM信元传输时的端到端时延可变性(时延抖动)及丢失、迟交的信元都保证在规定值以下。,16,可用比特率ABR (Available bit rate)服务 “比尽力服务稍好一点”的服务。可能会丢失信元，但不能被重排序 ；保证最小信元传输速率 (MCR)，或比MCR更高（有足够空闲资源）；能够为发送方提供反馈信息。,17,网络层服务模型:,18,4.2 虚电路和数据报网络,运输层：提供无连接服务和面向连接服务。 如因特网的UDP、TCP 。网络层：提供无连接服务和面向连接服务。面向连接服务：源和目的主机之间先握手。无连接服务：无握手过程。,19,区别：,网络层：向运输层提供的主机到主机的服

8、务。 运输层：向应用层提供的进程到进程的服务。网络层：任何网络中的网络层只提供两种服务之一，不会同时提供。虚电路网络：提供连接服务。数据报网络：提供无连接服务。运输层：面向连接服务在网络边缘的端系统中实现。 网络层：面向连接服务在端系统及网络核心的路由器中实现。,20,本节内容,4.2.1 虚电路网络4.2.2 数据报网络4.2.3 数据报和虚电路服务的由来,21,4.2.1 虚电路网络,如X.25、帧中继和ATM等。 根据虚电路号转发分组。,22,1、虚电路VC 组成,源和目的地之间的一条连接路径：一系列链路和路由器；VC号：该路径上每段链路的号码，每条链路上的VC号可能不同； 路由器转发表

9、中的表项：VC路径上每台路由器中都有该表。,23,2、工作原理,在源和目的之间创建一个VC；源向该VC发送带有VC号的分组；每经过一台中间路由器，用新的VC号代替原VC号： 从VC号转发表获得；分组在每条链路上的VC号不同。依此规则，直到目的地。,24,主机A与主机B通信过程,12,22,32,1,3,2,VC号,接口号:路由器连接链路的接口号码,主机A与主机B之间创建一条VC： 路径为A R1 R2 B，3个链路分配VC号12、22和32。 传输时，分组VC号变化过程： 12 22 32 A R1 R2 B,A,B,R1,R2,R3,R4,25,3、VC号转发表结构,例，R1中的VC号转发表

10、。,路由器维护连接状态信息!,12,22,32,1,3,2,VC号,B,R1,R2,R3,R4,A,VC1VC2VC3VC4,26,只要该路由器创建新的VC，其转发表中就增加一项；终止一个VC，其转发表中就删除对应项。路由器必须为正在进行的连接维护连接状态信息，直到该连接释放。每条链路采用不同VC号的优点：减少分组首部VC字段的长度；简化虚电路的建立过程。,27,虚电路的三个阶段：,虚电路建立：在发送方与接收方之间建立一条虚电路，即决定所有分组要通过的一系列链路与路由器，并为每条链路确定一个VC号。发送方与网络层联系，指定接收方地址，由网络建立虚电路 (VC)。如图4-4（14步）。涉及到路径

11、上每个路由器转发表的更新、资源的预留等。,1. 发起呼叫,2. 入呼叫,3. 接受呼叫,4. 呼叫已连接,28,1. 发起呼叫,2. 入呼叫,3. 接受呼叫,4. 呼叫已连接,5. 数据流开始,6. 接收数据,数据传送： 沿该虚电路传输数据分组（56步）。 虚电路拆除： 由其中一方通知其网络层终止该虚电路； 通知网络另一侧的端系统呼叫结束，并更新路径上每台路由器中的转发表。,29,网络层与运输层连接建立区别,运输层的连接建立： 只涉及两个端系统，相互协商通信并共同确定连接的参数。网络中的路由器并不知道该运输层连接。网络层虚电路建立： 沿两个端系统之间路径上的路由器都要参与虚电路的建立，且每个路

12、由器都完全知道所经过的所有虚电路。,30,信令报文： 端系统向网络发送的指示虚电路的启动与终止的报文、以及路由器之间传递的用于建立虚电路的报文信令协议：用来交换信令报文的协议。,31,4.2.2 数据报网络,如，因特网。网络层无呼叫建立路由器没有端到端连接的状态无网络级“连接”的概念分组使用目的主机地址转发相同源和目的地的分组可能采用不同的路径,32,传输过程,发送方给要发送的分组加上目的端系统地址，并送入网络，经过若干中间路由器转发分组，直到目的地。,1. 发送数据,2. 接收数据,33,路由器转发方法：根据到达分组的目的地址在转发表中查询，找到相应的输出链路接口，并将分组转发出去。转发表：

13、每台路由器有一张。目的地址与链路接口的映射表。 转发表中的表项数与地址位数有关，每个可能的地址对应一项。 例，设目的地址32位， 40亿可能的项。,34,转发表,目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 000101

14、11 00011111 11111111 其他 3,例，某个路由器有4条链路（03），地址与链路接口关系：,是否可简化？,35,最长前缀匹配转发表,前缀匹配 链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 其他 3,36,路由器查表方法：,用目的地址前缀与转发表的前缀匹配：存在匹配：向对应链路转发。 如，目的地址 11001000 00010111 00010110 10100001 不存在匹配：选择“其他”项对应的链路转发。存在多个匹配：使用最长前缀匹配规则，即向与最长

15、前缀匹配的链路接口转发分组。 如，目的地址 11001000 00010111 00011000 10101010 ,0#,1#,前缀匹配 链路接口11001000 00010111 00010 0 11001000 00010111 00011000 111001000 00010111 00011 2 其他 3,37,说明,路由器转发表只维持转发状态信息；转发表由选路算法修改（15分钟更新）；虚电路网络转发表随虚电路的建立和拆除更新。一个端系统发送给另一个端系统的一批分组可能在网络中选择不同的路径，到达的顺序可能不一致。,38,虚电路服务,源于电话产业界（采用“真正”电路）。呼叫建立及每次

16、呼叫的状态要在网络中的路由器上维持，比面向数据报的网络要复杂。网络功能复杂，端系统设备简单。,39,数据报服务,由互连计算机的需求发展而来。与电话网相反。网络层服务模型简单。端系统功能复杂：高层实现许多功能，如按序传送、可靠数据传输、拥塞控制与DNS名字解析等；带来的结果：因特网服务模型提供的服务保证最少（可能没有！），对网络层的需求最小，使得互连使用各种不同链路层技术的网络变得更加容易。许多应用都在位于网络边缘的主机（服务器）上实现。,40,4.3 路由器工作原理,网络层转发功能： 将分组从路由器的输入链路传送到适当的输出链路。路由器的体系结构：,输入端口,选路处理器,交换结构,输出端口,物

17、理层 数据 查找 链路层 转发,排队 数据 物理层缓存 链路层,41,输入端口,将一条物理链路端接到路由器的物理层；实现路由器的数据链路层功能；实现查找与转发功能，以便分组通过路由器交换结构转发到适当的输出端口；用于控制性分组从输入端口转发到选路处理器。 通常，路由器中的多个端口被集中到一块线路卡（line card）上。,42,交换结构,将路由器的输入端口连接到它的输出端口。完全包含在路由器中。,43,输出端口,存储经过交换结构转发给它的分组，并将分组发送到输出链路。完成与输入端口顺序相反的数据链路层和物理层功能。 对双向链路，输出端口与其输入端口通常在同一线路卡上成对出现。,44,选路处理

18、器,执行选路协议、维护选路信息和转发表以及执行路由器中的网络管理功能。 因特网路由器市场，Cisco公司主导产品。4.3.1 输入端口4.3.2 交换结构4.3.3 输出端口4.3.4 何时出现排队,45,4.3.1 输入端口,线路端接与数据链路处理： 实现与输入链路相关的物理层和数据链路层功能。查找转发,输入链路,线路端接,数据链路处理（协议、拆封）,查表、转发、排队,交换结构,46,查找/转发：,确定将一个到达的分组通过交换结构转发给哪个输出端口。 通过查找转发表实现。分散式转发：选路处理器计算转发表，给每个输入端口存放一份拷贝，能随选路更新。在每个输入端口本地做出交换决策，无须激活中央选

19、路处理器。可避免在路由器中某个单点产生转发处理瓶颈。,47,集中式转发：路由器的输入端口处理能力有限；直接将分组转发给中央选路处理器，查找转发表并将分组转发到适当的输出端口。 如，将工作站或服务器用作路由器时，采用此法。选路处理器就是CPU，输入端口是一块网络接口卡。,48,查表速度：,查表：搜索转发表，查找最长匹配的表项，若无相应表项找出默认选路表项。 查找速度：受许多因素影响，如路由器速度、链路速率、查找算法等。目标：输入端口的处理速度要超过线路速度。 即完成一次查找的时间应少于从输入端口接收一个分组所需的时间（对收到的分组的输入处理在下一个接收操作结束之前完成）。 如，对运行速率为2.5

20、Gbit/s的OC48链路，若分组长256B，查找速度大约为每秒一百万次。,减少排队,51.2M48,49,查找方法：,线性查找：按顺序找。对庞大的转发表不合适。 二分查找：将转发表表项存放在一个树形数据结构中。 树的每一层对应目的地址的一个比特，查找某个地址时，从树的根节点开始，依次查地址的每一位。 内容可寻址内存(CAM)：将一个32bit IP地址提交给CAM，由它以常数时间返回该地址对应的转发表表项内容。如，Cisco8500系列。 将最近被访问的表项保存在高速缓存(cache)中：,50,二分查找：,第一比特： 0：左子树包含与该目的地址对应的转发表表项； 1：表项在右子树中。 下一

21、比特： 0，选择初始子树的左子树； 1，选择初始子树的右子树。 N步之内可找到相应的转发表表项（N是地址的位数，地址空间为2N）。 如，因特网32bit IP地址需32步。,0,0,1,1,0,1,00 01 10 11,51,输入端口问题,分组阻塞 (blocked)： 来自其他输入端口的分组当前正在使用交换结构。 被阻塞的分组必须在输入端口处排队，等待以后调度通过交换结构。,52,4.3.2 交换结构,内存,总线,纵横制,将分组从输入端口交换（转发）到输出端口中。,53,1、经内存交换,早期用计算机作为路由器输入端口与输出端口之间的交换由CPU(选路处理器)控制完成；输入端口与输出端口类似

22、I/O设备： 当分组到达输入端口时，通过中断向选路处理器发出信号，将分组拷贝到处理器内存中； 选路处理器根据分组中的目的地址查表找出适当的输出端口，将该分组拷贝到输出端口的缓存中。,54,输入端口,输出端口,内存,系统总线,转发速度,受内存带宽的速度限制 (每个分组穿过两次总线) 若内存带宽为每秒写入或读出B个分组，则总的转发吞吐量 (分组从输入端口被传送到输出端口的总速率)小于B/2。,55,现代路由器 由输入线路上的处理器来执行目的地址的查找，并将分组存储(交换)进适当的存储位置。 类似共享内存的多处理机，用一个线路卡上的处理器将分组存储进适当输出端口的内存中。 如，Cisco 8500。

23、,56,2、经总线交换,输入端口通过一条共享总线将分组直接传送到输出端口，不需要选路处理器的干预。,总线,每次只能有一个分组通过总线传送。 分组到达一个输入端口时，若总线正忙，会被暂时阻塞，在输入端口排队 路由器交换带宽受总线速率限制。,57,3、经交换矩阵交换,纵横式交换机：由2n条总线组成，n个输入端口与n个输出端口连接。 到达输入端口的分组沿水平总线穿行，直至与所希望的输出端口的垂直总线交叉点：若该条垂直总线空闲，则分组被传送到输出端口；否则，该到达的分组被阻塞，必须在输入端口排队。,高级设计: 数据报分割成固定长度信元, 通过交换矩阵来交换信元,58,4.3.3 输出端口,取出存放在输

24、出端口内存中的分组，并将其传输到输出链路上。 当交换结构将分组交付给输出端口的速率超过输出链路速率，就需要排队与缓存管理功能。,交换结构,排队：缓存管理,数据链路处理(协议、解封),线路端接,59,4.3.4 何时出现排队,输入端口和输出端口都会形成分组队列。当队列逐步增长，路由器缓存空间满，会出现分组丢失 (packet loss)，在输入端口队列或输出端口队列。丢失具体位置，取决于流量负载、交换结构的相对速度、线路速度等因素。假定：输入线路速率与输出线路速率相同有n个输入端口和n个输出端口交换结构速率：将分组从输入端口移动到输出端口的速率。,60,1、输入端口不排队,若交换结构的速率至少是

25、输入线路速率的n倍，在输入端口处不会出现排队。 最坏情况：有n条输入线路同时接收分组。 交换结构可以在每个输入端口(同时)接收一个分组的时间内将n个分组从输入端口传送到输出端口。,n条,n条,n倍,接收,转发,61,2、输出端口排队,设交换结构的速率至少是线路速率的n倍。最坏情况：到达每个输入端口的分组都被发往同一个输出端口。在一个单位时间（接收或发送一个分组）内，将有n个分组到达该输出端口，排队(等待)发送到输出链路上；在发出队列中一个分组的时间内，又有n个分组到达。 依此类推，最终排队的分组快速增长，很快占满输出端口的存储空间，使后续分组被丢弃。,62,例,假定：线路速度相同，交换结构处理

26、速度是线路速度的三倍。,交换结构,交换结构,在时间t输出端口竞争,一个分组时间以后,t时刻：每个输入端口都到达一个分组，都发往最上侧的输出端口。 一个单位时间后（接收或发送一个分组的时间）： 三个原始分组都被传送到输出端口，并排队等待发送。 又有两个新分组到达交换结构的输入端，其中的一个分组要发往最上侧 的输出端口。下一个单位时间：三个分组中的一个通过输出链路发送出去。,63,分组调度程序,在输出端口排队的分组中选出一个发送。原则：先来先服务FCFS：简单。加权公平排队WFQ：在具有排队分组的不同端到端连接之间公平地共享输出链路。,64,分组丢弃方法：,若缓存已满，丢弃分组。丢弃后到的分组（弃

27、尾）；删除一个或多个已排队的分组； 活动队列管理AQM算法：在缓存填满前丢弃分组或首部加标记，向发送方提供拥塞信号。 如，随机早期检测RED算法： 输出队列长度维护一个加权平均值。,65,随机早期检测RED算法：,设最小阈值minth和最大阈值maxth平均队列长度小于最小阈值minth，到达分组被纳入队列；队列满或平均队列长度大于最大阈值maxth ，到达分组被标记或丢弃；平均队列长度在minth， maxth之间，到达分组以某种概率被标记或丢弃。,66,3、输入端口分组排队：,交换结构比输入端口总和的速度慢 输入队列产生排队 交换结构不够快，即相对于输入线路速度不能快得使所有到达的分组无延

28、迟地通过它传送，则在输入端口出现分组排队，以等待通过交换结构传送到输出端口。,67,如，采用纵横式交换结构, 假定：所有链路速度相同；交换结构速率与输入链路速率相同：分组从输入端口传送到给定输出端口的时间与从输入链路接收一个分组的时间相同；分组按FCFS方式从输入队列移动到输出队列中。 结果：分组输出端口不同：多个分组可以被并行传送。发往相同输出端口：不同输入队列中的分组发往同一输出队列，其中的一些分组被阻塞，在输入队列中等待（交换结构一次传一个分组到端口）。,68,例,不同输入队列前端的两个分组要发往右上角的同一输出端口。若先发送左上角队列前端的分组，左下角队列中的分组要等待，左下角队列中排

29、在该分组后面的分组也要等待线头HOL (head-of-the-line)阻塞： 输入队列中后面的分组被位于线头的一个分组阻塞(即使输出端口空闲的)，等待通过交换结构发送。,时间t：输出端口竞争，仅一个红色分组能被传输,时间t1：绿色分组经历了HOL阻塞,交换结构,69,4.5 选路算法,分组通过路由器转发，每个路由器都有一张转发表，选路算法决定转发表内容。选路：确定分组从发送方传送到接收方所要通过的路径（路由）。数据报服务：在给定源和目的地之间传输不同分组可能采用不同的路由。虚电路服务：在给定源和目的地之间的所有分组采用同一路径。,70,概念,默认路由器 ：与主机直接相连的一台路由器，又叫第

30、一跳路由器。 每当主机发送一个分组时，都先传送给它的默认路由器。 源路由器：源主机的默认路由器。 目的路由器：目的主机的默认路由器。 从源主机到目的主机的选路归结为从源路由器到目的路由器的选路。,H2,R1,R2,默认路由器,71,选路算法：,确定一个分组从源路由器到目的路由器所经路径的算法。 即在给定的一组路由器以及连接路由器的链路中，找到一条从源路由器到目的路由器的“好”路径。“好”路径：具有“最低费用”的路径。 由许多因素决定，如链路长度、传播时延、价格等。,72,网络的抽象图模型：,用“节点图”表示网络的结构。 图G = (N，E)表示N个节点和E条边的集合，每条边是来自N的一对节点。

31、节点：表示路由器(做出分组转发判决的点)。 如u，v，w，x，y，z。 边：连接节点的线段，表示路由器之间的物理链路。 如(u，v)、 (u，x) 、(u，w)、,73,边的值（费用）,表示对应链路的物理长度、或链路速度、或与链路相关的费用。约定： c(x，y) 表示节点x和节点y之间边的费用（从节点x到节点y的链路费用）。 若节点x与节点y直接相连（x与y是邻居） 则c(x，y )= 链路费用 如c(u，v) = 2，节点u与节点v互为邻居 若节点x与节点y不直接相连（x与y不是邻居） 则c(x，y) = 如c(u，y) = ，c(u，z) = c(x，y)= c(y，x) 如c(u，v)

32、= c(v，u) =2,选路算法：根据给定的网络抽象图，找出从源节点到目的节点间的最低费用路径。,74,路径,路径表示：用路径上的节点来描述。 如图G = (N，E)中的一条路径，是一个节点序列(x1,x2,xp)，其中每个相邻节点x1,x2,xp依次连成边。 路径(x1,x2,xp)费用：沿途所有边的费用之和。即 c(x1,x2) + c(x2,x3) + +c(xp-1,xp) 通常，任意两个节点x和y 之间有多条路径，费用不一定相同。 最低费用路径 ：该路径上链路费用之和最小。 若所有链路费用相同，则最低费用路径就是最短路径 ，即在源和目的地之间经过链路最少的路径。,75,例,如图，源节

33、点u和目的节点w之间的最低费用路径：,(u,x,y,w) ，费用为3。,76,选路算法分类：,根据算法是全局性还是分散性划分根据算法是静态还是动态划分根据对负载是否敏感划分因特网常用的两种选路算法： 动态全局链路状态算法 动态分散式距离向量算法4.5.1 链路状态选路算法4.5.2 距离向量选路DV算法4.5.3 层次选路,77,全局选路算法,用完整的、全局性的网络信息来计算最低费用路径。即以所有节点之间的连通性及所有链路的费用为条件。 在开始计算前，以某种方式获得这些信息。 可在单个位置计算，也可在多个位置上复制。 拥有连通性和链路费用的完整信息。链路状态算法LS：必须知道网络中每条链路的费

34、用。,78,分散式选路算法,以迭代的、分布式的方式计算最低费用路径。 节点只有与其直接相连链路的费用信息：不需拥有所有网络链路费用的完整信息。 通过迭代计算过程并与相邻节点(邻居节点)交换信息 逐步计算出到达某目的节点或一组目的节点的最低费用路径。 距离向量算法DV：每个节点维护到网络中所有其他节点的费用（距离）的估计向量。,79,静态选路算法： 路由确定后基本不再变化。当人工干预调整时，可能有一些变化。 动态选路算法： 当网络的流量负载或拓扑发生变化时，改变路径。 可以周期性地或直接地响应拓扑或链路费用的变化。易受选路循环、路由振荡之类问题的影响。,80,负载敏感算法： 链路费用会动态地变化

35、，反映出底层链路的当前拥塞水平。 如果当前拥塞的一条链路被赋以高费用，则选路算法应绕开该拥塞链路来选择路由。 如早期的ARPAnet选路算法。负载迟钝算法： 某条链路的费用一般不反映其当前的(或最近的)拥塞级别。 如因特网的选路算法。,81,4.5.1 链路状态选路算法,前提条件：已知网络拓扑和所有链路的费用，作为算法的输入。获取方法：每个节点向网络中广播链路状态分组（含有它所连接的链路的费用）。 由链路状态广播算法实现。最终使所有节点都有一个相同且完整的网络视图。每个节点都可以运行链路状态算法并计算出最低费用路径集。,82,Dijkstra最低费用路径算法（最短通路算法）,计算从某节点（源节

36、点，如u）到网络中所有其他节点的最低费用路径。是一种迭代算法，即： 经第k次迭代后，可知道到k个目的节点的最低费用路径。基本思想： 以源节点为起点，每次找出一个到源节点的费用最低的节点，直到把所有的目的节点都找到为止。,83,符号定义：,c(x,y): 从节点x到y的链路费用; = 如果不是直接邻居D(v) ：从源节点到目的节点v的当前费用 ；p(v)： 从源节点到节点v的路径上的前一节点(节点v的邻居)；N： 节点集合，从源节点到这些节点的最低费用路径已被求出。,u,x,y,w,v,84,Dijsktra算法组成,由一个初始化步骤和其后的循环组成。循环执行的次数与网络中的节点个数（除源节点）

37、相同。结束时，算出从源节点到网络中所有其他节点的最短路径。,85,算法,1 初始化: 2 N = u 3 对所有节点v 4 if v 临近 u 5 then D(v) = c(u,v) 6 else D(v) = 78 Loop 9 找出w不在N中使得D(w)最小 10 将w加入N 11 对于所有v临近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/ 15 until 所有节点在 N中,86,算法描述：,（1）初始化（1#6#） N =源节点u； 对所有不在N

38、中的节点v，标出其D(v)值：节点v与源节点u直接相连，D(v) = c(u，v) 节点v与源节点u不直接相连 ，D(v) = ,1 初始化: 2 N = u 3 对所有节点v 4 if v 临近 u 5 then D(v) = c(u,v) 6 else D(v) = ,87,（2）找出一个到源节点的费用最低的节点w，并以此更新其它点D(v) 值从不在N 中的节点中找出一个D(w)值最小的节点w，并将w加入到N 中。(9#10)对不在N 中，但与节点w是邻居的节点v，用新的值更新 D(v)=minD(v)，D(w)+c(w,v) 将节点v原值与节点v现经节点w到源节点的值比较，取小值。（3）

39、重复步骤(2) 直到所有的网络节点都在N 中为止。,8 Loop 9 找出w不在N中使得D(w)最小 10 将w加入N 11 对于所有v临近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/ 15 until 所有节点在 N中,88,例,计算从u到所有可能目的节点的最低费用路径。计算过程如表4-3，表中的每一行表示一次迭代结束时的算法变量值。,89,步骤0,Nu,D(v),p(v)2,u,D(w),p(w)5,u,D(x),p(x)1,u,D(y),p(y),D(

40、z),p(z) 4,y,D(w)：min(5，1+3)=4,D(y)：min(，1+1)=2,2,u 4,x 2,x ,2,u 3,y 4,y,3,y 4,y,1 ux,2 uxy,3 uxyv,4 uxyvw,5 uxyvwz,90,构建从源节点到所有目的节点的路径,对于每个节点，都得到从源节点沿着它的最低费用路径的前一节点；每个前一节点，又可得到它的前一节点；以此继续，可以得到到所有目的节点的完整路径。 如节点z的前一节点依次为： zyxu 得出从源节点u到节点z的最低费用路径为：uxyz，费用为4。,91,2,u 4,x 2,x ,u,根据目的节点的找出顺序和其费用以及前一节点，可以画出

41、源节点u到所有目的节点的最低费用路径树。,根据得到的所有目的节点的完整路径，或最低费用路径树，可以生成源节点的转发表。 转发表：存放从源节点到每个目的节点的最低费用路径上的下一跳节点。 即指出对于发往某个目的节点的分组，从该节点发出后的下一个节点。,92,默认路由 * ： 表示所有具有相同“下一跳”的表项。即将“下一跳”相同的项合并为一项，目的节点用“*”表示。优先级最低，转发分组时，当找不到对应表项时，才使用默认路由。,节点u的转发表目的点下一跳 u vv wx xx yx zx,节点u的转发表目的点下一跳uvv*x,将网络中每一个节点作为源点，分别用上述方法计算，可以得到每一个节点的转发表

42、。,2,1,2,1,1,u,y,x,w,v,z,93,算法的计算复杂性：,设n个节点(除源节点)，最坏情况下要经多少次计算才能找到从源节点到所有目的节点的最低费用路径?第一次迭代：搜索所有的n个节点以确定最低费用节点第二次迭代：检查n-1个节点；第三次：检查n-2个节点； 依次类推。 所有迭代中需要搜寻的节点总数为n(n+1)/2。算法复杂性为n平方阶序O(n2)。,94,LS算法的缺陷：,可能产生“振荡”。例图4-26,一个简单网络拓扑。设：链路费用等于链路上的负载；链路费用是非对称的： c(u，v)与c(v，u)仅当在链路(u，v)两个方向的负载相同时才相等。有三个同时发往w的注入流量：节

43、点z：一个单元；节点x：一个单元；节点y：e的流量。,e,1,1,95,初始： 图(a)，其链路费用相当于承载的流量第一次： 节点x、y都确定顺时针方向到w的路径费用最低，为1。产生图(b)费用。第二次： 节点x、y、z都确定逆时针方向到w的路径费用最低，为0。产生图(c)费用。第三次： 节点x、y、z都确定顺时针方向到w的路径费用最低，为0。产生图(d)费用。,1,1+e,e,0,e,1,1,0,0,(a),(b),(c),e,(d),e,96,避免振荡：,使链路费用不依赖于所承载的流量：不可行；避免所有的路由器同时运行LS算法：比较合理。 既使路由器以相同周期运行LS算法，在每个节点上算法

44、的执行时刻也不同。因特网的自同步： 既使路由器初始时以同一周期但不同时刻执行算法，算法执行时刻最终会同步并保持。 采用随机时间的方法，即每台路由器随机发送链路通告。,97,4.5.2 距离向量选路DV算法,是一种迭代的、异步的和分布式的算法。分布式：每个节点都从其直接相连邻居接收信息，进行计算，再将计算结果分发给邻居。迭代：计算过程一直持续到邻居之间无更多信息交换为止。自我终结：算法能自行停止。异步：不要求所有节点相互之间步伐一致地操作。,98,最低费用表示：,dx(y)：节点x到节点y的最低费用路径的费用。用Bellman-Ford方程表示 dx(y) = minvc(x,v)+ dv(y)

45、 （4-1）c(x,v)+ dv(y)：x与某个邻居v之间的直接链路费用c(x，v)加上邻居v到y的最小费用。即x经v到节点y的最小的路径费用。minv ：从所有经直接相连邻居到节点y的费用中选取的最小路径费用。,99,例如图4-25,源节点u到目的节点z的最低费用路径。源节点u有三个邻居：邻居v：dv(z) = 5 、 c(u,v) = 2邻居w：dw(z) = 3 、 c(u,w) = 5邻居x：dx(z) = 3 、 c(u,x) = 1 du(z) = min c(u,v) + dv(z), c(u,w) + dw(z) , c(u,x) + dx(z) = min2+5， 5+3，1

46、+3 = 4 即源节点u经相邻节点x到目的节点z的路径费用最低，为4。,得到节点u的转发表中到目的节点z的下一跳是节点x,100,DV算法基本思想：,设Dx(y)：节点x到N中某个节点y的估计费用；Dx：节点x的距离向量。Dx = Dx(y)：y在N中，即节点x到N中所有其他节点y的估计费用。 基本思想： 每个节点有一张选路表（距离表），维持选路数据，随着算法进行，不断更新，直到静止。节点x选路表更新选路表的距离向量当距离向量不再变化，算法静止,101,节点x选路表,节点x选路表（距离表）:行：该节点的距离向量Dx和其邻居的距离向量Dv列：所有目的节点。 节点x的距离向量Dx ，即节点x到每个

47、目的节点y的估计费用； Dx = Dx(y)：y在N中节点x每个邻居的距离向量Dv ，即x的邻居v到每个目的节点y的估计费用，Dv = Dv(y)：y在N中,DxDyDz,邻居,102,更新其距离向量,每个节点不断向邻居发送其距离向量拷贝；当节点x收到一个邻居v的新距离向量，先保存，并用公式（4-1）更新自己的距离向量： Dx(y) = minvc(x,v)+ Dv(y) 从所有经邻居v到节点y的费用中选取最小路径费用。若距离向量发生改变，将新的距离向量通知给邻居。,103,当距离向量不再变化，算法静止,此时Dx(y)收敛到dx(y)，即得到节点x到节点y的最低费用路径。,104,1、距离向量

48、DV算法描述：2、链路费用改变与链路故障3、增加“毒性逆转 4、LS算法与DV算法比较5、其他选路算法,105,1、距离向量DV算法描述：,对每个节点x（1）初始化：（2）更新自己的距离向量 （3）重复执行（2），直到没有更新的距离向量发出,等待 (收到本地链路代价变化或邻居来距离矢量更新)重新计算距离矢量如果到任何目的节点的距离矢量发生变化, 通知邻居,初始化,106,距离矢量算法:,1 Initialization: 2 for all destinations y in N: 3 Dx (y) = c( x, y ) /* if y is not a neighbor then c( x

49、, y )= */ 4 for each neighbor w5 Dw (y) = for all destinations y in N6 for each neighbor w7 send DV Dx = Dx (y) :y in N to w,在所有的节点, X:,9 loop 10 wait (until I see a link cost change to neighbor w or 11 until I receive update from neighbor w) 13 for each y in N: Dx(y) = c(x,v) + Dv(y) 16 if Dx(y) ch

50、anged for any destination y 17 Send DV Dx = Dx (y) : y in N to all neighbors 19 forever,初始化,107,（1）初始化：,计算节点x到所有目的点y的距离向量Dx(y) 若目的点y是节点x的邻居，则Dx(y) = c(x,y ) 否则，Dx(y)= （2#3#）节点x的每一个邻居w到所有目的点y的距离向量为 Dw(y) = （4#5#）把节点x的距离向量Dx = Dx(y)：y在N中 （节点x到每个目的节点y的估计费用）发给每一个邻居w（6#7#）,1 Initialization: 2 for all des