计算机网络课件

上海理工大学计算机工程学院

第3章

数据链路层

陈家琪计算机网络-第3章数据链路层2

3.1基本概念

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

任何其他的交换结点。

结点结点

»数据链路：链路+规程（通信协议来控制这些数据

的传输）。

A数据链路层的作用：

■通过一些数据链路层协议（即链路控制规

程），在不太可靠的物理链路上实现可靠的数

据传输。

陈家琪计算机网络-第3章数据链路层3

数据链路层的主要功能

①链路管理：数据链路的建立、维持和释放；

②帧同步：收方能从收到的比特流中区分一帧开始和

结束的地方；

③差错控制：收方收到有差错的数据帧时，能检错重

传或纠错；

④流量控制：发方发送数据的速率必须使收方来得及

接收；

⑤透明传输：不管所传数据是什么样的比特组合，收

方都能正确接收。并能将数据与控制信息分开；

⑥寻址：保证每一帧都能发送到目的站。

陈家琪计算机网络-第3章数据链路层

为网络层提供的服务

①无确认的无连接的服务：

适用于误码率很低的通信信道；或语音通信；

②有确认的无连接的服务：

适用于误码率很高的通信信道；如无线通信；

③有确认的面向连接的服务：

适用于通信要求较高（可靠性、实时性）的情况

陈家琪计算机网络-第3章数据链路层5

差错检测和纠正

差错：接收的与发送的数据不一致。

随机差错：具有独立性，与前后码元无关。

突发差错：相邻多个数据位出错。

差错产生的原因

通信信道的噪声：

①热噪声：由传输介质导体的电子热运动产生。幅

度较小，是产生随机差错的主要根源。

②冲击噪声：由外界电磁干扰产生，幅度较大，

是产生突发差错的主要根源。

冲击噪声是引起差错的主要原因。

陈家琪计算机网络-第3章数据链路层6

差错评价指标

误码率：错传的码元数与所传输码元总数之比。

Pe=Ne/N

其中，N—传输的码元总数，Ne一错传的的码元数

误比特率：

错传的比特数与所传输总比特数之比。

在二进制码元时，误比特率=误码率。

普通电话线路：Pe=IO/〜io-6

大多数通信系统：Pe=10-5〜10-9

陈家琪计算机网络-第3章数据链路层7

差错控制的基本方式

①反馈纠错

在接收端能发现差错，但不能确定错码的位置，通过反

馈信息请求发送端重发，直到接收端肯定确认为止。

适用于双工通信和非实时通信系统。

②前向纠错

在接收端不仅能发现错码，而且还能够确定错码的位

置，并纠正错码。

适用于单工通信和实时通信系统。

③混合纠错

少量差错在接收端自动纠正，若超出自行纠正能力时，

通过反馈信息请求发送端重发。

陈家琪计算机网络-第3章数据链路层8

误码控制基本原理

为了能判断传送的信息数据是否有误，在传送

时增加必要的附加判断数据；在不发生误码的情况

之下，附加判断数据是完全多余的，但如果发生误

码，即可利用信息数据与附加数据之间的特定关系

来实现检错和纠错。

即，为了使数据码具有检错和纠错能力，应当

按一定的规则在数据码的基础上增加一些冗余码（又

称监督码）。

陈家琪计算机网络-第3章数据链路层9

码字的检错与纠错能力

码字（n位）=数据码（m位）+冗余码（r位）。

海明距离：两个码字之间对应码元位的不同码元

的个数。

10001001

㊉10100011

00101010

有3位不同，所以，海明距离=3

陈家琪计算机网络-第3章数据链路层10

码字编码的海明距离

对于一种码字编码，在这个码字集合中，可得到

所有任意两个码字的海明距离，其中最小的海明距离

称为该码字编码的海明距离（L

定理L如果d>2t+l,则该编码可纠正任何t个（或t个以

下）的错误。

定理2：如果d>e+l,则该编码可检测出任何©个（或e个

以下）的错误。

