五、因特网的路由选择协议

1.有关路由选择协议的几个基本概念

Ⅰ、理想的路由算法

路由表中的路由是怎样得出的呢？核心是路由算法。一个理想的路由算法要正确且完整、计算简单、能适应通信量和网络拓扑的变化、算法要有稳定性、公平、最佳（这里指相对于某一种特定要求下得出的较为合理的选择）。

路由选择是复杂的，因为它是网络中的所有结点共同协调工作的结果，而且环境一直在变，可能发生拥堵。这样很难从网络中的各结点获得所需的路由选择信息。

静态路由选择策略：也叫非自适应路由选择，简单、开销小、但不能及时适应网络状态的变化，适应于简单的小网络

动态路由选择策略：也叫自适应路由选择，能较好适应网络状态变化，但实现复杂、开销大。

Ⅱ、分层次的路由选择协议

因特网采用的路由选择协议主要是自适应的、分布式的。分层原因：①因特网大，路由表大，处理起来耗时；②许多单位不愿意外界了解自己单位网络的布局细节。

于是因特网将整个互联网划分为许多较小的自治系统（autonomous system），记为AS。AS经典定义是在单一技术管理下的一组路由器，而这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由，同时还用一种AS之间的路由选择协议用以确定分组在AS之间的路由。一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。

（1）内部网关协议IGP（interior gateway protocol）：与外部无关，多用RIP、OSRF，自治系统之间的路由选择也叫域内路由选择。

（2）外部网关协议EGP（external gateway protocol）：若源主机和目的主机处在不同自治系统中（这两个自治系统可使用不同的网关协议），当数据报传到一个自治系统的边界时，就需要使用一种协议将路由器选择信息传递到另一个自治系统中，这样的协议就是外部网关协议EGP。自治系统之间的路由选择也叫域间路由选择。多用BGP（外界网关协议BGP，border gateway protocol）。

2.内部网关协议RIP

Ⅰ、工作原理

路由信息选择协议RIP（routing information protocol）是内部网关协议IGP中最先得到广泛使用的协议，是一种分布式的基于距离向量的路由选择协议，是因特网的标准协议，其最大优点是简单。

要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。从一路由器到直接连接的网络的距离定义为1，从一路由器到非直接连接的网络的距离定义为所经过的路由器加1。也有定义：到直接连接的网络的距离为0。距离也称跳数（hop count）。

RIF协议和哪些路由器交换信息——仅和相邻路由器交换信息

交换什么信息？——交换信息是当前本路由器所知道的全部信息，即自己的路由表。即：我到本自治系统中所有网络的（最短）距离，以及到每个网络应经过的下一跳路由器。

什么时候交换信息？——按固定的时间间隔交换路由信息。如每隔30s，或者网络拓扑发生变化时。

它主要信息是什么？——到达某个网络的距离（即最短距离），以及应经过的下一跳地址。更新原则是找到每个目的网络的最短距离，这种更新算法又称为距离向量算法。

路由器只知道直接连接的网络的距离，接着每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息，这样多次以后，所有路由器知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。它有点像市场里聒噪的人，但又收敛，即在自治系统中所有的结点都得到正确的路由选择信息的过程。

Ⅱ、距离向量算法

（1）对每一个相邻路由器发送过来的RIP报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，并把所有的“距离”字段的值加1。每一个项目都有三个关键数据，即：到目的网络N，距离是d，下一跳路由器是X。

[这样做原因——便于进行本路由的更新，假设从位于地址X的相邻路由器发来的RIP报文的某一个项目是：“Net2，3，Y”，意思是“我经过路由器Y到网络Net2的距离是3”，那么本路由器就可推断出：“我经过X到网络Net2的距离应为3+1=4”。于是，本路由器就把收到的RIP报文的这一个项目修改为“Net2，4，X”，作为下一步和路由器原有项目进行比较时使用（只有比较后才知道是否需要更新）。]

（2）对修改后的RIP报文中的每一个项目，进行一下步骤：

若原来路由表中没有目的网络N，则把该项目添加到路由表中。

[这样做的目的——表明这是新的目的网络，应当加入到路由器中。]

否则（即在路由表中有目的网络N，这时就再查看下一跳路由器地址）

若下一跳地址路由器地址是X，则把收到的项目替换原路由表中的项目。

[替换的目的——这是最新的消息，要以最新的消息为准。到目的网络的距离有可能增大或减小，但有可能没有改变。]

否则（即这个项目是：到目的网络N，但下一跳路由器不是X）

若收到的项目中的距离d小于路由器中的距离，则进行更新。

[这样做的目的——使距离最短]

否则什么也不做。

[这样做的原因——若距离更大了，显然不应更新。若距离不变，更新后得不到好处，因此也不更新。]

（3）若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，则把距离置为16（距离为16表示不可达）。

（4）返回。

上述算法基础：Bellman-Ford算法。设X是结点A到B的最短路径上的一个结点，若把路径A→B拆成两段路径A→X和X→B，则每一段路径A→X和X→B也都分别是结点A到X和结点X到B的最短路径。

