计算机网络笔记

此份笔记是本人学习过程中自己总结记录的，其内容受到课堂教学内容、采用教材、个人认知水平的影响。虽然笔者力图保证内容准确以及易于理解（起码自己能看懂），但难免存在谬误或者渲染问题。非常欢迎您通过邮件等方式联系我修改，让我们一起让这份笔记变得更好！

第一章概论

1、互联网

网络：节点和边构成的，与大小形状无关的拓扑

计算机网络：一种其上存在协议的特定的网络，其中

节点包括手机、电脑等主机节点（是数据的源或者目标），以及中继器、交换机、路由器等数据交换节点。
连接起这些节点的边，也称之为链路。具体而言，连接主机节点和交换节点的称为接入链路（access），连接交换节点和交换节点的称为骨干链路（backbone）。

互联网（Internet）：以 TCP 协议和 IP 协议为主的一族协议来支撑工作的，世界上使用人数最多的计算机网络。

互联网中的主机节点称之为端系统（end system）或者主机（host），包括设备本身、能够通讯的操作系统以及运行在其上的网络应用程序等。

互联网中也有交换节点，链路。评价链路的一个重要指标是带宽，单位是 bps（bits per second）。

互联网是网络的网络，Internet 可以理解为 inter+network，也即网际。例如国内有教育网、中国移动等网络，都接入到了互联网。

互联网的标准是IETF（Internet Engineering Task Force）发布的RFC（Request For Comments，请求评述）文档的形式。

协议指对等的实体在通信过程中应该遵守的规则的集合。

协议包括格式、次序和动作：

格式指协议数据单元（Protocol Data Unit，PDU）的格式。PDU 在不同层有不同的具体称呼。PDU 有哪些字段、每个字段有多长（语法），字段的值有什么含义（语义），都属于格式的范畴。
次序指动作的顺序。例如只有接收到请求，才能发响应报文。
动作指收到请求报文之后，应该做哪些相应的操作。

互联网还可以看成分布式的进程，以及为这些分布式进程提供通信服务的基础设施。进程可以认为是应用层，基础设施可以认为是应用层以下的所有实体。

互联网另一种划分，是把主机节点、端系统这种位于互联网边缘的称之为网络边缘；路由器、交换机这种称为网络核心；将网络边缘接入网络核心的称之为接入网。这种划分与之前基本相同，只是换了一个称呼。

2、网络边缘

应用进程和应用进程之间通讯有两种模式：

客户端/服务器模式（C/S）：服务器为主，客户端为从。服务器持有资源，等待客户端的请求。服务器先运行起来，客户端后运行起来。这种模式可拓展性比较差，负载较大时服务器会宕机。
对等模式（Peer To Peer，P2P）：每一个节点既可以是服务器，也可以是客户端。文件分布在各个节点之上，通信是分布式的。

通信也有两种方式：

面向连接：要先建立起一个连接，才能开始通信。通信状态由端系统维护，中间的节点不知情。一般采用 TCP 协议（具有流量控制、拥塞控制的能力，能可靠地、有序地传输数据）
无连接：不需要建立连接，直接发送符合规范的报文即可。一般用 UDP 协议（不可靠，没有流量控制，没有拥塞控制）

3、网络核心

网络核心的作用是将源端系统的数据传输到目标端系统。数据在网络核心中传输的方式也有两种：电路交换和分组交换。

3.1、电路交换

Circuit switching，电路交换。两个端系统要通信时，要先通过信令系统建立起一个专有的，独享的链路。电路交换保证了性能，要求建立呼叫连接。电路交换一般用于传统的电话网络中。

如果连接建立起来，但是没有数据被发送，则分配的资源就会被浪费。因为这是独享的，其他端系统不能使用。

假如通信链路带宽很大，电路交换不会把所有的带宽分配给一对端系统。带宽等网络资源会被分成若干个小片，一条通信链路使用其中一片。其中用到频分多路复用技术（FDM）、时分多路复用技术（TDM）、波分多路复用技术（WDM）等。

电路交换不适合计算机之间的通信。因为其连接建立的时间比较长，而且计算机之间通信具有突发性，不是时时刻刻都需要通信，可能浪费链路的资源。也有不可靠的因素。

3.2、分组交换

Packet switching，分组交换。把要传输的数据分为一个个的分组（packet）。传输时，拿到整个分组后，才继续将这个分组转发给下一个节点，这就是存储转发。

分组交换有排队和延迟问题。如果某个节点上到达的速率小于发送的速率，分组需要排队（被缓存），等待传输。如果路由器的缓存用完了，分组会丢弃。可变长的排队延迟和可能的丢弃现象，是获取链路共享性的代价。

分组交换中用到了统计多路复用，是一种特殊的时分多路复用，但划分方式不像普通时分多路复用是固定的，比较多变。可以 A 节点连续用几个时间片，然后 B 只用 1 个，然后 A 再连续用几个。

分组交换可以同时支持的用户对数量更多。

3.3、分组交换的连接

进行分组交换时，两个节点之间的连接有两种方式：

数据报方式：要传输的分组携带了目标主机的完整地址，主机之间不需要建立连接，分组之间的传输是独立的。根据目标地址一段一段的确定方向，像逐步问路。
虚电路方式（Virtual Circuit, VC）：需要建立连接，还需要维护连接状态。分组没有携带目标的完整地址，而是携带了一个虚电路标识，来确定方向。

3.4、关键功能

网络核心的关键功能包括两方面：

路由：决定分组从源到目标的路径。由路由算法算出路由表。
转发：将分组从路由器的输入链路转移到输出链路。根据路由表来决定转移到哪个输出链路。

路由和转发相互配合，完成了数据交换的任务。

4、接入网

将网络边缘接入网络核心也有多种方式

4.1、modem

modem 是 modulator（调制）和 demodulator（解调）的合称，这个词本身含义为调制解调器。根据其发音，也常称为“猫”。

其基本原理是利用调频、调幅、调相位或综合调制等手段将上网的信号调制到电话线上进行传输，然后在用户段将数据解调出来，反之亦然。

具体而言，电话线上传输的音频信号的频率一般是 4kHz 以内，要把上网信号调制到这个频段。

由于上网信号要借用电话线进行传输，所以上网的时候不能打电话，打电话的时候不能上网。

4.2、DSL

Digital Subscriber Line，数字用户线。

仍然是调制解调的方式，但是信号被调制到 4kHz 以上的一部分区域。这部分区域被非对称地划分为两部分，较小的一部分用于上行，较大的部分用于下行。

本质上仍然是采用现有的线路，只是利用了电话信号频段之外的一个频段。由于不与电话信号重合，所以可以上网的同时打电话。

上行速率一般能达到 1Mbps，下行速率一般能达到 10Mbps。

4.3、线缆网络

基本思路是利用有线电视的线缆。

最开始，有线电视的线路是单向的，有线电视公司将电视信号单向传递给千家万户。对现有的有线电视线路进行改造，使其能支持双向传输。用户可以将自己的信号上行传输。各用户共享上行带宽。

这种方式可以提供最高 30Mbps 的下行速率和 2Mbps 的上行速率

4.4、家庭/企业接入

一个典型的家用网络可以是：手机、平板、笔记本电脑等无线设备连接到无线接入点（Access Point，AP），然后无线接入点以及其他设备接到家用路由器上，再经过猫等接入到互联网中。

企业或者大学的网络也是类似的：电脑通过网线连接到某个交换机上，再连接到核心交换机上，最后再到运营商。

5、物理媒介

就是信号传输依赖的具体的物理的媒介。可以分为导引型媒介和非导引型媒介。

导引型媒介，是有形的媒介，信号约束在介质中传输，例如光缆、双绞铜线等。

非导引型媒介，是无形的媒介，信号在整个空间中传输，例如电磁波在空气或者外层空间中传输。

具体而言：

双绞铜线（Twisted pair, TP）：两条绝缘的铜线绞在一起，类似螺旋形状
同轴电缆：两根同轴的铜导线。中心一根铜导线，然后一个同心的铜网环绕。
光缆：玻璃纤维中全反射传递光信号。误码率低，衰减低。
开放空间：在开放空间中传电磁波。容易被干扰、衰减、吸收

6、Internet 结构和 ISP

之前提到，Internet 是网络的网络。各个小网络（例如家庭中的移动设备、路由器等）接入到 ISP（Internet Service Providers）来连接到互联网。

然后，ISP 之间也应该是互联的。于是任意两个端系统就可以互相通信了。

ISP 之间如果是全连接，代价高昂而且可拓展性差。于是进一步出现层级结构，接入 ISP 连接到区域 ISP，区域 ISP 再连接到全局 ISP。ISP 之间也会有 IXP 节点（Internet Exchange Point），互相交换数据。

一些大型公司例如谷歌等，会在核心 ISP 旁边部署自己的数据中心（Data Center，DC），然后部署专线或者租用其他服务商的光缆，建立起自己的专网，接入到互联网中。

alt text

具体而言，从上到下有这些层级：

第一层 ISP（Tier 1 ISP）：是覆盖国家/国际的 ISP，速率和带宽都比较大。第一层 ISP 与其他第一层 ISP 之间相联，并与大量第二层 ISP 相联。
第二层 ISP（Tier 2 ISP）：一般是区域性 ISP，通过向第一层 ISP 付费来接入到互联网。
第三层 ISP 和其他本地 ISP：这些 ISP 连接到更高层的 ISP

7、分组延时、丢失和吞吐量

之前已经提到，现在网络中通常采用分组交换的方式进行传输。

7.1、分组延时

一个分组在两个节点（或者说一 hop）传输的分组延时包括四个部分：

节点处理延时：分组到达后，校验、查询路由表等耗费的时间。通常是微秒数量级或者更少。
排队延时：之前可能有其他分组需要被传输，在队列中等待的时间。这个时间通常是随机的，取决于当前路由器的拥堵情况
传输延时：整个数据报被发出这个节点的时间。设分组长度为 $L \text{bits}$ ，链路带宽为 $R \text{bps}$ ，则传输延时为 $L/R \text{s}$ ，通常是微秒级到毫秒级。
传播延时：一个比特从一个节点发出到被另一个节点接收，所需的花费在物理链路上的时间。设物理链路的长度为 $d$ ，在媒介上的传播速度为 $s$ ，则传播延时为 $d/s$ ，通常是微秒级到毫秒级。

排队延时取决于拥塞程度，一般用流量强度来量化。设分组到达队列的速率为 $\alpha$ ，单位是个每秒。则流量强度定义为 $L\alpha/R$

流量强度在 0 到 1 之间（不能超过设定的上限）。流量强度趋于 0 时，排队延时非常小；流量强度趋于 1 时，排队延时就会趋于正无穷。

可以利用tracert命令来跟踪到每一个节点所需的延迟：

tracert www.gucas.ac.cn

通过最多 30 个跃点跟踪
到 www.gucas.ac.cn [64.32.10.26] 的路由:

  1     1 ms     2 ms     1 ms  192.168.0.1
  2     3 ms     5 ms     3 ms  SMBSHARE [192.168.1.1]
  3     3 ms     3 ms     2 ms  172.28.0.1
  4     5 ms     5 ms     5 ms  183.233.43.57
  5     8 ms     7 ms     8 ms  221.179.3.149
  6     *        *        *     请求超时。
  7     8 ms     *        *     221.183.89.241
  8     8 ms     7 ms     7 ms  221.183.92.22
  9    14 ms    11 ms    11 ms  221.183.55.81
 10   173 ms     *      171 ms  223.120.12.105
 11   172 ms   175 ms   172 ms  223.120.6.18
 12   172 ms     *      190 ms  chinamobile.100ge.1-50.la.sharktech.net [107.167.0.222]
 13     *        *        *     请求超时。
 14   175 ms   171 ms   171 ms  64.32.10.26

IP 数据头中有一个TTL字段，TTL 字段的值每经过一个节点就会减 1。如果在某个节点（Time To Live，生存时间）减为 0 了，这个节点就会向源主机发送一个ICMP（Internet Control Message Protocol）协议报。源主机只要计时，就能知道到每个节点的延时了。

为了测出到目标节点的延时，设置 TTL 为无限大，同时设置该分组传递给一个肯定没有程序在监听的端口。这样到达目标节点之后，目标节点也会发送一个说明端口不可达的 ICMP 协议报。

7.2、分组丢失

节点上分组队列的长度是有限的。当分组到达的速率超过了传出的速率，就会发生分组丢失。

分组丢失后有三种情况，

如果与上一个节点之间的链路是可靠的，则可以直接由上一个节点重传
由源主机重传
不重传

7.3、吞吐量

吞吐量是指在源端和目标端之间的数据传输速率。包括瞬间吞吐量和平均吞吐量。

每条链路上的传输速率不同。吞吐量受传输速率最小的那条链路的限制。端到端路径上，限制端到端吞吐率的链路称之为瓶颈链路。

实际中，每一条链路可能有多对主机在用，每对主机只能获得其 $1/n$ 的带宽，这一点也要考虑进去。

8、协议层次和服务模型

计算机网络采用层次模型，将网络复杂的功能划分为分层功能明确的一个个层次，每个层次实现了一个或一组功能，并提供一些上层可以使用的功能，称之为服务。

8.1、服务

服务是低层实体向上层实体提供的他们之间通信的能力。这是不同层之间的，垂直的关系。

服务用户就是使用服务的层，服务提供者就是提供服务的层。上层使用下层服务的形式是原语（Primitive），可以理解为一个不可分的动作，例如创建、发送、接受等。

服务访问点（Service Access Point，SAP），指上层使用下层提供的服务时，使用的层间的接口，例如套接字、地址、端口等。可以用于区分不同的服务用户。

服务也可以分为面向连接的和无连接的。描述和之间通信方式中一样。

8.2、协议

协议是对等层实体，在相互通信的过程中，需要遵循的规则的集合。这是同层之间的，水平的关系。

本层协议的实现需要利用下层提供的服务以及本层做的一些处理。协议的目的是为了实现本层的功能，同时向上层提供更好的服务。

本层的功能不仅包括下层提供的服务，还包括本层实现的新功能（例如对等层之间的交流）

8.3、数据单元

本层要传递的信息称为SDU（Service Data Unit），加上ICI（Interface Control Information）之后变成IDU（Interface Data Unit）通过 SAP 传递到下一层。

下一层接到 IDU 后，抛弃掉 ICI，得到 SDU，然后进行一定处理（分组，或者多个 SDU 合并），然后加上头部就变成了 PDU。

每一层 PDU 有具体的名称。

8.4、互联网协议栈

计算机网络层次结构包括五层：

物理层：负责将一个个比特转化为物理信号，然后通过物理媒介从一个点到达另一个点，以及反过程。
链路层：在相邻网络节点之间传输以帧为单位的数据。帧中包含真正的数据比特以及帧头帧尾等，它们一起构成了整体。这一层的协议有 PPP（点对点协议）、802.11（WiFi）等
网络层：提供了以分组为单位的端到端的传输。这一层的协议主要有 IP 和多种路由选择协议
传输层：提供了进程到进程的传输。在网络层主机到主机传输的基础上进一步能区分出进程。除此之外，还将不可靠的通信编程可靠的通信，加强网络层的服务。这一层的协议主要是 TCP 和 UDP
应用层：利用下层提供的服务，实现各种各样的网络应用。这一层有非常多的协议，例如 FTP、HTTP、DNS 等

ISO/OSI 参考模型中，在应用层和传输层之间还加入了表示层和会话层：

表示层：用于对信息编码进行加密、压缩等转换，使得上层只需要关注语义信息，而不需要知道具体是如何编码的。
会话层：用于维持会话，具体包括数据交换的同步、检查点维护和恢复等。

在互联网协议栈中，这两层都是交给应用层实现的。

8.5、各层次的数据单元

之前提到，不同层次的 PDU 有具体称呼。具体而言：

应用层的 PDU 成为报文（Message）
传输层的 PDU 称为报文段（Segment），如 TCP 段。如果是无连接方式，也称为数据报（Datagram）例如 UDP 数据报
网络层的 PDU 称为分组（Packet）。IP 数据报虽然名字里有“数据报”，但是是网络层的。
链路层的 PDU 称为帧（Frame）
物理层的 PDU 是位

第二章应用层

1、网络应用的体系结构

在第一章已经提到了，网络应用之间有 C/S 模式和 P2P 模式。

1.1、C/S 模式

S 指 Server，意为服务器。一直在运行，并拥有固定的 IP 地址，监听约定好的端口号。

C 指 Client，意为客户端。由客户端主动与服务器通信。客户端的 IP 地址可能是动态的。

两者之间的地位是不平等的。服务器持有各种资源，客户端向服务器请求资源。

这种模式的缺点是可拓展性比较差。如果客户端数量增多，服务器可能难以承载。C/S 模式下，随着客户端数量的增多，到达某个阈值后，性能会断崖式的下降。

另一个缺点是可靠性比较差。客户端都依赖于服务器。如果服务器宕机，所有的用户都会受到影响。

1.2、P2P 模式

各个端系统处于对等的地位，既可以做服务器，也可以是客户端。

因此拥有良好的可拓展性。每多一个节点，既是多了一个客户端，也是多了一个服务器。性能随着节点数量的增加，不会出现断崖式下降的情况。

缺点是难以管理，节点上线和下线的时间是不确定的，节点只有上线的时候才能发挥出其功能。

1.3、混合模式

即 C/S 模式和 P2P 模式的混合体。

例如 Napster，是一个 MP3 音乐文件分享的系统。每一个主机在中心服务器上注册，同时告知自己拥有的资源信息。需要下载某文件时，询问中心服务器，得到拥有该文件的主机。然后主机和主机之间传输文件。也就是说，查询文件是 C/S 模式的，文件传输是 P2P 模式的。

即时通信软件也是类似的原理。

2、进程通信

发起连接的进程称之为客户端进程，等待连接的进程称之为服务器进程。P2P 体系结构的一次会话中，也有客户端进程和服务器进程之分。

分布式进程之间要实现通信，需要考虑以下问题：

进程标识和寻址问题（用户）：每个进程需要有一个唯一的标识，能够通过这个标识来区分。同时还希望这个标识包含位置信息，能通过标识找到这个进程。
传输层提供的服务是怎么样的（服务）：需要知道形式是怎样的，SAP 和 API 是怎样的
怎样定义报文的语义来实现应用（用户使用服务）：定义应用层的协议、报文格式、报文解释等

2.1、第一个问题——对进程编码

现在采用的进程的标识或者说编码，一般包括三个部分：

