第三层数据链路层 | Rainnn の Blog

数据链路层负责两台网络中相邻的机器的承载信息的帧的传输：主要解决传输中错误的检测和纠正以及数据流的控制问题

数据链路层是计算机网络中自上而下的第二层。在第一层物理层中，关注的重点在于传输介质和数据的编码等问题上，最终实现了数据的传输，这种通信主要由网卡（其实还包括操作系统的一部分）硬件完成。

利用物理层提供的不可靠的比特传输服务（功能），在两台相邻机器之间实现可靠高效的数据通信的算法和协议。或者可以说成将一条不可靠的物理线路（line）通过协议提升为一条可靠的数据链路（data link）。

相邻：两台机器之间通过一条信道连接起来。按序到达是其固有特性。

可靠：接收方接收到的数据和发送方发送的数据一致。可靠性主要包括两个方面的内容：差错控制和流量控制。

差错控制是为了克服线路误差带来的传输错误

流量控制是为了避免快速的发送方淹没慢速的接收方。

淹没：指发送方发送的太快，使得接收方来不及接收所有的数据，造成数据的丢失。

高效：充分利用信道的带宽（传输能力）

高效性主要指能够充分利用线路的带宽，主要是克服线路延迟给可靠传送数据带来的限制。

3.1 数据链路层的设计问题

3.1.1 提供给网络服务层的服务

数据链路层的功能是为网络层提供服务

最主要任务是把数据从源机器的网络层传输到目标机器的网络层

数据链路层从网络层获取数据包，将其封装为“帧头+有效载荷+帧尾”的帧（Frame），数据链路层的核心就是帧的管理。

帧：数据链路层对等体之间交换的协议数据单元。关于帧，有这些需要知道的内容：

由发送方实体将从网络层接收到的分组添加额外的字段（协议字段）封装而成。

接收方实体根据协议字段的取值执行相应的操作（协议算法）。

判定接收的数据正确后，最终将协议字段去掉，将分组提交给自己所在设备的网络层。

帧的长度是有限制的。每个传输线路都有一定的差错率，帧的最大长度限制是为了让一个帧在传输过程中出现差错这个现象成为“小概率事件”，从而易于处理出错的帧。在网络中经常使用重传处理差错。

每个帧包括一个帧头（Header），一个有效载荷（用于存放数据）以及一个帧尾。

数据链路层，可以提供三种可能的服务（就是第一章中提到的有/无连接、可靠/不可靠服务）：

无确认的无连接服务。

有确认的无连接服务。

有确认的有连接服务。

显然，一般来说不存在无确认的有连接服务，因为无确认直接违背可靠传输的基本原则。没有确认帧，发送方无法得知数据是否正确接收，也无法进行重传或纠错。因此，无确认的有连接服务无法提供可靠性，不符合数据链路层提供可靠服务的目标，也就不存在无确认的有连接服务。

无确认的无连接服务 Unacknowledged connectionless service

Frame is sent with no connection / error recovery

例：Ethernet 无确认

差错率较低，差错交给上层处理；实时应用

有确认的无连接服务 Acknowledged connectionless service

如果需要，帧将与重传一起发送 Frame is sent with retransmissions if needed

例：802.11 一帧一确认

不可靠、较短延迟信道

有确认的有连接服务 Acknowledged connectionless service

卫星信道或长途电话电路；流水发送+批量捎带确认

不可靠、较长延迟信道

面向连接的实现机制

面向连接分为三个阶段：建立连接；使用连接传输数据；释放连接。

连接一般是一个逻辑概念，所以也成为逻辑链接。保持数据的顺序性是面向连接的一个重要特征。

建立连接：通信双方初始化各种变量和计数器。发送方包括用于缓存已经发送但是没有收到确认的帧的缓冲区，管理缓冲区的指针，重传定时器等；接收方包括用于缓存接收帧的缓冲区，已经提交帧的标号等。

传输数据：使用各种变量和计数器传递数据。

释放连接：通信双方释放使用的各种变量和计数器。

3.1.2 成帧

成帧（位填充、字节填充）

成帧的主要工作是将每一段来自上层的数据封装起来，使得数据链路层的接收方实体能够正确识别一个帧的开始和结束（能够确定帧的边界），并能依据帧中携带的各种控制字段（额外添加的协议字段）判断所接收帧的正确性（是否在传输过程中出错、是否是想要的那一帧）。

