网络层负责将数据包从源节点传送到目的节点.pdf

《网络层负责将数据包从源节点传送到目的节点.pdf》由会员分享，可在线阅读，更多相关《网络层负责将数据包从源节点传送到目的节点.pdf（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第 1 页BOOTPBOOTP 的缺点是它必须手工配置服务器中的数据库信息的缺点是它必须手工配置服务器中的数据库信息,当一台新的机器进入一个当一台新的机器进入一个.将到来的报片重新组装一个完整数据报的将到来的报片重新组装一个完整数据报的过程称为重组过程称为重组,重组是在目的主机中进行的重组是在目的主机中进行的.网络层负责将数据包从源节点传送到目的节点网络层负责将数据包从源节点传送到目的节点BOOTPBOOTP 的缺点是它必须手工配置服务器中的数据库信息的缺点是它必须手工配置服务器中的数据库信息,当一台新的机器进入一个当一台新的机器进入一个.将到来的报片重新组装一个完整将到来的报片重新组装一个完

2、整数据报的过程称为重组数据报的过程称为重组,重组是在目的主机中进行的重组是在目的主机中进行的.BOOTP 的缺点是它必须手工配置服务器中的数据库信息,当一台新的机器进入一个.将到来的报片重新组装一个完整数据报的过程称为重组,重组是在目的主机中进行的.第五章网络层网络层负责将数据包从源节点传送到目的节点，这中间可能会经过许多中间节点，也可能会穿过多个网络。这是网络层和数据链路层不同的地方，数据链路层只负责在相邻两个节点之间传送数据。网络层的主要功能是：路由选择、拥塞控制、网络互联和计费。1.1.网络层设计问题网络层设计问题网络层的主要设计问题包括网络层向传输层提供的服务，以及通信子网的内部设计。

3、（1）面向连接的服务与无连接服务无连接服务：以Internet 阵营为代表，认为通信子网本质上是不可靠的，用户肯定需要自己做差错控制和流量控制的工作，既然如此，通信子网干脆只提供最基本的数据传输服务就行了，即只负责将分组正确路由到目的节点，除此之外不提供差错控制、顺序控制、流量控制等其它功能。从这个思想出发，那么通信子网是无连接的，每个分组是一个独立的传输第 2 页单位，携带完整的地址，在每个节点被独立传输，分组之间彼此没有联系。面向连接的服务：以电信公司阵营为代表，认为通信子网应该提供可靠的面向连接的服务，在这里服务质量是一个重点需要考虑的因素。只有在通信前建立连接，才能进行服务协商并预留足

4、够的资源，才能保证象话音、视频等一类实时业务获得它们所需要的服务质量。这两派意见的焦点在于是否需要建立连接，至于是否需要保证数据传输的可靠其实是可选的。提供无连接服务的典型代表是因特网，提供面向连接服务的典型代表是电话网和ATM网络。事实上，由于实时多媒体应用的不断普及，服务质量的问题越来越受到关注，而因特网在这方面的局限性也日益凸现，因此因特网也在不断地改进，IPv6 就引入了面向连接的特性。（2）无连接服务的实现在提供无连接服务的通信子网中，每个分组被独立地传输，分组常被称为数据报，而通信子网则称为数据报子网。用图 5-2 的例子来说明数据报子网的工作原理：主机的网络层从传输层接收一个消息

5、。将消息封装成分组，发送给距它最近的路由器。若消息太大，超过了分组的最大长度，还需要先将消息划分成较小的数据块，再分别封装成分组。每个路由器都有一张路由表，记录各个已知的目的地址及这些地址所在的输出线路。每当从网络端口收到一个分组，首先判断自己是否是分组的目的地，是就将分组交给合适的上层实体去处理；否则用分组的目的地址查找路由表，从相应的输出线路转发分组。如果分组长度超过了输出链路上的最大传输单元（称MTU，Maximum TransferUnit），路由器的网络层必须将分组分成较小的片段，每个片段封装成分组，独立传输。目的主机的网络层将收到的分组交给传输层；如果分组被划分成了若干个片段，目的

6、主机先将各个片段重组，再交给传输层。路由器中的路由模块负责生成和维护路由表（使用路由算法），转发模块负责查找转发表和转发分组。转发表是根据路由表生成的、便于快速查找的数据结构。（3）面向连接服务的实现在提供面向连接服务的通信子网中，通信前首先需要建立一条从源节点到目的节点的传输通路（也称为连接），相关的数据包都沿着这条通路传输，传输结束后要释放这条通路。建立连接的目的是避免在每收到一个分组后，都要去查找庞大的转发表。其基本思想是，将从源主机到目的主机的路径记录在沿途经过的每一个路由器中，此后，该连接上的所有分组都在这条路径上传输。由于在同一条物理链路上可能存在多条连接，因此需要为每条连接分配一