Ⅲ、举例

R6收到相邻路由器R4发来的路由更新信息，现在更新R6的路由表。

解：如同路由器一样，我们不需要知道该网络的拓扑。先把距离加1，并把下一跳路由器都改为R4，得出下表：

把这个表和a比较。第一行在a中没有，就添加到a中。第二行的Net2在表中有，且下一跳路由器也是R4，因此要更新（距离增大了）。第三行的Net3在a中有，但下一跳路由器不同，于是比较距离，新的路由信息的距离是2，小于原来表中的4，因此要更新。这样更新后的R6的路由表如下：

RIP协议让一个自治系统中的所有路由器都和自己的相邻路由器定期交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。这里还应注意：虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也是不同的。

Ⅳ、RIP协议的报文格式

较新版本是RIF2，可支持变长子网掩码和CIDR，还提供简单的鉴别过程支持多播。RIF2和RIF1的首部相同，但后面的路由部分不一样，它使用运输层的用户数据报UDP进行传送（使用UDP的端口520）。

解释：命令字段指出报文意义，1表示请求路由信息，2表示对请求路由信息的响应或未被请求而发出的路由更新报文。首部后面“必为0”是为了4字节字的对齐。地址族标识符（又称为地址类别）字段用来标志所使用的地址协议。如采用IP地址就令这个字段的值为2（原来考虑RIP也可用于其他非TCP/IP协议的情况）。路由标记填入自治系统号ASN（autonomous system number），这是考虑使RIP有可能收到本自治系统以外的路由选择信息。

一个报文最多可包括25个路由，因而RIP报文的最大长度是4+20*25=504字节。如超过，必须再用一个RIP报文来传送。

鉴别功能时报文怎么变？——把原来写入第一个路由信息（20字节）的位置用作鉴别，这时应将地址族标识符置为全1，而路由标记写入鉴别类型，剩下的16字节为鉴别数据。在鉴别数据之后才写入路由信息，但这时最多只能再放入24个路由信息。

Ⅴ、评价

缺点——当网络出现故障时，要经过很长时间才能将此信息传送到所有的路由器。好消息传播得快，而坏消息传播得慢。举例如下：

在R1将“1,16，直接”传递到R2之前，有30s，然而R2可能已经把自己的路由表信息发送给了R1。R1收到后误认为R2可能到达网1，所以把路由信息修改为“1,3，R2”，表明“我到网1的距离是3，下一跳经过R2”，并把更新的信息发送给R2。等等。

为使坏消息传播得更快，可以让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送。

优点：实现简单，开销小

缺点：①RIF限制了网络的规模，它能使用的最大距离为15（16表示不可达）

②路由器间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。

③坏消息传播得慢，使更新过程的收敛时间过长。

3.内部网关协议OSPF

Ⅰ、OSPF协议的基本特点

名字：最短路径优先OSPF（open shortest path first），使用了Dijkstra提出的最短路径算法SPF。它不表示其他的路由选择协议不是“最短路径优先”。实际上，所有自治系统内部使用的路由选择协议（包括RIF协议）都是要寻找一条最短的路径。

最主要特征——使用分布式的链路状态协议（link state protocol），而不是像RIF那样的距离向量协议。

和RIP相比的特点：

如何发送信息？——向本自治系统中所有路由器发送信息。这里用洪泛法，路由器通过所有输出端口向所有相邻的路由器发送信息，而每一个相邻路由器又将此信息发往其所有的相邻路由器（但不再发送给刚刚发来信息的那个路由器）。这样，最终整个区域中所有的路由器都得到了这个信息的一个副本。而RIP只是向自己相邻的几个路由器发送信息。

发送什么信息？——与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”（表示费用、距离、时延、带宽等）。

什么时候发送信息？——当链路状态发生变化时，而RIP是定期交换路由表的信息。它优点是更新过程收敛得快。

各路由器频繁交换链路状态信息，所以所有的路由器最终都能建立一个链路状态数据库（link-state database），这个数据库实际上就是全网的拓扑结构图，这个拓扑结构图在全网范围内是一致的（这称为链路状态数据库的同步），于是每个路由器都能使用链路状态数据库中的数据，构造出自己的路由表（使用Dijkstra的最短路径路由算法）。而RIP协议的每一个路由只知道所有网络的距离以及下一跳路由器，但却不知道全网的拓扑结构。

Ⅱ、划分区域

划分原因：为使OSPF能够用于规模更大的网络，它将一个自治系统再划分为若干个更小的范围，叫作区域。每个区域都有一个32位的区域标识符（点分十进制表示）。一个区域不要太大，在一个区域内的路由器最好不超过200个。

区域内部通信——利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治网络，这样大大减少了通信量。一个区域内的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑结构。

区域间如何通信？——OSPF使用层次结构的区域划分。上层的区域叫作主干区域（backhome area），主干区域的标识符规定为0.0.0.0，它是用来连通其他在下层的区域，从其他区域来的信息都由区域边界路由器进行概括，R3，R4，R7都是区域边界路由器。每一个区域至少有一个区域边界路由器。主干区域内的路由器叫作主干路由器，如R3，R4，R5，R6，R7。一个主干路由器可以同时是区域边界路由器。在主干路由器内还要有一个路由器专门和本自治系统外的其他自治系统交换路由信息。这样的路由器叫作自治系统边界路由器（如R6）。

