数据链路层概述

保证数据传输的有效，可靠性

  • 差错的检测和控制
  • 流量控制（基于速率/基于反馈）-在数据链路层通常采取基于反馈的模式，即由接收方向发送方提供处理能力大小，发送方根据处理能力提供对应流量

帧

（数据链路层处理的协议数据单元PDU）

帧的组成：帧头+载荷+帧尾

  • 帧头：包含定位所需要的地址，物理地址信息
  • 载荷：上层网络层传递下来的包
  • 帧尾：校验和，做帧的校验

帧的组成

数据链路层使用物理层提供的服务，所以要将物理层处理的位流（bits）转换成数据链路层能够处理的帧，这个过程就叫做“成帧”。

成帧

将原始的位流分散到离散的帧中

常见的四种成帧方法

  1. 字符计数法
  2. 字节填充的标志字节法
  3. 比特填充的比特标记法
  4. 物理层编码违例法

字符计数法

发送方：

在每个帧头部中的第一个字段，标识该帧的长度共有多少字符

接收方：

通过第一个字段，就知道这个帧有几个字符，在哪里结束该帧

优点： 实现简单

缺点： 没有考虑重新同步问题，一旦出错，无法恢复，工程中极少使用

字节填充的标志字节法

考虑了重新同步问题，每一帧采用一个特殊字节做帧界，即当前帧的开始与上一个帧的结束

标记 数据 标记 数据 …

将这个特殊字节称为标志字节（flag byte）

存在问题：当传输数据中也存在标志字节时，会和真正的帧界混淆

解决方案：当数据中存在标记字节时，在标记前添加转义字符（这种方式解决了一部分问题，但同时也带来了一些特殊情况，当数据中包含转义字符时，又必须在转义字符前添加转义字符避免混淆）

特殊情况下传输数据内容：

ESC FLAG ESC FLAG ESC FLAG

在成帧过程中就变成了
ESC |ESC | ESC | FLAG |ESC | ESC |ESC | FLAG |ESC | ESC |ESC | FLAG
—|—|—|—|—|—|—|—|—|—|—|—

缺点： 1.数据中存在帧界或转义符时容易混淆，大量的标志字节或转义字符会造成低效率的成帧（最坏情况50%）。2. 不适用于任意比特数的帧，必须是8位整数倍

比特填充的比特标记法

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

当帧内容出现与帧标志相同位串01111110时：

在5个1后插入一个0，即变成01111101，接收方将自动删除第5 个1后的0。这称为位填充法（零比特填充法），也称为透明传输。

当扫描过程中出现错误导致部分帧没有被正确接收：

接收方会继续扫描直到读取到下一个帧标志，开始重写转换同步数据

优点： 可以传输任意比特数的帧，同时传输效率更高

物理层编码违例法

将冗余信号用作帧界

例如：在4B/5B编码模式中，将4比特映射到5比特上，能够承载32位却只利用了16位，剩下的位就可以用作帧界

例如：在曼彻斯特编码中，只利用了高到低表示1，低到高表示0，却没有利用高到高，低到低两种情况

曼彻斯特编码

优点： 由于利用的是冗余信号，不会混淆，传输效率较高

差错处理的概述

处理错误的常见手段

  1. 纠错：恢复出正确的数据
  2. 检错：仅仅检出错误，不恢复，通常伴随重传

常见错误类型

  1. 单个错误：分散在各个数据块中
  2. 突发错误：集中于一个数据块，整个数据块都是错误

纠错码（前向纠错技术）

发现错误，从错误中恢复出正确的来。

由于纠错码需要纠错，这个过程中需要太多的冗余位，所以开销较大。在有线网络中极少使用，主要应用于无线网络中

检错码

只能发现错误，不能从错误中恢复，但可采用重传恢复

主要应用于局域网

码字：包含数据位和校验位的n位单元（模式）

海明距离：两个码字的海明距离指，两个码字间不同位的数目

例如：“11010101”与“10000101”的海明距离就是2

海明距离可以利用异或运算，其中1的个数表示海明距离

全部码字的海明距离：

指在全部码字中任意两个码字间海明距离的最小值

海明距离的意义：

如果海明距离为d，则一个码字要变成另一个码字，需要跳变d位（发生d个一位错误）才能实现。

海明距离与“检错”的关系：

海明距离为d+1的编码能检测出d位的差错

奇偶校验码：

海明距离为2，能检验出1位错误

奇偶校验码就是将一个校验位追加到传输数据中，分为奇校验和偶校验，校验位的值是“0”还是“1”取决于数据中“1”的个数。

例如：

DATA:100011

偶校验:100011 1

奇校验:100011 0

因为Data中含义3个1，偶校验就是加入校验码后1为偶数个，所以添加1。对应的奇校验则加入0

