《计算机通信与网络》课件第八讲广域网2012

1、广 域 网广域网的基本概念广域网中的分组转发机制路由选择算法拥塞控制广域网的基本概念 当计算机之间的距离较远时，例如，相隔几十或几百公里，甚至几千公里，局域网显然就无法完成计算机之间的通信任务。这时就需要另一种结构的网络，即广域网。 广域网: 包含物理层、链路层和网络层。由局域网和广域网组成互联网 广域网是由一些结点交换机以及连接交换机的链路组成。结点交换机执行分组存储转发的功能。结点之间都是点到点的连接，但为了提高网络的可靠性，通常一个结点交换机往往与多个结点交换机相连。下图表示相距较远的局域网通过路由器与广域网相连，组成了一个覆盖面很广的互连网。广域网的构成网络层的功能路由选择和转发流量控

2、制网络互连分组的分段与重组差错控制顺序化 网络层提供的服务网络层为连接在网络上的主机所提供的服务可以有两大类：无连接的网络服务（数据报服务）面向连接的网络服务（虚电路服务）。 提供数据报服务的特点 H1H5H2H4H3ACDBH6E分组交换网H1 向 H5 发送分组H2 向 H6 发送分组路径可能变化网络随时接收主机发送的分组（即数据报）网络为每个分组独立地选择路由。 E.1E.2E.3C.1C.3C.2提供数据报服务的特点 H1H5H2H4H3ACDBH6E分组交换网网络尽最大努力地将分组交付给目的主机，但网络对源主机没有任何承诺。提供数据报服务的特点 H1H5H2H4H3ACDBH6E分组

3、交换网网络不保证所传送的分组不丢失也不保证按源主机发送分组的先后顺序以及在时限内必须将分组交付给目的主机 提供数据报服务的特点 H1H5H2H4H3ACDBH6E分组交换网当网络发生拥塞时网络中的结点可根据情况将一些分组丢弃 提供数据报服务的特点 H1H5H2H4H3ACDBH6E分组交换网数据报提供的服务是不可靠的，它不能保证服务质量。实际上“尽最大努力交付”的服务就是没有质量保证的服务。 2022/7/122022/7/122022/7/122022/7/12两种服务的思路来源不同 虚电路服务的思路来源于传统的电信网。电信网负责保证可靠通信的一切措施，因此电信网的结点交换机复杂而昂贵。数据

4、报服务力求使网络生存性好和使对网络的控制功能分散，因而只能要求网络提供尽最大努力的服务, 这种网络要使用较复杂且有相当智能的主机作为用户终端。可靠通信由用户终端中的软件（即TCP）来保证。 数据报服务与虚电路服务之争 让网络只提供数据报服务就可大大简化网络层的结构。 但技术的进步使得网络出错的概率已越来越小，因而让主机负责端到端的可靠性不但不会给主机增加更多的负担，反而能够使更多的应用在这种简单的网络上运行。因特网发展到今天的规模，充分说明了在网络层提供数据报服务是非常成功的。 网络上传送的报文长度，在很多情况下都很短。用数据报既迅速又经济。若用虚电路，为了传送一个分组而建立虚电路和释放虚电路

5、就显得太浪费网络资源了。 数据报服务和虚电路服务都各有一些优缺点 在使用数据报时，每个分组必须携带完整的地址信息。在使用虚电路的情况下，每个分组不需要携带完整的目的地址，而仅需要有个很简单的虚电路号码的标志。这就使分组的控制信息部分的比特数减少，因而减少了额外开销。 数据报服务和虚电路服务都各有一些优缺点 在使用数据报时，主机承担端到端的差错控制和流量控制。在使用虚电路时，分组按顺序交付，网络可以负责差错控制和流量控制。 数据报服务和虚电路服务都各有一些优缺点 数据报服务对军事通信有其特殊的意义。当某个结点发生故障时，后续的分组就可另选路由，因而提高了可靠性。但在使用虚电路时，结点发生故障就必

