【计算机网络】协议总结

链路层

可靠传输

在链路层传输中，可能出现的错误包括数据位出错、分组丢失、分组失序、分组重复等。可靠传输服务希望实现发送端发送什么，接收端就接收到什么。虽然下面将在链路层这一章节中介绍SW、GBN、SR三种协议，但要明确的是，可靠传输服务并不仅仅局限于链路层，其他各层均可选择实现可靠传输。

停等协议 - SW

停等协议(Stop and Wait, SW)的发送方每发送一帧数据就停止，并等待接收方发送确认帧，收到确认后再发送下一帧。

确认与否认、超时重传

发送方发送数据后等待接收方ACK或NAK的响应，并启动超时计时器，如果一定时间收不到响应则启动超时重传。

确认丢失

如果确认分组丢失，接收方需要能感知到数据分组是否重复，因此数据分组需要编号，在停等协议中，由于每发送一个数据就进行等待，因此使用一位编号就够了。

确认迟到

如果确认分组迟到，在图示情况中，发送方需要感知到第二个ACK是对第二个DATA 0的重复确认，而不是对DATA 1的确认。因此确认分组也需要使用一位编号。

回退N帧协议 - GBN

回退N帧协议(Go Back N, GBN)允许发送方连续发送多个帧（即发送窗口可以大于1），以解决停等协议信道利用率低的问题。

发送方可在未收到接收方确认分组的情况下，将序号落在发送窗口内的多个数据分组全部发送出去；但接收方的接收窗口大小仅为1，也就是只有接收到了此窗口所代表的序号的分组，接收方才会回复ACK并且移动接收窗口。同理，发送方收到了发送窗口中最早的那个序号对应分组的ACK，才会移动发送窗口。

累计确认

接收方不一定要对收到的数据逐个确认，也可以对最后一个分组进行确认。ACK n表示序号为n及其之前的分组都已经被正确接收。称这种方法为累计确认。例如图中，接收方只对1号、4号数据分组进行确认，并且ACK 1在传输过程中丢失，发送方仍然可以根据收到的ACK 4判断0~4号分组都已经被正确接收。

有差错情况

例如发送方发送了5/6/7/0/1五个分组，但5号数据分组丢失，此时由于到达的四个分组都与接收窗口序号不匹配，接收方会将其丢弃，并重复响应ACK 4。

选择重传协议 - SR

选择重传协议(Selective Repeat, SR)加大接收窗口的长度（即接收窗口也可以大于1），缓存乱序到达的帧，这样不至于在一些情况下需要重传所有未被确认的帧从而导致效率降低。

与GBN一样，发送方可在未收到接收方确认分组的情况下，将序号落在发送窗口内的多个数据分组全部发送出去；接收方可接收未按序到达但没有误码并且序号落在接收窗口内的数据分组；发送方收到未按序到达的确认分组时，对其进行记录，以防止其相应数据分组的超时重发，但发送窗口不能向前滑动。为了使发送方仅重传出现差错的分组，接收方不再采用累积确认，而是对每个正确接收的数据分组进行逐一确认。

例如发送方发送了0/1/2/3四个分组，但2号数据分组丢失，此时0号、1号按序到达，接收窗口可以向前移动；而3号分组可以被接收，但接收窗口不能移动。

返回的ACK到达发送方之后，发送方可以把发送窗口的起点移动到2号，同时记录3号分组已接收。移动发送窗口后，可以把新纳入窗口的4号、5号发送出去。

如果4号、5号可以被正常接收，并且返回的ACK 4、ACK 5可以正确到达发送方，那么最后会使得发送窗口和接收窗口都卡在2的位置，并最终触发2号分组超时重传。

媒体接入控制

共享信道要着重考虑的一个问题就是如何协调多个发送和接收站点对一个共享传输媒体的占用，即媒体接入控制(Medium Access Control, MAC)。

载波监听多路访问 - CSMA

载波监听多路访问(Carrier Sense Multiple Access, CSMA)的思想是在发送帧之前监听信道。其原理是：当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会互相叠加而增大。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。

非坚持CSMA

非坚持指的是对于监听信道忙之后就不继续监听。
当主机要发送数据并对信道进行监听时，发现信道空闲则可直接传输；忙则等待一个随机的时间之后再进行监听。
这样的缺点是可能存在各主机都在延迟等待过程中，使得信道处于空闲状态但无人发送数据，媒体使用率降低。

1-坚持CSMA

当主机要发送数据并对信道进行监听时，发现信道空闲则可直接传输；忙则一直保持监听，直到空闲马上传输。
这样的缺点是假如有两个或两个以上的站点有数据要发送，冲突就不可避免。

p-坚持CSMA

