网络-数据链路层

Posted by Young Ken on 2017-09-22

数据链路层

数据链路层就把信息块从A机器传到B机器,B机器把这个信息块取出来。

数据链路层的设计问题

数据要完成了一些功能,包括:

  • 给上层提供接口
  • 出来传输错误
  • 防止接收端被发送方淹没

提供给网络的服务

数据链路层的主要职责是向上层(网络层)提供服务,它提供的服务主要有三种:

  • 无确认的无连接服务

这样的服务发送端只管发送数据,不管接收端是否接收到数据。当然了,逻辑链接也不用建立。使用场景(1)错率非常低的场景(2)语音传输,因为实时比丢失更重要

  • 有确认的无链接服务

这样的服务比上一个可靠点,这样的服务依旧没有逻辑链接,但是会确认帧是否到达目的地,典型应用WIFI。

  • 有确认的有链接服务

发送端和接收端要建立链接,并且为每个帧编号,并且有一个定时器,发送帧的时候,定时器启动,在定时范围内没有收到接收方发回的反馈,发送方认为这个帧丢了,那么从新发送这个帧。

成帧

什么是成帧,网络层给链路层一坨数据,说把这坨数据发送给XX机器,链路层要把这坨数据拆分成帧,这个过程叫做成帧,成帧的关键就找到帧的头和尾巴。

成帧的方法有几个

  • 字节计数法

现在这个方法很少用了。

  • 字节填充的标志字节

我们都知道一行的结尾是‘/n’,但是我的为本里就有‘/n’怎办,这时候转义字符就登场了。标志字符同样的原理。

找个特殊字符当做帧的头和尾巴,比如我们想用FLAG做帧的头和尾巴,当解析帧的时候,看到遇到FLAG就认为是头,再来一个是尾巴,但是我的帧包含了FLAG字符,有个转义字符ESC。

原来的字符是A FLAG B 加上转义字符就变成 A ESC FLAG B。

  • 比特填充的标志比特

听上去好上个一样呢,对了,原理相同,上个是字符,这个个是比特。

差错控制

这个下面会非常详细的说,也比较好理解,就是怎么确保每个帧都到达发送端采用的策略。

流量控制

当发送方是个无比强大的机器,接收方只是个Android手机,这个是尴尬了,Android手机不能处理如此大数据。解决方案通常有两种,一个是基于反馈流量控制简单理解就是接收方反馈信息告诉发送方我的状态。第二种:基于速度的流量控制也就是直接限制发送发的流量。

错误检测和纠正

虽然现在的光纤错误率比较低,但是无线链路和老的回路错误率还是比较高的。所有进行纠错和纠正还是非常必要的。在网络传输中处理错误通常有两种方式,第一个叫做纠错码验错码,这两种方式都是在发送信息上加载一些信息,来达到检查错误的原理。

纠错码

纠错码有四种,分别是:

  • 海明码

海明码(Hamming Code)是一个可以有多个校验位,具有检测并纠正一位错误代码的纠错码,所以它也仅用于信道特性比较好的环境中,如以太局域网中,因为如果信道特性不好的情况下,出现的错误通常不是一位。

​ 海明码的检错、纠错基本思想是将有效信息按某种规律分成若干组,每组安排一个校验位进行奇偶性测试,然后产生多位检测信息,并从中得出具体的出错位置,最后通过对错误位取反(也是原来是1就变成0,原来是0就变成1)来将其纠正。

具体看这个博客讲的帧的非常明白

  • 卷积码

属于一种纠错码(error-correcting code)。相对于分组码,卷积码维持信道的记忆效应(memory property)。卷积码的由来,是因为输入的原始消息数据会和编码器(encoder)的冲激响应(impulse response)做卷积运算。有兴趣的同学可以找点资料。

  • 里得所罗门码
  • 低密度奇偶校验码

检错码

相比于无线链路来说,光纤很少出错,这样就不需要纠错码,只需要检错就行了。

检错码包括:

  • 奇偶

是检测传输过程中有无错误的一种方式,原理比较简单,就是每7位数,在后面追加一位校验码。

偶检验方式1011010有偶数个1在末尾加0

奇检验方式1011010有奇数个1在末尾加1

优点简单,但是缺点很明显,就是错误检率是0.5。

  • 检验和

