4 网络层

运输层：依赖网络层的服务为运行在不同主机上的应用进程之间提供了逻辑通信服务。

网络层（Network Layer）：提供了主机到主机的通信服务，可以分解为两个部分，即数据平面和控制平面，网络层的分组是数据报（datagram）。

• 数据平面：网络层中每台路由器的功能，即到达路由器一条输入链路的数据报如何转发（forwarding）到该路由器的一条输出链路。
  • 转发（forwarding）：将分组从一个路由器输入链路接口转移到适当的输出链路接口的路由器本地操作，通常由硬件实现。
• 控制平面：网络范围的逻辑，即数据报沿端到端路径在路由器之间的路由选择（routing）方式。
  • 路由选择（routing）：确定一个分组从源到目的地所采取的端到端路径的网络范围处理过程，通常由软件实现。

因特网的网络服务模型（network service model）：因特网的网络层仅提供单一的服务，即尽力而为服务（best-effort service），这种服务既不能保证传送的分组以它们发送的顺序被接收，也不能保证它们最终交付，既不能保证端到端时延，也不能保证有最小的带宽。

4.1 网络层：数据平面

4.1.1 路由器

组成

• 输入端口（input port）：数据链路层处理（协议，拆封），查找，排队，转发。

  • 转发表从路由选择处理器经独立总线复制到每个输入线路卡。
  • 在每个输入端口本地做出转发决策，避免了集中式处理的瓶颈。
  • 路由器用分组目的地址的前缀与转发表的中的表项进行匹配，选取最长的匹配项，并向该项相关联的链路转发该分组（最长前缀匹配规则）。
  • 队列首部（Head-Of-the-Line，HOL）阻塞：一个输入队列中排队的分组，因位于队列首部的分组被阻塞（可能因为队列首部输出端口缓存溢出）而必须等待（即使该分组的输出端口是空闲的）。

• 交换结构（switch fabric）：链接输入端口和输出端口，交换数据，是路由器内部的网络。

  • 经内存（memory）交换
  • 经总线（bus）交换
  • 经互联网络（interconnection network）交换

  

• 输出端口（output port）：存储从交换结构接收的分组（排队，缓存），数据链路处理（协议，封装），传输分组。

  • 缓存溢出的策略：丢弃到达的分组（弃尾），删除部分排队中的分组。
  • 分组调度器位于输出端口，用于决策优先传输哪个排队中的分组。

• 路由选择处理器（routing processor）：执行控制平面功能，计算、维护转发表（在SDN路由器中，负责与远程控制器通信，接收远程控制器计算的转发表），网络管理功能。

缓存

• 过少：丢包
• 过多：时延（缓存膨胀（bufferbloat）：因持续缓冲导致长时延）

分组调度

• 先进先出（First-In-First-Out，FIFO）：优先传输更早排队的分组。

• 优先权排队（priority queuing）：优先传输优先级更高的分组，对优先级相同的分组做FIFO调度。

  • 非抢占式（non-preemptive）优先权排队：一旦分组开始传输，就不能打断。

• 加权公平排队（Weighted Fair Queuing，WFQ）：为每个类分配一个权重，根据权重不同，每一轮循环为每个类分配不同的传输数量，若遇到空的类队列，立即服务循环中的下一个类。

  使用以下两种规则：

  • 循环排队规则（round robin queuing discipline）：在优先权相同的类之间，调度器循环为这些类提供调度服务。
  • 保持工作排队规则（work-conserving queuing discipline）：在有分组排队等待传输时，不允许链路保持空闲。

4.1.2 网际协议（Internet Protocol，IP）

4.1.2.1 IPv4

1、数据报结构及字段

首部

• 版本（4b）：IP的版本号

• 首部长度（4b）：首部中包括长度可变的选项（一般为空），选项为空时，首部长度为20B

• 服务类型（8b，TOS）：区分提供服务类型不同的数据报

