Video在线视频

距离矢量路由算法

因为站得不高

看得不远

只相信它的邻居

导致无穷计数、路由环等问题

链路状态路由选择

力图站得足够高看得足够远

来避免距离矢量的问题

但是要站得多高看得多远呢

链路状态路由是Link State Routing的译文

下面我们都把它简称为LS

LS的主要思想可以用五个词来描述

发现

设置、构造、发送和计算

先来看发现

要发现什么呢

发现它的邻居

当一个路由器启动的时候

在每个点到点的线路

发送一个特别的Hello数据包

收到Hello分组的路由器

会回发一个应答

在应答中包含了它自己的名字

全球唯一的一个名字

当这样的Hello报文一来一回的时候

一台路由器就了解到了它的邻居

有的时候呢还不止一个邻居

有多个邻居

第二个步骤呢叫做设置

设置链路成本

到邻居的链路开销、代价

可以自动配置

会由运营商配置

一种常用的开销选择就是跟链路带宽成反比

有的时候呢也可以采用链路延迟作为开销

为了决定线路的延迟开销

路由器可以发送一个特别的回声分组ECHO

另一端立刻回送一个应答

通过应答包的到来就可以测量往返时间 RTT

发送路由器可以获得一个合理的延迟估计值

为了得到更好的延迟结果

可以多次测量取平均值

第三步 构造

构造链路状态分组

LSP

叫做Link State Packet

有的时候也叫Link State Advertisement

LSA

LSP或者LSA构造之后

被发送给其它的路由器

在这个分组中包含了上述发现的邻居

和到邻居的链路开销

也就是说这台路由器侦查到了

它周边的状况、地图信息

它把这些信息呢构造成这个分组

所以在这个分组里面包括了发送方的标识

就是谁发出去的这个小地图

第二个呢就是序列号

第三个是age

第四个是它有哪些邻居 邻居的列表

第五个 到邻居的成本

应该什么时候构造这个LSP或者LSA的分组呢

可以选择周期性地来构造和发送

或者在有特别事件发生的时候再构造

比如某条线路Down掉了或者某个邻居Down掉了

或者有一个接口上来了

这些都是一个事件

这个事件可以触发它

主动地把这种变化够造成分组

通告给其它的路由器知道

这实际上就是我们所说的触发更新

看一个LSA的例子

在图中路由器C有三个邻居

它的LSA是这样的

首先第一部分就是C自己

也就是说是谁发出了这个LSA

第二个呢就是Sequence Number

它可能发出非常多的LSA

那么这个Sequence Number区分出来了它发出去的是哪一个

第三部分呢叫作age

这个age的作用呢 我们稍后再讲

接下来第四部分第五部分

就是它的邻居列表

和到这些邻居它的代价列表

第四个单词叫发布

发布的是LSA或者LSP

这一步非常重要

关系到LSP是否能够

分发到所有的路由器

如果分发不完整

将导致路由器构造的拓扑图不完整

即对网络的认识不完整

分发的基本的算法是这样的

第一步 每个分组都包含一个序列号

序列号随着新分组的产生而递增

第二步 路由器记录下它看见的所有LSP

的源路由器和序列号对

第三

当一个新的分组到达的时候

路由器根据它的记录

做出一个判断

如果这个分组是新的

也就是说序列号不在表中

就被从除了来的线路外的所有其它线路转发出去

实际上就是做广播

泛洪

如果发现到达的这个分组是一个重复分组

就是序列号相等

那么这个分组就会被丢弃

如果到达的分组的序列号

比对应的源路由器发出去的

曾经到过此地的分组的最大序列号还小

则该分组被当做一个过时的信息而被拒绝

这个基本的算法可以保证

我们的分组LSA、LSP能够送达到所有的路由器

但是呢可能会遭遇到两个问题

第一 序列号回转问题

它会引起新老分组识别混淆

比如说用三个比特来表示序列号

那么序列号就可以从000、001一直变化到最大111

下一个分组呢

又是从000开始了

这就是序列号回转问题

那么这个问题会导致

我们的路由器无法甄别

000跟7——111相比

到底是哪个是新的哪个是旧的

解决的办法就是

使用32比特来表示序列号

那么32位表示的序列号是一个非常大的一个值

即使每秒产生一个分组

也需要137年才会发生号码回转

