链路状态协议——排序、老化

时间:2024-03-14 18:09:59

洪泛过程是链路状态协议中最复杂的部分,而洪泛中最重要的过程就是排序和老化。
***:是用来标记LSA的,其作用有两个。
作用1:防止相同的LSA重复接收,避免无效洪泛带来的资源浪费。
路由器洪泛LSA时,每个拷贝中的***都是相同的,这个***和LSA的其它部分一起被保存在LSDB中。当有路由器接收到在本地LSDB中的已存在的LSA且***相同时,路由器将丢弃这些信息。如果信息相同但***更大时,路由器会将LSA的信息和***重新保存并洪泛该***更大的LSA。按照这种方式,当所有路由器都接收到LSA的最新拷贝时,洪泛扩散停止。
作用2:比较新旧LSA,防止过时LSA影响路由器的判断。
当一链路在短时间内状态发生多种变化,路由器因此会发出多个LSA描述该链路状态,其它路由器可能会同时收到多个不同状态的LSA,此时,路由器就可以通过***的大小来判断LSA的新旧,继而了解链路的状态。
***是携带在LSA中固定字段内的一个数字编码。所以,随着LSA数量的增加这个空间会被用完。为了能更好的发挥协议的作用,我们设计的以下的序列空间模式。
1.线性序列空间
这个设计的思想很简单,针对协议的特性设计一个它永远也用不完的字段。但这只是“质点”般的存在。因为有以下两个问题:
1)“我”命由空间,不由“我”
如果协议一直都是在正常的情况下运行,那么我们就可以很容易设计出一个路由器寿命内的***字段。但是,总会有些链路出现故障,大量使用***,这样就算有再多的***也会被用完。线性序列空间中如果一个路由选择协议用完了所有***,那么它在重新使用最低***之前必须停止,并等待它所发出的LSA在所有数据库中都不再使用。
2)重启即是新生
在路由器启动期间会遇到更为常见的困难。如果路由器A是重新启动的,它将无法记得上次使用的***,必须重新使用1.但是路由器A的邻居却依然在数据库中保留着路由器A上次的***,按照越小即越旧的思想,路由器A重启后发送的LSA会邻居被忽略。而且,路由选择进程必须一直等到网络上所有陈旧(前世)的LSA都消失才能运行。
为了使线性序列空间的使用价值更高。在洪泛扩散行为中添加新的规则:如果一台重启路由器向邻居发送LSA的***比邻居保存的***更老,那么邻居会发回自己保存的LSA。重启路由器在接收到LSA后将知道重启前自己使用的***并做出相应调整。
然而需要小心的是,最近使用过的***不能接近上限。否则,重新启动后的路由器将不得不再次重启。所以必须设定规则限制路由器“跳跃”地使用***。例如,规定一次***地增加不能超过整个序列空间的1/2。
IS-IS使用的就是线性序列空间。

循环序列空间
这是解决***字段有限的另一中方法——***循环使用。32位的字段内紧跟在4294967295后面的是0.然而在这里的故障也会让人左右为难,重启的路由器可能会遇到同线程***一样的问题。
循环序列编号建立了一个不合逻辑的奇特的位。如果x是1— 4294967295之间的任何一个数。那么0<X<0。在运行正常的网络中通过声明两条规则可以维持这种条件。其中,声明的规则用来确定什么时候一个***大于另一个***。
假定序列空间为n,有两个***a、b.如果满足下面任何一个条件,则认为a更新。
链路状态协议——排序、老化
简单起见,我们使用一个6位的字段长度为例。
链路状态协议——排序、老化
链路状态协议——排序、老化
假定的两个***为45、15.
45>15 且 45-15=30<32
所以45 更新
假定的两个***为16、60
16<60且60-16=44>32
所以16更新
总结一下:大减小的值若大于序列空间的一半,则小新;若小于序列空间的一半,则大新。图中对应的是小弧度按逆时针方向的起点和终点,终点新。
可以看出规则强制***循环使用。
但是在不正常的网络中呢?设想在一个网络中使用6位的***空间。现有一台路由器决定离线,当它离线时突然发送了3个相同且***为44的LSA。不幸的是,一个邻居发生了故障——丢掉了几位数据,将第二个和第三个LSA的***的几位丢失(第一个LSA为101100(44),第二个LSA为101000(40),第三个LSA为001000(8))。随即该邻居路由器向外泛洪扩散了这三个LSA。结果造成3个LSA***各不相同。
应用循环规则:44比40跟新,40比8更新,8比44跟新。
这样3个LSA都会持续的更新下去。数据库也不断的被最新的LSA更新。直到数据库缓冲被塞满。CPU超载为止,最终整个网络崩溃。
现代网络的先躯ARPANET早期曾使用过带有6为***空间的链路状态协议。在1980年10月27日,两台路由器发生了上面所说故障。从而造成ARPANET停顿。

