计算机网络笔记 五.网络层

发表于 更新于

概述

主要功能:

  • 网络互连: 处理不同类型网络互连时出现的问题
  • 寻址: 找到地址标识的节点. 寻址建立在路由的基础上.
  • 路由 Routing: 根据数据的目的地址, 确定到目的网络的最佳路径

相关协议: ATM, IP.

主要设备: 路由器, L3 交换机.

网络层向传输层提供的服务

网络层的必要性:

  • 相距较远的局域网之间的互联互通需要有结构化的统一地址编排, 而 MAC 地址是硬件地址, 与位置无关, 无法用来路由.
  • 二层交换机不隔离广播域, 网络规模较大时易形成广播风暴.

网络层的设计目标:

  • 服务应该与通信子网的技术无关
  • 对传输层而言, 通信子网的数量, 类型和拓扑结构是隐蔽的
  • 网络地址应采用统一的编号模式

争论: 网络层提供面向连接的服务还是非连接的服务

无连接的服务:

  • Internet 社区: 高效, 可扩展, 网络简单, 终端智能
  • 数据报网络: IP

面向连接的服务:

  • 电话公司: 便于管理, 提升服务质量, 网络智能, 终端简单
  • 虚电路网络: ATM

无连接的服务和面向连接的服务都使用存储转发.

数据报网络

来自传输层的数据经过网络层处理后直接发送.

每个分组中携带完整的目的地址, 路由器根据该地址查找转发表来实现分组转发

数据报网络的特点:

  • 每个分组的寻路是独立的, 可以合理利用网络资源
  • 如果途中一个节点或一条链路故障, 可以给分组重选路由
  • 分组头需要包含地址字段, 也会增加开销 (overhead)
  • 各分组途径的路径可能不同, 可能出现后发先到
  • 分组必须有生存时间限制, 生存期满时分组被抛弃, 防止在网络内死转

虚电路网络

分组在发送前建立虚连接或者虚电路 (VC, Virtual Circuit), 即在源和目的主机之间的每个交换机上建立「连接状态」.

分组只携带链路范围内有效的 VCI (VC Identifier), 在交换机上标识自己所属的 VC.

服务质量保证: 在建立连接阶段确保每条虚电路能有足够的资源, 以保证带宽, 延时等需求.

特点:

  • 一条物理链路可以对应多条逻辑信道
  • 一条虚电路由各物理链路上的逻辑信道级联而成, 占用了节点上的一条逻辑信道实际上是占用了该节点上缓存器内的一个存储空间
  • 分组靠逻辑信道号 LCN 选择路由, LCN 只有局部意义, 所以减少了分组头标的开销和处理的复杂度
  • 有接入控制, 能有效防止拥塞

虚电路与数据包的比较:

问题 数据报 虚电路
连接建立 不需要 需要
路由与转发 每个分组都包含源/目的地址, 独立路由, 路由器根据分组的目的地址进行路由转发 建立连接时需要路由, 一旦建立逻辑通道, 后续分组都根据分组头的逻辑通道号转发
路由器状态 不保留分组路由过的状态信息 路由器需要保留每个连接的状态信息, 以便后续分组的转发
分组路径与到达顺序 同一流的分组可能沿不同的路径到达目的端, 有可能乱序 同一流的分组沿建立好的虚电路到达按序目的端
路由器故障影响 通过相邻节点的路由表更新, 能迂回故障节点 故障路由器上的所有连接都将中断
服务质量 较难提供 易于在建立连接时在路径上的各个节点预留资源
拥塞控制 较难提供 在建立连接时, 可根据网络的资源选择路径, 避免网络拥塞

路由算法

路由 Routing: 找到从源主机到目的主机 (所在网络) 的「最佳」路径的过程, 基于路由算法得到路由表.

转发 Forwarding: 在路由器内部将分组从输入端口转发到输出端口的过程, 基于转发表.

注: 虽然路由算法找到的是「路径」, 但是对于执行路由算法的路由器来说, 由于分组采用逐跳转发, 所以只需要在路由表中指定转发的下一跳节点即可.

路由算法的分类

静态路由/非自适应算法: 事先算好, 适用于用户主机或小规模网络.