IP 地址：唯一的 32 位的 IP 地址用于区分主机
使用的协议：TCP 或者 UDP
端口号（Port Number）：有许多使用 TCP 的进程，端口号用于确定是哪一个

有一些约定俗称的端口号，例如 Web 应用默认是 TCP 80 端口，FTP 服务是 TCP 21 端口。

2.2、第二个问题——穿过层间需要的信息

使用传输层的服务，要穿过层间的接口，需要一些信息：

本层要传送的报文（即 SDU）
目标进程的标识信息（IP 地址+TCP/UDP+端口号）
发送进程的标识信息（IP 地址+TCP/UDP+端口号）

除了 SDU 本身，传输时还要携带许多额外信息。为了尽量减少额外信息，要使用Socket（套接字）。

Socket 类似于操作系统中的句柄或者文件描述符，一个 Socket 就代表着（源 IP，源端口号，目标 IP，目标端口号）这个四元组。传输时只需要带上 Socket 即可，Socket 和对应的四元组由本地系统进行维护。这种形式也便于操作系统管理。

UDP 情况下，只需要提供目标 IP 和目标端口，一个 Socket 指代一个二元组。

套接字相当于指定了一个门或者端节点（TCP Socket 指定了两个，UDP Socket 指定了一个），进程通过门发送和接受报文。

2.3、第三个问题——指定应用层协议

应用层协议，定义了运行在不同端系统上的进程如何相互交换报文。具体而言，包括交换的报文的类型；各种报文类型中的语法、各个字段的语义、进程何时发送报文，如何进行响应等内容。这些都在介绍协议时提到了。

应用协议只是应用的组成部分之一，应用本身还包括用户界面、自身业务处理逻辑等。

应用层要用到传输层提供的服务，不同的应用需要的服务特性不同。一般考虑传输层服务的这些方面：

数据丢失率
延迟
吞吐量
安全性

例如文件传输服务对延迟不敏感，但对数据丢失率的要求非常高；但是直播对延迟非常敏感，但是可以容忍一定的数据丢失。

从另一个方面考虑，传输层提供了 TCP 和 UDP 两大类型的服务。

TCP 有可靠的传输服务，同时有流量控制、拥塞控制等功能；UDP 则是不可靠的。

UDP 无需建立连接，节省时间，适合事务性的引用。不做可靠性的工作，适合那些对实时性要求比较高而对正确性要求不高的应用。没有流量控制和拥塞控制，应用就能够按照设定的速度发送数据，不会受到策略的影响。

TCP 和 UDP 自身都不提供任何安全性，实际内容都是明文传输的。

SSL 库基于 TCP 实现，可以提供加密的 TCP 连接。

3、Web 和 HTTP

Web 是一种应用，HTTP 是用于支持 Web 应用的协议。

3.1、Web 页面和 URL

一个Web 页面由若干个对象组成。

对象可以是HTML（HyperText Markup Language，超文本标记语言）文件、图片、Java 小程序、声音文件等。

Web 页一般包含一个基本的 HTML 文件，这个 HTML 文件中再包含若干个对象的引用（链接）。

一般通过URL（Uniform Resource Locator，统一资源定位符）来引用对象

以http://user:psw@www.baidu.com/home/file:port为例，来说明一下 URL 的结构

协议名		用户		口令		主机名	路径名		端口
`http`	`://`	`user`	`:`	`psw`	`@`	`www.baidu.com`	`/home/file`	`:`	`port`

支持匿名访问时，用户名和口令都是可选的；一般 Web 应用默认是 80 端口，也可以不给出。所以最终我们在浏览器地址栏看到的一般是http://www.baidu.com/home/file。

客户端发起请求，接受到 base HTML 之后，浏览器解析 HTML，渲染出来。如果其中包含一些 URL，就再根据这些 URL 去请求其他资源。最终渲染出一个完整的网页。

3.2、HTTP

HTTP（HyperText Transfer Protocol，超文本传输协议）是无连接的，运行在 TCP 之上，是 C/S 模式。

HTTP 是无状态的，不维护客户的任何信息（一次会话结束之后，不会记得和谁连接过，传输了什么等信息）

HTTP/1.0：由 RFC 1945 规定，是非持久 HTTP，也就是说一次会话只能传输一个对象。
HTTP/1.1：由 RFC 2068 规定，默认使用持久连接，是持久 HTTP。连接建立之后，可以在这个连接上传输多个对象，再关闭。服务器端采用先来先服务的策略，如果队首是一个很大的文件，队列中的其他文件就会长时间不被处理，这种现象被称之为队首阻塞（HOL 阻塞）。
HTTP/2：由 RFC 7540 规定。可以根据客户端指定的对象优先级来安排请求对象的传输顺序。还可以将对象分成帧，每个对象轮流发一个帧，减轻 HOL 堵塞。
HTTP/3：增加了拥塞控制和安全性相关的内容，以及更多基于 UDP 的流水线传输。

3.3、响应时间模型

RTT 往返时间（Round-Trip Time），是指一个小分组从客户端到服务器，再回到客户端所需的时间（由于是小分组，本身的传输时间忽略）。

则客户端从发起请求，到最终拿到 HTTP 响应所需的响应时间包括：

一个 RTT，用于发起 TCP 连接
一个 RTT，用于发起 HTTP 连接并获得响应
对象（基本 HTML）的传输时间

alt text

非持久的 HTTP 每个对象都要两个 RTT。每个对象都要重新建立 TCP 连接，操作系统必须为每个 TCP 连接分配新资源。

而持久 HTTP 在服务器发送 HTTP 响应之后，仍然保持 TCP 连接。客户端可以直接发送下一个请求。

进一步的，持久 HTTP 还可以分为流水线方式和非流水线方式：

非流水线方式：得到上一个 HTTP 响应之前，不能发送下一个 HTTP 请求
流水线方式：发送了一个 HTTP 请求之后，不用等 HTTP 响应，可以接着发下一个请求。这是 HTTP/1.1 的默认模式。

3.4、HTTP 报文格式

HTTP 报文包括请求报文和响应报文。HTTP 报文是 ASCII 编码的，所以解码之后是人可阅读的。

3.4.1、HTTP 请求报文

一个 HTTP 请求报文的例子如下：

POST /somedir/page.html HTTP/1.1
Host: www.someschool.edu
User-agent: Mozilla/4.0
Connection: close
Accept-language:fr

{
    .....
}

第一行是请求行，包括命令、路径、使用协议
接下来几行是首部行，包括主机名，客户端等
然后是一个额外的换行符结尾，表示报文结束
如果是 POST 请求，还需要上传一些内容，放在最后的实体主体（Entity Body）中

向服务器提交表单有两种方式：

POST 方式，也即直接把表单放在请求报文换行符后面的实体主体中
URL 方式，把信息放在 URL 中，以参数形式上载。例如http://www.baidu.com/s?user=114514&psw=1919180

HTTP/1.0 的命令有 GET、POST、HEAD。其中 HEAD 命令是只需要基本 HTML 的头部的意思（HTML 也分为头部和主体），一些搜索引擎只获取头部来建立索引，方便用户搜索。

HTTP/1.1 在此基础上还有 PUT 和 DELETE。

3.4.2、HTTP 响应报文

一个响应报文的例子如下：

HTTP/1.1 200 OK
Connection close
Date: Thu, 06 Aug 1998 12:00:15 GMT
Server: Apache/1.3.0 (Unix)
Last-Modified: Mon, 22 Jun 1998
Content-Length: 6821
Content-Type: text/html

data data data data data ...

第一行是状态行，依次是协议版本、状态码、状态文本。状态文本简要描述了状态码的含义
之后是首部行，包括日期、服务器信息、内容长度等。通过长度，能确定哪些是有用的数据。
紧接着，也是一个额外的换行用于分隔
最后是 HTML 的具体内容

一些状态码和状态文本：

200 OK：表示请求成功，请求对象就在响应报文的后续部分
301 Moved Permanently：表示请求的对象已经被永久转移了，其新的位置在响应报文首部行的 Location 字段。客户端会自动用新的 URL 去获取对象。
400 Bad Request：通用的错误代码，表示请求不能被服务器解读
404 Not Found：表示请求的对象在服务器上找不到
505 HTTP Version Not Supported：服务器不支持该 HTTP 版本

3.5、Cookies

之前提到，HTTP 是无状态的协议。这在一些电子商务网站上不太合适，这种情境下需要维护客户端的信息，包括他曾经买过什么，订单状态等等。

可以通过Cookies 技术来解决，由 RFC6265 规定。

客户端第一次访问某服务器，这个服务器就可以在响应报文加一个 set-cookie 首部行。之后客户端再访问的时候，在请求报文中，带上 cookie 首部行，值就是之前服务器提供的。这样 cookie 就和客户对应起来。

服务器可以在后端维护一个数据库，利用 cookie 来索引；客户端的浏览器也可以维护一个 cookie 文件，每次访问指定网站时，就带上相应的 cookie。

3.6、Web 缓存

可以设置代理服务器（proxy server）。优先到代理服务器（缓存）请求，如果代理服务器中有，直接返回（这也称之为命中）。如果没有，代理服务器再向源服务器请求。

对客户端来说，引入代理服务器后，获得请求变快了；对于源服务器来说，也降低了负载。

利用条件 GET可以控制从缓存中获取的版本。

在请求报文中首部行中加入If-Modified-Since: <some date>字段，如果缓存中的文件这个日期之后没被修改过，就会返回304 Not Modified。如果修改过，会返回200 OK以及最新的内容。

4、FTP

File Transform Protocol，文件传输协议

alt text

FTP 由 RFC959 规定，是 C/S 模式，FTP 服务器默认监听的端口号是 21。

FTP 协议是有状态的协议，服务器要维护客户端的状态，要知道哪个客户端，现在在哪个目录。

FTP 工作的过程如下：

FTP 客户端主动向 FTP 服务器 21 号端口发起请求，建立 TCP 连接，这个连接称之为控制连接。服务器会验证用户名和指令。
客户端通过控制连接发送命令，浏览服务器文件目录或者发出下载文件请求。
服务器收到文件下载请求后，主动向客户端的 20 端口建立一个数据连接，然后通过数据连接来传输数据。

控制连接称之为带外传送，数据连接是带内传送。

FTP 的命令和响应（状态码）也都是 ASCII 编码的。

一些命令：

USER username
PASS password
LIST filename、RETR filename（即 GET）、STOR filename（即 PUT）

一些状态码和状态文本：

331 Username OK, password required
125 data connection already open; transfer starting
425 Can't open data connection
452 Error writing file

5、Email

用户不直接与邮件服务器交互，而是使用用户代理（也即邮件阅读器这种软件），最终是由用户代理与服务器交互（Web 应用的用户代理是浏览器）。

邮件服务器之间通过SMTP（Simple Mail Transfer Protocol，简单邮件传输协议）来进行通信

5.1、SMTP 与邮件发送接收过程

SMTP 由 RFC 2821 规定，运行在 TCP 之上，监听 25 号端口。SMTP 是持久连接的。

SMTP 中的命令和响应也都是 ASCII 编码的，直接打印出来时人可读的。响应包括响应码和响应文本。

邮件传输包括三个阶段：握手（建立 TCP 连接）、传输报文、关闭

一次发送和接受邮件的过程如下：

A 通过用户代理撰写邮件并发送给 B
A 的用户代理把邮件发送给 A 的邮件服务器中，邮件放在报文队列中
A 的邮件服务器作为客户端，按 SMTP，主动向 B 的邮件服务器发起 TCP 连接
A 的邮件服务器向 B 的邮件服务器传输邮件
B 的邮件服务器将 B 的邮件放到 B 的邮箱
B 通过用户代理，将邮箱里的邮件拉取下来

引入队列，没邮件可发时，可以定期清空队列，不用时刻待命，减少资源消耗；邮件较多时，排队可以缓解拥挤

HTTP 主要是用于拉取，是拉协议；SMTP 主要是用于推送，是推协议

HTTP 每个对象都封装在各自的响应报文中。base HTML 中可能包含其他对象的引用，这些对象必须通过另外的响应报文获取。

SMTP 中，可以将多个对象都包含在一个报文中。

RFC 822 规定了文本报文的标准，一个文本报文分为首部和主体。

首部有一系列首部行，例如：

1
2
3

To:
From:
Subject:

主体是具体内容，只能是 7 位 ASCII 码可以表示的字符范围

5.2、MIME

Multimedia Mail Extension，多媒体邮件扩展

SMTP 要求报文必须是 7 位 ASCII 编码的，这样表示非 ASCII 字符就很麻烦，于是引入了 MIME。

使用 MIME 要在首部行加上 MIME-Version 字段，报文段使用 base64 编码。这样最终都是 ASCII 字符，可以使用 SMTP 传输了。接收到之后，再解码得到原文。

5.3、邮件访问协议

从服务器访问邮件需要用到邮件访问协议，包括：

POP3（Post Office Protocol，邮局访问协议），由 RFC 1939 规定
IMAP（Internet Mail Access Protocol），由 RFC 1730 规定
HTTP

POP3 协议使用包括两个阶段：

用户确认阶段，客户端用 user、pass 命令来声明用户名和口令，服务端响应有+OK 和-ERR
事务处理阶段，客户端用 list, retr, dele, quit 等命令来交互

具体还有两种模式：

下载并删除模式：客户端拿到的是邮件的唯一副本，删除之后，服务器上就没有这个邮件了
下载并保留模式：客户端拿到的只是一个副本，其他设备仍然能访问这个邮件

POP3 在会话中是无状态的。只维护用户是谁，在哪个邮箱中，不支持远程目录的维护。

IMAP 提供远程目录的维护，允许用户用目录来组织报文，是有状态的。

6、DNS

Domain Name System，域名系统。DNS 提供了主机名到 IP 的转换，是一种运行在应用层的基础设施，是核心 Internet 功能。DNS 不直接为人类所用，而是供 Web 应用，FTP 应用等使用。DNS 是基于 UDP 的。

之前提到，用 IP 地址来表示主机和路由器。但是 IP 地址是一串数字，不方便记忆。人类通常倾向于使用有意义的字符串来标识互联网上的设备。于是有必要存在一种工具，能做字符串和 IP 地址之间的转换。这就是 DNS。

DNS 要解决的问题：

如何命名设备？首先新名字要好记，便于人类使用，而且不宜重复。
如何完成名字到 IP 地址之间的转换？
如何维护这样的映射关系？

一开始，采用的是没有层次的命名，且只使用一台机器来维护主机名到 IP 地址的映射表。节点数量很少时，这种方法没有问题。后来，节点数量越来越多，上面的方法就不适用了。于是出现了 DNS。

DNS 的主要思路是：

分层的，基于域的命名机制
借助若干个分布式的数据库完成名字到 IP 地址的映射

DNS 除了完成主机名和 IP 之间的转换之外，还有其他功能：

主机别名和规范名字之间的转换
邮件服务器别名到邮件服务器规范名字之间的转换
负载均衡。也即平衡各个 DNS 服务器上的询问。

6.1、层次化命名

DNS 解决第一个问题的方式采用层次树状结构命名。

最上层是根，根被划分为几百个顶级域（top level domains）。顶级域包括两类：

通用的（generic）：.com .edu .gov .int .mil .org 等
国家的（countries）：.cn .us .nl .jp 等

继续往下，每个域可以划分为若干子域。

域和域之间用逗点间隔。整个命名空间就构成了一棵树。所以一个主机名形如主机名.子域名.顶级域名。

一个域管理其下一层的子域。

例如 .cn 下面有 edu.cn com.cn 等。创建一个新的域必须征求其所属域的同意。

域之间的关系与物理网络无关。一个域的主机可以不在一个网络中，一个网络的主机也不一定在一个域里面。域只是一种逻辑的划分。

6.2、分布式名字服务器

DNS 解决第二个问题的方式是建立分布式的名字服务器，让主机通过访问这些名字服务器来获取名字到 IP 地址的映射。

6.2.1、DNS 服务器的层次结构

只使用一个名字服务器（Name Server），存在可靠性、可拓展性差以及难维护等问题。

之前提到，DNS 将命名空间划分为若干个互不相交的区域（Zone）。每个区域上有对应的名字服务器，这个服务器维护着所管辖的下一层子域的权威信息。

从上到下依次是根 DNS 服务器、顶级域 DNS 服务器（Top-Level Domain Sever，TLD Sever）、权威 DNS 服务器。

根 NDS 服务器有其管辖的子域对应的 TLD 服务器的 IP 地址，TLD 服务器有其管辖的子域对应的权威 DNS 服务器的 IP 地址。

名字服务器中，维护着资源记录（Resource Records，RR），其格式为(Name, TTL, Type, Cass, Value)。其中，

Name：就是域名
TTL：之前已经介绍过，是生存时间。如果是权威信息，TTL 就是无限长；如果是缓存信息，就是一个有限值。TTL 归零，这个记录就要被删掉
Class：指类别，用于区分不同的网络类型。如果是 Internet，Class 的值就是 IN
Type是资源记录的类型，决定了 Name 和 Value 之间的关系
- Type=A，则 Name 是主机名，Value 为对应的 IPv4 地址
- Type=AAAA，则 Name 是主机名，Value 为对应的 IPv6 地址
- Type=CNAME，则 Name 是别名，Value 为对应的正规名字
- Type=NS，则 Name 是一个域名，Value 是一个该域名的权威服务器的域名
- Type=MX，则 Name 是一个邮件服务器的别名，Value 是该邮件服务器的正规名字

可以有多个 CNAME 记录，将多个别名指向一个正规名；然后再用一个 A 或者 AAAA 记录，将正规名，指向一个 IP 地址。

如果 IP 地址更改，只需要更改一个 A 记录即可，提供了灵活性。

DNS 的大致工作过程：

应用调用解析器（resolver）
解析器作为客户端，向名字服务器（名字服务器的 IP 地址是设定好的）发查询报文
名字服务器返回响应报文（包含了名字对应的 IP）
应用得到 IP 地址

还有一种 DNS 服务器称之为本地 DNS 服务器。严格上讲，不属于之前三层的层次结构。

每一个 ISP 都有一个本地 DNS 服务器，也称为默认名字服务器。一个主机发起的 DNS 查询会先发到本地 DNS 服务器，由本地 DNS 服务器转发到之前提到的层次结构中。

本地 DNS 服务器的地址是预先设置好的，区域内的主机都知道。

6.2.2、查询过程

例如要查询jwxt.sysu.edu.cn的 IP 地址。

首先会尝试在本地 DNS 服务器中查询。查询上传到本地 DNS 服务器之后，如果有相应的记录，则可以直接返回对应的 IP 地址。

