网络层概述

网络层的功能

  • 转发:路由器将输入链路到达的分组移动到适当的输出链路。是数据平面实现的唯一功能。

  • 路由选择:网络层决定分组从发送方流向接收方时采用的路由或路径。是控制平面实现的唯一功能。

转发发生的时间很短,通常由硬件实现。路由选择发生的时间长的多,通常用软件实现。

数据平面的方法

每台网络路由器中都有转发表。路由器通过使用分组的首部值在转发表中索引来转发分组。

控制平面的方法

传统方法

路由选择算法决定了插入该路由器转发表的内容。每一台路由器中的路由选择算法与其他路由器中的路由选择算法通信,计算出转发表的值。

SDN(Software-Defined Networking) 方法

路由选择功能与路由器在物理上分离,路由器只负责转发,远程控制器计算并分发转发表。

网络服务模型

因特网的网络层提供尽力而为服务,即摆烂服务,什么都不保证。

数据平面

路由器工作原理

路由器体系结构

  • 输入端口

    线路端接(物理层) -> 数据链路处理(链路层) -> 查找、转发、排队

    查找转发表是在输入端口实现的,使用最长前缀匹配规则,用分组目的地址的前缀与转发表中表项进行匹配。

  • 交换结构

    经内存、总线或互联网络交换,将分组从输入端口交换到输出端口。

  • 输出端口

    排队 -> 数据链路处理(链路层) -> 线路端接(物理层)

  • 路由选择处理器

排队

  • 输入排队

    如果交换结构不能快得使所有到达的分组无时延地通过,那么输入队列中的某目的地端口没有竞争的分组可能因为队列前端分组的目的地端口存在竞争而被迫需要等待。这种现象叫做线路前部 (HOL) 阻塞。

  • 输出排队

    单纯就是来的太快堵住了。

内存不够缓存分组时需要选择丢弃分组,有时在填满缓存之前就丢弃分组或者给分组打标记是好的,这种策略被称为主动队列管理 (AQM)。

缓存数量 $B=\frac{RTT \times C}{\sqrt{N}}$,$RTT$ 是平均往返时延,$C$ 是链路容量,$N$ 是 TCP 流的数量。

分组调度

  • 先进先出 (FIFO / FCFS)

  • 优先权排队

    分组被分类放入优先权类,优先权高的先传输,同优先权 FIFO。

  • 循环和加权公平排队
    加权公平排队 (Weighted Fair Queuing, WFQ) 是一种通用形式的循环排队。给所有到达的分组分类,并给每个类 $i$ 分配 $w_i$ 的权值,根据权值大小给类排序,轮流传输类内的分组,如果发现类为空就移向下一个类。WFQ 保证第 $i$ 类分配到 $\frac{w_i}{\sum w_j}$ 的带宽。

网络协议:IPv4、寻址、IPv6 及其他

IPv4 数据报

IPv4

  • 版本号:IP 协议版本。
  • 首部长度
  • 服务类型 (TOS):区分不同类型的 IP 数据报。
  • 数据报长度:总长度,以字节计。16 bits,IP 数据报理论最大长度 65535 字节。
  • 标识、标志、片偏移:与 IP 分片有关。
  • 寿命 (TTL):每当一台路由器处理数据报值减 1,为 0 时数据报丢弃。
  • 协议:到达目的地时把数据部分交给哪个运输层协议。6 为 TCP,17 为 UDP。
  • 首部检验和:路由器计算首部检验和并和数据报中的值比较,出错就丢弃错误数据报。每台路由器要重新计算首部校验和并写入。
  • 源和目的 IP 地址
  • 选项
  • 数据 (有效载荷)

一个 IP 数据报有 20 字节的首部(假设无选项),如果数据报承载一个 TCP 报文段,则每个(无分片的)数据报承载 40 字节的首部(再加上 20 字节的 TCP 首部)。

IPv4 数据报分片

一个链路层帧能承载的最大数据量叫作最大传送单元 (MTU),它限制了 IP 数据报的长度。一旦 IP 数据报过长就需要分片,在端系统中重新组装。

发送主机给发送的数据报贴上标志号,每次 +1。当路由器需要分片时,形成的每个片具有初始数据报的源地址、目的地址和标识号,使用偏移字段指定该片应放在初始 IP 数据报的哪个位置,最后一个片的标志 bit 被设为 0,其他片被设为 1。

IPv4 编址

主机或路由器与物理链路的边界叫作接口。一个 IP 地址与一个接口相关联。

因特网的地址分配策略被称为无类别域间路由选择 (CIDR)。

