网络连通图与路由选择

路由器的另一个主要功能是:计算应当把数据包发向哪个网络结点(路由器或最终的接收者)。自然地,转发的结点必须处于从本结点到最终结点的通路上。然后,把数据(分片或直接)转到下一个结点上。

对此,每个路由器里要存一张路由表,给出一个算法决定下一个(与最终目的地联通的)结点的地址,称为下一跳地址(next-hop address)。

当可以有多个地址供选择时,路由器就存在一个策略选择,例如,选两个结点间传输速率最快那个结点,当然,也可以定义一个缺省的结点或路由器,一个路由是多个结点组成的串接序列,表达从当前结点能到达到最终结点经过的结点。

以图5-2的Node B(路由器)为例,在接收到“Red”这个数据包时,由于该数据包的最终目的地是Host2,而可前传的下一个地址是Node C 或Node E。这个例子中选择了Node C,而没选Node E。

路由的基本算法如下:

给定一个目的地地址D,下一个可以转发的结点地址N,

如果,N 直接与D 的地址匹配,

那么,将数据直接给网络链路上的D;

否则如果,路由表中包含一个带N 的路由,

那么,将数据包送给路由表中所列的下一个地址N;

否则如果,有一个默认的路由结点,(www.xing528.com)

那么,将数据包送给缺省的路由结点;

否则,向前给数据包的源发出者发送一个错误信息,任务失败。

当没有路由可用时,向前发送一个错误信息给数据包的源发出者,通知它不能转发该数据包,从而避免不必要的重新传输。

上面算法的关键是要有一个路由表,这张路由表存放各个结点之间的连通情况,构成了一个网络连通图(参见3.6.6节),路由器的路由选择就成为一个图的连通路径算法问题。由于通信线路可能会出现故障,路由表可能不会完全反映真实的情况。由此,导致路由的选择有几种策略:静态路由、动态路由、缺省路由。

(1)静态路由:将路由器的路由选择预先设定好,不会随网络拓扑结构或通信的拥堵情况等的改变而自动改变。如果路由有多个可选结点,选择其中默认的下一跳结点。这会导致网络拓扑结构变化时(例如,有些中间结点坏了或出现拥堵),传输的效率就会下降。

(2)动态路由:在每台路由器上运行一个路由协议。这个路由协议会根据路由器上的接口的配置,以及所连接的链路的状态,生成路由表中的路由项。

动态路由协议通过路由信息的交换生成并维护转发所需的路由表,当网络拓扑结构改变时动态路由协议可以自动更新路由表,并负责决定数据传输最佳路径。例如,在因特网中的动态路由协议RIP、OSPF等。RIP称为路由信息协议(Routing Information Protocol)是基于距离矢量算法的路由协议,利用跳数来作为成本计量标准。OSP是开放式最短路径优先(Open Shortest Path First)的缩写,基于迪克斯加(Dijkstra)算法计算出最短路径的协议。

(3)缺省路由:缺省路由是一个路由表条目,用来指明一些在下一跳没有明确地列于路由表中的数据单元应如何转发。对于在路由表中找不到明确路由条目的所有的数据包都将按照缺省路由指定的接口和下一跳地址进行转发。

不同的路由协议可能会发现不同的路径,并非这些路径都是最优的。为了找到最优路径,各种路由协议(包括静态路由)被赋予了一个管理距离。这样,当存在多个路由信息源时,具有较小管理距离的路由协议所发现的路由将成为最优路由,并被加入路由表中。

注意:学好离散数学、图论、数据结构与算法等课程,可以帮助你理解路由协议。你也可以创立自己的路由协议。