如果不在：

本地服务器转发查询到.cn对应的根 DNS 服务器
根 DNS 服务器收到查询后，再转发查询到.edu对应的 TLD 服务器
TLD 服务器收到查询后，再转发查询到.sysu对应的权威 DNS 服务器
权威 DNS 服务器中有jwxt.sysu.edu.cn的 A 记录，生成响应报文，一路回传。
最终，原主机得到了jwxt.sysu.edu.cn的 IP 地址。

上面这种查询方式称为递归查询。递归查询中，根 DNS 服务器的负担比较重。

alt text

另一种查询方式是迭代查询：

本地 DNS 服务器问.cn根 DNS 服务器，根 DNS 服务器返回.edu TLD 服务器的地址
本地 DNS 服务器再问这个 TLD 服务器，TLD 服务器返回一个.sysu权威 DNS 服务器的地址
本地 DNS 服务器再问这个权威 DNS 服务器，权威服务器返回 jwxt.sysu.edu.cn的 IP 地址。
最终，原主机得到了jwxt.sysu.edu.cn的 IP 地址。

alt text

查询到了一个映射之后，通常会直接缓存在本地 DNS 服务器中，这样下次再查询相同的域名，就可以直接返回 IP 地址了。

但是可能存在数据不一致的问题。通常会将缓存的 TTL 设置为 2 天，到时间自动删除，需要再去获取新的数据。

6.2.3、DNS 报文

DNS 查询报文和响应报文的格式相同。

报文最开头两字节是 ID 号，用于区分不同的查询和响应。对应的查询和响应的 ID 号应该是相同的。

接下来两字节是 flag，用于标记查询方式，希望响应是权威信息还是缓存信息等。

6.3、维护

有了以上架构后，解决第三个问题就很简单了。一个维护的例子如下：

假设我们成立了一家公司，公司的域名是orange.com，公司网站是www.orange.com，邮件服务器是mail.orange.com，DNS 服务器是dns.orange.com。我们需要进行以下操作，来让别人能够访问我们的网站和邮件服务器：

要在 .com 的 TLD 服务器中添加两条记录
- 一条 A 记录，Name是权威服务器域名dns.orange.com，Value是服务器的 IP 地址
- 一条 NS 记录，Name是orange.com，Value是其权威服务器的域名，也即dns.orange.com
要在 orange.com 对应的权威服务器中添加两条记录
- 一条 A 记录，Name是www.orange.com，Value是该 Web 服务器的 IP 地址
- 一条 MX 记录，Name是邮件服务器的别名，Value是邮件服务器的正规名 mail.orange.com

7、P2P 应用

纯 P2P 架构中，每一个节点既可以是服务器，也可以是客户端。其特点是：

节点上线时间不确定，很少有一直在运行的服务器
任何端系统之间都能直接通信，主要利用Peer 节点（对等节点）的服务能力
Peer 节点是间歇上网，每次 IP 地址都可能会变化

具体的 P2P 应用有文件分发（如 BitTorrent）、流媒体（如 KanKan）、VoIP（Voice over Internet Protocol）

Peer 节点之间建立一次会话可以看作是连了一条边，这样构成的一个逻辑上的网络称之为覆盖网（Overlay）。

如果覆盖网的结构是随意的，就称之为非结构的 P2P；如果覆盖网中，是有环、树这样的特殊结构，就称之为结构化 P2P或者DHT P2P（Distributed Hash Table P2P，散列表 P2P）

7.1、非结构 P2P

7.1.1、集中式目录——Napster

集中式目录是非结构 P2P 的一种。之前讲到的 Napster 就是一个例子。

每个节点上线时，都要向中心目录服务器报告，自己已经上线以及自己的 IP 和所持有的资源。所以中心服务器就可以维护管理当前活跃节点的状态。当然，节点下线的时候也要告知目录服务器。

集中式目录存在一些问题：

单点故障：一旦目录服务器故障，整个网络都宕机，无法运作
性能瓶颈：随着用户数量增多，中心服务器压力变大

7.1.2、完全分布式——Gnutella

完全分布式是另一种非结构化的 P2P。其例子是Gnutella 协议，这是一种基于泛洪查询的协议。

Gnutella 中没有中心服务器，所有节点都是完全对等的。每一个节点一般与 10 个以内的邻居建立起覆盖网。

当需要查询的时候，向所有邻居发出请求；邻居收到请求后，又向所有自己的邻居发出请求。很快，请求就能遍布全网。如果查询命中，再原路返回。这样原来的节点，就知道网络中哪些节点拥有对应的资源。

当然不能无止尽的泛洪，可以设置有限 TTL 或者让节点记住自己已经泛洪过来加以限制。

一个新加入的节点使用 Gnutella 的前提是，要先建立起一个有 8 到 10 个邻居的覆盖网。

一开始会有一张列表，列表上是大概率在活跃的节点。新节点向列表上的节点发一个 Ping 报文。列表上的节点（如果是活着的节点）收到报文之后，回应一个 Pong 报文，同时转发给自己的邻居。其他的节点收到 Ping 报文之后，也给原节点回应一个 Pong 报文。

这样这个新节点就知道自己可以联系到哪些节点了。可以从中随机地选择一些节点作为自己的邻居，建立起覆盖网。

7.1.3、混合式——KaZaZ

还有混合式的非结构 P2P，例如 KaZaZ。

有组长和组员之分。组员首先向自己的组长请求，如果组长知道，就直接返回；如果组长不知道，由组长向其他组长进行泛洪查询。

文件有对应的元信息以及一个哈希值作为唯一标识。

7.1.4、BitTorrent

文件被均分为一个个的块，一组称之为洪流（Torrent）的节点，每个节点拥有一部分文件块。节点用位图（Bitmap）来维护自己拥有的文件块的情况。

节点通过泛洪请求其他节点，来获得完整的文件。当洪流中，所有节点的带宽之和越大，就说明数据交换越多，网络效率越高。为了达成这种局面，BitTorrent 采用了一系列的策略。

请求者角度：

请求者会优先请求那些网络中较为稀缺的块，使得块变得不稀缺。避免稀缺的块成为瓶颈。
会周期性向邻居询问有哪些块，交换位图信息。

提供者角度：

一报还一报（tit for tat）：会进行评估，优先向曾经给自己提供大带宽的节点提供服务
优化疏通：过一段时间，也会随机选择一些节点提供服务，以挖掘潜在的大带宽邻居

还有跟踪服务器（Tracking server）来维护各个洪流，以及洪流中的节点信息。用户可以通过 BT 客户端，向跟踪服务器发起请求。然后跟踪服务器会发回对应的洪流中部分节点的列表，然后就可以加入到洪流中，完成文件传输。

7.2、结构 P2P

每一个节点 IP 地址做哈希，然后按哈希值的大小顺序建成一个环。

文件的哈希值也按照大小顺序，维护在环上的各个节点之上。

8、CDN

现在，视频流量占了互联网流量的一大部分。然而目前，不仅用户数量十分庞大，且不同用户的特性不同（移动用户还是有线接入？带宽大还是小？），以前的技术无法较好满足用户需要，需要新的技术来解决这些问题。

视频可以看作是图像的序列，图像可以看成是像素的排列。每一个像素可以用若干个比特位来表示。直接传递原始的视频，所需的带宽非常大，是不可接收的。所以往往要对其进行编码、压缩。

编码的原理是利用时间上和空间上的冗余。时间上的冗余指相邻图像之间，可能只有一部分像素点不同，只需传输这一部分即可；空间上的冗余指同一张图像上，可能有连续的，完全相同的像素点，则只需要传输一个该像素点加上数量即可。

编码方式可以分为两大类，CBR（Constant Bit Rate）和VBR（Variable Bit Rate）。具体有MPEG1（1.5Mbps），MPEG2（3-6Mbps），MPEG4（常用于互联网，64Kps~12Mbps）

8.1、多媒体流化服务

现在在网站上播放视频，不是先从服务器下载整个视频文件之后，再播放。而是边下边播，就像建立了一个视频流一样，从服务器流到本地。这就是多媒体流化服务（Dynamic Adaptive Streaming over HTTP，DASH），是 HTTP 上的动态自适应流媒体协议。

流式视频的主要挑战：

服务器到客户端的带宽随时间变化。网络拥挤程度会不断变化。
拥塞造成的数据包延迟或者丢失会影响视频的播放质量。
客户端播放开始后，播放必须与原始时间匹配，也即要能保证连续播放。但是网络延迟是可变的。
客户端还会进行一些交互，例如快进、快退、暂停、重播等。

服务器端，会将视频文件分割为多个块。然后每个块都是独立存储，而且会提供不同编码格式，不同码率的版本。

告示文件（manifest file）用于描述不同块的信息。DASH 的告示文件 MPD（Media Presentation Description）使用 XML 格式，对音视频流作了多个维度的划分和相关信息说明。

客户端首先获取告示文件，然后会周期性测量到服务器的带宽。综合带宽和缓冲区的情况，查询告示文件，隔一个时刻请求一个块。客户端自适应决定，什么时候去请求块，请求什么编码速率的块，去哪个服务器请求块。

8.2、CDN

DASH 解决了用户特性不同的问题，CDN（Content Distribution Networks，内容分发网络）解决的是大量用户的问题。

只由单个超级服务器为所有用户提供服务，客户端到服务器的平均跳数多，而且根据“二八定律”，会浪费大量带宽在相同的内容上，且本身拓展性差。

CDN 就是设置大量的缓存节点，用户就近获取，而不需要到源服务器去获取。

布置有两大类型：

Enter Deep：将 CDN 服务器部署到 Local ISP 的级别，也即更贴近用户。这样所需的跳数少，但是需要部署的服务器数量较多，管理起来比较困难。例如 Akamai 公司，首创 CDN 技术。
Bring Home：只部署在少数的关键位置，然后采用租用线路的方式，将服务器簇连接起来。这种方式所需的跳数会多一些，但是只要部署少量服务器就能取得不错的效果。例如 LimeLight 公司。

用户想要获取某个资源，会被重定位到最近的拷贝请求。

CDN 是一个应用层的技术，是 OTT（Over The Top）的，主要位于网络边缘。OOT 带来了一些挑战：

从哪个 CDN 节点获取内容
用户在网络拥塞时应该采取什么行为
CDN 节点上应该采取什么部署策略，也即哪个节点应该存储哪些内容。

9、Socket API 编程

9.1、TCP 编程

首先介绍会用到的两个结构体

struct sockaddr_in {
    short int sin_family;      // 地址族
    unsigned short int sin_port; // 端口号
    struct in_addr sin_addr;   // IP 地址
    unsigned char sin_zero[8]; // 对齐
};
struct in_addr {
    unsigned long s_addr;      // 32 位 IPv4 地址
};

sin_family代表地址族（该结构体不仅仅用于 TCP/IP 这一类的通信），设置为AF_INET常量时，表示使用 IPv4 地址
sin_zero用于对齐，数组元素值一般设为 0

struct hostent {
    char *h_name;        // 官方主机名
    char **h_aliases;    // 主机别名的数组
    int h_addrtype;      // 地址类型 (通常是 AF_INET)
    int h_length;        // 地址长度
    char **h_addr_list;  // IP地址的数组
    #define h_addr h_addr_list[0]; // IP地址
};

设想一个场景：客户端从标准输入获取一个字符串，然后发送给服务器，服务器将这个字符串转换为大写之后再发回给客户端。

服务端代码如下：

void main(int argc, char *argv[]) {
    int welcomeSocket, connectionSocket;
    struct sockaddr_in server_addr;
    struct sockaddr_in client_addr;
    struct hostent *ptrh;

    int addrlen = sizeof(address);
    char buffer[128] = {0};

    port=atoi(argv[1]);

    // 创建welcomeSocket
    welcomeSocket = socket(AF_INET, SOCK_STREAM, 0));
    server_addr.sin_family = AF_INET;
    server_addr.sin_addr.s_addr = INADDR_ANY;
    server_addr.sin_port = htons(unsigned short(port));

    // 绑定welcomeSocket与服务器IP
    bind(welcomeSocket, (struct sockaddr *)&server_addr, sizeof(server_addr));

    // 监听连接
    listen(welcomeSocket, 10);

    while(1){
        // 接受客户端连接，建立connectionSocket
        connectionSocket = accept(welcomeSocket, (struct sockaddr *)&client_addr, &addrlen)
        // 读取客户端发来的字符串
        n=read(connectionSocket, buffer, sizeof(buffer));

        buffer=upper(buffer);

        n=write(connectionSocket, buffer, strlen(buffer)+1);

        close(connectionSocket);
    };
}

客户端的代码类似：

void main(int argc, char *argv[])
{
    int clientSocket;
    struct sockaddr_in client_addr;
    struct hostent *ptrh;

    int addrlen = sizeof(client_addr);
    char buffer[128] = {0};

    host = argv[1];
    port = atoi(argv[2]);

    // 创建welcomeSocket
    clientSocket = socket(AF_INET, SOCK_STREAM, 0));
    client_addr.sin_family = AF_INET;
    client_addr.sin_port = htons(unsigned short(PORT);
    // 根据域名获取服务器IP地址
    ptrh=get_host_by_name(host);
    memcpy(&client_addr, ptrh->h_addr, ptrh->h_length)

    // 绑定welcomeSocket与服务器IP
    bind(welcomeSocket, (struct sockaddr *)&server_addr, sizeof(server_addr));

    // 尝试连接服务器
    connect(clientSocket, (struct sockaddr*)&client_addr, sizeof(client_addr));

    gets(buffer);
    n=write(clientSocket, buffer, strlen(buffer)+1);
    n=read(clientSocket, buffer, sizeof(buffer));
    printf("%s\n", buffer);

    close(clientSocket);
}

基本的过程可以叙述如下：

服务端创建welcomeSocket，然后将这个 socket 与本地的某个 IP 和端口号绑定。开始监听listen
客户端创建 clientSocket，不需要绑定（实际上会有一个隐形的绑定）。
客户端调用connect，提供服务器的 IP 和端口，尝试建立连接
服务端收到连接请求后，调用accept，创建出 connectionSocket，这是一个四元组，与客户端的 IP、端口和服务端的 IP、端口绑定。同时给客户端一个响应。
客户端收到响应之后，clientSocket 变为有效的 socket，完成接下来的工作。

9.2、UDP 编程

UDP 编程基本类似。之前已经提到，UDP 的 socket 是一个二元组，只需与本地的 IP 和端口绑定，而且也不需要先建立连接，所以也不需要 welcomeSocket，不再赘述。

第三章传输层

传输层提供不同主机上进程之间的逻辑通信。

发送方将应用层的报文分成若干个报文段，然后传递给网络层；接收方将报文段重组为报文，然后传递给应用层。这一层常用的协议是 TCP 和 UDP。

传输层服务不仅依赖于网络层提供的服务，同时对网络层的服务进行增强。因为网络层的 IP，采用的是 best effort 策略，可能发生数据丢失、顺序混乱等问题。

其中一个很重要的增强就是复用/解复用。因为网络层是主机到主机的服务，而主机上有许多进程，通过实现复用/解复用，就可以实现传输层的进程到进程的服务。

有些方面是不能得到增强的，例如带宽和延时。

1、多路复用/解复用

简而言之，通过引入额外的端口信息来区分不同的进程。

创建 socket 并绑定时，就把进程 PID 和本地 IP 和端口号绑定起来了。通过 socket 进行传输时，自然就能知道目标 IP 和目标端口号。

在传输层，根据 socket 将本地 IP、端口和目标 IP、端口等信息用头部加以封装成段，再向下传输；到了接收方，接收方就可以根据这个头部信息，找到正确的 socket，从而找到正确的进程。

2、UDP

User Datagram Protocol，用户数据报协议，由 RFC768 规定。UDP 是无连接的，且提供的是尽力而为的服务，报文可能丢失、乱序。

UDP 常用于流媒体服务和事务性的应用（一次往返搞定，不需要建立起连接多次通信）

UDP 存在的理由：

不建立连接，延时小
不需要在发送端和接收端维护连接状态，简单
报文段的头部较小，开销比较小
无拥塞控制和流量控制，可以尽量快的发送报文

报文格式如下：

源端口号，两字节
目标端口号，两字节
整个报文的长度，两字节
校验和，两字节
报文主体，长度可变

其中校验和的计算如下：

构造伪头部，和 UDP 报文拼接在一起
拼接后的数据 16 位一组，看成若干个整数，然后相加。两个 16 位整数相加，如果最高位有进位，就加到最低位上（进位回滚），这样算出所有整数的“和”。最后取反，得到最终的校验和。

校验时，按照相同方式，构造，分组，算出所有整数的和。如果与收到的报文中的校验和相加，恰好是全 1，就说明大概率是正确的。（因为正确的校验和是恰好取反的）

如果不是全 1，则数据一定出错的；如果是全 1，也有可能出错，这种情况称之为残存错误。

3、可靠数据传输的原理

可靠数据传输（Reliable Data Transform，RDT）

RDT 在应用层、传输层和数据链路层都非常重要。下层提供的服务是不可靠的，这就需要可靠数据传输协议来使向上提供的服务变成可靠的。

信道的不可靠性决定了可靠数据传输协议的复杂性，设计 RDT 的思路：

渐增式地开发，也即一开始先假设下层信道是可靠的，然后逐渐去掉一些条件，让下层变得不可靠，然后增加 RDT 的机制，重新变为可靠的。
只考虑单向传输。双向传输等价于链各个单向传输。
使用有限状态机（FSM）来表述双方之间的状态转换。

3.1、RDT 1.0

假设下层信道完全可靠，没有比特出错，也不会出现分组丢失。

则发送方和接收方的 FSM 如下所示，其中横线上是事件，横线下是采取的动作：

协议只需要完成打包和解包的工作，没有其他的动作。

3.2、RDT 2.0

假设信道不会出现分组丢失，但是可能出现比特反转的现象，需要引入确认和校验机制。

发送方要根据规定的校验机制，计算校验和，并将得到的校验和一起发给接收方。

接收方接收到分组后，进行校验。如果校验通过，则向接收方发送 ACK 响应，显式地告知，已经正确的接收；否则发送 NAK 响应，显式地告知分组出错。

如果发送方接到 NAK 响应，就要重新发送一次分组。

alt text

像这样发送方发送一个分组，然后等待接收方正确应答后，才能发送下一个分组的协议称之为停止等待协议。

3.3、RDT 2.1

