第2节 路由算法
路由算法
- 路由算法的概念
- 最优化的原则
- 静态路由算法
- 动态路由算法
- 分级路由
基本概念－路由器的两个动作
- 转发(forwarding)
每个分组到达的时候，在路由表中查找该分组所对应的输出路径。 - 路由选择(routing)
使用路由算法。
负责填充和更新路由表。
路由算法
理想的路由算法
路由算法的分类
想想看：
最优化原则，对于计算机网络中的分组转发有什么作用？
如果I，J，K的最佳路由是r1+r2，则当I把分组交给J时，J一定会沿着r2把分组转发出去。
汇集树(Sink Tree)
静态路由算法
- 静态路由算法
最短路径路由算法
扩散算法
最短路径路由算法 (shortest path routing)
扩散算法（Flooding）
- 属于静态路由算法
- 基本思想
事先不需要任何网络信息；
路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。
将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径
想想看？
如何消除：过时的/重复的分组？
- 算法的优点是什么？
不需要事前知道任何网络的拓扑信息；
所有的网络路径都被尝试过；
第一个到达的分组走的路径可能是最优的。 - 算法的主要问题是什么？
产生大量重复分组。
解决的方法
- 源端收到分组时，在每个分组的头部增加一个计数器。此后，每经过一跳该计数器减1，为0时丢弃。
计数器的初值＝最佳路径的跳数/子网的直径； - 每个路由器记录收到已经扩散过的分组，从而避免再次发送这些分组。
源端在每个分组中放置一个序号；
记录{源端地址，序号}；
每个路由器将得到的同一源端的分组的最大序列号分组记录下来，小于该序号的丢弃。
选择性扩散算法 （Selective Flooding）
- 选择性扩散算法是扩散法的一种改进。
能够消除多余的分组。 - 应用情况
对路由器和线路的资源过于浪费，实际的商用网络很少直接采用；
具有极好的健壮性，可用于军事应用；
作为衡量标准评价和初级拓扑消息获得方式应用于其它路由算法。
动态路由算法
距离矢量路由算法
链路状态路由算法
- 动态路由算法常见的有三种类型：
距离矢量D-V(Distance-Vector) 算法，如：RIP、IGRP、BGP；
链路状态L-S(Link State)算法，如：OSPF、IS-IS；
混合算法，如：Cisco的EIGRP。
5.2.4 距离矢量路由算法 （Distance Vector Routing）
- 路由以矢量（距离、方向）的方式被通告出去的，其中距离是根据度量来定义的(延迟、跳数等)，方向是根据下一跳路由器定义的。
使用距离矢量算法
试着扮演一次路由器吧！
距离=跳数
对链路故障的反应
好事传千里，坏事不出门！! 一个靠邻居“谣言”活着的路由协议
如何解决上述问题？
先想想：导致上述问题的本质原因是什么？
-
根据路由环产生的过程,可知通过水平分割法对解决两路由器之间形成的路由环是极为有效的方法.毒性逆转法可解决多路由器之间的路由环问题
5.2.5 链路状态路由算法 （Link State Routing）
算法的基本操作
1.发现邻居结点，并学习它们的网络地址
2.测量到各邻居节点的延迟或者开销
3.创建链路状态分组
4. 使用扩散法发布链路状态分组
使用的是可靠的扩散法
开动脑筋：存在的问题（1）
- 如果序列号回转了，则可能会产生混淆。
- 解决办法：
使用32位序号；
即使每秒钟产生一个链路状态分组，也需要137年才可能发生回转。
开动脑筋：存在的问题（2）
- 如果：
路由器崩溃后，序号重置；
或者序号出错； - 解决方法
增加年龄（age）域，每秒钟年龄减1，为零则丢弃。
链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；
链路状态包需要应答；
- 从E发来的链路状态包有两个，一个经过EAB，另一个经过EFB；
- 从D发链路状态包有两个，一个经过DCB，另一个经过DFB；
5.计算到每个其它路由器的最短路径
- 每个路由器都获得了自己的路由拓扑图
- 据Dijkstra算法计算最短路径;
- 生成自己的路由表
链路状态算法（LS） 和距离矢量算法（DV）的比较
- 路由信息的复杂性
LS
路由信息向全网发送
N节点，E个连接的情况下，每个节点发送O(nE)的报文
DV
仅在邻居节点之间交换 - 收敛（Convergence）速度
LS
使用最短路径优先算法，算法复杂度为O(n**2)
n个结点（不包括源结点），需要n*(n+1)/2 次比较
使用更有效的实现方法，算法复杂度可以达到O(nlogn)
可能存在路由振荡（oscillations）
DV
收敛时间不定
可能会出现路由循环
count-to-infinity问题 - 健壮性: 如果路由器不能正常工作会发生什么?
LS
结点会广播错误的链路开销
每个结点只计算自己的路由表
DV
结点会广播错误的路径开销
每个结点的路由表被别的结点使用，错误会传播到全网
5.2.6 分级路由
为路由器减负
不使用分级路由
使用分级路由
分级路由
- 假设某个子网中有720台路由器.
如果不使用分级路由方法：
每个路由器中的表项为720项； - 如果采用两个分级，分成24个区域，每个区域30个路由器：
30 本地表项
23 远程表项 - 如果采用三个分级，分成8个群，每个群包含9个区域，每个区域包含10个路由器，则：
10 本地表项
8 个本地群中的区域项
7 远程群
用图表示广域网的例子
在路由表中使用默认路由
