第6章---网络层

1、第6章 网络层,6.1 网络层服务及其实现 6.2 路由选择 6.3 交通控制 6.3 交通控制,6.1 网络层服务及其实现,6.1.1 面向连接的服务和无连接的服务 网络层为传输层提供服务。一般来说网络层在IMP中运行,传输层在主机中运行,因此网络层与传输层之间的界面就是通信子网和用户之间的界面,网络层提供的服务就是通信子网为用户提供的服务。ISO为网络层定义了两种服务面向连接的服务(ISO8348)和无连接的服务(ISO8473)。,关于网络层应该提供什么样的服务的问题在ISO内部有相当大的争议。代表电信公司的一方,出于行业习惯,认为通信网络应该提供面向连接的服务。因为传统的电话网络服务就

2、是面向连接的(但是电路交换的)。另一方以ARPA网为代表,坚持网络层只提供无连接的服务,毕竟ARPA网以这种方式已成功地运行多年了。,由图6.1可以看出,从数据链路层开始都向上面的邻层分别提供面向连接的服务和无连接的服务,只有物理层提供一种服务,即透明地传输比特流。在传输层和网络层,对上层的任何一种服务(面向连接的或无连接的)都可以用下层的任何一种服务实现。,图6.1 OSI参考模型中面向连接的服务和无连接的服务,6.1.2数据报和虚电路 一种自然的想法是在通信子网内部用数据报方式实现无连接的网络服务,用虚电路实现面向连接的网络服务。 四种组合中有三种是可供选择的: (1)内部虚电路实现面向连

3、接的服务。 (2)内部数据报实现面向连接的服务。 (3)内部数据报实现无连接的服务。 (4)内部虚电路实现无连接的服务。,下面介绍几种具体网络中实现网络服务的方法。 (1)ARPANET。 ARPANET提供两种服务,并分别称其为数据报服务和虚电路服务,但是在通信子网内部只有数据报一种实现方法。 (2)TYMNET。TYMNET 网络是美国Tymshare公司于70年代建成的商用计算机通信网,目前它的服务范围已扩展到加拿大和欧洲地区。TYMNET网络内部用虚电路支持面向连接的网络服务,网络把用户主机看作是字符流(而不是分组流)的源。,图6.2 TYMNET的虚电路,图6.3TYMNET的帧和分

4、组的格式 (a)帧(物理记录)格式 (b)分组(逻辑记录)格式,在其他常见的网络中,提供的服务和实现方法也各不相同,DECnet网络层用数据报提供无连接的网络服务,面向连接的服务由上层实现SNA则和TYMNET一样,网络层用虚电路提供面向连接的网络服务。这4种网络提供的服务和实现方法表示在表61中。,表61 网络服务及其实现方法,6.2 路由选择,网络层的主要功能是把数据分组从源结点传送到目标结点,所以为传送的数据分组选择合适的路径就是网络层要解决的关键问题。路径选择算法的好坏关系到网络资源的利用率和网络性能的高低。,无论采用什么样的路由选择算法,路由选择过程都涉及到下面一些问题: (1)测量

5、(或获取)有关路由选择的网络参数 (2)把路由信息传播到适当的网络结点(网管中心或有关的转发结点) (3)计算和更新路由表 (4)根据路由表的信息对传送中的分组进行调度。,图6.4 网络信息流的振荡,6.2.1 最短通路算法 最短通路的更一般的说法是最少费用通路。通路的费用是组成通路的各段链路的费用的累加和,一段链路的费用则可根据网络的设计目标不同而指定为线路容量,线路延迟,队列长度或可用资源数量等。无论采用哪种费用准则,都可用一个数表示费用的值。于是,如图6.5所表示的那样,最小费用通路问题就归结为加权图中的最短通路问题,这个问题的算法已经定型。,图6.5 加权图中的最短通路,假定结点1为源