动态路由/自适应算法: 根据网络拓扑结构和状态的变化动态调整最优路径, 每个路由器需要动态更新路由表. 适用于动态性大的网络或大规模网络, 算法包括距离矢量算法和链路状态算法.

「最优」: 跳数, 物理距离, 队列长度, 排队延迟, 可用带宽等.

路由算法的图模型

图中的节点表示路由器或网络, 图中的边对应于网络中的链路, 每条边上都有一个相应的开销 Cost.

Cost 是跳数, 物理距离, 队列长度, 排队延迟, 可用带宽等因素的函数.

路由算法即找到开销最小的路径.

距离矢量算法

距离矢量算法, 也称 Bellman-Ford 算法.

距离矢量 DV (Distance Vector):

  • 每个节点都维护一个包含了到所有其它节点的「距离」的路由表, 也称为矢量表.
  • 每个节点都将自己的路由表 (矢量表) 分发给它的邻居节点.

基本思想: 每个节点把自己的所有路由表 (矢量表) 发给邻居节点.

存在的问题:

  • 逐跳扩散路由信息, 对网络状态变化反映速度慢.
  • 路由表只包括下一跳的信息, 存在计数到无穷问题, 适用网络规模受限.

算法过程

初始时每个节点都知道到自己直接邻居节点的距离, 到其它节点的距离被指定为无穷大.

每个节点向它的所有直接邻居节点发送自己的所有路由表信息, 告诉邻居节点自己到其它节点的距离.

A 接收到邻居节点发送的路由表信息, 则 A 计算通过该邻居到其它每个节点的距离, 如果该距离小于自己保存的路由表中到对应节点的距离, 则用该距离和邻居更新路由表

更新消息

在距离矢量算法中, 节点通过发送更新消息向直接邻居节点公告自己到其它每个节点的距离.

两种情况下发送更新消息:

  • 定期更新
  • 触发更新, 一个节点从它的邻居节点接收到消息, 导致改变路由表而引发的更新.

故障

故障发现机制:

  • 节点通过发送控制分组持续检测另一个节点的链路, 并查看是否收到确认.
  • 如果节点在最近几次更新周期中接收不到预期的定期更新, 则确定该链路 (或链路另一端的节点) 发生故障.

故障处理: 最先发现故障的节点会发送更新消息给邻居节点, 将到故障链路或故障节点的距离设置为无穷大.

故障可能导致路由环路.

解决方案:

  • 限制选择一个相对较小的数作为无穷大的近似值, 例如 16, 但这种方法限制了网络的可扩展性.
  • 水平分割 (split horizon), 当一个节点把路由更新发送给邻居节点时, 它并不把从各个邻居节点处学到的路由再回送给该节点. 但水平分割只对两个节点的路由循环有效, 更大的路由循环需要更强的措施.

链路状态算法

  • 主动测试邻接节点的状态
  • 定期地将相邻节点的状态信息传送给所有节点
  • 每个节点都拥有完整的网络拓扑信息, 然后计算到每个节点的最佳路径

该方法也叫最短路径优先 (Shortest Path First) 算法, 简称 SPF 算法.

链路状态 LS, Link State:

  • 每个节点都知道到自己邻居节点的链路状态 (开销).
  • 每个节点到达邻居节点的链路状态信息在整个网络中传播, 因此每个节点都有足够的网络信息来建立一个完整的网络映像, 因此能够找到到达网络中任何节点的最短路径.

链路状态分组 LSP, LS Packet: 在 LS 算法运行过程中, 每个节点创建 LSP, 包含信息:

  • 创建该 LSP 的节点标识 ID
  • 与该节点直接相邻的节点列表, 包括到这些相邻节点的链路状态 (开销)
  • 一个序列号'
  • 这个分组的生存期 (TTL)

链路状态算法的两个过程:

  • LSP 的可靠传播和扩散
  • 节点根据所积累的 LSP 知识的总和进行路由计算

可靠扩散

第一步: 可靠扩散/泛洪 Reliable Flooding.

  • 节点创建 LSP.
  • 节点沿着所有与其直接相连的链路将 LSP 发送出去, 接收到 LSP 的每个节点再沿着除接收链路以外的所有其它与它相连的链路转发出去, 这个过程一直继续, 直到 LSP 到达网络中的所有节点.
  • 相邻路由器之间的 LSP 传递使用确认和重传机制来保证可靠性.

