计算机网络-数据链路层

第三章数据链路层

实现相邻机器间的的可靠、有效通

信

2数据链路层设计的问题

•为网络层提供服务

一无确认的无连接服务

-有确认的无连接服务

-有确认的面向连接服务

•成帧

-比特流分成离散的帧，每一帧计算校验和

•差错控制

-处理传输错误

•流量控制

-调节数据流，确保慢速的接收方不会被快速的发送方淹（g

F

胞无确认的无连接服务

•无确认是指接收方在收到数据后，毋需发回

一个确认

•无连接服务是指在数据传输前，毋需建立逻

辑链路

■物理线路的连接并非意味着提供有连接的

服务

•无确认并非不可靠，由上层负责

I

_____■

力宥确认的面向无连接服务

•使用前不建立连接，即不建立数据链路但传

输的信息必须得到确认

•这在信号传播延时较大、线路状态不一定很

可靠的情况下是有效的

早有确认的面向连接服务

•使用前先建立连接，即先建立数据链路，并

且每帧的传输必须得到确认

•有连接的服务必须在使用前先建立连接（即

建立逻辑链路）然后使用，最后释放

N数据帧的组成

数据帧的组成必须保证能识别一个完整的帧，

并保证一旦出现传输差错导致前一个帧丢

失，必须能识别下一个帧即再同步。

­字符计数法

•带字符填充的首尾界符法

­带位填充的首尾标志法

・物理层编码违例法

$

N字符计数法

把帧的长度用一个字节表示作为帧的头部

帧长度计数错

33

51243678980124568789()123

第1帧第2帧第3帧第4帧

融字符填充的首尾界符法

电'

用特殊的字符作为帧头和帧尾

如三STXMynameisJohnETX

接收方一旦丢失了帧信息只要查找就可重

新确定帧边界

1)1.1:STXM11amejsJ0ncDLE1：T.\

1()024D79206E616D65206973204A6F6E651003

F

面向字符的帧格式

¥

•这是一种面向字符的帧格式，所传输的数据都是字

符（ASCH字符或EBCDIC字符），在帧内容中不允

许出现帧同步字符，在面向字符的异步串型通信中

常使用这种格式。

•面向字符的帧格式不适宜传输数据中包含二进制

数的帧，因为在包含二进制数的帧中很可能出现

DLESTX等字符o

•一种方法是在二进制数中偶然出现的DLE前再插

入一个DLE。这就称为字符填充。

带位填充的首尾标志法

•在面向二进制位的同步串型通信中常使用带位填充的首尾

标志格式，如HDLC

-这是一种面向二进制位的帧格式，把所有需传输的数据（不论是

ASCH字符还是二进制位串）一字排开，并以特殊的位模式

01111110作为帧标志，即一个帧的开始（同时标志前一个帧的结束）

-当帧内容中出现一个与帧标志相同的位串01111110,则在5个1后

插入一个0,即变成01111101,接收方将自动删除第5个1后的0。称

为位插入法，或透明传输

-如果由于干扰，一个帧没有正确接收，则可扫描接收串一旦扫描到

01111110,即新的一帧从此开始。即可以再同步

N物理层编码违例法

•在曼切斯特编码中，连续高电平或连续低电平可用

作帧边界

•采用冗余编码技术，如曼切斯特编码，即两个脉冲

宽带表示一个二进制位

•数据0：低-高电平对5

•数据1：高-低电平对m

•高-高电平对和低-低电平对没有使用，可用作帧边

界，在令牌环网中使用编辑违例格式

N可靠性传输

■差错控制］:校验和重发

-帧的正确性保证:帧的校验

-传输正确性保证:超时和重发

•流量控制：窗口协议帧

-发送方和接收方之间的协调

■协议描述和验证

I~311

N差错控制

•如何保证数据帧的正常传输:通过三种手段

处理三种可能出现的情况：

-确认

-数据帧丢失

-重复帧

N确认

•接收方在收到了正确的帧后向发送方发肯

定性确认。如收到的帧有问题，则发否定性

确认，此时发送方将重发此帧

•确认的前提是经差错检测，帧是正确的

■

N差错检测和校正

•超时只是传输出错的一种情况，更多的传输

出错是数据中的一位或几位因噪声干扰而

出错

•噪声分两种

-信道所固有的、持续存在的随机热噪声

-外界突发原因而造成的冲击噪声

■通常接收方应能检错、甚至纠错