RDT2.0 有一个问题，如果 ACK 和 NAK 也出错，则接收方收到这个错误的 ACK/NAK 之后，不知道该如何动作。RDT 2.1 在 RDT2.0 的基础上，解决 ACK/NAK 可能出错的问题，其对 ACK/NAK 也引入校验机制。

发送方如果发送分组之后，收到的响应不是 ACK/NAK，直接重传一份。分组上要携带一个序号，用于区分不同的分组。

接收方如果再次收到一个序号相同的分组，就知道自己的响应可能出错了，于是再次发一个 ACK。

发送方的 FSM：

接收方的 FSM：

序列号只需一位的 0 和 1 就够了。

接收方接到正确的序号为 0 的分组后，如果再次接到一个 0 分组，就说明 ACK 出错了，需要再次发送一个 ACK。如果接到 1 分组，说明上一个 ACK 是正确的。

3.4、RDT 2.2

在 RDT2.1 的基础上，舍弃了 NAK，使用带编号的 ACK。

接收方收到正确的分组 1，就返回 ACK 1；如果收到不正确分组 1，就返回 ACK 0，以代替 NAK。

发送方如果收到不对应的 ACK，则和收到 NAK 一样，重传当前分组。

带编号的 ACK 可以进一步扩展，如果收到不正确的分组 N，就返回带最后一个正确接收到的分组编号的 ACK，即 ACK N-1。

发送方收到重复的响应，就说明分组出错了，重传当前分组。

为以后同时发送多个分组的的流水线协议做准备。

3.5、RDT 3.0

假设除了会出现比特反转之外，还会出现分组丢失。这种情况下，如果不引入额外机制，会出现死锁。发送方在等待接收方的 ACK，但是分组丢失了，接收方永远不可能发送 ACK。

RDT 3.0 通过引入超时重传机制来解决这个问题。

发送方超过一定时间没收到 ACK，就重传一份。由于分组是带序号的，接收方会根据序号直接丢掉重复的分组。

引入超时重传后的发送方的 FSM：

超时计时器要合理设置。如果设置的时间限制过短会降低效率：

alt text

如图，过早超时，仍然能够正常工作，但是效率较低，一半的分组和确认都是重复的。

这种停止等待协议，信道容量很大时，显得性能非常差。停止等待协议协议要求，发送一个分组后，在收到回应之前不能发送下一个分组，协议本身限制了物理资源的使用。

3.6、流水线协议

利用流水线原理，允许发送方在未得到对方确认的情况下一次发送多个分组。为实现流水线，首先必须要使用多个比特的序号。

除此之外，发送方和接收方都需要设置缓冲区：

发送方设置缓冲区，因为可能需要重传
接收方需要缓冲区，因为上层接收数据的速率和收到数据的速率可能不一致，还因为收到分组的数据可能是乱序的，要先进行排序。

流水线协议大致有两种，回退 N 步（GBN）和选择重传（SR）。这两者可以用滑动窗口协议来统一描述。

3.7、滑动窗口协议

3.7.1、发送窗口和接受窗口

将要发送的分组按序号顺序排成一列。

发送缓冲区就是这个序列上的一个滑动窗口，包含了若干个连续的分组。这些分组都是可以发送或者已发送但是未确认的分组。

发送窗口是一个发送缓冲区的子集，是一个更小的窗口，有前沿和后沿，包含已发送但是未确认的分组。发送窗口的范围不能超过发送缓冲区的范围。

发送窗口的大小为 1，就是停止等待协议；发送窗口的大小大于 1，就是流水线协议。

一开始，发送窗口的大小为 0，前沿和后沿重合。一旦发送了一个分组，前沿就向前移动。一旦有分组得到确认，后沿与整个发送缓冲区一起向前移动。

同样的，有接收缓冲区和接受窗口。接收缓冲区和接受窗口是一致的，只有它们覆盖范围内的分组才能被接收。

如果接收窗口的大小为 1，就是 GBN 协议。这种情况下，只能按序号大小的顺序接收。确认的方式是累计确认，也即返回 ACK N 时，表示 N 及以前的分组已经全部收到了（是按顺序接收的）。

如果接收窗口的大小大于 1，就是 SR 协议。这种情况下，只要是在范围内的分组，可以乱序接受。确认的方式是非累计确认，也即返回 ACK N 时，不代表 N 以前的分组都被接收了。

如果收到了接受窗口之外的分组，这个分组会被丢弃。

3.7.2、GBN 与 SR 的对比

GBN 协议的异常情况：触发超时重传时，会将当前发送窗口中所有的分组发送出去。因为一般是后沿的那个分组，也即最先发送的分组最先超时。而 GBN 协议下，接受窗口的大小为 1，只有这个分组被确认后，接收方才会接收后续分组。从表面上看，就是整个窗口内的分组都被重发一次。或者说，回到窗口内的第一个分组开始发送。所以称之为回退 N 步协议。

SR 协议的异常情况：触发超时重传时，只会重新发送触发超时的那个分组。所以称之为选择重传协议。

GBN 协议和 SR 协议发送窗口大小都大于 1，都可以未经确认发送多个分组。

不同点在于触发重传时的机制，如之前所述。GBN 协议只拥有一个超时计时器，是针对最老的还未被确认的分组；SR 协议有多个超时计时器，每一个未确认的分组都有一个。

GBN 实现起来简单，但是回退 N 步的代价较大。所以 GBN 适用于出错率低的场景。

SR 出错时，重传一个代价较小，但是实现起来复杂，接收方需要多个缓冲单元。所以 SR 适用于链路容量大（延迟大、带宽大）的场景，此时用 GBN，重传代价过大，SR 更合适。

4、TCP

Transmission Control Protocol，传输控制协议，由 RFC793、1122、1323、2018、2581 规定。

TCP 提供的是点到点的面向连接的服务，发送方和接收方均有缓存。且 TCP 是流水线的，有流量控制，是全双工通信。

TCP 传输的是可靠的、按顺序的字节流。从物理层面上讲，能传输的分组长度是有限制的，再刨去之后要加上的 TCP 头和 IP 头，TCP 会将字节流分为大小为MSS（Max Segment Size）的片段再进行传输。

4.1、TCP 报文

从前到后的结构如下：

16 位：源端口号
16 位：目标端口号
32 位：序号。这里的序号不是可靠数据传输中分组的序号，而是指当前分组主体内容的第一个字节，在整个字节流的偏移量+初始序号。初始序号是在建立连接是确定的，一般不是固定的 0 或者 1 之类的。
32 位：确认号。与序号类似，不是指分组的序号，而是字节的序号。当接收方响应 ACK N 时，说明接收方已经正确收到了字节流的前 N-1 及以前的所有字节，希望发送方从第 N 个字节开始发送。（累计确认）
16 位：首部长度（以 4 字节为单位）以及一些保留位和特征位
16 位：接收窗口（的大小）。即能接受的字节数量。
16 位：校验和
16 位：紧急数据指针

以上共 20 个字节，是首部必备的。接下来还可以有若干个字节的可选项，整个首部的长度由首部长度确定，再后面是长度不定的主体部分。

4.2、TCP 超时计时器的设置

超时计时器设置过长，对报文段丢失的响应较慢；设置过短，容易引起不必要的重传

首先会定时进行采样，也即发送一个测试的报文，然后记录延迟，得到 SampleRTT。

然后结合近期的采样值，进行指数加权移动平均：

$\text{EstimatedRTT}^{(n)}=(1-\alpha)*\text{EstimatedRTT}^{(n-1)}+\alpha*\text{SampleRTT}$

一个典型的 $\alpha$ 值 0.125

RTT 短时间内大致是呈高斯分布的，这只是估计出一个中值。还需要估计出方差，再利用 $3\sigma$ 原则，使得绝大部分延迟在正常范围内的报文不用重传。

偏离程度计算如下： $\text{DevRTT}=(1-\beta)*\text{DevRTT}+\beta*|\text{SampleRTT}-\text{EstimatedRTT}|$

一个典型的 $\beta$ 值是 0.25

最后超时计时器设置为 $\text{Timeout}=\text{EstimatedRTT}+4*\text{DevRTT}$

4.3、TCP 重传

TCP 采用累计确认。当接收方响应 ACK N 时，说明字节流 N 以及之前的数据均已收到。

例如发送方方连续发送序号为 92（长度为 8 字节）和序号为 100（长度为 20 字节）的包，接收方响应 ACK 100 和 ACK 120。但是 ACK 100 丢失，发送方只收到 ACK 120。这不会导致发送方重传序号 92 的包，因为这是累计确认的。只有等到超时，发送放才能意识到序号为 92 的包丢失了，然后重传。

TCP 超时时间由 4.2 中提到的公式计算。且触发重传时，会将下一次的超时时间设置为原来的两倍，避免触发大量重传，导致网络情况进一步恶化。

TCP 还有快速重传机制，也即当发送方接收到对同一个数据包三个冗余的 ACK（共四个 ACK）时，说明这个 ACK 对应的数据包之后的那个数据包已经丢失。此时发送方会立即重传，不需要等待超时。

4.4、TCP 流量控制

在接收方有一个缓冲区，上层应用从缓冲区中读取数据，发送方发送的数据最终暂存在缓冲区中。如果网络层传送数据的速率比应用层读取数据的速率更快，则缓冲区会溢出，造成数据丢失。

为了控制发送速率，接收方在响应报文的接收窗口字段（receive window, rwnd）中会告知接受缓冲区的剩余空间。发送方发送的报文长度不应该超过 rwnd 指明的值。

接收缓冲区（RcvBuffer）的大小一般是固定的，通常默认的长度是 4096 字节。现在操作系统会根据情况自动调整接收缓冲区的大小，也可以通过套接字的选项来设置。

4.5、TCP 连接管理

在交换数据之前，发送方和接收方需要先“握手”建立连接。“握手”的目的是双方知道彼此之间要建立连接，同时确认一些连接参数。

首先考虑以下最简单的两次握手，也即发送方发送连接请求，然后接收方同意建立连接。

这种方法并不总是有效的，因为握手的报文也可能丢失、乱序，且会受到延迟影响。例如可能出现下面这种情况：

alt text

连接请求由于超时，发送方重新发送了一次。但上一个连接已经正常关闭了，服务器正常对这个重传的连接请求发送响应，但是发送方认为连接已完成，不会再建立起连接。这就变成了一个半打开的虚假连接。

由于服务器同意建立连接，会分配一定资源。这样的半打开连接就造成了资源的浪费。

进一步地：

alt text

如果连接请求和数据都重传了，两次握手的情况下服务器就会误以为这是正常的另一个连接请求和对应的数据，相当于接受了重复的数据，同样是造成资源的浪费。

所以 TCP 采用的是三次握手：

第一次握手：客户端向服务器发送连接请求，报文中标志位 SYN=1，同时指定初始序号 Seq=x
第二次握手：服务器进行响应，确认收到了连接请求。响应报文中标志位 SYN=1，ACK=1，同时指定自己的初始序号 Seq=y，并指明下一个希望收到的报文序号 ACKnum=x+1
第三次握手：客户端进行响应，响应服务器的报文，标志位 ACK=1，并指明希望从服务器接收到的下一个报文的序号 ACKnum=y+1

三次握手的情况下，之前提到的半连接的情况即可以被避免。同时，由于初始序号的存在，也不会出现误认连接导致数据重复的问题。

关闭连接，两方任意一方发送标志位 FIN=1 的报文即可主动关闭连接。关闭连接是四次挥手：

客户端发送 FIN=1, Seq=x 的报文
服务器接进行响应 ACK=1, ACKnum=x+1。
服务器再发送 FIN=1, Seq=y 的报文给客户端
客户端进行响应 ACK=1, ACKnum-y+1.

等待一段时间后，资源全部释放，连接正式关闭。

4.6、拥塞控制原理

拥塞控制简单来说是太多的源发送了太多数据包，使网络来不及处理，表现出来就是网络时延变长且丢包。流量控制只是单纯接收方处理不过来。

第一种拥塞的情况：

alt text

假设路由器的缓冲区大小是无限的。一开始，随着 $\lambda_{\text{in}}$ 上升， $\lambda_{\text{out}}$ 也上升。当两个主机的发送速率逐渐接近 $R/2$ 时，链路中流量强度接近 1，时延趋近于无穷大， $\lambda_{\text{out}}$ 不再上升。

第二种拥塞的情况：

alt text

路由器缓冲区是有限的。则随着 $\lambda_{\text{in}}$ 提升，缓冲区会溢出，出现丢包的情况，需要重传，则有 $\lambda_{\text{in}}'\geqslant \lambda_{\text{in}}$ 。

随着 $\lambda_{\text{in}}'$ 上升，一开始 $\lambda_{\text{out}}$ 同步上升，后来 $\lambda_{\text{out}}$ 上升速率下降。因为随着丢包情况变多，需要发更多的包，才能达到相同的输出速率。

真实情况中，时延逐渐变长，一些包就算没有丢失，也会滞留在网络中，导致进一步触发重传。而这些重传完全是不必要的，于是又浪费了一部分性能。

第三种拥塞的情况：

alt text

考虑主机 A 到主机 C 的红色线路。当主机 A 的 $\lambda_{\text{in}}'$ 增加时，主机 D 到主机 B 蓝色线路在 R1 上的分组会被主机 A 的分组完全淹没。则主机 D 到 R4 这一段的传输完全是无用功（后面完全被丢弃了，根本传不过去）。

根据以上三种情况，可以发现随着传输速率的增加，时延会逐步提高，进而导致丢包和重传。不必要的重传又会导致情况继续恶化。上游传输能力也可能因为下游的丢包而被完全浪费。所以出现拥塞时，如果不加以控制，整个网络情况会加速恶化。

拥塞控制方法可分为端到端的拥塞控制以及网络辅助的拥塞控制。

端到端的拥塞控制就是根据观察到的实验和丢包现象推断出拥塞。例如触发快速重传时，说明有丢包，可能此时网络状况不佳。这就是 TCP 采用的方法。

网络辅助的拥塞控制，是由路由器向发送主机或者接受主机直接进行反馈，通过设置字段等方式显式地指明拥塞程度或者设置发射速率。

例如 IP 首部 TOS 字段中的 ECN（Explicit Congestion Notification，明确拥塞通告）标志位。处于拥塞中的路由器对经过自己的包设置 ECN，等到目的主机接受到这个包之后再通知源主机即可。配合使用 TCP 首部中的 ECE、CWR 标志位也可以。

还有 ATM 的 ABR 协议，DECbit 协议等都是用于拥塞控制。

4.7、TCP 拥塞控制

TCP 拥塞控制使用的方法是AIMD（Additive-Increase, Multiplicative-Decrease，加性增乘性减）

维护一个 cwnd（congestion window，拥塞窗口），其值代表一个 RTT 内能允许发送多少数据到网络中。cwnd 是随拥塞状态动态变化的，初始值为一个 MSS。记 TCP 发送速率为 $\text{cwnd}/\text{RTT}$

一开始是慢启动（Slow Start，SS）状态，每接受到一个 ACK，cwnd 就翻倍。这样，发送速率指数级增加，直到发生丢包事件或到达慢启动阈值（ssthresh, slow start thershold）。

cwnd 到达慢启动阈值后，进入拥塞避免（Congestion Avoidance, CA）状态，一个 RTT 如果没有发生快速重传或者超时丢包，cwnd 加一（而不是翻倍）。

发生超时丢包后，说明网络拥塞。先将 ssthresh 设置为当前 cwnd 的一半，然后将 cwnd 置为 1，回到慢启动状态。

以上是TCP Tahoe 算法，是最早的 TCP 拥塞控制算法之一。

TCP Reno 算法在此基础上进行了改进，引入了快速恢复机制。

触发快速重传之后，进入快速恢复状态，然后先将 ssthresh 降为当前 cwnd 的一半，cwnd 变为 ssthresh+3（而不是像之前一样直接变为 1）。

等到收到不同的 ACK（也即出发快速重传的那个包被收到了），cwnd 变为 ssthresh，重新进入拥塞避免状态。

慢启动持续的很短，在较长的时间跨度下可以忽略不计。于是在拥塞控制下，cwnd 大小就呈下图中的锯齿状：

alt text

Linux 中默认的 TCP 拥塞控制算法是 TCP Cubic。

记 $w_{\max}$ 是检测到拥塞丢包时的发送速率。发生丢包后，cwnd 减半，希望快速爬升到 $w_{\max}$ 附近，然后再以较慢的速率接近 $w_{max}$ ，利用三次函数来实现，效果如下：

alt text

还有基于延迟的 TCP 拥塞控制。如TCP BBR（Bottleneck Bandwidth and Round-trop propagation time），其目标是让链路尽可能满的同时保持低延迟（不爆满），刚好足够。

TCP BBR 不断测量当前的发送速率（上个 RTT 内发送的字节数除以测量到的 RTT），如果其接近非拥塞时的发送速率，就线性增加 cwnd；如果远低于非拥塞时的发送速率，就线性减少 RTT。

4.8、TCP 的公平性

如果 K 个 TCP 会话共享带宽为 R 的瓶颈链路，则最终每个会话会得到 $R/K$ 的平均链路速率，这就是 TCP 的公平性。

考虑两个会话的情况，假设一开始是不公平的。两个会话都进入拥塞避免状态，cwnd 逐渐加一，当超过最大带宽时发生丢包，此时两者 cwnd 同时除以 2。如此反复，最终会接近均分带宽的情况。

alt text

所以在都使用 TCP，RTT 相同，拥塞避免有固定数量的会话个数时，TCP 是公平的。

由于 UDP 没有拥塞控制，以恒定速率发送且能容忍报文丢失，使用 UDP 的会话流量会压制 TCP 的会话。

第四章网络层：数据平面

1、概述

网络层主要是在发送主机和接受主机对之间传送分组。发送端将段封装为数据报，然后进行传输；接收端对数据报解封装，然后将得到的段上交给传输层实体。

网络层的两个最重要的功能：路由和转发。

路由是一个“全局”的功能，指使用路由算法决定分组从发送主机到接收主机的路径；转发是一个“局部”的功能，指决定路由器内分组从输入端口转发到合适的输出端口。

网络层可以分为数据平面和控制平面，分别对应着上面的转发功能和路由功能。

数据平面是“本地”的，决定路由器内的数据怎么转发；控制平面是“网络”范围内的，决定数据报从源主机到目标主机之间端到端的路径。

两个平面都有两种方式：传统方式和SDN（Software-Defined Networking，软件定义网络）方式。

转发的传统方式是基于目标地址（IP）+转发表的；转发的 SDN 方式是基于多个字段和流表的。

