计算机网络之网络层－ 路由算法与路由协议_链路状态路由选择算法( ls算法) 计算过程,以下图为例,从x结点出发, 分别求到达结

1. 路由选择算法

1.1.  带权无向图；

将网络抽象为一个带权无向图G=(N,E)， N表示结点集合， E是边的集合。

网络中的路由器抽象为图G的结点， 连接两个路由器的网络链路抽象为G的边。

网络链路的费用（ 比如时延） 抽象为G中的权值。

如果两个结点间有边， 例如从结点X到结点Y，则从结点X到结点Y耗费的费用记做C(X,Y)=10。

如果两个结点间没有边， 例如结点X到结点U，则从结点X到结点U耗费的费用记做C(X,U)=∞。

1.2. 路由选择算法的分类；

1. 是否需要全局信息

2. 静态动态

3. 是否敏感

2. 链路状态路由选择算法（ LS算法）

2.1. 算法概念；

链路状态路由选择算法是一种全局式路由算法， 需要构建出整个网络的拓扑图。

链路状态路由选择算法： 利用 Dijkstra算法 求最短路径。

注意：关于P(v)的值，如果路径上只有两个结点，则 P(v) 就是最后一个结点，例如： X→Y， P(y)就是y。

2.2. 算法计算过程；

链路状态路由选择算法（ LS算法） 计算过程，以下图为例，从X结点出发， 分别求到达结点Y,U,V,W的最短距离。

结合上图，从结点X开始，依次得出X结点到每个结点的直接D[]与P[]的值。

此时， 比较D[]， 找到最短的 D[] 对应的结点， 并且把该结点加入S中，如下图所示，把y结点加入了S集合中。

Y加入S后， 继续求X到U,V,W的最短距离。 注意， 此时Y可以连接到的结点， 如果路过Y可以到达， 也是一条链路。

此时， 比较新一轮的D[]， 找到最短的D[]对应的结点， 并且把该结点加入S中。但是发现， Y和V不是在一条链路上的，所以在新的一轮链路上要把y点移除掉。

第三轮计算：

第四轮计算：

路由器x上的转发表只存放下一跳路由器， 而不是最终路由器。所以，结点X上的转发表如下图所示：

2.3. 算法练习题；

结合上图，填出以下的空：

答案如下：

3. 距离向量路由选择算法（ DV算法）

距离向量路由选择算法： 基础是Bellman-Ford方程（简称B-F方程） 。

通过以上计算得到结点 X 到结点 Z 的最短路径是{x，y，z}。

由此规定：网络中每个结点x， 估计自己到网络中结点y的最短距离， 记为Dx(y)，称为结点x的距离向量。

路由器分别维护自己的转发表（ DV） 如下：

每个路由器同时会收到邻居的通告，并对转发表进行更新。

上图中，x 的DV中到 z 的距离原本为7，当收到 y 点的通告，y 点会告诉 x 点我这里到 z 点的距离只有3，而 x 点到 y 点的距离只有2，所以 x 的DV中对到 z 点的距离进行了更新，即3加2等于5。

同理，z 的DV中对到 x 的距离也进行了更新，最终更新的表如下：

4. 层次化路由选择

在合理的网络规模范围内： LS算法和DV算法。

大规模网络：层次化路由选择（最有效可行的解决方案）。

层次化路由选择组成：

1. 自治系统（ autonomous system， AS） ： 互联网按组织边界划分为多个自治系统，每个自治系统由运行相同路由协议和路由选择算法的路由器组成。

2. 网关路由器： 每个自治系统存在至少一个与其他自治系统互连的路由器。

大规模互联网的路由划分为两层：

1. 自治系统内路由选择： 计算到达自治系统内目的网络的路由。

2. 自治系统间路由选择： 负责其他自治系统网络的可达性信息。

5. Internet路由选择协议

Internet层次化路由选择分为内部网关协议与外部网关协议。

5.1. 内部网关协议（Interior Gateway Protocol，IGP）： Internet自治系统内路由选择协议；

1. 路由信息协议(Routing Information Protocol， RIP)；

RIP： 较小的AS（自治系统）， 基于距离向量路由选择算法的IGP；

RIP报文： 封装进UDP数据报。

RIP特性：

A. RIP在度量路径时采用的是跳数。

B. RIP的费用定义在源路由器和目的子网之间。

C. RIP被限制的网络路径不超过15跳的自治系统内使用。

由以上路由器B的转发表可知：由路由器 B 到目的子网 z 的下一跳路由器是C，需要的跳数是10，路由器 A 与 路由器 B 相邻，A 到 z 的跳数为3，所以 B 改道经过 A 到达 z，B到A为 1 跳，A到z为 3 跳，共 4 跳。

计算示例：设网络中路由器使用RIP协议， 路由器B的当前路由表如表1所示， B收到从路由器C发来的路由信息如表2所示，试给出路由器B更新后的路由表。

路由器B更新后的路由表如下：

2. 开放最短路径优先协议(Open Shortest Path First， OSPF)；

OSPF： 较大规模的AS， 基于链路状态路由选择算法的IGP。

RIP报文： 直接封装在 IP数据报传输。

OSPF的优点：

A. 安全；

B. 支持多条相同费用路径；

C. 支持区别化费用度量；

D. 支持单播路由与多播路由；

E. 分层路由；

5.2. 外部网关协议（Exterior Gateway Protocol，EGP）： Internet自治系统间路由选择协议；

EGP报文： BGP封装进TCP报文段。

BGP主要有4种报文：

1. OPEN（ 打开） 报文， 用来与BGP对等方建立BGP会话；

2. UPDATE（ 更新） 报文， 用来通告某一路由可达性信息， 或者撤销已有路由；

3. KEEPALIVE（ 保活） 报文， 用于对打开报文的确认， 或周期性地证实会话的有效；

4. NOTIFICATION（ 通知） 报文， 用来通告差错；

5.3. 协议对比；