一般情况下，冗余位越多（即r越大），检错纠错

能力越强，但相应的编码效率也随之降低了。

陈家琪计算机网络-第3章数据链路层11

示例：偶校验的检错与纠错能力

例：对于偶校验（使每个码字中都有偶数个1）

数据码为2位（有用数据为00、01、10、11）

冗余码为1位（偶校验位）

有用数据经过偶校验编码，其码字集合：

000、OIL101、110;

该编码的海明距离d=2,

根据定理1,该编码不能纠正任何错误（t=0）。

根据定理2,该编码可检测出任何1个错误（e=l）o

寄校验的检错能力与偶校验一样。

陈家琪计算机网络-第3章数据链路层12

误码控制编码的分类

按冗余码的控制功能分：

①纠错码：在接收端能发现并自动纠正差错。

②检错码：在接收端能发现差错。

纠错检错的常用方法

①海明码：可纠错和检错，实现复杂，效率低。

②奇偶校验码：方法简单，检错能力差。

③循环冗余编码(CRC):实现容易，检错能力强，广

泛使用。

陈家琪计算机网络-第3章数据链路层13

检错码：循环冗余码一CRC码

特点：实现容易，检错能力强，广泛使用。

常结合反馈重传法来保证信息的可靠传输。

码字组成：

数据码CRC校验码

发送的码字…b2b03・・・r2rlr0

n位

编码与解码的计算采用二进制比特序列多项式。

二进制比特序列多项式：

m1

M(x)=bm_1x'+…+小声'+...+bjX+b0

其中，力产0或I,5共机位

陈家琪计算机网络-第3章数据链路层14

例：若数据码=110011,

可表示为:M(x)=1-x5+l9x4+0・%3+0-x2+1-x+1

即：M(x)=x5+x4+x+1o

生成多项式G(x):

r

G(x)=g^+...+g^+...+g产+g0

其中,g产。或I,r>i>0,g,wO>g°w0,共r+1位

G（x）被通信双方事先共同选定使用：

发送端：通过6（切生成校验码；

接收端：通过仃⑴校验接收的码字。

对于多项式的运算：采用模2计算（加法不进

位，减法不借位）；加减法是一样的。

模2计算即是异或运算。

陈家琪计算机网络-第3章数据链路层15

在发送端：

1.生成校验码:

把要发送的数据码M⑴V去除G（x）,所得的余

数值就是循环冗余码（简称CRC校验码）。

M(x)-xrR(x)。⑴为商

=。(%)+

G(x)G(x)尺⑴为余数（CRC校验码）

M(x)-xr-l?(x)G⑴共r+1个bit位,

=e（x）

G(x)•*-共r个bit位

2.发送R(x):即-R(x)

实际上，把CRC校验码&x）附加到数据码■⑴

的后面，就构成编码多项式然后爰

送传输。

陈家琪计算机网络-第3章数据链路层16

在接收端：

接收到M(x)-xr+R(x)后，按如下操作进行校

验：

M(x)-xr+R(x)〜、E(x)。⑴为商

--------------------=0(x)4--------,人

G(x)G(x)石⑴为余数

=0无错

W0有错

陈家琪计算机网络-第3章数据链路层17

CRC示例1：发送端

例：设数据码版㈤=110011,

采用生成多项式G(x)=x4+x3+l(即11001),r=4

发送端：求CRC校验码

M(x)-xrR(x)

=。(%)+

G(x)G(x)

100001―商Q(x)

G(x)->11001/1100110000M(x)-xr

11001多项式运算采用

10000二进制模二算

11001法，

1001—余数R(x)即，异或运算

发送码：M(x)xr+R(x)=1100111001

数据位校验位

陈家琪计算机网络-第3章数据链路层18

CRC示例1：接收端一无差错

接收端:采用生成多项式G(x)=M+-+1(即iiooi)

接收到M(x)-xr+R(x)后，按如下操作进行校

验：人人