6、须重新建立另一条虚电路。 数据报服务还很适合于将一个分组发送到多个地址(即广播或多播)。 数据报服务和虚电路服务都各有一些优缺点 虚电路与数据报的比较表 数据报 虚电路是否需要建立连接 不需要需要分组中的目的地址完整地址VC标识路由器中的路由表 只需一个很简单 的路由表要为每个虚电路保存一个路由表 选路每个分组独立选路，路由可能不同 在VC建立时选路， 所有分组路由相同几乎不受影响所有经过该路由器的VC都将终止分组的顺序总是按发送顺序到达目的站到达目的站可能不按发送顺序路由器故障的影响差错控制和流量控制由主机负责由子网负责广 域 网广域网的基本概念广域网中的分组转发机制路由选择算法拥塞控制X.

7、25帧中继广域网中的分组转发机制层次结构的地址结构 广域网中一般都采用层次地址结构(hierarchical addressing)。 最简单的层次结构地址举例 用二进制数表示的主机地址划分为前后两部分。前一部分的二进制数表示该主机所连接的分组交换机的编号。后一部分的二进制数表示所连接的分组交换机的端口号，或主机的编号。 所连接的交换机的编号所连接的交换机端口的编号计算机在广域网中的地址2, 1 2, 2456745674 5 6 7交换机1交换机 2交换机31, 11, 33, 23, 3每个交换机都有两组端口。一组是和本地主机相连的低速端口，另一组是和其他交换机相连的高速端口。123123

8、1 2 32, 1 2, 245674567交换机 2交换机31, 13, 23, 3每个主机地址中后面的数字是指该交换机的低速端口主机地址3, 2是指连接在交换机 3 的 2 号低速端口交换机11, 3主机地址1, 3是指连接在交换机 1 的 3 号低速端口1231234 5 6 71 2 32022/7/122022/7/122022/7/122022/7/122022/7/12按照目的站连接的交换机号确定下一跳 只要转发表中目的站一栏中的交换机号相同，那么查出的“下一跳”就是相同的。 在转发分组时，可只根据分组的主机地址中的交换机号来查找转发表。只有当分组到达与目的主机相连的结点交换机时

9、，交换机才检查第二部分地址（主机号），并通过合适的低速端口将分组交给目的主机。 目的站 下一跳 1, 1 交换机1 1, 3 交换机1 3, 2 交换机3 3, 3 交换机3 2, 1 直接 2, 2 直接目的站 下一跳 1,* 交换机1 3,* 交换机3 2, * 直接 采用层次编址优化图的应用可用图论中的“图(graph)”来表示整个广域网。用“结点”表示广域网上的结点交换机，用连接结点与结点的“边”表示广域网中的链路。连接在结点交换机上的主机与分组转发无关，因此在图中可以不画上。 2022/7/122022/7/122022/7/122022/7/122022/7/122022/7/12

10、2022/7/12虚电路的路由表 为使节点能区分一个分组属于哪条虚电路，每个分组必须携带一个逻辑信道号;同样，同一条 虚电路的分组在各段逻辑信道上的逻辑信道号可能也不相同。传输中，当一个分组到达节点时，节点根据其携带的逻辑信道号查找虚电路表，以确定该分组应发往的下一个节点及其下一段信道上所占用的逻辑信道号，用该逻辑信道号替换分组中原先的逻辑信道号后，再将该分组发往下一个节点。 路由表在建立虚电路（虚呼叫）时确定。分组在传送时只需携带虚电路号，虚电路号只具有本地意义，根据虚电路建立顺序由各主机、各结点自主排序，入出口号不一定相同。虚电路路由表建立过程示例AEDCBH2H3H1H4H5依次建立5条

11、VC：VC1：A-B-EVC2：A-B-DVC3：B-D-EVC4：C-E-DVC5：A-B-C-D 入口出口H1H1H1125012B012BB 入口出口AAH2 3010E001DD 入口出口BBE010H4001EH4 入口出口H3B4000E002D 入口出口BDC000H5010D A B C D EA2C0H5CH412路由选择过程就是填上交换表，以后数据发送只需要携带VC号。VC5：H1-A-B-CDH4广 域 网广域网的基本概念广域网中的分组转发机制路由选择算法拥塞控制路由选择算法 路由选择算法的特点正确和完整计算简单自适应性 稳定性公平 最佳 路由选择算法的特点 1 算法必须

