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

第五章 广域网 1.广域网的构成 5.1 广域网的基本概念 wan 2 wan 4 wan 3 wan 1 左图所示的广域网 中，云图中及云图相连 的部分称之为通信子网 ，以外的部分为资源子 网。通信子网提供的是 数据传输服务， 它实 现osi体系结构中的底 三层，即物理层、数据 链路层和网络层。 通信距离：几十或几百公里，甚至几千公里以上。 网络构成：由一些结点交换机及连接这些交换机的 链路组成。结点交换机执行存储转发功能。 所在层次：广域网使用协议在网络层。局域网使用 的协议在数据链路层。 网络互联：局域网通过路由器与广域网相连，构成 全球互连网。 研究重点：路由选择 2.网络层提供的服务 无连接的网络服务数据报服务； 面向连接的网络服务虚电路服务。 1）数据报服务（datagram）：主机只要想发送数据 就随时可发送，每个分组独立地选择路由。 2）虚电路服务（virtual circuit）：通信前主机要先 建立一条虚电路，之后数据沿固定路由传送，通 信后拆除虚电路。 （a）数据报服务 （b）虚电路服务 数据报和虚电路的比较： 项目数据报虚电路 建立连接不需要需要 寻址方式每个分组都有源端和目的 端的全地址 在连接建立阶段使用目的端地址， 分组使用短的虚电路号 路由选择每个分组独立选择路由在虚电路建立时进行，之后所有分 组均按同一路由 结点失败的影 响 出故障的路由器可能会丢失 分组，一些路由可能会发生 变化 所有经过出故障的路由器的虚电路 均不能工作 分组的顺序不一定按发送顺序到达目 的站 总是按发送顺序到达目的站 端到端的差错 处理 由主机负责由通信子网负责 端到端的流量 控制 由主机负责由通信子网负责 拥塞控制难如果有足够的缓冲区分配给已经建 立的每一条虚电路，则容易控制 1.结点交换机中的路由表 层次结构的编址方案 最简单方案：把一个地址分成前后两部分a，b,a表示结点 交换机编号，b表示计算机终端编号。 路由表：每个结点都有一个路由表，包括目的站及下一跳两 部分。 交换机2的路由表： 5.2 广域网中的路由选择机制 目的站下一跳 1，1 交换机1 1，3 交换机1 3，2 交换机3 3，3 交换机3 2，1 本交换机 2，2 本交换机 如图节点交换机2中的路由表 交换机3 交换机1 交换机2 交换机2 路由表 2, 12, 2 1, 1 1, 3 3, 2 3, 3 目的站 1, 1交换机1 1, 3交换机1 3, 2交换机3 3, 3交换机3 2, 1本交换机 2, 2本交换机 下一站 1 3 2 计算机的编址和网络层节点交换机的路由表 路由表的简化 将目的站定义为交换机号，只有分组到达目的结点交换机, 交换机才检查第二部分地址，再将分组交给目的计算机。上例 每个交换机连接2个终端，路由表简化后为原来1/2大小。 2、用图表示广域网 研究广域网路由问题时，可用图论中“图”来表示广域网 2 4 3 1 结点1的路由表： 目的站下一跳 1 23 33 43 默认路由：所有具有相同“下一站”的项目，用默认路由代 替，其目的站用符号“*”标记 目的站 下一跳 1 * 3 结点1路由表使用默认路由后， 更加简洁,减少了搜索时间。 1.理想的路由算法 算法必须是正确和完整 计算上简单 具有自适应性 具有稳定性 算法公平 算法应是最佳的 5.3 路由选择的一般原理路由选择的一般原理 2. 路由算法的分类 非自适应路由选择策略 自适应路由选择策略 （1）非自适应路由选择：固定路由算法、分散通信 量法、洪泛法、随机走动动法 （）自适应路由选择 ：分布式路由选择选择 策略、 集 中式路由选择选择 策略、混合式路由选择选择 策略 3.非自适应路由选择 固定路由法 原理：在每个结点上保持一张路由表，表上标明对每一 个目的地址应走哪条链路进行转发。这些表是在整个系统进 行配置时生成的，并且在此后的一段相当时间保持固定不变 。 方法：将网络内任何两个结点之间的最短通路事先计算 好，然后根据这些最短通路制成路由表，存放在各个结点中 。 关键点：算出给定网络中任意两个结点之间的最短通路。 即寻找从源结点到网络中其他各结点的最短通路。 令d（v）为源结点（结点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） 这种方法是事先在每个结点的内存中设置一个 路由表，但此路由表中给出几个可供采用的输出链路， 并且对每条链路赋予一个概率。 目的 站 经 过 概 率 经 过 概 率 经 过 概 率 am0.50l0.40n0.10 bm0.50n0.20l0.30 cn0.65m0.25p0.10 dn0.55p0.30m0.15 ep0.45n0.30m0.25 abc d m n e p g l 节点g中的路由表 洪泛法（flooding） 这种方法是当某个结点收到一个不是发给它的分 组时，就向所有与此结点相连的链路转发出去。当然，不 能再把这个分组发到它刚刚离开的那个结点，否则就永远 有一些分组来回不停地在各条链路上“振荡”。 采用两种方法来限制分组数目: 一种方法是在每个分组的首部设置一个计数器。 每当分组到达一个结点时，计数器即自动加1。当计数器所 计的数达到规定值时（如达到端到端所能达到的最大段数 ），即将此分组丢弃。 另一种方法是在每一个结点建立一个登记表 ，凡经过此结点的分组均进行登记。当某个分组再 次通过该结点时，即将该分组丢弃。 随机走动法(random walk) 这种方法又称为随机徘徊，其特点是当分组 到达某个结点时就随机地选择一条为转发的路由。 4.自适应路由选 择 分布式路由选择策略 在分布式路由选择策略中，最基本的算法有两个 ，即距离向量算法和链路状态算法。 下面介绍距离向量算法。每个结点上保持有两个 向量： di为结点i的时延向量 dij为结点i至结点j的最小时延的当前估值 n为网络中的结点数 si为结点i的后继结点向量 sij为结点i至结点j的当前最小时延路由中 结点i的后继结点 其中： dkj为结点k至结点i的时延的当前估值 a为结点k的所有相邻结点的集合 每个结点定期与它所有相邻结点交换它们的时延向 量。然后根据收到的全部时延向量来修改本结点的d与s。 对于任一结点k，修改方法如下： 使 为最小 0242021 12363128 25181936 4027824 1473022 23201940 1831631 1720019 2101422 911710 2422220 293399 a b c d e f g h i j k l to a i h k 延迟 延迟 延迟 延迟 是8 是 10 是12 是6 从j的四个邻居收到的向量 8a 20a 28i 20h 17i 30i 18h 12h 10i 0- 6k 15k 新估计的从 j的延时 线路 j的新路由表 路由器j从其邻居收到距离向 量表后计算自己的向量表 分布式路由选择方法的几个要素： 对于网络的某种特性的测量过程。 关于如何传播上述特性的测量结果的协议。 如何计算出所确定的路由。 时延的测量方法： 早期arpanet把在一个结点中向某条链路发 送的等待队列中的分组数目再加上一个常数（即偏 移）作为此链路的时延。 存在的问题： 当一个分组到达某一个结点时，还需要经过一段处理时间 （这时间是可变的）才加入等待队列。 等待队列长度的瞬时值（在测量瞬间得到的值）并不能精 确代表链路的平均时延。实际测量结果表明，在高负荷工 作下，虽然网络的平均时延很大，但仍还有不少分组具有 很小的时延，而有的队列长度有时甚至下降到零。 等待队列的长度仅仅是影响分组的延时许多因素中的一个 。仅就这一因素进行测量不能得出精确的结果。 改进方法： 不再用队列长度表示时延，而是将时延实际测量出来。 当分组到达某个结点时，立即在分组上写入到达时间，即打上 时间戳（timestamp）。当该分组发送时，再记录发出时间。发 出时间减去到达时间再加上分组的发送时间和传播时间，即得 出时延。若收到否认响应，则在重传时将发送时间更新，“时 延”是一次成功的发送所经历的时间。 路由表的更新： 在新的路由算法中，不再是128 ms更新一次，而是10s更 新一次，时延信息采用广播方式传送给其它结点。 集中式路由选择策略 网控中心ncc负责全网状态信息的收集、路由计算以 及路由选择的实现。 优点：各个结点不需要进行路由选择计算，较容易得 到更精确的路由最优化，消除了路由不断变来变去的“振荡” 现象。还可起到对进入网络的通信量的某种流量控制作用。 缺点：一个是距离ncc较近的地方通信量的开销较大 ，这是因为要周期性地从所有结点收集网络的状态信息的报告 ，同时还要将路由选择的命令从ncc送到网内的每一个结点。 另一个更严重的缺点是可靠性问题，一旦ncc出故障，则整个 网络即失去控制。 混合式路由选择策略 目前可行的混合式路由选择策略只能是将集中式 的和孤立的路由选择策略结合起来。集中式的路由选择策 略用来寻找在稳定状态下的最佳路由，然后由ncc将路由表 送到每一个结点去。而孤立的路由选择策略则用来提供对 局部的拥塞和故障的迅速响应。 1、拥塞控制的意义 若对网络中某一资源的需求超过了该资源所能提供的可用 部分，网络的性能就要变坏，这种情况就叫做拥塞（congestion ） 对资源的需求可用资源 1）解决网络拥塞是一项系统工程 网络拥塞往往是由许多因素引起的. 2）拥塞控制与流量控制的关系密切 拥塞控制是一个全局性的过程 流量控制往往指在给定的发送端和接收端之间的点对点通信 量，是一个局部的过程 5.4 拥塞控制 3）进行拥塞控制需要付出代价 4）死锁问题 当网络负载继续增大到某一数值时,网络的吞吐量就下降 到零,网络已无法工作。这就是所谓的死锁（deadlock） （1）直接死锁：由互相占用对方需要的资源而造成的死 锁 （2）重装死锁： 5）拥塞特点 当网络负载较小时，有拥塞控制的吞吐量反而比无