棒棒糖形序列空间
棒棒糖形序列空间是线性序列空间和循环序列空间的综合。它有一个线性组件和一个环形组件。循环序列空间的缺点是没有一个数小于其它所有数。线性序列空间的缺点是不能循环使用***,即***有限。
当路由器A重启时,它从小于其他所有数的a开始。邻居识别出这个数,这时邻居数据中还保留着A重启前使用***为b的LSA。那么邻居会发送b***的LSA给路由器A,路由器A会跳至该***。
在知道自己重启前的***之前,路由器A发送了不止一个LSA,因此,在邻居通知路由器A重启前使用的***或重启前使用的***从所有的数据库中消失之前。路由器A必须准备充足的重启数,以便路由器A不会用光所有的***。
这些线性重启***形成了棒棒糖的棒。在这些***用完或邻居提供了使路由器A跳转的***后,路由器A进入循环部分即棒棒糖的糖体。
在设计棒棒糖序列空间时使用了有符号数,即-k<0<k,从-k到0的负数是棒部分,从0到k的正数是糖。
***的规则如下:假设有两个***a和b.
当且仅当:
链路状态协议——排序、老化
就认为b更新.
链路状态协议——排序、老化
链路状态协议——排序、老化
假设路由器要重新启动,最后一个被发送的LSA的***位0X00005DE3。路由器重启后,当它与邻居同步数据库时,路由器发送***为0X80000001的LSA,邻居检测数据库发现该路由器重启前的LSA的***为0X00005DE3,这时邻居路由器会将这个LSA发送给重启路由器告诉重启路由器“这是你离开时的位置”。重启路由会记录这个***为正数的LSA。如果还要发送新LSA,它就会使用0X00005DE3的***。
棒棒糖形序列空间是应用与OSPF最初版本OSPFV1中的。虽然使用了有符号数是对线性序列空间进行了改进,但循环部分还是会和纯粹的循环序列空间一样容易产生歧义。OSPFV1一直处于实验环境。当前使用的OSPFV2采用了线性和棒棒糖形的最好特性。OSPFV2像棒棒糖形序列空间一样使用从0X80000001开始的有符号数线性空间,但在循环部分保持了线性直到到达最大数0X7FFFFFFF为止。此时,在重启前OSPF进程必须从所有的数据库中删除LSA。

老化
LSA格式中将要包含一个用于通告年龄的字段。当LSA被创建时,路由器将该字段置为0.随着数据包的扩散,每台路由器都会增加LSA中的年龄。(IS-IS中是设置了最大值,然后递减)
老化过程为洪泛扩散过程增加了另一层可靠性,该协议为网络定义了一个最大的年龄差距(MaxAgeDiff)值。路由器可能会收到LSA的多个拷贝,其中***相同,年龄不同。若年龄差距小于MaxAgeDiff ,认为是正常的网络延迟造成的年龄差异,数据库会将原有LSA继续保存,新收到的LSA不被扩散。若年龄差距大于MaxAgeDiff,认为网络出现异常,因为LSA的***没有增加。在这种情况下,较新的LSA被记录下来。并将数据扩散出去。典型的MaxAgeDiff时间为15min.
保存在链路状态数据库中的LSA的年龄会不断增加,如链路状态记录的年龄增加到某个最大年龄值(MaxAge,由特定的路由协议定义),那么一个带有MaxAge值的LSA被洪泛扩散到所有邻居。邻居随即从数据库中删除相关记录。
当LSA的年龄到达MaxAge时,将被从所有的数据库中删除,这需要有一种机制来定期的确认LSA并且在到在到达最大年龄之前将它的计时器复位。链路状态刷新计时器(LARefesh Time)就是做此用途。一旦刷新计时器超时,路由器将向所有的邻居洪泛扩散新的LSA。收到的邻居会把有关路由器记录的年龄设置为新接收到的年龄。OSPF定义的MaxAge为1小时,LSRefresh Time 为30min。