12、是正确和完整的 每一个结点交换机中的路由表，都必须给出到所有可能的目的站的下一站应怎样走，并且，所给出的走法应是正确的。 正确是指:沿着各交换机中路由表所指引的路由，分组一定能够最终到达目的计算机所在的交换机，并且该交换机可以根据自己的路由表识别出目的计算机直接与自己相连，而不会再向其他交换机转发该分组。路由选择算法的特点2 算法在计算上应简单 由于在每个结点上都要进行路由选择的计算，因此必然要增加分组的时延，计算简单可以使时延增加的不多。 路由选择的计算不应使网络的通信量增加太多的额外开销。如果为了计算合适的路由必须使用网络其它结点发来的大量状态信息时，额外开销就会较大。 3 算法的自适应性

13、 当网络中的通信量发生变化时，算法能自适应地改变路由。 当某个或某些结点、链路发生故障不能工作，或者修好了再投入运行时，算法也能及时地改变路由。有时称这种自适应性为“健壮性”。 路由选择算法的特点4 算法应具有稳定性 当通信量和网络拓扑发生变化时，路由算法应收敛于一个可以接受的解，而不应产生过多的振荡。所谓“振荡”，就是指由算法得出的路由是在一些路由之间来回不停地变化。 路由选择算法的特点5 算法应是公平的 这就是说，算法应对所有用户（除对少数优先级高的用户）都是平等的。例如，若使某一对用户端到端的时延最小，但却不考虑其它的广大用户，这都明显地不符合公平性的要求。路由选择算法的特点6 算法应是

14、最佳的 这里的“最佳”是指以最低的费用来实现路由算法。需要强调的是，“费用”这个词并非指“钱”，而是包括链路长 度、数据率、链路容量、传播时延、保密性、差错率等许多因素。从这里可以看出，不存在一种绝对最佳的算法。所谓“最佳”只能是在某种 特定要求下的较为合理的选择。 一个实际的路由选择算法，应尽可能接近于理想算法。在不同的应用条件下，对以上提出的六个方面也可以有不同的侧重。 路由选择算法的特点路由选择算法 分类： 非自适应路由算法（静态路由） 固定路由法洪泛法分散通信量法随机走动法 距离矢量路由选择 链路状态路由选择自适应路由算法 （动态路由）非自适应路由选择1 固定路由法 这种方法是在每个结

15、点上保持一张表，表上标明对每一个目的地址应当走哪条链路进行转发。这些表是在整个系统进行配置时生成的，并且在此后相当的一段时间里固定不变。当网络拓扑固定不变且通信量也相对稳定时，采用固定路由法时是最好的。非自适应路由选择固定路由法中路由表的制作 常用的方法是将网络内任何两个结点之间的最短通路事先计算好，然后根据这些最短通路制成路由表，存放在各个结点中。每个分组都可以在所到达的结点中查找到下一步应转发到哪一个结点。 这种路由选择策略的关键是要算出给定网络中任意两个结点之间的最短通路。最短通路算法: Dijkstra算法已知条件: 整个网络拓扑和各链路的长度。目的：求从源结点到网络中其他各结点的最短

16、路径。 1453212622535311注意: 最短通路的概念。 测量路径长度方法:站点数 也可采用其他的度量法。例如:每条链路都标上用一个标准测试分组每小时或每天测试运行所得的平均队列长和传输时延来标识。此时，最短路径也就是最快路径。 在大多数通用情况下，链路的标注可以是距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延和其他一些因素的函数计算出来。令D(v)为源结点(1)到结点v的距离，它就是沿某一通路的所有链路的长度之和。再令l(i ,j) 为i到j的距离。(1)初始化 令N表示网络结点的集合。先令N=1。对所有不在N中的结点v, 写出: D(v)= l(1,v) 结点v和