确定帧的边界有一些基本的要求：容易识别一个帧的开始和结束（出错时容易同步）；开销尽可能少。

字节计数法 Byte count

利用头部中的一个字段来标识该帧中的字符数。当目的节点的数据链路层收到字节计数值时就知道后面跟随的字节数，从而可以确定帧结束的位置。

这种方法比较简单，知道字符数就知道该帧在何时结束

但是计数值出错之后，接收方就找不到下一帧正确的起始位置，很难重新同步

错误之后无法要求重传（接收方不知道从哪里开始错误）

这种方法很少被使用

问题：如果计数字段出错，即失去了帧边界划分的依据，接收方就无法判断所传输帧的结束位和下一帧的开始位，收发双方将失去同步，从而造成灾难性的后果。

字节填充的标志字节法 Byte stuffing

使用一些特定的字符来界定一帧的开始与结束。发送方的数据链路层在数据中“偶尔”出现的每个标识字节的前面插入一个特殊的转义字节（ESC）

接收方的数据链路层在将数据传递给网络层之前必须删除转义字节，这种技术成为字节填充。

这种方法更长，但更容易在错误后重新同步

比特填充的标志比特法 Bit stuffing

使用一个特定的比特模式，即01111110来标志一帧的开始和结束。

为了不使信息位中出现比特流01111110被误判为帧的首尾标志，发送方的数据链路层在信息位中遇到5个连续的1时，将自动在其后插入一个0；而接收方做该过程的逆操作，即收到5个连续的1时，则自动删除后面紧跟的0，以恢复原信息。

问题：采用比特填充和字节填充两种方法时，一帧的长度要取决于它所携带的数据内容。

物理层编码违例法（曼彻斯特编码）

物理层编码中有一些编码形式（Code）不会出现在常规数据中（编码违禁）

使用编码违禁来区分帧的边界

例如：4B/5B编码中有25-24=16个编码在数据编码中不会被使用

这些分界符是保留不用的，可以用来区分帧的边界，不需要填充

3.1.3 差错控制

差错控制可以修复接收到的有错误的帧

差错控制需要在接收端识别出错误，发送端收到接收端的反馈的控制帧对所接收到的帧进行肯定或否定的确认，重传有错误的帧。

硬件故障导致帧丢失，发送端可能永远无法得到反馈

解决方法：发送方发送一帧时，启动计时器，计时器超时，重传该帧。

给发出的帧分配序号，接收方根据序号区分原始帧和重传帧

3.1.4 流量控制

流量控制的设计问题是发送方发送帧的速度超过接收方接收的速度，发送方应该如何处理。

基于反馈的流量控制（隐式，非明确指明）（feedback-based flow control）

接收方给发送方返回信息，允许发送更多数据（隐式，非明确指明）

基于反馈的较为常见（链路层和更高层次）

基于速率的流量控制（显示，明确指明）（rate-based flow control）

协议的内置机制来限制发送方传输数据的速率（显式，明确指明）

仅在传输层的一部分可见

网络接口卡（NIC，Network Interface）能以‘线速’运行

能以帧到达的速度处理帧

基于速率的流量控制通过显示限制发送方的发送速率实现。具体见传输层拥塞控制慢启动方案。

基于反馈的流量控制机制：

流量控制的本质是发送方发送的速率应该与接收方的接收速率相匹配。

首先是接收方，一般有一个或多个缓存帧的缓冲区来接收数据帧，处理程序处理缓冲区里面的帧，这样可以避免边接收边处理造成的数据丢失。

即使有缓冲区缓存数据，当发送方的速率长时间超过接收方的速率时，缓冲区会满，从而造成数据丢失。

最终方案：双方的通信速率应该由接收方决定,即基于反馈的流量控制方案。本章将确认作为反馈信号。

高效性

流水发送：为了避免一帧传递完后再传递下一帧带来的线路带宽的浪费，尤其是在线路较长时，发送方可以流水发送多帧。这需要发送方有多个缓冲区来缓存已经发送还没有收到确认的帧（没有传输完成的帧）。

捎带确认：为了避免单独的确认帧浪费资源，将确认使用接收方发送的数据帧携带。这要求双工通信。

批量确认：在流水场景中，接收方收到多个帧时返回一个确认，从而减少确认帧的个数。尽最大可能不触发已正确接收帧的重传。

3.2 差错检测和纠正

错误检测和纠正（CRC）

