LOADING

加载过慢请开启缓存 浏览器默认开启

计网学习笔记(5)：网络层

2025/5/8 专业学习 private 计算机网络

网络层的位置和功能

网络层是处理端到端(end-to-end)传输的最底层！

Hop(跳)：

主机之间通信，经过一个路由器就是一跳。

网络层的主要功能：

  1. Internetworking 网络互联：将异构的网络实现互联，向上(传输层)提供统一的接口；
  2. Addressing 编址：保证设备之间接口地址（IP Address）唯一且格式统一；
  3. Packeting 组包：将上层需要传输的数据封装为包(Packet)；
  4. Routing 路由：选路，决定数据包的下一条，通过路由器(Router)实现；
  5. Fragmenting 分段/分片：由于不同数据链路层支持的最大数据长度不同，需要适应不同的数据链路层，对数据包进行分段；

网络层提供的服务

网络层需要向上(传输层)提供服务，要求：

  • 路由技术独立：即传输层不需要知道路由器的技术，网络层提供的接口是透明且统一的；
  • 传输层对路由完全透明：不需要看到路由技术和数据包是如何路由的；
  • 传输层获得的网络地址的格式是统一的；

又分为：

  • Virtual Circuit 虚电路：Connection-Oriented，面向连接的；
  • Datagram 数据报：Connectionless，无连接的；

两者都属于分组交换 Packet Switching，区别是：

  • Datagram 数据报：
    • 每一个包需要携带目的地的完整地址；
    • 路由器通过路由表转发包，路由表是动态更新的；
    • 包到达目的地可能是乱序的，即每个包选择的路径可能不相同；
  • Virtual Circuit 虚电路：
    • 在数据包进行传输之前，网络先建立了一条端到端的虚拟电路；
    • 传输过程中，数据包携带虚拟电路地址 VCI(Virtual Circuit Identifier)，作为地址标识，这比标准的地址短的多；
    • VC建立后，所有包需要遵循VC的路径进行路由，所以包到达目的地是一定是按序的；

路由

路由表 = 路由算法 + 路由协议；根据路由算法和路由协议产生和更新路由表(Routing Tables)，根据路由表进行选路，转发数据包

1. 路由算法

1.1 设计路由算法的原则

  • 正确性；
  • 简单性；
  • 健壮性；
  • 可快速收敛到稳定状态；
  • 公平性；
  • 最优策略：最小化转发延时、最大化网络吞吐量；

1.2 路由算法的分类

  • 静态路由 Nonadaptive/Static Routing：
    • 提前计算出路由表；
    • 往往不会改变，需要手动维护；
    • 不能根据网络实时流量和拓扑结构的变化动态调整；
  • 动态/自适应路由 Adaptive Routing：
    • 能适应网络拓扑 Topology 和业务量 Traffic 的变化；

1.3 一些概念

  • 最优化原则：最优路径上的任意两点间的路径也是最优的；
  • 宿树/汇集树 Sink Tree：以目的地节点为根，由所有源节点到目的节点的最优路径路由构成；
    • 由于是树，显然是无环的，不存在无限的跳数；

1.4 路由思想和策略

以下阐述的只是一些路由思想，或者说寻找最优路径的思想，但在实际环境中并不能有效工作；

  • 最短路算法：Dijkstra 算法
    1. 建立有向加权图；
      • 节点为路由器，注意没有主机；
      • 边为通信线路；
      • 边权可以为跳数、传输时延、物理距离等等；
    2. 通过 Dijkstra 算法寻找最短路；
  • 一些选路策略：
    • 固定查表选路 Fixed Routing；
    • 泛洪 Flooding：
      • 其基本过程如下：
        • 将数据包转发给每个邻居；
        • 邻居再将收到的数据包转发给除了来路之外的所有链路(防止数据包原路返回)；
      • 优点：
        • 泛洪显然不需要路由表，简单粗暴；
        • 不需要网络信息；
        • 具有鲁棒性，所有路径都会被尝试，所有节点都会被到达，所以至少有一个数据包会按照最短的路由达到目的地；
        • 在建立路由表时可能较为有用；
      • 缺点：
        • 产生大量重复的数据包；
        • 最终可能有一个或多个重复的数据包到达目的节点；
      • 限制泛滥手段：
        • 跳计数器 Hop Counter：
          • 每个数据包携带一个 Hop Counter，一般由发送方初始化为源地址到目的地址的距离或子网的网络半径；
          • 每经过一跳，Hop Counter 减 1；
          • 当 Hop Counter 为 0 时，丢弃该包；
        • 序列号 Sequence Number：
          • 发送方在每个包前添加序列号；
          • 每个路由器会记录每个发送方目前的最大序列表，表示该序列号已经通过该路由，从而避免重复转发；
    • 随机选路；
    • 自适应选路；

