第四章 网络层

网络层的任务是要以分组为单位将数据信息从源节点传送到目的节点。
　　网络层的功能与服务
　　路由选择
　　拥塞控制
　　X.25中的网络层

第一节 网络层的功能与服务
4.1.1 网络层功能及模型
网络层的作用：在数据链路层提供的在相邻两个节点之间透明、可靠的传送数据帧的功能的基础上，进一步管理网络中的通信，将从传输层交出的数据以分组为单位，从源节点通过通信子网沿适当的路径传
送到目的节点。
网络层的功能：
向传输层提供服务、路由选择、拥塞控制、网络互联。

4.1.2 网络层提供的服务
面向连接的网络服务 ——虚电路服务
无连接的网路服务 ——数据报服务
4.1.2.1 虚电路服务
虚电路：在通信之前，需要在源节点和目的节点间建立起一条逻辑上的网络连接，我们称之为虚电路。
建立虚电路过程：
建立连接
数据交换
拆除连接

虚电路的实现：
建立虚电路时分配给该虚电路一个没用过的虚电路号，以区别于本系统中的其他虚电路。
传送数据时，每个数据分组含有分组号、校验和控制信息及其要经过的虚电路的号码，以区别其它虚点路上的分组信息。

每个节点都应保持一个虚电路表，它的每一项记录了一个打开的虚电路信息，包括虚电路号、前一节点和下一节点的标识。
通常采用“动态”虚电路号码选取法：即总是选取当前尚未使用的最低虚电路号。

4.1.2.2 数据报方式
数据报服务：没有虚电路建立的过程，每一个发出的分组（称为一个数据报）都携带了完整的目的地址信息，因而每一个分组都可以独立的选择路由。
分组到达目的节点的顺序有可能与发送顺序不完全一致，甚至会失去某些分组。
要求接收方主机具有重新排序、纠正重复或丢失分组的功能。

数据报实现
在每个节点同样要有一个路由表，按照每个分组所携带的目的地址查找路由表来决定应沿哪条链路转发分组。
4.1.2.3 虚电路服务与数据报服务的比较

第二节 路由选择
4.2.1 理想的路由算法
路由算法：网络节点在收到一个分组后，决定在那一条输出链路上传送
下去所使用的策略。
理想的路由算法的一些特点：
(1)正确性。必须是信息快速、正确的传输。
(2)简单性。计算简单可以减少时延。另外，路由选择的计算不应使网络的通信量增加太多的额外开销。
(3)坚固性。算法应能适应通信量和网络拓扑的变化，要有自适应性。有时称这种自适应性为“健壮性”(robustness)。
(4)稳定性。当通信量和网络拓扑发生变化时，路由算法应收敛于一个可以接受的解，而不应产生过多的振荡。
(5)公平性。算法应对所有用户（除对少数优先级高的用户）都是平等的。
(6)最佳性。是指以最低的费用来实现路由算法。实际上，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
4.2.2 最短通路路由选择
例：寻找从源节点A到网络中其他各节点的最短通路。
令D(ν)为源节点(节点A)到节点ν的距离；
令N表示网络节点的集合，初始时令N＝{A}；
令l(i，j)为节点i至节点j之间的距离。

算法：
(1)初始化
D(ν)= (A , ν) 若节点ν与节点A直接相连
∞ 若节点ν与节点A不直接相连
(2)寻找一个不在N中的节点ω，其D(ω)值为最小，把ω加入到N中，然后对所有不在N中的节点，用D(ν)和[D(ω)+λ(ω，ν)]中的较小的值去更新原有的D(ν)值，即：
D(ν)←min[D(ν)，D(ω)+λ(ω，ν)]
(3)重复步骤(2)，直到所有的网络节点都在N中为止。