6、结点,则 (1)初始化:置N=1,对每一个vN,置D(v)=l(1,v) (2)重复:找出一个结点wN,且D(w)是最小的,把w加入N。然后对所有不属于N的结点v按下式更新D(v): D(v)=MinD(v),D(w)+l(w,v) 对图6.5应用这个算法,可得到表62,产生的最短通路树表示在图6.6(a)中。图6.6(b)是为结点1计算出的路由表,该表指明通向各个目标结点的转发路径。,表62 Dijkstra算法,图6.6 计算最短通路的例 (a)最短通路树 (b)结点1的路由表,搜索过程如下: (1)初始化:置D(1)=0,所有非目标结点都加上标志(,) (2)重复:对每一个非目标结点v用

7、下式更新D(v): D(v)=MinD(w)+l(v,w) 其中结点w为v的相邻结点。,表63 Ford&Fulkerson算法,6.2.2 路由选择策略 1.固定式路由选择 这是一种最简单的路由选择策略。每一对源和目标之间的通路都是按照某种最小费用准则预先选择好的,并存储在网络中某些地方。在设计网络路由时依据的费用准则不能与网络的动态参数(例如通信量的分布)有关,至多在网络拓扑结构变化时才重新计算一次全网的路由。固定式路由选择的实现可采用路由表法。例如,对图6.5的网络应用前面介绍的最短通路算法可为各个结点产生路由表,如图6.7所示。,图6.7 固定式路由选择,2. 扩散式路由选择 扩散式路

8、由选择的原理如下:源结点把分组发送给每个相邻结点,每个中间结点接收到分组后复制若干个拷贝,转发给除输入链路之外的其他各个相邻结点,这样同一分组的拷贝像洪水泛滥一样,迅速布满全网,总有一个拷贝最先到达目标结点。 目标结点接收最先到达的分组后丢弃其余分组。使用扩散式路由选择时,有可能发生分组被重复拷贝的情况,例如在图6.8中结点2和3都收到了结点1发来的分组,它们拷贝后都要把分组发往对方,形成了无谓的重复传送。,图6.8 扩散式路由选择,扩散式路由选择技术有两个特性值得注意: (1)源和目标结点之间所有可能的通路都被试用了,这样无论有多少链路或结点失效,只要有一条通路存在,分组总能到达目的地。 (

9、2)由于所有通路都被利用了,必然有一个分组走了最短的通路最先到达目标结点。,3. 随机式路由选择 随机式路由选择与扩散式相比对网络负载的增加小得多。同时仍然保持了扩散式的简单性和坚强性。 为了减少盲目性,可以对各个输出链路指定不同的选择概率。例如根据各个输出链路数据速率用下式计算出每条链路的选择概率:,4.自适应式路由选择 实现这种高标准的灵活的算法要付出更大的代价: (1)最佳路由的计算更复杂,更频繁,因而开销更大 (2)收集到的路由信息要传播到计算路由的结点,或者计算的结果要传播到转发分组的结点。这些都增加了网络的负载 (3)自适应算法对网络参数的变化反应太快会引起网络流的振荡,反应太慢则

10、得不到最佳路由,为减少这些风险要经常对算法本身的某些参数进行调整,这又增加了网络管理的难度。,自适应算法虽然有这些缺点,但是在大型公共网络中仍然得到广泛的应用。因为这种算法的优点也是明显的: (1)能极大地改善网络的性能,网络的经营者可以得到最大的吞吐率,网络用户则会明显感到网络延迟很小 (2)能对网络的通信量进行控制,避免或减缓网络中拥挤和阻塞的发生(这一点后面还要详细讨论)。,通常根据路由信息的来源和进行路由决策的地点,把各种自适应算法分为以下三类: (1)孤立式自适应策略:利用本地信息进行分布式控制 (2)分布式自适应策略:利用相邻结点的信息进行分布式控制 (3)集中式自适应策略:利用全

11、网结点的信息进行集中式控制。,图6.9 孤立式自适应路由选择算法的例,6.2.3 路由选择算法实例 1. ARPANET ARPANET的路由选择算法经过了多次修改,其中较大的变化有三次。下面分别介绍这三次变化及算法演变过程。 仍然用图6.5的网络为例,图中各个链路上的数字代表链路延迟(即队列长度)。根据这个图,可计算出结点1的路由表如下:,1 1 0 2 2 2 3 4 3 4 4 1 5 4 2 6 4 4,目标结点 下一 结点 延迟 时间,图6.10 网络延迟的例,假设经过很短时间后,网络中的链路延迟变成了图6.10所示的那样。于是结点1收到了三个相邻结点传送的延迟矢量: D2 D3 D

