第6章路由算法

1、第第6 6章章 路由算法路由算法uyxwvz2213112535图: 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的连接图抽象：边的代价uyxwvz2213112535 c(x,x) = 链路的代价 (x,x) - e.g., c(w,z) = 5 代价可能总为, 或者是链路带宽的倒数, 或者是拥塞情况的倒数Cost of pa

2、th (x1, x2, x3, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) 问题: 结点到结点的最小代价路径是什么？路由算法:发现最小代价路径的算法r路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源结点到目标结点的较好路径m较好路径: 按照某种指标较小的路径r路由算法(routing algorithm):网络层软件的一部分,完成路由功能r路由的时机m虚电路:在建立虚电路时使用(会话路由选择，session routing)m数据报:每个分组独立路由路由的概念r汇集树(sink tree)m一个结点的汇集树:所有其它结点到此结点的最优路径形成

3、的树m路由算法就是为所有路由器找到并使用汇集树最优化原则(optimality principle)r正确性(correctness)：算法必须正确和完整，使分组一站一站接力，正确发向目的站点r简单性(simplicity)：在计算机上，算法的实现应该简单。最优但复杂的算法，时间延迟很大，不实用，不应为了获取路由信息而增加很多的通信量r健壮性(robustness)：算法应适应通信量和网络拓扑的变化，不向很拥挤的链路发送数据，不向中断的链路发送数据r稳定性(stability)：产生的路由不应该摇摆r公平性(fairness)：对每一个站点都公平r最优性(optimality)：某一个指标的最