奇偶校验检错举例：

有一组传输数据只有四种格式“00”，“11”，“01”，“10” 。
经过偶校验，编码后变为“000”，“110”，“011”，“101”

此时发送方向接收方传输数据“101”.产生一个跳变成为“111”.

显而易见“111”这个数据不在四种基本数据内，所以接收方可以成功检错

如果这个过程中发生两次跳变，可能变为“011”.

这个数据虽然变化了，但也出现在基本数据内，所以接收方无法成功检错，说明接收方无法通过奇偶校验处理两次及以上跳变

海明距离与“纠错”关系

海明距离为2d+1的编码，能够纠正d位及以内的差错

纠错的原理在于，此时即使码字发生d次跳变，这个错误码字与原码字之间的距离仍然是最近的。所以接收方只需要找到与这个错误码字海明距离最接近的码字就能将错误纠正

例如：一个系统有4个合法码字（0000000000, 0000011111, 1111100000 ， 1111111111）

海明距离是 5=2*2+1，所以可纠正2位错误.

发送方：0000011111

发生两次跳变后：0000000111

接收方发现差错并且找到海明距离最近的码字进行替换。

收方纠正后: 0000011111

假如发生3次跳变（超出纠错范围）：0000000011

收方找到的海明距离最近码字是：0000000000

可以看到无法再进行纠错

显而易见，随着海明距离增大，纠错能力就不断增强

但是，海明距离越大意味着合法码字越少，传输效率也就越低

二者只能找到一种平衡，而不能同时保持高纠察率以及高传输效率吧

纠1位错的海明码

假设一个系统，经过编码后的码字位数是n位，则n位的组成应该为n=m+r 。其中m表示传输的数据位，r表示冗余位。

在海明码中，将这些冗余位用作纠错位

如何确定冗余位个数r：

在数据传输过程中有m位数据位，所以合法码字有2^m个，而总位数为n，所以一共 有2^n个码字。任取一个合法码字，要保证其跳变一位后能够被纠错，或者说其跳变一位就变成错误码字，就需要至少n+1个码字来表示它。

例如：总位数为5的 “10010” 是一个合法码字，为了保证其跳变一位后会变成错误码字，就要求 “10011”，“10000”，“10110”，“11010”，“00010”这五个与其海明距离为1的码字全部为错，也就是“10010”需要5+1个码字来表示。

综上，则有以下条件成立：

$$
(n+1)2^m<=2^n
$$

$$
n=m+r
$$
推导出：

$$
(m+r+1)<=2^r
$$

利用上式容易得出，纠正单个错误需要的校验位的下界满足：

m r n
1 2 3
2~4 3 5~7
5~11 4 9~15
12~26 5 17~31
27~57 6 33~63

海明纠错码

  1. 将每一个码字从左到右编号，最左边为第一位
  2. 规定凡编号为2的次幂的位是校验位，如1位，2位，4位，8位，16位…
  3. 其余各位均是数据位，如3，5，6，7，9…
  4. 每一个校验位的设置规则：包括自己在内的一些位的集合的奇偶值（奇偶校验）

如何决定每个数据位的校验位：

将某一位数据位的编号展开成2的次幂的和（例如11可以写作：1+2+8），那么每一项所对应的位即为该数据位的校验位（供接收方使用）

如：一个系统中，码字的数据位是7位，根据上文公式求得冗余位是4位，所以码字位数一共11位，其中1，2，4，8位属于校验位（下图P表示校验位，D表示数据位）

— 1 2 3 4 5 6 7 8 9 10 11
— P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7
1=2^0 Y Y Y Y Y Y
2=2^1 Y Y Y Y Y Y
4=2^2 Y Y Y Y
8=2^3 Y Y Y Y

上述图表中描述了我们在第四条中所说的每一个校验位所在的集合，例如第三行表示了1这个校验位的值由1，3，5，7，9，11这些位的值结合奇偶校验决定

— 1 2 3 4 5 6 7 8 9 10 11
— P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7
信息码 - - 1 - 0 0 1 - 0 0 0
检验位 0 0 - 1 - - - 0 - - -
海明码 0 0 1 1 0 0 1 0 0 0 0
(上图采用了偶校验)

海明码纠错过程

  1. 首先将差错计数器置0
  2. 当海明码数据到达接收端后，接收端逐个检查各个校验位的奇偶性。
  3. 如发现某一校验位和它所检测的集合的奇偶性不正确，就将该检验位的编号加到差错计数器中。
  4. Counter=0，无差错。Counter ≠0，出错，该值指明出错的位

比如：

接收到码字为00111000100，校验各校验位：(采用偶校验)

第一位：00111000100，校验集合有3个1，错。counter+1

