大学生计算机网络及应用教程 网络层.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 热土豆算法举例：结点4收到一个发往结点6 的分组 左图：结点4当前各方向的队列长度Q 右表：结点4关于目标结点6的徧置表B 发往结点1，Q+B=2+9=11 发往结点2，Q+B=3+6=9 发往结点3，Q+B=1+3=4 发往结点5，Q+B=5+0=5 Q+B=4为最小值，发往结点3为最佳路由 自适应式路由选择的缺点: (1) 最佳路由的计算更复杂，更频繁，因而开销更大 (2) 收集到的路由信息要传播到计算路由的结点，或者计算的结果要传播到转发分组的结点。这些都增加了网络的负载 (3) 自适应算法对网络参数的变化反应太快会引起信息流的振荡，反应太慢则得不到最佳路由，为减少这些风险要经常对算法本身的某些参数进行调整，这又增加了网络管理的难度 自适应路由选择的优点： (1) 能极大地改善网络的性能，网络的经营者可以得到最大的吞吐率，网络用户则会明显感到网络延迟很小 (2) 能对网络的通信量进行控制，避免或减缓网络中拥挤和阻塞的发生 由于这些重要的优点，自适应路由选择虽然代价很高，但在大型公共网络中得到广泛的应用 4 路由选择算法实例 1）ARPANET ARPANET的路由选择算法基于分布式自适应策略，随着网络的发展经历了三次重大修改： 1969年的算法根据各输出链路的队列长度选择路由，但随着网络技术的进步和复杂化，数据的拥挤程度逐渐不再是决定最佳路由的唯一因素 1979年的新算法直接测量链路延迟选择路由 由于链路延迟包含了分组在转发结点的停留时间和链路优劣两个因素，适应了新的网络状态，网络性能比老算法有很大改善 新算法的缺点是新计算出的路由表的有效性与网络的负载大小有很大关系，在网络负担很重的情况下，当所有结点根据测量到的链路延迟信息确定了新路由表时，网络实际的时延情况已经有了很大改变，这种滞后效应导致信息流振荡，从而耗费了大量的线路带宽，使网络负担更重，甚至引起拥挤和阻塞 ARPAnet的设计者们认为，问题的本质是每个结点都想得到最佳路由，而这些要求是互相冲突的，于是在1987年进行了第三次大修改 新算法的计算过程分为两步，目的是消除路由选择中的振荡，使平均路由好，而追求所有通路最佳 (1) 首先测量最近10秒钟各链路的平均延迟，结合各链路容量，计算出各链路利用率p (2) 用上一时刻的平均利用率平滑最近10秒钟的利用率，得出n时刻新的平均利用率： u(n) = 0.5p(n) + 0.5u(n-1) u(n)：n时刻新的平均利用率 p(n)：最近10秒钟的利用率 u(n-1)：上一时刻的平均利用率： u(n-1) = 0.5p(n-1) + 0.5u(n-2) 由于第三次修改使用了平均和平滑算法，避免了对网络参数变化的过敏反应，因而有效地抑制了信息流振荡 又由于路由选择基于线路利用率，兼顾了平均延迟和线路容量两个因素，通过卫星链路（高时延）和地面链路（低时延）的对比实验表明，轻负载时，链路延迟起主要作用，重负载时，线路容量起主要作用 2）TYMNET TYMNET是集中控制的网络，由一个中心结点进行路由管理，管理中心记录着每一条链路的固定费用值，例如4800b/s链路费用值为12， 9600b/s链路费用值为10，如果经过链路的某一虚电路等待了0.5s以上没有等到服务，则称为过载，费用值增加16 TYMNET的第二个特点是使用虚电路提供面向连接的网络服务 管理中心计算好路由信息后把虚电路经过的所有结点列表装配成一个穿线分组，发送给源结点，穿线分组从源结点出发沿着预定的路径到达目标结点，使沿路结点都得到虚电路路由信息。建立一条虚电路需时12ms TYMNETI的第三个特点是，在轻负载时尽量使用高速链路，当负载增加时，路由选择算法能平滑地把负载分散到低速链路上 TYMNETI的第四个特点是链路