区域划分优点？——使交换信息的种类增多了，但协议复杂了。每一个区域内部交换路由信息的通信量大大减小，这样使OSPF协议能够用于规模很大的自治系统中。

Ⅲ、OSPF直接用IP数据报传送（而不是UDP）

原因——构成的数据报很短，能减少路由信息的通信量。还不必将长的数据报分片传送，分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而真个数据报就必须重传。

版本：当前版本号是2。

类型：五种类型分组中的一种。

分组长度：包括OSPF首部在内的分组长度，以字节为单位。

路由器标识符：标志发送该分组的路由器的接口的IP地址。

区域标识符：分组属于的区域的标识符。

检验和：用来检测分组中的差错。

鉴别类型：目前只有两种，0（不用）和1（口令）。

鉴别：类型为0时就填入0，为1时就填入8个字符的口令。

OSPF的其他特点：

①灵活性：对不同的链路可根据IP分组的不同服务类型（TOS）而设置成不同的代价，它对于不同类型的业务可计算出不同的路由。这是RIP没有的。

②负载平衡：如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。在代价相同的多条路径上分配通信量是通信量工程中的简单形式。而RIP只能找到某个网络的一条路径。

③所有OSPF路由器之间交换的分组都具有鉴别的功能，因而保证了仅在可信赖的路由器之间交换链路状态信息。

④支持可变长度的子网划分和无分类的编址CIDR。

⑤由于网络中的链路状态可能经常发生变化，因此OSPF让每一个链路状态都带上一个32位的序号，序号越大状态就越新。

Ⅳ、OSPF的五种分组类型

类型一：问候（hello）分组。用来发现和维持邻站的可达性

类型二：数据库描述（database description）分组。向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。

类型三：链路状态请求（link state request）分组。向对方请求发送某些链路状态项目的详细信息。

类型四：链路状态更新（link state update）分组。用洪泛法对全网更新链路状态。这种分组复杂、核心。路由器用这种分组将其链路状态通知给邻站。共有五种不同的链路状态。

类型五：链路状态确认（link state acknowledgment）分组。对链路更新分组的确认。

问候分组的用处——OSPF规定每两个相邻路由器每隔10秒钟要交换一次问候分组，这样就能确知哪些邻站是可达的。只有可达才能将邻站的链路状态信息存入链路状态数据库。若有40秒未收到邻路由器发来的问候分组，则认为该邻站是不可达的，应立即修改链路状态数据库，并重新计算路由表。

其他四种分组都是用来进行链路状态数据库的同步。同步是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫作“完全邻接的”（fully adjacent）路由器。不是完全邻接的路由器表明它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。

其他四种分组用来进行链路状态数据库同步的原因？

①一个路由器开始工作时，它只能通过问候分组得知它有哪些相邻的路由器在工作，以及将数据发往相邻路由器所需的“代价”。如果所有路由器都把自己的本地链路状态信息对全网进行广播，那么各路由器只要将这些链路状态信息综合起来就可得出链路状态数据库。但这样开销太大。

②所以，OSPF让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。摘要信息主要就是指出有哪些路由器的链路状态信息已经写入了数据库。经过与相邻路由器交换数据库描述分组后，路由器就使用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的这种分组交换，全网同步的数据链路数据库就建立了。

在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就要使用链路状态更新分组，用洪泛法向全网更新链路状态。OSPF用的是可靠的洪泛法。如下图，小箭头表示更新分组，空心箭头表示确认分组。

 为确保链路状态数据库与全网的状态保持一致，OSPF还规定每隔一段时间，如30分钟，要刷新一次数据库中的链路状态。

由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF协议要比距离向量协议RIP好很多。它也没有“坏消息传播得慢”的问题。

若N个路由器连接在一个以太网上，则每个路由器要向其他（N—1）个路由器发送链路状态信息，因而共有（N—1）^2个链路状态要在这个以太网上传送。OSPF协议对这种多点接入的局域网采用了指定的路由器的方法，使广播的信息量大大减少。指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

4.外部网关协议BGP

Ⅰ、背景

BGP是不同AS的路由器之间交换路由信息的协议。那不同AS之间的路由选择为什么不用内部网关协议？

内部网关协议主要是设法使数据报在一个AS中尽可能有效地从源站传送到目的站。在一个AS内部也不需要考虑其他方面的策略。然而BGP使用的环境却不同。这是因为：

①因特网的规模太大，使得AS之间路由选择非常困难。

原因有两点，一点是连接在因特网主干上的路由器，必须对任何有效的IP地址都能在路由表中找到匹配目的的网络。而主干路由器中，一个路由器的项目数早已超过了5万个网络前缀。如果使用链路状态协议，则每一个路由器必须维持一个河大的链路状态数据库。对于这样大的主干网用Dijkstra算法计算最短路径时花费的时间也太长。