第二位：00111000100，校验集合有1个1，错。counter+2

第四位：00111000100，校验集合有2个1，对

第八位：00111000100，校验集合有1个1，错。counter+8

累加出错位编号：1+2+8=11

可计算得其第11位出错，将该位由0改为1，即纠正得到正确结果: 00111000101

利用海明码纠正突发错误

突发错误虽然是整个数据块的错误，但可以利用海明码巧妙的逐个纠正

  1. 将连续的k个码字按行排列成矩阵
  2. 发送数据时，按列发送，每列k位
  3. 如果一个突发性错误长度是k位，则在k个码字中，至多只有一位受到影响，正好可用海明码纠错改位后恢复

海明码纠错

检错码

采用检错码的原因：

纠错码占用太多冗余位，信道利用率不高

在局域网中，主要使用的是检错码

常见的检错码：

  • 奇偶校验码（海明距离为2，检一位错）
  • 互联网校验和
  • 循环冗余校验码

奇偶校验码：

奇偶位取值等同于对数据位进行模2和运算

例如，采用偶校验: 1110000 -> 11100001

接收方能够检查出是否存在单个比特的错误（或者奇数个）

出错误的概率在50%（奇数跳变成功检验，偶数则不能）

校验和

校验和通常是按照N位码字来进行模2加/和运算，发送方将运算结果附加在数据报文尾部 ，作为校验位。

例如：16位的互联网补码校验和

特点：

  • 比奇偶检验更好的检错性能
  • 能检出高至N位的突发错误
  • 检错随机错误率1-2^N
  • 易受系统错误干扰，比如，增加的“0”

互联网校验和计算文档：RFC1071（computing the internet checksum）

（1）待校验的相邻字节成对组成16比特的整数一行，按列
从低位开始计算其模2和；并将结果按位取反码，作为校验
和取值。

（2）检查校验和时，将所有字节，包括校验和，进行相加
并求二进制反码。接收方：如果结果为全1 ，无错误

注意：如果某列的模2和有溢出，向高位进位，如果高位产
生进位，循环向低位进位。

循环冗余检错码CRC

任何一个k位的帧都可以看成一个k-1次的多项式

例如：1011001 可以看成->
$$
x^6+x^4+x^3+x^0
$$
(k项k-1阶多项式)

CRC系统里一定具有生成多项式：G(x)，G(x)为r(冗余码个数)阶

还具有m位帧的多项式：M(x),且一般 m>r , M(x)>G(x)

接下来：

$$
\frac{x^rM(x)}{G(x)}=Q(x)+R(x)
$$
Q(x)表示商，R(x)表示余数

易知：

$$
\frac{x^rM(x)-R(x)}{G(x)}=Q(x)
$$
说明
$$
x^rM(x)-R(x)
$$
一定能被G(x)整除，所以将它作为转码后的数据传送给接收方

接收方在收到后，将其与约定好的生成多项式G(x)相除：

  • 若为0，说明传输过程中没有发生错误
  • 若不为0，说明传输过程发生错误

在二进制运算中，减法和加法都做异或运算，即相同得0，相异得1

例如：11010+10100=01110，11001-10010=01011

模2运算：模2加以及模2减等同于异或运算，即相同得0，相异得1

0⊕0=0; 0⊕1=1;
1⊕0=1; 1⊕1=0.

CRC码计算：

发送方

传输的一帧：1101011011（m=10）

易知：
$$
M(x)=x^9+x^8+x^6+x^4+z^3+x+1
$$

规定：收发双方采用统一的
$$
G(x)=x^4+x+1
$$

计算得：
$$
T(x)=x^4M(x)=x^4(x^9+x^8+x^6+x^4+z^3+x+1)=x^{13}+x^{12}+x^{10}+x^8+z^7+x^5+x^4
$$
(相当于在原码字后边加r个0)

开始计算：（采用模2除法，用G(x)去除X^r*M(x)，得余数）

运算

计算11010110110000/10011 得余数1110 ，采用模2减法，用XrM(x)减去余数，得到带CRC校验和的帧,11010110110000-1110=11010110111110，所以：

最终得到发送给接收方的数据= 1101011011(帧数据)1110(余数)

接收方

接收方在得到传输过来的码字后，会利用规定的G(x)与之相除，能够整除则认为传输正确

如果不能被整除，则检测为传输出错

生成多项式国际标准

CRC-12 ：$x^{12} + x^{11} + x^3 + x^2 + x^1 + 1 $。用于字符长度为6位

CRC-16 ：$x^{16} + x^{15}+ x^2+ 1 $。用于字符长度为8位

CRC-CCITT ：$x^{16} + x^{12}+ x^5+ 1$。 用于字符长度为8

CRC32 ：$G(x)= x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^3+x+1$