纠错码是除m个数据位外增加r个冗余位作

为校验位，整个长度为n=m+r

N纠错码和检错码

•纠错码

-附加的冗余信息足够使接收方推导出已发出的字符应

该是什么；

-海明(Hamming)码

•检错码

-附加的冗余信息使接收方知道有差错发生，但不知错在

哪里，要求重传；

-校验和(CheckSum)

-块校验码(BlockCheckCode)

-循环冗余检错码CRC(CyclicRedundancyCheck)

N海明码

•海明距离:两个码字中不同的位的个数

■N位码字:m个数据+r个冗余校验位二n

•奇偶校验:在数据后面加一个奇偶位，使码

字内1的个数为偶数。

-单比特错都会产生奇偶位不正确的码字

•海明码用于定位哪一位不正确，但只能纠正

单个位的差错_____寸

海明（Hamming）纠错码

*

•m个数据位外加r个纠错位。

•在20=0,1,23.・）的位置放的是纠错位。

•m个数据位的次序不变。

•如字符m的7位二进制码为1101101要加上4位纠

错码0011（偶校验），共11个bit

1110987654321

A7A6A5P4A4A3A2P3A1P2Pl

11001100111

信息位影响的纠错位

•一个信息位影响多个纠错位

信息位信息组位组位展开影响的纠错位

A711=8mi对P4、P2、P1有影响

A610=8+2对P4、P2有影响

A59=8+1对P4、P1有影响

A47=4+2,1对P3、P2、pitr影响

A36=4+2对P3、P2有影响

A25=4+1对P3、P1有影响

对、有影响

A1=2+1P2P1»

N纠错位的取值

•一个纠错位由多个信息异或然后取偶/奇校

验

纠错位纠借位的取值（再取偶/奇校验）

P4=A7㊉A6㊉A5

P3=A4㊉A3㊉A2

P2=A7㊉A6㊉A4㊉A3㊉A1

P1=A7㊉A5㊉A4㊉A2㊉A1

r

海明码纠错位取值举例

•采用偶校验

检错位纠错位的取侑（再取偶校验）

P4=A7㊉A6㊉A5=0

P3=A4㊉A3㊉A2=0

P2=A7㊉A6㊉A4㊉A3㊉A1=1

P1=A7㊉A5㊉A4㊉A2㊉A1=1

■

1110987654321

A7A6A5P4A4A3A2P3A1P2P1

11001100111

N接收方的校验

校验位校验位计算表达式

S4=A7㊉A6㊉A5㊉P4

S3=A4㊉A3㊉A2㊉P3

S2=A7㊉A6㊉A4㊉A3㊉AI®P2

SI=A7㊉A5㊉A4㊉A2㊉AI㊉PI

•计算结果S4s3s2sl为0000意味着接收正确

•计算结果S4s3s2sl为0101意味着第5位出错

N接收方的校验举例

・字符m采用海明码的发送序列为11001100111

