《计算机网络》第五章

1、第五章 网络层网络层端到端数据传输的最低层 网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机。 网络层需要了解通信子网的拓扑结构，选择合适的传输路径。 网络层要预防和控制通信子网中超量的信息分组造成的拥塞。 网络层还要处理不同网络中源端和目的端之间的差异。§ 5.1 网络层设计的有关问题 对网络层所提供的服务存在着两种观点：-面向连接的服务，复杂的功能放在通信子网中。-无连接服务，复杂的功能放在主机中。网络层的内部结构网络层提供的服务是否可靠与有无连接并没有关系。理论上存在四种组合，但最 重要的只是其中的两种组合：-可靠的面向连接服务。-不可靠的无连接服务。针对两种服务

2、，网络层有两种不同的工作方式：-虚电路(virtual circuit )方式。当建立连接时，从信源到信宿的路由就作 为连接建立的一部分加以保存， 此路由用于传输连接上的所有数据， 当释放连 接时，虚电路也随之撤消。-数据报(datagrams)方式。即使提供面向连接的服务也不预先选择路由，发 出的每个分组所选择的路由独立于其前面发出的分组， 后续的分组可以走不同 的路由，比虚电路方式更健壮，更容易处理传送失败和拥塞。§5.2 路由选择算法 路由选择是网络层的主要功能，负责为分组选择合适的转发路径。 路由选择算法应具有以下几种特征：正确性( correctness )、简单性( si

3、mplicity )、健壮性( robustness )、稳定性( stability )、公平性( fairness ) 和最优性( optimality )。一个好的路由选择算法是兼顾某几种重要的性能指标。路由选择算法的分类分为两大类：-非自适应算法(non-adaptive algorithm):也叫静态路由选择(staticrouting )，预先离线计算好路由表，在网络启动时装入到路由器中，在网络 运行过程中不会根据网络流量和拓扑结构的变化而改变。简单。-自适应算法 (adaptive algorithm ):也叫动态路由选择 (dynamic routing ), 根据当前网络流量

4、和拓扑结构的变化， 动态在线地计算网络的路由。 复杂、健 壮，网络负担重。最短通路路由选择算法最短通路( shortest path )路由选择算法属于自适应路由算法。它将一个通信 子网抽象成一张图，图中的顶点代表网络节点(路由器)，弧线代表通信线路， 弧线上的权代表相邻顶点间的“距离”(可为物理上的距离，或指分组在其间的 传输时间，也可指线路上的通信费用等)。任意一对顶点之间的最小权值即为它 们的最短通路。求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉( Dijkstra )提 出了按通路长度递增的次序产生最短通路的算法，基本思想为:-首先从起始点出发，找出距起始点最近的结点，然后

5、以此结点为基础找出距起 始点次近的结点， 如此每次都找出比前一次次短的通路， 直至某个通路到达给 定的目的，这时所得到的通路就是源到目的的最短通路。-具体可采用标记方法。扩散法( flooding )扩散法为静态算法，也称洪泛式。基本思想:路由器将收到的每个分组，从除了 分组到来的线路外的所有输出线路上发出。可靠性高，但容易造成网络拥塞，改进办法有: 在每个分组头中增加一个站点计数器( hop counter ):每经过一个站点，计 数器减 1，当计数器减为 0时，就扔掉分组。 计数器的值可设置为源到目的的长 度或子网的直径。记下分组扩散的路径， 确保分组只转发一次。 可以让源路由器对来自主机

6、的每 个分组设置一个序号， 每个路由器对应于每个源路由器都有一张表， 用来记录 已转发过的分组(源路由器和序号)。选择扩散法( flood selectively ):只转发到与正确方向接近的那些线路上。适用于负荷轻的小规模网络以及特别强调健壮性的网络。基于流量( flow-based )的路由选择 一种既考虑拓扑结构又兼顾载荷的静态路由选择算法。 基本思想：利用已知的载荷平均流量，计算出该线路上的平均分组延迟；由所有 线路的平均延迟，计算出整个网络的平均分组延迟，从而找出具有网络最小延迟 的最优路由选择算法。采用这种技术必须预知的几种信息：-网络的拓扑结构-给出通信量矩阵Fj-各线路容量的矩

