计算机网络：网络层

overview

basic

网络层可以被分为数据平面和控制平面。数据平面的功能可以理解为每台路由器的控制功能，控制平面可以理解为对整个网络的控制。在进入正式的讨论之前，还需要区分两个概念：

• 转发：路由器将输入链路的分组正确地移动到输出链路（或者阻挡）。
• 路由选择：网络层决定分组所采用的路由和路径，使用合适的路由选择算法来决定一个分组流动的路径。

---

PART1：数据平面

网络服务模型

Internet提供尽力而为服务，大概意思是：我尽力了，但我不保证任何东西。

基于链路层帧的字段来做转发决定的分组交换机，称为链路层交换机，其他分组交换机称为路由器，为网络层的设备。

路由机

一台路由机一般包含下面的部分：

• 输入端口
• 交换结构
• 输出端口
• 路由选择处理器

输入端口处理

在输入端口，路由器根据转发表来查找输出端口，使得到达的分组根据交换结构到达输出端口。转发表复制于路由选择处理器。一种比较简单的转发表是基于地址的前缀进行匹配（因为显然输出端口的数量有限）。查表的操作需要硬件和快速查找算法的搭配。通过查表确定输出端口之后，分组就可以进入交换结构，但也有可能因为排队而导致该分组阻塞。

交换结构

交换有几种方式可以完成：

经内存交换

路由器就如同一个计算机，cpu控制输出端口和输入端口的交换，具体地，通过内存来交换。显然这种方法极有可能导致传输速度受到内存带宽的限制。

经总线交换

输入端口为分组加上一个标签，将分组通过总线发送给每一个输出端口，但只有对应标签的输出端口可以收到，在输出端口处再去掉该标签。每个分组共用一条总线：交换受总线带宽速率的限制。

经互联网络交换

如纵横式交换机，可以并发转发多个分组，为非阻塞的。当然，如果两个不同输入端口的分组的输出端口原因的话，还是需要等待

输出端口

取出输出端口的内存中的分组并发送到输出链路中。

排队

从上文可知，排队可能出现在输入端口和输出端口处。

在输入端口处，分组需要等待前面的分组发送，被称为线路前部(HOL)阻塞。

在输出端口处，分组需要等待输出链路传播。在此处可能产生排队，当缓存超过内存时，需要对队列进行处理（主动队列管理(AQM)算法）。

分组调度

对于上面提到的，在输出端口的队列，我们需要有一定的排队规则，使得队列中的分组有不同的优先级，即决定谁先输出。以下为几种调度的规则：

• FIFO：先进先出，超过内存的分组直接丢弃。这种方法确保了分组从输入端口到输出链路的次序
• priority queuing：优先权排队，到达输出链路的分组会被分类放入不同优先级的队列。比如携带网络管理信息的分组、基于IP的实时话音分组等可能有更高的优先级。在同一优先级的队列中，采用FIFO。
• round robin queuing discipline：循环排队规则，分组像使用优先权排队一样被放入不同的队列，但每个队列并不存在真正的优先级，循环调度器为每条队列轮流提供服务。一种较为通用的循环排队为加权公平排队。

网际协议(IP)

IPv4

数据报格式

IPv4（Internet Protocol Version 4）的数据格式通常被称为“IPv4数据报”或“IPv4包”，它包括以下几个主要部分：

首部（Header）

IPv4数据报的首部部分长度至少为20字节，最多可扩展到60字节。首部用于传递与路由和传输数据相关的控制信息。以下是IPv4首部各字段的简要说明：

• 版本（Version）： 4位，表示协议的版本号，对于IPv4，值为4。
• 首部长度（IHL, Internet Header Length）： 4位，表示首部的长度，以4字节为单位，最小值为5（表示20字节的基本首部），最大值为15（表示60字节的最大首部）。
• 服务类型（Type of Service, ToS）： 8位，用于指定优先级和服务质量（QoS）。
• 总长度（Total Length）： 16位，表示整个数据报的长度（包括首部和数据），单位为字节，最大长度为65535字节。
• 标识（Identification）： 16位，唯一标识数据报的ID，用于数据报的重组。
• 标志（Flags）： 3位，用于控制分片，其中有一个常见的DF（Don’t Fragment）标志。
• 片偏移（Fragment Offset）： 13位，指示数据报片的偏移，用于重组分片后的数据报。
• 生存时间（TTL, Time to Live）： 8位，数据报在网络中的跳数限制，每经过一个路由器，该值会减1，值为0时数据报被丢弃。
• 协议（Protocol）： 8位，表示上层协议的类型，如TCP（6）、UDP（17）。
• 首部校验和（Header Checksum）： 16位，用于检验IPv4首部的完整性和有效性。
• 源IP地址（Source Address）： 32位，发送方的IP地址。
• 目的IP地址（Destination Address）： 32位，接收方的IP地址。
• 选项（Options）： 可选字段，长度可变，主要用于调试、测试或特殊控制功能。