形如 a.b.c.d/x 的 IP 地址,x 被称为子网掩码,表示左侧 x bit 定义了子网地址,称为前缀。一个组织通常分配一段连续的地址,享有共同的前缀,剩余的 32 - x bit 是用于区分该组织内部设备的。

一台主机发出一个目的地址为 255.255.255.255 的数据报时,该报文会交付给同一网络的所有主机。

动态主机配置协议 (DHCP)

DHCP 被称为即插即用协议或零配置协议,需要在子网中有一台 DHCP 服务器或 DHCP 中继代理(通常是一台路由器)。

DHCP 客户与服务器交互共 4 步:

  • DHCP 服务器发现:客户在 UDP 分组中向端口 67 发送 DHCP 发现报文,目的地址使用 255.255.255.255,源地址使用 0.0.0.0 。
  • DHCP 服务器提供:DHCP 服务器收到一个 DHCP 发现报文,用 DHCP 提供报文作出响应,包含发现报文的事务 ID、向客户推荐的 IP 地址、网络掩码以及 IP 地址租用期。仍然使用广播地址 255.255.255.255 。
  • DHCP 请求:客户从一个或多个服务器提供中选择一个,向选中的服务器提供用 DHCP 请求报文进行响应。
  • DHCP ACK:服务器用 DHCP ACK 报文对 DHCP 请求报文响应,证实所要求的参数。

网络地址转换 (NAT)

具有专用地址的地域是指其地址仅对该网络中的设备有意义的网络。

NAT 路由器对外界的行为就如同一个具有单一 IP 地址的单一设备。NAT 利用 NAT 转换表将分组转发到内部主机,表项中包含了端口号及 IP 地址。

IPv6

IPv6

  • 地址容量被扩大了。引入了任播地址,可以使数据报交付给一组主机中的任意一个。
  • 首部长度被固定为 40 字节。
  • 加入了流标签,占 20 bits,用于给属于发送方要求进行特殊处理的特殊流的分组加上标签。
  • 流量类型类似于 IPv4 中的 TOS。
  • 下一个首部标识数据报中的内容需要交付给哪个协议,与 IPv4 协议字段使用相同的值。
  • 跳限制:转发数据报的每一台路由器将它 -1,到 0 时该数据报被丢弃。
  • IPv6 不允许分片,而是让发送方发送一个更小的 IP 数据报。
  • 选项和首部检验和也没有了。

从 IPv4 迁移到 IPv6 的方法包括建隧道。将 IPv6 的数据报套在 IPv4 数据报中,借助 IPv4 路由器传送到另一台 IPv6 路由器。

通用转发和 SDN

匹配加动作转发表在 OpenFlow 中称为流表,表项包括:

  • 首部字段值的集合
  • 计数器集合
  • 动作集合

控制平面

路由选择算法

把网络抽象成图,节点是路由,边是物理链路。

  • 集中式:链路状态 (LS) 算法 / 分散式: 距离向量 (DV) 算法
  • 静态 / 动态
  • 负载敏感 / 负载迟钝

链路状态路由选择算法 (LS)

链路状态广播使得所有节点都具有该网络的统一、完整的视图。每个链路状态分组包含了它所连接的链路标识和开销。

然后跑个 Dijkstra。

如果链路开销等于链路上承载的负载,它会变得非对称,可能会出现振荡。解决方案是让每台路由器发送链路通告的时间随机化,使得并非所有路由器同时运行 LS 算法,同时避免了路由器的自同步。

距离向量路由选择算法 (DV)

DV 算法是迭代的、异步的和分布式的。

每个节点 $x$ 维护距离向量 $D_x = [D_x(y): y \in N]$,表示 $x$ 到点集 $N$ 中所有其他节点 $y$ 的开销估计向量。每个节点时不时向每个邻居发送它的距离向量副本。当节点 $x$ 收到邻居节点 $v$ 的距离向量副本,则利用 Bellman-Ford 方程更新距离向量:$D_x(y) = \min{c (x, v) + D_v(y)}$。如果节点 $x$ 的距离向量被改变了,就向所有邻居发送更新后的距离向量。最终 $D_x(y)$ 收敛到最低开销。所以是不是就是跑了下 Bellman-Ford 算法

DV 算法真正想知道的是下一跳路由器邻居节点,其实就是松弛过程中取得最小值的邻居,并用它更新转发表。

DV 算法的无穷计数问题

反转了!考虑链路开销改变,如果链路开销变大,节点更新距离向量过程中由于算法是分布式的,会遇到路由选择环路的问题,即节点松弛过程中使用的距离向量的路径包括了节点本身,导致需要来回迭代巨大多次,这个问题也被称为无穷计数问题。

