《路由算法分类》由会员分享，可在线阅读，更多相关《路由算法分类（11页珍藏版）》请在金锄头文库上搜索。
1、路由算法及分类路由算法及分类:1、非自适应算法，静态路由算法不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。特点：简单，开销少；灵活性差。2、自适应算法，动态路由算法可根据网络流量和拓扑结构的变化更新路由表。特点：开销大；健壮性和灵活性好。3、最优化原则(optimality principle )如果路由器J在路由器I到K的最优路由上，那么从 J到K的最优路由会落在同一路 由上。4、汇集树(sink tree)从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树， 称为汇集树；路由算法的目的是找出并使用汇集树。BBFig. 5-
2、S (a) A subnet (b) A sink iree for router B.几种典型的路由选择算法：1、最短路径路由算法(Shortest Path Routing)1)基本思想构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。2）测量路径长度的方法结点数量地理距离传输延迟距离、信道带宽等参数的加权函数3） Dijkstra 算法每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；初始时，所有结点都为临时性标注，标注为无穷大；将源结点标注为0,且为永久性标注，并令其为工作结点
3、；检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于 该结点的标注，则用新计算得到的和重新标注该结点；在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点， 并成为下一轮检查的工作结点；e(2 A)C (9. B；0.重复第四、五步，直到目的结点成为工作结点；/Ei4.B). / /、*父G (5, E)卜 g.T他1= 6. E； 2-中Fig* 5-6. The first five steps used in computing the shorlcsl pall from A Io D. The arrows indicale the workin
4、g node.2、洪泛及选择洪泛算法1） 洪泛算法（Flooding）属于静态路由算法a）基本思想把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。b）王要问题洪泛要产生大量重复包。c）解决措施每个包头包含站点计数器，每经过一站计数器减1,为0时则丢弃该包;记录包经过的路径2）选择性洪泛算法（selective flooding ）洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。3）应用情况路由器和线路的资源过于浪费，实际很少直接采用；具有极好的健壮性，可用于军事应用；作为衡量标准评价其它路由算法。3、基于流量的路由算法（Flow-Based Routing ）属于静
5、态路由算法1）基本思想既考虑拓扑结构，又兼顾网络负荷；前提：每对结点间平均数据流是相对稳定和可预测的；因此路由选择问题归结为找产生网络最小延根据网络带宽和平均流量，可得出平均包延迟, 迟的路由选择算法。提前离线（off-line ）计算2）需要预知的信息网络拓扑结构；通信量矩阵Fij ;线路带宽矩阵Cij ;3）路由算法（可能是临时的）ABc0EF9417工AABABCABFDAEAEF98324BBABCBFDBFEBF48332CBACBCDCECEF13334DDFB ADFBDCDCEDFE72335E.AEFBECECDEF44245FFEArBF匚CFDFEDestination出
6、）Fig. 5-H* (a) A subnei with line cpacjlies shown in kbps, (b) The traffic in packcts/sec and the routing matrix. 1LineXj (pkts/sec)Cj (kbps)nCj (pkts/sec)I, msec)Weight1AB142025910.1712BC122025770.1463CD61012.51540 0734AE112025710.1345EF135062.5200.1596FD8101252220098?BF102025670,1228EC82025590098F
7、ig. 5-9, Analysis of the subnet of Hg. 54 using a mean packet size of 800 bits. The reverse traffic (BA, CH, etej is the siime us the lUrwHnl Irafiic.1/m = 800 bits根据排队论，平均延迟T = 1/ (mC - l)4、距离向量路由算法( Distance Vector Routing)属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于 ARPANET , 被RIP协议采用。1)基本思想
8、每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；邻居结点X发来的表中，X到路由器i的距离为Xi,本路由器到X的距离为m,则路由器 经过X至ij i的距离为Xi + m。根据不同邻居发来的信息，计算 Xi + m ,并取最小值，更新 本路由器的路由表；注意：本路由器中的老路由表在计算中不被使用delay from JTc AIHKj l
9、inRA B C nE 卜 G H 1J K L02420218A1236312820A2518193628I402782420H1423/203019401730II181731206031191812HH210142210I911710024222206K29339915KJAJIJHJKdelay delay de ay delay isisisis810126V 、v /New routing tabic for JNew cat matedVserors received fromtJs four neighborsFig. 5-10. (a) A subnet, (b) Input
10、 from A, I,H, K, and the new routing table for Jt2)无限计算问题算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；ABcD EABCDE*8婚 c Initially1234 Initially1gg oo After 1 exchange3234 After 1 exchange12 酬 After 2 exchanges3434 After 2 exchanges1238 After 3 exchanges5454 After 3 exchanges1234 After 4 exchanges5656 After 4 exchanges767
11、6 After 5 exchanges1B78 After 6 exchange;00 M 00 M陶Fig. 5UL The count-to-infiniiy problem.3）水平分裂算法工作过程与距离向量算法相同，区别在于到X的距离不向真正通向 X的邻居结点报告，使得坏消息传播的也快。虽然广泛使用，但有时候会失败。5、链路状态路由算法 （Link State Routing ）1）距离向量路由算法的主要问题选择路由时，没有考虑线路带宽；路由收敛速度慢。2）链路状态路由算法发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送 HELLO包发现邻居结点；两个或多个路由器连在一个 L
12、AN时，引入人工结点；测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以 2即为延迟。将所有学习到的内容封装成一个包；包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；Fig. 5-15链路状态包定期创建或发生重大事件时创建。将这个包发送给所有其它路由器；3）基本思想洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；4
13、）改进序号循环使用会混淆，解决办法：使用32位序号；路由器崩溃后，序号重置；链路状态包到达后， 延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；链路状态包需要应答；计算到每个其它路由器的最短路径。根据Dijkstra算法计算最短路径；5）实用协议OSPFIS-ISFig. 5-13* (a) Nine routers and a LAN. (b) A graph model of (a).Fig* 5-15. (a) A subnet, (b) Ihe link state packets for this subnet.Smdg养 ACK HagstJ，、1Source Seq. Age ACFACFDataA2160Q11100F21601In0niE215