LSP 的产生:

  • 周期性公告
  • 触发式公告: 拓扑结构变化, 意味着一个与节点直接相连的链路或者邻居出现故障
    • 链路故障发现: 链路层协议发现
    • 邻居故障发现: 周期性的「hello」分组发现

LSP 更新:

  • LSP 携带序列号, 节点每产生一个新的 LSP, 就将序列号加 1, 在节点上, 序列号大的 LSP 将替换序列号小的 LSP.
  • LSP 携带生存期 TTL, 每个节点在将接收到的 LSP 扩散到其它节点之前, 对其 TTL 减 1. TTL 为 0 时, 看作是删除该 LSP 的信号.

LSP 开销: 设置大的周期性公告间隔, 通常为几小时.

路由计算

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

Dijkstra 算法略, 忘了去 B 站找个视频看.

距离矢量与链路状态的比较

距离矢量 (DV) 路由算法:

  • 每个节点只和直接相连的节点进行通信
  • 节点向相邻节点告诉它所知道的所有节点的路由信息
  • 节点根据相邻节点的路由信息更新自己的路由表
  • 分布式计算, 计算得到到所有节点的最短路径的下一跳节点
  • 可扩展性差:
    • 距离矢量算法只适用于小规模网络, 为了避免计数到无穷问题, 网络直径一般不能超过 15 跳
    • 与链路状态算法相比, 对网络变化反应较慢

链路状态 (LS) 路由算法:

  • 节点向所有节点告诉其相邻节点的状态信息, 但只告诉它们自己确切知道的信息 (即与其直接相连的链路状态)
  • 每个节点都有一个全局的拓扑结构
  • 根据此拓扑结构计算路由表
  • (相对来说) 可扩展性好, 可靠

拥塞控制

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

路由器的队列溢出, 分组丢失, 礼崩乐坏.

拥塞的后果:

  • 分组延迟和丢包率增大
  • 加大源主机的分组重传
  • 网络有效吞吐量下降

拥塞的原因:

  • 路由器的处理速度, 存储空间, 带宽受限
  • 网络负载分布不平衡
  • 主机发送分组的速率过快

信道利用率指出某信道有百分之几的时间是被利用的 (有数据通过).

网络利用率则是全网络的信道利用率的加权平均值.

延时 D 与网络利用率 U 之间的关系:

D=D01−UD = \frac{D_0}{1-U}

UU: 网络的利用率
D0D_0: 网络空闲时的时延
DD: 网络当前的时延

结论: 信道或者网络利用率过高会产生非常大的延迟, 因此, 一些拥有较大骨干网的 ISP 通常控制他们的信道或者网络利用率不超过 50%, 如果超过了就要考虑扩容, 增大线路的带宽.

拥塞控制与流量控制

拥塞控制:

  • 网络拥塞的直接原因是网络负载的不均衡引起, 例如, 某个路由器的多个输入端口向同一个输出端口传输分组.
  • 拥塞控制是一个全局问题, 涉及的节点包括主机, 路由器.
  • 拥塞发生在网络内, 但对于无连接的网络很难在网络层单独控制拥塞, 因此网络层和传输层共同承担拥塞控制.

流量控制:

  • 接收端或所在网络的接收速度小于发送端的发送速度.
  • 只涉及收发两端, 是局部问题.

注意不要混淆.

拥塞控制的一般原理

从控制理论观点出发, 可以分为两类:

  • 开环控制 (Open Loop), 基于良好的设计.
    • 用良好的设计来解决问题, 尽量确保拥塞从一开始就不会发生
    • 业务量整形: 漏桶算法, 令牌桶算法
  • 闭环控制 (Close Loop), 基于反馈环路的概念
    • 监测系统何时, 何处发生拥塞
    • 将拥塞信息传到能控制拥塞的地方
    • 调整系统操作以缓解拥塞

指示网络拥塞的参数:

  • 分组丢包率/分组重传率
  • 平均队列长度
  • 平均分组延时

