计算机网络-广域网

1、2022-4-16CN-Chapter61第六章 广域网Wide Area NetworkCOURSE2022-4-16CN-Chapter626 广域网广域网的主要问题都在网络层。网络层：从源到目的传送分组，因此=网络层的设计要点：向上层提供服务；路由选择；拥塞控制；网络互连。本章：广域网概念；路由选择；拥塞控制。2022-4-16CN-Chapter636 广域网本章内容：广域网概念；路由选择；拥塞控制；简介X.25和Frame Relay。2022-4-16CN-Chapter646 广域网6.1 广域网的基本概念6.2 路由选择机制6.3 路由选择的一般原理6.4 拥塞控制6.5 X.

2、25简介6.6 帧中继简介2022-4-16CN-Chapter656.1 广域网的基本概念广域网：跨越大的区域的计算机网络。一、广域网的构成：节点交换机（或Routers)；节点之间的链路。广域网和局域网都是互连网的重要构件。从互连网的角度看，它们是平等的。2022-4-16CN-Chapter666.1 广域网的基本概念WAN2022-4-16CN-Chapter676.1 广域网的基本概念二、广域网提供的服务提供的服务：无连接的网络服务；=数据报面向连接的网络服务。=虚电路数据报Datagram每个分组可以独立地选择路由。虚电路Virtual Circuit沿虚电路进行通行。2022-4

3、-16CN-Chapter686.1 广域网的基本概念Virtual circuitdatagram2022-4-16CN-Chapter696.1 广域网的基本概念注意与实电路的区别。虚电路与数据报的区别 虚电路就像数字管道，顺序发送，顺序接收；分组到达目的站的顺序与发送时的顺序完全一致。数据报没有呼叫建立过程，不能保证按发送顺序交付目的站。2022-4-16CN-Chapter6106.1 广域网的基本概念2022-4-16CN-Chapter6116.1 广域网的基本概念虚电路与数据报的对比2022-4-16CN-Chapter6126.2 路由选择机制基本思想：基于查表（路由表）。一、

4、节点交换机（路由器）中的路由表路由涉及到对计算机的编址。因此先学习一种地址方案。层次编址方案地址有两部分组成：前部分为交换机；后部分为连接在交换机上的计算机。2022-4-16CN-Chapter6136.2 路由选择机制交换机1交换机2交换机31, 31, 12, 12, 23, 23, 3目的站 下一站1, 1 交换机1 1, 3 交换机1 3, 2 交换机33, 3 交换机32, 1 本交换机2, 2 本交换机路由表2022-4-16CN-Chapter6146.2 路由选择机制节点交换机的一个重要作用：提供一个路由表，供转发分组时用。路由表中的重要内容：目的站；下一站。路由选择中的下一

