上课课件-第4章-数据链路层

第四章数据链路层2013-10-241本章重点：正确理解数据链路层的相关概念和基本功能；掌握相关差错控制及流量控制的基本原理；为什么需要数据链路层如果链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失，那么数据链路层协议是可以不需要的。但是，这可能吗？需要数据链路层的理由：传输数据的信道是不可靠的（即不能保证所传的数据不产生差错），并且还需要对数据的发送端进行流量控制。如果不管发送方以多快的速率发送数据，接收是来得及收下，并及时上交主机，那么数据链路层协议也是可以不需要的。但是，这可能吗？2013-10-242基本概念要解决的问题如何在有差错的线 ，进行无差错传输。ISO关于数据链路层的定义数据链路层的目的是为了提供功能上和规程上的方法，以便建立、

和

网络实体间的数据链路。链路（link）：通信路径上连接相邻结点的通信信道称为链路。数据链路层协议定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。2013-10-243数据链路（Data

Link）层的主要功能是在物理层提供的通信线路连接和比特流传输功能的基础上，在相邻两台计算机之间在链路层上提供可靠和有效的通信。广域网中数据链路层的问题，属于“点到点”链

的数据传输

。2013-10-2444.1

数据链路层的设计问题数据链路层必须具备一系列主要功能：对网络层提供严格定义的服务接口，在两个网络实体之间提供数据链路连接的建立、维持和

；将需要传输的比特组装成数据链路层中的数据单元——帧（frame）；以及控制帧在物理链的传输，主要是处理帧的同步、传输差错和调节帧的流速，以使发送速率与接收方的接收能力相匹配。2013-10-2454.1.1

向网络层提供的服务2013-10-246网络层实体数据链路实体物理层网络层实体数据链路实体物理层DL-SAPDL-SAP网络层数据链路服务数据链路层数据链路连接传输介质图4-1

数据链路层结构及其服务为网络层提供三种合理的服务无应答式无连接服务，适用于误码率很低的线路，错误恢复留给实时业务大部分局域网；应答式无连接服务，适用于不可靠的信道，如无线网。面向连接的服务2013-10-2474.1.2

帧的构成帧的构成（考虑帧的同步问题）1．字符2．带字符填充的起始字符和终结字符法（附图）3．带位填充的起始/终结标志法（附图）（附图）2013-10-248字符计数的组帧方法2013-10-249字符计数一个字符现在的一个字符计数（b）有一个差错字符计数的组帧方法5

1

2

3

4

5

6

7

8

9

8

0

1

2

3

4

5

6

8

7

8

9

0

1

2

3第一帧

第二帧

第三帧

第四帧5个字符

5个字符

8个字符

8个字符（a）无差错出错5

1

2

3

4

7

6

7

8

9

8

0

1

2

3

4

5

6

8

7

8

9

0

1

2

3第一帧

第二帧（错误的）5个字符返回字符填充的组帧方法2013-10-2410DLESTXADLEBDLEETXDLESTXADLEDLEBDLEETXSTXADLEBDLEETXDLE(a)(b)(c)填充的DLE字符填充的组帧方法（a）网络层发出的数据；（b）经数据链路层填充后的数据；（c）数据传送给接收方的网络层返回位填充的组帧方法(a)

0(b)(c)

0111011111100填充的位01110位填充的组帧方法(a)

原始数据；(b)

线上数据；(c)

接收方器内的数据返回2013-10-24114.1.3

差错控制差错控制（1）向发送方提供有关接收方接收情况的反馈确认信息，表明发送的帧是否正确收到。如果发生差错，相应的帧必须重发。（2）链 的某个帧可能会完全丢失，如果协议规定发送方传出一帧后必须等待对该帧的确认，则显然一旦帧发生丢失，发送方将会 等下去。因此，必须在数据链路层中引入超时机制。（3）然而，如果所传出的帧或者返回的确认帧发生了丢失，则发送方会多次重发同一帧，这将造成接收方可能两次或多次收到重复的帧，因而可能将同一帧多次交付给网络层。为了防止这种情况发生，必须对发送的各帧进行顺序

，这样接收方就能判别是重复帧还是新帧。2013-10-24124.1.4

流量控制2013-10-2413流量控制如果发送端传送速率高于接收端处理速度，即使传输无差错，则也可能引起帧的丢失，为此必须防止此类情况发生。通常的方法是引入流量控制（简称流控）来限制发送方所发出的数据流量，使其发送速率不超过接收方能处理的速率。这种限制通常需要某种反馈机制，让发送端知道接收端能否继续接收。4.2