CRC32广泛应用于以太网计算循环冗余校验时用

例题：如果生成多项式是 G(x)= x^3 + x^2 + 1，待传送的原始码字分别是1111 和 1100，请计算采用CRC编码后的码字分别是多少？

解题：生成多项式是3阶的，所以r=3，生成多项式对应的位（除数）是：1101

待传输的1111，移位后变为：1111000（被除数），得到余数111

用1111000-111，得到编码后的码字为：1111111

三个单工协议-基本数据链路层协议

单工：数据的传输在某时是单向的

  • 无限制的单工协议
  • 单工停-等协议
  • 有噪声信道的弹弓协议

理想条件下假设：

  • 物理层，数据链路层和网络层是各自独立运行的进程（在工程中可能有各自不同的存在形式）
  • 机器A希望向B发送的是一个可靠的面向连接的长数据流
  • 假设机器不会崩溃，即使崩溃，我们不会处理因崩溃产生的错误
  • 从网络层拿到的数据是纯数据

几个协议共用的数据类型，调用函数

protocol.h文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define MAX_PKT 1024                    /* packet size in bytes */

typedef enum { false, true } boolean;   /* boolean type */
typedef unsigned int seq_nr;            /* sequence or ACK numbers  序列号或确认号*/

typedef struct {
    unsigned char data[MAX_PKT];
} packet;                               /* 从网络层传输来的包/分组 */
typedef enum { data, ack, nak } frame_kind; /* frame kind definition ack表示确认字符，nak表示否定应答或者非应答 */


typedef struct {
    frame_kind kind;                    /* what kind of frame? 帧的类型 */
    seq_nr seq;                         /* sequence number 序列号*/
    seq_nr ack;                         /* ACK number 确认号/确认字符*/
    packet info;                        /* the Network layer packet 包/分组（来自网络层）直接作为帧的载荷定义在帧的结构中*/
} frame;   //定义帧结构

typedef enum {
	frame_arrival,  //帧到达
	cksum_err,   //检错码错误
	timeout,   //时间超出
	network_layer_ready,   //网络层完成准备（可以发送下一条数据）
	ack_timeout  //延时确认计时器时间超出
} event_type;  //定义事件类型


/* wait for an event to happen; return its type of event */
/*等待事件发生，并返回事件类型：即上文事件类型类中的内容*/
void wait_for_event(event_type* event);

/* fetch a packet from the network layer for transmission 从网络层获取数据*/
void from_network_layer(packet* p);

/* deliver information from an inbound frame to the network layer 向网络层发送数据*/
void to_network_layer(packet* p);

/* get an inbound frame from the physical layer 从物理层获取数据*/
void from_physical_layer(frame* r);

/* pass the frame to the physical layer 向物理层发送数据*/
void to_physical_layer(frame* s);

/* start the clock and enable the timeout event 重传定时器启动*/
void start_timer(seq_nr k);

/* stop the clock and disable the timeout event 重传定时器关闭*/
void stop_timer(seq_nr k);

/* start an auxiliary timer and enable the ack_timeout event 捎带确认定时器启动*/
void start_ack_timer(seq_nr k);

/* stop an auxiliary timer and disable the ack_timeout event 稍待确认定时器关闭*/
void stop_ack_timer(seq_nr k);

/* allow the network to cause a network_layer_ready event */
void enable_network_layer(void);

/* forbid the network to cause a network_layer_ready event */
void disable_network_layer(void);

/* macro inc */
#define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0

其中定义了很重要的帧结构，以及事件类型，基本操作等等…

无限制的单工协议-协议1

这种协议设定了很多理想条件，在现实中很难满足，所以被称为“乌托邦协议”

理想条件：

  • 收发双方的网络层都处于就绪状态（随时待命）
  • 处理时间忽略不计（瞬间完成）
  • 可用的缓存空间无穷大（无限空间）
  • 假设DLL之间的信道永远不会损坏或者丢失帧（完美通道）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef enum { frame_arrival } event_type;
#include "protocol.h"

//封装发送过程
void sender1(void)
{
	frame s; /*buffer for an outbound frame 为帧准备内存空间*/
	packet buffer; /*buffer for an outbound packet*/
	while (true) {
		from_network_layer(&buffer); /*go get something to send 从网络层获取数据存入缓存 */
		s.info = buffer; /*copy it into s for transmission 将数据写入帧的载荷*/
		to_physical_layer(&s); /*send it on its way 将帧传递给物理层处理*/
	}
}

//解封装发送过程
void receiver1(void)
{
	frame r;
	event_type event; /*filled in by wait, but not used here*/
	while (true) {
		wait_for_event(&event); /*only possibility is frame arrival 等待数据到达事件*/
		from_physical_layer(&r); /*go get the inbound frame 接收来自物理层的数据并进行成帧*/
		to_network_layer(&r.info); /*pass the data to the network layer 将数据中的包向上传递到网络层*/
	}
}

