[网络协议]计算机网络——数据链路层

引言

??我们先来回顾一下计算机网络的结构，计算机网络的设计目的是在不可靠物理链路实现两台相邻机器之间可靠、有效的通信。

• 可靠不是通过通信手段保证可靠，而是在允许通讯出错的情况下解决插错问题。

??在上一章我们介绍了物理层，那么在数据链路层，我们提出如下问题：

• 数据链路层将数据组合成数据块进行传输，这种数据块称为帧(frame)，帧是数据链路层的传送单位，那么如何将数据组合成数据块呢？
• 如何控制帧在物理信道上的传输，包括如何处理传输插错，如何调节发送速率以使接收方想匹配，如何在两个网络实体之间提供数据链路通路的建立、维持和释放的管理？

??计算机网络中有两种链路：

• 点对点

• 广播

数据链路层的设计问题

• 问题1：连接还是无连接？
• 问题2：如何进行分帧？
• 问题3：发送方和接收方能力不对等怎么办？
• 问题4：如何处理差错？

提供网络层服务

• 问题1：连接还是无连接？

??计算机网络最主要的服务就是将数据从源机器的网络层传输到目标机器的网络层。在源机器的网络层有一个实体(称为进程)，它将一些比特交付给数据链路层，要求传输到目标机器。数据链路层的任务就是将这些比特传输给目标机器，然后再进一步交付给网络层。
??因此，数据链路层可以设计成向上提供各种不同的服务。实际提供的服务因具体协议的不同而有所差异。一般情况下，数据链路层通常会提供以下三种可能的服务：

• 无确认连接服务(LAN)：源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。
• 有确认无连接服务(WLAN)：当向网络层提供服务时，数据链路层仍然没有使用逻辑连接，但是其发送的每一帧都需要单独确认。这样，发送方可以知道一个帧是否已经正确地到达目的地。如果一个帧在指定时间间隔内还没有到达，则发送方将再次发送该帧。这类服务适用于不可靠信道。
• 有确认面向连接服务(Point-to-Point link)：这种是数据链路层最为复杂的服务。源机器和目标机器在传输任何数据之前要建立一个连接。连接上发送的每一帧数据都要被编号，数据链路层确保发出的每一帧都被接收方收到。它还保证每个帧只会被接收一次，并且所有的帧都将按照正确的顺序被接收。因此，面向连接服务相当于为网络层提供了一个可靠的比特流。它适用于长距离且不可靠的链路，比如微信通信或者长途电话电路。

成帧

• 问题2：如何进行分帧？

??为什么要成帧呢？数据链路层需要处理传输错误，调节数据流的快慢。为了达到处理传输错误的目的，数据链路层将数据流分成帧并且计算每一帧的校验和，接收方对校验和进行检验，在发现有数据传送错误时，只需要将有差错的帧再次进行传送即可，而不需要将全部数据的比特流进行重传，这将会大大提高传送效率；不仅如此，封装成帧还可以根据发送接收双方的能力调节数据流的快慢，当接收方速度过慢时，数据链路层可以停止发送下一帧并保持数据的完整性。

??那么，我们要如何确定一帧的开始和结束分界呢？

字节计数法

??字节计数法就是利用帧头部的一个字段来标识该帧中的字符数。

• 特点
  • 帧不定长
  • 用帧头的一个控制字符区分帧的首位
  • 按照控制字符说明帧的长度，确定帧的边界
• 问题
  • 控制字符的数值错误造成发送与接收不同步
    

字节填充的标志字节法

??用一些特殊字节（FLAG）作为帧开始和结束标志，用转义字符（ESC）来区分二进制数据中存在的特殊字节。

接收方

比特填充的标志比特法

??这是一种面向二进制位的帧格式，把所有需传输的数据以比特位一字排开，并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志前一个帧的结束）

??当帧内容中出现一个与帧标志相同的位串01111110，则在5个1后插入一个0，即变成01111101，接收方将自动删除第5 个1后的0。这称为位填充法（零比特填充法），也称为透明传输。

??如果由于干扰，一个帧没有正确接收，则可扫描接收串，一旦扫描到01111110，即新的一帧从此开始。即可以再同步

??比特填充的标记比特法，可以传输任意比特数的帧了，同时，它的传输效率也比 字节填充的标记字节法要高。