1.5 DVR(距离矢量选路 Distance Vector Routing)

1.5.1 执行步骤

  • 每个路由维持一个路由表，包括：
    • 到其他路由的最短距离；
    • 到该路由使用的下一条的接口；
  • 每个路由会周期性（RIP：30s）地播报自己的路由表；
  • 路由器会根据收到的邻居的路由表更新自己的路由表；
  • 如果在一段时间内（RIP：180s）都没有收到某个路由器的路由表，则将该路由器从自己的路由表中删除（将距离设置为 \(\infty\) ）；
  • 当迭代至各个路由器的路由表均不发生变化后，则认为构建路由表结束；

1.5.2 特点

  1. 邻接节点之间共享网络信息（路由表）；
  2. 只和初始邻接节点共享信息；
  3. 对所有接口广播信息；
  4. 周期性地广播；

用一句话概括，就是路由器周期性地向所有邻居 广播整个路由表；

1.5.3 问题

  • 收敛速度较慢；
  • “好消息”迅速传遍整个网络，但对“坏消息”反应慢；（React rapidly to good news but leisurely to bad news）；即无穷计数 Count-to-Infinity 问题；
  • 按传闻进行路由；（Rumor based routing）

无穷计数问题：

大致的情况就是，节点A下线后，其余节点之间由于只知道距离，不知道路径，相互传递距离，反复更新距离（比如上图B没收到A但收到C的路由表，认为可以通过C到达A，于是更是路由表中到达A 的距离为 1 + 2 = 3，然后C又认为可以通过B到达A，如此循环更新，直到 \(\infty\) ）；

RIP协议中规定：权重(按跳数 Hop 计) > 16，则认为是 \(\infty\)，即认为节点已经断开；

注：上面提到的RIP，并非R.I.P(Rest in Peace)，全称是 Routing Information Protocol，属于一种路由协议，该协议使用 DVR 路由算法；

与DVR不同，DVR只会向领接路由器发送路由表，而 LSR 中，每个路由器向网络中的所有路由器共享信息；当路由器在本地构建已知的最优网络拓扑图后，发送一个链路状态包 Link-State Packet 给所有路由器（Flooding）；主要特点如下：

  1. 共享整个网络的拓扑结构信息；
  2. 向网络中的所有路由器共享；
  3. 当网络拓扑结构改变时进行共享；

1.6.1 执行步骤

对于每个路由器：

  1. 从相邻的节点学习：
    1. 本路由器广播(用于广播网络)/多播(用于点对点链路)一个 HELLO Packet 给邻接节点；
    2. 邻接节点收到 Hello 包后，回复一个包含自己名字(Route IDs，全网唯一)的包；
  2. 测量通信线路开销：
    1. 通过 Echo Packet 测量往返延时RTT；
    2. 或测量信道带宽等参数；
  3. 构建 Link-State Packet：
    2. Seq 字段表示序列编号，用于检查路由器收到的 LSP 是否是新的：
      1. 如果是新序列编号的 LSP，则继续 Flooding；
      2. 如果是重复编号的或序列编号比已经收到的最大编号小的 LSP，则丢弃；
    3. Age 字段表示寿命，目的是为了避免 LSP 包无限泛滥，用于删除循环的路由；
    4. 当周期性地或监听到某些时间（比如某节点下线）等事件后构建 LSP 包；
  4. 发送 Link-State Packet：
    1. 由于需要实现可靠发送，所以采用前面提到的泛洪策略；
    2. 每个节点都有错误侦测机制，收到正确的数据包后会回复确认包；
  5. 计算新的路由：
    1. 本路由器收到所有的 LSP 包后，在本地运行 Dijkstra 算法，计算出通往每个目的节点的最短路径，并保存到路由表中；

1.6.2 采用 LSR 的协议

  • IS-IS 协议；
  • OSPF 协议；

1.7 层次/分级选路 Hierachical Routing

将距离较近的比如同一单位内的路由划分为同一个域 Region，在整个网络内先按照域进行路由，进入域后，才选路至路由器；

拥塞控制 Congestion Control

1. 拥塞