另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种,最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子:

我们要传输的信息为: 6、23、4

加上校验和后的数据包:6、23、4、33

  • 循环冗余校验

简单总结一下,当物理层不是很稳定,错误率很高的情况下,用纠错码,这样如果数据错误,有可能被恢复,但是缺点比较明显,传输的数据变多了,需要大量运算才能完成纠错。物理层比较稳定就可以用检错码,数据错了从新传就可以了,因为错误率低,没有多传输很多帧。

基本数据链路层协议

重点来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#defaylt MAX_PKT 1024
typedef unsigned int seq_nr; //帧的编号
typedef struct {unsigned char data[MAX_PKT];} packet;// 帧的实际数据
typedef struct {
frame_kind kind;
seq_nr seq;//序号
seq_nr ack;//确认
packet info;
} frame;
void wait_for_event(event_type *e); //等待事件发生
void to_network_layer(packet *p);//从网络接收包
void from_network_layer(packet *p);
void to_physicak_layer(frame *f);
void from_physicak_layer(frame *f);//从物理层得到数据
void stop_timer(seq_nr k);
void start_timer(seq_nr k);

一个网络协议的基本信息头,这个文件是protocol.h

乌托邦试的单工协议

来个最简单的协议,不考虑任何情况,只把数据从发送端发到接收端,接收端进行接收。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef enum {frame_arrival} event_type;
#include "protocol.h"
void sender(void) {
frame s;
packet buffer;
while(true) {
from_network_layer(&buffer);
s.info = buffer;
to_physicak_layer(&s);
}
}
void receiver(void) {
frame r;
event_type event;
while(true) {
wait_for_event(&event);
from_physicak_layer(&r);
to_network_layer(&r.info);
}
}

发送方运行在源机器上,接收端运行在目标机器上。

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

现在假设接收方被发送方淹没,上面已经提到了,这总情况有两个解决方案,我们采用第二种。也就接收方不断和发送方进行信息同步。具体就是当接收方接收到一个帧之后,会给发送方发送一个哑帧,告诉发送方可以继续发送数据了。

发送方发送一帧,等待对方确认后再发送,这样的协议叫做停-等式协议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef enum {frame_arrival} event_type;
#include "protocol.h"
void sender(void) {
frame s;
packet buffer;
event_type event;
while(true) {
from_network_layer(&buffer);
s.info = buffer;
to_physicak_layer(&s);
wait_for_event(&event);
}
}
void receiver(void) {
frame r,s;
event_type event;
while(true) {
wait_for_event(&event);
from_physicak_layer(&r);
to_network_layer(&r.info);
to_physicak_layer(&s);//**接收完数据发送一个哑帧**。
}
}

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

上面都不是常规情况,常规情况是通讯信道出错,也就是帧损坏或者丢失。

想一下这个也好解决,在发送端启动一个定时器,如果在超时时间内没有接到确认帧(在接收方接收到帧,会给发送方发送一个帧,告诉发送方我接收这个帧了,这个帧叫做确认帧)。那么发送发补发这个帧,直到发送方接收到确认帧为止。

这个情况看着好像问题都解决了,但是我们忽略了一个重要的点,确认帧和其他的帧都是一样的,也会丢的,如确认帧丢了会怎么样,发送端定时器超时,补发这个帧,实际情况这个帧已将被接收方接收了,这个帧就被从复发送了,这次网络传输失败了。

其实也有解决方案,每个帧加一个序号,这个序号是2取模(1或者0),当接收方接收到时0的时候,期待下一个帧是1,如这个时候确认帧丢失,发送方超时,从新发送0,接收方发现这个帧已将存在,从新发送确认帧,期待下一个帧是1,不断从复知道成功能。