练习

数据链路协议使用了下面的字符编码：

A:0100 0111
B:1110 0011
FLAG:0111 1110
ESC:1110 0000

为了传输一个包含4个字符的帧：A B ESC FLAG，试问使用下面的成帧方法时所发送的比特序列（用二进制表达）是什么？

1. 字节计数
2. 字节填充的标志字节
3. 比特填充的首位标志字节

• 字节计数
  0000 0100(4) 0100 0111(A) 1110 0011(B) 1110 0000(ESC) 0111 1110(FLAG)\
• 字节填充的标志字节
  • FLAG：起始、结束标志
  • ESC：转义
    0111 1110(FLAG) 0100 0111(A) 1110 0011(B) 1110 0000(ESC) 1110 0000(ESC) 1110 0000(ESC) 0111 1110(FLAG) 0111 1110(FLAG)
• 比特填充的首位标志字节

0111 1110(FLAG) 0100 0111(A) 11010 0011(B) 11010 0000(ESC) 0111 11010(FLAG) 0111 1110(FLAG)

流量控制

• 问题3：发送方和接收方能力不对等怎么办？

• 解决方案：

  • 基于反馈的流量控制：接收方给发送方反馈信息
  • 基于速率的流量控制：限定发送者的速率

差错控制

• 问题4：如何处理差错？

• 什么是错误？

  • 发送方：按一定顺序发送一定数量的帧
  • 接收方：可能会认为
    • 数据出错
    • 帧丢失
    • 帧乱序

• 差错控制需要解决的问题：

  • 找出差错并改正
  • 保证接收方不丢帧、不乱序的收到正确帧

• 差错处理方法：

  • 差错纠正
    • 根据冗余信息纠正
    • example:
      • data : 0
      • Send code: 00000
      • Receive code: 00011
      • Corrent: 00000
  • 差错检测/重传
    • 通常策略：加入冗余信息

差错检测和纠正

• 差错
  • 随机差错：具有独立性，与前后码元无关
  • 突发差错：相邻多个数据位出错
• 差错产生的原因
  • 通信信道的噪声引起差错：
    • 热噪声：由于传输介质导体的电子热运动产生。振幅较小，是产生随机差错的主要原因。
    • 冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。

??冲击噪声是引起差错的主要原因。
??为了能够判断传送的信息数据是否有错误，在传送时增加必要的附加判断数据；在不发生误码的情况之下，附加判断数据是完全多余的，但是如果发生误码，即可利用信息数据与附加数据之间的特定关系来实现检错和纠错。即，为了使数据码具有检错和纠错能力，应当按照一定的规则在数据码的基础上增加一些冗余码(又称为监督码)。

冗余码分为两种：

• 纠错码：接收者可以推断出哪些Bits出错了
• 检错码：接收者只是推断出错了，但是不知道错误在哪。

一些概念

• 码字
• 海明距离
• 检错能力
• 纠错能力

码字

• 码字：由若干代码组成的一个字，如0110011
• 距离：两个码字之间不同的代码个数
• 码距：一种码制中任意两个码字间距离的最小值

海明距离

??两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。对于一种编码集，在这个码字的集合中，可以得到所有的任意两个码字的海明距离，其中最小的海明距离称为该编码集的海明距离d。

??计算两个码字之间的海明距离的方法是对这两个码字进行异或运算，结果有a个1，则海明距离为a。

??这里海明距离为3.

检错能力

定理1： $如果d\ge e+1，则该编码可以检测出任何e个或e个以下的错误。$

解释： 对于一种编码集，在这个码字的集合中，可以得到所有的任意两个码字的海明距离，其中最小的海明距离称为该编码集的海明距离d。如果出现的错误为e + 1位，那么直接认定它为编码集的其它编码而非检测出错，故海明距离为e + 1的检错编码，只能检测出e位数据错误。

纠错能力

• 纠错码的功能：在接收方发现并纠正错误的数据帧
  定理2： $如果d\ge 2t+1，则该编码可纠正任何t个或t个以下的错误。$