校验和checksum：通信双方为了对传输的数据进行检错和纠错而根据一定的规则添加的额外的位（组合）

在数据链路层，接收方实体需要判断接收的帧是否在传输过程中出现了错误。如果没有传输错误，则将帧中包含的分组提交给网络层。否则，需要发送方重传这一帧。

帧的数据取值可能没有任何特征，这时需要添加额外的位来凑出某种或某几种特征，通过检验特征是否存在来判断数据传输是否正确。

最简单的检验和是奇偶检验。

在数据之外增加一位，这一位的目的就是将原有数据加上增加的这一位具有某种明显的特征。如“数据+校验位”中“1”的个数是奇数个（偶数个）。

发送方发送帧时，根据原来数据中1的个数决定校验位的取值。

以1位偶校验为例。“数据+校验和”中“1”的个数为偶数个。这就是约定的特征。

接收方收到帧后，检查“数据+校验和”中“1”的个数是否为偶数个。是，则认为帧传递正确。不是，则认为传输过程出现了错误，需要重传。

校验和的开销体现在额外增加的位的多少、位的位置和校验位生成和检查的算法的复杂性。校验位的多少影响线路使用的效率，校验算法的复杂性影响数据发送和接收的处理速率。总的来说，会影响真正数据传输的速率（或传输线路的利用率）。

校验和的复杂性需要平衡“校验通过则数据传输正确”的支持和开销两个方面的因素。

如果让“校验通过则数据传输正确”这个结论100%正确，需要的开销可能很大。一般支持这个结论到一个可以接受的置信度就可。

几个相关概念和工作机制：

重传：当某一帧在传输过程中出现错误时，网络中常用的处理方法是发送方重传这一帧，而不是接收方使用纠错算法纠正错误。

重传对发送方有资源要求，即保存自己所发送过的帧，需要时重新发送一次。只有当一帧被接收方正确接收并将帧中分组提交给网络层后，才认为这一帧的传递任务结束，才能清空保存这一帧的缓冲区。

一个分布式协议观点：通信双方组成一个分布式系统，只有当双方都认为一帧传递正确后，协议才认为这一帧的传递结束。校验和只是让接收方判断是否接收正确。

确认：接收方对自己所接收正确的帧回复一个确认，使得接收方也能知道这一帧已经被正确传输。

有了确认机制后，发送方如果收到一帧的确认，则认为这一帧已经被正确传递，并且接收方也这样认为（否则不会发回确认），这一帧的传递结束。清空这一帧所使用的资源。

如果发送方没有收到一帧的确认，则需要重传这一帧。

重传定时器：为了避免发送方长时间地等待确认，根据线路延迟等要素估计一个确认能够返回的时间，设置为重传定时器。当等待时间超过这个时间时，则认为确认无法回来，重发这一帧。

在定时器超时时一帧的确认没有回来，发送方只能认为接收方没有发回确认，也只能推断接收方没有收到正确的这一帧。所以选择重传这一帧。

但是，情况并不完全是这样。确认没有回来有可能是确认在传输过程中出错丢失了。重传会造成接收方收到重复的帧。（这是由于分布式系统中每个实体只能使用局部的部分的信息做出判断和操作）。

编号：为每个传递的帧确定一个编号，从而区别不同的帧。

当接收方收到一个已经接收过的编号的帧时，则认为是重复帧，直接丢弃这一帧，但要回复一个这一帧的确认（因为接收方在等待这一帧的确认）。

3.2.1 纠错码（海明码/汉明码）

（n，m）码，一个长为n的帧，包含m个数据位，r个校验位

r=n-m; 线性码中校验位是数据位的线性函数计算得到（常用异或=模2加法）

n位码字（codeword），码率=m/n

海明距离（Hamming distance)

两个codeword中不同的位的个数称为海明距离

一个编码方式的海明距离是两个合法编码之间最小的海明距离

检测d个错误需要d+1的海明距离，纠正d个错误需要2d+1的海明距离

海明码设计

海明码可以纠正1位的错误

每个合法的消息对应n个单个错误的码字，（n+1）2m<=2n

海明码需要的校验位r的计算（m+r+1）<=2r，例：如果m=7，r=4

校验位在2^k(k=0,1,2,..,r-1)

将数据的位置转化成二进制码。例如，1->1, 2->10, 3->11, 4->100,…,