4.2.3 路由选择的不同策略
1.非自适应路由选择——简单、开销小
(1)洪泛法(flooding)
策略：当某个网络节点从某条输入线路收到一个不是发给它的分组时，就向所有与此节点相连的其它链路转发出去。
优点：①算法简单，几乎不需要什么计算；
②可以在最短的时间内接收方收到信息；
③方便实现广播通信和多址通信，具有良好的健壮性，广泛应用于军事网中。
缺点：①造成分组无休止的传输；
②使接收方收到多个重复的分组；
③网络中分组数目迅速增长，结果导致网络出现拥塞现象。
改进：采用计数器或登记表法控制网络中分组数目的增长。
(2)有选择的洪泛法
策略：仅在满足某些事先确定的条件的链路上转发分组。
好处：分组不会向不希望去的方向转发。
(3)固定路由法
策略：在每个节点上保存一张由此节点到网络中其他节点的固定路由表（由网络设计人员或管理人员根据网络拓扑结构、流量分布和其他因素编制的，并且在此后的一段相当时间保持固定不变），表中规定一条或多条输出线。
适用：当网络拓扑固定不变并且通信量也相对稳定时。
(4)随机走动法(random walk)
策略：当分组到达某个节点时就随机地选择应当走哪条链路作为转发的路由，因此又称为随机徘徊。
适用：在非自适应的路由策略中，若可能发生节点或链路的故障，那么随机走动法巳被证明是非常有效的，它使得路由算法具有较好的健壮性。
(5)分散通信量法(traffic bifurcation)或查表选择路由(directory routing)
策略：事先在每个节点的内存中设置一个路由表，路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率；当一个分组到达该节点时，此节点即产生一个从0.00到0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。

2．自适应路由选择
当网络拓扑发生变化时及网络某个节点或链路发生故障时，在网络的某个局部范围做出调整路由的决定。
(1)孤立的路由选择策略
策略：只根据本节点的状态来选择路由，而不和其它节点交换状态信息。
“热土豆”算法：当收到一个分组时，不管其目的地址如何，把刚收到的分组以最快速度发往各链路中等待队列长度最短的等待队列中排队等候发送。 缺点：不准确，有时队列最短的方向井非正确的转发路由。
改进：令队列长度为Q，在每个队列增加一个对于某一目的地址的偏移数B，取Q+B值为最小的队列作为转发方向。
例如：对应于F，E，D和C的B值若分别为0，6，5和8．则算出相应的Q十B值分别为5，7，9和10，因此应把收到的分组送到发往F的队列中。

(2)分布式路由选择策略——是目前应用最广泛的路由算法
特点：适应性较好，每个节点周期性地从相邻的节点获得网络状态信息，同时也将本节点做出的决定周期性地通知周围的各节点，以使这些节点不断地根据网络新的状态更新其路由选择决定。
例：ARPANET使用算法是在每一个节点保持两个向量，即：

