第6章路由算法

1、第第6 6章章 路由算法路由算法 u yx wv z 2 2 1 3 1 1 2 5 3 5 图: G = (N,E) N = 路由器集合 = u, v, w, x, y, z E = 链路集合 = (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) 图抽象 标注：图抽象在其它网络上下文中也十分有用 例如: P2P, N是peer结点，E是TCP的连接 图抽象：边的代价 u yx wv z 2 2 1 3 1 1 2 5 3 5 c(x,x) = 链路的代价 (x,x) - e.g., c(w,z) = 5 代价可能总为,

2、 或者是链路 带宽的倒数, 或者是拥塞情况 的倒数 Cost of path (x1, x2, x3, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) 问题: 结点到结点的最小代价路径是什么？ 路由算法:发现最小代价路径的算法 r路由:按照某种指标(传输延迟,所经过的站点数目 等)找到一条从源结点到目标结点的较好路径 m较好路径: 按照某种指标较小的路径 r路由算法(routing algorithm):网络层软件的一部 分,完成路由功能 r路由的时机 m虚电路:在建立虚电路时使用(会话路由选择， session routing) m数据报:每个分组独立路由

3、路由的概念 r汇集树(sink tree) m一个结点的汇集树:所有其它结点到此结点的最优路径 形成的树 m路由算法就是为所有路由器找到并使用汇集树 最优化原则(optimality principle) r正确性(correctness)：算法必须正确和完整，使 分组一站一站接力，正确发向目的站点 r简单性(simplicity)：在计算机上，算法的实现应 该简单。最优但复杂的算法，时间延迟很大，不实 用，不应为了获取路由信息而增加很多的通信量 r健壮性(robustness)：算法应适应通信量和网络拓 扑的变化，不向很拥挤的链路发送数据，不向中断 的链路发送数据 r稳定性(stabilit

4、y)：产生的路由不应该摇摆 r公平性(fairness)：对每一个站点都公平 r最优性(optimality)：某一个指标的最优（时间、 费用或综合指标）。实际上，获取最优的结果代价 较高，可以选择次优的结果 路由算法的原则 路由算法的分类 自适应或者非自适应自适应或者非自适应? ? r非自适应算法(non-adaptive algorithm)：不能 适应网络拓扑和通信量的变化,路由表是事先计 算好的，也叫静态路由算法和非自适应路由算法 r自适应算法(adaptive algorithm)：能适应网络 拓扑和通信量的变化，也叫动态路由算法和自适 应路由算法 r固定路由算法（fixed rou

5、ting algorithm） r洪泛法（flooding） r随机走动法（random walk） r基于流量的路由算法（flow-based routing） 非自适应路由算法 r每个网络结点存储一张表格，表格的每一项记录到 达某个目的结点的下一结点或链路，而不是记录到 该目的结点的所有中间结点 r优点：简单，适合一个负载稳定和拓扑变化不大的 网络 r缺点：灵活性较差，无法对网络的拥塞和故障作出 反应 固定路由算法 r结点收到不是发给它的分组时，就将该分组的副本 向除输入链路之外的所有与此结点相连的链路转发 出去 r当网络的通信量很小时，该方法使分组的时延为最 小，因为在并行发送的路由中，

6、肯定有一条为最佳 r该方法的缺点是网络中的分组数目会迅速增加，导 致网络出现拥塞现象，应用并不广泛 r该方法可用于健壮性要求很高的地方，如军事网络 洪泛法 r随即徘徊法 r当分组到达某个结点时，随机选择一条链路作为转 发的路由；当某结点的输出链路有3条时，就以平均 概率0.33选择任一条链路作为转发路由 r当结点或链路发生故障时，该方法可使路由算法有 较好的稳健性 随机走动法 r该方法不仅考虑网络的拓扑结构，还要考虑网络的 负载因素 r对某一给定的线路，如果已知负载量与平均流量， 那么可以根据排队论的知识计算出该线路上的平均 分组延迟 r由所有的线路平均延迟，可直接计算出流量的加权 平均值，从

