Chapter 5 网络层

主要功能 相关协议 主要设备 网络层 寻址和路由：根据数据的目的地址，确定到目的网络的“最佳”路径，将数据路由到最终的目标主机 网络互连：处理不同类型网络互连中存在的问题 相关协议 ATM、IP 主要设备 路由器、（L3）交换机 应用层 传输层 网络层 数据链路层 物理层

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连

连接与无连接 无连接的服务 面向连接的服务 Internet社区：“网络简单、终端智能“，高效和可扩展性是主要考虑因素 数据报网络：IP 电话公司：“网络智能，终端简单”，服务质量是主要考虑因素 虚电路网络：ATM 存储转发

数据报网络 来自传输层的数据经过网络层处理后直接发送 每个分组中携带完整的目的地址，路由器根据该地址查找转发表来实现分组转发 转发表表项： 目的地址、输出端口、下一跳节点地址信息等 目的地址 输出端口 D 4 2 来自传输层的数据经过网络层处理后直接发送 每个分组中携带完整的目的地址，路由器根据该地址查找转发表来实现分组转发 转发表 转发表 路由器 路由器之间运行路由协议或者静态配置转发（路由）表

虚电路网络 分组发送前建立虚连接或者虚电路(VC: Virtual Circuit) ，即在源和目的主机之间的每个交换机上建立“连接状态” 分组输入时的VCI 从VC离开路由器的分组的输出端口 用于输出分组的一个可能不同的VCI 虚电路网络 输入端口 输入VCI 输出端口 输出VCI 3 4 5 1 2 7 分组发送前建立虚连接或者虚电路(VC: Virtual Circuit) ，即在源和目的主机之间的每个交换机上建立“连接状态” 分组只需携带链路范围有效的VCI( VC Identifier)，在交换机上标识自己所属的VC 服务质量保证：在建立连接阶段为每条虚电路分配足够的资源，以保证带宽、延时等需求 转发表 转发表 路由器 路由器之间运行路由协议或者静态配置转发（路由）表

在建立交换虚电路前，路由器之间先要通过路由协议生成转发表 虚电路建立 永久虚电路（PVC：Permanent VC） 管理员配置或者由管理员通过发起信令建立 交换虚电路（SVC：Switched VC） 主机通过发起信令建立 在建立交换虚电路前，路由器之间先要通过路由协议生成转发表 A发送建立分组给网络，最终目的地是D S1为建立分组分配输入VCI为3 S2为建立分组分配输入VCI为5 S4为建立分组分配输入VCI为7 D分配输入VCI为4 输入VCI通过反向路径返回给沿途各个节点 S1 S2 S3 S4 转发表 转发表

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连

路由和转发 路由（Routing）：找到从源主机到目的主机（所在网络）的“最佳”路径的过程 基于路由算法 转发（Forwarding）：在路由器内部将分组从输入端口转发到输出端口的过程 基于转发表 路由表 注：虽然路由算法找到的是“路径”，但是对于执行路由算法的路由器来说，由于分组采用逐跳转发，所以只需要在路由表中指定转发的下一跳节点即可

不同类型网络的路由 数据报网络：为每个分组选择路由路径，在不同时刻，为相同目的分组选择的路由路径可能不同 虚电路网络：在虚电路建立过程中选择好路由路径，接下来分组沿建立好的虚电路路径传输

“最优”路径度量：物理距离、跳数、队列长度、排队延迟、可用带宽等 路由算法:分类 非自适应算法（Nonadaptive）：事先为计算好每对节点之间的“最优”路径，然后在每个路由器配置好对应的路由表，也称为静态路由（Static Routing） 用户主机 小规模网络 自适应算法（Adaptive Algorithm）：根据网络拓扑结构和状态的变化动态调整“最优”路径，反映到每个路由器就是需要动态更新路由表，也称为动态路由（Dynamic Routing） 动态性大的网络 大规模网络 “最优”路径度量：物理距离、跳数、队列长度、排队延迟、可用带宽等

路由算法就是要找出图中任意两个节点之间开销最小的路径 路由算法：图模型 图中的节点表示路由器或者网络 图中的边对应于网络中的链路 每条边上都一个相应的开销(Cost)：物理距离、跳数、队列长度、排队延迟、可用带宽等因素的函数 路由算法就是要找出图中任意两个节点之间开销最小的路径

“距离”：物理距离、跳数、队列长度、排队延迟、可用带宽等 距离矢量路由：概述 距离矢量算法，也称为Bellman-Ford算法 距离矢量（DV： Distance Vector） 每个节点都维护一个包含了到所有其它节点的“距离”的路由表，也称为矢量表 每个节点都将自己的矢量表分发给它的邻居节点 “距离”：物理距离、跳数、队列长度、排队延迟、可用带宽等