7、个标识。每个分组必须携带其所属连接的标识，这样路由器检查分组头中的连接标识就知道分组属于哪个连接了。连接标识只具有局部意义，即同一条连接在不同的物理链路上可能被分配不同的连接标识。为此，路由器必须为经过它的所有连接建立一张连接表，对于每一条连接，记录其输入链路及在这条链路上的连接标识，还有输出链路及在输出链路上的连接标识。路由器在转发分组时，必须用输出链路上的连接标识替换分组头中的连接标识。从源主机到目的主机的连接称为虚电路，这是因为它只是表示了从源主机到目的主机的一条通路，与实际的物理通路（如固定地占用一个频道或时间片）并不相同。除了连接建立分组需要携带完整的网络层地址之外，其它分组只需要携

8、带一个连接标识第 3 页（虚电路号）。用图 5-3 的例子来说明虚电路子网的工作原理：源节点向目的节点发送一个连接建立分组，分组中携带完整的源地址和目的地址，并在源节点与源路由器之间的线路上选择一个当前未用的虚电路号，携带在分组头中；每一个中间节点收到连接建立分组后，根据分组的目的地址查找路由表，选择一条合适的输出线路，然后在输出线路上选择一个当前未用的虚电路号，替换分组头中的虚电路号，并在节点的虚电路表中记录下这条连接（输入线路，输入虚电路号，输出线路，输出虚电路号），最后从输出线路上转发该分组；这个过程不断重复直至到达目的节点，如果目的节点同意建立连接，则会发回一个连接确认分组，该分组沿着

9、相反的路径返回源节点，虚电路就建立起来了，这条虚电路是全双工的；随后，源节点在发送的每一个分组中都放入该分组所属的虚电路号，每个中间节点用输入线路和输入虚电路号查找虚电路表，用输出虚电路号替换分组头中的虚电路号，并从输出线路上转发分组，该过程不断重复直至分组到达目的节点；传输结束后，任何一方都可以发出一个连接拆除分组，收到该分组的节点删除虚电路表中的相应表项，并向下转发分组，当连接拆除分组到达另一方时，虚电路就被拆除了。（4）虚电路子网与数据报子网的比较虚电路子网与数据报子网各有其长处和短处：在虚电路子网中，每个分组（除连接建立分组之外）只需要携带较短的虚电路号而不是一个完整的目的地址，这可以

10、节省带宽，但却需要占用一部分内存空间来存放虚电路表；数据报子网刚好相反，它使用较小的内存空间，但要消耗较多的带宽。虚电路的建立需要花费一定的时间，但虚电路建立后，查找虚电路表进行分组转发是很快的；数据报子网虽然不需要连接建立时间，但每一个分组到达路由器时都要查找路由表转发，这个过程复杂得多也慢得多。由于在建立虚电路时可以预留资源，所以虚电路子网在提供服务质量保证和避免拥塞方面较数据报子网优越。由于节点或线路故障会使所有经过故障点的虚电路中断，而数据报却可以轻易地绕过故障点继续传输，因此数据报子网在健壮性方面较虚电路子网优越，而且数据报子网易于实现负载均衡。2.2.路由算法路由算法路由器的主要任

11、务是转发分组。在数据报网络中，路由器通过查找转发表来获得转发信息；而在虚电路网络中，路由器通过查找虚电路表获得转发信息。构建转发表和虚电路表的基础是路由器中维护的路由表。路由表是由路由算法建立起来的一张表，通常包含了从目的地址到分组转发路径上下一跳地址的映射。在我们考虑的互连网络环境中，每个终端节点通常有一台默认路由器（default router）。每当该终端欲与其它网络中的终端通信时，它总是将分组发送给它的默认路由器。我们将源主机的默认路由器称为源路由器，把目的主机的默认路由器称为目的路由器，则为一个分组选择从源主机到目的主机路由的问题归结为从源路由器到目的路由器的路由问题。我们可将路由问

12、题描述为：给定一组路由器和连接路由器的一组链路，寻找一条从源路由器到目的路由器的最佳路径。第 4 页什么是最佳路径呢？一般说来，视不同的应用而定，评价一条路径的好坏可能包括路径的物理长度、链路数据速率、分组传输延迟、通信费用、安全性等等。事实上，路径选择往往还要考虑到一些全局指标的优化，如网络吞吐量最大、平均包延迟最小、平均通信费用最低、网络负载均衡、路由稳定、健壮等等。显然，没有哪一条路径能够满足以上所有的指标，路由算法总是试图在几种重要的指标之间取得较好的折衷。为此，一般的做法是根据特定应用的需要使用一个代价函数将链路状态（如速率、延迟、费用等）映射为一个代价值，而路由问题就归结为寻找一条