使用毒性逆转技术可以避免无穷计数问题。它的思想是如果 $z$ 通过 $y$ 路由选择到目的地 $x$ ,则 $z$ 将向 $y$ 通告 $D_z(x) = \infty$,这样 $y$ 就无法经过 $z$ 到 $x$,避免了回路。然而涉及到 3 个或更多节点的环路就寄了。

LS 算法与 DV 算法的比较

LS 算法要求 $O(NE)$ 个报文,复杂度是 $O(N^2)$ 肯定要堆优化到 $O(NlogN)$ 啊。一个 LS 节点只计算自己的转发表,路由计算某种程度上是分离的,具有一定健壮性。

DV 算法只需要向邻居发报文,报文少,但收敛慢,还会遇到选择环路。健壮性也比较拉,可以把不正确的节点计算值扩散到整个网络。

因特网中自治系统内部的路由选择:OSPF

自治系统 (AS) 由一组通常处在相同管理控制下的路由器组成。AS 内运行的路由选择算法叫作自治系统内部路由选择协议。

开放最短路优先 (OSPF):路由器向 AS 内所有其他路由器广播路由选择信息,每台路由器在本地跑 Dijkstra,确定以自身为根节点到所有子网的最短路径树。

当链路状态发生变化,路由器要广播;当链路状态没有发生变化,路由器也要定期广播(至少 30min 一次)。

OSPF 优点:

  • 安全,能鉴别 OSPF 路由器之间的交换。支持简单的和 MD5 的鉴别。
  • 允许使用多条相同开销的路径。
  • 综合支持单播与多播路由选择。
  • 支持在单个 AS 中的层次结构。一个 OSPF AS 可以配置成多个区域,只有一个区域被配置成主干区域,为其他区域之间的流量提供路由选择。主干区域至少包括 AS 中所有区域边界路由器,可能包含了一些非边界路由器。分组先路由到区域边界路由器,通过主干路由到目的区域的边界路由器,再路由到目的地。

ISP 之间的路由选择:BGP

所有的 AS 允许相同的 AS 间路由选择协议,称为边界网关协议 (BGP)。

在 BGP 中,分组路由到 CIDR 化的前缀。BGP 可以为路由器完成两个任务:从邻居 AS 获得前缀的可达性信息、确定到该前缀的“最好的”路由。

通告 BGP 路由信息

每台路由要么是一台网关路由器(直接连接到其他 AS 中的路由器),要么是一台内部路由器(仅连接自己 AS 中的路由器)。

跨越两个 AS 的 BGP 连接称为外部 BGP (eBGP) 连接,相同 AS 中的两个路由器之间的 BGP 连接称为内部 BGP (iBGP) 连接。

网关路由器向其他 AS 的网关路由器发送 eBGP 报文通告前缀 x 的可达性,而其他 AS 的网关路由器又向 AS 中所有路由器发送 iBGP 报文通告前缀 x 的可达性,重复这个过程。

BGP 属性

BGP 属性及前缀称为路由。两个比较重要的 BGP 属性是 AS-PATH 和 NEXT-HOP。

AS-PATH 包含了通告已经通过的 AS 的列表。当一个前缀通告某 AS,该 ASN 加入 AS-PATH 列表。如果路由器在路径列表中看到包含了它自己的 AS,它将拒绝该通告,避免了通告环路。

NEXT-HOP 是 AS-PATH 起始的路由器接口的 IP 地址。NEXT-HOP 不属于 AS1 中某路由器的 IP 地址,但包含该 IP 地址的子网直接连接到 AS1。

确定最好的路由

热土豆嗯造洋芋路由选择算法是最简单的 BGP 路由选择算法。它的思想是将分组尽快送出 AS,因此路由器对于前缀 x,选择通往 NEXT-HOP 路由器开销最小的路由,至于 AS 外的情况一概不管。

实践中的路由器选择算法按顺序调用下列消除规则直到只剩下一条路由:

  • 路由被指派一个本地偏好值,选本地偏好值最高的。
  • 没选出来,选 AS-PATH 最短的。
  • 还没选出来,按热土豆选。
  • 怎么还没选出来 使用 BGP 标识符选择。

IP 任播

eg. CDN 公司为多台服务器指派相同的 IP 地址并通告。当配置路由选择表时路由器在本地使用 BGP 路由选择算法选择到该 IP 地址”最好的”的路由。

然而实践中 CDN 通常不用 IP 任播

路由选择策略

路由的本地偏好值由本地 AS 策略决定。

如果一个 AS 本身是进入 / 离开它的所有流量的源 / 目的地,则它是桩网络。所有接入 ISP 都一定是桩网络。为了实现这种行为,它可以向邻居通告它无法到达任何 AS。