路由和流量路由算法.ppt

《路由和流量路由算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、路由算法路由算法和流量控制的关系路由选择算法根据路由选择度量指标的不同，路由选择策略可以由多种具体的算法实现。常用的静态路由选择策略包括最短路径法、扩散法和基于流量法。动态路由选择策略包括距离矢量法和链路状态法。最短路径法1.基本思想在最短路径法中，数据沿着到目的网络的最短路径传送。每个路由器有一张路由表，表中包含去往任一目的路由器的下一跳路由器的地址和距离等路由信息。路由表在整个网络初始化配置时生成，并且在此后的一段时间内保持固定不变。当网络通信量相对稳定且拓扑结构固定不变时，采用最短路径法是最好的。基于流量的路由选择前面介绍的两个

2、有代表性的算法是针对网络拓扑结构设计的，在路由选择时没有考虑通信量的影响。这类路由选择算法会把大量的通信量汇集到最短路径的某一段上，尽管别的路径很“空闲”，例如，A到B的通信量很大，从A到C的分组仍然要走路径ABC，而不走AGEFC，尽管AGEFC很可能要比ABC空闲。可见，好的路由选择策略既要考虑拓扑结构又要兼顾通信量。下面，我们介绍这样的一种算法—基于流量的路由选择(flow-basedrouting)。1.基本思想基于流量的路由选择算法假定网络中每对路由器之间平均数据流量是相对稳定的和可预测的，然后通过对流量的定量分析，再对某个路

3、由选择进行优化(这个路由选择先由其他某个路由选择算法给出)。定量分析的基本作法是：对某一给定的链路，如果已知平均流量和载荷量，那么就可以由排队论原理计算出该链路上的平均分组延时。再由所有链路的平均延时，可直接计算出流量加权平均值，进而得到整个网络的平均分组延时。基于流量的路由选择就是要找出网络最小延时的路由。2.实施基于流量路由选择的条件从基本思想可以看出，基于流量的路由选择必须具有以下已知信息，才能给出正确的路由。(1)网络的拓扑结构：有了它，才能知道链路的数量。(2)路由器i和j之间的流量fij。(3)路由器i和j之间链路的载荷(容

4、量)cij。(4)初始路由算法：给出待优化路由。在流量和拓扑结构相对稳定的场合，这些条件容易满足的。这也正是静态算法适用擅长的场合，也是把该算法作为静态算法的原因。3.定量分析如图3所示，路由器之间链路上的数值表示容量cij(以bit/s为单位)，表的单元格中数据表示路由器之间链路上的流量fij(以分组/s为单位)和从源路由器到目的路由器的路由。例如从B到D的流量是3分组/s，路由是BFD。表中的路由是由初始路由算法得出的。图3算法示例条件值定量分析的步骤第1步：计算链路总流量λi。下面由fij来计算链路i的总流量λi。注意：(1)链

5、路i的总流量λi是指各路由经i的流量之和。例如链路AB的总流量λAB=9(A→B)+4(A→C)+1(A→D)=14，即λi=(2)链路是有向的，即AB和BA是两条链路。本例中流量是对称的，即XY流量与YX流量相等。链路的总流量如表1所示(8个链路)。定量分析的步骤（续1）第2步：计算链路平均分组数µci。链路i的平均分组数(平均流量)µci=其中µ=1/800。800代表分组平均长度(µ代表位宽度，单位s)。µci结果如表1所示。第3步：计算链路平均延时ti。由排队论知：ti=。8条链路的ti如表1所示。表1定量分析表(平均分组

6、长度=800bit)i链路λi(分组/s)ciµci(分组/s)ti(ms)权值ωi1AB142025910.1712BC122025770.1463CD61012.51540.0734AE112025710.1345EF135062.5200.1596FD81012.52220.0987BF102025670.1228EC82025590.098第4步：计算网络加权平均延时TT=其中ωi为链路i的权重，8条链路的ωi如表1所示，它等于总流量使用该链路的比例，而ωi=在本例中，8条链路的加权平均延时是86ms。4.路由决策上述定量分析的

7、结果给出了网络加权平均延时T，它可以看作是泛涵f以cij、fij和R0(初始路由选择算法)为输入值的输出值，即T=f(cij，fij，R0)因此，当R0变化时，即采用另外一种路由选择算法R后，会得到一个新的T*，当T*

8、由选择是可行的。当然计算比较的工作会影响路由选择的效率，分组会在路由器中多呆一会，但等待是值得的，因为它能得到更好的服务，就是那句话：Goodserviceworthyofwaitingfor!距离向量路由