路由的传统方式是在路由器中实现的；路由的 SDN 方式是在远程服务器中实现的。

传统方式下，每一个路由器都有自己单独的路由器算法元件，根据路由器算法决定端到端路径后，数据平面上 IP 协议再根据转发表决定局部的转发。传统方式下，各个路由器的控制平面是“分离的”，如果想要更改控制平面的逻辑，只能一个个路由器改，比较僵化。

SDN 方式下，有一个统一中心化的控制器（通常是远程的）与各个路由器的本地控制代理（Control Agent，CA）进行交互。路由器可以通过南向接口与中心控制器交互，根据流表匹配多个字段，然后进行相应动作。SDN 方式下的控制平面是“集中的”，只需在中心控制器上进行操作就可以控制所有路由器的逻辑。

网络层向上层提供的服务模型可以这样描述：

对于单个数据报的服务：是否能保证可靠传送、是否能提供延迟的保证（不高于某个时间）
对于数据报流的服务：是否能保证数据报按序传送，是否能保证流的最小带宽（不低于某个值），能否保证分组之间的延迟差（每个分组在网络中延迟的差）
连接建立：传输层中的连接（例如 TCP 是面向连接的）通常只反映在端系统之间，两个主机要维护连接状态；网络层的连接还涉及到路径上的路由器。服务是否保证路径上的路由器也维护连接状态。ATM 就是保证网络层连接的网络，而 IP 就不是。

Internet 是一个尽力而为的服务模型，不保证带宽、延迟、按序到达。

2、路由器的结构

一个高度简化的路由器结构图如下所示：

控制平面的路由器处理芯片计算出路由表，下发到输入端口的网络层处理部分。然后根据路由表，决定数据报通过高速交换结构转发到哪个输出端口。

输入端口中

绿色框代表物理层部分，是 Bit 级的接收
蓝色框是数据链路层部分，代表链路层协议的动作，如判断帧头帧尾，解封装取出数据
红色框代表网络层部分，根据数据报头部的信息以及路由表，然后进行转发。

当中间交换机构的交换速率小于输入端口的汇聚速率时，数据报在输入端口可能要排队，就会出现头端阻塞，也即队头的数据报阻止了队列的其他数据报向前移动，所以一般还会设置输入缓冲区。

定义交换速率为单位时间从输入到输出的速率。假如有 N 个输入端口，交换结构的交换速率应该是单个输入线路速率的 N 倍以上，交换结构才不会成为瓶颈。

三种典型的交换结构如下图所示：

通过内存交换，是第一代路由器。采用传统的计算机结构，是在 CPU 直接控制下的交换。分组从输入端口通过总线拷贝到内存，CPU 处理分组，然后通过总线传到制定的输出端口。转发速率被内存的带宽限制（数据包要通过总线两次），且一次只能转发一个分组。

通过总线交换。数据报通过共享总线，从输入端口到达输出端口，只要通过总线一次。交换速率受限于总线带宽，一次处理一个分组。
通过互联网络交换，可以并发转发多个分组，克服了总线带宽的限制。需要转发时，就短接输入端口和输出端口之间的总线（例如下图中就短接了 A 和 Y 间的总线）。互联网络有榕树（Banyan）网络以及纵横（Crossbar）网络等。

输出端口与输入端口是反着来的：

由于交换结构的速率大于单个输出端口的速率，所以输出端口也有缓冲区和排队机制，缓冲区满会丢弃数据报。输出端口还会根据调度策略，选择排队中的数据报进行传输。

调度策略有：

FIFO：先到先出。队满后还有丢弃策略还包括随机丢弃，优先级丢弃和尾丢弃
优先权：先发高优先级的，高优先级发完后发低优先级的。优先级依赖于带的标记，或者数据报中的字段。
RR：循环扫描不同类型的队列。发完一个类别的分组，再发下一个类别的分组。
WFR：也即 Weighted Fair Queuing，是一般化的 RR。每种类型得到的服务时间与权重呈正比。

3、IP 协议

网络层的协议有路由协议（包括路径选择协议，RIP，OSPF，BGP），IP 协议，以及 ICMP 协议（也称为信令协议，与测试网络通断等紧密相关）

3.1、IP 数据报的格式

也分为首部和数据部分。

首部一般为 20 字节，如果有可选项，可能更长。首部的具体结构如下：

IP 协议版本号：占 4bit，现在有 IPv4 和 IPv6
首部长度：占 4bit，以四字节为一单位的，最小为 5（也即代表首部 20 字节）
服务类型：占 8bit，区分不同类型的服务，用于确定优先级等，现在已不常使用
数据报总长：占 16bit，以 1 字节为一单位，表示整个数据报的总长度
标识：占 16bit，用于标识数据报，同一个大数据报分片得到的小数据报们拥有同一个标识
标志位：占 3bit，用于控制和表示数据报是否分片。这三位分别是 DF（Don’t Fragment，不分片），MF（More Fragments，更多分片），MBZ（保留位）。DF=1 时，表示不允许对该数据报进行分片。MF=1 时表示这是某个数据报的一个分片，后面还有其他分片，最后一个分片会设 MF=0。
片偏移量：占 13bit，以 8 字节为一单位，表示该分片数据包的数据首字节在整个大数据报中的偏移量
TTL：占 8bit，生存时间，每经过一个路由器 TTL 值减一
上层协议：占 8bit，用于告知数据部分应该交给上面的那个传输层协议处理（TCP、UDP 还是其他）
校验和：占 16bit
源 IP 地址：占 32bit
目标 IP 地址：占 32bit
可选项：例如经过路由器的时候，路由器可能将自己的信息添加到这一部分。不过一般都没有可选项。

接下来就是数据部分。

3.2、IP 数据报分片

链路层的最大传输单元（MTU）是 1500 字节，也即链路层上的每个帧最多能携带 1500 字节的数据。所以如果 IP 数据报的长度大于 1500 字节，就要进行分片。

一个 IP 数据报，除了 20 字节的 IP 头部，剩下的都是数据（包括 TCP 首部，这里也被视为数据了）。将数据划分成小片，然后都带上一个 IP 头部。注意，由于片偏移量是以 8 字节为一单位的，所以小数据片的字节数都是 8 的倍数。这样就把原来的大 IP 数据报分为若干个小 IP 数据报了，到达目标主机后才重组起来。

通过 IP 头部中的字段来标识这些小数据报。这些小数据报拥有相同的“标识”，不同的”片偏移量“。对于“标志位”，除了最后一片，其他片的标志位都设为 1（DF=0，MF=1），表示后面还有更多的分片；最后一片的标志位设为 0（DF=0，MF=0），表示后面没有分片了，自己就是最后一个分片。

一个具体的例子：

3.3、IP 地址

IP 地址是一个 32 位的二进制数，用于标识一个主机的接口或一个路由器的接口。

接口是指主机或者路由器和物理链路的连接处。主机和路由器都可以有多个接口，每一个接口都有一个 IP 地址与其相关联。

IP 地址可以划分为两个部分，高位部分称为网络部分，标识不同的网络；低位称为主机部分，标识同一个网络下的不同主机。

一个子网内部节点的 IP 地址，其网络部分相同；且子网内的各主机通信无需路由器接入，在物理上可以相互直接到达。

子网掩码是连续若干个 1 后接连续若干个 0 的 32 位二进制数，其与 IP 地址相与就能提取出 IP 地址的网络部分。也可以用 1 的个数来简化表示。

例如子网掩码 11111111_11111111_11111110_00000000 可以简记为 23，这个子网中主机的 IP 就可以写为 200.23.16.0/23

路由的时候是以子网为单位的，从一个子网路由到另一个子网。子网内到达某个主机最后是由交换机通过一跳完成的。

有类地址，一开始将 IP 地址划分为了 A、B、C、D、E 五类。

A 类地址，第一个字节是网络地址，后三个字节是主机地址，且网络地址的最高位为 0。

首八位全为 0 的地址（0.0.0.0~0.255.255.255）是保留地址，不分配，用于特定的网络配置或者初始化过程。特别地，其中 0.0.0.0 标识未知网络，一般用作默认路由。

首八位全为 1 的地址（127.0.0.0~127.255.255.255）也是保留地址，称之为回环地址，用于环路反馈等测试。特别地，其中 127.0.0.1 一般代表本机地址。

去掉保留地址后，A 类地址的范围包括 1.0.0.0~126.255.255.255

可见 A 类地址中不同的网络数少，但是每个网络中可以有大量主机。所以 A 类地址常用于大型网络。
B 类地址，前两个字节用于网络地址，后两个字节用于主机地址，且网络地址的首两位为 10。

B 类地址的范围是 128.0.0.0~191.255.255.255，常用于中型网络。
C 类地址，前三个字节用于网络地址，最后一个字节用于主机地址，且网络地址的首三位为 110。

C 类地址的范围是 192.0.0.0~223.255.255.255，常用于小型网络。
D 类地址首四位为 1110。

D 类地址的范围是 224.0.0.0~239.255.255.255，用于多播通信。
E 类地址的首五位为 1110

E 类地址的范围是 2400.0.0~255.255.255.255，保留用于未来或者实验用途。

还有一些特殊的地址：

主机部分全为 0：就是这个网络的网络地址（即与子网掩码相与后的结果）
主机部分全为 1：表示该子网的广播地址。与这个地址通信相当于向该子网内所有主机通信。

进一步，ABC 三类地址中还可以划分出私有地址，仅供局域网内使用，不会用于公网标识设备。

A 类私有地址：10.0.0.0~10.255.255.255
B 类私有地址：172.16.0.0~172.31.255.255
C 类私有地址：192.168.0.0~192.168.255.255

其他的则是公网地址，用于唯一标识整个互联网中的设备，可以在全球范围内被路由。

有类网络中，网络地址只能是一字节、两字节或者三字节，一个网络内的地址用不完就会浪费。

于是后来出现了CIDR（Classless InterDomain Routing，无类域间路由），也即网络部分可以是任意的位数，不局限于 8、16 或 24 位，更加自由。

地址格式一般为a.b.c.d/x，其中 x 就是子网掩码中 1 的位数，也叫子网前缀长度。

基于目的地的转发采用最长前缀匹配原则。路由器收到数据包后，从中提取出目的地 IP，然后在路由表中查询。

路由表的条目一般包含以下表项：目标子网号，子网掩码，出接口

拿到目标 IP 后，对于路由表中的某个条目，与子网掩码相与，如果结果与目标子网号相同，就说明匹配上了，转发到这个条目里指明的那个出接口。

至于最长前缀匹配，目前使用的都是 TCAM（Tenary Content Address Memory，三态内容可寻址存储器），可以在常数时间内查找所有条目，找到匹配最长前缀的那个。

3.4、主机如何获得地址——DHCP

一个子网内的主机如何获取自己的 IP 地址有两种方式：

手动配置/硬编码：在 Windows 下，可以打开设置，自己手动配置 IP 地址、默认网关、子网掩码、本地 DNS；Linux 下，硬编码在配置文件/etc/rc.config文件中，也可以通过指令更改
动态获取：根据DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）从服务器动态地获取地址。DHCP 是基于 UDP 的。

DHCP 的功能：

允许第一次加入网络时，动态地获取一个 IP 地址
更新获取到的 IP 地址的租用期（renew）
重启时，继续使用以前用过的 IP 地址（reuse）
支持短期在网的移动用户加入/离开网络

DHCP 服务器一般部署在路由器中，为路由器连接的所有子网提供服务。一个主机通过 DHCP 获取 IP 地址的大致过程如下：

DHCP discover：主机通过广播地址，在子网内查询是否有 DHCP 服务器在线
DHCP offer：某个 DHCP 服务器向该主机响应，返回可用的 IP 地址
DHCP request：主机正式向该 DHCP 服务器请求，使用这个 IP 地址
DHCP ack：DHCP 服务器同意请求。

DHCP 请求封装在 UDP 段中，然后封装到 IP 数据报中，最后封装在以太网的帧中。以太网的帧在局域网范围内光爆，被 DHCP 服务器接收到。然后逐步解封装，得到 DHCP 请求。

DHCP 服务器生成 DHCP ACK 响应，包含主机的 IP 地址（以及子网掩码）、第一条路由器的 IP 地址（也即网关，是该子网的出口）以及 DNS 服务器的 IP 地址。然后经过相同的封装解封装过程，最后到达主机。

3.5、网络如何获得地址——层次编址

上一小节讲到主机如何获取 IP 地址，或者说如何知道自己的主机地址（IP 地址的主机部分）。那一个子网本身的网络地址是如何获得呢？

例如一个 ISP 拥有地址块 200.23.16.0/20，从主机部分划出三位来，也作为网络部分，就可以进一步划分成 $2^3=8$ 个地址块，给下面的机构使用，例如 200.23.16.0/23.

同理，机构也可以继续划分出更小的子网。这样一层一层的划分下来方式就是层次编址。

最顶层的 ISP 的地址块是由 ICANN（Internet Corporation for Assigned Names and Numbers）机构管理划分的。

由于网络地址是层次编码的，所以可以做路由聚集。例如某个 ISP 下的机构的地址为 200.23.16.0/23、200.23.18.0/23、200.23.20.0/23，这个 ISP 就可以对上层 ISP 发路由通告：只要目的地是 200.23.16.0/20 的包就可以发到我这边来。这样做路由聚集，可以减少路由表中的条目，加快匹配。

同时，如果某一个机构转移到另一个子网下，例如 200.23.30.0/23 挂靠在了 199.31.0.0/16 的 ISP 下。由于无法进行路由聚集，这个 ISP 会如实告知上级 ISP：200.23.30.0/23 的数据包往我这边走。由于采取最长前缀匹配原则，虽然 200.23.30.0/23 也能匹配 200.23.16.0/20，但仍然会往正确的方向走。

3.6、NAT

Network Address Translation，网络地址转换技术。指同一个局域网内的所有设备，通过地址转换，只通过同一个公网 IP 地址与外面通信。例如下图中，10.0.0.1、10.0.0.2、10.0.0.3 这三台主机最终都通过 138.76.29.7 这个 IP 地址与外界通信。

NAT 技术的优点：

不在需要从 ISP 获取一块地址，只要一个 IP 地址就可以支持所有的局域网设备的通信需求
只要那个公共 IP 地址不变，局域网内设备的地址可以随意改变，而无需通知外界
可以改变 ISP 地址，而无需改变内部的地址设置
内网地址对外是不可见的，外界无法探知内网结构，更安全

要实现 NAT，路由器要做以下工作：

对外出的数据包，将源 IP 和源端口号替换为 NAT IP 和新的端口号，例如将 10.0.0.1:3345 替换为 138.76.29.7:5001。此后，外界只知道是 138.76.29.7 发来了一个包。
维护一张 NAT 转换表，记住源 IP、源端口号、NAT IP、新端口号的转换关系。
对于进入的数据包，查找 NAT 转换表，将目的 IP 和端口号，转换为内网中机器的 IP 和相应的端口号。如果没找到，就会拦截下来。

对于启用了 NAT 的一台内网主机，如果外界想要主动访问这台内网主机，是会被拦截的。因为 NAT 转换表中没有相应的条目。如何在启用 NAT 的情况下，从外界访问内网主机，就是 NAT 穿透问题。

第一种方案是静态配置 NAT，也即主动给 NAT 添加一个条目，对 NAT IP 特定端口的访问，转发到内网主机上。例如，对 138.76.29.7:80 的访问，允许转发到 10.0.0.1:80 上来。

第二种方案 UPnP IGD（Universal Plug and Play Internet Gateway Device）协议。这个协议可以增删 NAT 转换表上的端口映射。通过这个协议，就可以自动化静态 NAT 端口映射的配置过程。

第三种方案是采用中继服务器。外面不能直接访问，就先由内网机器主动访问一个中继服务器，然后外部也与这个服务器相连。这样双方就可以通过这个中继服务器相互通信了。

NAT 技术有许多争议：

理论上 NAT 是网络层的技术，应该最高只能处理网络层的东西（IP 地址），实际上它还修改了传输层的端口
违反了端到端原则，网络层应该进行的是主机寻址，但是 NAT 进行了端口处理，进行了端口寻址
NAT 穿透可能带来安全问题

3.7、IPv6

IPv6 出现的初始动机是 IPv4 的 32 位地址空间即将耗尽。除此之外，IPv4 中，IP 头部有 TTL 字段，每经过一个路由器都会发生变化，相应校验和也会发生变化，需要路由器重新计算，加重了负担。分片机制也有相同的问题。

IPv6 的首部为 40 字节，结构如下：

版本：占 4bit
优先权：占 8bit，用于确定流中数据报的优先权
流标签：占 20bit，用于识别相同的流中的数据报，从而实现流控制（QoS）
有效载荷长度：占 16bit，出了首部意外的字节数，包括拓展首部和数据部分
下一个首部：占 8bit，与 IPv4 中的“上层协议”字段类似。指出处理该数据报的下一个实体类型，例如 TCP、UDP 等。如果有拓展首部（也即 IPv4 中首部的可选项），这个字段的值就指出拓展首部的类型。
跳数限制：占 8bit，与 IPv4 的 TTL 字段类似
源 IP：占 128bit
目标 IP：占 12bit

接下来是数据部分

与 IPv4 相比，IPv6 首部没有校验和，也没有分片相关的字段和标志位，可选首部改为由“下一个首部”字段指定。

由于不允许分片，如果当前数据长度超过 MTU，会直接丢弃，并返回一个 ICMPv6 报文：Packet Too Big。这样，分片的负担就转移给了发送方，减轻了路由器的负担。

目前，IPv6 还没有普及。IPv6 网络内部和 IPv4 网络内部互相通信都没有问题。如果一个 IPv6 网络要向另一个 IPv6 通信，要经过 IPv4 的网络。可以通过建立隧道来解决。

IPv6 报文再封装上 IPv4 的首部，就可以通过 IPv4 网络进行传输了，到达目的地之后再解封装。

4、通用转发和 SDN

传统转发方式是匹配 IP 地址，然后转发到某个端口。事实上，包括转发、防火墙在内的许多网络应用都可以抽象为匹配+动作的方式。

SDN 方式将控制平面和数据平面分离。SDN 控制器（或者说网络操作系统）上通过北向 API 与网络控制应用交互，计算出流表；下通过南向接口将计算出的流表交给数据平面。然后数据平面根据流表进行匹配，再实施响应的动作。

网络是可编程的，只需要修改流表的生成方式，就能轻松控制网络。

流表的结构如图所示：

先根据包括目标 IP 在内的多个字段匹配，然后执行匹配表项中的动作。匹配+动作的方式抽象统一了不同的设备：