• 数据报长度（16b）：首部+数据

• 标识、标志、偏移：用于IP分片（由于最大传输单元的限制，需要将大的数据报分成若干小的数据报），IPv6已弃用

  • 标识（16b，identifier）：同一原始数据报分成的小数据报和该原始数据报具有相同的标识
  • 标志（3b，flags）：包括预留位（无意义）、DF（0表示允许分片，1表示禁止分片）、MF（0表示本片即为最后一片，1表示本片后还有分片）
  • 偏移（13b，offset）：以8B为单位，表示分片的数据报在原始数据报中的位置

  

• 寿命（8b，TTL）：防止数据报在网络中长期循环，每经一台路由器处理数据报TTL-1，TTL=0时丢弃该数据报

• 上层协议（8b）：即运输层协议，如TCP（6）和UDP（17）

• 首部检验和（16b）：仅计算IP数据报首部的检验和

数据：即有效载荷

2、编址

一个IP地址与一个接口（主机与物理链路之间的边界、路由器与任意一条链路的边界）相关联

一个路由器有多个接口，每个接口对应一条链路和一个IP地址

一个接口对应一个全球唯一的IP地址（NAT后面的接口除外）

点分十进制记法：32位IP地址，每8位分开，转化为十进制数，用句点隔开

（11000001 00100000 11011000 00001001 → 193.32.216.9）

子网（subnet）：互联的主机接口和/或路由器接口组成的网络

子网掩码（network mask）：同一子网下的接口的IP地址的前 n 位相同，这前 n 位定义了子网的地址，记作：XXX.XXX.XXX.XXX/n

子网的地址：子网掩码 + 全零 / n

一个IP地址：网络前缀 + 主机地址

一个子网最多能够容纳 2^n - 2 台主机（接口），主机地址全零表示该子网的地址，主机地址全一表示广播地址（向广播地址发送的报文将会被广播到所有同一子网下的主机和路由器），均不能被分配给接口

因特网的地址分配策略

• 分类编址（classful addressing）：子网地址被限制为8、16、24位，分别称为A、B、C类网络
• 无类别域间路由选择（Classless Interdomain Routing，CIDR）：目前采用，子网地址没有限制

地址获取

• ICANN（Internet Corporation for Assigned Names and Numbers）向ISP分配一块IP地址，ISP向其下的子网分配地址块（网络管理员手动分配，DHCP服务器自动分配）

• 动态主机配置协议（Dynamic Host Configuration Protocol，DHCP）：允许主机自动被分配一个IP地址，向主机提供被分配的IP地址、子网掩码、默认网关（第一跳路由器地址）、本地DNS服务器地址

  • 网络管理员可以配置DHCP，使某主机每次与网络连接时得到一个相同的IP地址，或被分配一个临时的IP地址

  • 自动化：即插即用协议（plug-and-play protocol）、零配置（zeroconf）协议

  • DHCP基于client-server架构和UDP协议，每个子网具有一台DHCP服务器或DHCP中继代理（通常是路由器）

  • 步骤

    • DHCP服务器发现：新到达的主机使用UDP分组广播DHCP发现报文（DHCP discover message）
      • src IP：0.0.0.0
      • des IP：255.255.255.255
      • 提供发现报文的ID给DHCP服务器
    • DHCP服务器提供：DHCP服务器收到DHCP发现报文后广播DHCP提供报文（DHCP offer message）向客户做出响应
      • src IP：DHCP服务器IP
      • des IP：255.255.255.255
      • 提供收到的发现报文的ID给客户识别、包含向客户推荐的IP地址、子网掩码、IP地址租用期（address lease time）
    • DHCP请求：新到达的主机从一个或多个服务器提供中选择一个，并广播DHCP请求报文（DHCP request message）（客户通知所有的服务器选择了某个服务器提供的IP，其他服务器可以重新启用提供的IP），回显配置的参数
    • DHCP ACK：DHCP服务器广播DHCP ACK报文（DHCP ACK message），证实所要求的参数

    

