网络层

端系统位于网络的边缘。当一个端系统向另一个端系统发送报文时，报文首先传输到一个与之相连的路由器(router)，该路由器再转发到另一个与之相连的路由器，……报文最终通过路由器的转发路径到达另一个端系统。其中，端系统到路由器以及路由器到路由器之间如何传输报文的问题是链路层将会讨论的问题，网络层我们默认转发是能轻易实现的。从源到目的地可能有多条路径，而报文经过的路径由路由器的转发机制决定——由路由器转发报文就好像一个不用导航而只会问路的人，每次走的方向都由被问路的人指定。

对于计算机网络而言，以上报文转发过程由两个独立的关键问题：第一，如何设置路由器的转发策略，使得报文能够准确抵达终点？第二，如何从整体上规划路线，使得报文尽量少走弯路。这就是网络层我们要讨论的两个主要内容，分别称为网络层的数据平面和控制平面。数据平面讨论每台路由器如何把来自各个不同源的报文发送往到不同目的地，这一过程称为转发(forwarding)；控制平面讨论如何从源主机到目的主机规划出一条报文路线，称为路由选择(routing)。注意，因特网的网络层并没有任何机制保证防止丢包、按时按序、安全到达等等，因特网的网络层协议只提供尽力而为服务（相当于根本无服务）。

数据平面(Data Plain)

路由器体系结构(Router Architecture)

每秒到达路由器的报文数量可能是千万量级的，因此路由器一般都用硬件实现。从功能上讲，路由器实现的功能不过是：某个输入端口读入一条报文，硬件判定改报文该沿哪个输出端口输出，在对应端口输出该报文。以上三个模块分别称为输入端口，交换结构，输出端口。除此之外，路由器还需要一个路由选择控制器模块与外界网络交互，这样才能实现控制平面对路由器转发方案的统筹安排。

输入端口首先基于链路层协议拆封报文，然后有一个缓存允许多个报文排队等待。

交换结构判定报文去向，可以直接用一个CPU做计算并在对应端口输出，也可以用一个总线输出每个输入但只允许特定接口接收，也可以用一种crossbar结构控制。

输出端口也有一个缓存允许未发送的报文排队等待，然后基于链路层协议重新封装报文，然后输出。

由于多个输入端口的报文可能会对应同一个输出端口，因此输出端口更容易排队。如果排队报文数量超出缓存，就会出现路由器丢包。经验告诉我们，路由器缓存应该大概设置成RTT乘以链路容量。其中，输入和输出的“排队”可以采用先进先出机制，也可以采用其他调度机制（如优先权机制、Round Robin或加权等等）。

网际协议(Internet Protocol, IP)

判定报文在哪个端口输出必须依据报文的信息。最直接的想法就是，让网络层的报文首部明确标明目的地，这样路由器就可以通过匹配首部字符串完成转发。为此，我们希望接入网络的每个端系统或路由器都有一个独一无二的目的地编码，网际协议规定了给端系统编码的规则，把这个编码称为端系统的IP地址(IP address)。所以当运输层的报文进入网络层继续发送时，要封装上首部信息，包括源IP地址、目的IP地址、IP的首部的检验和等等，其格式由具体的IP协议规定。

如今广泛应用的网际协议第四代(IP version 4, IPv4)把IP地址编码为32位字符串，用点分十进制记法表示（例如193.168.216.9）。

因特网的地址分配策略称为无类别域间路由选择(Classless Interdomain Routing, CIDR)。当一个设备要接入一个网络时，首先要向网络管理员提交申请，管理方会给该设备分配一个专用的IP地址。IP地址的管理一般是有层级的，有一个全球性的机构ICANN把IP分配给各大组织，各大组织又把IP分割分配给较低一级的组织，层层迭代，当普通用户申请IP时通常只需向邻近的一个服务器申请即可。如果一个组织（比如一个公司）由于设备众多需要申请数量众多的IP地址，通常它会被分配一块连续的地址空间。这些地址有相同的前缀，我们通常把这些有相同前缀的一块连续地址称为一个子网(subnet)，可以用\(a.b.c.d/x\)来指示前缀，其中\(/x\)这一记法称为子网掩码(subnet mask)，例如223.1.1.0/24表示IP地址前24位相同的地址构成的子网，该子网中所有地址都具有223.1.1.xxx的形式。管理员会为这个子网分配一个专门的IP地址223.1.1.0。利用这种方式，我们就把IP地址结构化了，子网外部的路由器对于发送到这一子网的报文只需检查其子网掩码对应的前缀，前缀以后的部分交给子网内部处理。