在这个协议中,发送方在前移到下一个数据之前必须等待一个确认,这样的协议叫做自动重复请求(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
typedef enum{frame_arrival, cksun_err, timeout} event_type;
#include "protocol.h"
void sender(void) {
seq_nr next_frame_to_send;
farme s;
packet buffer;
event_type event;
next_frame_to_send = 0;
from_network_layer(&buffer);//从网络层接收数据
while(true) {
s.info = buffer;
s.seq = next_frame_to_send;
to_physicak_layer(&s);
start_time(s.seq);
wait_for_event(&event);
if(event==frame_arrival) {
from_physicak_layer(&s);
if(s.ack == next_frame_to_send) {
stop_time(s.act);
from_network_layer(&buffer);
inc(next_frame_to_send);
}
}
}
}
void receiver(void) {
seq_nr frame_expected;
frame r,s;
event_type event;
frame_expected = 0;
while(true) {
wait_for_event(&event);
if(event == frame_arrival) {
from_physical_layer(&r);
if(s.seq == frame_expected) {
to_network_layout(&r.info);
inc(frame_expected);
}
}
}
}

滑动窗口协议

前面的协议,A机器给B机器发送一个帧,B机器给A机器发送确认帧,这样B机器有点浪费了,其实B机器也可以给A机器发送数据的,如果这样,那么确认帧是不是可以搭数据帧的便车(在数据帧的头部多一个字段,发送成功帧的帧号),答案是可以的,这样暂时延缓确认已便将确认信息搭载在下一个出境数据帧的技术叫做捎带确认。那么问题来了,如果确认帧只是搭出境帧的便车,A机器很可能就会超时,从新发送数据。这是时候就需要策略了。如果确认帧发现在一定时间内还没有便车,那么就要自己出发了,防止A机器超时。

无论什么协议都要保证网络断发送的数据要从A机器完整的无错的到达B机器。

滑动窗口的本质就是任何发送方和接收方都维护了一组序号,分别表示允许对应发送和接收的帧。

1位滑动窗口的协议

当滑动窗口是1的时候,滑动窗口退化成了停-等协议。但是停-等协议中我们强行规定,接收端只能接收数据,并且只能发送确认帧,如果这个限制去掉,那么A可以给B发送,B也可以给A发送。

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
typedef enum{frame_arrival, cksun_err, timeout} event_type;
void protocol(void) {
seq_nr next_frame_to_send;
seq_nr frame_expected;
frame r, s;
packet buffer;
event_type event;
next_frame_to_send = 0;
frame_expected = 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);//从物理层读取数据
if(s.seq == frame_expected) {
to_network_layer(&r.info);//把数据给网络
inc(frame_expected);
}
if(r.ack == next_frame_to_send) {
stop_time(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);
}
}

回退N协议

之前的模型是比较理想的,我们完全没有考虑网络延时的情况,也就是发送的数据很短的时间就能到达接收方,接收方很快就能返回确认帧。真实的情况是网络之间传输数据是有延时的。如果我们每次只发一帧(这帧的数据等于带宽),那么整个网络的利用率是0.5,那么怎么样才能提高利用率呢,连续发送多个帧。

这样连续发送多个包的技术叫做管道化

同时发送多个帧就设计到丢帧等情况,如果接收窗口大小为1。我要发送0-7个帧,当接收到3号帧的时候,发现2号帧还没有来,那么对不起,2-7帧都需要从新传。这个方式叫做回退N(go back N)。

当接收窗口很大的时候,我要发送0-7帧,当接收到3号帧的时候,没号2帧丢失,那么接收方继续接收其他帧,针对2号帧发一个否定确认(接收方发现错误,要求发送方从新传)。如果否认确定丢失,方式方超时,从新补发2号帧。这样的方式叫做选择重传

选择重传协议