简单来说，拥塞 Congestion 就是网络的负载（同一时间发送到网络的数据包）超过了网络的可用资源（ CPU 处理速度，Buffer 缓冲队列长度，Bandwidth 链路带宽）；拥塞的症状（判断网络拥塞的指标）主要有：

  • Long Delay；
  • Lost Packet 较高的丢包率；

上述症状并不能用来判断所有网络是否出现拥塞；无线网络产生丢包还要考虑误码等情况；

注意与流量控制进行区分，流量控制只是两个站点（发送方和接收方）之间进行本地的协调；但是拥塞控制的范围是整个网络，是一个全局的问题；

2. 解决方式

解决方式主要分为以下5种：

  1. 网络供给 Networking Provision；
  2. 业务感知路由 Traffic aware-routing；
  3. 准入控制 Admission control；
  4. 流量限制 Traffic throttling；
  5. 负载掉落 Load shedding；

从产生拥塞的问题来看，前两种属于增加资源，后三种属于减少负债；
从作用的时间节点来看，前三种属于预防性控制，后两种属于反应性(Reactive)措施；

2.1 流量调节/业务量减速 Traffic throttling

这是基于反馈的解决方案，需要路由器能够感知拥塞；其基本步骤如下：

  1. 拥塞检测：
    1. 检测输出链路利用率：不够精确；
    2. 排队分组，即计算路由器中缓存的数据包数量；
    3. 计算分组丢包数量：但是太迟；
    4. 估计队列延时 queuing delay：通过EWMA(Exponentially Weighted Moving Average 指数加权移动平均)计算，即\(d_{new} = \alpha d_{old} + (1-\alpha)s\)，其中 \(\alpha\) 是平滑因子（越大越平滑），\(s\) 是最近采样的队列长度；
  2. 拥塞通知：路由器需要通知数据包的发送方产生拥塞，让发送方降低业务量，主要有以下几种方式：
    1. 抑制分组 Choke Packet：路由器会发送一个 Choke Packet 给源节点（发送方），包含产生拥塞的目的节点信息；
      • 发送方发出的原始数据包会被标记，避免产生更多的 Choke Packet；
      • 实际应用中效果并不好，因为网络已经拥塞了还需要产生 Choke Packet 并在路由间传输；
    2. ECN(Explicit Congestion Notification 显式拥塞通知)：
      • 在 IP 和 TCP 协议中被使用；
      • 在 IP Packet Header 中专门设置了 2bits 作为拥塞控制比特位；
        • 默认设置为 00；
        • 在传输过程中，如果路由器检测到拥塞，将其设置为 11；
        • 当该数据包发送到目的端节点后，目的端节点通过传输层（端到端通信）发送 Congestion Signal 给源端节点；
  3. 业务量限制/调节：收到 Choke Packet 后，源节点会减少发送到某个目的地节点的业务量；
    • 减少业务量的方式包括但不限于减小发送窗口；

问题：当拥塞恢复时，路由器不会通知端节点恢复业务量？

需要发送方自身进行推测和试探；比如 TCP 的 AIMD 机制（慢启动 + 加性增大），当拥塞时，TCP 会将发送窗口大小减半，然后逐步增加发送窗口大小，如果没有再次丢包，则继续慢慢加大发送窗口，如果丢包则再次降速。

2.2 Loading Shedding 负载掉落

关键问题是选择丢弃哪些数据，需要根据不同的应用场景进行选择。

RED(Random Early Detection 随机早期检测)：

  • 路由器在路由完全失效前，就随机丢弃一部分包；
  • 路由器并不会（显式）通知源节点，而是直接丢弃选中的包，但是源节点因为没有收到 ACK，检测到丢包后，会感知到拥塞的信息，并降低发送速度。
  • 上述方法即属于隐式通知；

举个例子：
1. 发送方此时发送了窗口内的 4、5、6 三个序号的数据帧；
2. 路由器收到序号为 4 的数据帧时，接收并回复 ACK 4；
3. 路由器收到序号为 5 的数据帧时，因为 RED 机制选中而被丢弃；
4. 路由器收到序号为 6 的数据帧时，它选择缓存该帧，但由于它期望收到序号为 5 的帧，所以它会回复 ACK 4；
5. 发送方收到了两个重复的 ACK 4，那么它会知道，后面发送的数据可能丢包了。

注：TCP协议中，规定源节点如果收到 3 个及以上相同的 ACK，则认为发生拥塞；

服务质量 Quality of Service

1. QoS 参数