Di——节点i的时延向量； d_ij——节点i至节点j的最小时延当前估值(d_ij=0)； n—— 网络中的节点数； S_i——节点i的后继节点向量； S_IJ——后继节点(节点i到节点j当前最小时延路由中的第二个节点。 对于任一节点k每隔128ms与其所有相邻节点交换时延向量，按以下方法对本节点的时延向量和后继节点向量进行修改： d_ki＝ [d_ki+d_ij-] S_ki==i，用这个i使[d_ki+d_ij-]为最小。
A——节点k的所有相邻节点的集合； d_ki——节点k到节点i的时延的当前估值。

(3)集中式路由选择策略
策略：利用网控中心NCC，专门收集各节点定期发来的状态信息，然后由它根据这些状态信息及网络拓扑结构，动态的计算出每个节点现时的路由选择表，再将新的路由选择表同时送回各个节点使用。
优点：算法能定期按拓扑结构和信息量变化修改各节点的路由选择表； 容易得到精确的路由，消除了分组在网内“兜圈子” 及路由“振荡”的现象； 可起到对进入网络通信量的某种流量控制作用。
缺点：在报告状态-计算-送回路由选择表的过程中花费了不少时间，因此在系统变化较快的网络中很难获得理想的控制效果；NCC的工作量大，因此需要采用速度快、可靠性高的机器；由于采用集中控制，因而NCC工作的可靠性尤为重要，所以应采用若干个级别的NCC协同控制，一旦高一级的NCC出现故障，低一级的NCC马上接替工作，但这种方法花费较大且仍不能满足全部要求；网中负载不平衡，靠近NCC的链路负担重，而远离NCC的链路负载较轻。
(4)混合式路由选择策略

第三节 拥塞控制
拥塞：当到达通信子网中某部分的分组量过多时，就会造成网络性能的下降的现象，称为拥塞。
网络性能下降的表现：信息报传输延迟增加和网络吞吐量下降。

4.3.1 拥塞产生的原因
出现资源拥塞的条件：
∑对资源的需求＞可用资源
解决网络拥塞的办法是采用流量控制。
拥塞控制的主要功能：
(1)防止网络因过载而引起吞吐量下降和时延增加；
(2)避免死锁；
(3)在互相竞争的各用户之间公平地分配资源。

4.3.2 拥塞控制方法

1．缓冲区预分配法——适用于虚电路通信子网
建立虚电路时

传送分组时

2．抑制分组法——可用虚电路或数据报通信子网
策略：在出现拥塞前兆时，对分组进行截流。
算法实现：
每个节点(路由器)都监视其输出线路利用率
μ可用下列公式更新：
f反映线路瞬时利用率，取值为0-1之间的常数；α反映了更新速度。
各节点为每一条线路定义阀值，当μ大于此值时，则该线路进入“告警”状态。
每新收到分组时路由器要查看其输出线是否处于“告警”状态，若是则发送一个抑制分组到源主机，并在抑制分组中指明分组的目的地，并在原分组上加一个标志，表示以后不用再产生抑制分组；发送端主机收到该抑制分组后，将发送速率降低一档，若继续发送抑制分组，则发送端继续降低速率。
3．分组丢弃法
策略：当缓冲区满时，将到来的分组丢弃，丢弃分组后，发送端因得不到确认而超时重发。
缓冲器分配规则：
为每个输入线分配一个能容纳一个分组的缓冲器先把到达的分组接收下来，检查该分组内有无对前面发送的信息报的应答，如果应答表明前一次发送的信息包已经妥收，那么把此分组丢弃，准备接收下一个分组。
限制输出线队列长度N+1个节点缓冲区除了分给输入线(1个)以外，剩余的全分给输出线(N个)。
分配给输出缓冲区的方法有平分法 最大分配法最小分配法 最大最小分配法
4．许可证法
策略：限制通信子网内的分组数目，使之不超过某一个固定值从而避免拥塞。
实现方法：在通信子网中有固定数目的许可证在网中随机巡航流动，任何一个分组想进入网络必须先获得一个许可证；当分组到达终点时就释放许可证。
许可证的分布原则：尽量减少分组等待许可证的时间。
平均分布；——忙、闲不公平
所有许可证在网内四处流动； ——付出等待时延
每个节点上保存少量许可证，其它许可证在网内流动。
存在问题：
能防止全局性拥塞，但仍不能完全消除局部拥塞；
需要防止许可证丢失。
设网内节点数为N，则许可证数可选为3N，每个节点能拥有的许可证L<3为最佳分布。
4.3.3流量控制
流量控制和拥塞控制的区别拥塞控制:必须保证通信子网能正常传输数据，包括流量控制，使全局性问题。
流量控制:根据接收端能承受的数据速率来调节发送端传输数据的速率，防止到达接收端的数据速率超过接收端的处理速率，只与发送者与接收者之间的点到点通信量有关。
流量控制是按级进行的，大致可以划分为四种不同级别。

1.网段级流量控制——需要解决“存储——转发”问题
目的：在相邻两节点之间维持一个均匀的流量，以避免出现局部缓冲区拥塞和死锁。
根据是对两节点间的流量还是对其中每条虚电路的流量进行控制可再划分为：
数据链路网段级流量控制——适用于虚电路、数据报两种业务采用信道队列限制法(即分组丢弃法)进行控制：监视每一个队列的缓冲区的占用情况并对其定义一个极限(固定的或动态可调的)，当某一队列中待转发的分组数超过此极限时即丢弃该分组。
特点：能有效的避免吞吐量的降低，但无法解决间接死锁的问题。
虚电路网段级流量控制——适用于虚电路

信道队列限制法有以下四种变形：
平均分配设N为节点中输出队列的总数,N_i为第i个队列中的分组数,而B为缓冲区的大小(除分配给输入线的之外），则约束条件为： 0≤N_i≤B/N 这种固定分配方法，效率低，性能较差。 最长队列共享 设bmax为所允许的最长队列(此处bmax＞B/N)，则约束条件为： 0≤N_i≤b_max 以及 ∑N_i≤B 最小分配共享 设b_min为保证分配给每一队列的缓冲区大小(当然bin ≤B/N)，则约束条件为： ∑Max(0, N_i -b_min)≤B-Nb_min 最小分配最长队列共享 合并了前两种方式，即每—队列保证有一个最小的缓冲区b_min供使用，同时其最大长度受b_max的限制。
死锁：两个节点之间互相僵持，整个网络不能传输分组，吞吐量为零的情况。
1.存储——转发死锁
直接存储——转发死锁：互相占用了对方需要的资源而造成的死锁。
间接存储——转发死锁：每个节点都试图向相临节点发送分组，但没有一个节点有空闲缓冲区来接收分组导致产生死锁。
2.重装死锁：发生在目的节点，因缓冲区不足无法排序组装造成。

信道队列限制法无法解决间接死锁的问题！
解决间接存储——转发死锁
采用结构化缓冲池策略或称为缓冲区的有向图分配法给每个节点开辟M十1个缓冲区(每个缓冲区存放一个分组)，并从0到M编上号码。仅当与主机相连的源节点的缓冲区0空闲时分组才能发往源节点的缓冲区0。
接着，仅当某个相邻节点中的缓冲区1空闲时分组才能发往缓冲区1，以后每转发一次，所到达的缓冲区的编号就增大一个号，0->1->2->……->M
最终，分组的最坏结局一定是以下两种情况之一：
· 传到所要到达的目的节点，然后交付给主机；
· 传到编号为M的缓冲区，然后被丢弃，因而不再消耗网络的资源。
2．源节点到目的节点级的流量控制——需要解决“重装死锁”问题目的：防止在输出节点出现由于目的节点到主机的连接线路过载或是由于主机接收数的速率太低而导致缓冲区拥塞。
当需要在目的节点把到达的分组重新装配成报文时有可能出现重装死锁！
在ARPANET中使用的源节点到目的节点级的流量控制的方法是：
①源节点发送报文时必须先发送一个“请求缓冲空间”的分组；
②目的节点收到该分组后，即为此报文保留8个缓冲区并回答一个“分配”分组。
③当整个报文的8个分组都收齐并送交主机后，目的节点就发回一个“准备下一报文”的确认分组。
④当源节点无报文要发送但仍收到“分配”分组时，须发回“归还”分组以释放目的节点缓冲空间。

3．进网级流量控制
目的：控制网络外部的通信量进入网络从而防止整个网内的缓冲区产生拥塞。
拥塞的测量：
①局部测量：测量入口节点缓冲区的情况；
②全局测量：测量全网所有缓冲区的占用程度；
③选择测量：测量某个目的节点的整条通路的拥塞情况。
将测量结果报告进网节点，以控制从外部进入网内的通信量。
最出名的进网级流量控制方案为许可证法。

4．传输级流量控制
目的：在两个远程进程之间的虚电路连接中提供分组的可靠传送，即在进程级防止用户缓冲区出现拥塞。
各层采取的流量控制：
数据链路层：进网级、网段级（数据链路网段级）
网络层：入口到出口级、网段级（虚电路网段级）
传输层：传输级

4.4.1 X.25简介
1．X.25的层次结构
由CCITT制定，是关于用专用电路连接到公用数据网上的分组型数据终端设备（DTE）与数据电路端接设备（DCE）之间的接口标准。
版本：1976、1980支持虚电路、数据报两种服务；1984取消了数据报服务；1988、1992只支持虚电路服务。
X.25协议目前以虚电路服务为基础。
分组级主要功能：向主机提供多逻辑信道的虚电路服务。

X.25的三层层次结构
物理层：数据传送单位是“比特”，接口标准采用X.21建议书。
数据链路层：数据传送单位是 “帧” ，接口标准采用平衡型链路接入规程LAPB，是HDLC的一个子集。
分组层：数据传送单位是“分组”，在DTE与的DCE之间可以建立多条逻辑信道
(0-4095号) 。

2．X.25的分组层
通信过程可分为三个阶段：呼叫建立阶段、数据传送阶段、虚电路释放阶段。

3．X.25的状态图
例：呼叫建立阶段的状态图

椭圆代表一个DTE或DCE对的状态；
箭头代表状态变迁的方向；
箭头旁边的文字说明表示是由谁(DTE还是DCE)发出了何种分组。
4.4.2 X.25的分组格式
X.25的分组可分为：控制分组、数据分组。
X.25分组由分组的首部和分组的数据部分组成。
所谓分组格式，主要就是指分组首部的组成，在分组的后面不加尾部。
1. 控制分组
例：呼叫请求分组

2．数据分组格式

4.4.3 X.25网络与字符方式终端的连接
CCITT制定了分组装拆器PAD(又称为分组组装分解设施)以适应以下两种情况：
PAD则提供了智能使字符方式终端能够用25协议同网上的其他主机通信；
PAD提供了许多参数供种类繁多、性能各异的字符方式终端选择，使其能够方便地接入到25网。
定义PAD设施的三个建议书：
30——描述PAD的功能以及控制它工作的一些参数。
28——描述PAD到字符方式终端的协议。
29——描述PAD到主机(同步终端)的协议。