资源描述：
《第6章路由算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第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的连接图抽象：边的代价uyxwvz2213112535c(x,x’)=链路的代价(x,x’)-e.g.,c(w,z)=5代价可能总为１,或者是链路带宽的倒数,或者是拥塞情况的倒数Costofpath(x1,x2,x3,…,xp)=c(x1
2、,x2)+c(x2,x3)+…+c(xp-1,xp)问题:结点ｕ到结点ｚ的最小代价路径是什么？路由算法:发现最小代价路径的算法路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源结点到目标结点的较好路径较好路径:按照某种指标较小的路径路由算法(routingalgorithm):网络层软件的一部分,完成路由功能路由的时机虚电路:在建立虚电路时使用(会话路由选择，sessionrouting)数据报:每个分组独立路由路由的概念汇集树(sinktree)一个结点的汇集树:所有其它结点到此结点的最优路径形成的树路由算法就是为所有路由器找到并使用汇
3、集树最优化原则(optimalityprinciple)正确性(correctness)：算法必须正确和完整，使分组一站一站接力，正确发向目的站点简单性(simplicity)：在计算机上，算法的实现应该简单。最优但复杂的算法，时间延迟很大，不实用，不应为了获取路由信息而增加很多的通信量健壮性(robustness)：算法应适应通信量和网络拓扑的变化，不向很拥挤的链路发送数据，不向中断的链路发送数据稳定性(stability)：产生的路由不应该摇摆公平性(fairness)：对每一个站点都公平最优性(optimality)：某一个指标的最优（时间、费
4、用或综合指标）。实际上，获取最优的结果代价较高，可以选择次优的结果路由算法的原则路由算法的分类自适应或者非自适应?非自适应算法(non-adaptivealgorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的，也叫静态路由算法和非自适应路由算法自适应算法(adaptivealgorithm)：能适应网络拓扑和通信量的变化，也叫动态路由算法和自适应路由算法固定路由算法（fixedroutingalgorithm）洪泛法（flooding）随机走动法（randomwalk）基于流量的路由算法（flow-basedrouting）非自适应
5、路由算法每个网络结点存储一张表格，表格的每一项记录到达某个目的结点的下一结点或链路，而不是记录到该目的结点的所有中间结点优点：简单，适合一个负载稳定和拓扑变化不大的网络缺点：灵活性较差，无法对网络的拥塞和故障作出反应固定路由算法结点收到不是发给它的分组时，就将该分组的副本向除输入链路之外的所有与此结点相连的链路转发出去当网络的通信量很小时，该方法使分组的时延为最小，因为在并行发送的路由中，肯定有一条为最佳该方法的缺点是网络中的分组数目会迅速增加，导致网络出现拥塞现象，应用并不广泛该方法可用于健壮性要求很高的地方，如军事网络洪泛法随即徘徊法当分组到达某
6、个结点时，随机选择一条链路作为转发的路由；当某结点的输出链路有3条时，就以平均概率0.33选择任一条链路作为转发路由当结点或链路发生故障时，该方法可使路由算法有较好的稳健性随机走动法该方法不仅考虑网络的拓扑结构，还要考虑网络的负载因素对某一给定的线路，如果已知负载量与平均流量，那么可以根据排队论的知识计算出该线路上的平均分组延迟由所有的线路平均延迟，可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟这样找出网络的最小平均延迟就可以实现最优路由选择基于流量的路由算法孤立路由选择集中路由选择分布式路由选择自适应路由算法每个结点并不利用其它结点来
7、的网络信息，仅仅根据它自己所看到的情况来确定路由最短等待法逆向学习算法孤立路由选择根据所有结点的网络信息来选择路由网络中设置了一个路由控制中心每隔一段时间，每个结点向路由控制中心发送状态信息，如链路连接情况、流量和队列长度等路由控制中心收集所有这些信息，然后根据它对整个网络的全局性了解，利用这些信息使用最短路径算法计算出每对结点之间的最佳路径，构造出路由表分发给对应的每个结点缺点：计算量大和路由控制中心的脆弱性集中路由选择根据来自于相邻结点的信息，通过一个最短花费路由算法计算出到每个目的地的路由分布式路由算法得到了广泛使用目前最流行的两个分布式路由算
8、法距离矢量路由算法（distancevectorrouting）局部：路由器只知道与它有物理连接关系的邻居路