距离矢量：算法过程 初始时每个节点都知道到自己直接邻居节点的距离，到其它节点的距离被指定为无穷大 节点A的初始路由表 目的 距离 下一跳 B 1 C D ∞ E F G

距离矢量：算法过程 每个节点向它的所有直接邻居节点发送自己的所有路由表信息，告诉邻居节点自己到其它节点的距离 A接收到邻居节点发送的路由表信息，则A计算通过该邻居到其它每个节点的距离，如果该距离小于自己保存的路由表中到对应节点的距离，则用该距离和邻居更新路由表 节点A的路由表 目的 距离 下一跳 B 1 C D ∞ E F G <A, 1> <B, 1> <D, 1> D 2 C <G, 1> <A, 1> G 2 F

距离矢量：更新消息 在距离矢量算法中，节点通过发送更新消息向直接邻居节点公告自己到其它每个节点的距离 两种情况下会发送更新消息 定期更新：节点以一定的频率自动发送更新消息 触发更新：每当一个节点从它的邻居节点接收到导致改变路由表中一个路由而引发的更新

距离矢量：故障 故障发现机制 故障处理 节点通过发送控制分组持续地检测到另一个节点的链路，并且查看是否接收到确认 如果节点在最近几次更新周期中接收不到预期的定期更新，则确定该链路（或者链路另一端的节点）发生故障 故障处理 首先发现故障的节点发送更新消息给它的邻居节点，其中到故障链路或者节点的距离为无穷大

距离矢量：故障实例 节点F发现它到G的链路发生故障 节点A的路由表 ∞ 目的 距离 下一跳 B 1 C D 2 E F G G 3 C G

无穷计数！ <A, 4> <A, 3> <A, 2> A B C 目的 距离 下一跳 A 1 C 目的 ∞ C 1 目的 距离 下一跳 B 1 A 4 目的 距离 下一跳 A 3 C 1 无穷计数！

解决方案1：限制选择一个相对较小的数作为无穷大的近似值，例如16，但这种方法限制了网络的可扩展性 <A, 4> <A, 3> <A, 2> A B C 目的 距离 下一跳 A 1 C 目的 距离 下一跳 B 1 A 2 目的 距离 下一跳 A ∞ C 1 目的 距离 下一跳 B 1 A 4 目的 距离 下一跳 A 3 C 1 解决方案1：限制选择一个相对较小的数作为无穷大的近似值，例如16，但这种方法限制了网络的可扩展性

解决方案2：水平分割 ，当一个节点把路由更新发送给邻居节点时，它并不把从各个邻居节点处学到的路由再回送给该节点 <A, ∞> A B C 目的 距离 下一跳 A 1 C 目的 距离 下一跳 B 1 A 2 目的 距离 下一跳 A ∞ C 1 目的 距离 下一跳 B 1 A ∞ 解决方案2：水平分割 ，当一个节点把路由更新发送给邻居节点时，它并不把从各个邻居节点处学到的路由再回送给该节点

水平分割只对两个节点的路由循环有效，更大的路由循环需要更强的措施 1）A发现到E的链路出现故障 2）A向B发送到E的距离为无穷大的分组 3）在A发送到E的距离为无穷大的更新消息到达C之前，C向B发送到E的距离为2的更新消息，此时B已经收到A发送的到E的距离为无穷大的分组，因此更新到E的距离为3 4）B发送到E的距离为3的更新消息给A，A更新到E的距离为4，A发送到E的距离为4的更新消息给C，C更新到E的距离为5 ….. <E, 3> <E, 2> <E, ∞>

链路状态：算法概述 链路状态LS：Link State 链路状态分组LSP：LS Packet 链路状态算法的两个过程 每个节点都知道自己邻居节点的链路状态以及每条链路的开销 每个节点到达邻居节点的信息在整个网络中传播，因此每个节点都有足够的网络信息来建立一个完整的网络映像，因此能够找到到达网络中任何节点的最短路径 链路状态分组LSP：LS Packet 在LS运行过程中，每个节点创建LSP，包含信息： 创建该LSP的节点标识ID 与该节点直接相邻的节点列表，包括到这些相邻节点的链路开销 一个序列号 这个分组的生存期（TTL） 链路状态算法的两个过程 LSP的可靠传播和扩散 节点根据所积累的LSP知识的总和进行路由计算