??如果一个码字有t位发生差错，它仍然距离原来的码字距离最近，可以直接恢复为该码。
??比如收到一段码为 U ， 和 A 这个合法码有3位不同，和 B 这个合法码有4位不同，那么U会被纠正成为 A 。基于这个背景 发送端 发送了一段码为 A ，由于错误里面的 t 位被反转，也就是犯了 t个错，距离为t， 导致接收端收到了的码为 B，任意另外一个合法的码为 C
A ------t------- B -------y---------C
??B 要能正确被还原成A， 那就要求 B 离 A更加接近，也就是 距离 t<y, 两个合法码之间的距离为 t + y， 可以得出 t+y > 2t , 由于码是01离散的 > 2t 就意味着 从 (2t+1) 起步。
??一般情况下，冗余位越多，检错纠错能力越强。但相应的编码效率也越低，成本越高。

CRC

参考文章：CRC校验码

• CRC的检错能力
  • 能检查出所有单bit的错误
  • 能检查出全部离散的2bit错误
  • 能检查出全部奇数个错误
  • 能检查出全部长度小于或者等于K为的突发错误（K是生成多项式的阶）

基本数据链路层协议

• 数据链路协议主要考虑的问题：
  • 避免所传送的数据可能出现差错和丢失。
  • 使发送方发送数据的速率适应接收方的接收能力。
    

??由于计算机网络中各个层次之间相互独立，因此我们在设计数据链路层协议时，排除那些与数据链路层无关的工作，总是基于以下假设：

• 点到点的链路中所有的结点都不会崩溃。
• 物理层、数据链路层和网络层都是独立的进程
• 数据链路层使用数据帧，网络层使用分组
• 数据链路层只处理信道上的事务
• A发送一个长的数据流给B，使用可靠的面向连接的服务。
• 三个事件：
  • wait_for_event: 空闲时等待
  • cksum_err: 校验和出错
  • frame_arrival: 帧正确到达
• 数据结构如下：

typedef struct frame
{
	frame_kind kind;		// 帧类型
	seq_nr seq;				// 序号
	seqnr ack;				// 确认序号
	packet info;			// 网络层的包
};

一个乌托邦式的单工协议

??该协议基于以下假设：

• 数据单向传输
• 接收方数据处理能力无限
  • 无限的缓冲区
  • 不需要流量控制
• 信道不会出现错误
  • 真不会损坏和丢失
  • 不需要差错控制
    

数据链路交换规则(Protocol1)

• sender

void sender1()
{
	frame s;			// 要从缓冲区发出去的帧
	packet buffer;		//  要从缓冲区发出去的包
	while(true)
	[
		from_network_layer(&buffer);		//接收从网络层来的包
		s.info = buffer;					// 将包放入帧中
		to_physical_layer(&s);				// 将帧发给物理层
	}
}

• receiver

void receiver1()
{
	frame r;		// 要接收到缓冲区的帧
	event_type event;		// 事件的类型
	while(true)
	{
		wait_for_event(&event);		// 等待事件
// 这里的wait_for_event函数接收到的只有frame_arrival才会继续进行，否则会进行错误处理，具体操作和我们要讲的协议无关，不再赘述。
		from_physical_layer(&r);	// 从物理层接收到帧
		to_network_layer(&r.info);	// 将帧发送给网络层
	}
	// 这里的wait_for_event函数接收到的只有frame_arrival才会继续进行，否则会进行错误处理，具体操作和我们要讲的协议无关，不再赘述。
}

无错信道上的单工停-等协议(Protocol2)

??很显然，这样的乌托邦协议在实际应用中根本不现实，那么我们进一步放宽假设：

• 数据单向传输
• 接收方数据处理能力有限
  • 有限的缓冲区
  • 需要流量控制
• 信道不会出错
  • 帧不会损坏和丢失
  • 不需要差错控制

??该协议和乌托邦协议的区别在于接收方数据处理能力有限，因此我们可以进行流量控制，通过接收方的反馈机制限制发送方的数据发送流量，使其适应接收方的处理速度。即发送方在收到接收方反馈信息之前停止发送。

??我们将两种情况进行一个对比。

数据链路交换规则(Protocol2)

• sender

• sender

void sender2()
{
	frame s;
	packet buffer;
	event_type;
	while(true)
	{
		from_network_layer(&buffer);
		s.info() = buffer;
		to_physical_layer(&s);
		wait_for_event(&event);		// 收到接收方的反馈
	}
}