12、4 2 5 1 0 3 2 3 0 5 2 5 0 4 1 6 6 3 8,由于d1,2=2,d1,3=5,d1,4=1,故对应于3个延迟矢量可计算得到3个新的延迟矢量: 目标结点 D2 D3 D4 2 2 8 3 3 5 5 6 4 4 10 1 5 6 6 7 6 8 8 9,然后取每行的最小者,可得到结点1的新路由表: 目标结点 下一结点 延迟时间 1 1 0 2 2 2 3 3 5 4 4 1 5 3 6 6 3 8,计算过程是这样的:首先测量最近10秒钟的平均延迟,然后对这个值进行下面的处理: (1)利用简单的M/M/1排队模型,把平均延迟转换为链路利用率的估值。根据排队论,利用率p

13、可表示为延迟t的函数: 其中,s为分组服务时间,即平均分组长度(600bit)/链路速率。,(2)用以前的利用率平滑上一步的计算结果,得出平均利用率: u(n+1)=0.5p(n+1)+0.5u(n) 其中u(n)表示在取样时刻n的平均利用率,p(n+1)表示在取样后的下一时刻根据第1步计算的利用率。 (3)把链路费用表示为平均利用率的函数,函数关系如图6.11所示。最后得到的费用值实际上是变换了形式的线路时延。,2. TYMNET TYMNET是集中控制的网络,由一个运行管理程序的中心结点进行路由管理,管理程序记录着每一条链路的固定费用值。 TYMNETI的特点是,在轻负载时,尽量使用高速链

14、路,当负载增加时,路由选择算法能平滑地把负载分散到低速链路上,同时各个转发结点的处理开销也很小。 TYMNET也对恢复过程进行了改进。,图6.11 ARPANET的时延函数,6.3 交通控制,6.3.1 交通控制技术的分类和分级 1.交通控制技术的分类 交通控制技术有三种类型,各有不同的控制目标,即流量控制,拥挤控制和防止死锁。 (1)流量控制。 流量控制是指调节两点间的传输速率,即由接收方根据它的接收速率控制发送过程,避免出现来不及接收的情况,通常用某种形式的滑动窗口协议来实现流量控制。,图6.12 有效吞吐率和网络负载的关系,图6.13 缓冲区干扰的例,图6.14 缓冲区干扰引起的吞吐率衰

15、减,(2) 拥挤控制。 拥挤控制不同于流量控制,它的目的是保持网络中的分组数不要超过某一限度,因为一旦这一界限被打破,网络性能将显著下降。 分组在网络中流动类似于车辆在公路上行驶,重负载下的通信网络更像是交通高峰时期的公路系统。,图6.15 拥挤控制的效果,(3) 防止死锁。 计算机网络中发生死锁和多任务操作系统中发生死锁的情况是类似的,即多个用户进程等待已分配的资源获得释放,并且进程对资源的等待和占用关系形成环路条件。 最简单的一种死锁是直接存储转发死锁。如图6.16(a)所示,结点A和B通过一段链路直接相连,当负载较重时,结点A中的缓冲区迅速被流向B的分组占满,而结点B中的缓冲区则被流向A

16、的分组用完。,另外一种死锁是间接存储转发死锁,这种死锁表示在图6.16(b)中。若每一个结点中的缓冲区都被发往下一个结点的分组占满,使得每一个结点都不能接收新的分组,这样就形成了等待回路,使信息无法流动。,图6.16 存储转发死锁 (a)直接死锁 (b)间接死锁,图6.17 结构化的缓冲池,图6.18 分组通过结构化缓冲,图6.19装配死锁 (a)装配缓冲区死锁(b)重排序死锁,2. 交通控制技术的分级 分组交换网中的各种交通控制技术可以分级实施,图6.20画出了通常的分级方法。,图6.20 交通控制的分级,6.3.2 交通控制技术的实现 1. ARPANET中的交通控制 当某一最大限制达到时