单工停-等协议 协议2

无限制的单工协议条件过于完美，现实中要想实现就需要不断解除这些完美条件。

单工停-等协议首先取消了可用缓存空间无限大这一理想条件

也因此，需要解决接收方有可能被发送方传输的大量数据淹没这一问题

解决方法：

接收方在每次接收到数据后，会向发送方返回一个哑帧，表示自己已经正常接收到数据，并且可以继续接收数据。发送方在收到返回的哑帧后，才会继续传输下一个数据。
停等协议

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


typedef enum { frame_arrival } event_type;
#include "protocol.h"
void sender2(void)
{
	frame s; /*buffer for an outbound frame*/
	packet buffer; /*buffer for an outbound packet*/
	event_type event; /*frame arrival is the only possibility */
	while (true) {
		from_network_layer(&buffer); /*go get something to send */
		s.info = buffer; /*copy it into s for transmission*/
		to_physical_layer(&s); /*bye - bye little frame */

		/*
		 *这里体现了与第一种协议的区别，
		 *在发送一条数据后不会立即循环发送下一条
		 *而是等待返回的哑帧再进一步操作
		 */
		wait_for_event(&event); /*do not proceed until given the go ahead*/
	}
}
void receiver2(void)
{
	frame r, s; /*buffers for frames*/
	event_type event; /*frame arrival is the only possibility */
	while (true) {
		wait_for_event(&event); /*only possibility is frame arrival */
		from_physical_layer(&r); /*go get the inbound frame */
		to_network_layer(&r.info); /*pass the data to the network layer */
		/*
		 *与第一种协议不同之处
		 *收到信息并传到网络层后，没有立即进入接收状态
		 *而是返回一段哑帧
		 */
		to_physical_layer(&s); /*send a dummy frame to awaken sender */
	}
}

有噪声信道的单工协议-协议3

有噪声的单工信道协议在前文基础上，取消了帧不会损坏或丢失这一理想条件

认为信道中含有噪声，有噪声就会引发错误

进而考虑如何处理以下衍生问题并解决

发现错误后如何通知发送方，如何修正错误，恢复正确帧：（PAR肯定确认重传协议/ARQ自动重传请求）

在接收方对数据进行检验并且检验正确后，会向发送方返回一个确认帧，发送方在收到确认帧后继续传输数据。

发送方在数据发送的同时启动重传定时器（防止锁死），超过定时器规定时间还未收到确认帧（发送过程失败或者返回确认帧过程失败，或者检验错误），发送方就会重置计时器，并且重传原数据。

在传输过程中，每个帧都具有自己独一无二的编码，防止数据帧成功到达接收方并且检验合格但返回确认帧失败的问题，同时方便重排

ARQ

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef enum { frame_arrival } event_type;
#include "protocol.h"
void sender3(void)
{
	seq_nr next_frame_to_send; /*seq number of next outgoing frame 出站序列号-用于区别各个帧 */
	frame s; /*scratch variable */
	packet buffer; /*buffer for an outbound packet*/
	event_type event;
	next_frame_to_send = 0; /*initialize outbound sequence numbers 初始化出站序列号 */
	from_network_layer(&buffer); /*fetch first packet 获取第一个数据包*/
	while (true) {
		s.info = buffer; /*construct a frame for transmission 将包放入帧的载荷*/
		s.seq = next_frame_to_send; /*insert sequence number in frame */
		to_physical_layer(&s); /*send it on its way 向物理层传输 */
		start_timer(s.seq);  /*if answer takes too long, time out 开启重传计时器*/
		wait_for_event(&event); /*frame arrival, cksum err, timeout 等待确认帧返回*/
		if (event == frame_arrival) {  //判断是否返回确认帧
			from_physical_layer(&s); /*get the acknowledgement 获取物理层回传的数据*/
			if (s.ack == next_frame_to_send) {   //获得收方确认则执行以下操作
				stop_timer(s.ack); /*turn the timer off 重置重传计时器*/
				from_network_layer(&buffer); /*get the next one to send 从网络层获取下一个传输数据*/
				inc(next_frame_to_send); /*invert next frame to send 转化序列号*/
			}
		}
	}
	//如果这个过程中没有收到返回的确认帧，或确认帧表明传输错误
	//则通过while循环进行重传
}
void receiver3(void)
{
	seq_nr frame_expected;
	frame r, s;
	event_type event;
	frame_expected = 0;
	while (true) {
		wait_for_event(&event); /*possibilities: frame arrival, cksum err*/
		if (event == frame_arrival) {
			/*a valid frame has arrived */
			from_physical_layer(&r); /*go get the newly arrived frame */
			if (r.seq == frame_expected) {  //获得正确传输的数据
				/*this is what we have been waiting for*/
				to_network_layer(&r.info); /*pass the data to the network layer 将数据向网络层传输*/
				inc(frame_expected); /*next time expect the other sequence nr 下一阶段期待的序列号*/
			}
			s.ack = 1 - frame_expected; /*tell which frame is being acked 告知发送方需要传输的数据*/
			to_physical_layer(&s); /*send acknowledgement 返回确认帧*/
		}
	}
}