网络地址转换（Network Address Translation，NAT）

• 专用网络（private network）：内部地址仅对网络中的设备有意义的网络

• NAT使能路由器：对外界隐藏了内部网络的细节

  • 路由器从ISP的DHCP服务器获取自身的IP地址（全球唯一）
  • 路由器本身运行一个DHCP服务器，为内部网络中的主机分配IP地址（在内部是唯一的，但并不是全球唯一的，对外部网络没有意义）
  • 使用NAT转换表，将内部主机的IP地址和端口号映射成新的端口号，对外使用新的端口号和自身的IP地址，对内根据收到数据的目的端口号转化成内部主机的IP地址和端口号，并将数据发送给响应主机的相应端口

  

4.1.2.2 IPv6

数据报结构及字段

动机

• 32比特的IP地址空间不足：128比特的IPv6地址
• 简化首部（40B）：舍弃许多IPv4字段
• 流标签（flow label）：给属于特殊流的分组加上标签，这些特殊流是发送方要求进行特殊处理的流（流的定义尚未确定）

从IPv4到IPv6的迁移

• 建隧道（tunneling）：两台IPv6路由器之间的中间IPv4路由器的集合称为一个隧道，借助隧道，可以将IPv6数据报放在IPv4数据报的数据字段进行传输

  

4.2 网络层：控制平面

4.2.1 路由选择算法

分类

• 集中式/分散式
• 静态/动态
• 负载敏感/负载迟钝

4.2.1.1 链路状态（Link State，LS）算法

是集中式路由选择算法，路由器用全局状态信息计算出最低开销路径

路由震荡：路由器的同步状态更新（自同步：路由器上LS算法趋向于在同一时刻执行），可能导致数据在路由器间来回传递，最终当数据TTL归零时被丢弃（避免自同步的方法：每台路由器发送链路通告的时间随机化）

例如：Dijkstra算法（计算从某一节点到其他所有节点的最短路径）

• 初始化：将节点 u（起始节点）加入子集N‘（N‘中的节点是已经确定最短路径的节点），并记录到相邻节点 i 的距离D(i)（到不相邻节点 j 的距离记为D(j) = ∞），以及沿当前路径到相邻节点 i 的前一节点p(i) = u
• 每次迭代选取D(i)中的最小值D(m)，并将m加入到N’中（因为从 u 到达其他节点的距离都比到m的距离更远，不可能再有一条更短的路径到达m了），更新不在N’内的节点 i 的[D(i), p(i)] = min{[D(i), p(i)], [D(m) + c(m, i), m]}（c(m, i)表示从m到 i 的距离，若m不与 i 邻则c(m, i) = ∞）
• 当所有节点都在N‘中时终止程序

Initialization:
	N’ = {u}
	for all nodes v
		if v is a neighbor of u
			then D(v) = c(u,v)
		else D(v) = ∞

Loop
	find w not in N’ such that D(w) is a minimum
	add w to N’
	update D(v) for each neighbor v of w and not in N’:
		/* new cost to v is either old cost to v or known least path cost to w plus cost from w to v */
		D(v) = min(D(v), D(w)+ c(w,v))
until N’ = N

4.2.1.2 距离向量（Distance-Vector，DV）算法

是分散式路由选择算法，路由器以迭代、分布式的方法计算出最低开销路径

对于DV算法：每个节点维护到网络中所有其他节点的距离向量（开销估计向量）

例如：Bellman-Ford算法

• 对于每个节点 x：
• 初始化：记录到 x 相邻节点 i 的距离Dx(i)（到不相邻节点 j 的距离记为Dx(j) = ∞），向 x 的每个邻居发送 x 的距离向量列表Dx
• 若有邻居节点 i 向 x 发送 i 的距离向量列表，计算每一个Dx(j) = min_j{ c(x, i) + Di(j) }，若Dx发生变化，则向 x 的每个邻居重新发送Dx