13、从源路由器到目的路由器的代价最小的路径。一般来说，路由优化较多考虑最小化分组延迟和最大化网络吞吐量，但这是一对矛盾。人们通常所做的一个折衷是最小化分组经过的跳数（hop），因为减少跳数常常会减小分组穿过网络的延迟，同时也会消耗较少的带宽资源，从而提高吞吐量。按照路由算法使用的网络状态信息是全局信息还是局部信息，路由算法可以分为全局路由算法和分布式路由算法。全局路由算法由于使用全局状态信息易于获得较优路径，但状态信息交换需要消耗较多的网络带宽，分布式路由算法则相反。按照路由表是预先配置的还是动态生成的，路由算法可以分为静态路由算法和动态路由算法。静态路由算法根据网络流量的一般特性预先（离线）计算

14、好路由表，在网络初始化时下载到路由器中，此后不再改变。静态路由算法简单易行，但适应性差，只适用于负载稳定、拓扑变化不大的网络。动态路由算法随时根据网络当前的拓扑结构和流量特点计算路由表，适应性强，但算法复杂，实现难度大，而且容易引起路由循环及路由振荡等问题。（1）最优化原则最优化原则：如果路由器 J 位于路由器 I 和路由器 K 的最佳路径上，那么从路由器 J 到路由器 K 的最佳路径也落在这条路径上。（用反证法可以证明）推论：从所有源节点到一个指定目的节点的最佳路径形成了以目的节点为根的树，这棵树称为汇集树。所有路由算法的目的都是要发现和使用汇集树，但由于网络是动态变化的，每个节点对网络的了

15、解可能是不全面的，因此它们不一定总能找到汇集树，但汇集树可以用来衡量一个路由算法的好坏，看它能在多大程度上找到和使用汇集树。（2）最短路径路由选择研究路由算法常用的一种技术是将通信子网抽象为一张图，图中的顶点代表路由器，边代表通信线路（常称为链路），权代表链路的距离，这样在一对给定的路由器之间寻找一条最佳路由的问题，就转变成在图中一对给定的顶点间寻找一条最短通路的问题。在这里“距离”是一个广义的概念，它可以指跳数、物理距离、队列长度、传输延迟等等。一般情况下，权重是距离、带宽、平均流量、通信代价、平均队列长度、延迟及其它相关因素的函数，通过改变权重函数，路由算法就可以找出满足各种特定要求的最佳

16、路由。有好几种算法可以求图中两顶点之间的最短通路，以下介绍的是 Dijkstra 算法。Dijkstra算法的基本思想是，从源（目的）点开始，首先求离源（目的）点最近的通路，然后求离源（目的）点次近的通路，依次类推，直至有一条通路到达目的（源）顶点，则这条通路就是源点与目的顶点之间的最短通路。例见图5-7，程序算法见图 5-8。（3）扩散法扩散法是一种静态路由算法，每一个输入的分组都被从除输入线路之外的所有其它线路上转发出去。扩散法显然会产生大量的分组副本，因此必须有一些办法来抑制无限的转发。一种办法是在分组头中携带一个跳数计数器，分组每到一个节点其跳数计数器就减1，第 5 页当计数器为 0

17、时分组被丢弃。计数器的初始值可以设为通信子网的直径，即相距最远的两个节点之间的跳数。另一种办法是记住哪些分组已经转发过了，从而确保一个分组不会被同一个节点转发两次。这要求源路由器从主机收到一个分组后，将一个序号放入分组头中，同时每一个路由器对于每一个源路由器都要维护一张序号表，记录从每一个源路由器上已经收到的分组的序号。每当一个路由器收到来自某个源路由器的分组时，就用分组的序号去查找该源路由器的序号表，如果序号已在表中则该分组被丢弃。为了防止序号表过大，序号表中还应增设一个计数器 k，表示序号直至 k 的分组都已经转发过了，从而不需要保留序号小于k 的序号。扩散法的一种较实用的变形是选择性扩散

18、，在这种算法中分组只朝着大致正确的方向转发，而不是转发到除输入线路外的所有线路上。尽管扩散法在很多应用中都不实用，但它确实也有一些适用的地方。比如由于扩散法的鲁棒性（robustness）很好，它在战场的军事网络中特别有用；其次扩散法在本质上是一种广播式的路由算法，因此在一些要求广播传输的应用中也很有用，如分布式数据库的同步更新；在无线网络中位于发送站功率范围内的所有站都能收到发送站发送的消息，这其实也是一种扩散的形式，这个特性常被一些算法所利用；由于扩散法总能找到最短通路，因此其它路由算法都可以和扩散法进行比较，以衡量各自的算法性能。（4）距离矢量路由算法距离矢量（Distance Vect