5、站：只取决于数据报中的目的站地址，与源站地址无关。2022-4-16CN-Chapter6156.2 路由选择机制把“目的站”换成“目的站的交换机号”，路由表还可以简化(例如前图中的交换机2中的路由表）。这时，分组转发时只用第一部分地址，到了目的交换机时，才检查第二部分地址。目的站下一站 1 交换机1 2 交换机3 3 本交换机2022-4-16CN-Chapter6166.2 路由选择机制二、用图表示广域网图Graph：节点表示交换机；节点之间的边表示链路。341213422022-4-16CN-Chapter6176.2 路由选择机制上图每个节点的路由表：目的站 下一站 1 - 2 3 3

6、 3 4 3节点1路由表目的站 下一站 1 3 2 - 3 3 4 4节点2路由表目的站 下一站 1 1 2 2 3 - 4 4节点3路由表目的站 下一站 1 3 2 2 3 3 4 -节点4路由表2022-4-16CN-Chapter6186.2 路由选择机制利用默认路由代替相同的下一站后：目的站 下一站 1 - * 3 节点1路由表目的站 下一站 2 - 4 4 * 3 节点2路由表目的站 下一站 1 1 2 2 3 - 4 4节点3路由表目的站 下一站 2 2 4 - * 3 节点4路由表2022-4-16CN-Chapter6196.2 路由选择机制问题：如何生成这些路由表？=路由算法

7、。2022-4-16CN-Chapter6206.3 路由选择的一般原理理想的路由算法非自适应路由选择固定路由法分散通信量法洪泛法随机走动法自适应路由选择分布式路由选择策略集中式路由选择策略2022-4-16CN-Chapter6216.3.1理想的路由算法算法必须是正确的和完整的。算法在计算上应简单。尽量减少时延，不应使网络的通信量增加太多的额外开销。算法应能适应通信量和网络拓扑的变化（自适应性）。算法应具有稳定性。不应产生过多的振荡。所谓“振荡”就是指由算法得出的路由是在一些路由之间来回不停地变化。2022-4-16CN-Chapter6226.3.1理想的路由算法算法应是公平的。算法应是

8、最佳的。以最低的费用，不存在一种绝对的最佳路由算法。算法分类（按是否能够随网络的通信量或拓扑进行调整）：非自适应路由选择自适应路由选择2022-4-16CN-Chapter6236.3.2非自适应路由选择是一种静态的路由选择策略。固定路由法（最短通路法）已知整个网络拓扑和各链路的长度（或链路延迟、或费用），求给定网络中两个结点之间的最短通路。2022-4-16CN-Chapter6246.3.2非自适应路由选择算法：中为止。点都在），直到所有的网络结）重复步骤（值，即：原有的中的较小的值去更新中的结点，用然后对所有不在中。加入到值为最小。把，其中的结点）寻找一个不在（直接相连与结点若结点不直接

9、相连与结点若结点写出中的结点。对所有不在先令表示网络结点的集合。令）初始化（算法如下：之间的距离。至结点为结点再令的集合。的所有链路的长度之和通路的距离，它就是沿某一）到结点为源结点（结点令NvwlwDvDvDvDvwlvDvDNNwwDwNvvlvvDvNNNjijilvvD23),()(),(min)()(),()(),()(21), 1(1,)(,11),(1)(2022-4-16CN-Chapter6256.3.2非自适应路由选择示例：2022-4-16CN-Chapter6266.3.2非自适应路由选择2022-4-16CN-Chapter6276.3.2非自适应路由选择2022-4

10、-16CN-Chapter6286.3.2非自适应路由选择2. 分散通信量法(traffic bifurcation)原理：事先在每个结点的内存中设置一个路由表。路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率。当一个分组到达该结点时，此结点即产生一个从0.00到0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。2022-4-16CN-Chapter6296.3.2非自适应路由选择2022-4-16CN-Chapter6306.3.2非自适应路由选择3. 洪泛法(Flooding)原理：当某个节点收到一个不是发给它的分组时，就向所有与此节点相连的链路传发出去。=会有

11、一条路由是最佳的。特点：可靠性或鲁棒性好，在军网中有应用价值；无需路由表；2022-4-16CN-Chapter6316.3.2非自适应路由选择算法简单，处理延迟小；缺点分组副本多，降低了网络利用率；易导致拥塞现象。思考：如何限制分组的数目？2022-4-16CN-Chapter6326.3.2非自适应路由选择4. 随机走动法原理：当分组到达某个结点时就随机地选择一条链路作为转发的路由。相当于以平均概率选择一条转发路由。特点：具有较好的鲁棒性。计算简单，不需路由表。2022-4-16CN-Chapter6336.3.3 自适应路由选择从时间上：在某个时刻根据当时的情况（拓扑结构变化、节点或链路

12、故障）调整路由。从空间上：在网络的某个局部范围做出调整路由的决定，或在调整路由时，所根据的某些网络状态信息是来自网络的某个局部范围。2022-4-16CN-Chapter6346.3.3自适应路由选择1. 分布式路由选择策略策略：每个节点周期性地从相邻的节点获得网络状态信息，同时也将本节点做出的决定周期性地通知周围的各节点，以使这些节点不断地根据网络的新状态更新路由表。介绍距离向量算法（distance vector)2022-4-16CN-Chapter6356.3.3自适应路由选择距离向量算法：（1）在每个节点上保持两个向量：Di：节点i的时延向量；Si：节点i的后继节点向量。iNiiiN

13、iissSddD. ,1.12022-4-16CN-Chapter6366.3.3自适应路由选择距离向量算法：N为网络的节点数；dij为节点i到节点j的最小时延的当前估值（dii=0)(j = 1, , N)；sij为节点i的后继节点（j=1,N)。(2) 每个节点每隔128ms与它的所有相邻节点交换它们的时延向量。(3) 根据收到的全部时延向量来修改本节点的时延向量和后继节点向量：2022-4-16CN-Chapter6376.3.3自适应路由选择距离向量算法：其中：A为节点k的所有相邻节点的集合； dki为节点k到节点i的时延的当前估值。为最小使用这个 ,minijkikjijkiAikj

14、ddiisddd2022-4-16CN-Chapter6386.3.3自适应路由选择距离向量算法示例：目的节点 延迟 下一站节点 1 0 - 2 2 2 3 5 3 4 1 4 5 6 3 6 8 3 D1 S1节点1的路由表2022-4-16CN-Chapter6396.3.3自适应路由选择距离向量算法示例：目的节点 延迟 下一站节点 1 0 - 2 2 2 3 3 4 4 1 4 5 2 4 6 4 4203235330213122013D2D3D4 D1 S1节点1收到的3个时延矢量更新后的路由表2022-4-16CN-Chapter6406.3.3自适应路由选择分布式路由算法的三个要素

15、：网络的某种特性的测量过程；如何传播上述特性的测量结果的协议；如何计算出所确定的路由。改进：新的时延度量：时间戳方法时间测量时延。10s钟更新一次；时延信息的广播。2022-4-16CN-Chapter6416.3.3自适应路由选择2. 集中式路由选择策略思想：设置网控中心NCC。NCC负责全网状态信息的收集、路由计算以及路由选择的实现。特点：各节点不需要进行路由选择计算，系统整体考虑路由的优化。对接入网络的通信量的控制进行整体考虑。2022-4-16CN-Chapter6426.3.3自适应路由选择缺点离NCC较近的地方通信量的开销较大。可靠性问题。在军事环境下，NCC是个弱点。3. 混合式