当主机要发送数据并对信道进行监听时，发现信道空闲则以p概率直接传输；忙则一直保持监听，直到空闲再以p概率传输。对于空闲时其余的1-p概率，则会等到下一个时间槽重复上述规则。

碰撞检测 - CSMA/CD

上述的三种CSMA发生冲突后，仍然会坚持把数据帧发完，这时接收方收到叠加在一起的有碰撞数据会响应否认NAK或者不响应等待发送方重发，这是一种被动的方式。碰撞检测(Collision Detection, CD)就是边发送数据边检测信道上信号电压的变化情况，来判断是否有其他主机也在发送数据。如果发现碰撞则立刻主动终止发送。

强化碰撞

以太网的强化碰撞：当发送帧的站点检测到碰撞，除了立即停止发送帧外，还要再继续发送48位的人为干扰信号，以便有足够多的碰撞信号使所有站点都能检测出碰撞。

争用期

图中$\tau$是单程传播时延，$\delta$并没有很强的物理含义，我们只是假设主机D发送数据后经过$\delta$时间检测到A的信号。这张图的重点是，在$\delta$趋近于0的情况下，A最长需要$2\tau$的时间检测到碰撞。我们把$2\tau$称作争用期(Contention Period)，它的意义是只要经过$2\tau$时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞。

截断二进制指数规避算法

第$cnt$次重传的退避时间为$2\tau \times r$，r为从集合$\{0,1,2,3,\dots ,2^{\min (cnt,10)}-1\}$中随机选出的数。当重传达16次仍不能成功时，则丢弃该帧，并向上层报告。

最小/最大帧长的由来

如果一个帧的长度太小，可能一个站点还没来得及检测到其发送的帧产生了碰撞，就已经将这个帧发送完毕了。帧的传输时间要大于争用期。对于10 Mb/s以太网，帧的最小长度为64字节。减去帧头和帧尾，数据部分至少应为46字节。

如果一个帧的长度过大，一个站点不停地发送帧，其他站点就一直无法无法使用信道；如果帧的长度过大，接收方的缓冲区也可能产生溢出。以太网规定数据部分最长为1500字节，加上帧头和帧尾，帧的最大长度为1518字节。

碰撞避免 - CSMA/CA

在无线局域网中可能会出现隐蔽站的问题，使用碰撞检测意义不大。不同于以太网，802.11标准使用碰撞避免(Collision Avoidance, CA)而不是碰撞检测。

使用确认帧

CSMA、CSMA/CD都没有使用确认帧机制。但因为无线信道的通信质量远不如有线信道，因此CSMA/CA要求接收方收到数据帧后响应ACK，发送方收到ACK就可以进行下一个数据帧的发送。

预约信道

802.11标准允许发送站对信道进行预约。
检测到信道空闲时，源站先发送请求发送(Request To Send, RTS)，包括源地址、目的地址和这次通信所需的时间；
若目的站收到源站发来的RTS帧且媒体空闲，就响应允许发送(Clear To Send, CTS)它也包括这次通信所需的时间（从RTS复制）。CTS帧可以被目的站范围内所有站点收到，其作用有两点：给源站明确的发送许可，同时指示其他站在预约期内不要发送。

网络层

自治系统、IGP和EGP

自治系统(Autonomous System, AS)通常由一组处在相同管理控制下的路由器组成。通常，一个互联网服务提供商(Internet Service Provider, ISP)中的路由器以及连接它们的链路构成一个AS。不过某些ISP会将它们的网络划分为多个AS。一个自治系统将会分配一个唯一的自治系统号(ASN)。

自治系统可以被理解为互联网中的小型网络单位。由此产生了自治系统内部路由选择协议(intra-AS routing protocol)和自治系统间路由选择协议(inter-AS routing protocol)。有时也会把这两个概念称作内部网关协议(Interior Gateway Protocol, IGP)和外部网关协议(Exterior Gateway Protocol, EGP)。

IGP和EGP并不指代某个具体的协议，而是代表一个类别。下面会讨论如下三个协议：

路由信息协议 - RIP

路由信息协议(Routing Information Protocol, RIP)是基于距离矢量法的，较为简单，适用于小网络。
RIP协议要求网络中每一个路由器都维护从自己到每个其他目的网络的距离，这个距离用跳数来衡量，每经过一个路由器跳数+1。
RIP协议允许一条路最多包含15个路由器，即跳数最多为15，超过则表示不可达。
RIP协议只和相邻路由器交换信息，交换的信息是自己的路由表。

RIP协议路由更新规则

路由表中包含目的网络、到目的网络的距离、下一跳路由器。对于每个路由器，路由表更新规则为：

考虑一个例子：

开放最短路径优先 - OSPF

