第第4章章 网络层网络层q运输层：运输层：接受网络层提供的接受网络层提供的主机到主机的通信主机到主机的通信服务。服务。为主机上的为主机上的两两个进程之间提供通信个进程之间提供通信服务。服务。 运输层只在网络的主机中出现；运输层只在网络的主机中出现；网络层在网络的主机和路由器中出现。网络层在网络的主机和路由器中出现。 本章主要讨论本章主要讨论网络层如何实现主机网络层如何实现主机到主机的通信服务到主机的通信服务。应用层运输层网络层链路层物理层1主要内容主要内容网络层功能网络层功能和服务：虚电路和数据报；和服务：虚电路和数据报；路由器结构：路由器结构：分组转发分组转发；网络层的网络层的选路选路：决定分组从源到目的地所经路径的一：决定分组从源到目的地所经路径的一些选路算法。些选路算法。4. 1 概述概述4.2 虚电路和数据报网络虚电路和数据报网络4.3 路由器的构成路由器的构成4.4 IP 协议协议4.5 选路算法选路算法4.6 因特网的选路因特网的选路4.7 广播和多播广播和多播小结小结24. 1 概述概述r发送方主机网络层的作用：发送方主机网络层的作用：将来自运输层的每个报文段将来自运输层的每个报文段封装成一个数据报（网络层封装成一个数据报（网络层分组）；分组）；将数据报向目的地发送，即将数据报向目的地发送，即向相邻的路由器向相邻的路由器R1发送。发送。networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH1H2R1R23r接收方主机网络层的作用：接收方主机网络层的作用：接收接收来自相邻的路由器来自相邻的路由器R2的的数据报；数据报；解封出报文段，并交付给其解封出报文段，并交付给其运输层。运输层。 networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH1H2R1R2路由器的主要作用：路由器的主要作用： 将数据报将数据报从输入链路从输入链路“转发转发”到输出链路。到输出链路。 通常路由器只实现通常路由器只实现下三层部分下三层部分4.1.1 转发和选路转发和选路4.1.2 网络服务模型网络服务模型 41、网络层功能、网络层功能将分组从发送主机移动到接收主机。将分组从发送主机移动到接收主机。主要包括：主要包括：转发：转发： 当一个分组到达某个路由器的当一个分组到达某个路由器的输入链路时，该路由器必须将其移输入链路时，该路由器必须将其移动到合适的输出链路。动到合适的输出链路。 与路由器的与路由器的内部结构内部结构有关。有关。选路：选路： 确定分组从发送方流向接收方确定分组从发送方流向接收方时所经过的路由或路径。时所经过的路由或路径。 通过通过选路算法选路算法计算路径。计算路径。networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH2R1R25两者区别：两者区别：转发：转发：将分组从路由器的一个输入链路接口转移到一将分组从路由器的一个输入链路接口转移到一个合适的输出链路接口的个合适的输出链路接口的本地动作本地动作。 只涉及分组在路由器中从入链路到出链路的传只涉及分组在路由器中从入链路到出链路的传送送选路：选路：指分组从源到目的地的端到端路径的指分组从源到目的地的端到端路径的网络范围网络范围动作动作。 涉及网络中的所有路由器，集体经选路协议涉及网络中的所有路由器，集体经选路协议交互，决定分组从源到目的地的路径。交互，决定分组从源到目的地的路径。类比类比汽车旅行汽车旅行: :选路选路: : 从起点到目的终点计划行程的过程。从起点到目的终点计划行程的过程。转发转发: : 通过单个立交桥的过程通过单个立交桥的过程62、路由器如何转发分组、路由器如何转发分组转发表：转发表：每台路由器有一张。每台路由器有一张。分组首部分组首部（目的地址或某个连接标识）和（目的地址或某个连接标识）和相应相应输出链路输出链路的对照表。的对照表。 转发表的转发表的内容由选路算法决定内容由选路算法决定（集中式或分布（集中式或分布式）。式）。71230111到达分组首部的值选路算法选路算法本地转发表本地转发表首部值首部值输出链路输出链路01000101011110013221转发方法：转发方法： 路由器根据到达路由器根据到达分组的分组的首部值首部值在转发在转发表中查询，找到相应表中查询，找到相应的输出链路接口，并的输出链路接口，并将分组转发出去。将分组转发出去。83、术语、术语r分组交换机：分组交换机：一台通用分组交换设备，根据一台通用分组交换设备，根据分组首部分组首部值值，从输入链路接口到输出链路接口传送分组。，从输入链路接口到输出链路接口传送分组。链路层交换机：链路层交换机：根据根据链路层字段值链路层字段值作转发决定的分组作转发决定的分组交换机。交换机。路由器：路由器：根据根据网络层字段值网络层字段值作转发决定的分组交换机。作转发决定的分组交换机。94、连接建立、连接建立运输层连接：运输层连接：如如TCP协议，在数据实际传输之前，需协议，在数据实际传输之前，需要要发送方和接收方经过三次握手发送方和接收方经过三次握手建立所需的状态信息。建立所需的状态信息。网络连接：网络连接：指网络层数据分组开始传输前，在所选择指网络层数据分组开始传输前，在所选择的从源到目的地的从源到目的地路径上的各路由器之间相互握手路径上的各路由器之间相互握手，建，建立连接状态。立连接状态。 如如ATM、帧中继的网络层。、帧中继的网络层。 因特网网络层不执行连接建立。使用因特网网络层不执行连接建立。使用IP协议！协议！104.1.2 网络服务模型网络服务模型r问题：问题：发送主机的发送主机的运输层是否能依靠网络层运输层是否能依靠网络层将分组交付到目将分组交付到目的地；的地；多个分组多个分组是否能按发送顺序交付是否能按发送顺序交付给接收主机的运输层；给接收主机的运输层；传输两个连续分组的传输两个连续分组的时间间隔时间间隔是否与接收到的时间间是否与接收到的时间间隔相同；隔相同；网络层网络层是否能提供网络拥塞是否能提供网络拥塞的反馈信息；的反馈信息；连接发送与接收主机的运输层通道的抽象视图（特性）连接发送与接收主机的运输层通道的抽象视图（特性）是什么？是什么？ 由网络层提供的服务模型来确定由网络层提供的服务模型来确定。11网络服务模型网络服务模型 ： 定义在网络的一侧定义在网络的一侧“边缘边缘”到另一侧到另一侧“边边缘缘”之间（即在发送与接收端系统之间）之间（即在发送与接收端系统之间）端到端到端的数据运输特性。端的数据运输特性。121、网络层可能提供的服务、网络层可能提供的服务确保交付：确保交付：确保分组到达目的地。确保分组到达目的地。具有时延上界的确保交付：具有时延上界的确保交付：主机到主机的时延。主机到主机的时延。有序分组交付：有序分组交付：按发送顺序到达。按发送顺序到达。确保最小带宽：确保最小带宽：当发送主机以低于特定比特率的速率当发送主机以低于特定比特率的速率发送比特，分组不会丢失，在一定时延到达。发送比特，分组不会丢失，在一定时延到达。确保最大时延抖动：确保最大时延抖动：发送方发送两个连续分组的时间发送方发送两个连续分组的时间间隔与接收到的间隔相同。间隔与接收到的间隔相同。132、因特网网络层提供的服务、因特网网络层提供的服务 单一的服务，即单一的服务，即尽力而为服务尽力而为服务(best-effort service)，类似于，类似于“根本无服务根本无服务”。分组间的分组间的定时定时不能被保证；不能被保证；分组的接收分组的接收顺序顺序与发送顺序不一定相同；与发送顺序不一定相同；传送的分组传送的分组不能保证最终交付不能保证最终交付，即网络可能未向目的，即网络可能未向目的地交付分组。地交付分组。143、ATM服务模型服务模型 提供多重的服务模型，即提供多重的服务模型，即在同一网络中为不同的连在同一网络中为不同的连接提供不同类别的服务接提供不同类别的服务。r恒定比特率恒定比特率CBR (Costant bit rate)服务：服务： 标准的标准的ATM服务模型。适用于实时、恒定比特率服务模型。适用于实时、恒定比特率的音频和视频流。的音频和视频流。服务目标：服务目标：使网络连接看起来就像在发送主机和接收主机之间有使网络连接看起来就像在发送主机和接收主机之间有一条专用的固定带宽的传输链路。一条专用的固定带宽的传输链路。ATM信元传输时的端到端时延可变性信元传输时的端到端时延可变性(时延抖动时延抖动)及丢及丢失、迟交的信元都保证在规定值以下。失、迟交的信元都保证在规定值以下。15r可用比特率可用比特率ABR (Available bit rate)服务服务 “比尽力服务稍好一点比尽力服务稍好一点”的服务。的服务。可能会丢失信元，但不能被重排序可能会丢失信元，但不能被重排序 ；保证最小信元传输速率保证最小信元传输速率 (MCR)，或比，或比MCR更高（有足更高（有足够空闲资源）；够空闲资源）；能够为发送方提供反馈信息。能够为发送方提供反馈信息。16网络层服务模型网络层服务模型:网网络体系体系结构构服服务模型模型带宽保保证无无丢失保失保证排序排序定定时拥塞指示塞指示因特网因特网尽力而尽力而为 无无 无无任何可能任何可能的的顺序序不不维持持 无无ATMCBR保保证恒定恒定速率速率 是是有序有序维持持拥塞不出塞不出现ATMABR保保证最小速率最小速率 无无有序有序不不维持持提供提供拥塞塞指示指示174.2 虚电路和数据报网络虚电路和数据报网络r运输层：运输层：提供无连接服务和面向连接服务。提供无连接服务和面向连接服务。 如因特网的如因特网的UDP、TCP 。r网络层网络层：提供无连接服务和面向连接服务。提供无连接服务和面向连接服务。面向连接服务：源和目的主机之间先握手。面向连接服务：源和目的主机之间先握手。无连接服务：无握手过程。无连接服务：无握手过程。18区别：q网络层：网络层：向运输层提供的向运输层提供的主机到主机主机到主机的服务。的服务。 运输层：运输层：向应用层提供的向应用层提供的进程到进程进程到进程的服务。的服务。q网络层：网络层：任何网络中的网络层只提供两种服务之一，任何网络中的网络层只提供两种服务之一，不会同时提供。不会同时提供。虚电路网络虚电路网络：提供连接服务。：提供连接服务。数据报网络数据报网络：提供无连接服务。：提供无连接服务。q运输层：运输层：面向连接服务在网络边缘的面向连接服务在网络边缘的端系统中实现端系统中实现。 网络层：网络层：面向连接服务在面向连接服务在端系统及网络核心的路由器端系统及网络核心的路由器中实现中实现。19本节内容4.2.1 虚电路网络虚电路网络4.2.2 数据报网络数据报网络4.2.3 数据报和虚电路服务的由来数据报和虚电路服务的由来204.2.1 虚电路网络虚电路网络 如如X.25、帧中继和、帧中继和ATM等。等。 根据根据虚电路号虚电路号转发分组。转发分组。211、虚电路、虚电路VC 组成组成源和目的地之间的一条连接路径源和目的地之间的一条连接路径：一系列链路和路由：一系列链路和路由器；器；VC号号：该路径上每段链路的号码，每条链路上的：该路径上每段链路的号码，每条链路上的VC号可能不同；号可能不同； 路由器转发表中的表项路由器转发表中的表项：VC路径上每台路由器中都有路径上每台路由器中都有该表。该表。222、工作原理、工作原理在源和目的之间在源和目的之间创建一个创建一个VC；源向该源向该VC发送带有发送带有VC号的分组号的分组；每经过一台中间路由器，每经过一台中间路由器，用新的用新的VC号代替原号代替原VC号号： 从从VC号转发表获得；号转发表获得；分组在分组在每条链路上的每条链路上的VC号不同。号不同。依此规则，直到目的地。依此规则，直到目的地。23主机主机A与主机与主机B通信过程通信过程122232132VC号号接口号接口号: :路由器连接链路的接口号码路由器连接链路的接口号码 主机主机A与主机与主机B之间创建一条之间创建一条VC： 路径为路径为A R1 R2 B，3个链路分配个链路分配VC号号12、22和和32。 传输时，传输时，分组分组VC号变化过程：号变化过程： 12 22 32 A R1 R2 BABR1R2R3R4243、VC号转发表结构号转发表结构 入接口 入VC # 出接口 出VC #1 12 2 222 63 1 18 3 7 2 171 97 3 87 例，例，R1中的中的VC号转发表。号转发表。路由器维护连接状态信息路由器维护连接状态信息!122232132VC号号BR1R2R3R4AVC1VC2VC3VC425只要该路由器创建新的只要该路由器创建新的VC，其转发表中就增加一项；，其转发表中就增加一项；终止一个终止一个VC，其转发表中就删除对应项。，其转发表中就删除对应项。路由器必须为正在进行的连接路由器必须为正在进行的连接维护连接状态信息维护连接状态信息，直，直到该连接释放。到该连接释放。r每条链路采用不同每条链路采用不同VC号的优点：号的优点：减少分组首部减少分组首部VC字段的长度；字段的长度；简化虚电路的建立过程。简化虚电路的建立过程。26虚电路的三个阶段：虚电路的三个阶段：r虚电路建立：虚电路建立：在发送方与接收方之间建立一条虚电路，即在发送方与接收方之间建立一条虚电路，即决定所有分组要通过的一系列链路与路由器，并为每条链决定所有分组要通过的一系列链路与路由器，并为每条链路确定一个路确定一个VC号号。发送方与网络层联系，指定接收方地址，由网络建立虚电发送方与网络层联系，指定接收方地址，由网络建立虚电路路 (VC)。如图。如图4-4（14步）。步）。涉及到路径上每个路由器转发表的更新、资源的预留等。涉及到路径上每个路由器转发表的更新、资源的预留等。应用运输网络数据链路物理应用运输网络数据链路物理1. 发起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已连接27应用运输网络数据链路物理应用运输网络数据链路物理1. 发起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已连接5. 数据流开始6. 接收数据q数据传送：数据传送： 沿该虚电路传输数据分组（沿该虚电路传输数据分组（56步）。步）。q 虚电路拆除：虚电路拆除： 由其中一方通知其网络层终止该虚电路；由其中一方通知其网络层终止该虚电路； 通知网络另一侧的端系统呼叫结束，并更新路径上通知网络另一侧的端系统呼叫结束，并更新路径上每台路由器中的转发表。每台路由器中的转发表。28网络层与运输层连接建立区别r运输层的连接建立：运输层的连接建立： 只涉及两个端系统，相互协商通信并共同确定连只涉及两个端系统，相互协商通信并共同确定连接的参数。网络中的接的参数。网络中的路由器并不知道该运输层连接路由器并不知道该运输层连接。r网络层虚电路建立：网络层虚电路建立： 沿两个端系统之间路径上的路由器都要参与虚电沿两个端系统之间路径上的路由器都要参与虚电路的建立，且路的建立，且每个路由器都完全知道所经过的所有虚每个路由器都完全知道所经过的所有虚电路。电路。29信令报文：信令报文： 端系统向网络发送的指示端系统向网络发送的指示虚电路的启动与终止的虚电路的启动与终止的报文报文、以及路由器之间传递的用于、以及路由器之间传递的用于建立虚电路建立虚电路的报文的报文信令协议：信令协议：用来交换信令报文的协议。用来交换信令报文的协议。304.2.2 数据报网络数据报网络 如，因特网。如，因特网。r网络层无呼叫建立网络层无呼叫建立r路由器没有端到端连接的状态路由器没有端到端连接的状态m无网络级无网络级“连接连接”的概念的概念r分组分组使用目的主机地址转发使用目的主机地址转发m相同源和目的地的相同源和目的地的分组可能采用不同的路径分组可能采用不同的路径31传输过程传输过程r发送方给要发送的分组发送方给要发送的分组加上目的端系统地址加上目的端系统地址，并送入，并送入网络，经过若干网络，经过若干中间路由器转发分组中间路由器转发分组，直到目的地。，直到目的地。 应用运输网络数据链路物理应用运输网络数据链路物理1. 发送数据发送数据2. 接收数据接收数据32r路由器转发方法：路由器转发方法：根据到达分组的根据到达分组的目的地址在目的地址在转发表中查询转发表中查询，找到相应的输出链路接口，并，找到相应的输出链路接口，并将分组转发出去。将分组转发出去。r转发表：转发表：每台路由器有一张。每台路由器有一张。目的地址与链路目的地址与链路接口接口的映射表的映射表。 转发表中的表项数与地址位数有关，转发表中的表项数与地址位数有关，每个每个可能的地址对应一项可能的地址对应一项。 例，设目的地址例，设目的地址32位，位， 40亿可能的项。亿可能的项。 33转发表 目的地址范围目的地址范围 链路接口链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他其他 3例，某个路由器有例，某个路由器有4条链路（条链路（03），地址与链路接口关系：），地址与链路接口关系：是否可简是否可简化？化？34最长前缀匹配转发表 前缀匹配前缀匹配 链路接口链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 其他其他 335路由器查表方法：用用目的地址前缀目的地址前缀与与转发表的前缀转发表的前缀匹配：匹配：存在匹配存在匹配：向对应链路转发。：向对应链路转发。 如，目的地址如，目的地址 11001000 00010111 00010110 10100001 不存在匹配不存在匹配：选择：选择“其他其他”项对应的链路转发。项对应的链路转发。存在多个匹配存在多个匹配：使用最长前缀匹配规则，即向与最长：使用最长前缀匹配规则，即向与最长前缀匹配的链路接口转发分组。前缀匹配的链路接口转发分组。 如，目的地址如，目的地址 11001000 00010111 00011000 10101010 0#1#前缀匹配前缀匹配 链路接口链路接口11001000 00010111 00010 0 11001000 00010111 00011000 111001000 00010111 00011 2 其他其他 336说明路由器转发表只维持转发状态信息；路由器转发表只维持转发状态信息；转发表由选路算法修改（转发表由选路算法修改（15分钟更新）；虚分钟更新）；虚电路网络转发表随虚电路的建立和拆除更新。电路网络转发表随虚电路的建立和拆除更新。一个端系统发送给另一个端系统的一个端系统发送给另一个端系统的一批分组可一批分组可能在网络中选择不同的路径，到达的顺序可能能在网络中选择不同的路径，到达的顺序可能不一致。不一致。37虚电路服务虚电路服务源于电话产业界（采用源于电话产业界（采用“真正真正”电路）。电路）。呼叫建立及每次呼叫的状态要在网络中的路由呼叫建立及每次呼叫的状态要在网络中的路由器上维持，比面向数据报的网络要复杂。器上维持，比面向数据报的网络要复杂。网络功能复杂，端系统设备简单网络功能复杂，端系统设备简单。 38数据报服务由互连计算机的需求发展而来。与电话网相反。由互连计算机的需求发展而来。与电话网相反。网络层服务模型简单网络层服务模型简单。端系统功能复杂端系统功能复杂：高层实现许多功能，如按序传送、可：高层实现许多功能，如按序传送、可靠数据传输、拥塞控制与靠数据传输、拥塞控制与DNS名字解析等；名字解析等；r带来的结果：带来的结果：因特网服务模型提供的服务保证最少（可能没有！），因特网服务模型提供的服务保证最少（可能没有！），对网络层的需求最小，使得对网络层的需求最小，使得互连使用各种不同链路层技互连使用各种不同链路层技术的网络变得更加容易术的网络变得更加容易。许多应用都在位于网络边缘的主机（服务器）上实现。许多应用都在位于网络边缘的主机（服务器）上实现。394.3 路由器工作原理路由器工作原理r网络层转发功能：网络层转发功能： 将分组从路由器的输入链路传送到适当的输出链路。将分组从路由器的输入链路传送到适当的输出链路。r路由器的体系结构：路由器的体系结构：输入端口输入端口选路处理器选路处理器交换结构交换结构输出端口输出端口物理层物理层 数据数据 查找查找 链路层链路层 转发转发 排队排队 数据数据 物理层物理层缓存缓存 链路层链路层 40输入端口输入端口将一条将一条物理链路端接到路由器物理链路端接到路由器的物理层；的物理层；实现路由器的实现路由器的数据链路层功能数据链路层功能；实现实现查找与转发功能查找与转发功能，以便分组通过路由器交换结构，以便分组通过路由器交换结构转发到适当的输出端口；转发到适当的输出端口；用于控制性分组从输入端口转发到选路处理器。用于控制性分组从输入端口转发到选路处理器。 通常，路由器中的多个端口被集中到一块通常，路由器中的多个端口被集中到一块线路卡线路卡（line card）上。上。41交换结构交换结构 将路由器的输入端口连接到它的输出端口。将路由器的输入端口连接到它的输出端口。完全包含在路由器中。完全包含在路由器中。42输出端口输出端口存储存储经过交换结构经过交换结构转发给它的分组转发给它的分组，并将分组，并将分组发送到发送到输出链路。输出链路。完成与输入端口顺序相反的完成与输入端口顺序相反的数据链路层和物理层功能。数据链路层和物理层功能。 对双向链路，输出端口与其输入端口通常在同一对双向链路，输出端口与其输入端口通常在同一线路卡上成对出现。线路卡上成对出现。43选路处理器选路处理器 执行执行选路协议、维护选路信息和转发表选路协议、维护选路信息和转发表以及执行以及执行路由器中的网络管理功能。路由器中的网络管理功能。 因特网路由器市场，因特网路由器市场，Cisco公司主导产品。公司主导产品。4.3.1 输入端口输入端口4.3.2 交换结构交换结构4.3.3 输出端口输出端口4.3.4 何时出现排队何时出现排队444.3.1 输入端口输入端口线路端接与数据链路处理：线路端接与数据链路处理： 实现与输入链路相关的物理层和数据链路层功能。实现与输入链路相关的物理层和数据链路层功能。查找转发查找转发输入链路输入链路线路端接线路端接数据链路处理数据链路处理（协议、拆封）（协议、拆封）查表、转发、排队查表、转发、排队交换交换结构结构45查找查找/转发：转发： 确定确定将一个到达的分组通过交换结构转发给哪个将一个到达的分组通过交换结构转发给哪个输出端口输出端口。 通过通过查找转发表查找转发表实现。实现。q分散式转发：分散式转发：选路处理器计算转发表，给选路处理器计算转发表，给每个输入端口存放一份拷每个输入端口存放一份拷贝贝，能随选路更新。，能随选路更新。在每个输入端口本地做出交换决策在每个输入端口本地做出交换决策，无须激活中央选，无须激活中央选路处理器。路处理器。可避免在路由器中某个可避免在路由器中某个单点产生单点产生转发处理瓶颈。转发处理瓶颈。46r集中式转发：集中式转发：路由器的输入端口处理能力有限；路由器的输入端口处理能力有限；直接将分组转发给中央选路处理器直接将分组转发给中央选路处理器，查找转发表并将，查找转发表并将分组转发到适当的输出端口。分组转发到适当的输出端口。 如，将工作站或服务器用作路由器时，采用此法。如，将工作站或服务器用作路由器时，采用此法。选路处理器就是选路处理器就是CPU，输入端口是一块网络接口卡。，输入端口是一块网络接口卡。47查表速度：查表速度：r 查表：查表：搜索转发表，搜索转发表，查找最长匹配的表项查找最长匹配的表项，若无相应，若无相应表项找出默认选路表项。表项找出默认选路表项。r 查找速度：查找速度：受许多因素影响，如路由器速度、链路速受许多因素影响，如路由器速度、链路速率、查找算法等。率、查找算法等。r目标：目标：输入端口的处理速度要超过线路速度输入端口的处理速度要超过线路速度。 即即完成一次查找的时间应少于从输入端口接收一个完成一次查找的时间应少于从输入端口接收一个分组所需的时间分组所需的时间（对收到的分组的输入处理在下一个接（对收到的分组的输入处理在下一个接收操作结束之前完成）。收操作结束之前完成）。 如，对运行速率为如，对运行速率为2.5Gbit/s的的OC48链路，若分组长链路，若分组长256B，查找速度大约为每秒一百万次。，查找速度大约为每秒一百万次。减少排队减少排队51.2M4848查找方法：查找方法：r 线性查找：线性查找：按按顺序找顺序找。对庞大的转发表不合适。对庞大的转发表不合适。r 二分查找：二分查找：将转发表表项存放在一个树形数据结构中。将转发表表项存放在一个树形数据结构中。 树的树的每一层对应目的地址的一个比特每一层对应目的地址的一个比特，查找某个地，查找某个地址时，从树的根节点开始，依次查地址的每一位。址时，从树的根节点开始，依次查地址的每一位。r 内容可寻址内存内容可寻址内存(CAM)：将一个将一个32bit IP地址提交给地址提交给CAM，由它以常数时间返回该地址对应的转发表表项内，由它以常数时间返回该地址对应的转发表表项内容。如，容。如，Cisco8500系列。系列。r 将最近被访问的表项保存在高速缓存将最近被访问的表项保存在高速缓存(cache)中：中：49二分查找：二分查找：第一比特：第一比特： 0：左子树包含与该目的地址对应的转发表表项；：左子树包含与该目的地址对应的转发表表项； 1：表项在右子树中。：表项在右子树中。 下一比特：下一比特： 0，选择初始子树的左子树；，选择初始子树的左子树； 1，选择初始子树的右子树。，选择初始子树的右子树。 N步之内可找到相应的转发表表项步之内可找到相应的转发表表项（N是地址的位是地址的位数，地址空间为数，地址空间为2N）。）。 如，因特网如，因特网32bit IP地址需地址需32步。步。00110100 01 10 1150输入端口问题输入端口问题r分组阻塞分组阻塞 (blocked)： 来自其他输入端口的分组当前正在使用交换结构。来自其他输入端口的分组当前正在使用交换结构。 被阻塞的分组必须在输入端口处排队，等待以后被阻塞的分组必须在输入端口处排队，等待以后调度通过交换结构。调度通过交换结构。514.3.2 交换结构交换结构内存内存总线总线纵横制纵横制将分组从输入端口交换（转发）到输出端口中。将分组从输入端口交换（转发）到输出端口中。521、经内存交换、经内存交换r早期用计算机作为路由器早期用计算机作为路由器输入端口与输出端口之间的输入端口与输出端口之间的交换由交换由CPU(选路处理器选路处理器)控制完成控制完成；输入端口与输出端口类似输入端口与输出端口类似I/O设备：设备： 当分组到达输入端口时，通过中断当分组到达输入端口时，通过中断向选路处理器发出信号，将向选路处理器发出信号，将分组拷贝分组拷贝到处理器内存到处理器内存中；中； 选路处理器根据分组中的目的地址选路处理器根据分组中的目的地址查表找出适当的输出端口，将该分组查表找出适当的输出端口，将该分组拷贝到输出端口的缓存中。拷贝到输出端口的缓存中。 53输入端口输入端口输出端口输出端口内存内存系统总线转发速度受内存带宽的速度限制受内存带宽的速度限制 ( (每个分组穿过两次总线每个分组穿过两次总线) ) 若内存带宽为每秒写入或读出若内存带宽为每秒写入或读出B个分组，则个分组，则总的转发吞吐量总的转发吞吐量 (分组从输入端口被传送到输出分组从输入端口被传送到输出端口的总速率端口的总速率)小于小于B/2。54r 现代路由器现代路由器 由输入线路上的处理器来执行由输入线路上的处理器来执行目的地址的查找，目的地址的查找，并将分组存储并将分组存储( (交换交换) )进适当的存储位置进适当的存储位置。 类似类似共享内存的多处理机共享内存的多处理机，用一个线路卡上的处，用一个线路卡上的处理器将分组存储进适当输出端口的内存中。理器将分组存储进适当输出端口的内存中。 如，如，Cisco 8500。552、经总线交换、经总线交换 输入端口输入端口通过一条共享总线将分组直接传送通过一条共享总线将分组直接传送到输出端口到输出端口，不需要选路处理器的干预。，不需要选路处理器的干预。总线总线 每次每次只能有一个分组只能有一个分组通通过总线传送。过总线传送。 分组到达一个输入端分组到达一个输入端口时，若口时，若总线正忙总线正忙，会被，会被暂时阻塞，在输入端口暂时阻塞，在输入端口排排队队 路由器交换带宽路由器交换带宽受总受总线速率限制。线速率限制。563、经、经交换矩阵交换矩阵交换交换r纵横式交换机：纵横式交换机：由由2n条总线组成，条总线组成，n个输入端口与个输入端口与n个个输出端口连接。输出端口连接。 到达输入端口的到达输入端口的分组沿水平总线穿行分组沿水平总线穿行，直至与所，直至与所希望的希望的输出端口的垂直总线交叉点输出端口的垂直总线交叉点：若该条垂直总线若该条垂直总线空闲空闲，则分组被，则分组被传送传送到输出端口；到输出端口；否则否则，该到达的分组被阻塞，必须在输入端口，该到达的分组被阻塞，必须在输入端口排队。排队。高级设计高级设计: : 数据数据报分割成固定长报分割成固定长度信元度信元, , 通过交通过交换矩阵来交换信换矩阵来交换信元元574.3.3 输出端口输出端口 取出存放在输出端口内存中的分组，并将其传输到取出存放在输出端口内存中的分组，并将其传输到输出链路上。输出链路上。 当交换结构将分组交付给当交换结构将分组交付给输出端口的速率超过输输出端口的速率超过输出链路速率出链路速率，就需要排队与缓存管理功能。，就需要排队与缓存管理功能。交换结构排队：缓存管理数据链路处理(协议、解封)线路端接584.3.4 何时出现排队何时出现排队输入端口和输出端口都会形成分组队列。输入端口和输出端口都会形成分组队列。当队列逐步增长，路由器缓存空间满，会出现当队列逐步增长，路由器缓存空间满，会出现分组丢分组丢失失 (packet loss)，在输入端口队列或输出端口队列。，在输入端口队列或输出端口队列。丢失具体位置，取决于流量负载、交换结构的相对速丢失具体位置，取决于流量负载、交换结构的相对速度、线路速度等因素。度、线路速度等因素。r假定：假定：输入线路速率与输出线路速率相同输入线路速率与输出线路速率相同有有n个输入端口和个输入端口和n个输出端口个输出端口交换结构速率：交换结构速率：将分组从输入端口移动到输出端口的将分组从输入端口移动到输出端口的速率。速率。591、输入端口不排队、输入端口不排队 若交换结构的速率至少是输入线路速率的若交换结构的速率至少是输入线路速率的n倍倍，在输，在输入端口处不会出现排队。入端口处不会出现排队。r 最坏情况：最坏情况：有有n条输入线路同时接收分组。条输入线路同时接收分组。 交换结构可以在每个输入端口交换结构可以在每个输入端口(同时同时)接收一个分组的接收一个分组的时间内将时间内将n个分组从输入端口传送到输出端口个分组从输入端口传送到输出端口。n条条n条条n倍倍接收接收转发转发602、输出端口排队、输出端口排队设交换结构的速率至少是线路速率的设交换结构的速率至少是线路速率的n倍倍。r最坏情况：最坏情况：到达每个输入端口的分组都被发往同一个到达每个输入端口的分组都被发往同一个输出端口。输出端口。在在一个单位时间（接收或发送一个分组）一个单位时间（接收或发送一个分组）内，将有内，将有n个个分组到达该输出端口，排队分组到达该输出端口，排队(等待等待)发送到输出链路上；发送到输出链路上；在发出队列中一个分组的时间内，又有在发出队列中一个分组的时间内，又有n个分组到达。个分组到达。 依此类推，最终排队的分组快速增长，很快占满输依此类推，最终排队的分组快速增长，很快占满输出端口的存储空间，使后续分组被丢弃。出端口的存储空间，使后续分组被丢弃。 61例例假假定定：线线路路速速度度相相同同，交交换换结结构构处处理理速速度度是是线线路路速速度的度的三倍三倍。交换结构交换结构在时间t输出端口竞争一个分组时间以后 t t时刻：时刻：每个输入端口都到达一个分组，都发往最上侧的输出端口。每个输入端口都到达一个分组，都发往最上侧的输出端口。 一个单位时间后（接收或发送一个分组的时间）：一个单位时间后（接收或发送一个分组的时间）： 三个原始分组都被传送到输出端口，并排队等待发送。三个原始分组都被传送到输出端口，并排队等待发送。 又有两个新分组到达交换结构的输入端，其中的一个分组要发又有两个新分组到达交换结构的输入端，其中的一个分组要发往最上侧往最上侧 的输出端口。的输出端口。下一个单位时间：下一个单位时间：三个分组中的一个通过输出链路发送出去。三个分组中的一个通过输出链路发送出去。 62分组调度程序分组调度程序 在在输出端口排队的分组中选出一个发送输出端口排队的分组中选出一个发送。原则：原则：先来先服务先来先服务FCFS：简单。简单。加权公平排队加权公平排队WFQ：在具有排队分组的不同端到端连在具有排队分组的不同端到端连接之间公平地共享输出链路。接之间公平地共享输出链路。63分组丢弃方法：若缓存已满，丢弃分组。若缓存已满，丢弃分组。丢弃后到的分组（丢弃后到的分组（弃尾弃尾）；）；删除删除一个或多个已排队的分组；一个或多个已排队的分组； 活动队列管理活动队列管理AQM算法算法：在缓存填满前丢弃分组或首在缓存填满前丢弃分组或首部加标记，向发送方提供拥塞信号。部加标记，向发送方提供拥塞信号。 如，如，随机早期检测随机早期检测RED算法：算法： 输出队列长度维护输出队列长度维护一个加权平均值。一个加权平均值。64随机早期检测随机早期检测RED算法：算法：设设最小阈值最小阈值minth和和最大阈值最大阈值maxth平均队列长度小于最小阈值平均队列长度小于最小阈值minth，到达分组被纳入队，到达分组被纳入队列；列；队列满或平均队列长度大于最大阈值队列满或平均队列长度大于最大阈值maxth ，到达分组，到达分组被标记或丢弃；被标记或丢弃；平均队列长度在平均队列长度在minth， maxth之间，到达分组以某种之间，到达分组以某种概率被标记或丢弃。概率被标记或丢弃。653、输入端口分组排队：、输入端口分组排队：交换结构比输入端口总和的速度慢交换结构比输入端口总和的速度慢 输入队列产生排队输入队列产生排队 交换结构不够快，即交换结构不够快，即相对于输入线路速度不能快相对于输入线路速度不能快得使所有到达的分组无延迟地通过它传送得使所有到达的分组无延迟地通过它传送，则在输入，则在输入端口出现分组排队，以等待通过交换结构传送到输出端口出现分组排队，以等待通过交换结构传送到输出端口。端口。66如，采用纵横式交换结构如，采用纵横式交换结构 假定：假定：所有链路速度相同；所有链路速度相同；交换结构速率与输入链路速率相同交换结构速率与输入链路速率相同：分组从输入端口分组从输入端口传送到给定输出端口的时间与从输入链路接收一个分传送到给定输出端口的时间与从输入链路接收一个分组的时间相同；组的时间相同；分组按分组按FCFS方式从输入队列移动到输出队列中。方式从输入队列移动到输出队列中。 结果：结果：分组输出端口不同：分组输出端口不同：多个分组可以被并行传送。多个分组可以被并行传送。发往相同输出端口：发往相同输出端口：不同输入队列中的分组发往同一不同输入队列中的分组发往同一输出队列，其中的一些输出队列，其中的一些分组被阻塞，在输入队列中等分组被阻塞，在输入队列中等待待（交换结构一次传一个分组到端口）。（交换结构一次传一个分组到端口）。67例不同输入队列前端的两个分组要发往右上角的同一输出不同输入队列前端的两个分组要发往右上角的同一输出端口。端口。若先发送左上角队列前端的分组，左下角队列中的分组若先发送左上角队列前端的分组，左下角队列中的分组要等待，左下角队列中排在该分组后面的分组也要等待要等待，左下角队列中排在该分组后面的分组也要等待r线头线头HOL (head-of-the-line)阻塞：阻塞： 输入队列中后面的分组被位于线头的一个分组阻塞输入队列中后面的分组被位于线头的一个分组阻塞(即使输出端口空闲的即使输出端口空闲的)，等待通过交换结构发送。，等待通过交换结构发送。时间时间t：输出端口竞争，仅一：输出端口竞争，仅一个红色分组能被传输个红色分组能被传输时间时间t1：绿色分组经历了：绿色分组经历了HOL阻塞阻塞交换结构684.5 选路算法选路算法 分组通过路由器转发，每个路由器都有一张分组通过路由器转发，每个路由器都有一张转发表，选路算法决定转发表内容。转发表，选路算法决定转发表内容。r选路：选路：确定分组从发送方传送到接收方所要通过的路确定分组从发送方传送到接收方所要通过的路径（路由）。径（路由）。数据报服务：数据报服务：在给定源和目的地之间传输在给定源和目的地之间传输不同分组可不同分组可能采用不同的路由能采用不同的路由。虚电路服务：虚电路服务：在给定源和目的地之间的在给定源和目的地之间的所有分组采用所有分组采用同一路径同一路径。69概念概念r 默认路由器默认路由器 ：与主机直接相连的一：与主机直接相连的一台路由器，又叫台路由器，又叫第一跳路由器第一跳路由器。 每当主机发送一个分组时，都每当主机发送一个分组时，都先传送给它的默认路由器。先传送给它的默认路由器。 源路由器：源路由器：源主机的默认路由器。源主机的默认路由器。 目的路由器：目的路由器：目的主机的默认路由目的主机的默认路由器。器。 从源主机到目的主机的选路归从源主机到目的主机的选路归结为结为从源路由器到目的路由器的选路从源路由器到目的路由器的选路。 networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH2R1R2默认路由器默认路由器70选路算法：选路算法： 确定一个分组从源路由器到目的路由器所经确定一个分组从源路由器到目的路由器所经路径的路径的算法。算法。 即在给定的一组路由器以及连接路由器的链路中，即在给定的一组路由器以及连接路由器的链路中，找到一条从源路由器到目的路由器的找到一条从源路由器到目的路由器的“好好”路径。路径。r“好好”路径：路径：具有具有“最低费用最低费用”的路径。的路径。 由许多因素决定，如链路长度、传播时延、价格等。由许多因素决定，如链路长度、传播时延、价格等。71网络的抽象图模型：网络的抽象图模型：用用“节点图节点图”表示网络的结构。表示网络的结构。 图图G = (N，E)表示表示N个节点和个节点和E条边的集合条边的集合，每条，每条边是来自边是来自N的一对节点。的一对节点。节点：节点：表示路由器表示路由器(做出分组转发判决的点做出分组转发判决的点)。 如如u，v，w，x，y，z。 边：边：连接节点的线段，表示路由器之间的物理链路。连接节点的线段，表示路由器之间的物理链路。 如如(u，v)、 (u，x) 、(u，w)、uyxwvz221311253572边的值（费用）边的值（费用） 表示对应链路的物理长度、或链路速度、或与链路相关表示对应链路的物理长度、或链路速度、或与链路相关的费用。的费用。约定：约定： 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) = c(v，u) =2选路算法：选路算法：根据给定的网络抽象根据给定的网络抽象图，图，找出从源节点到目的节点间找出从源节点到目的节点间的最低费用路径的最低费用路径。73路径r 路径表示：路径表示：用路径上的用路径上的节点来描述节点来描述。 如图如图G = (N，E)中的一条路径，是一个节点序列中的一条路径，是一个节点序列(x1, ,x2, , ,xp)，其中每个相邻节点其中每个相邻节点x1, ,x2, , ,xp依次连成边。依次连成边。r 路径路径(x1, ,x2, , ,xp)费用：费用：沿途所有边的费用之和沿途所有边的费用之和。即。即 c(x1, ,x2) + c(x2, ,x3) + +c(xp-1, ,xp) 通常，任意两个节点通常，任意两个节点x和和y 之间有多条路径，费用不之间有多条路径，费用不一定相同。一定相同。r 最低费用路径最低费用路径 ：该路径上该路径上链路费用之和最小链路费用之和最小。 若所有链路费用相同，则最低费用路径就是若所有链路费用相同，则最低费用路径就是最短路径最短路径 ，即，即在源和目的地之间经过链路最少的路径在源和目的地之间经过链路最少的路径。74例例 如图，源节点如图，源节点u和目的节点和目的节点w之间的最低费用路径：之间的最低费用路径： uyxwvz2213112535(u,x,y,w) ，费用为，费用为3。75选路算法分类：选路算法分类：根据算法是全局性还是分散性划分根据算法是全局性还是分散性划分根据算法是静态还是动态划分根据算法是静态还是动态划分根据对负载是否敏感划分根据对负载是否敏感划分因特网常用的两种选路算法：因特网常用的两种选路算法： 动态全局链路状态算法动态全局链路状态算法 动态分散式距离向量算法动态分散式距离向量算法4.5.1 链路状态选路算法链路状态选路算法4.5.2 距离向量选路距离向量选路DV算法算法4.5.3 层次选路层次选路76全局选路算法全局选路算法 用完整的、全局性的网络信息用完整的、全局性的网络信息来计算最低费用路来计算最低费用路径。即以所有节点之间的径。即以所有节点之间的连通性连通性及所有链路的及所有链路的费用费用为条为条件。件。 在开始计算前，以某种方式获得这些信息。在开始计算前，以某种方式获得这些信息。 可在单个位置计算，也可在多个位置上复制。可在单个位置计算，也可在多个位置上复制。 拥有连通性和链路费用的完整信息。拥有连通性和链路费用的完整信息。链路状态算法链路状态算法LS：必须知道网络中每条链路的费用。必须知道网络中每条链路的费用。77分散式选路算法分散式选路算法 以以迭代的、分布式的方式迭代的、分布式的方式计算最低费用路径。计算最低费用路径。 节点节点只有与其直接相连链路的费用信息只有与其直接相连链路的费用信息：不需拥有所：不需拥有所有网络链路费用的完整信息。有网络链路费用的完整信息。 通过迭代计算过程并与相邻节点通过迭代计算过程并与相邻节点( (邻居节点邻居节点) )交换信息交换信息 逐步计算出到达某目的节点或一组目的节点的最低费逐步计算出到达某目的节点或一组目的节点的最低费用路径。用路径。 距离向量算法距离向量算法DV：每个节点维护到网络中所有其每个节点维护到网络中所有其他节点的费用（距离）的估计向量。他节点的费用（距离）的估计向量。78静态选路算法：静态选路算法： 路由确定后基本不再变化。当人工干预调整时，可路由确定后基本不再变化。当人工干预调整时，可能有一些变化。能有一些变化。 动态选路算法：动态选路算法： 当网络的流量负载或拓扑发生变化时，改变路径。当网络的流量负载或拓扑发生变化时，改变路径。 可以周期性地或直接地响应拓扑或链路费用的变化。可以周期性地或直接地响应拓扑或链路费用的变化。易受选路循环、路由振荡之类问题的影响。易受选路循环、路由振荡之类问题的影响。79r负载敏感算法：负载敏感算法： 链路费用会动态地变化链路费用会动态地变化，反映出底层链路的当前拥，反映出底层链路的当前拥塞水平。塞水平。 如果当前拥塞的一条链路被赋以高费用，则选路算如果当前拥塞的一条链路被赋以高费用，则选路算法应绕开该拥塞链路来选择路由。法应绕开该拥塞链路来选择路由。 如早期的如早期的ARPAnet选路算法。选路算法。r负载迟钝算法：负载迟钝算法： 某条链路的费用一般不反映其当前的某条链路的费用一般不反映其当前的(或最近的或最近的)拥塞拥塞级别。级别。 如因特网的选路算法。如因特网的选路算法。804.5.1 链路状态选路算法链路状态选路算法r前提条件：前提条件：已知已知网络拓扑网络拓扑和所有和所有链路的费用，链路的费用，作为算作为算法的输入。法的输入。r获取方法：获取方法：每个节点向网络中广播每个节点向网络中广播链路状态分组链路状态分组（含（含有它所连接的链路的费用）。有它所连接的链路的费用）。 由链路状态由链路状态广播算法广播算法实现。最终使所有节点都实现。最终使所有节点都有一个相同且完整的网络视图。有一个相同且完整的网络视图。r每个节点都可以运行每个节点都可以运行链路状态算法并计算出最低费用链路状态算法并计算出最低费用路径集。路径集。81Dijkstra最低费用路径算法（最短通路算法）最低费用路径算法（最短通路算法）计算从某节点（计算从某节点（源节点，如源节点，如u）到网络中所有其他节点）到网络中所有其他节点的最低费用路径。的最低费用路径。是一种是一种迭代算法迭代算法，即：，即： 经第经第k次迭代后，可知道到次迭代后，可知道到k个目的节点的最低费个目的节点的最低费用路径。用路径。r基本思想：基本思想： 以以源节点为起点源节点为起点，每次找出一个每次找出一个到源节点的费用到源节点的费用最低的节点，直到把所有的目的节点都找到为止。最低的节点，直到把所有的目的节点都找到为止。82符号定义：符号定义：c(x,y): 从节点从节点x到到y的链路费用的链路费用; = 如果不是直接邻居如果不是直接邻居D(v) ：从源节点到目的从源节点到目的节点节点v的当前费用的当前费用 ；p(v)： 从源节点到节点从源节点到节点v的路径上的的路径上的前一节点前一节点(节点节点v的的邻居邻居)；N： 节点集合，从源节点到这些节点的最低费用路径节点集合，从源节点到这些节点的最低费用路径已被求出。已被求出。uxywv83 Dijsktra算法组成算法组成由一个由一个初始化步骤和其后的循环初始化步骤和其后的循环组成。组成。循环执行的次数与网络中的循环执行的次数与网络中的节点个数（除源节点）节点个数（除源节点）相同。相同。结束时，算出从源节点到网络中所有其他节点的最结束时，算出从源节点到网络中所有其他节点的最短路径。短路径。84算法算法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中中 85算法描述：算法描述：（1）初始化（）初始化（1#6#） N =源节点源节点u； 对所有不在对所有不在N 中的节点中的节点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) = 86（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）重复步骤）重复步骤(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中中 a aefcbd221311253587例例r计算从计算从u到所有可能目的节点的最低费用路径。到所有可能目的节点的最低费用路径。r计算过程如表计算过程如表4-3，表中的，表中的每一行表示一次迭代结束时每一行表示一次迭代结束时的算法变量值。的算法变量值。u uyxwvz221311253588步骤步骤0NuD(v),p(v)2,uD(w),p(w)5,uD(x),p(x)1,uD(y),p(y)D(z),p(z) 4,yu uyxwvz2213112535D(w)：min(5，1+3)=4 D(y)：min(，1+1)=2 2,u 4,x 2,x 2,u 3,y 4,y3,y 4,y1 ux2 uxy3 uxyv 4 uxyvw 5 uxyvwz89构建从源节点到所有目的节点的路径构建从源节点到所有目的节点的路径对于每个节点，都得到从源节点沿着它的最低费用路对于每个节点，都得到从源节点沿着它的最低费用路径的前一节点；径的前一节点；每个前一节点，又可得到它的前一节点；每个前一节点，又可得到它的前一节点；以此继续，可以得到到所有目的节点的完整路径。以此继续，可以得到到所有目的节点的完整路径。 如节点如节点z的前一节点依次为：的前一节点依次为： zyxu 得出从源节点得出从源节点u到节点到节点z的最低费用路径为：的最低费用路径为：uxyz，费，费用为用为4。u uyxwvz2213112535902,u 4,x 2,x u1w1y2v2z1xu uyxwvz2213112535根据根据目的节点的找出顺序目的节点的找出顺序和其和其费用费用以及以及前一节点前一节点，可，可以画出源节点以画出源节点u到所有目的节点的到所有目的节点的最低费用路径树。最低费用路径树。步骤步骤0NuD(v),p(v)2,uD(w),p(w)5,uD(x),p(x)1,uD(y),p(y)D(z),p(z) 4,y2,u 3,y 4,y3,y 4,y1 ux2 uxy3 uxyv 4 uxyvw 5 uxyvwz 根据得到的所有目的节点的完整路径，或最低费用路径根据得到的所有目的节点的完整路径，或最低费用路径树，可以生成源节点的转发表。树，可以生成源节点的转发表。 转发表：转发表：存放从源节点到每个目的节点的最低费用存放从源节点到每个目的节点的最低费用路径上路径上的下一跳节点。的下一跳节点。 即指出对于发往某个目的节点的分组，从该节点发出即指出对于发往某个目的节点的分组，从该节点发出后的下一个节点。后的下一个节点。91r 默认路由默认路由 * ： 表示所有具有相同表示所有具有相同“下一跳下一跳”的表项。的表项。即将即将“下一跳下一跳”相同的项合并为一项，目的节点用相同的项合并为一项，目的节点用“*”表示。表示。优先级最低优先级最低，转发分组时，当找不到对应表项时，才，转发分组时，当找不到对应表项时，才使用默认路由。使用默认路由。节点节点u的转发表的转发表目的点目的点 下一跳下一跳 u vv wx xx yx zx节点节点u的转发表的转发表目的点目的点 下一跳下一跳uvv*x 将网络中每一个节点作为源点，分别用上将网络中每一个节点作为源点，分别用上述方法计算，可以得到每一个节点的转发表。述方法计算，可以得到每一个节点的转发表。21211uyxwvz92算法的计算复杂性：r设设n个节点个节点(除源节点除源节点)，最坏情况下要经多少次计算才，最坏情况下要经多少次计算才能找到从源节点到所有目的节点的最低费用路径能找到从源节点到所有目的节点的最低费用路径?第一次迭代：第一次迭代：搜索所有的搜索所有的n个节点以确定最低费用节点个节点以确定最低费用节点第二次迭代：第二次迭代：检查检查n-1个节点；个节点；第三次：第三次：检查检查n-2个节点；个节点； 依次类推。依次类推。 所有迭代中需要搜寻的节点总数为所有迭代中需要搜寻的节点总数为n(n+1)/2。r算法复杂性为算法复杂性为n平方阶序平方阶序O(n2)。93LS算法的缺陷：算法的缺陷：可能产生可能产生“振荡振荡”。例图例图4-26, ,一个简单网络拓扑。设：一个简单网络拓扑。设：链路费用等于链路上的负载；链路费用等于链路上的负载；链路费用是链路费用是非对称的非对称的： c(u，v)与与c(v，u)仅当在链路仅当在链路(u，v)两个方向的负载相同时才相等。两个方向的负载相同时才相等。r有三个同时发往有三个同时发往w的注入流量：的注入流量：节点节点z：一个单元；一个单元；节点节点x：一个单元；一个单元；节点节点y：e的流量。的流量。wzyxe1194初始：初始： 图图(a)，其链路费用相当于承载的流量，其链路费用相当于承载的流量第一次：第一次： 节点节点x、y都确定都确定顺时针方向顺时针方向到到w的路径费用最低，的路径费用最低，为为1。产生图。产生图(b)费用。费用。第二次：第二次： 节点节点x、y、z都确定都确定逆时针逆时针方向到方向到w的路径费用最的路径费用最低，为低，为0。产生图。产生图(c)费用。费用。第三次：第三次： 节点节点x、y、z都确定都确定顺时针顺时针方向到方向到w的路径费用最低，的路径费用最低，为为0。产生图。产生图(d)费用。费用。wzyx11+ee0e1100(a)wzyx2+e0001+e1e11(b)(c)ewzyx02+e1+e10 011(d)wzyx2+e0001+e111e95避免振荡：避免振荡：使使链路费用不依赖于所承载的流量链路费用不依赖于所承载的流量：不可行；：不可行；避免所有的路由器同时运行避免所有的路由器同时运行LS算法算法：比较合理。：比较合理。 既使路由器以相同周期运行既使路由器以相同周期运行LS算法，在算法，在每个节点每个节点上算法的执行时刻也不同上算法的执行时刻也不同。r因特网的自同步：因特网的自同步： 既使路由器初始时以同一周期但不同时刻执行算既使路由器初始时以同一周期但不同时刻执行算法，算法执行时刻最终会同步并保持。法，算法执行时刻最终会同步并保持。 采用随机时间的方法，即每台路由器随机发送链路采用随机时间的方法，即每台路由器随机发送链路通告。通告。964.5.2 距离向量选路距离向量选路DV算法算法 是是一种迭代的、异步的和分布式的算法一种迭代的、异步的和分布式的算法。分布式：分布式：每个节点都每个节点都从其直接相连邻居接收信息从其直接相连邻居接收信息，进，进行计算，再将计算结果分发给邻居。行计算，再将计算结果分发给邻居。迭代：迭代：计算过程一直持续到计算过程一直持续到邻居之间无更多信息交换邻居之间无更多信息交换为止。为止。自我终结：自我终结：算法能自行停止。算法能自行停止。异步：异步：不要求所有节点相互之间步伐一致地操作。不要求所有节点相互之间步伐一致地操作。97最低费用表示：最低费用表示：dx(y)：节点节点x到节点到节点y的最低费用路径的费用。用的最低费用路径的费用。用Bellman-Ford方程表示方程表示 dx(y) = minvc(x,v)+ dv(y) （4-1）c(x,v)+ dv(y)：x与某个邻居与某个邻居v之间的直接链路费用之间的直接链路费用c(x，v)加上邻居加上邻居v到到y的最小费用。即的最小费用。即x经经v到节点到节点y的最小的路径的最小的路径费用费用。minv ：从所有经直接相连邻居到节点从所有经直接相连邻居到节点y的费用中选取的的费用中选取的最小路径费用。最小路径费用。98例如图例如图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+3 = 4 即即源节点源节点u经相邻节点经相邻节点x到目的节点到目的节点z的路径费用最低，为的路径费用最低，为4。u uyxwvz z2213112535得到节点得到节点u的转发的转发表中到表中到目的节点目的节点z的的下一跳是节点下一跳是节点x99DV算法基本思想：算法基本思想：设设Dx(y)：节点节点x到到N中某个中某个节点节点y的估计费用；的估计费用；Dx：节点节点x的距离向量的距离向量。Dx = Dx(y)：y在在N中中，即即节点节点x到到N中所有中所有其他节点其他节点y的估计费用。的估计费用。 r基本思想：基本思想： 每个节点有一张选路表（距离表），维持选每个节点有一张选路表（距离表），维持选路数据，随着算法进行，不断更新，直到静止。路数据，随着算法进行，不断更新，直到静止。节点节点x选路表选路表更新选路表的距离向量更新选路表的距离向量当距离向量不再变化，当距离向量不再变化，算法静止算法静止100节点节点x选路表选路表节点节点x选路表（选路表（距离表距离表）:行：行：该节点的距离向量该节点的距离向量Dx和其邻居的距离向量和其邻居的距离向量Dv列：列：所有目的节点。所有目的节点。 节点节点x的距离向量的距离向量Dx ，即节点，即节点x到每个目的节点到每个目的节点y的估的估计费用；计费用； Dx = Dx(y)：y在在N中中节点节点x每个邻居的距离向量每个邻居的距离向量Dv ，即，即x的邻居的邻居v到每个目到每个目的节点的节点y的估计费用，的估计费用，Dv = Dv(y)：y在在N中中xz127yx y zxyz0 2 7 DxDyDzDx(x) Dx(y) Dx(z) x y zxyzDy(x) Dy(y) Dy(z) Dz(x) Dz(y) Dz(z) 邻邻居居101更新其距离向量更新其距离向量每个节点不断向邻居发送其距离向量拷贝；每个节点不断向邻居发送其距离向量拷贝；当当节点节点x收到一个收到一个邻居邻居v的新距离向量，先保存，并用的新距离向量，先保存，并用公式（公式（4-1）更新自己的距离向量：）更新自己的距离向量： Dx(y) = minvc(x,v)+ Dv(y) 从所有经从所有经邻居邻居v到节点到节点y的费用中选取最小路径费用。的费用中选取最小路径费用。若距离向量发生改变，将新的距离向量通知给邻居。若距离向量发生改变，将新的距离向量通知给邻居。102当距离向量不再变化，算法静止当距离向量不再变化，算法静止 此时此时Dx(y)收敛到收敛到dx(y)，即得到节点，即得到节点x到节点到节点y的最的最低费用路径。低费用路径。1031、距离向量、距离向量DV算法描述：算法描述：2、链路费用改变与链路故障、链路费用改变与链路故障3、增加、增加“毒性逆转毒性逆转 4、LS算法与算法与DV算法比较算法比较5、其他选路算法、其他选路算法1041、距离向量、距离向量DV算法描述：算法描述：对每个节点对每个节点x（1）初始化初始化：（2）更新自己的距离向量更新自己的距离向量 （3）重复执行（）重复执行（2），直到），直到没有更新的距离向量发出没有更新的距离向量发出等待等待 (收到本地链路代价变化或收到本地链路代价变化或邻居来距离矢量更新邻居来距离矢量更新)重新计算距离矢量重新计算距离矢量如果到任何目的节点的距离矢量如果到任何目的节点的距离矢量发生变化发生变化, 通知邻居通知邻居 初始化初始化105距离矢量算法距离矢量算法:1 Initialization: 2 for all destinations y in N: 3 Dx (y) = c( x, y ) /* if y is not a neighbor then c( x, 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:14 Dx(y) = c(x,v) + Dv(y)15 16 if Dx(y) changed for any destination y 17 Send DV Dx = Dx (y) : y in N to all neighbors 19 forever 初初始始化化106（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 destinations y in N: 3 Dx (y) = c( x, y ) /* if y is not a neighbor then c( x, 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 107（2）更新距离向量）更新距离向量 发现发现直接相连的链路费用变化直接相连的链路费用变化，或，或收到邻居的新距收到邻居的新距离向量离向量，更新自己的距离向量，更新自己的距离向量 （10#11#） 用邻居的新距离向量更新到所有目的点用邻居的新距离向量更新到所有目的点y的距离向量的距离向量 （13#14#） Dx(y) = minvc(x,v)+ Dv(y) 在经每个在经每个邻居邻居v到目的点到目的点y的距离向量中，的距离向量中，选择一个最选择一个最小值作为当前新距离向量小值作为当前新距离向量，并将所经过的邻居，并将所经过的邻居v作为节点作为节点x转发表中到目的节点转发表中到目的节点y的的下一跳路由器下一跳路由器v*(y)。 若距离向量发生改变，向其邻居发送新距离向量。若距离向量发生改变，向其邻居发送新距离向量。 （16#17#）108例图例图4-27 每个节点维护一张每个节点维护一张选路表（距离表），选路表（距离表），随着算法随着算法进行不断变化。进行不断变化。 行：行：一个一个距离向量距离向量，每行分别表示，每行分别表示该节点的距离向量该节点的距离向量和其邻居的距离向量和其邻居的距离向量，即该节点和邻居到所有目的节，即该节点和邻居到所有目的节点的估计费用。点的估计费用。列：列：所有目的节点。所有目的节点。 109x y zxyz0 2 7 x y zxyz0 2 3x y zxyz0 2 3x y zxyz x y zxyz0 2 7x y zxyz0 2 3x y zxyz0 2 3x y zxyz0 2 7x y zxyz 7 102 0 1 2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0timexz127y节点节点x的距离矢量表的距离矢量表节点节点 y 节点节点 z Dx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2直接到直接到y费用最小。费用最小。X到到y的下一跳为的下一跳为yDx(z)=minc(x,y)+Dy(z),c(x,z) + Dz(z) = min2+1 , 7+0 = 3x经经y到到z费用最小。费用最小。x到到z的下一跳为的下一跳为y邻邻居居初始化初始化第一次第一次y 的新距离向量 向邻居发送向邻居发送z 的新距离向量 第二次第二次稳定稳定目的节点目的节点110 多次重复多次重复从邻居接收更新距离向量从邻居接收更新距离向量、重新计算选、重新计算选路表项、并向邻居发送更新通知的过程，一直持续到路表项、并向邻居发送更新通知的过程，一直持续到没有更新报文发出为止。没有更新报文发出为止。 算法进入静止状态，直到某个链路费用发生改变算法进入静止状态，直到某个链路费用发生改变为止。为止。1112、链路费用改变与链路故障、链路费用改变与链路故障 当一个节点检测到当一个节点检测到从它到邻居的链路费用发生变从它到邻居的链路费用发生变化时化时，就更新其距离向量，如果最低费用路径的费用，就更新其距离向量，如果最低费用路径的费用发生变化，通知其邻居。发生变化，通知其邻居。（1）某链路费用减少时情况）某链路费用减少时情况 例图例图4-28。当。当y 到到x的链路费用从的链路费用从4变为变为1的情况。的情况。xz1450y1112考虑考虑y 与与z 到目的节点到目的节点x的距离表变化的距离表变化t0：y 检测到检测到x的链路费用从的链路费用从4变为变为1，更新其距离向量，更新其距离向量，并通知其邻居并通知其邻居z；t1：z收到来自收到来自y的更新报文，并更新自己的距离表，此的更新报文，并更新自己的距离表，此时时到节点到节点x的最低费用减为的最低费用减为2，并通知其邻居，并通知其邻居y；t2：y收到来自收到来自z的更新报文，并更新自己的距离表，此的更新报文，并更新自己的距离表，此时时到节点到节点x的最低费用不变仍为的最低费用不变仍为1。不发送更新报文，算。不发送更新报文，算法静止。法静止。 当当x与与y之间费用减少，之间费用减少，DV算法算法只需两次迭代只需两次迭代到达静到达静止状态。止状态。 节点之间链路费用减少节点之间链路费用减少的的“好消息好消息”在网络中能迅在网络中能迅速传播。速传播。xz1450y1113（2）某链路费用增加时情况）某链路费用增加时情况例图例图4-28b，设，设x与与y之间的链路费用从之间的链路费用从4增加到增加到60。xz1450y60114r链路费用变化前链路费用变化前 Dy(x )=4 ，Dy(z )=1， Dz(y )=1，Dz(x )=5t0 时刻时刻：y检测到链路费用检测到链路费用从从4变为变为60。更新到。更新到x的最低的最低路径费用路径费用 Dy(x )=min c(y,x)+ Dx(x), c(y,z)+ Dz(x) =min60+0,1+5=6 经节点经节点z到到x费用最低，费用最低，此新费用错误，发给节点此新费用错误，发给节点z。t1时刻时刻：z收到新费用，更新其到收到新费用，更新其到x的最低路径费用的最低路径费用 Dz(x )=min c(z,x)+ Dx(x), c(z,y)+ Dy(x) =min50+0,1+6=7 经节点经节点y到到x费用最低，费用最低，发给节点发给节点y。xz1450y60115t2 时刻时刻：y收到新费用，更新到收到新费用，更新到x的最低路径费用的最低路径费用 Dy(x )=min c(y,x)+ Dx(x), c(y,z)+ Dz(x) =min60+0,1+7=8 经节点经节点z到到x费用最低，发给节点费用最低，发给节点z。 节点节点y或或z的最低费用不断更新。的最低费用不断更新。r产生产生“选路回环选路回环”：为到达为到达x， y通过通过z选路，选路，z又通过又通过y选路选路。 即目的地为即目的地为x的分组到达的分组到达y或或z后，将在这两个节点之后，将在这两个节点之间不停地来回反复，直到转发表发生改变为止。间不停地来回反复，直到转发表发生改变为止。xz1450y60116 上述循环将持续上述循环将持续44次迭代次迭代 (y与与z之间的报文交换之间的报文交换)，直到直到z最终算出它经由最终算出它经由y的路径费用大于的路径费用大于50为止。并确为止。并确定：定：z到到x的最低费用路径：的最低费用路径：zxy到到x的最低费用路径：的最低费用路径：yzxr说明：说明：链路费用增加的链路费用增加的“坏消息坏消息”传播很慢传播很慢！ 当链路费用增加很大，会出现当链路费用增加很大，会出现“计数到无穷计数到无穷”问题。问题。如链路费用如链路费用c(y，x)变为变为10000，c(z，x)变为变为9999时。时。xz1450y601173、增加、增加“毒性逆转毒性逆转”避免出现避免出现“选路回环选路回环”现象。现象。r基本思想：基本思想： 如果如果 z 通过通过 y 选路到达目的地选路到达目的地 x，则，则 z 将告诉将告诉 y，它到它到 x 的距离是无穷大（即的距离是无穷大（即 z 将告诉将告诉y，Dz(x )= ）; y 认为认为 z 没有到没有到 x 的路径，就不会试图经由的路径，就不会试图经由z选路到选路到x。 例，例，“毒性逆转毒性逆转”用来解决用来解决图图4-28b中的特定环路中的特定环路xz1450y118设使用设使用“毒性逆转毒性逆转”后，后，y距离表显示距离表显示Dz(x )= 。t0 时刻时刻：(x,y)链路费用链路费用从从4变为变为60。y更新其到更新其到x的最低费用的最低费用 Dy(x )=min c(y,x)+ Dx(x), c(y,z)+ Dz(x) =min60+0,1+=60 y直接选路到直接选路到x，将新费用，将新费用Dy(x )=60，通知，通知z 。t1时刻：时刻：z收到新费用，计算其到收到新费用，计算其到x的新的最低路径费用的新的最低路径费用 Dz(x )=min c(z,x)+ Dx(x), c(z,y)+ Dy(x) =min50+0,1+60=50 z直接选路到直接选路到x，将新费用，将新费用Dz(x )=50，通知，通知y。t2 时刻：时刻：y收到新费用，计算其到收到新费用，计算其到x的新的最低路径费用的新的最低路径费用 Dy(x )=min c(y,x)+ Dx(x), c(y,z)+ Dz(x) =min60+0,1+50=51 y经经z到到x费用最低，使用费用最低，使用“毒性逆转毒性逆转”抑制从抑制从y到到x方向的路方向的路径径t3 时刻：时刻：y通知通知z ，y到到x费用无穷大，费用无穷大，Dy(x )= 。 算法静止。算法静止。xz1450y60119毒性逆转局限：未解决未解决“不可计数问题不可计数问题”。当涉及到三个或更多节点的回路将不能被毒性逆转技当涉及到三个或更多节点的回路将不能被毒性逆转技术检测到。术检测到。1204、LS算法与算法与DV算法比较算法比较DV算法：算法：每个节点每个节点只与邻居互相交流只与邻居互相交流，得到邻居的新，得到邻居的新费用，并告知邻居自己的当前最低费用。费用，并告知邻居自己的当前最低费用。LS算法：算法：每个节点每个节点与所有其他节点广播交流与所有其他节点广播交流，只告知，只告知与其直接相连链路的费用。与其直接相连链路的费用。r报文复杂性：报文复杂性：LS算法：算法：知道网络每条链路的费用知道网络每条链路的费用，需发送，需发送O(nE)个个报文；当一条链路的费用变化时，必须通知所有节点报文；当一条链路的费用变化时，必须通知所有节点DV算法：算法：迭代时，迭代时，在两个直接相连邻居之间交换报文在两个直接相连邻居之间交换报文；收敛时间受许多因素影响；当链路费用改变时，只有收敛时间受许多因素影响；当链路费用改变时，只有该链路相连的节点的最低费用路径发生改变时，才传该链路相连的节点的最低费用路径发生改变时，才传播已改变的链路费用。播已改变的链路费用。121r收敛速度：收敛速度： LS算法：算法：需要需要O(nE)个报文和个报文和O(n2)的搜寻。的搜寻。DV算法：算法：收敛较慢。可能会遇到选路回环，或计数到收敛较慢。可能会遇到选路回环，或计数到无穷的问题。无穷的问题。122r健壮性：健壮性： 当一台路由器发生故障、操作错误或受到破坏时，当一台路由器发生故障、操作错误或受到破坏时，会发生什么情况会发生什么情况?LS算法：算法：路由器向其连接的路由器向其连接的一条链路广播不正确费用一条链路广播不正确费用。路由计算基本独立（仅计算自己的转发表），有一定路由计算基本独立（仅计算自己的转发表），有一定健壮性。健壮性。DV算法：算法：一个节点可一个节点可向任意或所有目的节点发布向任意或所有目的节点发布其不其不正确的最低费用路径。正确的最低费用路径。 一个节点的计算值会传递给它的邻居，并间接地一个节点的计算值会传递给它的邻居，并间接地传递给邻居的邻居。传递给邻居的邻居。 一个不正确的计算值会扩散到整个网络。一个不正确的计算值会扩散到整个网络。1235、其他选路算法r热土豆选路算法热土豆选路算法(hot potato routing)： 路由器路由器尽可能快尽可能快地转发输出分组。地转发输出分组。 向任意不拥塞的输出链路转发分组，不管目的向任意不拥塞的输出链路转发分组，不管目的地在哪里。地在哪里。r网络流算法：网络流算法： 把分组流量看成是一个网络中源和目的地之把分组流量看成是一个网络中源和目的地之间的流。将选路问题形式化为间的流。将选路问题形式化为数学上的受限优化问题数学上的受限优化问题（网络流问题）。（网络流问题）。r电路交换选路算法：电路交换选路算法： 每条链路资源每条链路资源( (如缓冲区、部分链路带宽如缓冲区、部分链路带宽) )都要都要保留给每个要经过该链路的连接。保留给每个要经过该链路的连接。 对分组交换数据网有帮助。对分组交换数据网有帮助。1244.5.3 层次选路层次选路 前面的选路方法，需要网络的前面的选路方法，需要网络的所有路由器执行相同所有路由器执行相同的选路算法的选路算法来计算通过整个网络的路径。来计算通过整个网络的路径。r 带来问题：带来问题： 规模规模 管理自治管理自治 r 层次选路：层次选路： 按区域或自治系统的形式组织路由器。按区域或自治系统的形式组织路由器。将一个大的将一个大的系统划分成若干小系统（自治系统），自治系统之间再系统划分成若干小系统（自治系统），自治系统之间再互连。互连。125r自治系统自治系统AS： 按按区域划分区域划分的系统。每个的系统。每个AS由一组在由一组在相同管理者相同管理者控制下控制下的路由器组成。的路由器组成。 同一个同一个AS内的路由器可运行相同的选路算法，且内的路由器可运行相同的选路算法，且拥有相互之间的信息。拥有相互之间的信息。自治系统内部选路协议自治系统内部选路协议 ： 在一个在一个自治系统内自治系统内运行的选路算法。运行的选路算法。网关路由器：网关路由器： 互连各互连各AS，负责转发目的地在本，负责转发目的地在本AS之外的分组（将之外的分组（将本本AS内的分组转发到另一个内的分组转发到另一个AS的路由器）。的路由器）。126自治系统间选路协议：自治系统间选路协议： 在在各各AS之间之间进行选路的选路算法。将分组从一个进行选路的选路算法。将分组从一个AS选路到另一个选路到另一个AS。路由器转发表：路由器转发表： 由由AS内部选路协议和内部选路协议和AS间选路协议产生。间选路协议产生。1273b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c例例AS间的互联间的互联三个自治系统：三个自治系统：AS1、AS2和和AS3。四个网关路由器：四个网关路由器： 1b、1c、2a、3a。自治系统内自治系统内分别运行各分别运行各自的内部选路协议；自的内部选路协议；自治系统间自治系统间运行运行AS间间选路协议。选路协议。1283b1d3a1c2aAS3AS1AS21a2c2b1b3c域间路由的任务域间路由的任务r假定假定AS1中的路由器接收中的路由器接收目的地是目的地是AS1外部的数据外部的数据报报m路由器应当路由器应当将分组朝着哪将分组朝着哪一个网关路由器转发一个网关路由器转发？AS1需要需要:r知道通过知道通过AS2可到达哪可到达哪些目的地，通过些目的地，通过AS3到到达哪些达哪些r传播这些可达信息到传播这些可达信息到AS1中所有路由器中所有路由器AS间选路的工作间选路的工作!129例子例子: 路由器路由器1d的转发表的转发表 设一个设一个子网子网x，AS1运行运行AS间选路协议后，得出：间选路协议后，得出：子网子网x只经只经AS3到达到达子网子网x可以经可以经AS3或或AS2到达到达3b1d3a1c2aAS3AS1AS21a2c2b1b3cx130AS间选路信息的交换间选路信息的交换r当一个当一个AS知道从一个相邻的知道从一个相邻的AS可以到达目的地，可以到达目的地，向所向所有其他的相邻有其他的相邻AS通告该选路信息。通告该选路信息。如，如，AS1从从AS2处得知，经处得知，经AS2可以到达子网可以到达子网x，AS1告告诉诉AS3，经，经AS1可以到达子网可以到达子网x。如果如果AS3向目的地向目的地x发送分组，先向发送分组，先向AS1转发，转发，AS1再再向向AS2转发。转发。3b1d3a1c2aAS3AS1AS21a2c2b1b3cx133主机 h2abbaaCABdcA.aA.cC.bB.acb主机h1在在A内的域内路由内的域内路由在在 A和和B之间的之间的域间路由域间路由在在 B内的域内路由内的域内路由例例 ：域内路由和域间路由：域内路由和域间路由主机主机h1向主机向主机h2发送发送134自治系统优点：自治系统优点：减少规模大的网络选路计算的复杂性：减少规模大的网络选路计算的复杂性： AS内部路由器运行相同的自治系统内部选路协议，内部路由器运行相同的自治系统内部选路协议，仅需要知道本仅需要知道本AS内的路由器与网关路由器。内的路由器与网关路由器。 各各AS之间，运行相同的之间，运行相同的AS间选路协议。间选路协议。管理职权灵活：管理职权灵活： 一个组织可自行选择一个组织可自行选择AS内部选路协议，每对相连内部选路协议，每对相连的的AS运行相同运行相同AS间选路协议，交换信息。间选路协议，交换信息。135因特网的层次选路因特网的层次选路r AS内部选路协议：内部选路协议：RIP选路信息协议：选路信息协议：基于距离向量的路由协议。基于距离向量的路由协议。OSPF开放最短路径优先：开放最短路径优先：采用采用Dijkstra最短费用路径最短费用路径算法，是一种链路状态协议。算法，是一种链路状态协议。rAS间选路协议：间选路协议：BGP边界网关协议边界网关协议：基于距离向量的路由协议。相邻基于距离向量的路由协议。相邻BGP路由器相互交换路径信息。路由器相互交换路径信息。136网络规模网络规模 网络很大：网络很大：路由器很多，计算的开销、存储及路由信路由器很多，计算的开销、存储及路由信息的通信等使息的通信等使选路计算非常复杂选路计算非常复杂。 因特网：因特网：数亿台主机组成，存储通向每台主机的信息数亿台主机组成，存储通向每台主机的信息需要巨大容量的内存。需要巨大容量的内存。 LS算法：算法：所有路由器广播链路状态更新的开销增大所有路由器广播链路状态更新的开销增大（占用很大的带宽）。（占用很大的带宽）。 DV算法：算法：在大量路由器中的迭代可能会不收敛在大量路由器中的迭代可能会不收敛!137管理自治管理自治 因特网是网络的网络。因特网是网络的网络。 网络中网络中所有路由器运行相同的选路算法所有路由器运行相同的选路算法，不一定适合，不一定适合某些组织。某些组织。 如，某公司希望按自己的情况运行路由器选路如，某公司希望按自己的情况运行路由器选路算法，或对外部算法，或对外部“隐藏隐藏”其网络的内部组织结构等。其网络的内部组织结构等。 理想情况，理想情况，一个组织能按自己的愿望运行和管理其网一个组织能按自己的愿望运行和管理其网络，又能连接到其他络，又能连接到其他“外部外部”网络。网络。138几种通信方式几种通信方式单播广播多播任播向一台主机寻址向所有主机寻址向某些主机寻址向一台或多台主机的几个接口寻址139单播和多播单播单播多播多播140多播多播特性特性r当当向向多个多个接收方接收方发送发送相同相同的的数据数据m更好更好的的带宽带宽利用率利用率m较少较少的的主机主机/ /路由器处理路由器处理m更快的参与更快的参与r应应用用m视视频频/ /音频音频广播广播 ( (电电视视，无线电无线电类类) )m视视频频会议会议m实实时时新闻新闻分发分发141 Internet 网络层转发转发表表选路协议选路协议路径选择RIP, OSPF, BGPIP 协议协议编址规则编址规则数据报格式数据报格式分组处理规则分组处理规则ICMP 协议差错报告路由器“信令”运输层运输层: TCP, UDP链路层链路层物理层物理层网络层网络层142IP：无连接交付系统rr提供不可靠、尽力而为、无连接提供不可靠、尽力而为、无连接提供不可靠、尽力而为、无连接提供不可靠、尽力而为、无连接分组交付服务分组交付服务m服务不可靠，服务不可靠，分组可能丢失、重复、延迟或不按序分组可能丢失、重复、延迟或不按序交付等交付等，但服务不检测这些情况，也不提醒发送方，但服务不检测这些情况，也不提醒发送方和接收方。和接收方。m服务是服务是尽力而为尽力而为的的，互联网互联网并不随意地丢弃分组并不随意地丢弃分组；只有当资源用完或底层网络出现故障时才可能出现只有当资源用完或底层网络出现故障时才可能出现不可靠性。不可靠性。m服务是无连接的服务是无连接的，每个分组都是独立对待的每个分组都是独立对待的。分组。分组序列可能经过不同的传输路径或者有的丢失有的到序列可能经过不同的传输路径或者有的丢失有的到达。达。143IP 数据报格式（IPv4）ver长度32 bits数据(变长,通常是一个TCP或UDP段)16-bit标识符首部检查和首部检查和寿命32 bit源IP地址IP协议版本号首部长度 (字节)剩余跳的最大数(在每台路由器减1)对分段/重装总数据报长度(字节)较高层协议交付的负载首部长度服务类型数据的“类型”标志段偏移高层32 bit目的IP地址选项 (如果有的话)例如，时间戳，记录所经路径，定义访问的路由器列表144IP地址（IPv4）节点在互连网中分配节点在互连网中分配的的一个唯一地址一个唯一地址。用于把分组送到目的用于把分组送到目的IP网络。网络。长度为长度为32比特比特。路由器通常有多个路由器通常有多个IP地址地址IPv6中IP地址扩展到地址扩展到128位位223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27145IP 地址结构A类：大型类：大型B类类：中型：中型C类类：小型：小型D类类：包括两部分：包括两部分： 网络号：网络号：指明主机所在指明主机所在物理网络的编号物理网络的编号。 主机号：主机号：主机主机在物理网络中的在物理网络中的编号。编号。0 网络号网络号10 网络号网络号1110110 网络号网络号146IP地址“点分十进制”表示 将将4个字节中的个字节中的每一个字节分别用十进制数来表示每一个字节分别用十进制数来表示，4个十进制数之间用个十进制数之间用 “.” 分隔。分隔。如如223.1.1.1 = 11011111 00000001 00000001 00000001223111147小结小结网络层服务：网络层服务：虚电路和数据报虚电路和数据报路由器：路由器：构成、工作原理构成、工作原理选路算法选路算法: : 链路状态和距离矢量链路状态和距离矢量层次选路：层次选路：自治系统自治系统148