提高传输效率的协议实现方式：

全双工：

在信道传输的过程中，不再是单向的数据流动，而是除去了常见的收发双方概念，两方同时进行接受与发送数据的工作，提高数据传输的效率

捎带确认：

接收方在发送确认帧时，不再新建一个帧，而实挂靠到一个将要前往发送方的数据帧末尾。提高了信道利用率，但要注意，有时收发双方数量是不对等的，也就是我们不一定能等到可以挂靠的数据帧，所以我们要建立一个稍待确认计时器，超时之后直接发送确认帧

批发数据（管道化技术）：

在等待第一帧的确认帧返回时，不停止数据发送，而是持续发送数据，等第一帧的确认帧返回，再确定是否继续进行发送过程

滑动窗口协议-协议4

上文所提到的三种协议都是单工或半双工协议，在等待确认帧返回的空闲时间里不进行任何操作，所以信道的利用率非常低。协议4-6区别于前文三种协议，采用以下几种手段提高信道利用率

全双工模式

即在通讯过程中允许双方同时相互传输数据，整个过程模糊了收发双方的概念，因为双方都在同时进行收和发的操作

管道化技术（批量发送）

在等待上一帧的确认帧返回时，不是单纯等待，而是继续发送帧。它可以一次性发送多条数据，我们将这些数据的组合称为一个窗口，管道化技术就是在逐个发送窗口。所以我们也称其为滑窗技术

滑动窗口

整个过程中双方都对应拥有两个窗口：

  1. 发送窗口：对应着已经发送，未被确认的数据帧的序列号
  2. 期望接收的数据帧的序列号

滑动窗口

可以看到整个滑动窗口的流程是首先从接收一方开始，接收方首先将窗口设置在0位置，表示期望接收到0序列号的帧，接下来发送方开始滑动窗口到0，并向接收方发送0数据帧，在接收方收到第一帧后，接收方返回确认帧并且滑动窗口到1位置表示期望收到1数据帧，发送方在接到确认帧后继续滑动窗口并发送对应帧

协议代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define MAX_SEQ 1			
#include"protocol.h"

void protocol4(void)
{
	seq_nr next_frame_to_send;  //将要发送的帧的序列号
	seq_nr frame_expected;   //期望收到的帧的序列号
	frame r, s;  
	packet buffer;
	event_type event;
	next_frame_to_send = 0;  //初始化将要发送的帧的序列号，从0号帧开始发送
	frame_expected = 0;   //表明期望接受到的帧是0号帧
	from_network_layer(&buffer);   //从网络曾获取包
	s.info = buffer;  //放入要发送的帧中
	s.seq = next_frame_to_send;
	s.ack = 1 - frame_expected;
	/*
	 *由于是双工协议，所以采用了稍待确认
	 *也就是将确认帧放到数据帧中，提高了信道利用率
	 */
	to_physical_layer(&s);  //像物理层开始传输
	start_timer(s.seq);  //启动计时器
	while (true) {
			wait_for_event(&event);  //接收对应事件
			if (event == frame_arrival) {
				from_physical_layer(&r);  //从物理层获取返回的确认帧+数据帧 
				//通过帧的seq号判断是否是期望接受的帧
				if (r.seq == frame_expected) {  
					to_network_layer(&r.info); //如果是就将数据继续向网络层传输
					inc(frame_expected);  
					//这里调用了一个宏用来移动窗口
					//这个宏的作用就是将期望的数据帧序列号+1，将期望窗口调整到下一位置
				}
				//通过帧的ack号与发送出的帧序列号比较，判断数据是否成功到达接收方
				//以及是否继续发送下一帧或者重传
				if (r.ack == next_frame_to_send) {
					stop_timer(r.ack);
					from_network_layer(&buffer);
					inc(next_frame_to_send);
				}
			}
			s.info = buffer;
			s.seq = next_frame_to_send;
			s.ack = 1 - frame_expected;
			to_physical_layer(&s);
			start_timer(s.seq);
		}
}

窗口滑动条件

接收方收到帧后，首先核对帧是否与期望相同，如果相同，则返回确认帧并且滑动接收窗口（frame_expected+1）然后将数据像网络层传输