另一点是，AS各自运行自己选定的内部路由选择协议，并使用本AS指明的路径度量，因此，当一条路径通过几个不同AS时，要想对这样的路径计算出有意义的代价是不太可能的。比如，对某AS来说，代价为1000可能表示一条比较长的路由，但对另一AS代价为1000却不可能表示不可接受的坏路由。因此，对于AS之间的路由选择，要用“代价”作为度量来寻找最佳路由也是很不现实的。比较合理的做法是在AS之间交换“可达性”信息。例如，告诉相邻路由器：“到达目的网络N可经过ASx”。

②AS之间的路由选择必须考虑有关政策。

比如AS1要发数据报给AS2，本来最好是经过AS3，但是AS3不愿意让这些数据报经过本AS的网络。又比如，仅在到达某些地址时才经过ASx。

于是，边界网关协议BGP只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。BGP采用了路径向量（path  vector）路由选择协议，它与距离向量协议和链路状态选择协议都有很大区别。

Ⅱ、路径向量选择协议

在配置BGP时，每一个AS的管理员要选择至少一个路由器作为该AS的“BGP发言人”。一般说来，两个BGP发言人是通过一个共享网络连接在一起的，而BGP发言人往往就是BGP边界路由器，但也可以不是BGP边界路由器。

一个BGP发言人与其他AS的BGP发言人要交换路由信息，就要先建立TCP连接，然后在此连接上交换BGP报文以建立BGP会话（session），利用BGP会话交换路由信息，如增加了新的路由，或撤销过时的路由，以及报告出差错的情况等等。使用TCP连接能提供可靠的服务，也简化了路由选择协议。使用TCP连接交换路由信息的两个BGP发言人，彼此成为对方的邻站（neighbor）或对等站（peer）。每一个BGP发言人除了必须运行BGP协议外，还必须运行该AS所使用的内部网关协议，如OSPF或RIP。

BGP所交换的网络可达性的信息就是要到达某个网络（用网络前缀表示）所要经过的一系列AS。当BGP发言人互相交换了网络可达性的信息后，各BGP发言人就根据所采用的策略从收到的路由信息中找出到达各AS的较好路由。下图是上图AS1上的一个BGP发言人构造出的AS连通图，它是树形结构，不存在回路。

因特网的多级结构的网络拓扑决定了BGP路由选择协议的特点。看下图，自治系统AS2的BGP发言人通知主干网的BGP发言人：“要到达网络N1，N2，N3和N4，可经过AS2。”主干网在收到这个通知后，就发出通知：“要到达网络N1，N2，N3和N4可沿路径（AS1，AS2）。”同理，主干网还可以发出通知：“要到达网络N5，N6和N7可沿路径（AS1，AS3）。”

从上面的讨论可以看出，BGP协议交换路由信息的结点数量级是自治系统AS数的量级，这要比这些AS中的网络数少很多。要在许多AS之间寻找一条较好的路径，就是要寻找正确的BGP发言人（或边界路由器），而在每一个AS中BGP发言人（或边界路由器）的数目是很少的。这就使得AS之间的路由选择不致过分复杂。

BGP支持CIDR，因此BGP的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的AS序列。由于使用了路径向量的信息，就可以很容易地避免产生兜圈子的理由。如果一个BGP发言人收到了其他BGP发言人发来的路径通知，它就要检查一下本AS是否在此通知的路径中。如果在这条路径中，就不能采用这条路径（因为会兜圈子）。

在BGP刚刚运行时，BGP的邻站是交换整个的BGP路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销方面都有好处。

BGP—4的四种报文：OPEN（打开）报文，用来与相邻的另一个BGP发言人建立关系，使通信初始化。UPDATE（更新）报文，用来通告某一路由的信息，以及列出要撤销的多条路由。KEEPALIVE（保活报文），用来周期性地证实邻站的连通性。NOTIFICATION（通知报文），用来发送检测到的差错。

若两个邻站属于两个不同AS，而其中一个邻站打算和另一个邻站定期地交换路由信息，这就应当有一个商谈的过程（因为很可能对方路由器的负荷已很重因而不愿意再加重负担）。因此，一开始向邻站进行商谈时就必须发送OPEN报文。如果邻站接收这种邻站关系，就用KEEPALIVE报文响应。这样，两个BGP发言人的邻站关系就建立了。

一旦邻站关系建立了，就要继续维持这种关系。双方中的每一方都要确信对方是存在的，且一直在保持这种邻站关系。为此，这两个BGP发言人彼此要周期性地交换KEEPALIVE报文（一般每隔30秒）。KEEPALIVE报文只有19字节长（只用BGP报文的首部），因此不会造成网络上太大的开销。

UPDATE报文是BGP协议的核心内容。BGP发言人可以用UPDATE报文撤销它以前曾经通知过的路由，也可以宣布增加新的路由。撤销路由可以一次撤销许多条，但增加新路由时，每个更新报文只能增加一条。

