计算机网络PPT教学课件-第5章_广域网.ppt

第五章 广域网 分散通信量法（traffic bifurcation） 这种方法是事先在每个结点的内存中设置一个路由表，但此路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率。 洪泛法（flooding） 这种方法是当某个结点收到一个不是发给它的分组时，就向所有与此结点相连的链路转发出去。当然，不能再把这个分组发到它刚刚离开的那个结点，否则就永远有一些分组来回不停地在各条链路上“振荡”。 采用两种方法来限制分组数目: 一种方法是在每个分组的首部设置一个计数器。每当分组到达一个结点时，计数器即自动加1。当计数器所计的数达到规定值时（如达到端到端所能达到的最大段数），即将此分组丢弃。 另一种方法是在每一个结点建立一个登记表，凡经过此结点的分组均进行登记。当某个分组再次通过该结点时，即将该分组丢弃。 随机走动法(random walk) 这种方法又称为随机徘徊，其特点是当分组到达某个结点时就随机地选择一条为转发的路由。 4.自适应路由选择 分布式路由选择策略 在分布式路由选择策略中，最基本的算法有两个，即距离向量算法和链路状态算法。 下面介绍距离向量算法。每个结点上保持有两个向量： 每个结点定期与它所有相邻结点交换它们的时延向量。然后根据收到的全部时延向量来修改本结点的D与S。对于任一结点k，修改方法如下： 分布式路由选择方法的几个要素： · 对于网络的某种特性的测量过程。 · 关于如何传播上述特性的测量结果的协议。 · 如何计算出所确定的路由。 时延的测量方法： 早期ARPANET把在一个结点中向某条链路发送的等待队列中的分组数目再加上一个常数（即偏移）作为此链路的时延。 存在的问题： 当一个分组到达某一个结点时，还需要经过一段处理时间（这时间是可变的）才加入等待队列。 等待队列长度的瞬时值（在测量瞬间得到的值）并不能精确代表链路的平均时延。实际测量结果表明，在高负荷工作下，虽然网络的平均时延很大，但仍还有不少分组具有很小的时延，而有的队列长度有时甚至下降到零。 等待队列的长度仅仅是影响分组的延时许多因素中的一个。仅就这一因素进行测量不能得出精确的结果。 改进方法： 不再用队列长度表示时延，而是将时延实际测量出来。当分组到达某个结点时，立即在分组上写入到达时间，即打上时间戳（timestamp）。当该分组发送时，再记录发出时间。发出时间减去到达时间再加上分组的发送时间和传播时间，即得出时延。若收到否认响应，则在重传时将发送时间更新，“时延”是一次成功的发送所经历的时间。 路由表的更新： 在新的路由算法中，不再是128 ms更新一次，而是10s更新一次，时延信息采用广播方式传送给其它结点。 集中式路由选择策略 网控中心NCC负责全网状态信息的收集、路由计算以及路由选择的实现。 优点：各个结点不需要进行路由选择计算，较容易得到更精确的路由最优化，消除了路由不断变来变去的“振荡”现象。还可起到对进入网络的通信量的某种流量控制作用。 缺点：一个是距离NCC较近的地方通信量的开销较大，这是因为要周期性地从所有结点收集网络的状态信息的报告，同时还要将路由选择的命令从NCC送到网内的每一个结点。另一个更严重的缺点是可靠性问题，一旦NCC出故障，则整个网络即失去控制。 混合式路由选择策略 目前可行的混合式路由选择策略只能是将集中式的和孤立的路由选择策略结合起来。集中式的路由选择策略用来寻找在稳定状态下的最佳路由，然后由NCC将路由表送到每一个结点去。而孤立的路由选择策略则用来提供对局部的拥塞和故障的迅速响应。 1、拥塞控制的意义 若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏，这种情况就叫做拥塞（congestion） Σ对资源的需求可用资源 1）解决网络拥塞是一项系统工程 网络拥塞往往是由许多因素引起的. 2）拥塞控制与流量控制的关系密切 拥塞控制是一个全局性的过程 流量控制往往指在给定的发送端和接收端之间的点对点通信量，是一个局部的过程 3）进行拥塞控制需要付出代价 4）死锁问题 当网络负载继续增大到某一数值时,网络的吞吐量就下降到零,网络已无法工作。这就是所谓的死锁（Deadlock） （1）直接死锁：由互相占用对方需要的资源而造成的死锁 （2）重装死锁： 5）拥塞特点 当网络负载较小时，有拥塞控制的吞吐量反而比无拥塞控制时要小。