路由器：匹配目的 IP 的最长前缀，动作是转发到某一输出端口
防火墙：匹配 IP 地址或者端口号，动作是允许通过或者阻塞掉
交换机：匹配目的 MAC 地址，动作时转发或者泛洪
NAT：匹配 IP 地址和端口号，动作是修改地址和端口号·

第五章网络层——控制平面

前面已经提到，控制平面对应着路由，就是按照某种指标找到一条从源节点到目标节点的较好路径。

需要再次强调的是，路由是子网与子网之间的路由，也等价于路由器和路由器之间的路由。只要到达了这个路由器，也就到达了这个子网，也就可以到达子网中的任意一台主机。

1、路由选择算法

路由选择算法是网络层软件的一部分，可以计算出路由表。

路由选择算法按照知晓全局还是局部信息，可以分为集中式的和分布式的。

如果所有路由器都具有完整的拓扑和链路开销信息，这就是集中式的，例如链路状态算法（Link State Algorithm）；如果路由器初始只知道与邻居之间的链路开销，通过不断与邻居交换信息，迭代地进行计算，这就是分布式的，例如距离向量算法（Distance Vector Algorithm）。

路由选择算法还可以按照更新速度，分为静态的和动态的。

如果路由随时间变化缓慢，通常由人工进行调整，就是静态的；如果路由变化很快，周期性更新或响应链路开销的变化，就是动态的。

1.1、链路状态算法

链路状态算法大致可分为两步，首先是各个路由器通过各种渠道获得整个网络的拓扑、链路代价等信息，然后计算出本点到其他点的最优路径，得到路由表。

第一步获取网络拓扑的大致流程如下：

某个路由器向自己所有的线路发送分组，其他路由器收到分组后进行回应，并告知自己的信息。这样该路由器就知道了自己有哪些邻居。
测量到相邻节点的代价
组装一个分组，描述自己以及到邻居节点的代价。分组包括发送者名称、序号、年龄（Age 字段，与 TTL 类似，防止无限泛洪）、邻居列表（包括邻居的名字以及到邻居的代价）
将分组广播到其他所有路由器

第二步找最优路径，利用的是 Dijkstra 算法：

将所有节点分为临时节点和永久节点。一开始，所有节点都是临时节点。将源节点的节点代价 $D$ 设为 0，其余节点的节点代价为 $\infin$
从临时节点中，挑选出节点代价最小的节点 $w$ 。更新所有与节点 $w$ 相邻的临时节点 $v$ 的节点代价，更新规则如下：

$D(v)=\min\{D(w)+c(w, v), D(v)\}$
将节点 $w$ 变为永久节点。若临时节点集为空，算法结束；否则回到第二步。

采用堆的 Dijkstra 的时间复杂度为 $O(n\log n)$

采用链路状态算法时可能出现路由选择的振荡。当以链路承载流量作为链路开销时，如果出现拥塞，路由选择就会反复变化，出现振荡。

可以强制链路开销不依赖与承载的流量，或者确保所有路由器不同时运行链路状态算法，也即让发布路由通告的时间错开、随机化，来解决路由选择振荡的问题。

1.2、距离矢量算法

距离矢量算法是动态、分布式的路由选择算法。

其核心思想是，每个路由器都维护一个距离矢量，这个距离矢量包含代表到其他节点的代价。等待到邻居的链路代价变化或者从邻居传来新的距离矢量；然后重新计算到各个目标节点代价，得到新的距离矢量；如果目标的距离矢量发生变化，通告邻居，然后继续等待。

Bellman-Ford 方程：

$D_{x\rightarrow y}=\min_v\{c(x, v)+D_{v\rightarrow y}\}$

其中节点 $v$ 是节点 $x$ 的邻居。

距离矢量算法计算出的路由表，每个条目包含：

目标节点
到达目标节点的下一跳节点
到达目标节点的代价

距离矢量算法的特点是好消息传得快，坏消息传得慢。所谓好消息是指有新的路由器加入等原因导致某段链路代价降低；坏消息是指路由器下线等导致某段链路不可达。

考虑拓扑 $A\leftrightarrow B\leftrightarrow C\leftrightarrow D$ ，两个节点之间的代价均为 1。收敛后，B、C、D 到 A 的代价应该分别为 1、2、3

假如 A, B 之间的链路断开，下一个周期内，B 通过测量邻居，认识到 A 不可达了。但是 C 的距离矢量告诉它，C 到 A 的代价是 2，于是 B 认为自己可以以 $1+2=3$ 的代价到 A。B 距离矢量更新后，C 认为自己可以以 $3+1=4$ 的代价到 A。

依次类推，这样的计算要经过很多次，直到设定的阈值（认为是不可达的代价值）时，剩下的节点才会意识到 A 已经是不可达的了。这就是无穷计算问题。

可以通过水平分裂算法来缓解这个问题。仍然利用上面的例子，不同的是，由于C 要到 A 的下一跳就是 B，所以它就不越俎代庖，而是告诉 B 自己到达不了 A，反正 B 节点肯定知道自己能不能到 A。这样，几次运算，A 不可达的消息就都知道了。

或者可以这样理解。路由器向外发布某网段的路由信息之后，不再接受从反方向发布回来的同一网段的路由更新信息。

在上面的例子中，B 直到 A 不可达了，并告知 C。B 就不会再接受从 C 反方向来的“可以用代价 2 到 A”的更新信息。

然而，水平分裂算法会在某些拓扑形式下失效，不是万能的。

1.3、两种算法的比较

在消息复杂度上，或者说节点之间需要传递的消息数量上：链路状态算法需要泛洪，而距离矢量算法只要和邻居之间传递消息。所以距离矢量算法的消息复杂度更低。

在收敛时间上：链路状态算法一般都能很快收敛（除了震荡外），而距离矢量算法是迭代式的，需要经过多轮计算才能收敛，而且可能存在路由环路、无限计算问题。所以链路状态算法的收敛时间更短。

在健壮性上：假如某个路由器故障，提供的信息都是错误的。对于链路状态算法来说，每个节点计算自己的路由表，错误路由器影响较小，是局部的；而对于距离矢量算法来说，坏消息会传遍整个网络，影响较大。所以链路选择算法的健壮性更好。

2、路由选择协议

在讨论路由选择算法时，我们考虑的是理想化的情况：路由器数量很少，网络内所有路由器地位一样，在一个平面内就能解决问题。然而实际上，网络的规模是巨大的，不管是链路状态选择算法和距离矢量算法在这种规模下都是十分困难的。同时不同网络的管理者希望按照自己的方式管理网络，同时希望对外隐藏自己网络的细节。

这就引入了层次路由的概念。现实中，路由器被组织进一个个自治系统（Autonomous System，AS），或称为域。每个 AS 由全局唯一的 ASN 标识（ASN 即 AS 号，由 ICANN 区域注册机构分配）。

同一个 AS 内的所有路由器必须运行相同的自治系统内部路由选择协议（域内路由选择协议），不同 AS 中的路由器可以运行不同的域内路由选择协议。

网关路由器是位于 AS 边缘的路由器，直接连接到另一个 AS 中的一台或者多台路由器。网关路由器运行域间路由选择协议以及域内路由选择协议。

域内路由选择协议确定目的地为 AS 内部的路由表条目，域内和域间路由选择协议共同确定目的地为 AS 外部的路由表条目。

2.1、内部网关协议——IGP

Interior Gateway Protocol，也即域内路由选择协议，包括 RIP、EIGRP、OSPF、IS-IS 等。

RIP，路由信息协议，是基于距离矢量算法，每 30 秒交换一次距离矢量，已经不再广泛使用了。

EIGRP，增强的内部网关路由协议，也是基于距离矢量算法的。

IS-IS，与 OSPF 基本相同。

OSPF（Open Shortest Path First），开放最短路优先路由选择协议，世基于链路状态算法的。

链路开销由网络管理员配置，可以是带宽、延迟等。

每台路由器会向自治系统内的所有路由器广播路由选择信息。当链路状态发生变化时，就会广播；链路状态未发生变化，至少每隔三十分钟，也会广播一次。

链路状态通告包含在 OSPF 报文中，由 IP 承载，其 IP 首部的上层协议字段为 89。OSPF 协议自己实现可靠报文传输、链路状态广播等功能。

OSPF 还有安全保障，仅有受信任的路由器能参与一个 AS 内的 OSPF 协议，防止恶意入侵。

OSPF 还可以支持层次结构。一个自治系统内可以配置两级的层次结构——区域和主干区域。

链路状态通告仅在本区域内核主干区域中泛洪，每个节点都有其本地区域的详细拓扑，只知道到达其他目的地的方向。

2.2、外部网关协议——EGP

External Gateway Protocol，也即域间路由选择协议。不同的 AS 可以采用不同的 IGP，但是必须使用相同的 EGP。互联网事实上的 EGP 是BGP（Border Gateway Protocol，边界网关协议），这是一种基于策略的路由选择协议。

BGP 为每个自治系统每个路由器提供了完成以下任务的手段：

从邻居 AS 获得前缀（子网）的可达性信息
- 每个前缀标识一个子网或者一个子网的集合
- 外部 BGP 连接（eBGP）从邻居 AS 获得前缀的可达性信息
- 内部 BGP 连接（iBGP）向 AS 内部的所有路由器传播前缀的可达性信息
确定到某前缀的最好的路由
- 一台路由器运行一个 BGP 路由选择过程
- 根据策略和可达性信息确定到该前缀的最好的路由

两个 BGP 路由器通过使用 179 端口的半永久 TCP 连接来交换 BGP 报文。报文通告了去往不同前缀的路径，BGP 是基于改进的路径矢量算法，除了代价之外，还告知了到达目的地的完整路径，从而避免环路的发生。

BGP 报文的类型：

OPEN: 打开与远程 BGP 对等体的 TCP 连接、并验证 BGP 发送方；包括 BGP 版本号、自己所属的 AS 号、路由器 ID、 Hold Time 值、认证信息等
UPDATE: 通告新路由（或撤消旧路由）
KEEPALIVE: 在没有更新报文的情况下保持连接状态；确认 OPEN 请求； 19 字节，只有首部，包括标记、长度、类型等，没有数据
NOTIFICATION: 如果发现对方发过来的消息有错误或者主动断开 BGP 链接，就发送该消息，并关闭链接；如收到该消息，也会将链接变为 idle（空闲）状态。
ROUTE-REFRESH: 请求对等体重新发送路由信息

前缀+属性就构成一条路由。其中两个非常重要的属性：

AS-PATH：包含了到达该前缀已经通过的 AS 列表，路由器可以使用该属性来检测和防止循环通告。如果通告中包含本 AS，路由器就会拒绝这个通告，防止环路。例如 AS3-AS2-AS1，含义是依次经过 AS3、AS2、AS1 可以到达前缀。如果本 AS 是 AS4，添加到 AS-PATH 的最前面。
NEXT-HOP：下一跳地址，是 AS-PATH 起始的路由器接口的 IP 地址。

接受某条路径通告的网关路由器根据入口策略接受或拒绝该路径，也根据策略是否向其他邻居通告该路径。

路由器可能知道到达某个前缀的多条路由，路由器必须在可能的路由中选择最好的一条放到路由表中。路由器会顺序调用以下规则知道留下一条路由：

本地偏好值：由管理员设置策略来决定偏好值的计算方式，保留偏好值最高的那些路由
AS-PATH：保留 AS-PATH 最短的那些路由
NEXT-HOP：保留到 NEXT-HOP 代价最小的那些路由。也即尽可能快地送出本路由，也形象的称为热土豆路由
附加规则：根据 BGP 标识符等来选择路由

2.3、IGP 与 EGP 的比较

AS 之间，策略问题起主导作用，一个给定的 AS 是否能经过某一个 AS 可能非常重要，必须有策略来控制。而 AS 内部，都在相同的管理控制下进行，策略相对不重要。

AS 之间，路由选择是面向策略的，性能是次要的问题。而 AS 之内，更关注性能。

3、OpenFlow

前面已经提到过 SDN 方式。OpenFlow 协议运行在 SDN 控制器和 SDN 控制的交换机或其他实现了 OpenFlow API 的设备之间。

OpenFlow 协议运行在 TCP 之上，使用 6635 的默认端口号。一共有三类 OpenFlow 报文：

Controller-to-Switch：消息由控制器发出，用于管理和获取交换机状态。例如读交换机状态、配置交换机、修改交换机流表表项、让交换机发送某个分组等。
Asynchronous：消息由交换机发出，用于将网络时间和交换机状态变化更新发送到控制器。例如某个分组不能被任何流表表项匹配，上交给控制器处理；端口状态变化通知；通知控制器删除了一个流表项。
symmetric：其他

SDN 的优势：令控制平面更可靠、可拓展，实现了一个安全的分布式系统。可以实现网络流量的负载均衡。可以设置路由偏好，比较灵活。对故障具有鲁棒性。

具体的 SDN 控制器有 ODL（OpenDayLight）控制器，ONOS 控制器等。

4、ICMP

因特网控制报文协议，被主机和路由器用来彼此沟通网络层的信息，包括差错报告、回显请求等。

ICMP 报文也承载于 IP 上。ICMP 报文包括：

类型字段
编码字段
引起该 ICMP 报文首次生成的 IP 数据包的首部和前八个字节，以便发送方能确定引起差错的数据报

5、网络管理

现实生活中，每个自治系统（网络）是由数千个交互的硬件和软件组成。这样一个复杂系统需要监控、配置和控制。这就引出了网络管理的概念：包括了硬件、软件和人类元素的设置、综合和协调，以监视，测试，轮询，配置，分析，评价和控制网络及网元资源，用合理的成本满足实时性、运营性能和服务质量的要求。

一个网络中会有若干个被管设备，每个被管设备对应有一个代理和管理信息库（存储着设备的配置数据、统计信息等）。

网络管理员在管理服务器上操作，通过网络管理协议来管理被管设备。

网络管理的三种方法：

CLI：直接对每个设备发命令或者脚本（例如用 ssh 或者 telnet 进入设备的管理界面，然后直接执行命令）
SNMP/MIB：通过简单网络管理协议（Simple Network Management Protocol）来查询/设置被管理设备数据（Management Information Base）
NETCONF/YANG：这是一种更抽象的、网络范围内的、全面的管理方法，强调对多设备的配置和管理。YANG 是一种数据建模语言，NETCONF 是与远端设备或者在远端设备之间交互兼容 YANG 的动作和数据。

5.1、SNMP/MIP

SNMP 有两种模式来传递网络控制管理和信息报文：

相应有两大类报文：

具体的报文类型如下：

5.2、NETCONF/YANG

NETCONF 是在管理服务器和被管设备之间运行的协议，其功能包括：

操作：检索、设置、激活、增加、修改，删除设备的配置
原子提交操作在多个设备上执行
查询运行数据和统计数据
订阅来自设备的通知

NETCONF 使用远程过程调用（RPC）方式进行通信。NETCONF 协议报文以 XML 编码，通过安全，可靠的传输协议（例如 TLS）进行交换。

实现 NETCONF 协议的建模语言有很多种，目前使用最广的是 YANG 语言。

YANG（Yet Another Next Generation）是数据建模语言，用于规范 NETCONF 网络管理数据的结构、语法、语义。它使用 XML，内置了数据模型。

第六章链路层和局域网

网络层解决了一个子网如何到达另一个子网的路由问题。链路层解决的是一个网络内部，如何由一个节点（主机或者路由器）到达另一个节点的问题。

1、导论

具体而言，链路层包括：数据的检错和纠错、多点接入（共享信道）和点到点连接（独享接入）、链路层寻址、可靠数据传输/流控制、LAN（以太网、WLAN、VLAN）等内容。

一个子网中，节点的连接方式有两种：点到点连接和多点连接。

点到点连接一般用于广域网（WAN）。两个节点通过一条链路连接起来，从这个节点发的包一定是给另一个节点，独享这条链路。不存在寻址、共享信道等问题，所以点到点链路的链路层服务实现比较简单。

点到点链路一般带宽大、距离远（例如跨洋海底电缆），延迟也比较大。拨号上网也属于点到点连接，拨号后，申请一条从家到服务商的链路，不能被其他人共享。

反过来想，如果广域网采用多点连接方式。由于延迟大，距离远，链路布设起来不方便，容易受到地理条件的限制，节点之间发送数据也容易冲突。

多点连接的网络中，所有节点接到共享型介质或者网络交换机上。从一个节点发出的包理论上可以被其他所有节点接收到，所以存在寻址以及信道冲突等问题。多点连接方式的网络，其链路层功能实现起来相对复杂很多。要协调各节点对共享型介质的访问和使用，这就是所谓的多点接入问题。

反过来想，如果局域网很多设备的情况下，采用点到点连接方式。可以想想每两个节点之间都要有一条链路，链路数量是十分庞大的。

在链路层中，主机、路由器、交换机、网桥都称为节点。将节点连接起来的就是链路，包括有形的（网线、光纤、光缆）和无形的（开放空间传递电磁波）。

链路层的 PDU 称为帧，相应的有封装和解封装的过程。

链路层负责从一个节点通过链路将帧中的数据包发送到相邻的节点。同一个帧可能通过不同种类的链路传输，例如先是光纤，然后经过网线，最后通过空气电磁波被移动设备接收。不同链路上有不同的链路协议。

链路层提供的服务：

成帧：将数据包封装在帧中，加上帧头、帧尾。帧头部使用 MAC 地址来标识源和目的地址。如果采用的是共享型介质，还要获得信道访问权以接入信道。
可靠传输：在一个网络的相邻两个节点间完成可靠的数据传递。不是所有的链路层都提供这种服务，在高出错率的链路上，例如无线链路，就要实现可靠数据传输。这种情况下，如果不在链路层做差错控制的工作，到了上层再处理代价会很大。但是在一些低出错率的链路，例如光纤和双绞线上，一般不会实现可靠控制。
流量控制：使得相邻的发送和接收方速度匹配
错误检测：差错由信号衰减和噪声引起。接收方检测出错误后，通知发送方重传。
差错纠正：接收方检查和纠正错误。
半双工和全双工

链路层功能实现在网卡（Network Interface Card，NIC，或者也叫网络适配器）或芯片组上，包括链路层和相应的物理层功能。网卡连接到主机的系统总线上。

发送端控制器取得由高层协议栈生成并存储在内存中的数据包，封装成帧，然后增加差错检测比特、可靠数据传输等，将该帧传进通信链路。