16、路由选择策略对于相应类型的通信量、负荷以及网络的连同情况，采取不同的路由策略。2022-4-16CN-Chapter6436.4 拥塞控制什么是拥塞？拥塞控制与流量控制？拥塞控制的一般原理？2022-4-16CN-Chapter6446.4.1 拥塞控制的意义1. 什么是拥塞？网络的资源：链路的容量、交换节点中的缓冲区和处理器能力。在某段时间，如果对网络中某一资源的需求超过了该资源所能够提供的可用部分，网络的性能变坏，这种情况就叫拥塞(congestion)。2022-4-16CN-Chapter6456.4.1 拥塞控制的意义拥塞发生的条件：对资源的需求 可用资源=需要拥塞控制。拥塞控制并不

17、能通过单纯地增加资源来解决。单独地增加资源，往往会把瓶颈转移到其它的地方。问题的实质是：整个系统的各个部分不匹配。需要一个总体平衡方案。2022-4-16CN-Chapter6466.4.1 拥塞控制的意义2. 拥塞控制与流控制相关但是有区别：拥塞控制的前提：网络能够承受的网络负荷。它是一个全局性的过程，涉及到所有的主机、路由器、以及与降低网络传输性能有关的所有因素。流量控制：使发送端的发送速率不要使接收端来不及接收。通过收发两方的反馈和交互来实现流量控制。2022-4-16CN-Chapter6476.4.1 拥塞控制的意义举例流量控制的问题：链路1000Gbps；巨型机以1Gbps速率向P

18、C传文件。拥塞问题：链路1Mbps；1000台大型机在网络上；500台向其余的500台以100kbps传送文件。拥塞控制需要代价：获取网络内部的了流量分布情况，产生额外的开销。2022-4-16CN-Chapter6486.4.1 拥塞控制的意义3. 网络输入负荷和吞吐量的分析理想情况在吞吐量饱和之前，网络吞吐量等于网络负荷。但网络负荷超过某一限度，吞吐量不再增长。实际情况轻度拥塞：网络的吞吐量明显小于理想的吞吐量时。2022-4-16CN-Chapter6496.4.1 拥塞控制的意义吞吐量输入负荷拥塞轻度拥塞2022-4-16CN-Chapter6506.4.1 拥塞控制的意义拥塞：当网络

19、负荷达到一定值，网络的吞吐量反而随网络的负荷的增加而下降。死锁：当网络负荷达到一定值，网络的吞吐量下降到零。网络无法工作。死锁直接死锁：互相占用了对方的资源。重装死锁：路由器的缓冲区的拥塞。2022-4-16CN-Chapter6516.4.1 拥塞控制的意义C3 C2 B4 A3A4 A2 A1B3 B2 C1 B1路由器P路由器R路由器Q路由器路由器直接死锁重装死锁2022-4-16CN-Chapter6526.4.1 拥塞控制的意义无拥塞控制时：当网络负荷较小时，有拥塞控制的吞吐量反而比无拥塞控制时要小。网络性能恶化有时是由于网络的资源被浪费。例如浪费信道的容量、节点的存储空间等。这样造

20、成吞吐量的下降。2022-4-16CN-Chapter6536.4.2 拥塞控制的一般原理原理：寻找使不等式不成立的条件。对资源的需求 可用资源增加可用资源（链路、带宽）减少用户对资源的需求（拒绝新的连接请求；要求用户减轻其负荷等）实际中非常难以设计，因为这是一个动态的问题。2022-4-16CN-Chapter6546.4.2 拥塞控制的一般原理方法：开环控制：在设计网络时就考虑拥塞问题，一旦系统远行，不再更改。闭环控制：基于反馈环路的思想。监测网络以监测到拥塞在何时、何处发生；将拥塞发生的信息送到可采取行动的地方；调整网络的运行。2022-4-16CN-Chapter6556.4.2 拥塞

21、控制的一般原理拥塞的监测方法：由于缺少缓冲空间而被丢弃的分组百分数；平均队列长度；超时重传的分组数；平均分组时延；分组时延的标准差。2022-4-16CN-Chapter6566.5 X.25简介1976年，CCITT的标准。X.25只是一个对公用分组交换网的接口的规范。不涉及网络内部应该做成什么样子。X.25网是指该网络与网络外部DTE的接口是遵循X.25标准。不同厂家的X.25网，具体实现有很大差别。以虚电路服务（呼叫和永久VC）为基础。2022-4-16CN-Chapter6576.5 X.25简介三个层次物理层：接口标准采用X.21建议书；数据链路层：LAPB（平衡型链路接入规程）分组层2022-4-16CN-Chapter6586.5 X.25简介2022-4-16CN-Chapter6596.6 帧中继简介需求：提供高速分组服务。帧中继替代X.25。X.25的考虑：网络发展初期，网络传输设施基本是模拟电话线，误码率高。因此X.25采取的措施是：在数据链路层，用LAPB保障帧在节点间无差错传输。