7、而得到整个网络的平均分组延迟 r这样找出网络的最小平均延迟就可以实现最优路由 选择 基于流量的路由算法 r孤立路由选择 r集中路由选择 r分布式路由选择 自适应路由算法 r每个结点并不利用其它结点来的网络信息，仅仅根 据它自己所看到的情况来确定路由 m最短等待法 m逆向学习算法 孤立路由选择 r根据所有结点的网络信息来选择路由 r网络中设置了一个路由控制中心 r每隔一段时间，每个结点向路由控制中心发送状态 信息，如链路连接情况、流量和队列长度等 r路由控制中心收集所有这些信息，然后根据它对整 个网络的全局性了解，利用这些信息使用最短路径 算法计算出每对结点之间的最佳路径，构造出路由 表分发给对

8、应的每个结点 r缺点：计算量大和路由控制中心的脆弱性 集中路由选择 r根据来自于相邻结点的信息，通过一个最短花费路 由算法计算出到每个目的地的路由 r分布式路由算法得到了广泛使用 r目前最流行的两个分布式路由算法 m距离矢量路由算法（distance vector routing） 局部：路由器只知道与它有物理连接关系的邻居路由器 和到该路由器的代价 m链路状态路由算法（link state routing） 全局：所有的路由器拥有完整的拓扑和边的代价的信息 分布式路由选择 r历史及应用情况 m由Bellman、Ford和Fulkerson等提出 m用于ARPANET， Internet和No

9、vell r基本思想 m每个结点都保存一张到目的地的路由表 到目的地的下一结点 测量出到目的地的度量值（metric）：初始化时，直接 连接的目的地置为0（表示无需经过别的路由器），其 它置为 m每个结点把它的路由表定期向它直接连接的相邻结点传递 距离矢量路由算法 m当结点K从结点J接收一个更新消息后，它对 到每个目的地的路由和距离度量进行检查 如果J知道一条到目的地的更短的路径，结点K更 新该目的地对应的下一结点标识和距离度量 如果J列出了一个K还没有记录的某个目的地的路 径，结点K会向表中增加一项 如果K记录的下一结点标识为J，并且J所报告的到 目的地的距离改变了，也会更新路由表中的距离

10、度量 距离矢量路由算法 r算法表示 m初始化。对于每个结点G，对所有它直接连接的 目的地N，路由表中的表项用三元组(N,G,0)来表 示，即从结点G到目的地N无需经过转发 m结点G定期发送它的路由表给相邻结点。更新信 息中对应着每一个目的地N用一个三元组来表示 （N,V,D），即到目的地N的路由上的下一结点为 V，G到N的距离为D 距离矢量路由算法 m结点G收到G送来的路由信息，对于更新信息中 给出的每个目的地，在G的路由表中查找相对应的 表项，设它为（N,V,D），而更新信息中的三元组 为（N,V,D），C为结点G和G之间的距离 如果找不到相应的表项，在G的路由表中增加一项 ：(N,G,D+

11、C) 如果V=G，G中路由表对应的表项根据D+C和D的 比较获得 如果D+CD，G中表项更新为(N,G,D+C) 否则G中表项保持原状，仍为(N,V,D) 距离矢量路由算法 正确的算法 r如果找不到相应的表项，在G的路由表中增加一项：(N,G,D+C) r 如果V=G，G中路由表对应的表项根据D+C和D的比较获得 r如果D+CD，G中表项更新为(N,G,D+C) r否则G中表项保持原状，仍为(N,V,D) r 改为： r 如果找不到相应的表项，在G的路由表中增加一项： (N,G,D+C) r 如果V=G，那么无条件的把G中的项目更新为G中的 (N,G,D+C)。 r 如果VG，G中路由表对应的