理论上当一台设备刚加入网络时，需要管理人员手动为其分配IP。但这样太过于麻烦也不太现实，考虑你从寝室带着手机到了教室，手机在连接寝室WiFi时有一个IP，在连接教室的WiFi时又有一个不同的IP。为此，人们设计了一个自动配置接入网络的主机的IP地址的协议：DHCP(Dynamic Host Configuration Protocol，动态主机配置协议)，又称plug-and-play。一般，每个子网都有一台DHCP服务器，基于此，DHCP自动分配IP的流程是：设备刚接入子网时，像整个子网广播（广播的操作方法是，发送一个目的IP为255.255.255.255的报文，这是广播专用IP地址。源IP设为0.0.0.0，因为它还不知道自己的地址）；DHCP服务器在接收到该消息之后生成一个IP地址然后广播；设备接收到这个IP以后向DHCP服务器发送该IP地址的请求报文；服务器随后发送ACK报文给主机。至此主机的IP就设置完成了。

我们发现这样一个问题：假设一块连续地址已经被分配给了一个公司，但该公司又购置了新设备，此时不能保证可以扩大这一连续地址区域，因为相邻地址可能已经被分配给别人了。此时我们可以分配一块不连续的地址给它，但是用一个映射来创造出地址连续的假象。现在广泛采取的方案是每个子网的进出口接一个网络地址转换路由器(Network Address Translation router, NAT)。在子网内部，设备都认为自己的IP为10.0.0.0/24中的地址，但在报文进出子网经过NAT路由器时，由NAT路由器内部的一张NAT转换表把各个IP转换为实际的IP，这一转换表在设备初始分配IP时就写入路由器。

路由器也必须分配IP地址。事实上，同一个路由器的不同接口会被分配不同的IP地址。

随着设备数量的增加，32位串不足以编码地球上所有设备和路由器了。所以人们推出了IPv6，用128位串编码IP地址，确保再也不会不够用。

以上讨论的转发方式可以称为基于目的地的转发(Destination-Based Forwarding)。它有一定的局限性，例如相同目的地的报文一定会走相同的路径。事实上我们有时希望相同目的地的报文可以沿多条路径并行发送，这时基于目的地的转发就不够用了。有一种称为通用转发(General Forwarding)的机制可以实现上一点，它还能方便的实现防火墙（屏蔽特定源的报文）等功能，方法是在路由器中维护一张流表(flow table)：在匹配网络层报文时，并不只看目的地地址，而是匹配报文段中的各类信息，根据流表做出相应的动作。

控制平面(Control Plain)

在数据平面，我们解决了路由器如何转发数据的问题——路由器的“匹配+动作”机制（IP地址前缀匹配+动作，流表匹配+动作）。留给控制平面的问题是，如何分配并协调各个路由器上的“匹配+动作”机制？分配路由器的转发表的协议称为路由选择协议(Routing Protocol)。

以上问题有两种解决方法。第一种是，利用路由器之间互相的通信来更新转发表，这称为per-router control，是解决这一问题的传统方法；第二种是，把所有路由器都接入一个控制中心，让控制中心统筹协调，这称为logically centralized control 。第二种方法通常采用软件定义网络(Software Defined Network, SDN)来实现，也即用软件作为控制中心分发路由器的转发表。接下来的讨论第一种方法：

路由选择算法

我们首先把网络建模为带有边权的有向图，图的节点就是端系统或路由器，边权由对应的链路的长度、容量、传输速度等综合确定。给定一张有向图，我们有求任意起点到终点的最短路的高效算法，著名的有Dijkstra、Bellman-Ford等。

Dijkstra有一个特点，它需要维护图的全局状态信息。我们需要维护的点集\(S\)是全局的（用堆优化则需要维护堆，也是全局的），每时每刻我们必须知道整张图的完整信息才能够做转发表的分配决策。因此利用Dijkstra的路由选择协议称为链路状态协议(Link State Protocol, LS)。在Per-Router Control中，每个路由器都必须掌握全局信息，因此每个路由器必须向全网络广播信息，由此确定转发表。每次检测到链路状态变化（如某节点断开或某边权改变），都需要重新广播，并让所有路由器重新计算。