BGP可以很容易解决距离向量路由选择算法中的“坏消息传播得慢”这一问题。当某个路由器或链路出故障时，由于BGP发言人可以从不止一个邻站获得路由信息，因此很容易选出新的路由。距离向量算法往往不能给出正确的选择，是因为这些算法不能指出哪些邻站到目的站的路由是独立的。

Ⅲ、BGP报文的格式

通用首部分：

标记字段——鉴别收到的BGP报文（假定将来会有人发明出合理的鉴别方案），当不使用鉴别时，标记字段要置为全1。

长度字段——指出包括通用首部在内的整个BGP报文以字节为单位的长度，最小值是19，最大值是4096。

类型字段——值为1到4，分别对应于上述四种BGP报文中的一种。

OPEN报文：

共6字段，即版本（1字节，现在的值是4）、本自治系统号（2字节，使用全球唯一的16为自治系统号）、保持时间（2字节，以秒计算的保持为邻站关系的时间）、BGP标识符（4字节，通常就是该路由器的IP地址）、可选参数长度（1字节）和可选参数。

UPDATE报文：

共有5个字段，即不可行路由长度（2字节，指明下一个字段的长度）、撤销的路由（列出所有要撤销的路由）、路径属性总长度（2字节，指明下一个字段的长度）、路径属性（定义在这个报文中增加的路径的属性）和网络层可达性信息NLRI（network layer reachability information）。最后这个字段定义发出此报文的网络，包括网络前缀的位数、IP地址前缀。

KEEPALIVE报文：

只有BGP的19字节长的通用首部

NOTIFICATION报文：

有3个字段，即差错代码（1字节）、差错子代码（1字节）和差错数据（给出有关差错的诊断信息）。

5.路由器的构成

Ⅰ、路由器的结构、查找转发表、转发分组

是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。

整个路由器结构可划分为两大部分：路由选择部分和分组转发部分。

路由选择部分：

也叫控制部分，核心构件是路由选择处理机，其任务是根据所选定的路由选择协议构造出路由表，同时经常或定期地和相邻路由器交换路由信息而不断地更新和维护路由表。（如何根据路由选择协议和更新路由表？）

分组转发部分：

由三部分组成：交换结构、一组输入端口和一组输出端口（端口指硬件接口）。

交换结构——switching fabric，又称交换组织，作用是根据转发表（forwarding table）对分组进行处理，将某个输入端口进入的分组从一个合适的输出端口转发出去。它本身是网络，但又包含在路由器中，所以叫“路由器中的网络”。

转发和路由选择区别——“转发”就是路由器根据转发表把收到的IP数据报从路由器合适的端口转发出去，只涉及到一个路由器。但“路由选择”则涉及到很多路由器，路由表则是许多路由器协同工作的结果。这些路由器按照复杂的路由算法，得出整个网络的拓扑结构变化情况，因而能够动态地改变所选择的路由，并由此构造出整个的路由表。路由表一般仅包含从目的网络到下一跳（用IP地址表示，后面写）的映射，而转发表是从路由表中得出的。转发表包含完成转发功能所必须的信息。这就是说，在转发表的每一行必须包含从要到达的目的网络到输出端口和某些MAC地址信息（如下一跳的以太网地址）的映射。将转发表和路由表用不同的数据结构实现会带来一些好处，这是因为在转发分组时，转发表的结构应当使查找过程最优化，但路由表则需要对网络拓扑变化的计算最优化。路由表总是用软件实现的，但转发表可以由特殊的硬件来实现。注意：在讨论路由选择原理时，往往不去区分转发表和路由表的区别，而可以笼统地都使用路由表这一名词。

输入输出端口——有三个方框，1、2、3分别代表物理层、数据链路层、网络层的处理模块。物理层进行比特币的接收。数据链路层则按照链路层协议接收传送分组的帧。在把帧的首部和尾部剥去后，分组就被送入网络层的处理模块。若接收到的分组是路由器之间交换路由信息的分组（如RIP或OSPF分组等），则把这种分组送交路由器的路由选择部分中的路由选择处理机。若收到的是数据分组，则按照分组首部中的目的地址查找转发表，根据得出的结果，分组就经过交换结构到达合适的输出端口。一个路由器的输入端口和输出端口就做在路由器的线路接口卡上。

输入端口中的查找和转发功能在路由器的交换功能中是最重要的。为了使交换功能分散化，往往把复制的转发表放在每一个输入端口中（如上图中的虚线箭头）。路由选择处理机负责对各转发表的副本进行更新。这些副本称为“影子副本”（shadow copy）。分散化交换可以避免在路由器中的某一点上出现瓶颈。

Ⅱ、查找转发表和转发分组实现中的困难

上述已介绍了查找转发表和转发分组的概念。问题就在于路由器必须以很高的速率转发分组，最理想的情况就是输入端口的处理速率能够跟上线路把分组传送到路由器的速率。这种速率称为线速（line speed或wire speed）。重点在于提高转发表的速率。