111。98765(4371

A7A6A5P4A4A3A2P3AIP2P1

11；00：1110111

校验位校验位计算表达式的值

S4=A7©A6©A5©P4=1㊉1®0©()=0

S3=A4㊉A3㊉A2④P3=1㊉130㊉()=0

S2=A7®A6©A40A3®A1©P2=101®I©1®1®1=0

S1=A7©A5©A4©A2®A1㊉P1=100©1©0©1㊉1=0

S4S3S2S1=000()意味校验正确

接收方的校验举例

・如接收到的序列为11001110111

,

111()98764D21

A7A6A5P4A4A3A2P3\\P2P1

110011I1011I

校验位校验位计算表达式的值

S4=A7©A60A5©P4=1©100®()=0

S3=A4®A3®A2®P3=1®1010O=1

S2=A70A6©A40A3®A1㊉P2=101©101®1©I=0

S1=A7©A5©A4©A20A1®P1=100©1©1®1©1=1

S4S3S2SI=0101意味第5位出错

校验和

•算法简单实现容易但检错率不高

-将发送的数据看成是二进制整数序列，并划分成一段段

规定的长度（如8位、16位、32位等），计算他们的和。如

校验和大于规定的长度，则将进位加到最后的校验和中。

-将校验和和数据一起发送。

-在接收端，重新计算校验和，与原校验和比较。

•如要传输"Helloworld.”

HeII0LJ\\oiId

48656C6C6F20776F726C642E7I1()

以16位为例：

4865H+6C6cH+6F20H+776FH+726cH+642EH+进位二71FCH

块校验码

块校验码BCC(BlockCheckCode)简单常用，但检

错的强度较弱，如在同一列上有偶飘位错，则不能

检测

-如传输的数据都是ASCH字符，每个字符进行奇偶校验,

然后把所有的字符(连同奇偶位)进行异或运算，运算结

果即为其块校验码。

-发送端一面发送一面计算，最后发送块校验码

-接收端一面接收一面计算，最后与接收到的块校验码比

如“Helloworld.*采用偶校验，校验后的字符序列为:

HC1101_1\\011d

48656C6C6FA0776F726CE42E2L

48H㊉65H①6cH㊉6cH96FH㊉A0H㊉77H36FH㊉72H

①6cH，㊉E4H82EH=2EH

2循环冗余检错码CRC

・任何一个k位的帧看成为一个k-1次的多项式M(x),如

1011001看成x6+x4+x3+x。

•设定一个多项式编码生成多项式G(x),G(x)为r阶k>r

•如xrM(x)/G(x)=Q(x)+R(x)/G(x),其中Q(x)为商、R(x)为

余数，R(x)为M(x)的CRC码

■将CRC码接在帧后一起发送，即发送数据为

•xrM(x)+R(x)

•在二进制运算中，减法和加法都做异或运算即

0+1=1,1+1=0

•因为便1\/1(刈-1刈)一定能被6(刈整除，即余数为0,则接收

方只要计算的余数为0即为正确

3HCRC码计算举例

如一帧为1101011011

即M(x)=x9+x8+x6+x4+x3+x+1

G(x)=x4+x+1

T(x)=x4M(x)

=x4(x9+x8+x6+x4+x3+x+1)

=x13+x12+x1°+x8+x7+x5+x4

IF

NCRC码计算举例

N

11010110110000/10011

=1100001010……1110

即11010110110000+1110能被10011整除

(模2运算的加、减和异或，其运算结果相同)

如发送方发送的M(x),接收方收到的是M(x)

+R(x),除非M(x)+R(x)是G(x)的整倍数，否

则不能被整除，即都能被检测到已出错

I

_______________________■

F

，立个生成多项式的国际标准

1,

•CRC-12:x12+x11+x3+x2+x1+1

用于字符长度为6位

•CRC-16:x16+x15+x2+1

用于字符长度为8位

•CRC-CCITT:x16+x12+x5+1

用于字符长度为8位

K循环冗余校验检测差错

b循环冗余校验(CyclicRedundancyCheck,CRC)技术

•计算CRC的硬件使用两个简单的部件：

-一个移位寄存器(shiftregister)

-一个异或(exclusiveo「或xor)单元。

about

000

011

101

110

shiftregistershiftregister

valuetobeoutputinputoutput

shiftedinvalueshiftsinchanges

(b)

号'模块联接

二所有移位寄存器中的值都被初始化为0,并且消息的位串一次移入

一位

•在整个消息都被移入该设备后，移位寄存器中包含消息的16位CR

Co

・接收计算机使用相同的硬件来计算一个接收到的消息的CRC,并

且证实它是否与发送计算机传输的CRC相一致。

•为了简化对CRC的校验，标准CRC算法对上述机制进行了很小

的修改一当计算CRC时，发送方在消息末尾临时附加16位0。

从数学上来看，CRC使用一个以X的事表示的多项式来除消息。

图6-10所对应的多项式为：

X)=X16+¥2+g+_l»

N差错控制

•如何保证数据帧的正常传输。通过三种手段

处理三种可能出现的情况：

-确认

-数据帧丢失

-重复帧

N数据帧丢失

•通过发送方（超时）计时器解决

・超时（TimeOut）：在传输过程中，所发送的帧

丢失，接收方根本没有收到，不可能发送确

认帧（包括否定性确认）。而发送方正在等待

接收方的确认帧，当然也不可能等到接收方

的回音。所以，发送方一旦发送一帧，就启

动一计时器，在规定的时间内，一般都应收

到回音，如收不到回音，则在计时器溢出时,

再重发此帧

N重复帧

•重发机制也包括当接收方发送的确认帧丢

失而导致发送方的重发

•由于接收方确认帧的丢失，导致发送方多次

发送同一帧，接收方也将多次收到同一帧，

要能区别是否是同一帧，则每帧都应有一个

帧的编号

针可靠性传输

•差错控制:校验和重发

-帧的正确性保证:帧的校验

-传输正确性保证:超时和重发

・流量控制:口协议帧

-发送方和接收方之间的协调

■协议描述和验证

N流量控制

•发送方和接收方速率的匹配即流量控制

-如接收方的处理能力低于发送方，即使传输中

没有出错，也可能被“淹没”，所以通常在接收方

的缓冲区到达一定量时，应及时通知发送方，暂

停发送，等候通知，这就是流量控制机制。

-基本数据链路协议

一滑动窗口协议

N基本数据链路协议

•可以这样理解:在一台主机中物理层、数据

链路层、网络层等等都有各自的进程在运行。

并且假设：

•AB两台主机要求可靠的、面向连接的通信。

在接收方的数据链路层，循环调用过程

wait_for_event(&event),即等待某个事件

发生一一

时ah_for_event(&event)的参数

•发生了某个事件，此过程将返回参数event,

有两个取值：

一checksum_err

•如event=checksum_err意即所接收的帧的校验

和错，应考虑不发送确衣帧或发送否定性确认帧

一frame_arrival

•5nevent=frame_arrival即帧已到达并校验正确，

贝U调用from_physical_layer从物理层取得帧，检查

帧头的控制信息，如一切正常，则仅把其中的分组交

网络

帧的基本格式

•一般意义上的帧的格式

typedefstruct{

frame_kindkind;

seq^_nrseq;

seq^_nrack;

packetinfo;

}frame;

帧类型顺序号确认号分组

帧头-------

湎'议1一种无限制的单工协议

•一种理想的环境，理想的协议。假定

-链路是理想的传输通道，所传输的任何数据既

不会出错也不会丢失

-即不需校验，也不可能重发

•不管发送方以怎样的速率发送数据，接收方

都能及时接收

-即处理器的处理速度无限高，处理时间可忽略

不计，缓冲区空间无限大，毋需流量控制

voidsenderl(void)voidreceivel(void)

((

frames;framer;

packetbuffer;event_typeevent;

while(true){while(true)

from_network_layer(&buffer);(

s.info=buffer;wait_for_event(&event);

to_physical_layer(&s);from^physical^ayer(&r);

}一~to_network_layer(&r.info);

)一一

)

}

曷亦议2:一个单工的停-等协议

1,

•然而接收方不可能具有足够高的CPU处理能力来

及时处理所有的接收帧，也不可能具有足够大的缓

冲区。但仍假定：

-链路是理想的传输通道，所传输的任何数据既不会出错

也不会丢失

-即不需校验，也不可能重发

•所以当它来不及处理时，应通知发送方暂缓发送，

一旦可以继续接收，则通知发送方继续发送

voidsender2(void)voidreceive2(void)

((

frames;framerzs;

packetbuffer;event_typeevent;

event_typeevent;while(true)

while(true)

wait_for_event(&event);

(

from_network_layer(&buffer);from_physical_layer(&r);

s.info=buffer;to_network_layer(&);

to_physical_layer(&s);to_physical_layer(&s);

wait_for_event(Sevent);)

}

出、议3有噪声信道的单工协议

•在噪声信道中应考虑传输有差错的情况

•所谓差错

•帧的损坏;如帧中若干位出错，通常CRC都能检测到

■帧完全丢失;一旦帧头出错，接收方将检测下一个帧

头以同步，但该帧已丢失

•所以发送方应启动一个计时器超时即再发

送

协议3的要点

•发送方要记录下一个准备发送的顺序号

•接收方要记录下一个期望接收的顺序号

•发送过程和接收过程是严格交替的

•也称为ARQ协议automaticrepeatrequest

•即使接收到的不是期望的帧，只要接收到一个正确

的帧，都将发送一个空的确认

voidsender3(void)voidreceives(void)

((

next_frame_to_send=0;frame_expected=O;

from_network_layer(&buffer);

while(true){

while(true){wait_for_event(&event);

s.info=buffer;if(event==frame_arrival){

s.seq=next_frame_to_send;from_physical_layer(&r);

to_physical_layer(&s);if(r.seq==frame_expected){

start_time(s.seq);to_network_layer(&);

wait_for_event(&event);inc(frame_expected);

if(event==frame_arrival){}-

from_network_layer(&buffer);to_physical_layer(&s);

inc(next_frame_to_send);

)

}-

}

)}

}

议3的重发机制存在的问题

•效率较低

-如接收方收到的帧出错，或者整个数据帧丢失，

则不发确认帧，发送方在超时后重发，直至正确,

效率极低

・接收方会收到重复帧

-如接收方收到了正确的收到了数据帧并发送了

确认帧，但此确认帧丢失，发送方在超时后重发

此帧，这样，接收方的数据链路层收到两个完全

相同的帧

•对重复帧仍发确认造成发送方误解

冽子

超时

d

一一I

发送方

>

发重收发收发

送收发发到送重发到收发

帧到送帧确帧收送确送到送

确确

A

A认

B

A

A认确

i帧

帧7

/

g认

7

—上上

4

一一一一一髓

----------------------

N传输失败的原因

・发送方:A帧，A帧，B帧，C帧

■接收方:A帧，A帧，C帧，A帧重复，B帧丢失

•A帧重复问题:计时器的时间间隔应足够长,

即Timeout的初值应足够大

•B帧丢失问题:B帧丢失，接收方没有收到，

无法确认，而且发送方也没有感觉，无法重

发，主要原因是确认帧为空帧，尤其没有顺

序号

国协议3的问题

・不能双向传输

•由于应答无序号，导致系统不可靠

・效率低

5

滑动窗口协议

•双向传输

■数据帧编号，发送方和接收方维持一组序列

号，对应发送窗口和接收窗口

•发送窗口中的序列号代表已经发送但尚末

确认的帧

•接收窗口对应于允许接收的帧，任何落在窗

口之外的帧被丢弃

*4(void)

erame_to_send=0;

expected=0;

fromj_network_layer(&buffer);

s.info=buffer;

s.seq=next_frame_to_send;

s.ack=l-frame_expected;一位滑动窗口协议

to_physical_layer(&s);

start_time(s.seq);Next_frame_to_send

while(true){

wait_for_event(&event);Frame_expected

if(event==frame_arrival){

from_physical_layer(&r);只能为0或1

if(r.seq==frame_expected){

to_network_layer(&r,info);

inc(frame_expected);

)一确认通过“捎带”返回发送

if(r.ack==next_frame_to_send){方

from_network_layer(&buffer);

inc(next_frame_to_send);

}———

}

s.info=buffer;

s.seq=next_frame_to_send;

s.ack=l-frame_expected

to_j>hysical_layer(&s);start_time(s.seq);

}

)

主机A发送,主机B等待

•初始化后组成发送帧•初始化后尚未组成发

其中送帧，在接收到A0帧后

交网络层，并组成发送

帧，（捎带确认）其中

•发送帧顺序号seq=O

•对接收到的帧的确认

ack=1•发送帧顺序号seq=O

•实际上此确认无意义•对接收到的帧的确认

ack=O

•通过物理层发送

•通知AO帧收到

*A端首先发送B端等待发送

A发送（。,1.A0）、SeqackA发送AO,seq=O

B收到(0.1,AO)AB收到JAO

B发送(0,0,BO)B发送BO,并确认A0

A收到(0,0.B0)▲/rA收到BO及对AO的确认

八发送。・0.AI）、A发送Al及对BO的确认

B收到(1.0,Al)▲B收到八1及对BO的确认

B发送(1,1,Bl)B发送Bl及对Al的确认

A收到(1,1,Bl)PA收到Bl及对Al的确认

八发送（0.1.A2）、A发送A2及对Bl的确认

B收到(0,1,A2)▲B收到八2及对Bl的确认

B发送(0,0,B2)B发送B2及对A2的确认

A收到(0,0.B2)▲，八收到B2及对A2的确认

A发送。・0,A3）、八发送八3及对B2的确认

B收到(1,0,A3)▲B收到八3及对B2的确认■n

B发送(I.UB3)

BxA端和B端都同时发送

⑨'___________

A发送(0.1.AO)、/B发送(0,1.BO)B也已从网络层得到BO

B收至lj(0,1,AO)▲B以为B（）分组A没有收到

//B发送(0,0.BO)所以B又重复BO分组

A收到(0.1,BO)/人以为A0分组B没有收到

人发送(0.0.AO)、/

所以A又重复A0分组

B收到(0.0.AO)▲B收到A0及对B0的确认

1/B发送(1,0.Bl)B发送B1及对A0的确认

A收到(0,0,B0>▲'/人收到B0及对A0的确认

A发送(1.0,Al)、/

A发送A1及对B0的确认

B收到(1,0,Al)▲B以为B1分组A没有收到

/

B发送(1,I.Bl)所以B又重复BI分组

A收到(I.0,Bl)▲‘八以为八1分组B没有收到中

A发送（l,LAl）、所以人又重复A1分组

B收到(1.1.Al)▲

B发送(0,1.B2)

N

退后n帧的协议

•协议4的主要问题是信道利用率太低，发送

端的等待时间至少是发送端到接收端传播

时间的二倍

•信道的利用率为：发送时间/来回时间

•管道化pipelining:在等待确认的时间内继续

发送

•存在的问题:信道不可靠，使发送端在意识到

数据丢失时，已有大量数据到达接收端中

”退后n帧协议(gobackn)

•当接收端发现一错帧后，抛弃此帧及以后所

有收到的帧，不发确认。当发送端出现超时

后，重发自该帧起的所有帧

・问题:浪费带宽

•发送方连续发送了7帧，2〜8,但2#帧无确

认超时后，从2#帧起开始重发

后退n帧协议的图释

voidsender5(void){

enable_network_layer();ack-_expected

ack_excepted=0;

next_frame_to_send=0;

frame_excepted=0;

nbuffered=0;

while(true){

wait_for_event(&event);

switch(event){

casenetwork_layer_ready:Next_frame

_to_send

network_layer_ready^bSI

caseframe_arrival:frame_arrival处理

casecksum_err:;

casetimeout:timeout处理

}

if(nbuffered<MAX_SEQ)

enable_network_layer();

elsedisable_network_layer();

}_____2____2_____-—■n

)

_layer_ready^bS

twork_layer(&buffer[next_frame_to_send]);

^nbufffered=nbuffered+1;

lhend_data(next_frame_to_sendzframe_expected,buffer);

inc(nextframetosend);

Frame_arrive处理

from_physical_layer(&r);

if(r.seq==frame_expected){

to_network_layer(&);

inc(frame_expected);

}一

while(between(ack_expected,r.ack,next_frame_to_send)){

nbuffered=nbuffered-1;

stop_timer(ack_expected);

Timeout处理

next_frame_to_send=ack_expected;

for(i=l;i<=nbuffered;i++){

send_data(next_frame_to_sendAframe_expectedzbuffer);

inc(next_frame_to_send);

)

选择性重传协议

•有一个差错时仅重发一帧

N选择性重发窗口协议

■接收方定义了一个辅助计时器，如果辅计超

时前无反向通信，发送单独的应答；

•当接收到一个错帧（包括CRC错或帧序号错）

时发送一个否定性确认NAK

•帧格式中增加帧类型字段

voidsender6(void)

(

enable_network_layer();

ack_expected=O;

next_frame_to_send=0;

frame_expected=O;

too_far=NR_BUFS;

nbuffered=0;

for(i=0;i<NR_BUFS;i++)arrived[i]=false;

waitforevent(&event);

switch(event)

(

casenetwork_layer_ready:

发送处理一一

caseframe_arrival:

帧到达处理

casecksum__err:

if(no_nak)send_frame(nak,0,frame_expected,out_buf)

casetimeout:

send_frame(data,oldest_frameAframe_expected,out_buf);

caseack_timeout:

send_frame(ack,0,frame_expectedrout__buf);

}-

if(nbuffered<NR_BUFS)enable_network_layer();

else

na-workl.ayarO_____.._~F

发送数据处理

nbuffered=nbuffered+1;

/*取新的分组*/

from_network_layer(&out_buf[next_frame_to_send%NR_BUFS]);

/*发送该帧*/

send_frame(data,next_frame_to_send,

frame_expected,out_Jouf);

inc(next_frame_to_send);/*发送窗口的前沿+1*/

from_pha1_1ayer(&r);

==data){

i>C[(,(t.seq!=frame_expected)&&no_nak)

X〉swra_frame(nakz0,frame_expected,out_buf);

■elsestart_ack_timer();

if(between(frame_expected,r.seq,too_far)&&

(arrived[r.seq%NR_BUFS]==false)){

arrived[r.seq%NR_BUFS]=ture;

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=ture;

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_expectedzout_buf);

while(between(ack_expected,r.ack,next_frame_to_send)){

nbuffered=nbuffered-1;

st的gtimer(ack_expected%NRJLLES)----

i9CTack_expected);

协议6例子

•考虑一种情况n=3即帧号为01234567发送窗

口和接收窗口的大小均为7

•发送方连续发送了7帧，帧号为0123456,然后

等待确认

•在尚未接收到帧前，接收窗口为0123456。发

送方发送的7帧正确地收到后，接收方发出了确认

6,意即。〜6帧全部收到，然后取出分组交网络层,

清缓冲区，并调整窗口为7012345

•发送方一直在等待确认，但确认帧由于某种原因失

踪了，在超时后，发送方重发0123456,并等待确认:

法协议6例子（续）

•接收方收到0123456帧，认为是第二批来的帧，照正常

处理，发现012345均在其接收窗口内，当然接收，并存

入缓冲，6丢弃。但由于应首先到达的7未到，所以只能发6

ack,意即再次确认上次收到的0〜6

•但在发送方来看，收到了6ack后才知道重发的0〜6总算

收到了，于是调整窗口为7012345,从网络层取分组，

并发送第二批帧

•接收方在收到7012345后，发现012345帧已在缓存

中，是重复的，应丢弃7,接收然后交网络层，清缓冲区，调

整接收窗口

•此时，接收方的网络层发现数据链路层交来的第二批分组

卜议6当WT=WR=7失败的原因

2

•原因在于接收窗口过大，新窗口与原窗口中

的有效顺序号有重叠

•所以通常:发送窗口+接收窗口=2n

且发送窗口>=接收窗口

N协议6更具实用性

•发送窗口=接收窗口=(MAX_SEQ+1)/2

-接收窗口过大，新窗口与原窗口中的有效顺序号有重叠

会造成失败。

•协议6中增加了否定性确认NAK,当收到一个坏帧,

或收到一个非期望的帧，则发一个NAK帧

•协议6中增加了一个辅助定时器，当收到一个正确

的帧，而没有可捎带确认的数据帧，当辅助定时器

超时，则立即发送一个ACK帧

I~311

N协议描述与验证

•由于实际使用的协议非常复杂，需有形式化

的和数学的方法来验证协议的正确性

•有限状态机模型(finitestatemachine)

•Petri网模型

H

有限状态机模型

•协议机(protocolmachine):包括发送方和接收方

・有限状态机把协议形式化为一个四元组(S,M,I,T)其中：

-s：进程和信道可能进入的状态集合

-IVk能在信道上进行交换的帧的集合

-I:进程初始状态的集合

-T:两两状态之间转换的集合

•每个系统状态都可分解为:发送方状态、接收方状态、信道状态

­状态在发生某个事件时，可能会转换到另一个状态，把状态作为节点，转换用

有向线段表示，则协议的状态图是一个有向图

•有向图中的节点(状态)是一个三元组(发送方状态，接收方状态，信道状态)

协议3的有限状态机模型

发送方状态0发送了。号帧

1发送了1号帧

接收方状态0期望接收。号帧

1期望接收1号帧

信道状态0信道上有。号帧

1信道上有1号帧

A信道上有ACK帧

S信道上没有任何

，议3有限状态机状态变迁图

2

4收ACK发02收ACK发1

事件和状态变迁表

编号事件简称事件动作状态变迁

0数据丢失信道出错，造成帧丢失无(XXX，(XXS)

。号帧到达正期待。号领接收。号帧.改期待帐号为1,

1接收（）号帧(000)+(01A)

的接收方并向信道发ACK

ACK女到达发送。号帧接收ACK帧，发送帐号改为1,

发送1号帧(01A)+(l11)

的发送方并从网络层取分组发送1号帧

1号帧到达正期待1号帧接收1号帐.改期待帐号为。，

>接收1号帧(111)+(10A)

的接收方并向信道发ACK

ACK独到达发送1号帧接收ACK帧，发送帧号改为0,

4发送。号帧(10A),(000)

的发送方并从网络层取分组发送。号帧

0号帧到达正期待1号坝从信道取下0号帧,拒收，即不

5拒收。号帧(010)+(01A)

的接收方交网络层，并向信道发ACK

1号帧到达正期待0号帧从信道取下1号帧,拒收,即不

6拒收1号帧(101)+(l0A)

的接收方交网络层，并向信道发AC'K

发送。号帧的发送方等

7里发0号帧重发。号帧(OXS).(0X0)

待ACK计时器超时

发送1号帧的发送方等

8里发1号帧重发1号帧