19、or，DV）路由算法是一种应用广泛的动态路由算法，曾被早期的 ARPANET、DECnet 和 Novell的 IPX 采纳作为路由算法，目前因特网中的RIP 协议和 BGP协议使用的也是这个算法。路由问题本质上是图论中的一个问题。以节点代表路由器，边代表路由器之间的链路，权代表链路的代价，路由的基本问题是找出任意两个节点之间代价最小的路径。路径的代价等于组成这条路径的所有边的代价之和。距离矢量算法解决这个问题的基本思想是：假设源节点知道自己到每个邻居节点的链路代价（即距离），以及每个邻居节点到目的节点的最小代价，则最小代价路径问题就是求源节点的一个邻居节点，使得通过该邻居节点到达目的节点的代

20、价最小。用数学语言描述就是：dx(y)=minpc(x,p)+dp(y)，pN(x)，其中 x 和 y 分别为源节点和目的节点，N(x)为 x 的直接邻居集合，dx(y)为从 x 到 y 的最小代价路径的代价，c(x,p)为 x 到其直接邻居 p 的链路代价。该方程称为 Bellman-Ford 方程，因此 DV 算法也称为分布式 Bellman-Ford 算法。为求解此问题，DV 算法要求每个节点知道自己到所有邻居节点的距离（即c(x,p)），这是完全可以做到的。这里的距离是一个广义的概念，可以指到目的节点的跳数、到目的节点所需的时间、或者到目的节点的分组队列长度等。若按跳数计算距离，则相邻

21、节点间的距离等于 1；若以延迟计算距离，则每个节点只需和各个邻居节点交换特殊的“回声”分组，根据发送和接收到分组的时间差就可以推算出到各个邻居节点的延迟时间；若以分组队列长度计算距离，则只需统计一下去往该节点的分组数量即可。对于非相邻的节点，初始时可假设距离为无穷大。其次，DV 算法要求每个节点知道其邻居节点到目的节点的最小距离，这需要通过邻居节点之间的消息交换来实现。DV 算法要求每个节点（设为 x）维护一张路由表，网络中每个节点在此表中占有一个表项，并以节点作为路由表的索引。每个表项包括两部分内容：去往该目的节点（设为y）的最佳输出线路（用下一跳节点p 进行标识）以及估计到该目的节点的最短