7、阵C-选定一种路由选择算法距离矢量路由选择距离矢量路由选择( distance vector routing )算法是现代计算机网络两个最 常使用的动态路由选择算法之一。基本思想：每个路由器维护一张(矢量)表，表中给出到每个目的节点已知的最 佳距离和路径；每个路由器还不断测试到达相邻路由器的距离；相邻的路由器之 间也不断地相互交换矢量信息； 这样每个路由器将测试出的到达相邻路由器的距 离加上相邻路由器给出的矢量信息， 就可得知通过相邻路由器到达每个目的节点 的距离，选择最佳路径更新表的信息。无穷计算 (count-to-infinity) 的问题DV算法收敛慢，其时间复杂度为 qn3)。特别是

8、它对好消息的反应迅速，但对坏 消息却反应迟钝。其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无穷计算的 后果。在实际使用中，可通过设置距离的最大值(如设置为网络最长路由加1)来扼制这种无限的增长。链路状态路由选择链路状态路由选择(link state routing )算法1979年出现在ARPAne上，作为 一种用来取代DVR勺动态路由选择算法，之后得到了广泛的应用。基本思想：通过各个节点之间的路由信息交换，每个节点都可获得关于全网的拓 扑信息，即所有的节点、各节点间的链路连接和链路的代价（时延或费用等）， 可将这些拓扑信息抽象成一张带权无向图， 然后利用最短通路路由选择算法计

9、算 出到各个目的节点的最短通路。链路状态路由选择算法的步骤找出所有可达的相邻节点及它们的网络地址；测定到这些相邻节点的代价；将以上信息构成链路状态分组（ link state packet ）；向网上所有节点发送链路状态分组；利用收到的链路状态分组计算到各目的节点的最短通路。分级路由选择（ hierarchical routing ） 将网络分成一些区域，每个区域内的路由器只负责本区域内的分组转发，而不管 其它区域的情况，目的地址不在本区域内的分组都发给指定的区域路由器去处 理。当网络规模很大时，往往需要分成多级。 路由信息的交换只在本区域内进行，路由器内部需存储的路由信息大大减少。节 省了路

10、由器的存储空间和网络带宽。缺点是选择的路由可能不是最佳的。§ 5.3 拥塞控制 拥塞-当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整 体性能下降，这种现象称为拥塞。-拥塞不加控制地发展下去，最终导致网络通信停顿（有效吞吐量为零），即阻 塞。拥塞控制的基本原理根据控制论，拥塞控制方法分为两类-开环控制（拥塞预防）-闭环控制（拥塞解决）拥塞控制算法拥塞预防策略通信量整形和通信量管制通信量整形( traffic shaping )：迫使分组按预定的速率进入网中，避免突发 性的大通信量造成网络瞬间过载。广泛用于面向连接的工作方式(如 ATM)。通信量管制( traffi

11、c policing )：网络对用户的通信量进行监视，对遵守约定 的用户，保证其要求的服务；对违反协议的数据采取惩罚措施，如丢弃、降低优 先级、不保证服务质量等。以上方法一般用于以虚电路方式工作的网络层， 在建立虚电路的时候由双方协商 而定。在数据报子网上实现比较困难，但可应用于传输层的连接中。漏桶( leaky bucket )算法在主机和网络之间接入一个“漏桶”(固定长度的分组队列)，无论主机以多大的速率发送分组，“漏桶”中的分组总是以恒定的速率注入网中。若主机发送过 快，当“漏桶”满了以后，多余的分组即被丢弃。令牌桶( token bucket )算法 令牌桶算法能较快地响应突发数据的到

12、来，且不会丢失数据。 令牌桶中每隔定长的时间产生出一个令牌(计数器)，当桶装满后，随后产生的 令牌就被丢弃。分组在桶外的缓冲区中等待发送，桶中有多少令牌就允许发送多 少个分组，每个令牌用后即销毁，当桶中没有令牌时必须停止发送。为了平滑大量突发数据的出现，可在令牌桶后面增加一个漏桶，使得漏桶的速率 大于令牌桶但小于网络的峰值速率拥塞的解决虚电路子网中采用许可控制( admission control )的三种策略： 一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解除。 允许建立新的虚电路， 但要仔细选择路由， 以便所有新的虚电路绕过拥塞的区 域。在虚电路建立时， 子网与主机对所需服务质量进行