看下图，输出端口从交换结构接收分组，然后把它们发送到路由器外面的线路上。在网络层的处理模块中设有一个缓冲区，实际上它就是一个队列。当交换结构传送过来的分组速率超过输出链路的发送速率时，来不及发送的分组就必须暂时存放在这个队列中。数据链路层处理模块把分组加上链路层的首部和尾部，交给物理层后发送到外部线路。

若分组处理的速率赶不上分组进入队列的速率，则队列的存储空间最终必定减少到零，这就使后面再进入队列的分组由于没有存储空间而只能被丢弃。以前我们提到过的分组丢失就是发生在路由器中的输入或输出队列产生溢出的时候。当然，设备或线路出故障也可能使分组丢失。

Ⅲ、交换结构

作用：将分组从一个输入端口转移到某个合适的输出端口。

下面介绍三种常用的交换方法，它们都是将输入端口I1收到的分组转发到输出端口O2。

（a）通过存储器

最早使用的路由器就是利用普通的计算机，用计算机的CPU作为路由器的路由选择处理机。路由器的输入和输出端口的功能和传统的操作系统中的I/O设备一样。当路由器的某个输入端口收到一个分组时，就用中断方式通知路由选择处理机。然后分组就从输入端口复制到存储器中。路由器处理机从分组首部提取目的地址，查找路由表，再将分组复制到合适的输出端口的缓存中。若存储器的带宽（读或写）为每秒M个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速率）一定小于M/2。这是因为存储器对分组的读和写需要花费的时间是同一个数量级。

图中，分组通过存储器进行交换。与早期的路由器的区别就是，目的地址的查找和分组在存储器中的缓存都是在输入端口中进行的。

（b）通过总线

数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。但是，由于总线是共享的，因此在同一时间之能有一个分组在总线上传送。当分组到达输入端口时若发现总线忙（因为总线正在传送另一个分组），则被阻塞而不能通过交换结构，并在输入端口排队等待。因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。

（c）通过互连网络

它有2N条总线，可以使N个输入端口和N个输出端口相连接，这取决于相应的交叉结点是使水平总线和垂直总线连通还是断开。当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线连通，然后将该分组转发到这个输出端口。但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。

六、IP多播

1.IP多播的概念

图a是视频服务器用单播方式向90个主机传送同样的视频节目。为此，需要发送90个单播，即同一个视频分组要发送90个副本。路由器R1在转发分组时，需要把收到的分组复制成3个副本，分别向R2、R3、R4各转发1个副本。当分组到达目的局域网时，由于局域网具有硬件多播功能，因此不需要复制分组，在局域网上的多播组成员都能收到这个视频分组。

图b是视频服务器用多播方式向同一个多播组的90个成员传送节目。这时，视频服务器只需把视频分组当做多播数据报来发送，并且只需发送一次。主机很大时，能减轻网络中各种资源的消耗。在因特网范围的多播要靠路由器来实现，这些路由器必须增加一些能够识别多播数据报的软件。能够运行多播协议的路由器称为多播路由器（multicast router）。多播路由器当然也可以转发普通的单播IP数据报。

在因特网上进行多播就叫做IP多播。IP多播所传送的分组需要使用多播IP地址，而一个主机有唯一的IP地址。如果某个主机想接受某个特定多播组的分组，那么怎么才能使这个多播数据报传送到这个主机？

显然，这个多播数据报的目的地址一定不能写入这个主机的IP地址。这是因为在同一时间可能有成千上万个主机加入到同一个多播组。多播数据报不可能在其首部写入这样多的主机的IP地址。在多播数据报的目的地址写入的是多播组的标识符，然后设法让加入到这个多播组的主机的IP地址与多播组的标识符关联起来。

其实多播组的标识符就是IP地址中的D类地址，我们用每一个D类地址标识一个多播组。它是“尽最大努力交付”，不保证一定能够交付给多播组内的所有成员。因此，多播数据报和一般的IP数据报的区别就是它使用D类IP地址作为目的地址，并且首部中的协议字段值是2，表明使用IGMP协议。

显然，多播地址只能用于目的地址，而不能用于源地址。此外，对多播数据报不产生ICMP差错报文。因此，若在PING命令后面键入多播地址，将永远不会收到响应。

D类地址中有一些不能随意使用，因为有的地址已经被IANA指派为永久组地址了。

IP多播可分为两种，一种是只在本局域网上进行硬件多播，另一种则是在因特网的范围进行多播。前一种比较简单，但很重要，因为现在大部分主机都是通过局域网接入因特网的。在因特网上进行多播的最后阶段，还是要把多播数据报在局域网上用硬件多播交付给多播组的所有成员（看图b）。下面讨论硬件多播。

2.在局域网上进行硬件多播

因特网号码指派局IANA拥有的以太网地址块的高24位为00-00-5E，因此TCP/IP协议使用的以太网多播地址块的范围是从00-00-5E-00-00-00到00-00-5E-FF-FF-FF。在3.4.3讲过，以太网硬件地址字段中的第1字节的最低位为1时即为多播地址，这种多播地址数占IANA分配到的地址数的一半。因此IANA拥有的以太网多播地址的范围是从01-00-5E-00-00-00到01-00-5E-7F-FF-FF。不难看出，在每一个地址中，只有23位可用作多播。这只能和D类IP地址中的23位有一一对应的关系。D类IP地址可供分配的有28位，可见在这28位中的前5位不能用来构成以太网硬件地址。由于多播IP地址与以太网硬件地址的映射关系不是唯一的，因此收到多播数据报的主机，还要在IP层利用软件进行过滤，把不是本主机要接收的数据报丢弃。