12、表项根据D+C和D的比较获得 r如果D+CD，G中表项更新为(N,G,D+C) r否则G中表项保持原状，仍为(N,V,D) r该改为：如果V=G，那么无条件的把G中的项目更新为G。理由 是：要以最新消息为准。见谢希仁第五版计算机网络148页 距离矢量路由算法 距离矢量路由算法 路由器1的更新前的路由表 路由器2发给路由器1的报文 路由器1的更新后的路由表 rDV的无穷计算问题 mDV的特点 好消息传的快 坏消息传的慢 m好消息的传播以每一个交换周期前进一个路由器 的速度进行 好消息：某个路由器接入或有更短的路径 举例 距离矢量路由算法 rDV的无穷计算问题 m坏消息的传播速度非常慢（无穷计算问

13、题） m例子 第一次交换之后， B从C处获得信息，C可以到达A(C-A, 要经过B本身)，但是路径是2，因此B变成3，从C处走 第二次交换，C从B处获得消息， B可以到达A，路径为3 。 因此，C到A从B走，代价为4 无限此之后， 到A的距离变成INF，不可达 距离矢量路由算法 rLS的背景 mDV的问题 代价没有考虑线路带宽因素，认为所有线路带宽一样 慢速收敛问题（无穷计算问题） m1979年后ARPANET的路由算法都转为LS rLS的基本工作过程 m发现相邻结点，获知对方网络地址 m测量到相邻结点的的代价（延迟或开销） m组装一个LS分组，描述它到相邻结点的代价情况 m将分组通过扩散的方

14、法发到所有其它路由器 1.通过Dijkstra算法找出最短路径 链路状态路由算法 q发现相邻结点，获知对方网络地址 m一个路由器加电之后，向所有线路发送HELLO分组 m其它路由器收到HELLO分组，回送应答，在应答分组中告 知自己的全局唯一的名字 m在LAN中，通过广播HELLO分组，获得其它路由器的信息 链路状态路由算法 q测量到相邻结点的代价（延迟或开销） m实测法，发送一个分组要求对方立即响应 m回送一个ECHO分组 m通过测量时间可以估算出延迟情况 q组装一个分组，描述相邻结点的情况 m发送者名称 m序号，年龄 m列表： 给出它相邻结点，和它到相邻结点的延迟 链路状态路由算法 q将分

15、组通过扩展的方法发到所有其它路由器 m顺序号：用于控制无穷的扩散，每个路由器都记 录（源路由器，顺序号），发现重复的或老的就 不扩散 具体问题1： 循环使用问题 具体问题2： 路由器崩溃之后序号从0开始 具体问题3：序号出现错误 m解决问题的办法：年龄字段(age) 生成一个分组时，年龄字段不为0 每过一个时间段，AGE字段减1 AGE字段为0的分组将被抛弃 链路状态路由算法 q通过Dijkstra算法找出最短路径 m路由器获得各站点LS分组和整个网络的拓扑 m通过Dijkstra算法计算出到其它各路由器的最短路 径(汇集树) m将计算结果记录到路由表中 rLS的应用情况 mOSPF协议，用于

16、Internet上 链路状态路由算法 r计算路由时，一般使用Dijkstra（迪杰斯特拉）算法 rDijkstra算法为每条边赋予一个非负的权值，以两结 点间路径权值的和作为该路径的距离 r在网络中，每个结点都要用Dijkstra算法计算出到其 它各结点的最短路径，从而构造出该结点的路由表 最短路径算法 1 54 32 6 2 2 1 3 1 1 2 5 3 5 rDijkstra算法首先建立一个除源点外的所有结 点的集合S，集合S保存尚未被删除的结点 rDijkstra算法使用两个数组D和R，每个结点在 这两个数组中都各有一项 m数组D的第i项存储从源点到结点i的最短距离 m数组R的第i项存