数据（Data/Payload）

IPv4数据报的负载部分，携带上层协议（如TCP、UDP）的数据。根据总长度和首部长度的不同，数据部分的大小可变，最大可以达到65515字节（65535字节的总长度减去最小的20字节首部长度）。

IPv4的整个数据报结构如下所示：

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version|  IHL  |Type of Service|          Total Length           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Identification        |Flags|     Fragment Offset      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Time to Live |    Protocol    |       Header Checksum          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                         Source Address                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Destination Address                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options (if any)                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             Data                               |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

数据报分片

不同链路层协议可能不能承载相同大小的网络层分组，一个链路层帧可以承载的最大数据量为最大传输单元。为了解决该问题，需要将IP数据报分为更小的数据报（切成片），用链路层帧来封装并发送。至于片的组装，不会放在路由器中，而是放在端系统中处理，以提高传输效率。数据报中的标识、标志、片偏移字段就是用来重组的。

编址

IP地址采用的是点分十进制记法，IP地址长度为32bits共4个字节，将每个字节用十进制来写，每个字节用.隔开，就可以得到IP地址。全球的每台主机和路由器的每个端口都有一个独一无二的IP地址，一个接口的IP地址一部分需要通过子网来确定。在一个子网中，多个接口的IP地址有共同的前缀。

Internet的地址分配策略为**无类别域间路由选择(CIDR)**，在使用子网寻址时，将地址变为a.b.c.d/x的形式，x代表了地址第一部分的bit数，前x位位该地址的前缀。一个组织会被分配一块连续的地址（具有相同的前缀）。网络中外部的路由器，只会考虑前缀，从而减少转发表的长度。剩余的bit用于区分内部设备。这种方式使得子网划分和分配十分灵活（x不需要为8的倍数）。

特例：目的地址为255.255.255.255的数据报回交付给同一个网络的所有主机，可能会转发给邻近的子网。

获取地址

为了获取一块IP地址用于子网，会先向ISP申请地址，ISP可以将已有的分配地址分配给需要者。如果ISP想要更多的地址，需要向ICANN组织申请。

一个组织在获取了一个一块地址后，需要分配给组织内的主机。显然手动分配过于麻烦，一般采取的是动态主机配置协议(DHCP)，也叫即插即用协议(plug-and-play protocol)/零配置(zeroconf)协议，网络管理员可以设定某个主机在每次连入网络都被分配相同的地址，或者是不同的临时地址。

DHCP协议

对于一台新到达的主机，DHCP协议分为以下几步：

• 主机发送**DHCP发现报文(DHCP discover message)**。使用广播地址255.255.255.255向所有主机的67端口发送该报文。
• DHCP服务器收到一个DHCP发现报文，用**DHCP提供报文(DHCP offer message)**作出响应，使用广播地址。因为一个客户有可能可以在多个DHCP服务器中选择。
• 新的客户选择一个服务器，对其发送**DHCP请求报文(DHCP request message)**。
• 服务器用DHCP ACK message来对请求报文响应

地址转换

**网络地址转换(NAT)**的工作原理是：

• 所有的主机与 NAT 路由器连接，所有的主机对于外部世界看作是单个设备和一个 IP 地址，通过这一个 IP 地址不同的端口来区分内部的主机。
• NAT 使用 NAT 转换表（NAT Translation Table） 将这个公开的 IP 地址加端口和所有内网 IP 地址加端口之间有一对一映射关系。也就是 NAT 转换表的一个记录，将公网 IP 和一个端口映射一个内网的进程。
• 外部客户端请求 NAT 内的主机，是通过请求 NAT 路由器的 IP 地址和指定端口，NAT 路由器接收到请求后，通过修改报文的目标地址为局域网地址，修改目标端口为进程的端口，将这个报文转发给内网的主机的一个进程。
• NAT 内的主机访问外部的主机，请求经过 NAT 路由器的时候，NAT 路由器修改报文的源地址为 NAT 路由器的地址，修改源端口为 NAT 路由器的一个端口。
• 所有内网中的主机不直接与外部的通信，所有的通信都是 NAT 路由器与外部进行的。NAT 通过修改报文的内容从而达到与内网的通信。