而一台路由器它基本上到不了137年就会死掉

想想看你的电子产品多久就会重新去购买一次你就知道

32位的序列号可以彻底地解决这个问题

第二个问题是

如果一台路由器崩溃

那么它将丢失自己的序列号记录

如果它再从零开始的话

新分组就会被当作旧分组而被拒绝

还有一个问题就是序列号被破坏的问题

比如说发送方的序列号本来是4

但是由于传输的过程里头产生了一位错误

序列号被看做65540

那么序列号为5到65540的分组

就会被当做过时的分组而被拒绝

事实上这些分组都是新的分组

解决上述路由器崩溃

或者序列号损坏的方法是这样

每一个分组的序列号之后我们加上一个年龄age

并且呢 这个年龄是每秒钟减一

当年龄减为零的时候

来自该路由器的信息将被抛弃

通常地

每隔一段时间

比如说十秒钟

一个新分组就会到来

所以只有Down机的时候

才可能导致超时

来看一下age是怎么解决刚才说的两个问题的

一 路由器崩溃的问题

设想一下这样的情形

路由器A发送LSP给路由器B

B记录下收到的A的LSP的信息

然后A崩溃了

此时路由器B上记录下的A的LSP对应的age

已经开始倒计时

当A再次启动

通常age已经倒计时到零

A的LSP被B扔掉了

所以当重启后的A发送的LSP再次来到B

B上已经没有A的记录

新到达的LSP被重新记录

而不会被当做一个旧的分组扔掉

二 序列号损坏的问题

当某个LSP的序列号被损坏了

变成了另外一个序列号

由于序列号的连续性

损坏后的序列号并没有后续的序列号跟上

是孤立的

所以 损坏后的序列号对应的那个LSP

很快就会因为age倒计时到零而被丢弃

正确序列号的LSP将会被

重新纪录

还有一些改进可以让

基本的算法更加的健壮

当一个LSP或者LSA到达某台路由器的时候

它不是马上对它作出决策

而是首先被放到一个保留区中等待一段时间

在这个等待的时间里面

如果来自相同路由器的另外一个分组到达了

这两个分组的序列号会被比较

如果相等

就是重复分组

丢弃

如果不相等

旧的那个 就是序列号小的那个

被丢弃

为了防止路由器到路由器的线路发生错误

所有的链路状态分组

都要求被确认

当一条线路空闲的时候

路由器扫描保留区

以便选择一个LSP或者LSA

进行确认或者转发

举一个保留区的例子

拓扑图中的路由器b

有一个数据结构像这个表格所示

它的每一行对应着保留区中

也就是缓存中

一个还未被处理完毕的LSP

比如这一行

它表示E的21号LSP

通过A和F到达

它应该向C去转发

所以

对应A、C、F的发送标记是0 1 0

表示

不需要向A和F发送

但是向C发送

而确认的标记为1 0 1

表示应该向A和F发送确认

当路由器B还未做任何动作

一个E的21号LSP通过C到达了

那么

路由器B 这个时候要做的就是

修改发送标记为0 0 0

确认标记为1 1 1

意思是

E的21号LSP

B的三个邻居 A、C、F都收到过了

无需向它们去转发

只需要向它们发出确认就好了

一旦一个路由器

获得了全部的链路状态分组

就可以构造出全网的拓扑图来了

现在就可以用到第五个词 计算

可以使用

最短路径树

比如说 Dijkstra

来计算路由器之间的最短路径

计算的结果是

以路由器自己为根

到其它网络 到其它路由器的

最优的路径形成的一棵树

树显示的路由信息

将被安装在路由表中

引导数据分组的转发

LS路由的优点是

每个路由器的认识是一致的

根据LSP构造出的图完全一样

收敛快

它适合在大型的网络里头使用

它的缺点是

每个路由器都需要较大的存储空间

计算的负担也比较大

小结一下今天的内容

状态路由选择的基本原理是

一 发现邻居或邻居们

二 设置到它的邻居或者邻居们的成本

第三 把上述两步发现的信息

构造成LSA/LSP

第四 将LSA/LSP

分发到所有的其它的路由器

第五

一个路由器根据收到的LSA/LSP

构造出全网的拓扑图Graph

遍历这张图

就可以计算出一棵

以自己为根到达所有其它网络的

最优路径树