链路状态：可靠扩散 可靠扩散或者泛洪（Reliable Flooding） 节点创建LSP 节点沿着所有与其直接相连的链路将LSP发送出去，接收到LSP的每个节点再沿着除接收链路以外的所有其它与它相连的链路转发出去，这个过程一直继续，直到LSP到达网络中的所有节点 相邻路由器之间的LSP传递使用确认和重传机制来保证可靠性

LSP的扩散过程 LSP组成： 1) 创建该LSP的节点标识ID 2) 与该节点直接相邻的节点列表，包括到这些相邻节点的链路开销 3) 一个序列号 4) 这个分组的生存期（TTL）

链路状态：可靠扩散 LSP的产生 LSP更新 LSP开销 周期性公告 拓扑结构变化，这也就意味着一个与节点直接相连的链路或者邻居出现故障 链路故障发现：链路层协议发现 邻居故障发现：周期性的“hello”分组发现 LSP更新 LSP携带序列号，节点每产生一个新的LSP，就将序列号加1，在节点上，序列号大的LSP将替换序列号小的LSP LSP携带生存期（TTL），每个节点在将接收到的LSP扩散到其它节点之前，对其TTL减1 。当TTL为0被网络中所有节点看作是删除该LSP的信号 LSP开销 设置大的周期性公告间隔，通常几个小时

链路状态：路由计算 每个节点根据来自其它所有节点的LSP计算出完整的网络拓扑结构图 在网络拓扑结构图的基础上采用Dijkstra （最短路径）算法计算到每个目的节点的最短路径，即最佳路由

Dijkstra（最短路径）算法过程 试探表（Tentative）和证实表（Confirmed）：每条记录的格式为<目的，开销，下一跳>，证实表即为到所有其它节点的最短路径 1）用我的节点（以下称本节点）的一条记录初始化证实表，这条记录的开销为0 步骤 证实表 试探表 说明 1 (D, 0, -) 因为D是证实表中的唯一成员，所以观察它的LSP 2）在前一步中加入证实表的那个节点，称为Next节点，选择它的LSP 步骤 证实表 试探表 说明 1 (D, 0, -) 因为D是证实表中的唯一成员，所以观察它的LSP 2 (B, 11, B) (C, 2, C) D的LSP表明，我们可以以开销11通过B到达B，比表任何其它的路径都好，因此把它加到试探表中，同理C也加入

Dijkstra（最短路径）算法过程 试探表（Tentative）和证实表（Confirmed）：每条记录的格式为<目的，开销，下一跳>，证实表即为到所有其它节点的最短路径 3）将试探表中开销最小的记录加入证实表，Next节点设置为该记录所对应的目的节点 步骤 证实表 试探表 说明 2 (D, 0, -) (B, 11, B) (C, 2, C) D的LSP表明，我们可以以开销11通过B到达B，比表任何其它的路径都好，因此把它加到试探表中，同理C也加入 3 把试探表中开销最小的记录C加入到证实表中。接着，检查证实表中新的成员C的LSP

Dijkstra（最短路径）算法过程 试探表（Tentative）和证实表（Confirmed）：每条记录的格式为<目的，开销，下一跳>，证实表即为到所有其它节点的最短路径 4）对于Next节点的每一个邻居节点，计算从本节点到Next节点和再从Next节点到邻居节点的总开销之和 a) 如果邻居节点当前在试探表中，且开销小于当前登记在表中的开销，那么替换当前记录，其中“下一跳”是我到达Next节点所经历的节点 b) 如果邻居节点当前既不在证实表中，也不在试探表中，那么把<邻居节点，开销，下一跳>记录加入试探表中，其中“下一跳”是我到达Next节点所经历的节点 步骤 证实表 试探表 说明 3 (D, 0, -) (C, 2, C) (B, 11, B) 把试探表中开销最小的记录C加入到证实表中。接着，检查证实表中新的成员C的LSP 4 (B, 5, C) (A, 12, C) 通过C到达B的开销是5，所以替换记录（B，11，B） C的LSP告诉我们可以以开销12到达A

Dijkstra（最短路径）算法过程 试探表（Tentative）和证实表（Confirmed）：每条记录的格式为<目的，开销，下一跳>，证实表即为到所有其它节点的最短路径 5）重复步骤3和步骤4，直到试探表为空 步骤 证实表 试探表 说明 4 (D, 0, -) (C, 2, C) (B, 5, C) (A, 12, C) 通过C到达B的开销是5，所以替换记录（B，11，B），C的LSP告诉我们可以以开销12到达A 5 把试探表中开销最小的记录B加入证实表中，观察它的LSP 6 (A, 10, C) 因为可以经过B以开销5到达A，所以替换试探表中的记录 7 把试探表中开销最小的成员A移入证实表中，结束。