校验位1（20）覆盖所有数据位置序号的二进制码最后一位是1的数据，例如，1（1），11（3），101（5），111（7），1001(9)，1011(11)

校验位2（21）覆盖所有数据位置需要的二进制码倒数第二位是1的数据，例如，10(2), 11(3), 110(6), 111(7), 1010(10), 1011(11)

以此类推（4=22，8=23，16=24。。。），若采用偶校验，则校验位所控制的数据位的和是偶数，校验位为0，奇数为1（等同于异或和模2加法）

海明码

配奇原则

1的个数为偶数：1，奇数：0

3.2.2 检错码

奇偶检错码

奇偶（parity）检验是在数据末尾添加表示奇（1）偶（0）的检验位

偶校验：所有数据位相加模2，相当于异或

例如： 1110000->11100001

当数据位的和与奇偶校验位不相符，表明出现了错误

可以检测奇数个错误

Ex: 1 error, 11100101; detected, sum is wrong

Ex: 3 errors, 11011001; detected sum is wrong

Ex: 2 errors, 11101101; not detected, sum is right!

Error can also be in the parity bit itself

Random errors are detected with probability ½

交错（interleaving）校验可以检测突发连续错误（burst）

循环冗余码 CRC

基本思想：把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x) ，将所除得余式R(x)的系数附加在报文码之后发出；接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。

实现：用简单的移位寄存器电路即可。

每年都考，必会，简单！

G(x)为r次的生成多项式，k个信息码元的码多项式为f(x)，n=k+r

3.3 基本数据链路层协议 Elementary Data Link Protocols

基本数据链路协议（停等协议）

3.3.1 Link layer environment (数据链路层环境)

数据链路层一般在网络接口卡和操作系统驱动部分实现；网络层（IP）的实现一般是操作系统软件

网络层、数据链路层和物理层都是独立的进程

硬件实现：

物理层的功能实现驻留在网络接口卡中，主要功能包括按照一定速率将数据转换为信号发送出去和将接收到的信号转换为数据。

数据链路层的功能实现部分分布在网卡中，部分分布在操作系统中。网卡中的数据链路层功能主要包括对发送的数据生成校验和，对接收的数据检查校验和。

网卡上发送和接收的数据都存放在一个缓冲区中，由网卡上的物理层和数据链路层进程使用。

软件实现：

数据链路层的部分功能（本章关心的协议内容）在操作系统中实现，主要包括可靠性和高效性所涉及的各种功能。如重传、确认、编号、流量控制、流水等。

网络层的功能也在操作系统中实现。

操作系统中发送和接收的数据都存放在操作系统管理的缓冲区中，由位于操作系统中的数据链路层和网络层进程使用。

应用层有单独的缓冲区。数据需要在应用层缓冲区和操作系统缓冲区交换数据。

将网卡上实现的功能并列在一起，统称为物理层。

将位于操作系统中的这一部分数据链路层功能称为数据链路层。这是我们学习的重点，我们关心这一部分功能的协议实现。

所以，数据链路层协议不再关心校验和的生成和检查的具体实现。而是使用一种事件方式提供网卡操作的结果。当发送数据时，我们简单的发给物理层即可。接收数据时，可能有两个可能的结果，即收到一个通过校验的帧（from_physical_layer），或收到一个没有通过校验的帧（cksum_err）。

Group	Library Function	Description
Network layer	from_network_layer(&packet) to_network_layer(&packet) enable_network_layer() disable_network_layer()	从网络层获得一个将要发送的数据包把一个刚接收到的数据包传给网络层允许网络层工作（产生“ready”事件）阻止网络层产生“ready”事件
Physical layer	from_physical_layer(&frame) to_physical_layer(&frame)	从物理层接收一帧数据把一帧发送数据传递给物理层
Events & timers	wait_for_event(&event) start_timer(seq_nr) stop_timer(seq_nr) start_ack_timer() stop_ack_timer()	等待一个事件（数据包/帧到达、计时事件）对帧（seq_nr）开始(重置)一个倒计时timer 停止帧（seq_nr）的倒计时timer 开始（或重置）ACK 的倒计时 timer 停止ACK的倒计时 timer

3.3.2 Utopian Simplex Protocol （乌托邦单工协议）

假设没有错误，接收方和发送方一样快，考虑单向数据传输

无约束单工协议

工作在理想情况，几个前提：

单工传输

发送方无休止工作（要发送的信息无限多）