/* 在每个节点执行此算法 */
Initialization:
	for all destinations y in N:
		Dx(y) = c(x,y) /* if y is not a neighbor then c(x,y)= ∞ */
	for each neighbor w
		Dw(y) = ? for all destinations y in N
	for each neighbor w
		send distance vector Dx = [Dx(y) : y in N] to w

loop
	wait (until I see a link cost change to some neighbor w or until I receive a distance vector from some neighbor w)

	for each y in N:
		Dx(y) = minv{c(x,v) + Dv(y)}
		
	if Dx(y) changed for any destination y
		send distance vector Dx = [Dx(y) : y in N] to all neighbors

forever

4.2.2 自治系统内路由选择：OSPF

自治系统（Autonomous System，AS）：每个AS由一组通常处于相同管理控制下的路由器组成，通常一个ISP中的路由器以及互联它们的链路构成一个AS，某些ISP也会划分出多个AS，一个自治系统由全局唯一的AS号（ASN，由ICANN分配）标识。

开放最短路优先（Open Shortest Path First，OSPF）：OSPF及IS-IS是因特网使用的自治系统内部路由选择协议（intra-autonomous system routing protocol）

• 洪泛链路状态信息：路由器向自治系统内所有其他路由器广播路由选择信息（链路状态发生变化时、周期性广播），直接使用IP协议，不依赖于TCP或UDP
• Dijkstra算法：通过洪泛链路状态信息路由器构建了自治系统的拓扑图，每台路由器本地运行Dijkstra算法从而构建转发表

4.2.3 自治系统间路由选择：BGP

边界网关协议（Border Gateway Protocol，BGP）：BGP是因特网使用的自治系统间路由选择协议（inter-autonomous system routing protocol）

BGP中，分组路由到CIDR化的前缀

网关路由器（gateway router）：位于AS边缘的路由器，直接连接其他AS中的一台或多台路由器

内部路由器（internal router）：仅连接AS内部的主机和路由器

• 从邻居AS获得前缀的可达性信息（子网通告路由信息）

  • BGP连接：基于TCP连接交换路由选择信息（BGP报文）

  • 外部BGP（eBGP）连接：跨越两个AS的BGP连接，网关路由器通过eBGP会话向相连子网的网关路由器发送路由信息

  • 内部BGP（iBGP）连接：同一AS内两台路由器之间的会话（不与物理链路一一对应），收到路由信息的网关路由器通过iBGP会话向子网内的其他路由器发送路由信息

  • 每条BGP路由包含三个属性：NEXT-HOP、AS-PATH、目的地前缀

    • NEXT-HOP：AS-PATH起始路由器接口的IP地址

    • AS-PATH：到达目的地需要经过的ASN列表

  

• 确定到该前缀的“最好的”路由

  • 若路由中的AS-PATH包含路由器所在的AS，则该路由器拒绝这条路由通告
  • 热土豆路由选择（hot potato routing）：从所有路由中选择到达NEXT-HOP开销（通过AS内部路由选择获取）最小的那条
  • 路由器选择算法
    • 路由被指派一个本地偏好值作为其属性之一，优先选择具有最高该项属性的路由
    • 余下的路由中，优先选择具有最短AS-PATH的路由
    • 余下的路由中，优先选择到达NEXT-HOP开销最小的路由（热土豆路由）
    • 余下的路由中，使用BGP标识符选择路由

4.2.4 因特网控制报文协议（ICMP）

ICMP：用于主机和路由器彼此沟通网络层信息

ICMP报文承载于IP分组中的有效载荷

应用：ping程序（发送/回显）、源抑制报文（拥塞控制：拥塞的路由器向主机发送源抑制报文，减小主机的发送速率）、Traceroute程序（通过ICMP告警报文跟踪主机到主机之间的路由）