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