接收端控制器则检查纠错、查看流量控制信息，链路层软件响应控制器的中断，处理差错并提取数据包，传递给上层。

2、差错检测和纠正

数据 D 加上差错检测和纠正位（EDC）后，一起在链路中传输。一般，EDC 越长，可以得到越好的检测和纠正效果。

单 bit 奇偶校验可以检测单个 bit 级的错误。校验位与原数据一起，保证 1 的个数是奇数个或者偶数个。

二维奇偶校验可以检测和纠正单个 bit 级的错误。通过行校验码和列校验码可以定位出错的位置，并纠正过来。

传输层的章节介绍过传输层的校验和如何计算。链路层中用 CRC 校验和（循环冗余校验）。

首先将数据看成二进制比特串 $D$ 。一个比特串可以对应一个多项式，例如 $(1101)_2$ 对应 $x^3+x^2+0x+1$ 。双方约定一个生成多项式 $G$ ， $G$ 的次数为 $r$ 。

则发送方需要生成一个 $r$ 位的 CRC 校验码 $R$ ，使得其拼接在数据尾部后形成的比特串对应的多项式恰好能被 G 整除。接收方如果发现收到的数据和校验码拼接起来能被 $G$ 整除，说明过程中没有出错，通过校验。

这里“整除”中涉及的加减法都是模 2 运算，且都是无进位/借位的，均等价于异或。

下面来看 $R$ 如何生成。要有 $(D<<r)\oplus R=nG$ ，则有 $D<<r=nG \oplus R$ 。所以 $R$ 就是 $D<<r$ 除以 $G$ 的余数。

CRC 能够：

检查出所有的 1bit 错误
检查出所有的双 bit 错误
检查处所有长度不超过 $r$ 的错误
出现长度为 $r+1$ 的突发错误，检查不出的概率是 $1/(2^r-1)$
出现长度大于 $r+1$ 的突发错误，检查不出的概率是 $1/2^r$

3、多路访问控制

之前已经提到，有两种类型的链路。一个种点到点的（拨号访问的 PPP、以太网交换机和主机之间），另一种是多点连接，由于包会被发到共享型介质，每个节点都可以收到，相当于广播出去，所以也称为广播型链路（传统以太网、HFC 上行链路、802.11 WLAN）。

在广播型链路中，如果两个及以上的节点同时发送，则其他节点会收到多个信号的叠加，无法区分出原始信息，我们称这种情况是产生了冲突（collision）。所以我们要进行多路访问控制（Multiple Access Control，MAC），一般通过多路访问协议（Multiple Access Protocol，MAP）来实现（MAC 和 MAP 有时也互换使用，含义相似）。

MAP 是一种分布式算法，决定节点如何使用共享信道，也即何时可以发送。关于共享控制的信息也必须通过这个信道本身进行传输，没有带外的信道，各节点之间根据共享控制信息来协调信道的使用。

假如有一个 R bps 的广播信道，理想的 MAP 应该要做到：

仅有一个节点要发送时，能以 R bps 的速率发送
当同时有 M 个节点要发送时，每个节点可以以 M/R bps 的速率发送
是完全分布式的。不需要特殊节点来协调发送，也不需要进行时钟和时隙的同步。
简单，不拉低整体效率

MAP 协议大致分为三种：

信道划分协议：把信道按某种方式划分为小片，然后分配片给每个节点专用
随机访问协议：不进行信道划分，任由节点随时访问。允许冲突，能从冲突中恢复。
轮流协议：节点轮流进行发送。不会打断，所以数据较多的节点会获得更长的时间进行发送。

3.1、信道划分协议

TDMA，Time Division Multiple Access，时分多路访问。

信道的时间划分为一个个周期，周期内划分为若干个时隙。每个节点使用周期中固定的时隙。

缺点是，如果一个周期内那个节点不需要传输，对应的时隙就浪费了。

FDMA，Frequency Division Multiple Access，频分多路访问。

信道的有效频率被划分为一个个小的频段，每个节点被分配一个固定的频段。

缺点是，如果某个节点不需要发送，那个频段就被浪费了。

CDMA，Code Division Multiple Access，码分多路访问。

所有节点在整个频段上同时进行传输，采用不同的编码加以区分。前提是不会产生冲突，信号的同步很好，是线性叠加的，也即可以区分出来。

3.2、随机访问协议

当节点有帧要发送时，直接以全部的带宽 R bps 发送，不需要节点间预先协调。显然，如果同时有其他节点也在传输，就会发生冲突。

随机访问协议需要规定，如何检测冲突以及如何从冲突中恢复。

3.2.1、时隙 ALOHA 协议

其规定所有帧是等长的。时间被划分为相等的时隙，每个节点可以再时隙的开始发送一帧，持续一个时隙，且所有节点在时间上是同步的。

检测冲突：如果同一个时隙内有多个节点在发送，所有正在发送的节点可以通过检测信道意识到发生了冲突。

冲突恢复：意识到发生冲突后，每个节点都会在下一个时隙，以概率 $p$ 决定是否发送，直到无冲突发送成功

优点：

节点发送时，总能全速发送
高度分布式的，仅需保证时间同步即可，无需进行节点之间的沟通
简单

缺点：

存在冲突，发生冲突的那个时隙就浪费了
即使有帧要发送，也可能存在空闲的时隙。例如，上一个时隙冲突了，但是恰好都决定不发送。
发送帧必须传完，持续一整个时隙。但在此之前就可以检测出冲突，继续发送是无用功。
各节点时间上需要同步。

假定有 $N$ 个节点，每个节点都有很多的帧需要发送。一个节点成功发送帧的概率是 $p(1-p)^{N-1}$ ，则某时隙内恰好有一个节点发送成功的概率是 $f(p)=Np(1-p)^{N-1}$ ，由于：

$f'(p)=0\Leftrightarrow p=\frac 1 N$

所以：

$\lim_{N\rightarrow \infin}f_{\max}(p)=\lim_{N\rightarrow \infin}(1-\frac 1 N)^{N-1}=\frac 1 e$

所以信道最大利用率约为 37%

3.2.2、非时隙 ALOHA

也称为纯 ALOHA

节点无需在时间上进行同步，可以在任意时刻开始发送帧。则冲突发生的概率更大了，因为在时刻 $t_0$ 发送的帧，与在 $[t_0-t, t_0+t]$ 中某个时刻开始发送的帧都可能冲突。

非时隙 ALOHA 协议的信道最大利用率为 $1/2e$ ，约为 18%。

3.2.3、CSMA

即载波侦听多路访问

在传输前先侦听信道，如果侦听到信道空闲，就传送一个帧；如果侦听到信道忙，则推迟传送。这样可以减少冲突的发生。

但是仍然可能发生冲突。由于传播延迟的存在，可能侦听不到正在进行的传输。发生冲突时，整个冲突帧的传输时间都浪费了。

传播延迟（节点距离）越高，发生冲突的概率越大。

3.2.4、CSMA/CD

也即 CSMA 加上冲突检测，是有线局域网采用的协议

和 CSMA 一样，发送前要侦听信道；发送过程中检测到冲突后，停止发送，将信道让出，可以提升信道利用率。

冲突检测在有线局域网中容易实现，能量都集中在信道（线路）中，容易检测到冲突。

具体的有以太网 CSMA/CD 算法：

有数据要发送，创建帧
发送前，侦听信道。如果信道空闲，开始传送；如果信道忙，等空闲再开始发送。
发送过程中，侦听信道，进行冲突检测。如果一直没有冲突，发送成功；如果检测到冲突，放弃，之后再重发。
检测到冲突之后，除了放弃之外，还会发送一个Jam 信号，起到强化冲突的作用，告诉其他节点发生了冲突。（假如节点 A 发送的信号马上就要到达 B，B 恰好侦听觉得信道空闲，开始发送。结果发送没一会 A 的信号到了，B 马上放弃。此时 B 发送的信号只持续了非常短的一段时间，以至于别的节点可能都意识不到发生了冲突。所以 B 还会发送一个 Jam 信号用于强化冲突）
放弃后，节点进入指数退避状态。第 $m$ 次发送失败后，适配器会等待 $512K$ 个比特时间（当前链路满带宽发送一个比特的时间）后重发，其中 $K\in[0, 2^m-1]$ 。这个算法称之为二进制指数退避算法。

记 $t_{\text{prop}}$ 为 LAN 上两个节点之间的最大传播延迟， $t_{\text{trans}}$ 为传输最大帧所需的时间，则 CSMA/CD 的效率为：

$\text{efficiency}=\frac{1}{1+5t_{\text{prop}}/t_{\text{trans}}}$

以下情况，效率趋于 1：

$t_{\text{prop}}$ 趋于 0，小的局域网一个节点传输马上就能被接收到。事前的侦听就足够，几乎不会发生冲突。
$t_{\text{trans}}$ 趋于无穷大，某个节点要发送一个巨大的帧。协议保证不会被其他人打断，该节点独占信道一直发送。

CSMA/CD 的性能要比 ALOHA 更好，而且简单、廉价、分布式。

3.2.5、线缆接入网络中的 MAC

下行链路中，只有一个用户——CMTS。它将所有的数据广播到线缆中，所有的用户都可以看到所有的数据，如果数据标识的地址与自己的地址相符合，就接收下来。对于不同类型的数据（互联网、数字电视等），会通过 FDM 分成若干信道进行传输。

上行链路，则每个家庭都是用户，需要进行 MAC。不同类型的数据还是用 FDM，在此基础上还要用 TDM 划分出若干个时隙。每个用户竞争式地预约这些时隙，预约结果通过下行线路再返回回来，然后预约成功，用户就能占用相应时隙发送数据。

如果两个用户同时预约了某个时隙，就是发生了冲突，则两者的预约都不会成功，上行链路对这个时隙不会返回任何预约信息。用户意识到预约失败后采取二进制退避。

线缆接入网络就是多种 MAP 的结合体。

3.3、轮流协议

低负载时，信道划分协议效率低，只有少量信道被使用；随机访问协议效率高，在发送的节点能使用全部带宽发送。

高负载时，信道划分协议效率高，几乎所有信道都在使用；随机访问协议效率低，因为冲突增多了，浪费很多信道。

轮流协议在高负载和低负载表现都比较好，但是相对复杂。

轮询式

节点分为主节点和从节点。主节点依次邀请从节点进行传送。

缺点：

轮询本身也占用信道，有一定开销
等待时间较长，从节点只有被要邀请的时候才能发送，其他时间只能干等
单点故障问题。如果主节点故障，整个系统就会瘫痪。

令牌式

令牌是一个特殊的帧，在节点网络中轮转。令牌帧有特殊的标志位，表示自己当前空闲，是令牌帧；或者当前携带着数据，是数据帧。

某个节点要发送数据，且接收到空闲的令牌帧，该节点会给令牌帧的标志位置位，同时附加上数据。接收方接收到数据帧，如果是发给自己的，就把数据复制下来（一般还会置位表示自己已接收）。轮转一圈，又回到发送方之后，发送方重新置位，去掉数据，将其恢复成空闲的令牌帧。

最后由发送方来重置令牌帧，而不是接收方，是为了应对多个接收方的情况。

4、LAN

4.1、MAC 地址

32 位的 IP 地址是一个网络地址，用于子网与子网之间的路由。其使数据报从源子网到达目标子网，并最终能到达目标子网中的目标节点。

48 位的 MAC 地址是链路层的地址，用于使帧从一个网卡传递到与其物理连接的另一个网卡（同一个物理网络中）。理论上，全球每一张网卡都有唯一的 MAC 地址，网卡的 MAC 地址固化在其 ROM 中（有时候也可以通过软件来设置）。

为什么既要有 IP 地址又要有 MAC 地址，不能用一种就搞定吗？

IP 地址是分层的。一个子网所有设备的网络号是一致的，可以做路由聚集，减少路由表表项。而且我们希望网络层地址是可配置的。如果换成 MAC 地址，则需要定制一批网络号一致的硬件，且不可进一步配置，地址是固化不可改的。

MAC 地址是平面的。网卡在生产时并不知道用于哪个网络，而且地址也不能更改。所以只要作为一个唯一的标识，能区分不同的网卡即可。

这样分离开来，网卡坏了，IP 可以不变，只要与另一个网卡的 MAC 地址捆绑即可。上层也完全可以不用 IP 协议。

如果捆绑起来，假设只用 IP 地址，则仅支持 IP 协议，网络层协议不能换。

更极端，链路层不使用任何地址，每收到一个帧，都要传递到上面的网络层进行判断是否需要接受，会对网络层的工作产生干扰。

MAC 地址由 IEEE 管理和分配。

每一家网卡制造商会购买一片 MAC 地址空间，然后生产的设备就用这个地址空间里的地址。每个网卡都有唯一的 MAC 地址，且终身不变。

MAC 地址是平面的，可以接入任意一个网络。而 IP 地址是带层次的，不能随意调整。

4.2、ARP 协议

Address Resolution Protocol，地址解析协议。

网络层的路由中，从逻辑上看是从一个路由器到另一个路由器。但实际上，数据包要先下到链路层，封装为帧，传递给另一个网卡，再回到网络层，到达另一个路由器。在链路层中，是用 MAC 地址来导航的，要先把下一跳 IP 地址转化为下一跳 MAC 地址，这就是 ARP 协议的作用。

在 LAN 的每一个节点上，都有一个 ARP 表，存储了一些 LAN 节点的 IP-MAC 映射关系。映射关系并不是永久存储的，也有一个 TTL，一般是 20 分钟。这是因为 IP-MAC 的映射关系有可能是会变化的。

如果 A 要将帧发送给 B，首先拿着 B 的 IP 地址到 ARP 表中查询，查到了就直接用；

如果没有查到，A 会广播包含 B 的 IP 地址的 ARP 查询包。B 收到查询后，会回复 A 自己的 MAC 地址。A 收到之后，将映射关系保存到 ARP 表中，并将帧发送出去。

ARP 是即插即用的，无需网络管理员的干预，节点会自己创建更新 ARP 表项。

从一个子网的主机 A 经过路由器 R，到达另一个子网的主机 B 的过程，应该是这样的：

主机 A 创建一个 IP 数据报，源 IP 是 A 的 IP 地址，目标 IP 是 B 的 IP 地址
这个数据报交给网卡，下一跳是网关（R），所以网关会将数据包封装为一个帧，目标 MAC 地址是 R 的 MAC 地址，帧的内容包含原来的 IP 数据报
帧到达 R 之后，解封装，数据报又交到上层网络层。网络层根据数据包，发现目标 IP 为 B，查路由表，得到下一跳 IP 地址，以及出接口。
R 创建一个帧，目标 MAC 地址是 B 的 MAC 地址，从出接口继续传送给 B 的网卡。（注意！在路由器内部的一个接口到另一个接口，包并不带 MAC 地址，也就是不会重新封装。在出接口准备离开的时候才会重新封装）
B 的网卡接收到帧，解封装，传递给上层网络层。发现数据报的目标 IP 是自己，进行后续处理。

整个过程中，源 IP 和目标 IP 始终在 IP 数据报中不变。但是源 MAC 地址和目标 MAC 地址在不断变化，每一段链路都不仅相同。

ARP 协议是用于同一个广播域内解析 IP 地址到 MAC 地址。所以一个子网的主机向同一个子网的主机发包，会调用 ARP 协议解析 MAC 地址，然后发送；如果向另一个子网的主机发包，会直接交给默认网关，不会调用 ARP 协议尝试解析目标的 MAC 地址（调也没用，不在同一个广播域内，对方根本收不到 ARP 请求）

4.3、以太网

Ethernet，是目前最主流的 LAN 技术，比令牌网络和 ATM 网络更简单廉价。带宽从一开始的 10M，提升到现在的 10G。

一开始，采用的是总线结构。所有节点连接在同一根同轴导线上，一个主机发的包其他主机都能接收到，同轴导线末端有装置消除到达边缘的电磁波（否则会反弹回来造成碰撞）。

这种结构下，所有节点都在一个碰撞域内（发生碰撞时，会受到影响的节点构成的区域），所以可靠性非常差。一旦介质某一处破损，而截面又会反射信号，任何一个节点发送数据都会检测到产生碰撞。以太网又采用的是 CSMA/CD，就一直会等待。而且，一次只允许一个节点进行发送。

后来改用 HUB 结构，每个节点接到了 HUB 的一个端口上。一个节点发送数据包，HUB 会将数据包广播到其他所有端口。HUB 之间还可以级联起来。

这样一定程度上提高了可靠性。一般主机到 HUB 之间的介质容易受损，但是这样只影响这个节点，不会影响其他节点的正常工作，

但是 HUB 及其连接的主机还是处在一个碰撞域内，特别是级联情况下，影响到的主机更多。

目前最广泛采用的是星型结构（Switch 结构）。仍然是每个节点连接到 Switch 的一个端口上。但是一个节点发送数据包时，Switch 只会将数据包发送到想要前往的主机对应的端口，相当于一个瞬时的开关。

这样，碰撞域只瞬间存在于两台要通信的主机之间。同时，每个节点以及相连的交换机端口可以使用独立的以太网协议，且能多个节点同时发送而不至于产生碰撞。

以太网帧的结构如下图所示：

前导码，共 8 个字节，用于同步接收方和发送方的时钟速率，使得接收方将自己的时钟与发送端同步
目标 MAC 地址，共 6 个字节。如果某个设备接受到一个帧，发现目标 MAC 地址是自己或者广播地址，则接受，并解封装递交帧中的数据到网络层；否则忽略该帧。
类型：共 2 个字节，指出上层协议，一般是 IP（也可以是 Novell IPX、Apple Talk 等其他网络层协议）
数据
CRC 校验码。在接收方进行校验，如果未通过，丢弃这个帧。

以太网提供的是无连接、不可靠的服务。

无连接指的是，帧传输之前，发送方和接收方之间不会握手。

不可靠指的是，接收方不会发送 ACK/NAK 响应。一旦中间某些帧丢失，没有被接受方网卡收到，链路层和网络都不会处理，要一直到传输层。如果传输层使用了 TCP，就会重传；如果是 UDP，则也不会管，一直上到应用层，会看到出现缺失的数据。

以太网采用二进制退避的 CSMA/CD 协议作为 MAP。

有很多不同的以太网标准，它们使用相同的 MAP 和帧结构，但是速率、物理层标准、物理层媒介不尽相同。

例如这里面都以 100BASE 开头，100 表示速率为 100Mbps，BASE 表示使用的是二进制幅度调制技术。后半部分，T 表示双绞线（Twisted pair）作为物理介质，FX、SX、BX 则都是用光纤作为物理介质。