• receiver

void receiver2()
{
	frame r;
	event_type event;
	while(true)
	{
		wait_for_event(&event);
		from_physical_layer(&r);
		to_network_layer(&r.info);
		return_ack();	// 发送反馈
	}
}

有错信道上的单工停-等式协议

??无措的信道上的单工停-等式协议显然也不能满足我们的需求，因为信道不可靠，因此我们再放宽一下假设：

• 数据单向传输
• 接收方数据处理能力有限
  • 有限的缓冲区
  • 需要流量控制
• 信道会出错
  • 帧会损坏和丢失
  • 需要差错控制

差错控制

??差错控制，即帧不出错、帧不丢失、帧不乱序。

正常传输

数据帧被破坏

??数据帧出错的话，可以发送否认帧NAK请求发送方重新发送。

??那么是否可以不发送NAK呢？答案是可以，事实上可以不发任何应答信号，但是在这里，我们讨论初步的处理方法，直接回送NAK。

数据帧丢失

• 死锁现象：当出现帧丢失时，发送端将永远等待下去。
  ??如果我们在设计协议时不考虑帧丢失的话，那么接收方收不到帧，也就不会给发送方发送一个反馈，发送方接不到反馈，就不会发出下一帧，出现死锁现象。因此要对数据帧进行处理。
  ??我们的处理办法是设置一个超时处理(timeout)，当发送方在timeout时间内接收不到接收方的反馈信息时，将会重新发送帧。只有收到了接收方的肯定确认时才会发送下一帧，有了这个处理，上面所讨论的NAK不发送也可以。

• 两个协议：

  • PAR(Positive Acknowledgement with Retransmission，支持重传的肯定确认协议)
  • ARQ(Automatic Repeat reQuest，自动重复请求协议)

超时时间间隔：

• 太长：
  • 如果帧丢失，原先数据帧的重传会等待很长时间才能重新发送，浪费信道带宽。
• 太短：
  • 发送方会发送一些不必要的真，造成不必要的浪费，还可能分不清确认哪一帧。

??经过实际验证，将timeout设置为稍大于2t+的处理时间（t为传输时间）
??那么如果出现了下面的情况，确认帧丢失，发送方按照超时 重传的方法，接收端将受到重复帧，导致帧乱序，如何解决？

解决方案： 把每个帧进行编号，通过序号区分新的帧和旧的帧。

• 将发出的帧编号：
  • 重复帧：帧序号不变
  • 新帧：帧序号改变(+1)
• 变量：next_frame_to_send
• 在传输一个帧之后开启计时器，在规定的事件内未收到对方的确认帧，则重新发送该帧，重复重传过程，直到收到确认帧。
• 变量：frame_expected
  • 定义帧序列号的期望，检查帧有无差错
    • 正确：继续
    • 错误：发否认帧，继续等待接收
  • 根据接收帧的序列号，检查它是否是期待的帧：
    • 是：上交网络层
    • 不是：抛弃
• 等待事件：
  • cksum_err: 丢弃？
  • frame_arrive: 发送一个新的帧
  • Timeout: 重传帧

序号的比特数

??任何一个编号系统的序号所占用的比特数一定是有限的，因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。

??序号位的多少取决于是否能够确保接收端不会出现接收重复帧即可。混淆帧只出现在两个相邻帧之间，只需要两个序号，即1bit。

??对于ARQ协议，发送序号有0和1即可，每发送一个新的数据帧，发送序号就和上次发送的不一样，重发的数据帧发送序号不变。

if(Ns == R)
	接收
else
	丢弃

• S - 发送端本地状态序号
• R - 接收端本地状态序号
• Ns - 发送端附加到数据帧上的序号

数据链路交换规则(Protocol3)

• sender
  
• receiver
  

错误控制

$$\begin{gathered} 设：单程传输时延为T_d，数据帧发送时间为T_f,数据传输率为C，数据帧长度为L \\ 信道利用率C_r=\frac{总时间?等待时间}{传输一帧的总时间} \\ 忽略应答帧长度和处理时间 \\ {C}_r\approx \frac{T_f}{T_f+2T_d}=\frac{1}{1+2T_d\frac{C}{L}} \\ 数据帧L越短，信道利用率越低。 \end{gathered}$$