IPv6

IPv6（Internet Protocol Version 6）的数据格式相比IPv4进行了简化和优化，以提高路由效率和支持更大的地址空间。IPv6数据报由基本首部和有效载荷（数据部分）组成。以下是IPv6数据报的结构及其关键字段：

IPv6首部（Header）

IPv6首部固定长度为40字节，相比IPv4的可变长度，IPv6的首部更简洁高效。IPv6首部各字段的含义如下：

• 版本（Version, 4位）： 表示IP协议的版本号，IPv6的值为6。
• 流量类别（Traffic Class, 8位）： 类似于IPv4中的服务类型字段，用于定义数据包的优先级和服务质量（QoS）。
• 流标签（Flow Label, 20位）： 用于标识同一流中的数据包，方便路由器识别和处理具有相同流标签的包，提高流量管理的效率。
• 有效载荷长度（Payload Length, 16位）： 指定除首部外的数据部分的长度，最大可支持65535字节的有效载荷。若长度超过65535字节，则使用扩展首部。
• 下一个首部（Next Header, 8位）： 指定下一个首部的类型，通常指上层协议（如TCP、UDP），也可以指IPv6的扩展首部。
• 跳限制（Hop Limit, 8位）： 类似于IPv4的TTL（Time to Live），每经过一个路由器，该值减1，当值为0时，数据包被丢弃。
• 源地址（Source Address, 128位）： 发送方的IPv6地址。
• 目的地址（Destination Address, 128位）： 接收方的IPv6地址。

扩展首部（Extension Headers）

与IPv4不同，IPv6引入了扩展首部机制，用于处理不同的功能需求，如路由、分片、认证等。扩展首部是可选的，并且在基本首部和有效载荷之间插入。常见的扩展首部有：

• 路由首部（Routing Header）： 指定数据包经过的路由路径。
• 分片首部（Fragment Header）： IPv6通常不在中间路由器进行分片，但在源节点需要对大数据包进行分片时，使用此扩展首部。
• 认证首部（Authentication Header）： 用于数据包的认证和完整性检查，确保数据的安全性。
• ESP首部（Encapsulating Security Payload Header）： 用于加密数据包的有效载荷，确保数据的机密性。

数据部分（Payload）

数据部分是IPv6数据报的有效载荷，包含上层协议的数据（如TCP、UDP等）。有效载荷的长度由首部的有效载荷长度字段指定。对于超大数据包，可以通过扩展首部进行进一步处理。

IPv6数据报结构：

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Traffic Class |              Flow Label                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      Payload Length           | Next Header |   Hop Limit      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                         Source Address                        |
|                                                               |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                      Destination Address                      |
|                                                               |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                      Extension Headers (if any)               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                           Payload                             |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

通用转发

我们发现前文的基于目的地的转发，都是使用匹配+动作的模式，匹配指的是寻找目的的ip地址，动作指的是将分组发送到特定的输出端口。在通用转发中，两个词的更加通用，在这里的匹配指的是对多个首部字段的匹配，动作包括了转发、重写首部值（如NAT），阻挡/丢弃（防火墙），负载均衡分组等。每台分组交换机都有一张匹配加动作表，由远程控制器计算。

---

PART2：控制平面

路由选择算法

对于网络的路由，我们可以抽象成一个图，每个路由器代表一个节点，边代表了链路，边的值代表了其开销。我们的目的是，找出从源到目的地的最短开销路径。一般来说，路由选择算法可以分为：

• 集中式(centralized)：用完整的、全局的网络信息计算最短开销路径。具有全局状态信息的算法常叫做链路状态(LS)算法。
• 分散式(decentralized)：没有节点有完整的全局信息，通过迭代和分布式方式计算最低开销路径。一个例子是距离向量(DV)算法。

LS路由选择算法

为了每个节点都可以得知全局的信息，所有节点都会向网络中的所有节点广播链路状态的分组，使用链路广播算法。对于一个节点，在得到信息后，会使用路由选择算法（这里用Dijkstra算法）来计算从该节点到所有节点的最小开销路径

# N 为节点全集
# N' 代表了已知最小开销路径的目标节点的集合
# v 代表一个节点
# u 为源节点
# D(v) 为从源节点到目标节点的最小开销（本次迭代）

# Init:
N' = {u} 
for all nodes v
	if v is a neighbor of u
		then D(v) = c(u,v)
	else 
		D(v) = INF