接收方无休止工作（缓冲区无限大）

通信线路（信道）不损坏或丢失信息帧

工作过程

发送程序:取数据，构成帧，发送帧；

接收程序：等待，接收帧，送数据给高层

3.3.3 Stop-and-Wait Protocol for Error-free channel （无错误信道的停-等单工协议）

确保发送方不能超过接收方：

接收器在准备就绪时返回一个dummy frame（哑帧ack）

所谓的dummy帧就像EVA中的Dummy Plug一样，只是用来告诉sender可以发送下一个帧了，不需要做任何事情。

一次只输出一帧，称为stop and wait

我们添加了流控制

单工停等协议（A Simplex Stop-and-Wait Protocol）

增加约束条件：接收方不能无休止接收。

解决办法：接收方每收到一个帧后，给发送方回送一个响应。

工作过程

发送程序：取数据，成帧，发送帧，等待响应帧；

接收程序：等待，接收帧，送数据给高层，回送响应帧。

3.3.4 Stop-and-Wait Protocol for Noisy channel （有噪声信道的单工停-等协议）

增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。

解决办法：出错重传。

带来的问题：

什么时候重传 —— 定时

响应帧损坏怎么办（重复帧）—— 发送帧头中放入序号

为了使帧头精简，序号取多少位 —— 1位

发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（Positive Acknowledgement with Retransmission）或ARQ（Automatic Repeat reQuest）

该协议增加了一个计时器，发送方发出一帧，接收方只有在正确接收到数据之后才返回一个确认帧。如果到达接收方的是一个已经损坏的帧则将它丢弃，经过一段时间后发送方将超时，于是它再次发送该帧。这个过程将不断重复，直至该帧完好无损地到达接收方。

发送方在它所发送的每个帧的头部放上一个序号，然后，接收方可以检查它所接收到的序号，由此判断这个帧是新帧还是应该被丢弃的重复帧。

如果到达了一个有效确认帧，则发送方从它的网络层获取下一个数据包，并把它放入缓冲区覆盖掉原来的包，同时他还会递增帧的序号。如果到达了一个受损的确认帧，或者计时器超时，则缓冲区和序号都不作任何改变，以便重传原来的帧。

当一个有效帧到达接收方时，接收方首先检查它的序号，确定是否为重复数据包。如果不是，则接收该数据包并将它传递至网络层，然后生成一个确认帧。重复帧和受损帧都不会被传递给网络层，但它们的到来会导致最后一个正确接收到的数据帧的确认被重复发送，返回给发送方，以便发送方做出前进到下一帧或重发那个受损帧的决策。

这个协议能够实现重传，是因为：

如果拿到正确帧，相安无事

如果拿到校验和错误，啥也干不了，等超时

如果拿到超时（或者说上一种情况的超时），最终会自动超时重传

停-等协议的问题在于：只能有一个没有被ACK的帧在发送中，这样会导致发送方的带宽利用率很低。

为什么buffer不是越大越好？答案是，大buffer会带来更高的延迟。

3.4 滑动窗口协议

滑动窗口协议工作原理：

发送窗口、接收窗口

发送端

滑动窗口中的窗口指的是协议关心的内容，滑动指的是关心的内容在不断变化。

发送的信息帧都有一个序号，从0到某个最大值，0 ~ - 1，一般用n个二进制位表示0；

发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小 = 上界 - 下界，大小可变；

发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；

接收端

接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示能够接收的序号最大的帧，下界表示希望接收的帧。

接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应（确认）帧，上界、下界都加1。接收窗口大小不变。

一个基本要求：数据链路层协议必须按照发送的顺序递交所有的帧给网络层。

滑动窗口协议具体实现说明：

滑动窗口协议的实现本质上是一组针对缓冲区管理的协议。发送方和接收方都有一个（组）用于发送的和接收的缓冲区。发送缓冲区里面存放的是已经发送但没有收到确认的帧；接收缓冲区用于存放能够接收的帧。

发送窗口尺寸大小对应着发送缓冲区的使用情况，接收窗口尺寸大小对应着能够用于接收的缓冲区的个数。

发送窗口尺寸大小可以为0—MAX（MAX为能够使用的发送缓冲区的最大个数）；接收窗口尺寸大小固定。

发送缓冲区和接收缓冲区都组织成循环队列。

缓冲区的大小和帧所使用的编号（位数）没有直接关系。（一般缓冲区<最大编号）