开放最短路径优先(Open Shortest Path First, OSPF)是基于链路状态法的，较为复杂，适用于大网络。
每个路由器使用洪泛法向区域中的所有路由器发送信息，因此最终整个区域内所有路由器都得到了区域完整的图结构。然后每台路由器在本地运行Dijkstra最短路径算法，确定一个以自身为根节点到所有子网的最短路径树。

在单个自治系统中再划分层次结构

为了应用于规模很大的网络，OSPF协议可以将一个自治系统再划分为若干更小的区域。在每个区域内，一台或多台区域边界路由器负责为流向该区域以外的分组提供路由选择。在AS中只有一个区域被配置成主干区域。主干区域的主要作用是为该AS中其他区域之间的流量提供路由选择。该主干总是包含本AS中的所有区域边界路由器、但也可能包含非边界路由器。在AS中的区域间的路由选择要求分组先路由到一个区域边界路由器（区域内路由选择），然后通过主干路由到位于目的区域的区域边界路由器进而再路由到最终目的地。

OSPF 相较于 RIP 的优点

边界网关协议 - BGP

边界网关协议(Border Gateway Protocol, BGP)在这里只做简单的概念性介绍。

在不同自治系统内，度量路由的代价可能不同；自治系统之间的路由选择也需要考虑相关的政治、经济、安全因素。BGP只希望选择一条可达，无环路，且相对较优的路由。

在配置BGP时，每个AS需要选择至少一个路由器作为BGP发言人，不同自治系统的BGP发言人要通过TCP连接交换路由信息。当BGP发言人互相交换了网络可达性信息后，各BGP发言人就根据自己的策略选择出到达各自治系统的较好的路由，也就是构造出树形结构、不存在回路的连通图。

IPv4编址

网际协议(Internet Protocol, IP)现在有两个常用的版本，IPv4和IPv6。
每个IPv4地址长度为32位，等价为4字节，大约有40亿个可能的地址。地址通常用点分十进制记法表示，例如192.32.216.9。

粗略的分类

IPv4地址有诸多分类，且其中有很多特殊地址、保留地址，因此先从最普遍的地址分类入手，再逐渐深入介绍特殊的IPv4地址。
IPv4地址可以看作由两部分组成：网络号和主机号。根据网络号和主机号分为A、B、C三类，同时还有特殊的D、E两类。

特殊地址

上述分类中，各分类的范围中，都有很少一部分的地址有特殊的含义：

私有地址

提到IP地址，第一反应可能就是192.168.0.1这串数字了！又或许你打开cmd窗口输入ipconfig，然后发现你的设备IP地址是192.168.137.1。这个问题可能让人感到困扰：一方面，课本上说IP地址是互联网上唯一的；另一方面，似乎无论你处在哪个移动或有线网络下，你的设备IP总是长成192.168.x.x的样子，这似乎根本无法保证唯一性。这个问题涉及到私有地址。

除了特殊IP地址，还有一部分地址作为私有地址；这些地址不能用于在互联网上标识一个主机，只适用于在内部网络中使用。它们是：

这样的私有地址仅对本地网络中的设备有意义。但既然如此，想在互联网上发送或接收数据时，该如何处理编址呢？这需要用到网络地址转换(Network Address Translation, NAT)，NAT可以将内网的IP地址映射到互联网上的IP地址。从某种角度，NAT使得路由器对外界隐藏了本地网络的细节。

IPv6编址

用IPv6来取代IPv4主要是为了解决IPv4地址用尽问题，同时IPv6也在其他方面对于IPv4有许多改进。
每个IPv6地址长度为128位，地址通常用8组四位十六进制数表示，例如2001:0db8:86a3:08d3:1319:8a2e:0370:7344。

IPv6的地址有时可以省略，具体规则是：

例如下面的IPv6地址是等价的：

IPv6比IPv4的改进

地址解析协议 - ARP

在以太网协议中规定，同一局域网中的一台主机要和另一台主机进行直接通信，必须要知道目标主机的MAC地址，而网络层和运输层只关心目标主机的IP地址。
地址解析协议(Address Resolution Protocol, ARP)用于完成网络层地址（例如IP地址）和链路层地址（即MAC地址）的转换。

互联网控制报文协议 - ICMP

互联网控制报文协议(Internet Control Message Protocol, ICMP)被主机和路由器用来彼此沟通网络层的信息，ICMP最典型的用途是差错报告，提供可能发生在通信环境中的各种问题反馈。通过这些信息，管理者可以对所发生的问题作出诊断，然后采取适当的措施解决。

动态主机配置协议 - DHCP