第一章 计算机网络概述中已经讲过，QoS主要包括以下4个参数：

  • Reliability：可靠性，包括错误率和丢包率；
  • Delay；
  • Jitter；
  • Bandwidth；

针对不同的应用场景，对参数的要求各不相同，需要提供个性化的服务。

2. 提升服务质量的技术

2.1 流量整形 Traffic shaping

实际网络中，往往会出现突发流量 Traffic Burst。平均流量基本固定，但是短时间内的瞬时流量可能非常大。而流量整形的作用就是去除或减少突发流量，使得实时传输速率接近平均速率，其主要涉及以下2个算法。

漏桶 Leaky Bucket

事实上，桶就是一个 Buffer 队列，通过匀速从队列中拿出数据分组，实现匀速传输。如果桶满，则丢弃新来的数据或等待队列空。

令牌桶 Token Bucket

  • 路由器匀速产生令牌，如果令牌桶满则丢弃多余的令牌；
  • 数据包到达路由器的队列后，需要消耗令牌进行发送，一个 Token 对应 一个 Packet；
  • 令牌桶并没有数据队列的缓存限制，不会丢弃数据帧；
  • 令牌桶能接受一定的突发流量，比如突发流量到达，可以一次性消耗所有令牌（跟令牌桶的大小有关）；

如何计算经过令牌桶后的突发数据的持续时间？

令：

  • 突发数据的持续时间为 \(S\) sec；
  • 令牌桶的容量为 \(B\) Bytes；
  • 令牌的产生速率为 \(R\) Bytes/s；
  • 最大的输出速率为 \(M\) Bytes/s；

则有以下关系：

\[ B + R \times S = M \times S \]

即：

\[ S = \frac{B}{M - R} \]

2.2 分组调度 Packet Scheduling

先进先出队列 FIFO Queuing

  • 先到达的包先发出；
  • 后到达的包可能会因为队列空间不够而被丢弃；

优先级队列 Priority Queuing

  • 到达的数据包先经过一个分类器 Classifier，按照优先级不同存入不同的队列；
  • 同样，后到达的包如果对应的优先级队列已满，同样丢弃；
  • 如果空闲，那么高优先级队列中的数据包先被处理和发送；
  • 对低优先级的数据不公平，如果高优先级队列一直有数据需要发送，那么低优先级的数据无法发出；

公平队列 Fair Queuing

  • 对于每一个流（如果一系列包经过相同的路由，那么称其为流 Flow）都有一个队列，循环处理和发送每个队列中的数据包；

公平加权队列 Weighted Fair Queuing

  • 根据优先级对数据进行加权，一般高优先级对应较大的权重；
  • 循环按照权值处理每个优先队列，比如权值为3的则一次发送3个包，权值为2的一次发送2个包；

以下是教材的一个实现示例，实际上这种思想的实现方式并不唯一。

每个包的到达时间和长度是路由器已知的，发送完成的时间根据以下公式给出：

\[ Finsh\_time_i = max(Arrival\_time_i, Finish\_time_{i-1}) + \frac{Lengh_i}{Weight_i} \]

2.3 Admission Control

暂略；

2.4 Integrated Services

暂略；

2.5 Differentiated Services

暂略；

3. QoS的一个例子——保证转发 Assured Forwarding

  1. 所有的业务被划分为4个优先级；
  2. 通过 Traffic Policer 的令牌桶机制进行流量整形；
  3. 在经过 Traffic Policer 时，每个优先级下又被分类为3种优先级，或者说丢弃优先级，即丢包的可能性大小；
  4. 所以最终实际上有12种服务等级；
  5. 在每个 Packet 的 IP Header 的 ToS 字段(Type of Service 服务类型) 会携带 DSCP(6bits) + ECN(2bits)，其中：
    • DSCP(Differentiated Services Code Point 服务等级)；
    • ECN(Explicit Congestion Notification 拥塞控制)；
  6. 路由器接收到被划分后的包，根据以下2种机制进行分组调度：
    • WFQ(Weighted Fair Queuing 加权公平队列)：按照优先级进行公平调度；
    • RED(Random Early Detection 随机早期检测)：采用主动丢弃机制，这里被丢弃的概率就是前面划分的丢弃优先级；

互联 Internetworking

不同网络的协议不同，在不同网络间传输信息，需要实现网络互联。

1. 分段/分片 Fragmentation

不同的网络的 MTU(Maximun Transmission Unit 最大传输单元) 不同，在网络层传输数据时，需要进行分片处理。