计算机网络数据链路层

第三章数据链路层

主要研究

两台相连的机器数据链路层实现可靠、

有效通信的算法

InI

1

主要内容

11数据链路层设计问题

口差错检测和校正

II基本数据链路协议

口滑动窗口协议

口数据链路层示例

2

3.1数据链路层的功能及所提供的服务

•链路：是一条无源的点到点的物理线路段，中间没

有任何其他的交换接点。

•数据链路：把实现这些规程的硬件和软件加到链

路上，就构成了数据链路。

•数据链路层最重要的作用：通过一些数据链路

层协议（即链路控制规程），在不太可靠的物理链

路上实现可靠的数据传输。

在数据链路层数据传输的单位是帧。

3

数据链路层要完成的主要功能

•为网络层提供良好的服务接口

•将物理层的比特流组织成帧

•差错控制

•流量控制

4

3.1.1为网络层提供的服务

U无确认的无连接服务

国有确认的无连接服务

口有确认的面向连接服务

5

通信过程

Host1Host2Host1Host2

4

(3

Virtual

datapath

2

1

(a)(b)

无确认的无连接服务

口源机器向目的机器发送独立的帧，而目的机器对

收到的帧不作确认。

＞不存在连接的建立和释放过程；

＞数据链路层对丢失的帧不作恢复工作

口适用于：

A误码率很低；

A实时性要求高，如语音传输；

7

有确认的无连接服务

E对发送的每一帧进行单独确认，让发送方

知道帧是否安全到达°

A不存在连接的建立和释放过程；

A可提高可靠性；

口适用于：

A不可靠信道。

8

有确认的面向连接服务

口源机器和目的机器在传递任何数据之前，

先建立一条连接；

口在这条连接上所发送的每一帧都编上号，

数据链路层保证所发送的每一帧都确实已

到达；

U保证每帧只收到一次，且所有帧都按正确

顺序接收；

9

口分三个阶段

A建立连接，对双方变量和计数器初始化，

用于追踪帧，哪个帧接收到了，哪个帧

未接收；

A实际的帧传输；

A断开连接，释放用于维护连接的变量、

缓冲区及其它资源；

10

El数据链路层向网络层提供服务，并且使用物理层

提供给它的服务。

■物理层的工作是接收一个原始比特流，并准备把

它交给目的端，不保证比特流无差错；

■数据链路层对物理层传输的差错进行检测或纠错,

一般把比特流分成离散的帧，并对每一帧计算出

校验和，当帧到达目的地后重新计算校验和，相

符无差错，不相符则有差错。

11

3.1.2成帧方法

数据链路层要把比特流分成离散的帧。

把比特流分成帧的方法有：

字符计数法

带字节填充的分界符法

带位填充的分界标志法

物理层编码违例法

在数据链路层，接收端应能从收到的比特流

中准确的识别一个帧的开始和结束。

12

字符计数法

口在帧头部中使用一个字段来标明帧

内字符数

口缺点

计数值有可能由于传输差错而被“篡

改”，已很少采用。

13

字符计数法

5characters5characters8characters8characters

14

带字节填充的分界符法

口每一帧以标志字节FLAG作为开头和结束分

界符；

口一旦丢失同步，只需查找FLAG;

口在传输数据中出现FLAG时，在字符前插入

一个ESC的ASCII码一一字节填充

口缺点

完全依赖于8位ASCII字符

15

带位填充的分界标志法

u每一帧使用一个特殊的位模式,即

01111110作为开始和结束标志字节；

口当发送方的数据链路层在数据中遇到5

个连续的1时，它自动在其后插入一个

。到输出比特流中；

17

带位填充的分界标志法

(a)011011111111111111110010

(b)011011111011111011111010010

、t/

Stuffedbits

(c)011011111111111111110010

(a)原始数据(b)线上数据

(c)删除填充位后接收方存储器内的数据

18

物理层编码违例法

口每个数值位都要在中间进行一次电平

变换，如数据位。编码为低-高电平对,

数据位1编码为高-低电平对，确定位

边界。

19

3.1.3差错控制

口怎样保证所有的帧最终都按正确的顺

序交付给目的机器的网络层？

A发送帧错误

A发送帧丢失

A确认帧丢失

A重复帧

为了保证数据传输的正确性，在计算机通

信过程中通常采用检错重发。

20

3.1.4流量控制

■如何处理发送方的传送能力比接收方

接收能力大的问题？

A发送方运行在相对快速或负载较轻的机

器上，接收方运行在相对慢速或负载较重

的机器

21

思考题

口在大多数网络中，数据链路层通过请求重传

坏帧来处理传输错误.如果一个帧被损坏的

概率为P,在确认帧永远不会被丢失的情况

下，发送一帧所需要的平均传输次数是多

少？

22

3.2基本数据链路协议

口一种无限制的单工协议

・一个单工的停.等协议

口有噪声信道的单工协议

23

3.3.1一种无限制的单工协议

一种不现实的理想协议，也称为“乌托邦”

(utopia)+办议。假定:

»传送和接收方的网络层一直处于就绪状态；

A处理时间忽略不计，

»缓冲空间无限大；

»数据链路层信道中不存在丢失帧和损坏帧的

情况。

24

一种完全理想化的数据传输

:1链路是理想的传输信道。即传输的任何数

据都不会出错也不会丢失。

口不论发方的发送速率多快，收方均能收下

并及时上交主机。

25

乌托邦协议实现

工作过程

口发送程序：取数据，构成帧，发送帧;

typedefenum{frame_arrival}event-type;

#includenprotocol.h"

Voidsenderl(void)

(

frames;

packetbuffer;

While(true){

from_network_layer(&buffer));

s.info=buffer;

to_physical_layer(&s);

26

[1乌托邦协议实现

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

Voidreceiveri(void)

(

framer;

event-typeevent;

While(true){

wait_for_event(&event);

from.physica1-layer(&r);

to-network_layer(&r,info);

J

27

3.3.2一个单工的停-等协议

U现在的情况是：主机A向主机B传输数据

的信道是无差错的理想信道。

口问题：如何防止发送方发送数据过快,

而使接收方来不及处理？

28

一个单工的停-等协议

国如何防止发送过快，使接收过程来不及处理。

A如果接收过程需要△t的时间来执行from-

physicalTayer和to-network-layer,则发送

过程必须以低于每At时间一帧的平均速率进行

传输；

A或者说，如果在接收方的硬件中没有自动的缓

冲和排队功能，那么发送方只有当前一个帧被

from-physical-layer取走后才能传输新的帧，

否则新的帧就会把前一个帧覆盖；

29

一个单工的停-等协议

■要求接收方向发送方提供反馈。

A当接收方把一个分组传给本地的网络层后，向

发送方返回一个短帧（确认帧），允许发送方

发送下一帧；

»发送方在发送完一帧之后，要求等待一段时间,

直到该短帧（确认帧）到达。

发送方发送一个帧，不继续发送帧而等待一个确认,

这种协议就称为停一等协议。

发方发送数据的流量受收方的控制。

30

m单工停-等协议实现

typedefenum{frame.arrival}event-type;

#include,,protocol.h"

Voidsender2(void)

(

frames;

packetbuffer;

event.typeevent;

While(true){

from_network_layer(&buffer);

s.info=buffer;

to-physical-layer(&s);

wait_for_event(ftevent);

r

31

[1单工停-等协议实现

voidreceiver2(void)

framer,s;

event-typeevent;

While(true){

wait_for_event(ftevent);

from-physical-layer(&r);

to-network-layer(&r,info);

to-physical-layer(&s);

}}

32

在这种方式中，收方向发方反馈的信息，

只是回送给发送方的帧的到达的确认，而不需

要有任何具体的内容。只要发回一个没有内容

的信息就能起到流量控制作用。

33

3.3.3有噪声信道的单工协议

在实际中，传输信道并不是可靠的，并且还

需要对数据的发送端进行流量控制。

心"、必”接收方正确接收后，发回一个

发普什发送确认帧，发方发送下一个帧。

一个帧后

发方在一定时间内未收到确认帧

则发方重发此帧1

即有一个定时器进行计时，“一定时间”由

发

收约定长短。这个时间要定的合适，若太短

那么就会发生确认正在路上，而又发了一个

34

*若发方未收到确认帧，是接收方未能正确接收到这

个数据帧呢，还是发回确认帧丢失了呢

接收方要有能力判断是否重复地接收一个同样的

帧。即能区分接到的某一帧是新帧还是重发的帧。

发方的每个待发的数据帧都带上不同的发送序号。

如发送一个新帧序号001,那么收方通过检查这个序号

就可判别：

/是新帧--------接收-

〈是重复帧--------抛弃

（序号相同）

35

对于停等协议，数据帧中的发送序号

以0和1交替出现在数据帧中。

发送方在发送下一个数据项之前，等待一个

肯定的确认的协议，称为PAR或ARQ。

发送端对出错的数据帧进行

重发是自动进行的，所以称为

自动请求重发。

在这个协议下，在发方发送传输一帧并启动

计时器之后，发方所等待发生的情况有3种：

36

①在定时内确认帧无损到达：则发送方发送

下一个数据帧（连同其序列号）。

②受损的确认帧到达，那么发方重发此帧（序

号不会发生变化）。

③计时器超时，还未有确认帧到达，则发方

“超时重发”。

在接收方，在接收到一个数据帧时，即检查

数据帧有无差错，同时检查此帧的序号是否是一

个重复的帧。若是重复帧则抛弃。

37

发送方:

1.取一个数据帧；

2.发送状态变量初始化（清0）；

3.将发送状态变量的数值写入发送序号，将数据帧送交

发送缓冲区；

4.将发送缓冲区中的数据帧发送出去；

5.设置超时定时器（选择适当的超时重发时间）；

6.等待。（等待以下3个事件中最早出现的一个）

7.若收到确认帧，则：取一个新的数据帧；更新发送状

态变量，设为下一个序号；转到3。

8.若收到受损的确认帧（即否认帧），则转到4。（重

发帧）

9.若超时定时器时间到，则转到4。（重发帧）

38

接收方：

1.接收状态变量初始化（其数值等于欲接收的数

据帧的发送序号）；

2等待

3：当收至U一个数据帧，检查有无产生传输差错。

若检查结果正确无误，则继续4否则转到8。

4.若收到发送序号正确的数据帧，则继续5;否

则丢弃此帧，转到7;

5.将收到的数据帧中的数据部分送上交。

6.更新接收状态变量，准备接收下一个数据帧。

7.发送确认帧，并转到2。

8.发送否认帧，并转到2。

39

对于状态变量说明:

①每发送一个数据帧，都必须将发送状态设置

的值（0或1）写到数据帧的发送序号上。

但只有收到一个确认帧后，才更新发送状态

变量一次（0—1或1-0）,并发送新的数

据帧。

②在接收端，每接收到一个数据帧，就要将发

方在数据帧上设置的发送序号与本地的接收

状态变量相比较。若两者相等就表明是新的

数据帧，否则为重复帧。

40

③在接收端，若收到一个重复帧，则丢弃之

（不作任何处理），且接收状态变量不变，

但此时仍需向发送端发送一个确认帧。

④另外，发送端在发完一个数据帧时，必须在

其发送缓冲区中保留此帧的副本。这样才能

在出错时进行重发。只有在收到对方发来的

确认帧后，方可清除副本。

41

3.4滑动窗口协议

•使用同一条线路进行数据的双向传输。在这

种模式下：从A-〉B的数据帧和从B-〉A的确认帧

混在一起，必须查看到达帧头部分的kind字段加

以判断是数据帧还是确认帧。

一种改进：当一个数据帧到达后，接收过程

不是立即发送一个独立的控制帧，而是维持等待，

直到其网络层想发送下一个分组，确认被附加到

即将发送的数据帧上，这种技术称为“捎带技

术”。

42

捎带技术、单独确认帧

■捎带技术有效利用信道的带宽

口捎带技术也带来了单独确认帧所没有的复

杂性。即数据链路层等待多长时间才能把

捎带确认帧发出去?如果等待时间过长，

造成发送方计时器超时，也就违背了确认

的意义。可采用等待一个固定的毫秒数，

在这个时间范围内，新的分组到来则采用

捎带技术，否则以单独分组的形式发出确

次破。

43

滑动窗口协议

[1滑动窗口协议的关键在于：任何时刻发送

过程都保持着一组序列号，对应于允许发

送的帧。这些帧称作在发送窗口(sending

window)之内。相类似的，接收过程也维

持一个接收窗口(receivewindow)对应于

一组允许接收的帧。

44

滑动窗口的概念

动

每

发

帧

含

中

在

窗

个

出

都

滑

包

的

要

B议

口

一

-一

，

列

刻

任

列

个

何

序

时

发

一

组

方

持

着

号

，

篇

号

口

送

许

可

序

帧

着

对

送

应

的

内

。

送

发

些

作

在

允

之

这

有

前

送

内

的

。

当

输

传

发

帧

所

终

在

能

窗

以