动态主机配置协议(Dynamic Host Configuration Protocol, DHCP)是使用UDP协议的应用层协议，用于自动给内网机器分配IP地址等信息。虽然可以手动给内网设备一个一个的分配IP地址，但这项任务通常由DHCP服务器完成。

DHCP的四个步骤是：

运输层

用户数据报协议 - UDP

用户数据报协议(User Datagram Protocol, UDP)提供无连接、不可靠的服务，支持单播、多播、广播；UDP面向报文，对应用进程交下来的报文既不合并也不拆分。

UDP传输效率更高，其牺牲了可靠性来保证性能。UDP适用于实时应用，例如视频会议、电话等。
UDP首部开销小，只包括源端口、目的端口、长度、校验和共8字节。

传输控制协议 - TCP

传输控制协议(Transmission Control Protocol, TCP)提供连接、可靠的服务，仅支持单播；TCP面向字节流，把应用进程交下来的报文仅当作字节流。

TCP首部由20字节固定首部和最大40字节的扩展首部构成。下面是对一些字段的解释：

TCP连接建立

TCP通过三报文握手建立连接，目的是使双方能感知到对方的存在，同时协商一些参数。过程如下图所示：

TCP连接释放

TCP通过四报文挥手释放连接。服务端响应客户端的释放请求后进入关闭等待状态，但如果TCP服务器进程还有数据要发送，服务端仍然会发送完最后的数据才会发送连接释放报文段。
客户端确认了连接释放报文段后，还要经过2倍最长报文段寿命(Maximum Segment Lifetime, MSL)才进入关闭状态，这是为了防止客户端确认报文丢失，如果直接进入关闭状态就无法接收到服务端重传的连接释放报文。过程如下图所示：

TCP可靠传输

TCP综合了GBN和SR的一些机制来实现可靠传输。

TCP的接收方也会维护接收窗口，这点与SR类似；但TCP采用与GBN类似的累计确认。
需要注意的是，GBN中ACK n表示序号为n及其之前的分组都已经被正确接收，而TCP中ACK n表示序号为n-1及其之前的分组都已经被正确接收，接收方期望收到的最小序号的分组是序号n。

如果接收方收到了失序到达的分组，会缓存这些分组（像SR一样），但不是对分组逐一确认，而是累计确认期望收到的最小序号的分组（类似GBN）。TCP同样只有一个超时计时器（像GBN一样），如果发生超时就会重传窗口内所有已发送但未得到确认的数据。

不过，例如当发送方陆续发送序号n之后的分组，但却收到了重复的ACK n时，就可以判断分组n一定因为某些原因没有被接收方收到。 此时发送方可以不等到重传计时器超时，而是在收到3次重复确认后，就立即重传这个分组，这也被称为快重传。

TCP流量控制

传输速度快固然是好事，但如果发送方传输速度超过了接收方的接收能力就会导致丢包。TCP流量控制就是接收方通过ACK设置头部中的窗口字段，根据自己接收缓存的大小，动态地调整发送方的发送窗口大小。

一个特殊的情况是，当接收方通知发送方窗口大小为0时，发送方就不再会发送新的数据。此时发送方不收到接收方调整接收窗口的报文，双方就会陷入互相等待。因此TCP为每个连接设有一个持续计时器，只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器；若持续计时器超时就发送一个零窗口探测报文，对方在确认探测报文时就给出现在的窗口值。

TCP拥塞控制

如果网络中对某一资源的需求超过了可用的资源，例如很多主机都向带宽有限的链路上发送数据，就会引起拥塞。TCP拥塞控制就是为了防止过多数据注入到网络当中。

拥塞控制的实现

慢开始

执行慢开始算法时拥塞窗口初始大小为1，同时要设定慢开始门限值（图中是8），拥塞窗口将指数增大到门限值。

拥塞避免

拥塞窗口增大到门限值后执行拥塞避免算法，此阶段拥塞窗口线性增加1。
随着拥塞窗口增大，可能会有报文段发生丢失，引起发送方重传计时器超时。因此发送方判断网络可能出现了拥塞，此时会：

将慢开始门限值更新为发生拥塞时拥塞窗口的一半

将拥塞窗口置为1，并重新开始执行慢开始算法

慢开始和拥塞避免算法是1988年Tahoe版本提出的TCP拥塞控制算法，1990年Reno版本又增加了快重传和快恢复。

快重传

快重传就是使发送方尽快进行重传，而不是等超时重传计时器超时再重传。见上文TCP可靠传输。

快恢复

发送方一旦收到3个重复的确认，就知道现在只是丢失了个别的报文段。于是不启动慢开始算法，而执行快恢复算法。
发送方将慢开始门限值和拥塞窗口大小调整为当前窗口大小的一半，并开始执行拥塞避免算法。

参考资料

本文的部分内容、图片来源于：