差错检测和纠正有三种差错控制方法可供选择：前向差错控制也称前向纠错（FEC）。接收端检测到接收信息有错后，通过一定的运算，确定差错的具体位置，并自动加以纠正。反馈重发或称自动重发请求（ARQ）。接收端检测到接收信息有错后，通过反馈信号要求发送端重发原信息，直到接收端肯定确认为止，从而达到纠正差错的目的。纠检混合的差错控制方式。接收端对少量的接收差错自动纠正，而超过纠正能力的差错则通过反馈重发的方法加以纠正。注意：无论采用哪种差错控制方法，都要在原有信息中

冗余度才能实现纠错或检错。2013-10-24144.2.1

差错检测的基本概念2013-10-2415汉明（Hamming）定理二进制对称信道（BSC）分组码和卷积码信源信源编码信道编码信道信道译码信源译码信宿噪声源数字通信系统模型01ppBSC信道转移概率qq10分组码示意图nk幀信息序列n-k幀校验序列hamming(汉明)距离在一个码组集合中，任意两个码字之间对应位上码元取值不同的位的数目定义为这两个码字之间的汉明距离。即d(x,y)=∑x[i]⊕y[i]，这里i=0,1,..n-1，x,y都是n位的编码，⊕表示异或例如，(00)与(01)的距离是1，(110)和(101)的距离是2。两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U

和V的距离为4。在一个码字集合中，任意两个编码之间汉明距离的最小值称为这个编码的最小汉明距离。最小汉明距离越大，码组越具有

能力。2013-10-2416汉明定理用d表示码组的最小汉明距离1。当码组用于检测错误时，设可检测e个位的错误，则d

>=

e

+

12。若码组用于纠错，设可纠错t个位的错误，则

d>=2t+13。如果码组用于纠正t个错，同时检测e个错，则

d>=2t+e+12013-10-2417设码长为n，信息位长度为k，监督位长度为

r=n-k。如果需要纠正一位出错，因为长度为n的序列上每一位都可能出错，一共有n种情况，另外还有不出错的情况，所以须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2^r种情况。因此2^r>=n+1，即r>=log(n+1)2013-10-2418分组码：可以把数据信息分成组，每一组的校验位是由同一组的信息位进行线性变换得到的，它只对本组的信息位实行一致性校验。奇偶

、循环码、BCH码、汉明码均属于分组码。卷积码：在信息码中

的校验位不仅实行本分组校验，每一校验位还对前后分组中的信息位起校验作用。2013-10-24194.2.2

奇偶奇检验偶检验二维奇偶校验列校验位行校验位块校验位信息位b80

1

0

1

1

1

1

1

0

00b711111111110b601011110111b50110

*00*00000b400010101100b31

1

0

0

*

0

1

*1

0

0

11b210100111001b111101010111字符校验位二维奇偶示意图2013-10-24202013-10-24214.2.3

循环冗余码建立在严格的代数理论的基础上，基本方法是用代数多项式来表示码字（1）对于一种循环码，其中的任何两个码字按模2相加后，形成的新序列仍为一个有用码字（2）一个码字的每次循环移位一定也是码集合中的另一个码字生成多项式的最高幂次决定了检错能力G(x)=X^r+…..CRC码基本思想校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。循环冗余码的生成多项式G(x)

（CRC码，多项式编码）110101，表示成多项式G(x)=x5

+x4

+x2

+1生成多项式G(x)发方、收方事前商定；生成多项式的

和低位必须为1生成多项式必须比传输信息对应的多项式短。2013-10-2422循环冗余校验(CRC)的生成生成CRC采用模2除（模2减采用异或运算）如数据比特序列为10010111,G(x)=11010111110100CRC

的比特序列为1001011100100在接收将这个比特序列除以110101，余数为0则传输正确，否则表示传输错余数110101

1001011100000110101

100001110101

101001

110101

111000

110101

110100

110101

001002013-10-24232013-10-2424利用CRC-16或CRC-CCITT的16位的校验位，可以捕捉到：所有的1位、2位及奇数位的差错、所有长度小于和等于16位的突发错、99.997%的17位突发错、