17、储从源点到结点i路径上的下一站 r用Weight(i,j)作为从结点i到结点j的权值，如果 从结点i到结点j没有边，则权值为无穷大() 最短路径算法 r随后，开始循环 m每次都从S中删除一个与源点之间有最短路径的结 点u，然后检查从源点到仍然在S中并与u相邻的每 个结点的距离 m如果从源点通过u到某结点的权值之和，比此前源 点到该结点的最短距离小，则更新该值 r当所有结点都从S中删除后，就能计算出到每 个结点的最短距离，同时也构造出路由表 最短路径算法 具体算法具体算法 初始化集合S，为除源点外的所有结点。 初始化数组D，如果从源点到v有边存在，则D(v)为该 边的权值，否则为无穷大。 初始化

18、数组R，如果从源点到v有边存在，则R(v)=v， 否则为0。 While(集合S非空) 从S中选一结点u，使D(u)最小； 如果 D(u)无穷大错误，S中无路径存在，退出 把u从S中删除； 最短路径算法 对(u,v)为边的每个结点v 如果（v仍在S中） C= D(u)+ Weight(u,v); 如果（C D(u) R(v)=R(u); D(v)=C+1; 最短路径算法 r用Dijkstra算法，计算从源点1到其它每个结点的最短 距离和下一站路由表 最短路径算法 1 54 3 2 6 2 2 1 3 1 1 2 5 3 5 初始化：S=2,3,4,5,6 数组D（1到其它每个结点的最短距离）

19、数组R（1到其它每个结点的下一站路由表） 最短路径算法 1 54 32 6 2 2 1 3 1 1 2 5 3 5 123456 -251 123456 -23400 最短路径算法 最短路径算法 最短路径算法 链路状态路由算法 OSPF Development History 1987198919911993199519971999 OSPF Group formed OSPFv1 published RFC 1131 OSPFv2 published RFC 1247 Becomes recommended Cryptographic authentication Point-to-mult

20、ipoint interfaces MOSPF OSPFv2 update RFC 1583 CIDR OSPFv2 update RFC 2178 OSPFv2 update RFC 2328 OSPFv3 RFC 2740 消息复杂度消息复杂度 rLS: 有 n 结点， E 条链路，发送 报文O(nE)个 rDV: 只和邻居交换信息 收敛时间收敛时间 rLS: O(n2)， 算法需要O(nE)报文 m有可能震荡 rDV: 收敛时间变化 m可能存在路由环路 mcount-to-infinity 问题 健壮性健壮性: 路由器发生故障会出 现什么? LS: m结点会通告不正确的链路代 价 DV:

21、 mDV 结点可能通告不正确的 路径代价 m每一个结点的路由表可能被 其它结点使用 LS 和 DV 算法的比较 层次性路由 规模:有200M个目的主机 r不可能在路由表中存储 全部的目的地 r路由器的路由表交换会 淹没链路 自治管理 rinternet =网间网 r每一个网络管理员可能希望 控制自己网络内部的路由 我们前面讲的路由算法都比较理想化 r所有的路由器都是一样的 r网络是平面的 实际的网络不是这样的 r某个区域内的路由器 集合，自治系统 “autonomous systems” (AS) r在同一个AS内的路 由器运行相同的路由 协议 m“intra-AS” routing prot

22、ocol内部网关协议 m不同AS的路由器可能 运行着不同的内部网 关协议 网关路由器 r直接和其它AS的路由器 有直接的链路相连 层次性路由 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b Intra-AS Routing algorithm Inter-AS Routing algorithm Forwarding table 3c r转发表由AS内部和 AS间路由算法配置 mIntra-AS 设置AS内部 的目标网络 mInter-AS & Intra-As 设 置AS外部目标网络 层次性路由 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c

23、2b 1b 3c Inter-AS 任务 r假设AS1 中的路由器收 到了一个目标地址是 AS1 外部的数据报 m路由器应该将它转发到其 中的一个gateway routers 中，但是是哪一个？ AS1 需要: r获知哪一个目标可以通 过AS2 到达，哪一个可 以通过AS3 到达 r将这种可达性信息传播 到AS1中的每一个路由 器中 inter-AS路由的工作! Intra-AS and Inter-AS routing Gateways: perform inter-AS routing amongst themselves perform intra-AS routers with other routers in their AS inter-AS, intra-AS routing in gateway A.c network l