停止等待协议ARQ的优缺点

• 优点：比较简单
• 缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。
  &ems;?为了克服这一缺点，就产生了另外两种协议，即连续ARQ(GO BACK N)和选择重传ARQ。

滑动窗口协议

有噪声信道的全双工协议

&ems;?我们基于以下假设：

• 全双工数据传输：
  • 接收方和发送方两个方向同时传输数据
• 网络层接收处理数据的能力是有限的。
• 通信信道是不可靠的。

&ems;?那么我们要如何进行全双工数据传输呢？如果采用ARQ协议的方法，我们要设置四条信道：两条传输数据，两条进行应答，这样成本会很高，而且利用率低，通信效率也很低。因此我们要想办法减少信道的数量。

&ems;?我们采取如下的方法。这样我们可以只用两条信道：一条A到B，一条B到A。

&ems;?那么我们会有一个问题，发送单独的控制帧会浪费带宽，有没有一种办法避免呢？我们的处理方法是捎带确认。
&ems;?捎带确认就不专门发送确认帧，当有数据发送给对方时，顺便捎上确认帧。一个捎带不一定只捎带一个确认帧，可能捎带许多确认帧。

&ems;?为了区分数据帧和接收帧，我们在帧头中添加了kind，这样帧头就由kind, seq, ack, info, cksum组成了。

数据链路规则(Protocol4)

• Initializtion

  • Next_frame_to_sent = 0;
  • Frame_expected = 0;

• Send frame

  • s.info = buffer;
  • s.seq = next_frame_to_send;
  • s.ack = 1 - frame_expected;
  • To_physical_layer(&s);
  • Start_timer(s.seq);

  next_frame-to_send指明了发送方试图发送的那一帧
  frame_expected指明了接收方等待接收的那一帧

??在一般情况下，两个数据链路层中的某一个首先开始，发送第一帧。换句话说，只有一个数据链路程序应该在主循环外面包含to_physical_layer和start timer过程调用。如果这一帧正是接收方所期望的，则将它传递给网络层，并且接收方的窗口向前滑动。

??我们来比较一下下面两种情况：

• A端首先发送，B端等待发送，无过早超时，其运行过程正常。
• A端和B端同时发送，无过早超时，其运行过程不正常。

情况1

情况2

??如果A和B同时发起通信，则它们的第一帧就会交错，即使没有传输错误，也会有一半的帧是错误的，类似的情况同样发生在过早超时的情况下，即使有一方明显地首先开始传输也会发生这样的情况。

滑动窗口协议

??我们基于以下假设：

• 传播时间不能忽略
• 问题：停等协议的效率低
• 解决办法：在等待确认的时候，继续发送数据帧，这一过程称为管道化。
• 问题又来了：如何处理差错帧？是否要限定未确认帧和允许接收帧的数目

管道化的问题

??如果一个帧出错或者丢失，接收方如何处理后续到来的正确帧？

• 接收方策略
  • 丢弃后续的所有帧，该过程称为退后N
  • 缓存没有出错的帧，该过程称为选择重传
• 对应的发送方策略：
  • 从出错帧开始重传所有帧
  • 仅重传未确认帧

退后N协议

??当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N帧。这就是GO-DACK-N(退回N)法名称的由来。因为，对接收方来说，由于这一帧出错， 就不能以正常的序号向它的高层递交数据，对其后发送来的N帧也可能都不能接收而丢弃。

选择重传协议

??为了进一步提高信道的利用率，可设法只重传出现差错的数据帧或者是定时器超时的数据帧。但这时必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传ARQ协议。
??使用选择重传ARQ协议可以避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间，这在许多情况下是不够经济的。
??正因如此，选择重传ARQ协议在目前就远没有连续则协议使用得那么广泛。今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视。

三个问题

• 什么情况下用停等协议好？
  • 数据传输量小，传输距离近，传输时延小的情况，如WiFi协议
• 什么情况下用退后N协议好？
  • 退后N协议出错误的话会重新传输大量重复的数据，因此在信道可靠稳定的情况下用退后N协议好。
• 什么情况下用选择重传协议好？
  • 选择重传协议可以避免大量重复数据的传输，因此在信道不可靠不稳定的情况下用选择重传协议好。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