4、优（时间、费用或综合指标）。实际上，获取最优的结果代价较高，可以选择次优的结果路由算法的原则路由算法的分类自适应或者非自适应自适应或者非自适应? ?r非自适应算法(non-adaptive algorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的，也叫静态路由算法和非自适应路由算法r自适应算法(adaptive algorithm)：能适应网络拓扑和通信量的变化，也叫动态路由算法和自适应路由算法r固定路由算法（fixed routing algorithm）r洪泛法（flooding）r随机走动法（random walk）r基于流量的路由算法（flow-based routi

5、ng）非自适应路由算法r每个网络结点存储一张表格，表格的每一项记录到达某个目的结点的下一结点或链路，而不是记录到该目的结点的所有中间结点r优点：简单，适合一个负载稳定和拓扑变化不大的网络r缺点：灵活性较差，无法对网络的拥塞和故障作出反应固定路由算法r结点收到不是发给它的分组时，就将该分组的副本向除输入链路之外的所有与此结点相连的链路转发出去r当网络的通信量很小时，该方法使分组的时延为最小，因为在并行发送的路由中，肯定有一条为最佳r该方法的缺点是网络中的分组数目会迅速增加，导致网络出现拥塞现象，应用并不广泛r该方法可用于健壮性要求很高的地方，如军事网络洪泛法r随即徘徊法r当分组到达某个结点时，随

6、机选择一条链路作为转发的路由；当某结点的输出链路有3条时，就以平均概率0.33选择任一条链路作为转发路由r当结点或链路发生故障时，该方法可使路由算法有较好的稳健性随机走动法r该方法不仅考虑网络的拓扑结构，还要考虑网络的负载因素r对某一给定的线路，如果已知负载量与平均流量，那么可以根据排队论的知识计算出该线路上的平均分组延迟r由所有的线路平均延迟，可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟r这样找出网络的最小平均延迟就可以实现最优路由选择基于流量的路由算法r孤立路由选择r集中路由选择r分布式路由选择自适应路由算法r每个结点并不利用其它结点来的网络信息，仅仅根据它自己所看到的情况

7、来确定路由m最短等待法m逆向学习算法孤立路由选择r根据所有结点的网络信息来选择路由r网络中设置了一个路由控制中心r每隔一段时间，每个结点向路由控制中心发送状态信息，如链路连接情况、流量和队列长度等r路由控制中心收集所有这些信息，然后根据它对整个网络的全局性了解，利用这些信息使用最短路径算法计算出每对结点之间的最佳路径，构造出路由表分发给对应的每个结点r缺点：计算量大和路由控制中心的脆弱性集中路由选择r根据来自于相邻结点的信息，通过一个最短花费路由算法计算出到每个目的地的路由r分布式路由算法得到了广泛使用r目前最流行的两个分布式路由算法m距离矢量路由算法（distance vector rout

8、ing） 局部：路由器只知道与它有物理连接关系的邻居路由器和到该路由器的代价m链路状态路由算法（link state routing） 全局：所有的路由器拥有完整的拓扑和边的代价的信息分布式路由选择r历史及应用情况m由Bellman、Ford和Fulkerson等提出m用于ARPANET， Internet和Novellr基本思想m每个结点都保存一张到目的地的路由表 到目的地的下一结点 测量出到目的地的度量值（metric）：初始化时，直接连接的目的地置为0（表示无需经过别的路由器），其它置为m每个结点把它的路由表定期向它直接连接的相邻结点传递距离矢量路由算法m当结点K从结点J接收一个更新消息

9、后，它对到每个目的地的路由和距离度量进行检查 如果J知道一条到目的地的更短的路径，结点K更新该目的地对应的下一结点标识和距离度量 如果J列出了一个K还没有记录的某个目的地的路径，结点K会向表中增加一项 如果K记录的下一结点标识为J，并且J所报告的到目的地的距离改变了，也会更新路由表中的距离度量距离矢量路由算法r算法表示m初始化。对于每个结点G，对所有它直接连接的目的地N，路由表中的表项用三元组(N,G,0)来表示，即从结点G到目的地N无需经过转发m结点G定期发送它的路由表给相邻结点。更新信息中对应着每一个目的地N用一个三元组来表示（N,V,D），即到目的地N的路由上的下一结点为V，G到N的距离

10、为D距离矢量路由算法m结点G收到G送来的路由信息，对于更新信息中给出的每个目的地，在G的路由表中查找相对应的表项，设它为（N,V,D），而更新信息中的三元组为（N,V,D），C为结点G和G之间的距离 如果找不到相应的表项，在G的路由表中增加一项：(N,G,D+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

11、,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中路由表对应的表项根据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的

12、特点 好消息传的快 坏消息传的慢m好消息的传播以每一个交换周期前进一个路由器的速度进行 好消息：某个路由器接入或有更短的路径 举例距离矢量路由算法rDV的无穷计算问题m坏消息的传播速度非常慢（无穷计算问题）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年后ARPANE

13、T的路由算法都转为LSrLS的基本工作过程m发现相邻结点，获知对方网络地址m测量到相邻结点的的代价（延迟或开销）m组装一个LS分组，描述它到相邻结点的代价情况m将分组通过扩散的方法发到所有其它路由器1.通过Dijkstra算法找出最短路径链路状态路由算法q发现相邻结点，获知对方网络地址m一个路由器加电之后，向所有线路发送HELLO分组m其它路由器收到HELLO分组，回送应答，在应答分组中告知自己的全局唯一的名字m在LAN中，通过广播HELLO分组，获得其它路由器的信息链路状态路由算法q测量到相邻结点的代价（延迟或开销）m实测法，发送一个分组要求对方立即响应m回送一个ECHO分组m通过测量时间可

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

15、jkstra算法计算出到其它各路由器的最短路径(汇集树)m将计算结果记录到路由表中rLS的应用情况mOSPF协议，用于Internet上链路状态路由算法r计算路由时，一般使用Dijkstra（迪杰斯特拉）算法rDijkstra算法为每条边赋予一个非负的权值，以两结点间路径权值的和作为该路径的距离r在网络中，每个结点都要用Dijkstra算法计算出到其它各结点的最短路径，从而构造出该结点的路由表 最短路径算法1543262213112535rDijkstra算法首先建立一个除源点外的所有结点的集合S，集合S保存尚未被删除的结点rDijkstra算法使用两个数组D和R，每个结点在这两个数组中都各有

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

17、)为该边的权值，否则为无穷大。初始化数组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到其它每个结点的最短距离和下一站路由表 最短路径算法1543262213112535初始化：S=2,3,4,5,6数组D（1到其它每个结点的最短距离）数组R（

18、1到其它每个结点的下一站路由表） 最短路径算法1543262213112535123456-251123456-23400 最短路径算法 最短路径算法 最短路径算法链路状态路由算法OSPF Development History1987198919911993199519971999OSPF Group formedOSPFv1 published RFC 1131OSPFv2 published RFC 1247Becomes recommendedCryptographic authenticationPoint-to-multipoint interfacesMOSPFOSPFv2 up

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

20、次性路由规模:有200M个目的主机r不可能在路由表中存储全部的目的地r路由器的路由表交换会淹没链路 自治管理rinternet =网间网r每一个网络管理员可能希望控制自己网络内部的路由我们前面讲的路由算法都比较理想化r所有的路由器都是一样的 r网络是平面的 实际的网络不是这样的r某个区域内的路由器集合，自治系统“autonomous systems” (AS)r在同一个AS内的路由器运行相同的路由协议m“intra-AS” routing protocol内部网关协议m不同AS的路由器可能运行着不同的内部网关协议网关路由器r直接和其它AS的路由器有直接的链路相连层次性路由3b1d3a1c2aA

21、S3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cr转发表由AS内部和AS间路由算法配置mIntra-AS 设置AS内部的目标网络mInter-AS & Intra-As 设置AS外部目标网络层次性路由3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS 任务r假设AS1 中的路由器收到了一个目标地址是AS1 外部的数据报m路由器应该将它转发到其中的一个gateway routers中，但是是哪一个？AS1 需要:r获知哪一个目标可以通过AS2 到达，哪一个可以通过AS3 到达r将这种可达性信息传播到AS1中的每一个路由器中inter-AS路由的工作!Intra-AS and Inter-AS routingGateways:perform inter-AS routing amongst themselvesperform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cn