100Mbps 速率，通常也被称之为 Fast Ethernet。

4.4、物理层编码

Manchester 编码，曼彻斯特编码，在 10BaseT 中使用。

编码后，每一个周期中间，由 0 跳变到 1 表示 0，由 1 跳变到 0 表示 1：

这种跳变很容易从中提取出时间信号，使两边同步起来。但是同样由于跳变的存在，曼彻斯特编码的频率是原始信号的两倍，占用的带宽也变为原来的两倍。

10BaseT 要用 20Mbps 的带宽，效率是 50%。

4b5b 编码，用于 100BaseT 中。

由于曼彻斯特编码的效率较低，如果用于 100BaseT 中，需要 200Mbps 的带宽，代价较大。

4b5b 编码是将原始编码中每 4bit 用 5bit 来表示，同时保证过一定时间就有一个跳变，用于同步时钟。例如：

4b	5b	4b	5b
0000	11110	1000	10010
0001	01001	1001	10011
0010	10100	1010	10110
0011	10101	1011	10111
0100	01010	1100	11010
0101	01011	1101	11011
0110	01110	1110	11100
0111	01111	1111	11101

8b10b 编码，用于 1000BaseT 中，与 4b5b 类似。

4.5、交换机

之前已经简单介绍了一下交换机。

交换机对帧进行存储转发。对于到来的帧，检查帧头，根据目标 MAC 地址选择性转发到对应端口。转发时，采用 CSMA/CD 进行侦听、转发、回避等过程。

交换机本身并没有 MAC 地址，没有“寻址交换机”一说，只要物理连接到交换机上，包就能到达交换机并能被转发。

交换机对主机是透明的。通过交换机相联的节点仿佛直接连接起来一样，节点意识不到交换机的存在。

交换机是自学习的，即插即用，不需要网络管理员配置，可以自己更新交换表。

使用交换机的网络中，主机到交换机的连接是专用的，每条链路都是独立的碰撞域。

同时，交换机会缓存到来的帧，所以可以做到多路同时传输，到达交换机后，由交换机控制转发，不会碰撞。

交换机会有一个交换表（Switch Table），其中的表项包括：

MAC 地址
前往该 MAC 地址经过的接口
时间戳

与路由表相似。交换表是自学习的，而且每个表项有 TTL。

每次接收到一个帧，搜索交换表。如果找到了，就发往相应的端口；如果不知道，就泛洪，向所有端口转发。

特别地，如果源 MAC 地址和目标 MAC 地址一样，交换机会过滤掉这个包。因为既然包是从源来的，那肯定已经到达过了，就不用管了。

交换机是可以级联的，为了避免形成环，交换机会运行生成树算法，保证在一棵树上工作。

4.6、VLAN

虚拟局域网。

设想多个工作组的设备接到同一个交换机上，则所有 ARP、DHCP 类的广播包会被广播到接入了这个交换机上的所有工作组网络中，没有流量隔离。

又例如一个工作组的成员虽然坐在另一个工作组办公室，接入的是另一个工作组的交换机，但想要保持与原工作组网络的连接。原来的交换机很难实现这一点，当用户在不同组之间移动，或者用户属于多个组时，很难进行管理。

于是提出来 VLAN 的概念，特别是基于端口的 VLAN。

对于支持 VLAN 的交换机，可以通过配置，对交换机端口进行分组，将单个物理局域网（只有一个物理交换机，自然是连接设备都属于一个物理局域网）虚拟出多个虚拟局域网。

每个 VLAN 是一个广播域，彼此相互隔离。来自一个端口的广播包只能到达相同广播域中的其他端口，实现了流量隔离。

可以动态配置调整端口属于哪个 VLAN，很方便进行成员管理。

不同 VLAN 之间的转发是通过路由的。现实中，厂商一般销售的是 VLAN 交换机和路由器一体的设备。

对于跨多个交换机的 VLAN（即同一个 VLAN 的主机接入多个交换机上）之间的交换，可以通过干线端口（Trunk Port）来进行。

干线端口是交换机上的特殊端口，用于在跨多个交换机的 VLAN 之间传输帧。

为了区分不同的 VLAN，交换机之间转发的不是普通的 802.1 协议帧，而是 802.1Q 协议帧，其中新增了四个字节，其中：

TPID，标记协议标识符，占两字节，为固定值 0x8100，表示该帧载有 802.1Q 标记信息
TCI，标志控制信息
- VLAN ID，占 12bit
- 优先级，占 3bit
- 协议类型，占 1bit

5、MPLS

Multi-Protocol Label Switching，多协议标签交换。

这种技术引入固定长度的标签，然后按标签转发数据包，从而实现高速转发。标签的结构如下：

标签：占 20bit
实验位：占 3bit
栈位：占 1bit。MLPS 支持多个标签嵌套，栈位置 1 表示这是最底层的标签
TTL：占 8bit

一个经过 MPLS 加强的帧仅能在两个均为 MLPS 使能的路由器之间发送。MLPS 使能的路由器又称为标签交换路由器，它们只根据标签值（而不是目标 IP）转发报文到出口，相应的也有 MLPS 转发表。

基于 MLPS 标签的转发更加灵活，可以实现流量工程（类似于 SDN）。链路出现问题时可以借助提前计算的备份路劲快速重新路由。

可以通过拓展 OSPF 协议和 IS-IS 协议，使其能够承载 MPLS 路由选择信息。其实的 MPLS 使能路由器使用 RSVP-TE 协议在下游 MPLS 使能路由器上建立基于 MPLS 标签的转发。

6、数据中心网络

数据中心中有成千上万的主机，在很近的距离紧密耦合。数据中心的网络需要满足可靠性、低延迟、高带宽、高吞吐量等要求，以及管理、负载均衡、安全等方面。

一个典型的结构图如下：

data-center-net

交换机和机架之间存在非常多的连接，同构冗余来提供可靠性。

大型的数据中心通常由多台负载均衡器。负载均衡器是一个网络设备，用于将传入的网络流量分发到多台服务器上，以避免某台服务器过载。

数据中心网络运用了很多新协议：

链路层：使用 RoCE（基于融合以太网的远端内存直接访问）协议。数据在网络中两个节点的应用程序的虚拟内存间传输，不需要额外的复制和缓存，不需要内核参与，传输所有处理都由 NIC 硬件完成。
传输层：使用 ECN 协议来做拥塞控制，使用逐跳的拥塞控制试验方法
路由选择和管理：SDN 被广泛使用；尽可能将相关服务放到尽可能近的位置，减少第二层和第一层的通信。

第七章无线网络与移动网络

1、无线网络

无线网络，正如其名字所说，是区别于传播介质为有线电缆的有线网络的网络，其播介质为无形的电磁波。无线网络的两个重要挑战是：

如何在无线链路上传输数据，进行通信
如何处理用户在不同接入点之间的切换

无线网络的三个要素是：

无线主机：笔记本、智能手机、ITO 设备等运行应用的中断。可以是移动的也可以是固定的，无线不等于移动。
基站：其本身通常连接到有线网络，是有线网络与无线主机之间的中继。例如蜂窝塔或者 802.11 无线网的接入点。
无线链路：将无线主机连接到基站或者另一台无线主机。不同的无线链路可能采用不同的标准，拥有不同的传输速率、覆盖范围、传输频率等。无线链路需要协调多种访问控制协议。

无线网络标准通常以 802.11 开头，例如 802.11a、802.11b、802.11g、802.11n、802.11ac 等。覆盖范围和链路速率是无线网络的两种主要特性，不同标准的无线网络差异也主要体现在这两个方面。

无线网络大致可以分为两种：

基于基础设施的无线网络：存在基础设置（基站），无线主机通过基站连接到有线网络。移动主机从一个基站的覆盖范围移动到另一个基站的覆盖范围后，会自动改变连接的基站，进行切换。
自组织的无线网络：没有基站，无线主机之间只能向链路覆盖范围内的其他主机发送数据。所有的节点自己组织成一个网络，由节点自己提供路由、地址分配等服务，这种网络也被称为自组织网络（Ad hoc network）。

2、无线链路特征

无线链路与有限链路的区别在于：

信号衰减：无线局域网的信道是开放空间，传播介质是电磁波。电磁波在穿过物体时，信号会减弱；信号在自由空间中扩散，强度也会随距离增加而减弱，存在路径损耗。
干扰：不同信号源使用同一个频段发送信号会彼此干扰，环境中还可能存在电磁噪声，也会干扰信号传输。
多径传播：电磁波在传播过程中可能有反射，导致在接受处，收到传播时间不同的同一个信号，或者说在传播过程中经过多条不同的路径，最终到达接收端时会叠加在一起，使信号变模糊。

信噪比（Signal-to-Noise Ratio，SNR）是一个重要的无线链路质量指标，定义为收到的信号强度与环境中的噪声强度之比。SNR 越大，表明越容易从背景噪声中提取原始信号，链路质量越好。

比特差错率（Bit Error Rate，BER）是另一个无线链路质量指标，表示在传输过程中，接收端接收到的比特中错误比特的比例。

对于固定的调制方案，一般 SNR 越大，BER 越小。对于固定的环境（SNR 固定），一般比特传输率越大的调制方案，BER 越大。

无线链路在有多个发射者时，由于无线链路本身的特性，还会存在隐藏设备问题

考虑有 A、B、C 三个节点，A 和 C 都向 B 发送。由于距离和衰减的原因，A 的信号可以传到 B，但是到 C 是几乎衰减完了；反过来 C 的信号可以传到 B，但是到 A 时也衰减完了。C 对于 A 来说相当于“隐藏”起来了，反之亦然。如果采用 CSMA/CD，A 和 C 总会侦听到信道为空，有包就发送。两个节点恰好同时发送时，信号在 B 附近会发生冲突。

WLAN 被蜂窝技术中，广泛采用的信道划分协议为码分多址（CDMA）。

CDMA 给每个用户分配不同的编码。编码可以理解为一个码片序列，用户发送时要先将每段数据“乘”上码片序列中对应的值，再发送出去。

在用户的码片序列“正交”的情况下，允许多个用户在同一频段上同时发送数据，仍然能够用码片序列还原出对应用户发送的数据。

alt text

3、802.11 WLAN

802.11 是一个协议族，包含了一系列关于无线局域网段标准。802.11 设备工作在两个不同的频段上，2.4GHz 和 5GHz。不同标准的无线局域网均使用相同的 MAP——CSMA/CA，链路层的帧结构也是相同的。

802.11 无线局域网结构的基本构件是基本服务集（Basic Service Set，BSS）。一个 BSS 包括一个或多个无线主机、一个接入点（基站）以及无线主机与接入点之间的无线链路。

整个无线网络的频谱会被划分为不同频率的信道。由 AP 管理员为各个 AP 分配 SSID（Service Set Identifier，服务集标识符），以及信道号。相邻的 AP 可能会选用相同的信道，会产生干扰。

新加入的节点必须先于 AP 关联。802.11 标准要求，每个 AP 必须周期性的广播信标帧（Beacon Frame），其中包含了 AP 的 MAC 地址等信息。节点与 AP 建立关联包括主动和被动两种方式：

被动扫描：节点等待 AP 广播的信标帧到达，然后选择一个 AP 准备关联，向其发送关联请求帧。被选择的 AP 收到请求后，会回复关联响应帧。最后，关联建立。
主动扫描：节点广播一个关联请求帧，AP 收到后回复关联响应帧。节点选择一个 AP 建立关联，向其发送关联请求帧。被选择的 AP 收到请求后，会回复关联响应帧。最后，关联建立。

关联建立之后，通常节点向关联的 AP 发送一个 DHCP 发现报文，以获取 AP 所在子网的一个 IP 地址。

4、CSMA/CA

CSMA/CA，也即 CSMA 加冲突避免，是 802.11 网络使用的 MAP

之前已经介绍，无线链路存在各种问题。这些问题导致，冲突检测难以实现，也没有意义。

CSMA/CA 的过程如下：

节点侦听信道，如果一个 DIFS（Distributed Inter-Frame Spacing，分布式帧间隔）内信道闲，就发送整个帧，且不做冲突检测，发送过程中不监听。
如果检测到信道忙碌，会随机选择一个回退值。当信道空闲时，不断递减这个回退值；信道忙时，回退值不变。回退值归零时，发送整个帧。
接受方接收到帧之后，如果一个 SIFS（Short Inter-Frame Spacing，短帧帧间隔）内信道闲，会发送 ACK。
如果发送方没有接收到 ACK，会增加回退值，准备重新发送。

一般 SIFS 小于 DIFS，所以 ACK 总是优先发送出去，减少不必要的重传。

考虑两个节点同时开始等待第三个节点发送。如果是 CSMA/CD，第三个节点一发完，两个节点侦听到信道空闲，同时发送，则又会冲突。而如果是 CSMA/CA，检测到信道忙碌，两个节点都会选择一个随机的回退值，回退值清零才发送而不是侦听到信道空就发送。由于回退值大概率是不同的，所以两个节点大概率是依次发送，不会冲突。而且由于 CSMA/CA 不做冲突检测，中途不会放弃，发生冲突重传相当于又浪费了一整个发送时间，代价巨大。CSMA/CA 本质上就是事前借助随机回退值，避免了冲突的发生。

CSMA/CA 还有预约机制。在发送一个长帧之前，发送方先用 CSMA 向目标发送一个小的 RTS（Reservered To Send）分组（也可能冲突，但是较小，影响不大）。目标接收到 RTS 分组后，会广播一个 CTS（Clear To Send），作为 RTS 的响应让发送方准备发送帧。其他节点也能收到 CTS，知道这个信道被占用，接下来会推迟发送。

5、802.11 帧结构

802.11 帧结构如下图所示：

802.11-frame

第一行数字的单位是 byte，第二行数字的单位是 bit。

由四个地址段：

地址 1：接收方 MAC 地址
地址 2：发送方 MAC 地址
地址 3：AP 连接到的路由器接口的 MAC 地址
地址 4：仅在自组织网络中使用

AP 仅起到一个中继作用。考虑下面这个拓扑图：

其中 H1 向外网发送一个包。则其 802.11 帧的三个地址分别为：

地址 1：外网机器的 MAC 地址
地址 2：H1 的 MAC 地址
地址 3：R1 某端口的 MAC 地址

从无线网络到有线网络，帧要从 802.11 帧变为以太网帧，这个过程在 AP 上完成。AP 最终封装的以太网帧中：

源 MAC：H1 的 MAC 地址
目的 MAC：R1 的 MAC 地址

可以发现，源 MAC 不是 AP 自己的 MAC，所以说其仅仅起到一个中继作用。

反之，从外网发回 H1 的数据包，在 AP 上从以太网帧变为 802.11 帧。把以太网帧的源 MAC（是 R1 的 MAC）填到地址 2，目的 MAC（是 H1 的 MAC）填到地址 1，地址 3 仍然填 R1 的 MAC。

6、802.11 特性

速率自适应。当移动设备逐渐远离基站时，SNR 逐渐降低，BER 逐渐升高。当 BER 超过一定值时，基站和移动设备换用不同的调制方式，动态降低传输速率，以降低 BER。

功率管理。节点可以将 802.11 帧中的功率管理位置 1，告知 AP 自己将休眠一段时间。AP 收到这个帧之后，不会再向这个节点传输数据帧，而是会缓存目的地为该节点的数据帧。信标帧中会包含一个列表，如果某个节点有帧缓存在 AP 上，AP 会把这个节点加入列表中。

节点收到信标帧后检查列表，如果有自己，会醒来，并向 AP 发送一个 PS-Poll 帧，主动请求 AP 发送缓存的帧。如果没有，继续休眠，直到到达预定的休眠时间。

7、蓝牙

由 802.15.1 标准定义，是一种短距离无线通信技术（覆盖范围直径小于 10 米），主要用于设备之间的数据传输。这是一种无基础设置的自组织网络，工作于 2.4GHz 频段。

网络中的设备分为主设备和从设备，主设备轮询从设备，从设备只有在轮询到自己时才能发送数据。

蓝牙网络中每个时隙的长度为 625 微秒，发送方在每个时隙利用 79 个信道中的一个进行传输，然后已一种伪随机方式切换信道（调频拓展频谱）。

第一章 概论

1、互联网

2、网络边缘

3、网络核心

3.1、电路交换

3.2、分组交换

3.3、分组交换的连接

3.4、关键功能

4、接入网

4.1、modem

4.2、DSL

4.3、线缆网络

4.4、家庭/企业接入

5、物理媒介

6、Internet 结构和 ISP

7、分组延时、丢失和吞吐量

7.1、分组延时

7.2、分组丢失

7.3、吞吐量

8、协议层次和服务模型

8.1、服务

8.2、协议

8.3、数据单元

8.4、互联网协议栈

8.5、各层次的数据单元

第二章 应用层

1、网络应用的体系结构

1.1、C/S 模式

1.2、P2P 模式

1.3、混合模式

2、进程通信

2.1、第一个问题——对进程编码

2.2、第二个问题——穿过层间需要的信息

2.3、第三个问题——指定应用层协议

3、Web 和 HTTP

3.1、Web 页面和 URL

3.2、HTTP

3.3、响应时间模型

3.4、HTTP 报文格式

3.4.1、HTTP 请求报文

3.4.2、HTTP 响应报文

3.5、Cookies

3.6、Web 缓存

4、FTP

5、Email

5.1、SMTP 与邮件发送接收过程

5.2、MIME

5.3、邮件访问协议

6、DNS

6.1、层次化命名

6.2、分布式名字服务器

6.2.1、DNS 服务器的层次结构

6.2.2、查询过程

6.2.3、DNS 报文

6.3、维护

7、P2P 应用

7.1、非结构 P2P

7.1.1、集中式目录——Napster

7.1.2、完全分布式——Gnutella

7.1.3、混合式——KaZaZ

7.1.4、BitTorrent

7.2、结构 P2P

8、CDN

8.1、多媒体流化服务

8.2、CDN

9、Socket API 编程

9.1、TCP 编程

9.2、UDP 编程

第三章 传输层

1、多路复用/解复用

2、UDP

3、可靠数据传输的原理

3.1、RDT 1.0

3.2、RDT 2.0

3.3、RDT 2.1

3.4、RDT 2.2

3.5、RDT 3.0

3.6、流水线协议

3.7、滑动窗口协议

3.7.1、发送窗口和接受窗口

第一章概论

第二章应用层

第三章传输层

第四章网络层：数据平面

第五章网络层——控制平面

第六章链路层和局域网

第七章无线网络与移动网络