第五章网络层网络层——端到端数据传输的最低层●网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机。

●网络层需要了解通信子网的拓扑结构，选择合适的传输路径。

●网络层要预防和控制通信子网中超量的信息分组造成的拥塞。

●网络层还要处理不同网络中源端和目的端之间的差异。

§5.1 网络层设计的有关问题●对网络层所提供的服务存在着两种观点：–面向连接的服务，复杂的功能放在通信子网中。

–无连接服务，复杂的功能放在主机中。

网络层的内部结构●网络层提供的服务是否可靠与有无连接并没有关系。

理论上存在四种组合，但最重要的只是其中的两种组合：–可靠的面向连接服务。

–不可靠的无连接服务。

●针对两种服务，网络层有两种不同的工作方式：–虚电路（virtual circuit）方式。

当建立连接时，从信源到信宿的路由就作为连接建立的一部分加以保存，此路由用于传输连接上的所有数据，当释放连接时，虚电路也随之撤消。

–数据报（datagrams）方式。

即使提供面向连接的服务也不预先选择路由，发出的每个分组所选择的路由独立于其前面发出的分组，后续的分组可以走不同的路由，比虚电路方式更健壮，更容易处理传送失败和拥塞。

§5.2 路由选择算法●路由选择是网络层的主要功能，负责为分组选择合适的转发路径。

●路由选择算法应具有以下几种特征：正确性（correctness）、简单性（simplicity）、健壮性（robustness）、稳定性（stability）、公平性（fairness）和最优性（optimality）。

●一个好的路由选择算法是兼顾某几种重要的性能指标。

路由选择算法的分类●分为两大类：–非自适应算法（non-adaptive algorithm）：也叫静态路由选择（staticrouting），预先离线计算好路由表，在网络启动时装入到路由器中，在网络运行过程中不会根据网络流量和拓扑结构的变化而改变。

简单。

–自适应算法（adaptive algorithm）：也叫动态路由选择（dynamic routing），根据当前网络流量和拓扑结构的变化，动态在线地计算网络的路由。

复杂、健壮，网络负担重。

最短通路路由选择算法●最短通路（shortest path）路由选择算法属于自适应路由算法。

它将一个通信子网抽象成一张图，图中的顶点代表网络节点（路由器），弧线代表通信线路，弧线上的权代表相邻顶点间的“距离”（可为物理上的距离，或指分组在其间的传输时间，也可指线路上的通信费用等）。

任意一对顶点之间的最小权值即为它们的最短通路。

●求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉（Dijkstra）提出了按通路长度递增的次序产生最短通路的算法，基本思想为：–首先从起始点出发，找出距起始点最近的结点，然后以此结点为基础找出距起始点次近的结点，如此每次都找出比前一次次短的通路，直至某个通路到达给定的目的，这时所得到的通路就是源到目的的最短通路。

–具体可采用标记方法。

扩散法（flooding）●扩散法为静态算法，也称洪泛式。

基本思想：路由器将收到的每个分组，从除了分组到来的线路外的所有输出线路上发出。

●可靠性高，但容易造成网络拥塞，改进办法有：◆在每个分组头中增加一个站点计数器（hop counter）：每经过一个站点，计数器减1，当计数器减为0时，就扔掉分组。

计数器的值可设置为源到目的的长度或子网的直径。

◆记下分组扩散的路径，确保分组只转发一次。

可以让源路由器对来自主机的每个分组设置一个序号，每个路由器对应于每个源路由器都有一张表，用来记录已转发过的分组（源路由器和序号）。

◆选择扩散法（flood selectively）：只转发到与正确方向接近的那些线路上。

●适用于负荷轻的小规模网络以及特别强调健壮性的网络。

基于流量（flow-based）的路由选择●一种既考虑拓扑结构又兼顾载荷的静态路由选择算法。

●基本思想：利用已知的载荷平均流量，计算出该线路上的平均分组延迟；由所有线路的平均延迟，计算出整个网络的平均分组延迟，从而找出具有网络最小延迟的最优路由选择算法。

●采用这种技术必须预知的几种信息：–网络的拓扑结构F ij–给出通信量矩阵C ij–各线路容量的矩阵–选定一种路由选择算法距离矢量路由选择●距离矢量路由选择（distance vector routing）算法是现代计算机网络两个最常使用的动态路由选择算法之一。

●基本思想：每个路由器维护一张（矢量）表，表中给出到每个目的节点已知的最佳距离和路径；每个路由器还不断测试到达相邻路由器的距离；相邻的路由器之间也不断地相互交换矢量信息；这样每个路由器将测试出的到达相邻路由器的距离加上相邻路由器给出的矢量信息，就可得知通过相邻路由器到达每个目的节点的距离，选择最佳路径更新表的信息。

无穷计算(count-to-infinity)的问题●DVR算法收敛慢，其时间复杂度为O(n3)。

特别是它对好消息的反应迅速，但对坏消息却反应迟钝。

●其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无穷计算的后果。

●在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加1）来扼制这种无限的增长。

链路状态路由选择●链路状态路由选择（link state routing）算法1979年出现在ARPAnet上，作为一种用来取代DVR的动态路由选择算法，之后得到了广泛的应用。