99.998%的18位或更长位数的突发错在通讯与网络中，有如下国际标准的生成多项式：CRC-12=X12+X11+X3+X2+X1+1CRC-16=X16+X15+X2+1(IBM公司）CRC-16=X16+X12+X5+1（CCITT）CRC-32=X32+X26+...+1(ETHERNET)CRC编码的实现：1961年后已经采用了硬件技术4.3

反馈重发差错控制2013-10-24254.3.1

三种ARQ方案通常处理传输差错的办法如下：（1）肯定确认。接收端对收到的帧校验后未发现错误，回送一个肯定确认信号，用ACK表示，发送端收到ACK信号后即知道该帧传输成功。（2）否定确认。接收端收到一个帧后，经校验发现有错误，则回送一个否定确认信号，用NAK表示，发送端收到NAK后必须重发该帧。（3）超时重发。发送端在发出一个帧后开始计时，如果在规定时间内没有收到关于该帧的确认信号（ACK或NAK），则认为发生帧丢失或确认信号丢失，必须重新发送。1．等待式（S-&-W）ARQ送上层送上层重发出错送上层丢失超时重发送上层丢失不送上层超时重发送上层（a）

（b）（c）

（d）等待式ARQ方案中数据帧在链

的传输（a）正常情况（b）数据帧出错（c）数据帧丢失（d）应答帧丢失2013-10-2426应答帧的问题超时超时丢失送主机送主机送主机送主机主机送主机时间╳丢弃╳丢弃╳丢送弃发送站接收站等待式ARQ示例2013-10-2427等待式ARQ的传输效率低考虑一个单程 时延为250ms，速率为50Kbit/s的信道，设数据帧的长度为1000比特。在t=0ms时刻，发送端开始发送第一帧，直到t=20ms时，该帧才完全发送完毕。当t=270ms的时刻，帧才完全到达接收端。如果忽略确认帧的长度和接收端

的处理时间，应该到t=520ms时，发送端才能收到确认帧。这也就意味着数据传输过程中有500/520即96%的时间链路处于空闲状态，只利用了4%的链路有效带宽。因此，等待式ARQ方法为了获得通信的可靠性而牺牲了传输效率，过于浪费信道的有效带宽。2013-10-24282．回退N帧(Go-Back-N)ARQ连续重发请求是指发送端连续发送一系列信息帧，不等前帧确认便发下一帧。因此，连续重发请求方案把等待时间利用起来，传输效率大大提高。然而在实现上相应地需要更大的缓冲空间。有两种基本方法可用来处理重发请求：回退N帧ARQ选择性重发ARQ2013-10-2429回退N帧ARQ方案的示例2013-10-2430退步重传往返时间

退

步重传发端

1

2

3

4

5

6

7

8

9

3

4

5

6

7

8 9

10

11

1213收端1

2

3

4

5

6

7

8

9

3

4

5

6

7

8 9

10

11

12╳

╳送主机送主机丢弃丢弃送主机错误错误回退N幀ARQ的工作原理3.选择性重发ARQ2013-10-2431重传往返时间发端

1

2

3

4

5

6

7

8

9 3

10

11

6

1212收端与~11号一并送主机送主机出错，丢弃暂存于缓冲中暂存与4, 5号一并送主机选择性重发ARQ的工作原理1

2

3

4

5

6

7

8

9 3

1011 6

12╳

╳

╳

╳╳

jp4.3.2

通信效率假设链路传输速率为R，链数据传输的有效速率Re：正确接收的比特数Re

传输这些比特的总时间R

eR

P[需j次传输]

pej

1(1

pe)j1j

1

(1e11

pepe)

Nt

pe

1

(1

p)KRTs

K

na

2(t

p

tta)K/Rtptta

tp

ttana/R数据链路的时延分析时间2013-10-24322(t

p

tta)1.等待式ARQ的有效速率等待式ARQ较适合于短链路和传输速率不高的场合，对于较长的地面链路，传输速率较低时，通信效率较高，但当传输速率增高时，通信效率显著下降。对于链路，即使在传输速率较低的情况下，通信效率也较低，当传输速率增加时，效率极低。由此可见，等待式ARQ不适合于链路和地面高速率的数据链路。

K

na

2(t

p

tta)R

K nh

K

nh

(1 pe)(K

nh)R

NT

Ts

1

K

naRe(12a)T(T

2t

p)11

pe

RRe

K

K(1 pe)1

peR

Re

K(1

pe)

1 pe

(T

2t

p)R

12a

Ta

t

p2013-10-2433NT

1

Npe(1

pe)2Npe

2(1Npe

1(N2013-10-2434pe)1)penh)RRe

