你好,欢迎访问达普芯片交易网!|  电话:010-82614113

链路状态路由算法

发布时间:2008-12-01 09:41:51阅读:2791

  直到1979年,ARPANET都用的是距离矢量路由选择,之后变为由链路状态路由选择所代替。两个主要问题导致了 距离矢量路由选择算法的消亡。第一,因为延迟度量是队列长度,在选择路由时,并没有将线路的带宽考虑进去 。开始,所有的线路都是56Kb/s,因此线路带宽并不是待考虑的因素。但当有些线路升级为23OKb/s,乃至1. 544Mb/s后,不考虑带宽因素就很成问题了。当然,也可以在延时变量中加人线路带宽因子。但第二个问题依然存 在,也就是算法往往耗去过多时间用于记录信息,即使使用了像水平分离这样的技术。因此,它被一种全新的算 法,现在叫作链路状态路由选择(link state routmg)算法所替代。现在各种各样的链路状态路由选择算法得到 了广泛的应用。

  隐藏在链路状态路由选择之后的思想十分简单,可以分5部分加以描述。每个路由器必须完成以下的工作:

  发现它的邻居节点,并知道其网络地址;

  测量到它各邻居节点的延迟或开销;

  组装一个分组以告之它刚知道的所有信息;

  将这个分组发送给其他路由器;

  计算到每个其他路由器的最短路径。

  事实上,完整的拓扑结构和所有的延时都已被测量,并且被测量到各个路由器中。随后,各个路由器都可以用 Dijkstra算法来找出最短路径。下面,将更详尽地讨论上述五个步骤。

  (1)发现邻居节点

  当一个路由器启动以后,它的第一个任务就是要知道谁是它的邻居,这是通过向每条点到点线路发送特殊的 HELLO分组来实现的。在另一端的路由器应发送回来一个应答来说明它是谁,这个名字必须是唯一的。

  (2)测量线路开销

  链路状态路由选择需要每个路由器知道它到邻居节点的延迟,至少得有个可信的估计值。取得延迟时间的最直接 方式就是发送一个要求对方立即响应的特殊的ECHO分组。通过测量一个来回的时间再除以2,发送方路由器就可以 得到一个可靠的延迟估计值。想要更精确些,可以重复这一过程多次,再取平均值。

  其中一个有趣的话题是,在测量延迟时是否将载荷考虑进去。如果要考虑载荷因素,往返时间应该从ECHO分组 进人队列时开始计时;如果忽略载荷,计时器就得从ECHO分组排列队列第一位时开始计时。

  两种方法都会有争议,在延时测量中引人流量因素意味着当一个路由器在两条相同带宽的线路间进行选择时, 如果一条线路总是有很重的负载,而另一条线路总是负载较轻,那么后者将被认为是一条更短的路径,这种选样 能导致良好的`跬能。

  (3)创建链路状态分组

  一旦用于交换的信息收集起来,下一步就是构造一个包含所有数据的分组。该分组以发送者的标志符开头,紧 跟着是顺序号和年龄,和一个邻居节点列表,对于每个邻居节点,都给出了它们的延迟。

  创建链接状态分组很容易,难的是决定何时创建分组。一种可能性是定期创建,即每隔一定时间间隔就创建一 次;另一种可能性是当出现重大事件时(像线路或邻居节点的增删,或它的特征值明显改变时)再创建。

  (4)发布链路状态分组

  本算法中最具技巧性的部分就是如何可靠地发行链路状态分组。当分组被发布和安装后,首先得到分组的路由 器将改变其路由选择。同时,别的路由器可能还在使用不同版本的拓扑结构,这样导致了不一致性、死循环、不 可达机器和其他问题。

  首先描述基本发布算法,随后针对它进行一些调整。基本思想是利用扩散来发布链接状态分组。为了控制扩散 ,每个分组包含一个顺序号。该顺序号在每次发送新分组时加1。路由器记下它所见过的所有信息对(源路由器, 顺序号)。当一个新的链路状态分组到达时,它先查看一下该分组是否已收到过。如果是新的,把它再向除了进 人线路之外的所有线路发布;如果是重复的,则丢弃它。如果一个分组的顺序号比目前为止已到达的最大的顺序 号还小,贝刂被认为已过时而拒绝。

  这个算法有一点问题,但这些问题是可以控制的。首先,如果顺序号循环使用,就会发生冲突。解决办法是使 用00JL位的顺序号;如果每秒钟发送一个链路状态分组,就得花137年才能使计数循环回来,所以避免了发生冲突 的可能性。

  其次,如果一个路由器崩溃了,它将丢失其顺序号。如果它再从0开始,那么后面的分组可能会被当作重复分组 而被拒绝。

  最后,如果顺序号传送后出现错误,比如发送方发送的序列号是4,但是由于产生了一位错误,接收方看到的序 列号是65540,那么序列号从5到65540都会被当成过时分组而遭拒绝,因为当前顺序号被认为是65540。

  解决这些问题的办法是,在每个分组的顺序号之后再加上年龄字段,每秒钟将年龄递减1,当年龄变成零时,来自于那个路由器的信息就被丢弃掉。比如说,通常每lOmin进入一个新分组,因 此当路由器关掉后,路由器的信息便会过时(或者6个连续的分组部被丢失,不太可能发生)。在初始化扩散过程 中,年龄字段也一样递减,以保证没有任何分组会丢失并无限长地存活下去(一个年龄为零的分组将被丢弃)。

  对该算法的一些细化会使之更健壮。当一个链路状态分组扩散到一个路由器时,它并不立即排队等待传送。相 反,它先被送到一个保持区中等待一段时间。如果已有来自同一路由器的其他链路状态分组先行到达,则比较一 下它们的顺序号。如果相等,重复分组就被丢弃。如果不相等,老的分组就被丢弃。为了防止路由器至路由器线 路出问题,所有的链路状态分组都要应答。一旦线路空闲,保持区就会循环扫描以选择发送一个分组或应答。

  (5)计算新路由

  一旦一个路由器积累了一整套的链路状态分组,它便可以重组整个子网结构,因为每条线路出现过了。实际上 ,每条链路被表示了两次,两个方向各出现一次,两个值可以取平均,也可以分开用。

  现在Dijkstra的算法就可以在内部运行,以确定到所有可能目的地的最短路径。此算法的结果可以安装在路由 选择表中,并且通常通过操作恢复。

  对于一个有″个路由器,每个路由器有乃个邻居节点的子网来说,所需的存储输入数据的空间为kn的倍数。对 于大的子网,这可能还是个问题。而且,计算时间也可能成为一个问题,然而,在很多实际应用中,链路状态路 由选择算法工作得很好。

  但是,硬件或软件问题也能破坏该算法(对于其他算法也一样)。例如,如果一个路由器声明它拥有一条其实 并不存在的线路,或忘记了一条确实存在的线路,子网图将是不正确的。如果路由器不能正常地向前传递分组, 或在向前传递时将分组破坏了,也会出现麻烦。最后,如果它的存储空间溢出或路由计算出错,也会导致错误。 当子网逐渐增加到成百上千或上万个节点时,某些路由器崩溃的可能性就变得不可忽视了。解决这个问题的技巧 是,在不可避免地发生连续事故后,尽量将破坏限制在最小的范围之内。

  链路状态路由选择在实际网络中得到广泛的应用,所以有必要谈谈运用此算法的协议。OSPF协议被越来越多地 应用于因特网,它使用的就是链路状态算法。另一个重要的链路状态协议是中间系统至中间系统IS-IS (intermediate system Intermediate system),它是为DEGnet所设计的,后为ISO采纳,用于它的无连接网络 层协议CLNP。因此,它还被修改以适应其他协议,最著名的如IP协议。IS-IS被用于多种因特网骨干网中(包括 早先的NSFNET骨干网)和一些数字蜂窝系统,像CDPD。NovellNetWare使用一种IS-IS小的变型协议(NLSP)来为 IPX分组选择路由。

  基本上,IS-IS分发了一个路由器拓扑结构图,通过该图能计算出最短路径。每个路由器都在其链路状态分组中宣布它能直接到达的网络层地址。这个地址可以是IP,IPX,AppleTalk或其他任何地址。IS-IS甚至可以同时支持多种网络层协议。

  很多IS-IS设计的革新都被OSPF(OSPF比IS-IS晚几年设计)所采纳,它包括一种扩散链接状态更新信息的自稳定措施,支持LAN的命名路由器的概念,以及能计算和支持路径分裂及多种度量单位。最终导致IS-]S与OSPF之间只有很小的差别。最大的差别是,IS-IS能同时携带有关多个网络层协议的信息,而OSPF没有这一特征,在大型的多协议环境中,这一优势显得尤为重要。

在线人工客服

点击这里给我发消息

点击这里给我发消息

点击这里给我发消息

010-82614113

客服在线时间周一至周五
9:00-17:30