17、结点1直接相连 结点v和结点1不直接相连1453212622535311 以下图为例，讨论这种算法，即寻找从源结点到网络中其他结点的最短通路。为方便起见，设源结点为结点1，然后一步一步地寻找，每次找一个结点到源结点的最短通路，直到把所有的点都找到为止。(2)寻找一个不在N中的结点w,其D(w)值为最小。把w加入到N中。然后对所有不在N中的结点，用D(v),D(w)+l(w,v)中的较小的值去更新原有的D(v)值，即: D(v) Min D(v),D(w)+l(w,v)(3) 重复步骤(2), 直到所有的网络结点都在N中为止。 步骤2共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找

18、的最小值的D(w)值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N之中，整个算法结束。1453212622535311 最后就得出以结点1为根的最短通路树(左下图)。从最短通路树可看出源结点(1)到网内任何一个结点的最短通路。图中括号表示在第几步算法加入到集合N中的。初始化为第0步。 右下图中，画的是在结点1的内存中的路由表。145321262(3)(5)11(0)(4)以结点1为根的最短通路数结点1的路由表(1)(2) 事先在每个结点的内存中设置一个路由表，路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率。当一个分组到达该结点时， 此结点即产生一个从0.00到

19、0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。结点K中的路由ABCDEKMNLP目的站ABCDE经过概率经过概率概率经过MMNNP0.500.350.650.550.45LNMPNNLPMM0.400.350.250.300.300.100.300.100.150.25 这种方法和固定路由相比，可使网内的通信量更加平衡，因而可得到较小的平均分组时延。 2 分散通信量法 3 洪泛法 这种方法是当某个结点收到一个不是发给它的分组时，就向所有与此结点相连的链路转发出去。当然，不能再把这个分组发回它刚刚离开的那个结点，否则就永远有一些分组来回不停地在各条链路上振荡。当网络的通信量很小

20、时，洪泛法可使分组的时延为最小。此外，在许多条并行发送的路由中，显然有一条是最佳的。 在实际运行的网络中却很少采用洪泛法。这是因为采用洪泛法后，网络中的分组数目会迅速增长，结果导致网络出现拥塞现象。 1 在每个分组的首部中设置一个计数器，当分组到达一个结点时，计数器即自动加1。当计数器所计的数达到规定值时，即将此分组丢弃。 2 是在每一个结点建立一个登记表，凡经过此结点的分组都进行登记。当某个分组再次经过这个结点时，就将其丢弃。当然，这样付出的代价是各结点都要占去不少的存储空间。建立登记表的方法可以有效地防止分组在网内无限制地循环， 这种方法在其它路由选择方法中也是很有用的。 洪泛法在军用网中

21、是很有用的，因为它有很好的健壮性。 限制分组数目的方法洪泛法 适用情况：网络中通信量较小时 优点：简单、健壮、可能是最佳路由 缺点：网络中分组数目剧增，极易导致拥塞 改进：有选择的洪泛法，限制分组的转发方向4 随机走动法 特点:是当分组到达某个结点时就随机地选择一条链路作为转发的路由。例如，分组到达某结点后，可供转发的输出链路共有3 条，那么就以平均概率0.33选择任一条链路作为其转发的路由。 在非自适应的路 由选择策略中，若可能发生结点或链路的故障，那么随机走动法已被证明是非常 有效的，它使得路由算法具有较好的健壮性。 适用情况：可能发生结点或链路故障时 优点：健壮 缺点：不保证最佳路由自适

22、应路由选择算法自适应可以有几种不同的解释: 从时间上考虑，即在某个时候根据当时网络 的运行情况调整路由，例如，当网络拓扑发生变化，或在网络某个结点或链路发生故障时，也可以是每隔一段固定的时间等等。 从空间上考虑，即在网络的某个局部范围做出调整路由的决定，或在调整路由时所根据的某些网络状态信息是来自网络的某个局部范围。根据这种考虑，自适应路由选择可划分为以下三种： 分布式路由选择策略 集中式路由选择策略 混合式路由选择策略1 分布式路由选择策略 这种路由选择策略是每个结点周期性地从相邻的结点获得网络状态信息， 同时也将本结点做出的决定周期性地通知周围的各结点，以使这些结点不断地 根据网络新的状态

