第三章數據鏈路層

實現相鄰機器間的的可靠、有效通

信

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號幀