17、,多余的分组被丢弃。缓冲池分配情况如图6.21所示。ARPANET采用的这种缓冲区管理方法称为最小分配最大限制的共享分配法。,图6.21 ARPANETIMP的缓冲区分配,2. TYMNET中的交通控制 TYMNET对虚电路实施网络访问级和跳步级两级流控。管理程序在建立虚电路时根据要求的峰值数据速率指定沿路逻辑信道的缓冲区空间配额。各结点在允许的配额限制内发送数据,每发送一个字符,配额数减1。配额用完后,停止发送,等待恢复配额。在TYMNET中,由接收结点掌握恢复配额的时机,因为接收结点知道它在某个信道上接收了多少字符,也知道什么时候配额用完,或者它的缓冲空间是否富裕。,3.SNA中的交通控制

18、 SNA的交通控制机制是基于窗口步调的概念。网络中的交通流量以窗口为单位度量,在得到接收端认可的情况下,发送端可以发送一个窗口所能容纳的全部报文。(图6.22中,窗口大小K=4)。,图6.22 SNA的窗口步调机制,SNA的分组中有5bit的窗口步调机制,如表64所示。在每个窗口中发送的第一个分组把“虚路由步调请求”VRPRQ置位,表示请求允许发送下一个窗口。接收结点收到VRPRQ后,发回已将“虚路由步调响应”VRPRS置位的分组。如果接收结点无法为另外一个窗口分配缓冲资源,则暂缓发送VRPRS,直到有足够的资源可用。,表64 SNA分组中的窗口步调机制,若PCWS-MIN,则维持其不变,若P

19、CWS-MIN,则使PC=WS-MIN。总之在任何情况下,WS均复位为WS-MIN,PC值小于等于WS-MIN。处理过程如图6.23所示。,图6.23 SNA虚电路窗口步调控制,6.4 X.25公共数据网,6.4.1 X.25建议概述 公共数据网PDN(PublicDataNetwork)是在整个国家或全世界范围内提供公共电信服务的数据通信网。,图6.24表示三层之间的关系。本地的用户数据传送到X.25的分组层后,分组层在它前面加上包含控制信息的分组头。分组头和用户数据组成的分组交给链路层后,链路层又加上帧头和帧尾组成数据帧,然后由物理层送入通信子网。而帧头和帧尾信息则由LAP-B实体用于控制

20、数据链路的工作。,图6.24 X.25三层之间的关系,6.4.2 X.25分组层协议PLP 1.虚电路的建立和清除 X.25的分组层提供虚电路服务。有两种形式的虚电路:一种是虚呼叫VC(VirtualCalls),一种是永久虚电路PVC(PermanentVirtualCircuits)。虚呼叫是动态建立的虚电路,有呼叫建立,数据传送和呼叫清除等几个过程。,图6.25表示通过虚呼叫进行数据通信的例子。当一个DTE想与远方的DTE通信时首先要建立虚电路,于是它发送Call Requst分组,该分组中包含呼叫方和被呼方的地址以及它指定的虚电路代号。,图6.25 X.25虚电路的建立和清除,虚电路的

21、诊断分组保留之外,建立虚电路时可以使用其余的4095个代号,因而理论上说,一个DTE最多可建立4095个虚电路。这些虚电路多路复用DTEDCE之间的物理链路,进行全双工通信。一条虚电路可能对应于一个应用程序,进程或终端。DTE发出或接收的每个分组都属于某一个已存在或要建立的虚电路。,图6.26 虚电路代号的分配,2. 分组类型和格式 X.25PLP使用的分组类型列在表65中。各种分组的格式大同小异,分别列于图6.27(a)(e)。,表65 X.25PLP分组类型,PLP协议把用户数据分成一定大小的块(一般为128字节),再加24位或32位的分组头组成数据分组。 图6.27(e)表示的是Call Request分组的完整格式。分组类型字段对Call Request是0000101,对其他控制分组可能取别的值。,图6.27 X.25分组格式 (a)3位顺序号的数据分组(b)7位顺序号的数据分组 (c)RR,RNR和REJ分组(3位顺序号) (d)RR,RNR和REJ分组(7位顺序号)(e)控制分组,图6.27 X.25分组格式 (a)3位顺序号的数据分组(b)7位顺序号的数据分组 (c)RR,RNR和REJ分组(3位顺序号)