距离矢量和链路状态 在距离矢量算法中，每个节点只和直接相连的节点进行通信，但是它把所知的全部信息（即到所有节点的距离）都告诉它们 在链路状态算法中，每个节点和其余各个节点通过扩散或者泛洪的方式都进行通信，但是它只告诉它们自己确切知道的信息（即与其直接相连的链路状态） 距离矢量算法只适用于小规模网络，为了避免计数到无穷问题，网络直径一般不能超过15跳 与链路状态算法相比，距离矢量算法对网络变化反应较慢

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连

网络拥塞 当网络中出现太多的分组，超过路由器的处理能力时，就会产生网络拥塞拥塞（Congestion） 网络拥塞会导致性能下降 输出带宽、存储、处理器受限 业务负载分布不均衡 网络拥塞会导致性能下降 分组在路由器上的排队延迟和丢弃概率增大 源主机大量重传分组 网络有效吞吐量下降（Good Throughput） Good Throughput Packets Sent Desirable Congested Perfect Capacity of subnetwork 流量控制与拥塞控制：前者只与发送方和接收方相关，避免快速的发送方淹没慢速的接收方；后者与发送方和网络中的路由器相关，避免发送方的发送速率超过网络（路由器）能够承载的最大容量

解决方案 开环（Open Loop）：系统设计阶段 闭环（Close Loop）：系统运行阶段，基于反馈环路的概念 用良好的设计来解决问题，尽量确保拥塞从一开始就不会发生 闭环（Close Loop）：系统运行阶段，基于反馈环路的概念 监视系统，检测何时何地发生拥塞 将该信息传递到能采取行动的地方 调整系统运行以缓解拥塞 指示网络拥塞的参数：分组丢失/重传率、平均队列长度、平均分组延时

虚电路网络中的拥塞控制 用户事先与网络服务提供商协商好服务等级，在虚电路建立过程中预留相应的资源 接纳控制（Admission Control）：如果网络出现拥塞，拒接建立新的虚电路 虚电路建立时绕开发生拥塞的区域 Congestion Virtual Circuit A B

数据报网络中的拥塞控制 抑制分组 源抑制：当路由器发生拥塞时，发送抑制分组给源主机，其中指明原分组的目的地址；源主机收到抑制分组后，减慢到指定目的地的流量 逐跳抑制：抑制分组将对其通过的每跳都起作用 A B C E F D A B C E F D 抑制分组 抑制分组 反应速度快，要求中间节点有足够的缓存区 反应速度慢

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连 通过拥塞控制可以提高网络的性能，从而为更多的用户提供服务；但是对于使用网络的用户来说，如何保证其网络业务特别是多媒体业务的服务质量是一个非常重要的问题，而且也是用户评价网络好坏的一个关键因素。

服务质量度量参数 带宽或者传输速率 延迟 延迟抖动 分组丢失率 平均带宽或速率、 峰值带宽或突发速率 Fraction of Packets 应用 带宽 延时 延时抖动 可靠性 E-mail low high File transfer medium High Web access Remote login Audio on demand Video on demand Fraction of Packets Delay Minimum delay 带宽或者传输速率 平均带宽或速率、 峰值带宽或突发速率 延迟 延迟抖动 分组丢失率

支持服务质量网络基本要素 服务等级协议：事先在用户-网络运营商、网络运营商-网络运营商之间协商好的服务质量的水平 接纳控制：接入网入口路由器根据可用资源状况来决定是否给用户提供服务 流量调节：路由器检查用户的业务是否满足服务等级协议中约定的服务质量水平，若不满足，则对其进行整形 流量控制：路由器通过队列管理和调度等机制来实现资源的分配，保证用户能够获得服务等级协议中约定的服务质量水平 流量调节 转发 流量控制 输入端口 输出端口 接纳控制 管理机构 支持QoS 路由器

漏桶和令牌桶 在服务等级协议中描述用户的服务质量需求 常用令牌桶描述法（TOKEN_BUCKET_TSPEC）：平均速率、突发速率、突发长度（字节）、最大分组长度、最小分组长度 在流量调节中，对用户的业务进行测量，并且使其特性遵循服务等级协议约定，也称为业务量整形（Traffic Shaping）

漏桶算法（1） 漏桶算法：Leaky Bucket 只要桶中有水，水流出的速率就是常数 桶中没有水的时候，水流出的速率为0 桶满以后，往里面流的水会溢出

漏桶算法（2） 应用于分组传输的漏桶算法 平滑突发业务流：不论输入的速率为多大，输出速率始终是常数 以恒定的速率ρ发送