23、更新其路由选择决定。所以整个网络的路由选择经常处于一 种动态变化的状况。各个结点的路由表相互作用，是这种策略的特点。当网络状态发生变化时，必然会影响到许多结点的路由表，因此，要经过一定的时间以后，各路由表中的数据才能达到稳定的数值。 在分布式路由选择策略中，最基本的算法有两个:即 距离矢量路由选择(RIP协议) 链路状态路由选择(开放最短通路优先协议OSPF)算法: 在每一个结点上保持两个向量，即 di1 si1 Di= Si= diN siN 距离矢量路由选择其中: Di 为结点i的时延向量; dij 为结点i至j的最小时延的当前估值(dii=0) (j=1,.，N) N为网络中的结点数;

24、Si为结点i的后继结点向量; sij为后继结点(j=1,.，N),即从结点i到结点j的当前最小时延路由中结点i的后继结点。 每个结点每隔128ms与它的所有相邻结点交换它们的时延向量。然后根据收到的全部时延向量来修改本结点的时延向量和后继结点向量。dkj=Min dki+dij skj=i,dki 为结点k到结点i的时延的当前估值。iAA为结点k 的所有相邻结点的集合;例如:5145321262235311更新前结点1的路由表D1S1对于任一结点k, 可按以下方法进行两个向量的修改:结点1收到的3个时延向量结点1更新后的路由表 假定经过了128ms,结点1收到了来自3个相邻结点(2,3,4)的

25、时延向量D2,D3,D4, 于是进行更新运算，得出了更新后的路由表。 以d13=3,s13=4为例。 从结点1经不同结点到结点3的时延分别为: : d12+d23=2+3=5 : d13+d33=5+0=5 : d14+d43=1+2=3 D1S1145321262235311123456更新前结点1的路由表D1S1无穷计算问题(1) 对好消息反映迅速 考虑有一个路由器，它到目的地X的最佳路由也很长，如果在某次交换信息时，它的邻居A忽然报告说有一个到X的更短的延迟，即增加了新电路，使该路由器到X的距离更短，那么该路由器仅需简单地将输出到X的通信量转移到A上。在一次矢量交换中，好消息起了作用。考

26、虑一个5个节点的线性子网ABCDE初始时1第1次交换后1 2第2次交换后1 23第3次交换后1 234第4次交换后 为了简化问题，我们假设有一个定时器定期使所有路由器同时初始化矢量交换。新增加结点A 很明显，好消息的传播正常是每交换一次前进一个节点。在一个最长路径为N个节点的子网中，在N次交换内，所有路由器都会知道新增加的线路和路由器。无穷计算问题(2) 对坏消息反映迟钝 开始时，所有的线路和路由器都在网上。 忽然，A下网了。在第一次分组交换时，B没有从A处得到任何信息。所幸的是，C说:“别担心，我还有一条到A的长度为2的路径。”B并不知道C的路径还要经过B本身。B会想，C可能有多条独立的长度

27、为2的路径通往A。结果，B认为它能通过C到达A,路径长度为3。第一次交换中D和E并不更新其对应于A的表项。 第二次交换时，C注意到它所有的邻居都声称有一条通往A的长度为3的路径。它随意选择任意一个邻居，并将到A的距离设为4,如下图。ABCDE1234初始时3234第1次交换后3 434第2次交换后5 454第3次交换后5 656第4次交换后7 676第5次交换后7 878第6次交换后链路AB故障2 集中式路由选择策略 集中式路由选择策略的核心是网控中心NCC。NCC负责全网状态信息的收集、 路由计算以及路由选择的实现。 集中式路由选择策略的最大好处是各个结点不需要进行路由选择的计算。 由于是集

28、中在NCC计算路由，所以容易得到更精确的路由最优化，同时还消除了分组在网内“兜圈子”以及路由“振荡”的的现象，而这些问题在网络状态不太 明确时最容易发生。 集中式路由选择策略还可起到对进入网络的通信量的某种流量控制作用。这一点使得集中式路由选择策略很有吸引力。在分布式控制的网络，流量控制是很难实现的。 集中式路由选择策略存在两个较严重的缺点: 1 离NCC较近的地方通信量的开支较大。这是因为要周期性地从所有结点收集网络的状态信息 的报告，同时还要将路由选择的命令从NCC送到网内的每一个结点。 2 可靠性问题。一旦NCC出故障，整个网络将失去控制。为了解决这一 问题，可按不同等级设置若干个NCC