# Interate:

Loop：
find w not in N' and D(w) is minimum
add w to N'
update D(v) for each neighbor v of w and not in N':
	D(v) = min(D(v), D(w) + c(w,v))
until N' = N

值得注意的是，当一种算法使用==拥塞或者时延==来确定链路的开销，有可能会导致路由选择的振荡，（当算法选择了一个路径，导致路径流量变化，可能会影响下一次的判断）。一种解决办法是，让每台路由器发送通告的时间随机化。

DV路由选择算法

Initialization:
for all destination 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 form 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

在链路开销改变时，可能导致路由选择环路，可以看下下面这个简单的例子：

A-1-B-1-C

在这条路径中，节点C需要通过B来得到其到A的最小开销。当A对B突然不可达时，B需要重新计算距离向量。但此时C告诉B：自己可以以2的代价到达A，于是对于B，到A的最小开销更新为3（通过C去）。这时候C更新，到A的代价为4。导致B更新，到A的代价为5，以此类推，像进入了黑洞。这个问题被称为无穷计数问题。

毒性逆转可以解决这个问题。具体地，上面的例子中，C会“欺骗”B，告诉B：自己无法到达A。（关于A，C的情报通过B来获得，没有理由C还能反过来告诉B有关A的信息）通过这种方法==毒化==逆向路径。然而涉及到3个包括更多的节点的环路无法通过这个技术检测到。

OSPF

当路由器的规模变得巨大，需要将路由器组织进自治系统，便于：

• 减小算法运行的规模
• 管理自治

在同一个AS下的路由器都使用相同的路由选择算法，这个算法叫做自治系统内部路由选择协议，**开放最短路径优先(OSPF)**就是其中一种。OSPF使用的是LS算法，各条链路的开销由网络管理员配置。

BGP

当分组跨越多个AS进行路由时，需要自治系统间路由协议。在Internet中，所有的AS都运行相同的AS间路由选择协议，即**边界网关协议(BGP)**。对于BGP，路由的地址是CIDR化的前缀。

通告BGP路由信息

BGP使得每个路由器可以获得前缀的==可达性信息==。

在一个AS中，分为网关路由器和内部路由器。在BGP中，每对路由器使用179端口的TCP连接交换路由信息，其中发送的BGP报文称为BGP连接。跨AS的BGP连接为eBGP连接，AS内的BGP连接为iBGP连接。

假设网络由3个AS组成：
AS1-AS2-AS3，其中节点x在AS3中，现在需要所有路由器通告关于x的可达性信息，AS3的网关路由器会向连接的AS2的网关路由器发送AS3 x，该AS2的网关路由器会将该报文转发给同AS下所有路由器，AS2向AS1发送AS2 AS3 x的报文（和AS3到2类似），最终，AS2和AS1的所有路由器都知道x存在及到x的路径

确定最佳路由

路由器通过BGP连接通告前缀时，其前缀包括一些BGP属性，这里我们需要用到AS-PATH（已经通过的AS的列表），NEXT-HOP（AS-PATH起始的路由器的IP地址）。

hot-potato-routing

最核心的思想是，分组就像热土豆一样烫手，每个AS都想尽快将其交给下一个AS。

对于网络中的一个路由器，假设其有到达前缀x的多个BGP路由可以选择。对于每个BGP路由，其会找到==到达NEXT-HOP的最短路径==。其会选择==最短路径==开销最小的BGP路由。

路由器选择算法

在实际中的算法，结合了热土豆路由选择，会顺序调用以下的规则，直到选出路由：

• 选择具有最高本地偏好的路由：本地偏好的值可以由网络管理员设定。通过这条规则，可以避免一个网络承担其不愿承担的负载，或者用于将流量导到专门的线路上。
• 选择有最短AS-PATH的路由：（本地偏好值都相同）距离测度使用的是AS的跳数而非路由器的。
• 热土豆路由选择：（本地偏好值都相同且AS-PATH长度相同）
• 使用BGP标识符

IP任播

对于CDN，使用BGP，可以让客户请求距离最近的服务器。

IP任播常用于将DNS请求导向最近的根DNS服务器

ICMP

即为Internet控制报文协议，用于主机和路由器间沟通网络层的信息。ICMP承载在IP分组中，上层协议编码为1。ICMP可以用于拥塞控制，追踪路由路径（如Traceroute程序的原理）

SNMP

简单网络管理协议，常使用请求响应模式……（todo）