22、距离（即 dx(y)）。每个节点定期地和它的所有邻居节点交换路由表中的距离列表（即距离矢量），通报从本节点到其它各个节点的估算距离。每个节点利用从邻居节点收到的距离矢量，使用 Bellman-Ford 方程更新自己的距离矢量，并计算新的路由表。第 6 页若某个节点 x 与邻居 p 的距离为 m（即 c(x,p)），p 发布的距离矢量中 py表示节点 p 与 y之间的距离(即 dp(y)，则 x 判断自己通过 p 到达 y 的距离为 m+py；利用每个邻居节点发来的距离矢量进行同样计算，x 可以找到到达 y 的最佳输出线路；同样可以找到到达所有其它节点的最佳输出线路，更新路由表。例见图5-9。注

23、意在计算新路由表时，完全没有用到老的路由表。距离矢量路由算法的一个问题是算法有时收敛很慢，特别是它对坏消息的响应很慢，比如图 5-10 中的例子。出现这个问题的根本原因在于每个路由器发布的路由消息不完全是可靠的，特别是它不知道自己是否正在这条路径上。人们一直在努力解决这个问题，但至今为止仍然没有一个理想的解决方案。（5）链路状态路由算法链路状态路由算法于 1979 年代替了 ARPANET中的距离矢量路由算法，现在各种各样的链路状态路由算法得到了非常广泛的应用，如OSPF、IS-IS 等。LS 算法的基本思想是，每个节点利用可靠的方法获知其邻居节点以及到各邻居节点的链路的代价，通过与网络内其它

24、节点交换这些信息来获得关于全网的拓扑信息，即网中所有的节点、链路和链路的代价，将这些拓扑信息抽象成一张带权图，然后用图论的方法计算出到各个目的节点的最短路径。链路状态路由算法包括以下五个部分：发现邻居，获知邻居的网络地址；测量到每个邻居的延时；将以上信息构造成链路状态分组；向所有节点发送链路状态分组；计算到每个节点的最短路径。发现邻居：当路由器启动时，首先在它的每一条输出线路上发送一个特殊的 HELLO 分组，收到HELLO 分组的路由器必须尽快返回一个应答，告知自己的全局唯一地址。测量线路延时：最直接的方法是路由器在线路上发送一个特殊的ECHO 分组，收到 ECHO 分组的路由器必须立即发回

25、一个应答，通过测量发送与接收之间的时间（来回时间）并除以2，可以得到单向的线路延时。可以多测几组数据，求平均线路延时。显然在这里我们假设延时是对称的，但实际上并不总是这样。在计算线路延时时要不要考虑线路上的负载，这是一个颇有争议的问题。如果考虑线路上的负载，那么发送时间应从 ECHO 分组放入队列时算起；如果不考虑线路负载，那么发送时间应从 ECHO 分组到达队头时算起。考虑线路负载意味着当两条线路的带宽相同时，路由器将选择负载较轻的线路作为最佳输出线路，这种选择能导致良好的性能。但这会使轻负载的线路很快超载，从而另一条线路又成为最佳选择，这样容易引起路由表的剧烈振荡，导致不稳定路由和其它潜在

26、问题的产生，如图 5-12。只考虑带宽不考虑负载就不会出现这种问题，但完全不考虑负载也是不合理的，它会使流量都集中到高带宽的线路上，而低带宽的线路却很空闲。以上问题的根源在于路由器总是选择最佳线路转发分组，这很容易引起负载不均衡，因此较明智的做法是将负载按一定比例分布到多条线路上。构造链路状态分组：一旦收集到了各个邻居节点的地址及到各个邻居的线路延时之后，就可以构造一个链路第 7 页状态分组来携带这些信息。分组格式见图 5-13(b)，首先是发送方地址，然后是分组序号和寿命，最后是一个邻居列表，每个表项包括一个邻居地址和到这个邻居的延时。什么时候构造链路状态分组比较合适呢？一种办法是周期性地产

27、生链路状态分组，另一种办法是仅在发现网络拓扑发生改变时才产生，如邻居集合发生了变化，或到邻居的线路延时发生了变化。发送链路状态分组：该算法最复杂的部分是如何可靠地发送链路状态分组。当分组被发送和安装后，首先得到分组的路由器就会用它来改变自己的路由表，此时不同的路由器可能会使用不同的网络拓扑版本，这可能导致不一致、路由环路、不可达节点和其它问题。为了可靠地发送链路状态分组，采用了扩散法。每个分组携带一个序号，每当发送一个新的分组时，分组序号就加1。每个路由器维护一张由（源路由器，序号）对组成的列表，记录从每个源路由器收到的最新的分组序号。当一个链路状态分组到来时，用分组中的源路由器地址和序号查表

28、，如果这是一个新的链路状态分组，就用扩散法将其转发出去，否则将分组丢弃。采用序号来区分新旧分组是会有一些问题的，一是当序号折回时，新的分组都会被丢掉；二是当路由器发生崩溃并重起后，只能从序号 0 开始发送，这些分组也会被丢弃；三是当序号在传输过程中出错时，如4 变成了 65540，则其后大量的分组都会被丢掉。为解决序号折回的问题，使用了32 比特长的序号，这样即使每隔一秒发送一个链路状态分组，也需要 137 年的时间才会发生序号折回。针对后两个问题，解决的办法是在分组中增加一个寿命域，不管分组在网络中的什么地方，其寿命均每隔一秒减1，当寿命减为0 时分组被丢弃。还有一些改进的措施可增加算法的鲁

29、棒性。当一个链路状态分组进入一个路由器并需要扩散时，该分组并不马上放到传输队列里，而是放到一个临时区域中等待一小段时间。如果在该分组被发送前，来自同一个源路由器的另一个链路状态分组到来，则将这两个分组的序号进行比较。如果序号相同，就丢弃后来的分组；如果序号不同，则序号小的分组被丢弃。为防止分组在路由器到路由器的传输线路上出错，所有链路状态分组都必须被确认。当线路空闲时，临时区域被循环扫描，从中选择一个分组或确认进行发送。路由器将收到的链路状态分组存放在分组缓冲器中，使用图 5-14 所示的数据结构。每一行对应一个最近收到的但还未处理完毕的链路状态分组，除记录该分组的源路由器、序号、寿命、数据以

30、外，对应每一条输出线路还有发送和确认两个标志位，用来指示是否要在这条线路上转发或确认这个分组。解释例5-14。计算新路由：一旦一个路由器收集齐了一整套链路状态分组，它就可以建立完整的通信子网图，在这张图中每条链路均被报告了两次，这两个值可以分开用，也可以求平均值。图建立起来后，就可以运行 Dijkstra 算法求路由器到任何目的路由器的最短通路。（6）分级路由选择当网络变得很大时，要求每个路由器都知道到所有其它路由器的路径是不可能的，路由表会变得非常庞大，需要占用大量的内存，花费大量的 CPU 时间用于路由表的查找和维护，消耗大量的带宽用于路由信息的交换，这时采用分级路由选择是必然的。采用分级

31、路由选择时，将路由器划分到不同的区域中，每个路由器知道到区域内所有其它路由器的路由，但不知道其它区域内的路由细节。当需要将分组转发到其它区域时，路由第 8 页器只是简单地将分组发给区域内的网关路由器去处理。当将不同的网络互联在一起时，每个网络自然成为一个区域。当网络规模非常大时，两级往往是不够的，需要分成多级，每一级路由器都知道本级内如何路由，但必须通过上一级路由器将分组转发到本级之外的节点。一个两级网络的例子见 5-17。分级路由选择使得路由表的大小显著减小，但可能会因此增加某些节点的路径长度，当网络规模很大时这个代价是值得的。研究表明，有 N 个路由器的通信子网的最佳级数为lnN，每个路由

32、器需要的表项总数为elnN，由分级路由选择引起的有效平均路由长度的增长是很小的，完全可以接受。划分区域的一种很自然的方法是按管理域（也称自治域，AS）进行划分，因为每个组织都要求按自己的意愿运行和管理网络，或对外部隐藏网络的内部组织等。对于较大的自治域，还可以进一步将自治域划分成区（area）。区是 OSPF 的术语，一个区是从管理上配置成相互交换路由信息的路由器的集合。通过将域划分成区，可使单个域变得更大而又不会加重域内路由协议的负担。图示是一个划分成 4 个区的域。主干网区是一个特殊的区（也称区 0），不同区之间的通信都要通过主干网区进行。既是主干网区也是非主干网区成员的路由器称为区边界路

33、由器（Area Boarder Router，ABR），R1、R2 和 R3 都是区边界路由器。当分组要从一个非主干网区传送到另一个非主干网区时，分组首先到达与源网络相连的一个 ABR，然后穿过主干网区到达与目的网络相连的一个ABR，最后从该 ABR 进入目的网络。分组在非主干网区内的转发使用区内路由表，这是由同一个区内的路由器通过彼此交换链路状态信息生成的。为使源 ABR 能够准确地将分组转发到目的ABR，每个 ABR 汇总从其所在的非主干网区了解到的路由信息，计算到该区中每个网络的路由代价，然后将这些信息发送给区0 的所有节点。与此同时，每个 ABR 也汇总从其它 ABR 收到的路由信息，

34、并将这些信息通知到自己所在的非主干网区。这样，域中所有的路由器都知道如何到达域中的每个网络。当非主干网区中有多个 ABR 时，比如 R1 和 R2 均是区 2 中的 ABR，由于这些 ABR 发布的路由代价不相同，通过运行最短路径算法可知哪一个ABR 是最佳的。比如，对于区1 中的目的地来说，显然R1 是比 R2 更好的选择。（7）广播路由有些应用需要将消息发送给网络中所有的主机。将一个分组同时发送给所有目的节点，这称为广播，有多种方法可以实现广播发送。第一种方法是用单播的方式向每一个目的主机单独发送一个分组。这种方法浪费带宽，而且要求源主机知道网络中所有的目的主机。第二种方法是扩散法，这种方

35、法会产生较多的分组副本，需要采取一些措施限制过多的扩散。第三种方法是多目的路由，它要求每个分组携带一个目的地清单，每到一个路由器时，路由器检查所有的目的地址以确定一个最小的输出线路集合，在该集合的每一条线路上转发分组的一个副本，分组中仅携带使用该线路的目的地。当经过足够多次的转发后，每个分组将仅携带一个目的地，此时可将它当作普通的分组对待。多目的路由可以节省带宽的消耗，但仍要求源主机知道网络中所有的目的主机。第四种方法使用通信子网的生成树来转发分组，生成树是通信子网的一个子集，它包括所有的路由器但不存在回路，每个路由器仅将收到的分组转发到除输入线路以外的所有生成树线路上。这种方法生成的分组副本

36、数最少，消耗的带宽最少，但它要求每个路由器知道通信子网的一棵生成树，这个条件并不总是能够满足的（如采用距离矢量路由算法的通信子网）。第五种方法是反向路径转发，它只使用节点内部的路由表来转发广播分组，除此之外不第 9 页需要任何其它的知识，而且它产生的分组副本数比扩散法要少得多，性能与使用生成树的方法差不多。反向路径转发的基本思想是，当广播分组到达路由器时，路由器检查分组的源地址与输入线路，若输入线路与路由表中去往该地址的输出线路相同，则该分组很可能是来自该源路由器的第一个分组拷贝，于是路由器扩散转发该分组，否则将分组丢弃。例见图 5-20。这种方法的好处是算法合理、有效、易于实现且开销不大。（

37、8）多播路由在有些应用中，分散在各地的一些用户需要以小组的方式协同工作，一个用户需要向小组内的其它成员发送消息。如果组内成员很少，可以用单播的方式向每个成员发送消息；如果组包含了网络中的绝大部分用户，那么可以用广播的方式发送；如果组内成员绝对数量较多，但与全体用户数相比相对数量又很少，那么以上两种方式均不经济，这时候采用多播方式发送是最合适的。将一个分组发送给组内的所有成员，这称为多播。目前的网络适配器（Network Interface Card，NIC）都支持物理网络中的多播实现。NIC允许 CPU 描述和改变要监听的多播地址集合，由于 NIC 的存储空间有限，许多 NIC 限定多播地址集

38、合的大小为 64。实际上，一个典型的应用在任何时候只加入一到两个多播组（如接收一个音频流和/或一个视频流），而一个节点上任何时候最多只有几个应用加入多播，因此大多数计算机系统只同时使用几个多播地址。当多播帧到来时，将帧头中的多播地址与地址集合中的64 个地址逐一比较是一件费时的工作，一般的 NIC 都没有足够的计算能力在短时间内完成。为此，NIC 硬件采用了一种优化的实现方法。NIC 维护一个 64 比特的矢量，并用一个哈希函数将多播地址映射成0，63之间的一个数。从本质上说，这是将所有可能的多播地址划分成64 个组，每个组对应矢量中的一个比特。对于 CPU 指定要监听的每个多播地址计算一个哈

39、希值，并将矢量中对应比特的值置为 1。当一个多播帧到达时，NIC 计算该地址的哈希值，然后检查矢量中对应比特的值。若该比特的值为1，则接收该帧，否则丢弃。在这个方案中，NIC 不会漏掉任何一个该接收的多播帧，但可能会收下一个地址不匹配的帧，虽然这种概率是很低的。进一步的检查工作由 CPU 完成，即 CPU 收到一个多播帧后要检查其目的地址是否匹配。在互联网中实现多播传输的基本思想是：（1）所有欲接收相同分组的节点构成一个多播组（multicast group），每个组分配一个唯一的多播地址，发送给该组的分组均以该多播地址为目的地址。（2）网络中任何一个主机都可以选择加入或离开这个组，网络中运行

40、的组管理协议负责建立、维护和删除多播组。（3）网络中运行一个多播路由协议，负责为每个组建立多播转发树，多播转发树是能够到达该组所有成员主机的路径树。（4）当一个多播分组到达中间路由器时，中间路由器根据相对应的多播树转发分组。（5）当多播分组到达“最后一跳”路由器（与多播组的成员主机位于相同的物理网络上）时，使用物理网络的底层多播功能将分组发送到目的主机。可以通过扩展已有的单播路由算法（链路状态和距离矢量算法）来实现多播路由。在链路状态路由算法中，每个节点知道整个网络的拓扑信息，能够计算出从本节点到任一其它节点的最短路径。为支持多播路由，节点只需要再知道每个多播组的成员分布（连接）在哪些链路上即

41、可。为此，可令所有参与多播的主机定期在局域网上通报其所属的多播组，路由器监视这些消息，记录在每一条直连链路（局域网）上监听到的多播组，然后将每条链路对应的多播组集合作为链路的状态在网上广播。一旦知道了每个多播组所涉及的链路，每个路由器就可以计算出从任一源节点到任一多播组的最短路径多播树。需要注意的是，每个路由器必须有能力保存从每个源节点到每个多播组的最短路径多播树。显然这样的代价很高，因此，实际中路由器只计算并缓存当前活跃的（源节点，多播组）所对应的最短路径多播树。第 10 页扩展距离矢量路由算法要复杂一些，因为节点不知道整个网络的拓扑结构。在距离矢量路由算法中，每个节点只和相邻节点交换距离矢

42、量，知道到每个目的节点的最短路径上的下一跳，但无法知道每个多播组和哪些链路有关。对距离矢量路由算法的扩展包括两个方面。第一，由于节点不知道哪些链路连接了一个多播组的成员，因此需要设计一种广播转发机制，确保多播分组能够到达每一个局域网。第二，由于广播转发无法避开那些没有多播组成员的局域网，造成大量的无用传输，因此需要设计一种路径剪枝（prune）机制，将那些不包含组成员主机的网络排除在外。广播转发可采用逆向路径转发机制。为删除不包括组成员主机的网络，剪枝过程从叶子网络开始。参与多播的主机定期在其局域网上通报所属的多播组，连接在局域网上的路由器监听并汇总这些消息。当路由器收到一个发往组 G 的分组

43、而它并没有从局域网上监听到组G 的报告时，该路由器向其上游路由器（即在分组到来的输入链路上）发送一个剪枝消息，上游路由器从路径树中删除这个分支。如果一台路由器从它的每个下游路由器都收到剪枝消息，则它向上游路由器转发一个剪枝消息。这个过程递归进行，直至所有的无关分支都被删除，最终得到一棵以源 S 为根的组 G 的多播树。第一个应用于因特网并受到最广泛支持的多播路由协议 DVMRP（Distance-Vector Multicast Routing Protocol）就是采用了这种逆向路径转发加路径剪枝的多播路由算法。该算法的缺点是可扩展性较差，若网络中有 n 个多播组，每个组平均有 m 个成员，

44、则对于每个组需要保存 m 棵剪枝的生成树，总共需要保存 mn 棵剪枝的生成树。当网络中有大量的多播组存在时，需要消耗大量的内存。另外，如果绝大部分路由器都不需要参与多播发送，那么将多播分组广播到所有路由器，直到那些路由器发送剪枝消息明确要求将其删除，就不是一个好的设计选择。为解决多播路由的可扩展性问题，提出了基于核心的多播树。每个多播组只建立一棵由所有组成员共享的多播树，核心即为树根节点。当需要向该组发送多播分组时，多播分组首先被发送到核心节点，然后由核心节点进行转发。由于每个多播组只建立一棵共享树，内存的消耗大大减少了。共享树的缺点是分组转发路径可能不是最优的，分组从源节点到核心节点再到目的

45、节点的路径，可能比从源节点直接到目的节点的路径要长得多。这是共享树为实现可扩展性而付出的性能代价。第二种广泛应用于因特网并专为解决可扩展性问题而开发的多播路由协议是PIM（Protocol-Independent Multicast）。PIM 将多播路由问题划分为稠密模式和稀疏模式两种情况，稠密模式是指区域中的许多或大多数路由器都涉及多播路由过程，而稀疏模式是指只有很小一部分路由器涉及多播路由过程。在稠密模式中，PIM 采用广播与剪枝相结合的多播路由算法，类似于 DVMRP 的思想。在稀疏模式中，PIM 采用共享树的方法。但 PIM 的一个新颖之处是，当源节点的数据流量比较大时，可以从共享树切

46、换到特定源树，以提高分组转发的效率。在 PIM 稀疏模式中，每个多播组要选择一个汇集点（Rendezvous Point，RP）。RP 的选择过程非常复杂，在后面的讨论中假设所有路由器都知道某个给定多播组的RP的单播地址。当一个路由器 S 从其所在的局域网上监听到多播组 G 的通报时，路由器用单播方式向组 G的 RP 发送一个 Join 消息。Join 消息在到达 RP 之前要经过一系列的路由器，这些路由器均在转发表中创建一条共享树的记录，称为（*，G）记录（*表示所有发送方）。其中，Join消息到达的接口被标记为转发多播组 G 的分组的接口，向 RP 进一步转发 Join 消息的接口被标记为

47、本节点允许接收多播组 G 的分组的唯一接口。当 Join 消息到达 RP 时，就完成了从 S 到 RP 的分支建立过程。随着更多的路由器向RP 发送 Join 消息，新的分支被添加到共享树上，最终形成一棵以 RP 为根的共享树。当一个主机希望发送一个分组到组G 时，它构造一个目的地址为 G 的多播地址的分组，发送给局域网上一个指定的多播路由器（称指派路由器）。指派路由器用单播的方式将分组发送给 RP（使用隧道技术），然后由 RP 在共享第 11 页树上转发。当树的下游路由器（在转发方向上远离核心节点）观察到从某个源主机发来的数据量很大时，可以向源主机发送一个 Join 消息。Join 消息按最

48、短路径传向源节点，沿途经过的每个路由器都在转发表中创建树的（S，G）状态，最终得到一棵以源节点为根而不是以 RP 为根的多播转发树。此后，由该源主机发往组G 的多播分组均沿这棵特定源树转发。（9）移动主机路由所谓移动主机是指改变了网络接入点的主机。有两类移动用户，一类是迁移用户，他们基本上是静态的，但经常需要从一个固定网络转移到另一个固定网络，但在转移的过程中不进行通信；另一类是漫游用户，他们不断地改变网络接入点，而且在移动的过程中仍然需要保持通信。后一种移动在处理上需要考虑的最主要问题是如何在移动的过程中保持通信的连续性及服务质量。移动网络需要解决的第一个问题就是如何找到移动的主机，以下是一

49、种可能的路由方法。为了随时跟踪移动的主机，要求每个主机都有一个家乡网络以及在家乡网络上的一个家乡地址，这个家乡地址是一个永久地址，其它节点总是能够通过这个地址找到主机的，同时当主机连接在外地网络时还有一个在外地网络有效的临时地址（称为转交地址）。每个网络中有一个家乡代理，还有一个或几个外地代理。家乡代理为那些家乡地址在本网络但目前游离在外的移动用户服务，包括记录用户当前的转交地址，以及将发至家乡地址的数据包转发到用户的转交地址等。外地代理为那些家乡地址不在本网但目前连在本网上的用户服务，主要是为外地节点提供转交地址，并作为这些节点的缺省路由器，为他们转发数据包。当一个移动用户进入到一个外地网络

50、时，它必须获得一个转交地址，然后向家乡代理注册，并请求外地代理的路由服务。具体过程如下：每个外地代理定期地广播一个分组，宣布自己的存在及地址；移动节点通过接收这些分组并分析外地代理的地址，可以判断自己是否处于外地网络上以及是否切换了网络，如果在外地网络上则使用外地代理地址作为自己的转交地址；移动节点向外地代理发送一个注册消息，给出自已的家乡地址、家乡代理地址及认证信息等；外地代理向家乡代理转发该注册消息；家乡代理对注册消息进行认证，若有效则将移动节点的家乡地址及转交地址保存在绑定表中，然后发回一个注册应答消息；外地代理收到有效的注册应答后，将移动节点记录在自己的转发表中。其他节点使用移动节点的