捎带确认

捎带确认带来的复杂性：

捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。也就是说将下一个数据帧的 ack 设置为上一帧的 ack，有效利用 ack 的位置。优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断；带来的问题：复杂。

如果是双工通信，则每台机器都维护一个发送窗口和接收窗口反应当前的发送情况和接收情况。一台机器的发送窗口和对方机器的接收窗口逻辑上是一个方向的通信。

当一台机器有数据要发送时，帧中除了携带本次发送数据的编号、数据以外（与发送窗口有关），还需要携带本机作为接收方接收对方数据的情况（确认已接收的帧，捎带确认，与接收窗口有关）

当接收方没有及时的返回数据，对已经接收的数据帧的确认不能及时返回，可能会造成数据帧的超时重传。解决方案是设定一个确认定时器（ack_timer），当收到第一帧时启动确认定时器，如果在确认定时器超时时依然没有返回的数据帧，则产生返回一个单独的确认帧。

确认定时器的设定规则是保证最早接收的帧的确认能够在其重传定时器超时之前返回。

多个缓冲区（窗口尺寸大于1）协议机制

当有多个发送缓冲区时（发送窗口尺寸大于1）支持流水发送，即可以在没有收到确认的情况下连续发送多帧，这些帧保存在缓冲区中，每帧对应一个重传定时器。

捎带确认可能一次确认多个帧，此时发送窗口下沿连续滑动，直到第一个没有收到确认的帧；发送缓冲区将收到确认的帧所在的缓冲区清空（具体实现时可以被新的数据覆盖）。

当有多个接收缓冲区时（接收窗口尺寸大于1）支持乱序接收，即当前期望的帧没有到来（由于噪声出错）时，可以接收后面到来的传输正确的帧，放到相应的接收缓冲区内。但是，此时不能向网络层递交（按序要求）。当期望接收的帧到达后一起递交。

如果当前期望的帧没有到来，则启动否定确认机制，及时索要此帧，避免后面正确接收的帧触发超时重传。

滑动窗口协议概念

发送端维护的窗口内是它发送出但还未被确认的帧

Needs to buffer them for possible retransmission

Window advances with next acknowledgements

接收端维护的窗口内是它（预期）将要接收的帧

Needs to keep buffer space for arrivals

Window advances with in-order arrivals

更大的窗口可以实现管道化（pipelining）的数据传输从而提高链接的效率

Stop-and-wait (w=1) is inefficient for long links

Best window (w) depends on bandwidth-delay (BD)

Want w ≥ 2BD+1 to ensure high link utilization

BD（单向信道可以同时容纳帧的数量：带宽*传输时间/一帧的比特数），“1”要完整接收一个帧之后才会发送确认帧）

管道化的数据传输需要不同的错误/缓存机制的选择

We will consider Go-Back-N（回退N） and Selective Repeat（选择性重传）

3.4.1 一位滑动窗口协议

一位滑动窗口协议

发送窗口大小为1，1个发送缓冲区
接收窗口大小为1，1个接收缓冲区

Transfers data in both directions with stop-and-wait （窗口大小为1）

Piggybacks 把确认信息捎带在acks on reverse data frames for efficiency

（捎带确认）

需要解决传输错误，流量控制 early timers

在发送方和接收方前进的滑动窗口
Ex：窗口大小为1，序列号为3位。 — 在发送方和接收方前进的滑动窗口 Ex：窗口大小为1，序列号为3位。

一位滑动窗口协议的两种情况:

Simultaneous start [right] causes correct but slow operation compared to normal [left] due to duplicate transmissions.

左侧过程：

A 发送（0,1，A0），0 是 seq 的初始值，1 是对前一帧的 ack（或者初始值），A0 为数据，B 接收到后发送（0,0，B0），0 是 B 的 seq 的初始值，第二个 0 表示对 A0 的 seq=0 的 ack，B0 是数据，如此往复。

右侧过程：

A 和 B 都试图发送，A 先发送（0,1，A0），B 发送（0,1，B0）二者 seq 以及 ack 都应该是初始值，B 接收到后发现 A 的 ack=1，与自己发的（0,1，B0）的 seq 不一样，重传（0,0，B0），表示收到了 seq=0 的 A0，同样 A 也会重传（0,0，A0）表示收到了 seq=0 的 B0，也就是说，最终的结果相当于消息体 A0、B0 与 ack 消息被分开传输了。