发送方在收到确认帧后，核对响应帧号next_frame_to_send，全部完成后，从网络层获取新的数据，并将响应帧号next_frame_to_send+1即移动发送窗口，然后像物理层传输信息，否则，不移动窗口

滑动窗口基本概念

每个待发送帧被赋予一个序列号seq,seq的取值范围是 0 ~ 2^n-1（n位字段）

发送窗口

  • 顺序接收来自网络层的分组->成帧->赋予序列号
  • 最多保存W个已经发送、等待确认的帧
  • 窗口达到最大值W时强制关闭网络层

接收窗口

  • 对进入窗口的帧顺序提交网络层，产生确认
  • 落在窗口外的帧被丢弃

SEQ码和ACK码

因为滑动窗口协议只涉及1个窗口，所以在传输过程中，SEQ码和ACK码的取值只有0和1两种，当SEQ码=1时，表示当前发送的数据为1序列号的帧，当ACK码为1时，表示已经成功接收序列号为1的帧，期望接收序列号为0的帧（这里与直观感受并不一致）

通信双方初始值：seq =0, ack=1（期待接收seq=0）

窗口滑动机制

  • A首先发送数据帧（seq=0, ack=1, A0）–发送0帧，期望收到0帧
  • B收到A0，发送捎带确认帧（seq=0, ack=0, B0）–发送0帧，成功收到0帧，期望收到1帧
  • A收到对A0的确认，滑动窗口，发送帧（seq=1, ack=0, A1）–发送1帧，收到0帧，期望收到1帧

协议帧的差错控制

传输过程

可以看到在发生错误后，由于计时器时间设置不合理，接收方收到重复帧，这种情况下接收方会发送同样的确认帧返回发送方，但不会接收当前传过来的重复帧，这就使得整个流程可以正常运行，不会因为错误帧而中断。但整个流程效率极低

效率问题

假设窗口每次只发送一帧，那么可以通过运算获得整个过程的信道利用率：

$$
信道传输速率是： b (bps)
$$

$$
每帧的大小是： k (bits)
$$

$$
来回时间是： R (sec)
$$

$$
信道利用率=\frac{k}{k+bR}
$$

带入数据：信道容量 b = 50 kbps，传输延迟 R = 500 ms（双程），数据帧的长度 k = 1000 bit。（设接收方收到数据帧后马上回送确认短帧，没有延时）

可以算的信道利用率为3.85%，不足4%，利用率极低。这是因为我们一个窗口只发送了一帧，这一帧到达之前，窗口始终处于空闲状态，所以需要设定窗口合理的帧数，使利用率提高（增加滑动窗口长度）

设窗口长度为W(一个窗口发送字节的数量)

$$
在源端发送数据帧过程需要的时间=T_f =\frac{k}{b}
$$

$$
从发送完毕到确认帧返回需要的时间（双程延迟）R
$$

$$
从开始发送到确认返回总共需要的时间(T_f +R)
$$

$$
线路的利用率=\frac{W*T_f}{T_f +R}
$$

上文实例中若假设信道利用率为100%，可以解得W=26，也就是一个窗口发送26帧时，信道利用率最高。当然，这只是理想状态下的假设，正常情况下一般无法达到信道100%的利用

如何确定合适的W值

信道上的容量：一帧从发送方传输到接收期间可容纳的帧数量

带宽-延迟积：BD（B表示带宽，D表示时间）

窗口值：w=2*BD+1

实际上:w≤2*BD+1

例题：

主机甲和主机乙之间使用后退N帧协议（GBN）传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道为100Mbps，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认。若甲乙之间的单向传播延迟是50ms，则甲可以达到的最大平均传输速率约为？

解题：

假设平均传输效率为x(Mbps)

根据w=2BD+1

易知：$1000=2x(Mbps)*50(ms)*10^{-3}+1$

解得：x=80Mbps

管道化技术面临的出错情况

  • 连续发送W个数据帧，其中有一帧出错，但其后续帧被成功
    发送

    接收方的接收策略选择

  • 丢弃错帧及后续帧，其后续帧因不是期望接收帧也被丢弃，对应协议5
  • 丢弃错帧，缓存后续正确接收帧，对应协议6

回退n帧-协议5

上文提到了使用管道化技术带来的新问题与两种解决方式

  1. 回退n帧
  2. 选择性重传

这两种协议对应着不同的接收发送策略

回退n帧

接收方的接收策略与选择：

直接将错误帧与后续帧丢弃，后续的正确帧到来后因不是期望帧也被舍弃

发送方的发送策略：

发送前将所有帧缓存，在收到确认帧后，未为成功发送的帧以及后续所有帧进行重传

选择性重传

接收方的接收策略与选择：

