CHAPTER 5 NETWORK LAYER
Data Communications and
Computer Networks
中国科学技术大学网络学院 李艺
leeyi@
概述
网络层是OSI参考模型的得三层，它建立在数据链路层所提供的两个相邻的端点之间的数据帧的传送功能之上，将数据从源端经过若干中间的节点送到目的端，从而向运输层提供最基本的端数据传送服务。网络层是处理端到端数据传输的最低层，体现了网络应用环境中资源子网访问通讯子网的方式。
ISO 定义
网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。
网络层的作用
屏蔽不同类型网络之间的差异，实现互连
了解通信子网的拓扑结构，选择路由，实现报文的网络传输。
网络层提供的服务类型
面向连接的服务和无连接的服务。
概述
通信子网的内部操作
虚电路方式(virtual circuit) ：源结点与目的结点通信之前，先建立一条从源结点到目的结点的虚电路（即逻辑连接），然后通过该虚电路进行数据传送，当数据传输结束时，释放该虚电路。
每个交换机都维持一个虚电路表，用于记录经过该交换机的所有虚电路的情况，每条虚电路占据其中的一项。
数据报文在其报头中除了序号、校验和以及其他字段外，还必须包含一个虚电路号。
数据报方式(datagram) ：每个节点只需要用一张表来指明到达所有可能的目的端交换机的输出线路。
每个报文都要单独寻址，要求每个数据报包含完整的目的地址。
两种方式的差别：虚电路为每一对结点之间的通信预先建立一条虚电路，后续的数据通信沿着建立好的虚电路进行，节点不必为每个报文选择路由；而在数据报中，每一个节点为每一个转发报文进行独立的路由选择。
概述
两种方式如何选择？ 在广域网内部，是选择虚电路还是数据报，有几个权衡的因素。
节点的内存空间与线路带宽的权衡。
虚电路中，路由器需要维护虚电路的状态信息；
数据报，每个数据报都携带完整的目的/源地址，浪费带宽
虚电路建立时间和路由选择时间的比较。
虚电路需要在建立连接时花费时间
数据报则在每次路由时过程复杂
拥塞控制的能力
虚电路可以进行拥塞避免，原因是虚电路方式在建立虚电路时已经对资源进行了预先分配（如缓冲区）。
而数据报广域网要实现拥塞控制就比较困难，原因是数据报广域网中的节点机不存储广域网状态。
虚电路方式提供的是面向连接的服务；而数据报方式提供的是无连接的服务。
服务质量
虚电路方式很容易保证服务质量，适用于实时操作，但比较脆弱。
数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。
总之，数据报广域网无论在性能、健壮以及实现的简单性方面都优于虚电路方式。
概述
虚电路
概述
数据报
概述
网络层的内部组织、向主机提供的服务
在分组交换网中，通信子网向端系统提供的服务有虚电路和数据报。
通信子网内部的操作方式也分虚电路和数据报两种方式。
向主机提
供的服务
通信子网
工作方式
向主机提供的服务
UDP over IP
TCP over IP
数据报子网
UDP/IP over ATM
ATM over ATM
虚电路子网
数据报
(无连接)
虚电路
(面向连接)
概述
网络层提供的服务
寻址与路由
拥塞控制
网络互连
网络审计
虚电路
虚电路操作方式 在虚电路操作方式中，为了进行数据传输，网络的源节点到目的节点之间先要建立一条逻辑通路，因为这条逻辑通路不是专用的，所以称之为“虚”电路。
每条链路中可能有若干条虚电路支持；两个端系统之间也可以有多条虚电路为不同的进程服务，这些虚电路的实际路径可能相同也可能不同。
节点间的物理信道在逻辑上均可看做由多条逻辑信道组成，这些逻辑信道实际上由节点内部的分组缓冲器来实现。
所谓占用某条逻辑信道，实质上是指占用了该段物理信道上节点分配的分组缓冲器。
不同的逻辑信道在节点内部通过逻辑信道号加以区分，各条逻辑信道异步时复用同一条物理信道。
虚电路
工作原理
各节点在虚电路建立过程中在节点的虚电路表中建立一条逻辑信道记录。
每个分组携带一个逻辑信道号，同一条虚电路的分组在各段逻辑信道上的逻辑信道号可能不相同。
传输中，当一个分组到达节点时，节点根据其携带的逻辑信道号查找虚电路表，以确定该分组应发往的下一个节点。
下一段信道的逻辑信道号，由该逻辑信道号替换分组中原先的逻辑信道号后，再将该分组发往下一个节点。
虚电路
例：虚电路表建立。假设要建立下列6条虚电路：
1）ABCD； 2）ACD； 3）BCD；
4）BAE； 5）AEFD； 6）BFE。
解决思路：
由于虚电路上的数据是双向传输的，为保证两节点之间正、反两个方向的虚电路不相混淆；
在一个节点选取逻辑信道号来替换其前一节点的逻辑信道号时，不仅要考虑与下一节点之间的逻辑信道号不相同，还在考虑与下一节点作为另一个条反向虚电路的上一节点头时所选取的逻辑信道号相区别。
虚电路
路由选择
路由算法应具有的特性
正确性（correctness）
简单性（simplicity）
健壮性（robustness）
稳定性（stability）
公平性（fairness）
最优性（optimality）
它们之间有时是有矛盾的。例如，当A和A‘、B和B’、C和C‘之间正在通信，水平线路已经达到饱和状态，为了它们的最优传输，应该拒绝D与D’之间的通信，但失去了公平性。
路由选择
路由算法分类
非自适应算法，静态路由算法
自适应算法，动态路由算法
最优化原理（optimality principle）
如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。
证明：用反证法来证明。
已知： I到K的最佳路径为r1+r2，
设 J到 K的最佳路径没有落在I到K的路径上，而是另外一条路径r3，则I到K的最佳路径变成r1+r3，与前提条件矛盾。得证。
I
I
J
K
r1
r2
路由选择
接收树（sink tree）
从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为接收树；
路由算法的目的是找出并使用接收树。
静态路由选择
洪泛算法（Flooding）
原理：把收到的包，向除了到来的线路外的所有线路转发。
问题：洪泛要产生大量重复包。
解决措施：
每个包头置一个站点计数器，每经过一站计数器减1，为0时则丢弃该包；
记录包经过的路径。
选择洪泛算法（selective flooding）
原理：将收到的包仅发送到与目的方向接近的线路上。
评价
仍然占用大量的路由器和线路的资源，实际很少采用；
具有极好的健壮性，可用于军事应用；
静态路由选择
静态路由选择
固定路由选择算法
原理：每个节点存储一张表格，表格中每一项记录着对应某个目的节点的下一节点或链路。当一个分组到达该节点时，它根据分组中的的地址信息，从固定的路由表中查出目的点，然后转发给目的点对应的下一节点。
实现：网络控制中心按照最佳路由算法求出每对源点、目的点的最佳路由，然后为每一个节点构造一张固定路由表并分发给各个节点。
测量路径长度的方法
跳转数量
地理距离
传输延迟
距离、信道带宽等参数的加权函数
评价：优点是简便易行，在负载稳定，拓扑结构变化不大的网络中运行效果很好。缺点是灵活性差，无法应付网络中发生的阻塞和故障。
静态路由选择
Dijkstra算法：也称为最短路径算法（Shortest Path Algorithm ）、正向搜索算法（Forward Search Algorithm），是一种集中式的静态算法。
Dijkstra算法的正式定义：
设：N = 网络中所有节点的集合
S = 源节点
M = 已有算法归并的节点的集合
L(i,j) = 节点i与j之间链路权值；若两个节点间没有直接连接则为∞
C(n) = 算法求得的当前从S到n的最少花费路由的花费
算法步骤：
初始化
M={S}
C(n)=L(S,n) for n≠ S
从不再M中的相邻节点中找到出一个具有和节点S的最少花费路由的节点，并且把节点规约进M中。
更新最少的花费路径
重复步骤 2 和 3 ，知道M=N.
静态路由选择
Dijkstra算法实现
每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；
初始时，所有结点都为临时性标注，标注为无穷大；
将源结点标注为0，且为永久性标注，并令其为工作结点；
检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；
在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；
重复第四、五步，直到目的结点成为工作结点；
静态路由选择
动态路由选择
距离向量路由算法（Distance Vector Routing）：也称Bellman-Ford 路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP协议采用。
基本思想
每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；
以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；
每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；
邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表；
注意：本路由器中的老路由表在计算中不被使用。
动态路由选择
动态路由选择
存在无限计算的问题
算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；
动态路由选择
改进方法
水平分割算法，从对方知道的路由不再回传给对方；
设置16跳为无穷大，当跳数到达16时，认为路由不可达。
距离向量路由算法的主要问题
选择路由时，没有考虑线路带宽；
路由收敛速度慢。
由于16跳被认为是无穷大，故只适应小型网络
动态路由选择
链路状态路由算法（Link State Routing）
链路状态路由算法
发现邻居结点，并学习它们的网络地址；
路由器启动后，通过发送HELLO包发现邻居结点；
两个或多个路由器连在一个LAN时，引入人工结点；
测量到每个邻居结点的延迟或开销；
一种方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。
动态路由选择
将所有学习到的内容封装成一个包；
包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；
列表中对应每个邻居结点，都有发送方到它们的延迟或开销；
链路状态包定期创建或发生重大事件时创建。
动态路由选择
将这个包发送给所有其它路由器；
基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；
改进：序号循环使用会混淆，解决办法：使用32位序号；
计算新路由
在收集到全部的链路状态信息后，建立通信子网图，运行Dijkstra算法求到各目的顶点的最短路径，更新路由表。
动态路由选择
从E发来的链路状态包有两个，一个经过EAB，另一个经过EFB；
从D发来的链路状态包有两个，一个经过DCB，另一个经过DFB；
动态路由选择
链路状态算法（LS）和距离向量算法（DV）的比较
路由信息的复杂性
LS：路由信息向全网发送，具有n个节点，E条链路，每次发送的信息的算法复杂度为 O(nE)
DV：只在邻节点交换信息
收敛（Convergence）速度
LS：使用最短路径优先算法，算法复杂度为O(n2)；n个结点（不包括源结点），需要n*(n+1)/2 次比较；使用更有效的实现方法，算法复杂度可以达到O(nlogn)；可能存在路由振荡（oscillations）
DV：收敛时间变化较大，可能存在路由回路或无穷大记数问题
健壮性:
LS：节点可能传播不正确的链路值，因为每个节点只计算自己的路由表
DV：节点可能传播不正确的路径，因为每个节点的路由表都有其他节点使用，可能将错误的路由传播出去。
动态路由选择
分层路由（Hierarchical Routing）
网络规模增长带来的问题
路由器中的路由表增大；
路由器为选择路由而占用的内存、CPU时间和网络带宽增大。
分层路由的提出
分而治之的思想；
根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）…
分层路由带来的问题：路由表中的路由不一定是最优路由。
动态路由选择
将较大的自治域划分成区
动态路由选择
广播路由
实现广播发送的方法：
N-Way-Unicast：利用单播向每一个目的主机单独发送。这种方式实现简单，但浪费带宽，而且要求源主机知道所有目的主机。
扩散法：会产生较多的分组副本，需要有限制扩散的措施。
多目的路由：每个分组携带一个目的地列表，当多个目的地使用同一条输出线路时，只在这条线路上发送分组的一个拷贝。这种方式可以节省带宽，但仍要求源主机知道所有目的主机。
使用通信子网的生成树（以源节点为根）转发分组。这种方法生成的分组拷贝最少，但要求路由器知道通信子网的拓扑结构。
反向路径转发，这种方式只使用节点的单播路由表转发广播分组，不需要生成树的知识，也不需要知道所有的目的主机。
广播路由
反向路径转发
基本思想：
当广播分组到达路由器时，路由器检查分组的源地址与输入线路；
若输入线路与单播路由表中去往该地址的输出线路相同，则扩散该分组，否则丢弃分组。
优点：
算法合理、有效、易于实现且开销不大。
广播路由
(a) 子网. (b) 接收树. (c) 由反向路径转发建立的树.
拥塞控制
什么是拥塞
大量分组在短时间内进入通信子网（或其局部）并由此造成网络处理能力下降的现象。
拥塞发生的原因
负载超出了网络的处理能力。网络的处理能力是指节点的存储能力（内存容量）、计算能力（CPU速度）和数据传输能力（线路带宽），这些能力也称为网络的资源。
拥塞控制的任务
尽量避免拥塞的发生，并在出现拥塞的时候及时采取措施缓解拥塞。
拥塞控制与流量控制
拥塞控制针对通信子网，它要确保进入网络的数据量不超出网络的处理能力；流量控制针对接收终端，它要确保进入接收端的数据量不超出接收端的处理能力；
两者的相似之处是都需要控制源节点的数据发送。
拥塞控制
拥塞与负载的关系
拥塞控制
拥塞控制的两种方法
开环（open loop）方法：通过对系统进行精心设计来确保拥塞不会出现，实际操作起来比较困难；
闭环方法（closed loop）：建立在反馈环路的基础上，通过实时监测并在拥塞出现时采取积极的应对措施来减少拥塞。
缓解拥塞的两种应对措施
增加资源：如启用备用资源；
减小负载：如限制进入网络的数据量，丢弃负载等
拥塞控制
常见的拥塞控制措施
接纳控制（admission control）：用于虚电路子网，通信前先建立连接，用户与网络协商需要的资源，协商成功后才同意建立连接，并预留资源。
警告比特（warning bit）：路由器对所有使用拥塞线路的分组打上标记，接收端将标记拷入到给发送端的应答中，要求发送端相应地减小发送速度。
抑制分组（choke packets）：当路由器发现它的一条输出线路超载时，向所有使用这条线路的分组的发送端发送一个抑制分组，要求减小发送的速度。
逐跳抑制分组（hop-by-hop choke packets）：当路由器收到下游路由器的抑制分组后，立即减少发往下游路由器的数据。
负载丢弃（load shedding）：当路由器发现内存利用率超过一定门限时，主动丢弃部分分组以减小负载。
随机及早检测（Ramdom Early Detection, RED）
当路由器发现平均分组队列长度达到第一个门限值 （最小阈值）时，开始按照某个丢弃概率 p 丢弃到来的分组；
当平均队列长度达到第二个门限值（最大阈值）时，丢弃到达的分组；
平均队列长度的计算公式：
AvgLen = (1- Weight)×AvgLen + Weight×SampleLen
概率 p 是平均队列长度和上一次丢弃距当前时间的函数，分组队列长度越大，丢弃间隔越大，则丢弃的可能性也越大。
拥塞控制
服务质量
流（flow）：在同一对源和目的之间传输的分组流（packet stream）
服务质量QoS（Quality of Service ）：分组流对网络服务提出的要求，如可靠性、带宽、传输延迟、延迟抖动（jitter）等。不同应用对网络服务的要求是不同的。
实现服务质量的技术
过量提供资源（overprovisioning)
接收端缓存：消除延迟抖动
资源预留(resource reservation)：在流要经过的路径上预留所需的带宽、内存及CPU时间；
接纳控制(admission control)：仅当路径上的每个节点都能满足资源需求时才建立连接；
拥塞控制
流量整形（Traffic Shaping）
开环控制
基本思想
造成拥塞的主要原因是网络流量通常是突发性的；
强迫包以一种可预测的速率发送；
在ATM网中广泛使用。
漏桶算法（The Leaky Bucket Algorithm）
将用户发出的不平滑的数据包流转变成网络中平滑的数据包流；
可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数；
无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。
拥塞控制
拥塞控制
令牌桶算法（The Token Bucket Algorithm）
漏桶算法不够灵活，因此加入令牌机制；
基本思想：漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；
漏桶算法与令牌桶算法的区别
流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。
漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。
拥塞控制
拥塞控制
虚电路子网中的拥塞控制
许可控制（admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；
另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；
资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。
拥塞控制
抑制包（Choke Packets）
基本思想
路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态；
每个新包到来，检查它的输出线路是否处于警戒状态；
若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址。同时将原包打上标记（为了以后不再产生抑制包），正常转发；
源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；
通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。
拥塞控制
公平队列（Fair Queueing）算法
路由器的每个输出线路有多个队列；
路由器循环扫描各个队列，发送队头的包；
所有主机具有相同优先级；
一些ATM交换机、路由器使用这种算法；
一种改进：对于变长包，由逐包轮讯改为逐字节轮讯
拥塞控制
负载丢弃（Load Shedding）
上述算法都不能消除拥塞时，路由器只得将包丢弃；
针对不同服务，可采取不同丢弃策略
文件传输，优先丢弃新包，wine策略；
多媒体服务，优先丢弃旧包，milk策略；
设置包优先级，按优先级机制决定丢弃策略；
早期丢弃包，会减少拥塞发生的概率，提高网络性能。
习题：
本章习题请上网查阅教学网页：