发送方的窗口大小从0到最大值,接收端的窗口大小是一个固定值,如果帧在between中就接收这个帧。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#define MAX_SEQ 7
#define NR_BUFS ((MAX_SEQ + 1) / 2)
typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout} event_type;
#include "protocol.h"
bool no_nak = true;
seq_nr oldest_frame = MAX_SEQ + 1;
static bool between(seq_nr a, seq_nr b, seq_nr c){
return (((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a)));
}
static void send_frame(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer[]){
frame s;
s.kind = fk;
if(fk == data) s.info = buffer[frame_nr % NR_BUFS];
s.seq = frame_nr;
s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);
if(fk == nak) no_nak = false;
to_physical_layer(&s);
if(fk == data) start_timer(frame_nr % NR_BUFS);
stop_ack_timer();
}
void protocol6(void){
seq_nr ack_expected;
seq_nr next_frame_to_send;
seq_nr frame_expected;
seq_nr too_far;
int i;
frame r;
packet out_buf[NR_BUFS];
packet in_buf[NR_BUFS];
bool arrived[NR_BUFS];
seq_nr nbuffered;
event_type = event;
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
too_far = NR_BUFS;
nbuffered = 0;
for(i=0; i<NR_BUFS; ++i) arrived[i] = false;
while(true){
wait_for_event(&event);
switch(event){
case network_layer_ready:
nbuffered = nbuffered + 1;
from_network_layer(&out_buf[next_frame_to_send % NR_BUFS]);
send_frame(data, next_frame_to_send, frame_expected, out_buf);
inc(next_frame_to_send);
break;
case frame_arrival:
from_physical_layer(&r);
if(r.kind == data){
if((r.seq != frame_expected) && no_nak){
send_frame(nak, 0, frame_expected, out_buf);
}
else{
start_ack_timer();
}
}
if(between(frame_expected, r.seq, too_far) && arrived[r.seq % NR_BUFS] == false){
arrived[r.seq % NR_BUFS] = true;
in_buf[r.seq % NR_BUFS] = r.info;
while(arrived[frame_expected % NR_BUFS]){
to_network_layer(&in_buf[frame_expected % NR_BUFS]);
no_nak = true;
arrived[frame_expected % NR_BUFS] = false;
inc(frame_expected);
inc(too_far);
start_ack_timer();
}
}
if((r.kind == nak) && between(ack_expected, (r.ack + 1) % (MAX_SEQ + 1), next_frame_to_send))
send_frame(data, (r.ack+1) % (MAX_SEQ + 1), frame_expected, out_buf);
while(between(ack_expected, r.ack, next_frame_to_send)){
nbuffered = nbuffered - 1;
stop_timer(ack_expected % NR_BUFS);
inc(ack_expected);
}
break;
case cksum_err:
if(no_nak) send_frame(nak, 0, frame_expected, out_buf);
break;
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf);
break;
case ack_timeout:
send_frame(ack, 0, frame_expected, out_buf);
break;
}
if(nbuffered < NR_BUFS) enable_network_layer();
}
}

我们可以不将序号空间分开看看到底会发生什么
假设n取3,2的三次方为8,序号空间即0~7
S:sender R:receiver

  1. S 发送了0,1,2,3,4,5,6 号帧
  2. R 接受上述帧并且捎带发送 ACK of 6,但是丢失了
  3. S的0号帧首先超时,S 重发发送0号帧
  4. R收到0号帧,但是因为之前它已经接受0~6,发送了ACK of 6,它会认为0号帧是一个新的帧,而在0号帧之前的一个7号帧丢失。因为是选择重传协议,R会接受0号帧( the old)作为新帧(暂时放在缓存区),并通过发送NAK of 7通知S重发7号帧。
  5. S 发送7号帧
  6. R接受了7和0号帧,并且发送ACK of 0

这就出现了问题:1、R接受错误的0号帧作为新的帧 2、S在发送完7号帧之后收到了ACK of 0,而不是ACK of 7,此时对于S而言,它的0号帧早已在ACK of 6中确认。.出现这个问题的主要原因是我们不能区别新旧帧,现在我们将序号空间一分为二,首先发送0~3,继续走上面的步骤。走到步骤4.的时候R不会接受0作为新帧,因为R知道新的帧是4而不是0。这样就避免了上面的问题。
仅仅避免这个问题其实怎么分是都是可以的,我们可以将序号空间三等分,四等分。。。,但是为了尽可能利用资源,均分为两个部分最佳。

总结一下:

  • 我们只想通讯,也就是只想把数据从发送方传输到接收方,这样我们做了乌托邦协议。
  • 但是好景不长,因为接收端经常被数据淹没,这个时候我们就要用到停-等协议,也就是没有接到确认帧不会发送新数据。
  • 但是好景不长,因为确认帧丢失了,我们不得不建立补发机制。
  • 但是好景不长,每台机器只能发送这样太浪费了,我们要求每个机器既能发送也能接收,我们用了一个新的协议,滑动窗口协议。最简单的滑动窗口是发送方和接收方都有一个窗口。
  • 但是好景不长,每次只发一个包真的太浪费网络流量了,这样我们要求每次都发送连续的几个帧,这个急速滑动窗口的最终形态。