丢弃错误帧，将剩余正确帧保留并缓存

发送方的发送策略：

在收到确认帧后只重传错误帧

回退n帧

基本概念

  • 定义了序列号seq，以及滑动窗口长度W
  • 发送方持续发送数据，直到达到最大窗口长度
  • 接收窗口为1，在接到错误帧后不确认(引发超时，进而重传)
  • 发送方超时后进行重传，从未收到的确认帧处开始

回退n帧

可以看到在发送过程中，从2号帧开始出错，则后续帧都被丢弃。之后接收方会返回1号帧的确认帧（注意！不是返回2号帧，而是返回错误帧的上一位帧的确认帧，因为1号帧成功被接收，发送方借此可以判断是从2号帧开始需要重传的）

发送方与接收方

累计确认

在滑动窗口中采用了累计确认的方式来对帧进行确认

也就是说在收到对于5号帧确认时，暗含的意思就是已经完成了对0，1，2，3，4，5这几个帧的确认，而不必要每一个都发送确认帧

对于发送方，这样在接收到第n帧确认后，就可以删除n帧及以前所有的缓存

但这同样也引发了新的问题(规定)：

滑动窗口最大长度W不能超过最大序列号
比如：序列号用三位表示，则最大序列号=111。表示7，所以窗口长度不能等于8或超过8，超过8很好理解，因为如果窗口长度大于8，则，没有足够的序列号为每一个帧标记。

当序列号等于8时，有足够标记(0，1，2，3，4，5，6，7)但这也是不允许的，因为这会引发新的问题。

我们在返回确认帧时采取了累计确认，当第一个窗口的8个帧全部被顺利接收后，接收方会返回一个确认帧ACK=7,表示已经正常收到7号帧及之前元素，可以继续发送下一窗口了。

这时如果发送方在发送第二个窗口时发生错误，接收方根本没收到期望帧，就会重新发送确认帧ACK=7表示自己期望接受第二个窗口，可这时就会发生混淆，发送方不能分别这个确认帧，是希望对窗口二进行重传还是表示已经正常接收到窗口二。 无法正确执行程序

如果滑动窗口不超过8就不会有这种问题，比如滑动窗口为7，这样第一窗口的确认帧是ACK=6，第二窗口的确认帧是ACK=5（因为第二窗口帧的序列号是从7开始的：7，0，1，2，3，4，5）

这样就避免了过程中可能产生的歧义，很好的解决了问题

回退n帧需要发送方付出更大的缓存代价，缓存整个窗口的数据帧

适合出错较少的高速信道

选择性重传-协议6

基本概念

  • 接收窗口接收错误帧后的所有正确帧，并将它们缓存起来
  • 发送方只重传错误帧
  • 接收方在接收到重传帧后，将其与其他帧按正确顺序排序，再提交至网络层

选择重传协议的工作原理分析

接收方发送方2

否定确认NAK

  • 在接收方收到错误帧时会发送否定确认NAK到发送方
  • 这样可以加快出错帧的重传
  • 对出错帧回送否定确认，使发方不再等到超时再重传

滑动窗口长度选择

接收窗口：W= (MAX_SEQ + 1) / 2

发送窗口一般小于接收窗口

原因：

当发送窗口和接收窗口都比较大时，就会导致新老窗口序列号重叠，比如说序列号为3位（XXX），收发窗口大小都是7，则接收窗口第一次为（0，1，2，3，4，5，6），第二次为（7，0，1，2，3，4，5）。这其中（0，1，2，3，4，5）都为重叠部分。

当接收方正确接收第一窗口并滑动窗口后，确认帧被发送出去，但在确认帧发送过程中，全部丢失。所以发送方超时进行重发（0，1，2，3，4，5，6）这个窗口，当0号帧到达时

接收方不能判定他是重传帧，反而在第二个窗口发现了对应帧的序列号，这个重传帧就被错误的放在了第二个窗口，而实际上，它只是第一个窗口的重传帧而已

当W遵守W= (MAX_SEQ + 1) / 2 的规定时，就可以保证新老窗口之间没有重叠部分。，可以正常通过帧的序列号判定帧的类型

— 协议4：滑动窗口 协议5：回退n帧 协议6：选择性重传
发送窗口(SWnd) 0<SWnd<=1 0 <=SWnd<=MAX_SEQ 0 <= SWnd<= RWnd
接收窗口(RWnd) 1 1 (MAX_SEQ+1)/2

两种策略比较

回退n帧

  • 发送方需要较大的缓冲区，以便重传
  • 重传帧数多，适于信道出错率较少的情况

    选择重传

  • 接收方需要较大的缓冲区，以便按正确顺序将分组提交网络层
  • 重传帧数少，适于信道质量不好的情况