●基本思想：通过各个节点之间的路由信息交换，每个节点都可获得关于全网的拓扑信息，即所有的节点、各节点间的链路连接和链路的代价（时延或费用等），可将这些拓扑信息抽象成一张带权无向图，然后利用最短通路路由选择算法计算出到各个目的节点的最短通路。

链路状态路由选择算法的步骤⏹找出所有可达的相邻节点及它们的网络地址；⏹测定到这些相邻节点的代价；⏹将以上信息构成链路状态分组（link state packet）；⏹向网上所有节点发送链路状态分组；⏹利用收到的链路状态分组计算到各目的节点的最短通路。

分级路由选择（hierarchical routing）●将网络分成一些区域，每个区域内的路由器只负责本区域内的分组转发，而不管其它区域的情况，目的地址不在本区域内的分组都发给指定的区域路由器去处理。

●当网络规模很大时，往往需要分成多级。

●路由信息的交换只在本区域内进行，路由器内部需存储的路由信息大大减少。

节省了路由器的存储空间和网络带宽。

●缺点是选择的路由可能不是最佳的。

§5.3 拥塞控制●拥塞–当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降，这种现象称为拥塞。

–拥塞不加控制地发展下去，最终导致网络通信停顿（有效吞吐量为零），即阻塞。

拥塞控制的基本原理●根据控制论，拥塞控制方法分为两类–开环控制（拥塞预防）–闭环控制（拥塞解决）拥塞控制算法●拥塞预防策略通信量整形和通信量管制●通信量整形（traffic shaping）：迫使分组按预定的速率进入网中，避免突发性的大通信量造成网络瞬间过载。

广泛用于面向连接的工作方式（如ATM）。

●通信量管制（traffic policing）：网络对用户的通信量进行监视，对遵守约定的用户，保证其要求的服务；对违反协议的数据采取惩罚措施，如丢弃、降低优先级、不保证服务质量等。

●以上方法一般用于以虚电路方式工作的网络层，在建立虚电路的时候由双方协商而定。

在数据报子网上实现比较困难，但可应用于传输层的连接中。

漏桶（leaky bucket）算法●在主机和网络之间接入一个“漏桶”（固定长度的分组队列），无论主机以多大的速率发送分组，“漏桶”中的分组总是以恒定的速率注入网中。

若主机发送过快，当“漏桶”满了以后，多余的分组即被丢弃。

令牌桶（token bucket）算法●令牌桶算法能较快地响应突发数据的到来，且不会丢失数据。

●令牌桶中每隔定长的时间产生出一个令牌（计数器），当桶装满后，随后产生的令牌就被丢弃。

分组在桶外的缓冲区中等待发送，桶中有多少令牌就允许发送多少个分组，每个令牌用后即销毁，当桶中没有令牌时必须停止发送。

●为了平滑大量突发数据的出现，可在令牌桶后面增加一个漏桶，使得漏桶的速率大于令牌桶但小于网络的峰值速率拥塞的解决⏹虚电路子网中采用许可控制（admission control）的三种策略：◆一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解除。

⏹允许建立新的虚电路，但要仔细选择路由，以便所有新的虚电路绕过拥塞的区域。

⏹在虚电路建立时，子网与主机对所需服务质量进行协商。

若不能满足主机最低要求，则拒绝建立连接；否则就保留连接所需的多种资源，避免拥塞发生。

⏹抑制分组（choke packet）：–每个路由器监视本节点的资源利用情况，若某个方向的资源利用率超过一定的门限，则该路由器向有关源节点发送抑制分组，源节点相应减少发往该方向的数据量，直至该方向的拥塞解除。

–为了公平合理地控制引起拥塞的源节点的行为，可采用加权公平队列（weighted fair queuing）。

⏹在（高速的）WAN中为了及时解脱拥塞，可以上游使用更多的缓存为代价，这种方法称为站到站抑制分组。

⏹负载丢弃（load shedding）：–在没有办法消除拥塞时，只能采取极端措施，即丢弃部分的分组来解决拥塞。

–为了使网络能合理地丢弃分组，应用程序应对各分组标注优先级别，以便有选择依据。

●延时差控制：–为满足音频或视频数据流传输时对延时变化的敏感性，需要对传输延迟进行控制，以保证可接受的最大延时差。

–通过在沿途经过的路由器中计算分组传输的延迟，与预期的传输平均延迟之差决定其在输出队列中的优先次序，能够有效的减小传输延迟差。

⏹多点播送的拥塞控制：–多点播送要实现多个源端到多个目的端的分组传输流，其拥塞控制必须适应目的端的不断变换，加入不同的多点播送组造成的带宽需求变化。

–RSVP资源重复利用协议：根据接收者向上传送至发送者的带宽保留消息，沿途设置从源到目的的多点播送树的带宽预留，接收者可同时声明一个或多个想接收的源并在其中自由切换。

各个路由器利用这些信息来优化整体带宽使用计划。

§5.4 网络互联●连接不同网络的设备统称“网关”（gateway），用来在不同网络之间对数据进行转换。

网络互联设备●根据其工作层次的不同，分别称为：–中继器（repeater）：在物理层上再生放大物理信号。

–网桥（bridge）：在数据链路层上，采用存储-转发方式对数据帧进行传递。

–多协议路由器（multiprotocol router）：类似网桥，但工作在网络层，转发分组时要进行路由选择，对连接的不同网络还要进行不同协议的转换。

–传输网关（transport gateway）：用来建立两个网络间的传输连接。