M(x)-xr+R(x)=。(外+^^。㈤为商

G(x)E(x)为余数

=0无错

w0有错

100001―商Q(x)

G(x)-^11001/1100111001<-收到的发送码而(%)./+我(%)

z11001

11001

11001

余数成再无差错！

陈家琪计算机网络-第3章数据链路层19

CRC示例1：接收端一有差错

发送端发出的码字=1100111001

接收端收到的码字=1100100001,

突四错

100001―商Q(x)

G(x)-^11001/1100100001收到的码字曲(x).M+公(%)

'11001

00001

11001

—11000—余数£(x)

£(x)wO,检测到差错!

陈家琪计算机网络-第3章数据链路层20

CRC示例2：发送端

例：设数据吊㈤=11100110,G(x>11001,r=4

求CRC校验码K(x).・

10110110―商Q(x)

G(x).11001/111001100000<—M(x)-xr

111001

10111

11001

11100

11001

发送码：10100

M(x)-xr+R(x)11001

=11100110011011010

11001

陈家琪计算机网络-第3章数据链路层21

流行的生成多项式有:

CRC-8:G(x)=x8+x2+x+l

CRC-12:G(x)-x12+xn+x3+x2+x+l

CRC-16:G(x)=x16+x15+x2+l

CRC-CCITT:G(x)=x16+x12+x5+l

检测能力：

所有单个错、奇数个错和离散的二位错。

所有长度4r位的突发差错。

CRC的实现：

①硬件：采用多段移位寄存器及异或门组成CRC

校验电路来实现。

②软件：通过快速CRC校验软件来实现。

陈家琪计算机网络-第3章数据链路层22

3.2停止等待协议

数据链路协议主要考虑的问题:

①避免所传送的数据可能出现差错和丢失；

②使发方发送数据的速率适应收方的接收能力。

陈家琪计算机网络-第3章数据链路层23

理想化的数据传输

假设1:所传送的数据即不会出现差错和也不会丢

失；（不考虑差错控制问题）

假设2:接收端的数据接收速率足够快，有能力接

收发送端的数据发送率。

发送端接收端

（不考虑流量控制问题）

在理想化的条件下，数据链路

层不需要：

①差错控制协议；

②流量控制协议；时

就可保证数据的正确传输。间

陈家琪计算机网络-第3章数据链路层24

最简单流量控制的停止等待协议

保留假设1;去掉假设2。考虑流量控制问题f流量控制协议

使发送端发送数据的速率适应接收端的接收能力。

最简单流量控制协议

在发送节点：发送端接收端

①从数据链路层的发送缓存中取一个数据帧；

②发送这个数据帧；

③等待；

④若收到由接收端的应答信息，转到①。

在接收节点：

①等待；

②接收由发送端发来的数据帧；

③将其存入数据链路层的接收缓存；

④发送应答信息，表示数据帧已接收；转到①

陈家琪计算机网络-第3章数据链路层25

实用的停止等待协议（ARQ）

去掉假设1;去掉假设2。

考虑差错控制问题f差错控制协议；

考虑流量控制问题f流量控制协议；

初步协议：

①发送端发送数据帧后，等待接收端的应答帧；

②接收端收到数据帧后，通过CRC校验（一般用硬件检验）,

如果无差错，回送一个确认帧ACK,

否则，回送一个否认帧NAK。

③发送端收到应答帧，

如果是ACK,发送下一数据帧，

如果是NAK,重发数据帧。

陈家琪计算机网络-第3章数据链路层26

(a)正常情况

死锁现象:

当出现帧丢失时，发送端永

远等待下去。如何解决？发送端接收端

解决方法：

发送端设立一个超时计时器，

发送完一个数据帧时，就启动

它；

如果在规定时间tout内得不到应答

帧，就判定为超时，重传数据

帧。

Tout也称重传时间

（C）数据帧丢失

陈家琪计算机网络-第3章数据链路层28

重复帧差错:

发送端接收端

若应答帧丢失，按照超时

重发方法，接收端将收到重复

帧，如何解决？

解决方法：

给每个数据帧附加不同的

发送序号Ns,如果接收端收到

相同序号的数据帧，则丢弃，并1F

回送一个ACK。

(d)应答帧丢失

数据帧：帧头HiNs数据CRC帧尾

其它附加控制信息

陈家琪计算机网络-第3章数据链路层29

发送序号需要多少位？

对于ARQ协议，发送序号有0和1即可(只需1个bit);

每发一个送新的数据帧，发送序号就和上次发送的不一样,

重发的数据帧发送序号不变。

L^QUt

状态序号S,O->10

发送端I重重

帧序号NS'E

接收端_

状态序号丁oOfl

DlD2丢弃重复帧D2D3

if(Ns==R)接收else丢弃

S-发送端本地状态序号(Ibit)。

R-接收端本地状态序号(lbit)o

Ns-发送端附加到数据帧上的序号(lbit)o

陈家琪计算机网络-第3章数据链路层30

ARQ协议:

接收端

一重传

一重传

变序号-»

一变序号

陈家琪计算机网络-第3章数据链路层31

重传时间tout的选择

若Tout太长，浪费时间，

若Tout太短，过早重传数据，产生“额外”应答帧。

，toutJ,额外”应答帧

状态序号11：1.011工'o4fI】

发送端^v^x/XA/XA/一

帧序号NS'A/叉X义及叙

接收端\添\泵,

状态序号iio^i1111LoL1,

差错丢弃丢弃

如何解决？

提示：在确认帧ACK和否认帧NAK中附加序号。

陈家琪计算机网络-第3章数据链路层32

停止等待协议的信道利用率

设：单程传输时延Td,

传输时间

数据帧发送时间疗,

;等待时间

数据传输率C,数据帧长度L,Td,Td:

八.工皿方总时间一等待时间

信道利用率Cr=--------------------------

传送一帧的总时间

忽略应答帧长度和处理时间：

C”.=1

疗+2"1+2T"C

L

数据帧L越短，信道利用率越低。

陈家琪计算机网络-第3章数据链路层33

示例

例：卫星信道：

单程传输时延Td=250ms,

数据传输率。=50kb/s,

数据帧长度L=lkbit,

信道用1用率Cr=―1--=--------------------相=3.8%

…一”"50x103

1+2Tdl+2x0.250--------

vLIxlO3

例：若，Td=20ms,C=4kb/s,

要使信道利用率达到50%,L=?

,2Tdecr2X20X10-3X4X103X50%

L---------------=-----------------------------------=160(bit)

1-Cr1-50%

陈家琪计算机网络-第3章数据链路层34

3.3连续ARQ协议

目的：提高信道利用率。

方法：

发送端发送完一个数据帧后，不停下来等待应答

帧，而是连续再发送数据帧。当收到否认帧NAK时，

再控制重发。

实现要求：

数据帧需附加发送序号信息。否认帧附加出错的

数据帧发送序号。

常用协议：

①回退N帧ARQ协议(gobackn)

②选择重发ARQ协议(selectiverepeat)

陈家琪计算机网络-第3章数据链路层35

回退N帧ARQ协议(gobackn)

①方式1：

反馈否认帧NAK(含出错的数据帧发送序号)。再

从出错的数据帧开始重传。

往返时间退回3步重传

榭

攵

山

立

而

要求：发送端要求有一个能存储N个数据帧的缓冲区。

接收端只需能存储一个数据帧的缓冲。

陈家琪计算机网络-第3章数据链路层36

②方式2:

不反馈否认帧NAK。发送端采用超时机制。

发送端每发送一个数据帧就启动该帧计时器，

当收到确认帧后，计时器复位；如果直到超时

还没有收到确认帧，则重发该数据帧及后继的

帧。

T(l)T(2)T(3)T(2)T(3)T(3)T(3)

启动启动启斐复位tout时时启动复位

发

接

差错

陈家琪计算机网络-第3章数据链路层37

3.4选择重发ARQ协议(selective

repeat)

目的：进一步提高信道利用率。

方法：只重传出现差错的数据帧或者超时的数据

帧。

要求：在接收端要设置具有相当容量的缓存空间。

重传

送

发

榭

攵

差错、丢弃与4,5号一并送入上层

暂存于缓存中

陈家琪计算机网络-第3章数据链路层38

选择重发ARQ协议一工作原理示意图

陈家琪计算机网络-第3章数据链路层39

滑动窗口协议(SlidingWindows)

对于连续ARQ协议，采用了发送端不等待确认

帧返回就可连续发送帧，存在问题：

①当未被确认的数据帧数目太多时；只要有一帧出

错，就有很多数据帧需要重传，因而增大开销。

②为了对发送出去的大量未被确认的数据帧进行编

号，每个数据帧的发送序号也要占用较多的比特

数，因而又增大了开销。

滑动窗口协议：

对发送端已发送出去但未被确认的帧的数目加以限

制。

在发送端和接收端分别设置发送窗口和接收窗口。

陈家琪计算机网络-第3章数据链路层40

发送窗口（在发送端）

目的：用来对发送端进行流量控制。

发送窗口尺寸Ws：在还没有收到应答帧的情况下,

发送端最多可以连续发送数据帧的个数。

发送序号：

一般采用n位bit进行编号（0~2U）。

若n=3;则用3位bit进行编号（0~7）。

陈家琪计算机网络-第3章数据链路层41

•发送端只能连续发送窗口内的数据帧；

•每收到一个确认帧后，发送窗口的前、后沿顺时针

旋转一个号，并可以一个发送新的数据帧。

•若未应答帧的数目等于发送窗口尺寸时，便停止发

送新的数据帧。

发送0~4号数据帧，收到0号确认帧，又收到1~3号确认帧，

若没有收到它们的发送5号数据帧，继续发送6、7、0号数据帧。

确认帧，则停止发送。等待1~5号确认帧。

陈家琪计算机网络-第3章数据链路层42

接收窗口（在接收端）

目的：用来控制可以接收哪些数据帧而不可以接收哪

些帧。

接收窗口防：只有当收到的数据帧的发送序号落入接

收窗口内，才允许将该数据帧收下；否则，丢

收到0号数据帧后，

等待接收0号数据帧并发出0号确认帧又收到1~3号数据帧后,

等待接收1号数据帧。并发出1~3号确认帧，

等待接收4号数据帧。

陈家琪计算机网络-第3章数据链路层43

如果Wr=l9意味着只能按顺序接收数据帧。

如果防较大，有可能会出现数据帧的失序。

差错情况：设防=1；

若收到0号数据帧，接收窗口顺时针旋转一个号，

并发出0号确认帧；准备接收1号数据帧。

此时，如果收到的不是1号数据帧：

而是0号数据帧，表明发出0号确认帧发送端没有

收到，因此再发送一次0号确认帧，此时收到的0号数

据帧必须丢弃，否则发生重复。

若是2号数据帧，表明发送端发出的1号数据帧丢

失，因此发送1号否认帧，让对方重新发送1号数据

帧。

陈家琪计算机网络-第3章数据链路层44

应答帧丢失情况

,»/»*XL±111

Ws=2发送顺接收端Wr=2送

0234567上

层

回234567D0

返

01234567「ACK1034567D1

D01园4567

重发D1ACK2D2

0叵34567

012回567

ACK1

012回567D3D1丢弃

D4

012回567!D3

D4

101234^~6]7j

陈家琪计算机网络-第3章数据链路层45

应答帧被“篡改”情况:ACKfNAK

小、乎J.UJ

Ws=2发送顺接收端Wr=2送

上

0234567DO_

层

叵234567

ACKODO

0[11]34567ACK10垣34567D1

重发D1—NAK1

0五3456701园4567

DI------ACK2D2

'f012回567

0回34567ACK1

D1丢弃

瓯

012567D3

D4

012回567D3

D4

陈家琪计算机网络-第3章数据链路层46

…应翻被“篡改”情况：NAKfACK

接收端Wr=2缓

冲

叵234567D0

区

D1叵234567

ACK0D0

0叵34567

01234567D2NAK1

ACK1

0[0]34567

01[23]4567D3_-ACK2D2

•0[0]34567

012|34|567D4NAK1

回退，重发D1D3丢弃

_--0-卮34567

0[12|34567D1JNAK1

重发D1D4丢弃

0[12]34567ACK1o[rr|34567D1

01|2-1]4567

D2品,ACK^01|23|4567

丢弃ACK1

01[23]456701[2314567D2D3

0123fTT|67

0123[TT]67D4D5

陈家琪计算机网络-第3章数据链路层47

重叠问题

在接收前后，接收窗口范围内的有效序号出现重

叠。

Ws=4发送端接收端Wr=5

01234567

帅231456f

木

重复Dl~3丢弃

应答帧全部丢失

陈家琪计算机网络-第3章数据链路层48

避免重叠问题

为了避免重叠问题，接收窗口尺寸防42口/2。

Ws=4发送端接收端Wr=4

01234567

0123|4567

丢弃

应答帧全部丢失

陈家琪计算机网络-第3章数据链路层49

发送窗口的最大尺寸值

Ws=8发送端接收端Wr=4

0123R567

012314567

0123|4567

0123|4567

重复帧D0~7

应答帧全部丢失

所以，WSV2LL

陈家琪计算机网络-第3章数据链路层50

累积确认方法

接收端在连续接收若干个正确的数据帧以

后，对最后一个数据帧发回确认帧。

陈家琪计算机网络-第3章数据链路层51

窗口控制协议的信道利用率

两类情形:

发送窗口Ws=7

发送窗口Ws=4

陈家琪计算机网络-第3章数据链路层52

窗口控制协议的信道利用率

设：单程传输时延Td,数据帧发送时间7J,

数据传输率C,数据帧长度L,窗口尺寸Ws

在正常传输情况下，忽略应答帧长度和处理时间:

当ws・7y>2nz+7y时：CEOO%

3廊均

当Ws・7y〈2Td+2y时：

发送端I0|1|2|345

CL肱•疗二肱

~Tf+2Td1+2TdC

L接收端iI0I1I2.

LTd]Tf\_血」

显然，Ws越大，信道利用率越高。||||

陈家琪计算机网络-第3章数据链路层53

依据信道利用率进行窗口尺寸的选择

优化原则：

发送端收到窗口中第一个已发数据帧的确认时，正

好发完窗口中的最后一个数据帧。

Ws

由

Cr=r

l+2Td—

L

令0=100%

C

Ws^2Td—+l

L

Ws大于上述选择，贝40=100%,但浪费缓冲区；

Ws小于上述选择，则Cr<100%,发送端需要等待应

答而使发送停顿。

陈家琪计算机网络-第3章数据链路层54

示例

例：卫星信道：

单程传输时延Td=250ms,

数据传输率。=50kb/s,

数据帧长度L=1000bit,

窗口尺寸=—+1=2x0.25^—^-+1=26

阉LIxlO3

例：若，Td=20ms,C=56kb/s,Ws=8,L=?

2x0.02x56xl03

数据帧长度上=答了«320(bit)

Ws-18-1

在已知条件不变的情况下，设置L=160bit,信道

利用率如何？

陈家琪计算机网络-第3章数据链路层55

ARQ协议、连续ARQ协议的窗口尺寸

ARQ协议：

发送窗口Ws=L接收窗口Wr=l

连续ARQ协议：

•回退N帧ARQ协议：

发送窗口那＞1,接收窗口Wr=L

・选择重发连续ARQ协议：

发送窗口那＞1,接收窗口Wr＞L且Wr《Ws。

陈家琪计算机网络-第3章数据链路层56

3.5协议描述和测试

1.协议开发过程

协

议

协议设计

标

准

文

本协议综合

协议形式描述

协

议协议验证

性

能协议实现

评

价

协议测试

陈家琪计算机网络-第3章数据链路层57

协议的形式描述

描述方法：

①有限状态机

采用状态流程图进行描述。

②事件状态表

采用表格进行描述。

③结构化程序

采用程序代码进行描述。

④Petri网模型

采用状态流程图进行描述。

陈家琪计算机网络-第3章数据链路层58

有限状态机模型FSM

FSM协议描述方法也称状态转移图。

特点：易懂、易理解和易于实现。

组成：状态圆和有向弧。

输入事件1；输出事件1输入事件2

注：输入事件2不产

生相应的动作，所以

输出事件为空

陈家琪计算机网络-第3章数据链路层59

等待式ARQ协议一状态转移图

发送u而：

本地操作：[1]=启动定时器，[2]=本地状态序号S加1

[3]=复位定时器

收到ACK;

收到NAK;[1],重发数据帧

接收端：

本地操作：[1]=本地状态序号R加1,[2]=送网络层

收到数据帧一；NAK收到数据帧+；[1],[2],ACK

陈家琪计算机网络-第3章数据链路层60

等待式ARQ协议一状态转移图

ACKO丢失3°丢失

DO丢失状态定义

00-00

7

07

5X:发送端发送的数据帧

1

r00。01AY:接收端准备接收的数据帧

初始状态Z:信道上的数据帧

正常收发

42

3转换定义

10A111

1,2,3,4:正常收发

6D1丢失07:超时重发DO

008

8:超时重发D1

10111「5:丢弃DO

丢弃

QD1丢失6:D1

ACK1丢失

陈家琪计算机网络-第3章数据链路层61

事件状态表

由状态转移图发展而来。

结构：

事件事件1事件2事件n

当前状背•••

状态1••••••••••••

状态2••••••••••••

•••••••••记录ij•••

状态m••••••••••••

记录包含的内容：

①任何必须满足的条件;

②事件发生后的动作；

③进入的新状态。

陈家琪计算机网络-第3章数据链路层62

等待式ARQ协议一事件状态表

,/、2.1X1

友送乂而:

事件网络层收到收到

超时

当前状基来数据ACKNAK

空闲1000

等待确认0233

注：

0二出错情况，空闲

1二启动定时器，本地状态序号S加1,发送数据

帧，等待确认

2=复位定时器，空闲

3二启动定时器，重发数据帧，等待确认

陈家琪计算机网络-第3章数据链路层63

等待式ARQ协议一事件状态表

接收疆

事件收到

当前状忐数据帧

等待1

注：

1=PO&P1:送网络层，R力口1,发送ACK

NOTPl:发送NAK

Pl&NOTP0:发送ACK

其中，逻辑判定变量：

P0数据帧序号Ns=本地状态序号R

P1数据帧的校验正确

陈家琪计算机网络-第3章数据链路层64

Petri网模型

德国C・A.Petrit提出（1962,博士论文）。

4个基本元素：

1.位置：系统可能处于的状态；用圆圈表示。

2.转换：改变状态；用线段表示。

3.有向弧：位置与转换之间的相互依赖关系；用弧线表示。

4.标记：系统当前处于的状态；在圆圈中用黑点表示。

转换

陈家琪计算机网络-第3章数据链路层65

C:Seq0ontheline

D:Ackontheline初始化系统，发送第。帧

E:Seq1ontheline

1—发送第0帧

c第0帧在名

EmitOProcess0

02—超时

发送接收

3—发送第1帧

WaitExpect1

for丢失接收第14—超时

Ack0

TimeoutReject0

等待5一第。帧丢失

超时丢弃

6—Ack帧丢失

Ack链路上7一第1帧丢失

D

翳11Process18一丢弃第。帧

Ack

接收9一丢弃第1帧

丢失10一接收第0帧

等待Loss

WaitExpect011一接收第1帧

forE第M贞在链路上接收第0巾

Ack1

Timeout

1Reject1

超时丢弃

丢失

发送端7Loss接收端

Y....................

Sender's信道ChannelReceiver's

state