下面讨论IP多播所需要的协议。

3.网际组管理协议IGMP和多播路由选择协议

Ⅰ、IP多播需要两种协议

看下图，标有IP地址的四个主机都参加了一个多播组，其组地址是226.15.37.123。显然，多播数据报应当传送到路由器R1，R2，R3，而不应当传送到R4，因为与R4连接的局域网上现在没有这个多播组的成员。但这些路由器又怎样知道多播组的成员信息呢？这需要网际组管理协议IGMP（internet group management protocol）。

IGMP并非在因特网范围内对所有多播组成员进行管理的协议，它不知道IP多播组包含的成员数，也不知道这些成员都分布在哪些网络上。它是让连接在本地局域网上的多播路由器知道本局域网上是否有主机（严格讲，是主机上的某个进程）参加或退出了某个多播组。

显然，仅有IGMP协议是不能完成多播任务的，连接在局域网上的多播路由器还必须和因特网上的其他多播路由器协同工作，以便把多播数据报用最小代价传送给所有的组成员。这就需要使用多播路由选择协议。它比单播路由选择协议复杂得多。

举例：看上图，多播组①的成员有主机A，B，C，多播组②的成员有主机D，E，F。这些主机分布在三个网络N1、N2、N3上。

路由器R不应当向网络N3转发多播组①的分组，因为网络N3上没有多播组①的成员。但是每一个主机可以随时加入或离开一个分组。例如，主机G现在加入了多播组①。从这时起，路由器R就必须也向网络N3转发多播组①的分组。这就是说，多播转发必须动态地适应多播组成员的变化（这时网络拓扑并未发生变化）。请注意，单播路由选择通常是在网络拓扑发生变化时才需要更新路由。

再看一种情况。主机E和F都是多播组②的成员。当E向F发送多播数据报时，路由器R把这个多播数据报转发到网络N3。但当F向E发送多播数据报时，路由器R则把多播数据报转发到网络N2。如果路由器R收到来自主机A的多播数据报（A不是多播组②的成员，但也可向多播组发送多播数据报），那么路由器R就应当把多播数据报转发到N2和N3。由此可见，多播路由器在转发多播数据报时，不能仅仅根据多播数据报中的目的地址，而是要考虑这个多播数据报从什么地方来和要到什么地方去。

还有一种情况。主机G没有参加任何多播组，但G却可向任何多播组发送多播数据报。例如，G可向多播组①和②发送多播数据报。主机G所在的局域网上可以没有任何多播组的成员。显然，多播数据报所经过的许多网络，也不一定非要有多播组成员。总之，多播数据报可以由没有加入多播组的主机发出，也可以通过没有组成员接入的网络。

所以，IP多播复杂了。

Ⅱ、网际组管理协议IGMP

和ICMP相比，IGMP使用IP数据报传递其报文（即IGMP报文加上IP首部构成了IO数据报），但它也向IP提供服务。因此，我们不把IGMP看成是一个单独的协议，而是属于整个网际协议IP的一个组成部分。

从概念上讲，IGMP的工作可分为两个阶段：

第一阶段：当某个主机加入到新的多播组时，该主机应向多播组的多播地址发送一个IGMP报文，声明自己要成为改组的成员。本地的多播路由器收到IGMP报文后，还要利用多播路由器选择协议把这种组成员关系转发给因特网上的其他多播路由器。

第二阶段：组成员关系是动态的。本地多播路由器要周期性地探寻本地局域网上的主机，以便知道这些主机是否还继续是组的成员。只要有一个主机对某个组响应，那么多播路由器就认为这个组是活跃的。但一个组在经过几次的探寻后仍然没有一个主机响应，多播路由器就认为本网络上的主机已经都离开了这个组，因此也就不再把这个组的成员关系转发给其他的多播路由器。

IGMP设计得很仔细，避免了多播控制信息给网络增加大量的开销。采用的措施有如下：

（1）在主机和多播路由器之间的所有通信都是使用IP多播。只要有可能，携带IGMP报文的数据报都用硬件多播来传送。因此在支持硬件多播的网络上，没有参加IP多播的主机不会收到IGMP报文。

（2）多播路由器在探询组成员关系时，只需要对所有的组发送一个请求信息的询问报文，而不需要对每一个组发送一个询问报文（虽然也允许对一个特定组发送询问报文）。默认的询问速率是每125秒发送一次（通信量并不太大）。

（3）当同一个网络上连接有几个多播路由器时，它们能够迅速和有效地选择其中的一个来探询主机的成员关系。因此，网络上多个多播路由器并不会引起IGMP通信量的增大。