漏桶算法（3） 算法过程 1）将漏桶看做是一个有限长度的队列，以字节为单位计数，当分组到达的时候，如果队列中还有空间的话，就被添加到对列的尾部，否则该分组将被丢弃 2）在每一个嘀嗒周期，首先将计数器初始化为n，如果队列中第一个分组的字节数少于计时器的当前值，则将分组发送出去，并且将计数器减去该分组的字节数。然后对下一个分组执行同样的过程，直到出现计数器的值小于队列中的分组的长度为止。此时，传输过程终止，直到下一个嘀嗒再开始 3）到达下一个嘀嗒的时候，计数器被重置，执行步骤2），再次开始分组发送过程

漏桶举例 计算机以25M字节/秒速率产生数据，向网络发送1M字节的数据（即以25M字节/秒速率发送了40毫秒），而网络的最佳传输速率不超过2M字节/秒 为了降低传送速率取漏桶输出速率ρ=2M字节/秒，容量C=1M字节，因此1M字节的数据将传输500毫秒

令牌桶算法（1） 令牌桶：Token Bucket ρ 桶中保存的是令牌，每隔T秒产生一个 只有当桶中有令牌时才能传输数据 允许突发流量 Arriving packets ρ C 假设： S:突发长度（秒） C: 令牌桶容量（字节） M：最大输出速率（字节/秒） ρ ：令牌产生速率（字节/秒） C+ρS = MS S=C/(M-ρ)

令牌桶算法（2） 算法过程 1）每个令牌桶维护一个字节计数器，每隔T秒，计数器的值增加K字节，这就相当于往桶中放一个令牌，一个令牌代表了传输K字节的权利，令牌速率为ρ=K/T（字节/秒）。假设桶的大小为C字节，当计数器的值大于C字节时，就会发生溢出，需要注意的是，这里溢出丢弃的是令牌，而不是数据 2）当有分组等待发送时，如果计数器的值大于当前分组的长度，则发送该分组，并且将计数器的值减去分组长度。如果还有分组等待发送，继续执行上面的过程，直到计数器的值小于分组长度为止

令牌桶举例 计算机以25M字节/秒速率产生数据，向网络发送1M字节的数据（即以25M字节/秒速率发送了40毫秒），而网络的最佳传输速率不超过2M字节/秒 设突发长度为S秒，令牌桶容量C字节，令牌产生速率为ρ字节/秒，计算机最大数据速率M字节/秒。 取C=250,000B，M=25MB/s， ρ=2MB/s C+ ρs=MS S=C/（M-ρ）=11毫秒 剩余的以2M字节/秒发送364毫秒

C=250,000字节 C=500,000字节 C=750,000字节 C=500,000字节令牌桶加10M字节/秒漏桶 25MB/s for 40ms 2MB/s for 500ms 25MB/s for 11ms 2MB/s for 364ms 2MB/s for 228ms 2MB/s for 92ms 2MB/s for 190ms 25MB/s for 22ms 25MB/s for 33ms 10MB/s for 62ms

比较 漏桶算法的输出保持的是严格的均匀速率，不管业务流量的突发程度如何 令牌桶算法在大量突发数据到来的时候，允许输出流适当的加快 在漏桶算法中，不允许将空闲时的发送许可权保存起来以便发送大的突发数据（每个时钟嘀嗒后，漏桶的字节计数器都将被重置） 令牌桶算法在大量突发数据到来的时候，允许输出流适当的加快 可以将发送许可权保存起来，直到到达桶的最大尺寸。这也就意味着只要突发数据不超过桶的大小，就可以一次发送出去 在漏桶算法中，桶中填充的是数据，所以当桶填满后将丢弃分组，而在令牌桶中，桶中填充的是令牌，所以当桶填满后将丢弃令牌，相当于是传输许可，而不是分组

Chapter 5 网络层 5.1 向传输层提供的服务 5.2 路由算法 5.3 拥塞控制 5.4 服务质量 5.5 网络互连

网络互连的目标 实现不同网络中网络节点之间的通信

IP（Internet Protocol） 网络互连 我们这里将关注不同网络之间的互连，不同网络是指网络所采用的数据链路层及物理层协议不同，通过采用相同的网络层协议实现这些网络之间的互连互通，对于Internet，这个协议就是IP，使用的网络互连设备为路由器 IP（Internet Protocol） 802.3 802.11 ATM PPP V.90 FDDI

分段 不同的网络可能具有不同的最大数据传输单元（MTU：Maximum Transmission Unit），这也就意味着路由器接收到的分组如果大于转发网络的MTU时，需要对分组进行分段 何处进行分段重组？路由器处或者目的主机处

习题 6，9，21，22，26，28