Bellman-Ford的优势在于松弛操作\(d(x,y)\leftarrow \min\{d(x,y),d(x,u)+w(u,y)\}\)是局部的，因此一个路由器上\(d\)的信息改变不必向整个网络广播，只需要通知相邻节点。因此基于Bellman-Ford的路由选择协议是分布式协议。可以分析发现，对Bellman-Ford算法而言，当某边权减小时，该信息散播很快，且很快收敛；当某边权增大时，收敛速度却很慢。

开放最短路径优先协议(Open Shortest Path First Protocol, OSPF，)采用了Dijkstra算法（其中开放表示该协议的方案是向公众开放的）。每次链路状态改变时向所有节点广播。即便链路状态没有改变，也会保证每30分钟广播一次。

自治系统(Autonomous System)

随着端系统和路由器数量的增加，图的规模越来越大，以至于管理整个网络的路由器所需要的通信、计算、存储开销高到不可实现。为此，我们可以把路由器分割成一系列路由器组织，称为一个自治系统（AS，通常一个ISP中的路由器构成一个自治系统）。每个AS由一个独一无二的AS号标识，该编号也由ICANN注册时分配。这样，建立路由器的路径就分为了两个步骤：规划以各个AS作为节点的图的最短路；规划经过AS内部的最短路。前者称为自治系统间路由选择协议(Inter-AS routing protocol)，后者称为自治系统内部路由选择协议(Intra-AS routing protocol)。可以看到，OSPF可以用作Intra-AS协议。

因特网在所有AS上都运行相同的一个Inter-AS协议，称为边缘网关协议(Broder Gateway Protocol, BGP)。BGP处理从一个AS中的路由器到一个AS外的路由器之间的报文传播问题，报文的目的地是一个IP前缀（对应某个AS中的某个路由器）。每个AS内的路由器分为内部路由器(internal router)和网关路由器(gateway router)，其中每个网关路由器与若干相邻AS的网关路由器之间有链路相连。当起点路由器需要像前缀\(x\)发送报文时，\(x\)对应的路由器所在的AS需要像相邻AS告知其位置，相邻AS再向其相邻AS告知位置。这样所有AS都可以获知通向\(x\)的路径，得知了以AS为节点的以\(x\)为终点的图的拓扑结构。如何通告相邻的AS呢？BGP在路由器间建立BGP连接（一个TCP连接），AS内部的路由器之间的BGP连接称为iBGP，网关路由器间的BGP连接称为eBGP。在BGP连接中，路由器转发带有AS序列的报文，每经过一个新的AS就把该AS号添加到报文中。确定了AS间图的拓扑以后，BGP运行路由选择算法规划路线。最简单的算法是，对于每个路由器，利用Intra-AS协议确定该AS内距离它最近的网关路由器（这是一个贪心算法，每个路由器都好像手上的土豆太烫一样马上把报文扔掉，所以称为热土豆算法(hot potato routing)）。实践中BGP的算法更复杂，为每个路由器设置偏好值，优先转发到偏好值最高的路由器，如果偏好值相同就运行Bellman-Ford（边权为AS间的跳数）。

BGP报文需包括：目的前缀；下一跳的AS号；当前AS路径；...

ICMP

ICMP(Internet Control Message Protocol，因特网控制报文协议)用于主机与路由器之间通信。例如，当某个路由器发现一个报文无法转发时，它可以利用ICMP协议向源主机发送消息告知消息转发失败。这是ICMP最典型的用途，称为差错报告。另一些常见的ICMP用途包括，当路由器拥塞时向主机发送消息，告知主机发慢一点，这样的报文称为源抑制报文。

网络管理

网络层中路由器以及路由器之间的链路构成了复杂的系统，如何维护、管理这个系统？人们会建立管理服务器，存储网络设备的信息，然后与设备通信维护设备。该管理的通信方式遵循简单网络管理协议(Simple Network Management Protocol, SNMP)，这是一个应用层协议，通常用UDP协议传输。