漏桶算法

Leaky Bucket

只要桶中有水, 水流出的速率就是常数; 桶中没有水的时候, 水流出的速率为 0; 桶满以后, 往里面流的水会溢出.

将漏桶看做是一个有限长度的队列, 以字节为单位计数, 当分组到达的时候, 如果队列中还有空间的话, 就被添加到对列的尾部, 否则该分组将被丢弃.

在每一个时间周期, 首先将计数器初始化为 n (漏桶发送速率 × 时间周期, 单位时间能发送的数据量), 如果队列中第一个分组的字节数少于计数器的当前值, 则将分组发送出去, 并且将计数器减去该分组的字节数. 然后对下一个分组执行同样的过程, 直到出现计数器的值小于队列中的分组的长度为止. 此时, 传输过程终止, 直到下一个时间再开始该该分组发送过程.

省流: 总是以恒定速率输出, 溢出的数据被直接丢弃.

例: 计算机以 25MB/秒速率产生数据, 向网络发送 1MB 的数据 (即以 25MB/秒速率发送了 40 毫秒), 而网络的最佳传输速率不超过 2MB/秒, 如果采用漏桶算法, 中间节点进行数据传输的速率和总时间需要多久?

答: 为了降低传送速率取漏桶输出速率ρ=2MB/秒, 容量 C=1MB, 因此, 1MB 的数据将以 2MB/秒的速率传输 500 毫秒.

令牌桶算法

Token Bucket

桶中保存的是令牌, 每隔 T 秒产生一个, 只有当桶中有令牌时才能传输数据.

允许突发流量.

溢出丢弃的是令牌, 而不是数据.

例: 计算机以 25MB/秒速率产生数据, 向网络发送 1MB 的数据 (即以 25MB/秒速率发送了 40 毫秒), 而网络的最佳传输速率不超过 2MB/秒, 如果采用令牌桶算法且令牌桶容量为 250kB, 中间节点进行数据传输的速率和总时间需要多久?

答: 设突发长度为 S 秒, 令牌桶容量 C 字节, 令牌产生速率为ρ字节/秒, 计算机最大数据速率 M B/秒.
取 C=250,000B, M=25MB/s, ρ=2MB/s

C+ρS=MSS=CM−ρ=11msC+ ρS=MS \\ S=\frac{C}{M-ρ}=11ms

剩余数据以 2M 字节/秒发送 364 毫秒.

漏桶算法与令牌桶算法的比较

漏桶算法的输出保持的是严格的均匀速率, 不管业务流量的突发程度如何. 在漏桶算法中, 不允许将空闲时的发送许可权保存起来以便发送大的突发数据, 每个时钟嘀嗒后, 漏桶的字节计数器都将被重置.

令牌桶算法在大量突发数据到来的时候, 允许输出流适当的加快. 可以将发送许可权保存起来, 直到到达桶的最大尺寸, 意味着只要突发数据不超过桶的大小, 就可以一次发送出去.

在漏桶算法中, 桶中填充的是数据, 所以当桶填满后将丢弃分组; 在令牌桶中, 桶中填充的是令牌, 所以当桶填满后将丢弃令牌, 即丢弃传输许可, 而不是分组.

拥塞控制的闭环策略

闭环控制 Close Loop:

  • 检测到拥塞时, 就发一个分组给源端或向所有主机广播.
  • 在每个分组头中保留一个位或域, 当拥塞超过一定值时, 路由器就在该位或域上填上拥塞信息通知网络节点.
  • 由主机或路由器发送询问分组打听拥塞情况.

虚电路网络中的拥塞控制

用户事先与网络服务提供商协商好服务等级, 在虚电路建立过程中预留相应的资源.

节点上的接纳控制 (Admission Control): 如果网络出现拥塞, 拒接建立新的虚电路.

虚电路建立时绕开发生拥塞的区域.

数据报网络中的拥塞控制

抑制分组:

  • 源抑制: 当路由器发生拥塞时, 发送抑制分组给源主机, 其中指明原分组的目的地址; 源主机收到抑制分组后, 减慢到指定目的地的流量.
  • 逐跳抑制: 抑制分组将对其通过的每跳都起作用.