13、协商。 若不能满足主机最低 要求，则拒绝建立连接；否则就保留连接所需的多种资源，避免拥塞发生。抑制分组( choke packet )：-每个路由器监视本节点的资源利用情况，若某个方向的资源利用率超过一定的 门限，则该路由器向有关源节点发送抑制分组， 源节点相应减少发往该方向的 数据量，直至该方向的拥塞解除。-为了公平合理地控制引起拥塞的源节点的行为，可采用加权公平队列( weighted fair queuing )。在(高速的)WA中为了及时解脱拥塞，可以上游使用更多的缓存为代价，这种 方法称为站到站抑制分组。负载丢弃( load shedding )：-在没有办法消除拥塞时，只能采取极端

14、措施，即丢弃部分的分组来解决拥塞。-为了使网络能合理地丢弃分组，应用程序应对各分组标注优先级别， 以便有选 择依据。延时差控制：-为满足音频或视频数据流传输时对延时变化的敏感性，需要对传输延迟进行控 制，以保证可接受的最大延时差。-通过在沿途经过的路由器中计算分组传输的延迟， 与预期的传输平均延迟之差 决定其在输出队列中的优先次序，能够有效的减小传输延迟差。多点播送的拥塞控制：-多点播送要实现多个源端到多个目的端的分组传输流， 其拥塞控制必须适应目 的端的不断变换，加入不同的多点播送组造成的带宽需求变化。-RSV资源重复利用协议：根据接收者向上传送至发送者的带宽保留消息， 沿途 设置从源到目的

15、的多点播送树的带宽预留， 接收者可同时声明一个或多个想接 收的源并在其中自由切换。各个路由器利用这些信息来优化整体带宽使用计 划。§5.4 网络互联连接不同网络的设备统称“网关” (gateway)，用来在不同网络之间对数据进 行转换。网络互联设备根据其工作层次的不同，分别称为：-中继器(repeater ):在物理层上再生放大物理信号。-网桥(bridge ):在数据链路层上，采用存储-转发方式对数据帧进行传递。-多协议路由器(multiprotocol router ):类似网桥，但工作在网络层，转发分组时要进行路由选择，对连接的不同网络还要进行不同协议的转换。-传输网关(tra

16、nsport gateway ):用来建立两个网络间的传输连接。-应用网关(application gateway )：在应用层上进行协议转换。半网关网关可从中间分成两部分，每个部分称为一个半网关，每个网络都拥有和管理一 个半网关，半网关之间用无源的导线相连，两个半网关的接口处使用相同的中间 协议进行网络互连。网络互联的两种形式面向连接的级联虚电路( Concatenated Virtual Circuits )无连接网络互联( Connectionless Internetworking )级联虚电路从信源到信宿的虚电路穿越沿途各网络及网关。其建立方式同普通虚电路一样， 只是对连接不同协议网

17、络的多协议路由器要求进行协议转换。无连接网络互联网络层只提供最简单、最基本的数据报传输服务:无连接、独立路由、不可靠、 无序。隧道( Tunneling )实际上要转换两种不同协议的网络是很困难的，甚至不可能。有一种特殊情况:当信源和信宿都处在同一类型的网络中，而这两个网络又通过 另一种类型的网络进行互联。可采用挖隧道方式简单巧妙地解决协议的转换。在挖隧道方式中，实际并没有进行任何的协议转换，只是将被传输的数据分组作 为中间网络分组承载的数据，穿越过去。分段( fragmentation )不同的网络的分组长度是不一样的，当一个大分组穿越分组定义较小的网络时， 网关必须将一个大分组划分成若干个

18、小的段( fragment )，把各段作为单独的分 组进行发送。透明分段：在中间网络进出时分别进行分段和重组工作。每个小分组须含有计数 字段或分组结束标志以便出口网关重组，所有分组必须经同一网关发出。不透明分段：中间网关不重组各分段，每个分段的分组都作为单独原始的分组独 立传递，最后在目的地主机上进行重组。防火墙( firewall ) 防火墙设有过滤分组的网关，只有检查合格的数据才能进出网络。 由两部分组成： 两个用作进出分组过滤的路由器和一个用于对数据内容进行检查 的应用网关。§ 5.5 因特网上的网络层 因特网：在网络层，可以看作是一组由主干连接在一起的多个自治系统 (autonomous system )子网。IP协议是连接因特网的网络层协议IP地址因特网控制协议因特网控制消息协议 ICMP(Internet Control Message Protocol ) 地址解析协议 ARP(Address Resolution Protocol)反向地址解析协议 RARP(Reverse Address Resolution Protocol )内部网关路由选择协议因特网由大量自治系统( auton