《计算机网络ppt教学课件第5章广域网》由会员分享,可在线阅读,更多相关《计算机网络ppt教学课件第5章广域网(29页珍藏版)》请在金锄头文库上搜索。
1、第五章 广域网,1.广域网的构成,5.1 广域网的基本概念,WAN 2,WAN 4,WAN 3,WAN 1,左图所示的广域网中,云图中及云图相连的部分称之为通信子网,以外的部分为资源子网。通信子网提供的是数据传输服务, 它实现OSI体系结构中的底三层,即物理层、数据链路层和网络层。,通信距离:几十或几百公里,甚至几千公里以上。 网络构成:由一些结点交换机及连接这些交换机的链路组成。结点交换机执行存储转发功能。 所在层次:广域网使用协议在网络层。局域网使用的协议在数据链路层。 网络互联:局域网通过路由器与广域网相连,构成全球互连网。 研究重点:路由选择,2.网络层提供的服务,无连接的网络服务数据
2、报服务; 面向连接的网络服务虚电路服务。1)数据报服务(Datagram):主机只要想发送数据就随时可发送,每个分组独立地选择路由。 2)虚电路服务(Virtual circuit):通信前主机要先建立一条虚电路,之后数据沿固定路由传送,通信后拆除虚电路。,(a)数据报服务 (b)虚电路服务,数据报和虚电路的比较:,结点交换机中的路由表 层次结构的编址方案最简单方案:把一个地址分成前后两部分a,b,a表示结点交换机编号,b表示计算机终端编号。路由表:每个结点都有一个路由表,包括目的站及下一跳两部分。交换机2的路由表:,5.2 广域网中的路由选择机制,如图节点交换机2中的路由表,计算机的编址和网
3、络层节点交换机的路由表,路由表的简化将目的站定义为交换机号,只有分组到达目的结点交换机,交换机才检查第二部分地址,再将分组交给目的计算机。上例每个交换机连接2个终端,路由表简化后为原来1/2大小。,2、用图表示广域网研究广域网路由问题时,可用图论中“图”来表示广域网,2,4,3,1,结点1的路由表:,默认路由:所有具有相同“下一站”的项目,用默认路由代替,其目的站用符号“*”标记,结点1路由表使用默认路由后,更加简洁,减少了搜索时间。,1.理想的路由算法 算法必须是正确和完整 计算上简单 具有自适应性 具有稳定性 算法公平 算法应是最佳的,5.3 路由选择的一般原理,2. 路由算法的分类 非自
4、适应路由选择策略 自适应路由选择策略 (1)非自适应路由选择:固定路由算法、分散通信量法、洪泛法、随机走动法 ()自适应路由选择 :分布式路由选择策略、 集中式路由选择策略、混合式路由选择策略,3.非自适应路由选择 固定路由法原理:在每个结点上保持一张路由表,表上标明对每一个目的地址应走哪条链路进行转发。这些表是在整个系统进行配置时生成的,并且在此后的一段相当时间保持固定不变。方法:将网络内任何两个结点之间的最短通路事先计算好,然后根据这些最短通路制成路由表,存放在各个结点中。 关键点:算出给定网络中任意两个结点之间的最短通路。即寻找从源结点到网络中其他各结点的最短通路。,令D(v)为源结点(
5、结点1)到结点v 的距离,它就是沿某一通路的所有链路的长度之和。再令l(i,j)为结点i 至结点j 之间的距离。整个算法只有以下两个部分: a.初始化。N为结点的集合,先令N1,对其它结点v,求出: 与结点1直接相连与结点1不直接相连 b.寻找一个不在N中的结点w,其D(w)值为最小。将w加入到N中,对不在N中的结点,求:D(v)=MinD(v),D(w)+l(w,v) c.重复步骤b,直到所有的网络结点都在N中为止。,Dijkstra算法-最短距离(最小代价)算法 :,分散通信量法(traffic bifurcation)这种方法是事先在每个结点的内存中设置一个路由表,但此路由表中给出几个可
6、供采用的输出链路,并且对每条链路赋予一个概率。,节点G中的路由表,洪泛法(flooding)这种方法是当某个结点收到一个不是发给它的分组时,就向所有与此结点相连的链路转发出去。当然,不能再把这个分组发到它刚刚离开的那个结点,否则就永远有一些分组来回不停地在各条链路上“振荡”。采用两种方法来限制分组数目:一种方法是在每个分组的首部设置一个计数器。每当分组到达一个结点时,计数器即自动加1。当计数器所计的数达到规定值时(如达到端到端所能达到的最大段数),即将此分组丢弃。,另一种方法是在每一个结点建立一个登记表,凡经过此结点的分组均进行登记。当某个分组再次通过该结点时,即将该分组丢弃。随机走动法(ra
7、ndom walk)这种方法又称为随机徘徊,其特点是当分组到达某个结点时就随机地选择一条为转发的路由。,4.自适应路由选择,分布式路由选择策略在分布式路由选择策略中,最基本的算法有两个,即距离向量算法和链路状态算法。下面介绍距离向量算法。每个结点上保持有两个向量:,Di为结点i的时延向量 dij为结点i至结点j的最小时延的当前估值 N为网络中的结点数 Si为结点i的后继结点向量 Sij为结点i至结点j的当前最小时延路由中结点i的后继结点,其中:dkj为结点k至结点i的时延的当前估值A为结点k的所有相邻结点的集合,每个结点定期与它所有相邻结点交换它们的时延向量。然后根据收到的全部时延向量来修改本
8、结点的D与S。对于任一结点k,修改方法如下:,使 为最小,A B C D E F G H I J K L,TO A I H K,延迟 延迟 延迟 延迟 是8 是 10 是12 是6从J的四个邻居收到的向量,新估计的从J的延时线路,J的新路由表,路由器J从其邻居收到距离向量表后计算自己的向量表,分布式路由选择方法的几个要素: 对于网络的某种特性的测量过程。 关于如何传播上述特性的测量结果的协议。 如何计算出所确定的路由。 时延的测量方法:早期ARPANET把在一个结点中向某条链路发送的等待队列中的分组数目再加上一个常数(即偏移)作为此链路的时延。,存在的问题: 当一个分组到达某一个结点时,还需要
9、经过一段处理时间(这时间是可变的)才加入等待队列。 等待队列长度的瞬时值(在测量瞬间得到的值)并不能精确代表链路的平均时延。实际测量结果表明,在高负荷工作下,虽然网络的平均时延很大,但仍还有不少分组具有很小的时延,而有的队列长度有时甚至下降到零。 等待队列的长度仅仅是影响分组的延时许多因素中的一个。仅就这一因素进行测量不能得出精确的结果。,改进方法:不再用队列长度表示时延,而是将时延实际测量出来。当分组到达某个结点时,立即在分组上写入到达时间,即打上时间戳(timestamp)。当该分组发送时,再记录发出时间。发出时间减去到达时间再加上分组的发送时间和传播时间,即得出时延。若收到否认响应,则在
10、重传时将发送时间更新,“时延”是一次成功的发送所经历的时间。路由表的更新: 在新的路由算法中,不再是128 ms更新一次,而是10s更新一次,时延信息采用广播方式传送给其它结点。,集中式路由选择策略网控中心NCC负责全网状态信息的收集、路由计算以及路由选择的实现。优点:各个结点不需要进行路由选择计算,较容易得到更精确的路由最优化,消除了路由不断变来变去的“振荡”现象。还可起到对进入网络的通信量的某种流量控制作用。缺点:一个是距离NCC较近的地方通信量的开销较大,这是因为要周期性地从所有结点收集网络的状态信息的报告,同时还要将路由选择的命令从NCC送到网内的每一个结点。另一个更严重的缺点是可靠性
11、问题,一旦NCC出故障,则整个网络即失去控制。,混合式路由选择策略目前可行的混合式路由选择策略只能是将集中式的和孤立的路由选择策略结合起来。集中式的路由选择策略用来寻找在稳定状态下的最佳路由,然后由NCC将路由表送到每一个结点去。而孤立的路由选择策略则用来提供对局部的拥塞和故障的迅速响应。,1、拥塞控制的意义若对网络中某一资源的需求超过了该资源所能提供的可用部分,网络的性能就要变坏,这种情况就叫做拥塞(congestion)对资源的需求可用资源1)解决网络拥塞是一项系统工程网络拥塞往往是由许多因素引起的.2)拥塞控制与流量控制的关系密切拥塞控制是一个全局性的过程流量控制往往指在给定的发送端和接
12、收端之间的点对点通信量,是一个局部的过程,5.4 拥塞控制,3)进行拥塞控制需要付出代价 4)死锁问题当网络负载继续增大到某一数值时,网络的吞吐量就下降到零,网络已无法工作。这就是所谓的死锁(Deadlock)(1)直接死锁:由互相占用对方需要的资源而造成的死锁(2)重装死锁: 5)拥塞特点当网络负载较小时,有拥塞控制的吞吐量反而比无拥塞控制时要小。,2、拥塞控制的一般原理 1)增大网络的某些可用资源 2)减少一些用户对某些资源的需求 3)开环控制和闭环控制 开环控制方法在设计网络时事先将有关发生拥塞的因素考虑周到,力求网络在工作时不产生拥塞。但一旦整个系统运行起来,就不再中途进行改正了。 闭环控制是基于反馈环路的概念。属于闭环控制的有以下几种措施: 监测网络系统以便检测到拥塞在何时、何处发生。 将拥塞发生的信息传送到可采取行动的地方。 调整网络系统的运行以解决出现的问题。,