1(N

1)pe

K

1N

1p

KeN

Ts

22.回退N帧ARQ的通信效率(1

pe)(K

nh)1N

1peK

1

1K

penh1

(1pe

pe)(K1

peRK

RKR2013-10-24353.选择性重发ARQ的通信效率Re

KK nh

1

peK

nhR

1

1

pe

1

peK

nhK4.4

滑动窗口式流量控制2013-10-2436流量控制是一种协调发送端和接收端工作的技术，其目的是避免发送速度过快，使得接收端来不及处理而丢失数据。协调发送和接收的速率匹配连续性ARQ中，必须对已发送出去但未被确认的数据帧的数目加以限制（浪费资源、附加的帧序号开销大）通常接收端维持一定大小的接收缓冲区，当接收到的数据进入缓冲区后，接收端要进行简单的处理，然后才能清除缓冲区，再开始接收下一批数据。4.4.1

帧确认的滑窗式流控2013-10-2437滑窗式流控主要思想是：允许连续发送多个帧而无需逐个地等待应答，每个要发送的帧都包含一个序号（n位）。在传送过程中，循环重复使用已收到确认的那些帧的序号。在发送端和接收端分别设置发送窗口和接收窗口。窗口机制是实现数据帧顺序控制的逻辑过程，需要通信两端设置一定的缓冲区，用于保存已发送但尚未被确认、或者期望接收的数据帧。发送窗口2013-10-2438012W-1后沿前沿012W-1后沿前沿接收窗口滑动窗口示意图发送窗口：任何时刻发送端都保持着一组序号，对应于在还没有收到对方确认的条件下最多允许发送的帧。接收窗口：对应于一组允许（或期望）接收的帧。2013-10-2439滑动窗口协议主要工作原理

发送的信息帧都有一个序号，从0到某个最大值，0

~

2n

-1，一般用n个二进制位表示；

发送端始终保持一个已发送但尚未确认的帧的序号表。发送窗口，对应于在还没有收到对方确认的条件下最多允许发送的帧的序号范围。发送窗口的上界表示要还能发送的帧的最大序号，下界表示等待确认的帧的最小。发送窗口大小

=上界

-下界，大小可变；

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

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

接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。接收窗口2013-10-2440滑窗式流量控制举例2306657575754016

27DATA

0DATA

1DATA

2DATA

3DATA

4DATA

5DATA

6DATA

7DATA

020Ws=72Ws=4Ws=7

6Ws=1Ws=35

34发送窗口Ws—发送窗口大小4040403ACK

0ACK

1ACK

2

765765ACK

3ACK

4

7注：第5,6,7,0帧已接收，但仍在缓冲区中，尚未处理。接收端可

以通过反

馈确认帧

的速度来

调整或限

制发送窗

口的大小，达到流量

控制的目的当接收窗口保持不动时，发送窗口无论如何也不会前进。只有接收窗口前进后，发送窗口才有了前进的可能为了减少开销，接收端不一定每收到一个正确的数据帧就必须返回一个确认帧，而是可以在连续收到几个正确的数据帧以后，才对最后一个数据帧发回确认帧对错误帧和重复帧的处理比较复杂一些2013-10-24412013-10-2442窗口最大值与序号位长的关系0

1

2

3

4

5

6

7

0

1(a)

无差错的传送

(b)

应答幀全部丢失应送主机发端收端送主机（a）端发012345670

1端收×××××××应丢弃重传超时超时送主机（b）发送窗口的最大值与幀序号的关系发送方发送0-7为接收方成功接收，从

而接收方窗口清空，期待新的0-7帧；但是由于ACK丢失，从而发送方超时重发

旧的0-7，这不是接收方期待。从而滑

动窗口流控失败！本质上接收 方无法区分是否ACK丢失。

min1

2a

2013-10-2443窗口大小对传输效率的影响发端收端滑窗流控的链路利用率W=7（a）W>2a+1的情况(a=2)4

5

6

7

0

1

2

30

1

2

3时间发

01

23456701234端收端

τ0T12345670123时间W=40

1

2

3（b）W<2a+1的情况(a=2)0

1

2

3

4

5

6

7τ

T忽略ACK帧的长度,1