（4）在IGMP的询问报文中有一个数值N，它指明一个最长响应时间（默认值为10秒）。当收到询问时，主机在0到N之间随机选择发送响应所需经过的时延。因此，若一个主机同时参加了几个多播组，则主机对每一个多播组选择不同的随机数。对应于最小时延的响应最先发送。

（5）同一个组内的每一个主机都要监听响应，只要有本组的其他主机先发送了响应，自己就可以不再发送响应了。这样就抑制了不必要的通信量。

多播路由器并不需要保留组成员关系的准确记录，因为向局域网上的组成员转发数据报使用硬件多播。多播路由器只需知道网络上是否还有一个主机是本组成员即可。对询问报文实际上每一个组只有一个主机发送响应。

如果一个主机上有多个进程都加入了某个多播组，那么这个主机对发送给这个多播组的每个多播数据报只接收一个副本，然后给主机中的每一个进程发送一个本地复制的副本。

强调指出，多播数据报的发送者和接受者都不知道（也无法找出）一个多播组的成员有多少，以及这些成员是哪些主机。因特网中的路由器和主机都不知道那个应用进程将要向哪个多播器发送多播数据报，因为任何应用进程都可以在任何时候向任何一个多播组发送多播数据报，而这个应用进程并不需要加入这个多播组。

Ⅲ、多播路由选择协议

在多播过程中一个多播组中的成员是动态变化的，例如在收听网上某个广播节目时，随时会有主机加入或离开这个多播组。多播路由选择实际上就是要找出以源主机为根节点的多播转发树。在多播转发树上，每一个多播路由器向树的叶节点方向转发收到的多播数据报，但在多播转发树上的路由器不会收到重复的多播数据报（即多播数据报不应在互联网中兜圈子）。不难看出，对不同的多播组对应于不同的多播转发树。同一个多播组，对不同的源点也会有不同的转发树。

多播路由选择协议在转发多播数据报时采用了以下三种办法：

（1）洪泛与剪除

适合于较小的多播组，而所有的组成员接入的局域网也是相邻接的。一开始，路由器转发多播数据报使用洪泛的方法。为了避免兜圈子，采用了反向路径广播RPB（reverse path broadcasting）的策略。它要点是：每一个路由器在收到一个多播数据报时，先检查数据报是否从源点经最短路径传送过来的。进行这种检查很容易，只要从本路由器寻找到源点的最短路径上（之所以叫做反向路径，因为在计算最短路径时是把源点当作终点）的第一个路由器是否就是刚才把多播数据报传送过来的路由器。若是，就向所有其他方向转发刚才收到的多播数据报（但进入的方向除外），否则就丢弃而不转发。如果本路由器又好几个相邻路由器都处在到源点的最短路径上（也就是说，存在几条同样长度的最短路径），那么只能选择一条最短路径，选择的准则就是看这几条最短路径中的相邻路由器谁的IP地址最小。

（2）隧道技术

适用于多播组的位置在地理上很分散的情况。R1对多播数据报进行再次封装，即再加上普通数据报首部，使之成为向单一目的站发送的单播数据报，然后通过“隧道”从R1发送到R2。这种使用隧道技术传送数据报又叫做IP中的IP（IP-in-IP）。

（3）基于核心的发现技术

对于多播组的大小在较大范围内变化时都适合。它是对每一个多播组G指定一个核心路由器，给出它的IP单播地址。核心路由器按照前面讲过的方法创建出对应于多播组G的转发树。如果有一个路由器R1向这个核心路由器发送数据报，那么它在途中经过的每一个路由器都要检查其内容。当数据报到达参加了多播组G的路由器R2时，R2就处理这个数据报。如果R1发出的是一个多播数据报，其目的地址是G的组地址，R2就向多播组G的成员转发这个多播数据报。如果R1发出的数据报是一个请求加入多播组G的数据报，R2就把这个信息加到它的路由中，并用隧道技术向R1转发每一个多播数据报的一个副本。这样，参加到多播组G的路由器就从核心向外增多了，扩大了多播转发树的覆盖范围。

多播路由选择协议：

（1）距离向量多播路由选择协议DVMRP（distance vector multicast routing protocol）

（2）基于核心的转发树CBT（core basted tree）

使用核心路由器作为转发树的根节点。一个大的自治系统AS可划分为几个区域，每一个区域选择一个核心路由器。

（3）开放最短通路优先的多播扩展MOSPF（multicast extensions to OSPF）

是OSPF的扩充。它使用多播链路状态路由选择创建出基于源点的多播转发树。

（4）协议无关多播-稀疏方式PIM-SM（protocol independent multicast-space mode）

使用和CBT同样的方法构成多播转发树，采用“协议无关”是强调：虽然在建立多播转发树时是使用单播数据报来和远程路由器来联系，但这并不要求使用特定的单播路由选择协议。这个协议适用于组成员的分布非常分散的情况。

（5）协议无关多播-密集方式PIM-DM（protocol independent multicast-dense mode）

适用于组成员的分布非常集中的情况，例如组成员都在一个机构内。不使用核心路由器，而使用洪泛方式转发数据报。