29、，它们彼此不间断地互相监督。当高级别的 NCC出故障时，比它低一级的NCC马上接替工作。用这种方法开销较大，并且仍会 产生一些问题。在军事环境下，NCC显然是个非常容易受到打击的目标。 为了克服集中式路由选择的缺点，可以同时综合使用几种路由选择策略。3 混合式路由选择策略 从原则上讲，在一个网络中可以将一些不同类型的路由选择策略混合。这样只要在每一个结点明确定义出：对于何种类型的通信量、负荷以及网络的连通条 件，应当采用何种路由选择策略。 集中式的路 由选择策略用来寻找在稳定状态下的最佳路由，然后由NCC将路由表送到每一个 结点去。而孤立的路由选择策略则用来提供对局部的拥塞和故障的迅速响应。这

30、种响应只是暂时的，因而并不要求很精确。不需要很长时间NCC就会发现通信量以及网络拓扑的变化情况，于是就对路由表进行更新。 分级路由选择 随着网络的增大，路由器路由选择表也会成比例地增大。增大的表格不仅占用路由器的内存，而且需要更多的CPU时间扫描表格，以及更大的带宽来发送关于表格的状态报告。在某一时刻，网络可能会增大到不可能让每一个路由器都给出至其他每一个路由器的路径表项。因此，就像在电话网络中一样，不得不进行分级路由选择。 当采用分级路由选择时，将路由器划分为区域，每个路由器知道在自己的区域内怎样选择路由，将分组送到目的端的全部细节，但并不知道其他区域的内部结构。当不同的网络相连时，很自然地

31、将每个网络看作为独立的区域，以便让一个网络中的路由器免于必须知道其他网络的拓扑结构。 图1中给出了有5个区域的两级结构中作路由选择的一个定量分析的例子。区域1区域2区域3区域4区域54B1B1C2A2B2C2D3A3B4A1A4C5A5B5C5D5E1A的完整表目的线路站段数1B1A1B1C1C1B1B1B1B2A2B2C2D3A3B4A4B4C5A5B5C5D5E1B1C1C1C1C1C1C1C1C1C 1 1 2 3 3 4 3 2 3 4 4 4 5 5 6 51A的分层表目的线路站段数1A1B1C 2 2 23 4 51B1B1C1C1C 1 1 3 41C到区域2的所有通信量都经过1

32、B-2A的线路，其余的远程通信量都经过1C-3B的线路。分级路由选择将表项从17个减到7个。当区域数与区域中路由器的比例增大时，节省的表格存储空间也会按比例增长。2022/7/12广 域 网广域网的基本概念广域网中的分组转发机制路由选择算法拥塞控制拥塞控制一、拥塞控制的基本概念: 在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。这种情况叫做拥塞。 若网络中的许多资源同时产生拥塞，网络的性能就要明显变差，整个网络的吞吐量将随输入负载的增大而下降。对资源的需求 可用资源2022/7/12有人认为任意增加一些资源，如 : 扩大节点缓冲区的存储空间 提高链路的速

33、率 提高节点处理机的运算速度这样做就可以解决拥塞问题吗？网络拥塞往往是由许多因素引起的。 例如，当某个节点缓冲区的容量太小时，到达该节点的分组因无空间暂存而不得不被丢弃。此时若将该节点缓冲区的容量扩展到非常大。于是凡到达该节点的分组均可在这缓冲区中排队，不受任何限制。由于输出链路的容量和处理机的速度并未提高，因此在这队列中的绝大多数分组的排队等待时间将会很长很长，结果上层软件只好将其进行重传。由此可见，简单地扩大缓冲区的存储空间解决不了网络拥塞的问题。 又如， 处理机处理的速度太慢固然可能引起网络的拥塞。如某个路由器的CPU运行太慢，使得缓冲区中的队列变得很长，即使线路的容量还很富裕。简单地将处理机的速率提高，可能会使上述情况缓解一些，但往往又将瓶颈转移到其他的地方。 问题的实质是: 整个系统的各个部分不匹配。