《計算機網(wǎng)絡(luò)》第3章數(shù)據(jù)鏈路層

計算機網(wǎng)絡(luò)

第3章數(shù)據(jù)鏈路層

第3章數(shù)據(jù)鏈路層

*3.1數(shù)據(jù)鏈路層的基本概念

*3.2停止等待協(xié)議

3.2.1完全理想化的數(shù)據(jù)傳輸

3.2.2具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議

3.2.3實用的停止等待協(xié)議

3.2.4循環(huán)冗余檢驗的原理

3.2.5停止等待協(xié)議的算法

3.2.6停止等待協(xié)議的定量分析

［第3章數(shù)據(jù)鏈路層（續(xù)）

*3.3連續(xù)ARQ協(xié)議

3.3.1連續(xù)ARQ協(xié)議的工作原理

3.3.2連續(xù)ARQ協(xié)議的吞吐量

3.3.3滑動窗口的概念

3.3.4信道利用率與最佳幀長

3.4選擇重傳ARQ協(xié)議

第3章數(shù)據(jù)鏈路層（續(xù)）

I-

*3.5面向比特的鏈路層協(xié)議HDLC

3.5.1HDLC協(xié)議概述

3.5.2HDLC的幀結(jié)構(gòu)

*3.6因特網(wǎng)的點對點協(xié)議PPP

3.6.1PPP協(xié)議的工作原理

3.6.2PPP協(xié)議的幀格式

3.6.3PPP協(xié)議的工作狀態(tài)

數(shù)據(jù)鏈路層的簡單模型

*主機乩向“發(fā)送數(shù)據(jù)

路由肅修空由器R路由器R3

--------心呼乂一一三主機電

局域網(wǎng)一j-廣域網(wǎng)

從層次上來看數(shù)據(jù)的流動

應(yīng)用層做用層

運輸層［輸層

網(wǎng)絡(luò)層岡絡(luò)層

鏈路層較各層

物理層理勿理層

數(shù)據(jù)鏈路層的簡單模型

（續(xù)）

主機乩向“發(fā)送數(shù)據(jù)

路由器

主機Hl—一空」俟由哭R路由器“3__

--------大呼里-------主機電

局域網(wǎng)一J--廣域網(wǎng)

僅從數(shù)據(jù)鏈路層觀察幀的流動

應(yīng)用層女用層

運輸層,亙輸層

網(wǎng)絡(luò)層I網(wǎng)絡(luò)層

物理層L理層物理物理理層

3.1數(shù)據(jù)鏈路層的基本概念

■鏈路(link)是一條無源的點到點的物理線

路段，中間沒有任何其他的交換結(jié)點。

-一條鏈路只是一條通路的一個組成部分。

■數(shù)據(jù)鏈路(datalink)除了物理線路外，還必須

有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實現(xiàn)

這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了

數(shù)據(jù)鏈路。

-現(xiàn)在最常用的方法是使用適配器(即網(wǎng)卡)來實現(xiàn)

這些協(xié)議的硬件和軟件。

-一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層

的功能。

(a)

結(jié)點A結(jié)點B

數(shù)據(jù)

鏈路層

(b)

數(shù)據(jù)鏈路層像個數(shù)字管道

■常常在兩個對等的數(shù)據(jù)鏈路層之間畫出

一個數(shù)字管道，而在這條數(shù)字管道上傳

輸?shù)臄?shù)據(jù)單位是幀。

結(jié)點—幀幀結(jié)點

■早期的數(shù)據(jù)通信協(xié)議曾叫作通信規(guī)程

(procedure)o因此七數(shù)據(jù)鏈路層，規(guī)程

和協(xié)議是同義語。

A在數(shù)據(jù)鏈路層上傳輸數(shù)據(jù)幀

?發(fā)送方：一頭多快的速度發(fā)送數(shù)據(jù)幀，即每幀之間相隔

多長時間？如何確認對方是否收到數(shù)據(jù)？

?接收方：是否接收到正確的數(shù)據(jù)幀？如何告訴發(fā)送方?

.能及時處理接收到的數(shù)據(jù)幀嗎？

?傳輸過程：會出錯嗎？會丟失數(shù)據(jù)幀嗎？

!解決這些問題，是數(shù)據(jù)鏈路層的主要任務(wù)。

!針對這些問題所制定的通信規(guī)程就是數(shù)據(jù)鏈路層的通信

協(xié)議。

A數(shù)據(jù)鏈路層的主要功能

數(shù)據(jù)鏈路層最重要的作用就是:通過一些數(shù)據(jù)鏈路層

協(xié)議,在不太可靠的物理鏈路上實現(xiàn)可靠的數(shù)據(jù)傳輸。其

主要功能可歸納如下：

(1)鏈路管理

(2)幀定界

(3)流量控制

(4)差錯控制

(5)將數(shù)據(jù)和控制信息區(qū)分開

(6)透明傳輸

(7)尋址

A數(shù)據(jù)鏈路層的主要功能

齡鏈路管理當網(wǎng)絡(luò)中的兩個結(jié)點要進行通信時,數(shù)據(jù)的發(fā)方

必須確知收方是否已處在準備接受的狀態(tài)。為此通信的雙方必須

先要交換一些必要的信息，用術(shù)語講必須先建立一條數(shù)據(jù)鏈路。

在傳輸數(shù)據(jù)時要維持數(shù)據(jù)鏈路，而在通信完畢時要釋放數(shù)據(jù)鏈路。

數(shù)據(jù)鏈路的建立、維持和釋放就叫做鏈路管理。

(2)幀同步-在數(shù)據(jù)鏈路層，數(shù)據(jù)的傳送單位時幀。數(shù)據(jù)一幀一

幀地傳送，就可以在出現(xiàn)差錯時，將有差錯的幀再重傳一次，避

免了全部數(shù)據(jù)的重傳。幀同步是指收方應(yīng)當能從受到的比特流中

準確地區(qū)分出一幀的開始和結(jié)束。

A數(shù)據(jù)鏈路層的主要功能

酚流量控制發(fā)方發(fā)送數(shù)據(jù)的速率必須使收方來得及接收。當收

方來不及接收時，就必須及時控制發(fā)方發(fā)送數(shù)據(jù)的速率。

(4)差錯控制-在計算機通信中，一般都要求有極低的比特差錯率。

為此廣泛地使用了編碼技術(shù)，主要有兩大類，一類是前向糾錯，

即收方收到有差錯的數(shù)據(jù)幀時能自動將差錯改正過來。這種方法

的開銷較大，不適合于計算機通信。另一類是檢錯重發(fā)，即收方

可以檢測出收到的幀中有差錯，于是就讓發(fā)方重復(fù)發(fā)送這一幀，

直到收方正確收到這一幀為止。這種方法在計算機通信中是最常

用的。

A數(shù)據(jù)鏈路層的主要功能

瑞數(shù)據(jù)和控制信息區(qū)分開-由于數(shù)據(jù)和控制信息都是在同一信

道中傳輸，在許多情況下，數(shù)據(jù)和控制信息處于同一幀中，因此

一定要有響應(yīng)的措施使收方能夠?qū)⑺麄儏^(qū)分開來。

(6)透明傳輸-所謂透明傳輸就是不管所傳數(shù)據(jù)是什么樣的比特組

合，都應(yīng)當能夠在鏈路上傳送。當所傳數(shù)據(jù)中的比特組合恰巧與

某一個控制信息完全一樣時，就必須采取適當?shù)拇胧?，使收方?/p>

會將這樣的數(shù)據(jù)誤認為是某種控制信息。這樣才能保證數(shù)據(jù)鏈路

層的傳輸是透明的。

(7)尋址-在多點連接的情況下，必須保證每一幀都能送到正確

的地址。雙方也應(yīng)當知道發(fā)方是哪一個站。

3.2三個基本問題

(1)幀定界

(2)透明傳輸

(3)差錯控制

1.幀定界

-幀定界(framing)就是確定幀的界限。在一段數(shù)據(jù)的前

后分別添加首部和尾部，然后就構(gòu)成了一個幀。確定

幀的界限。

■首部和尾部的一個重要作用就是進行幀定界。也有其

——<MTU-------

數(shù)據(jù)鏈路層的幀長

用控制字符進行幀定界的方法舉例

幀開始符幀結(jié)束符

SOH裝在幀中的數(shù)據(jù)部分EOT

上幀

SOH：01

EOT：04

2.透明傳輸

出現(xiàn)了“EOT”

完整的幀一

發(fā)送—數(shù)據(jù)部分

云前

SOHEOTEOT

被接收端被接收端當作無效幀而丟棄

誤認為是一個幀

解決透明傳輸問題

■發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符“SOH”

或“EOT”的前面插入一個轉(zhuǎn)義字符“ESC”(其十六

進制編碼是1B)。

■字節(jié)填充(bytestuffing)或字符填充(character

stuffing)——接收端的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)

絡(luò)層之前刪除插入的轉(zhuǎn)義字符。

■如果轉(zhuǎn)義字符也出現(xiàn)數(shù)據(jù)當中，那么應(yīng)在轉(zhuǎn)義字

符前面插入一個轉(zhuǎn)義字符。當接收端收到連續(xù)的

兩個轉(zhuǎn)義字符時，就刪除其中前面的一個。

用字節(jié)填充法解決透明傳輸?shù)膯栴}

幀開始符幀結(jié)束符

原始數(shù)據(jù)

SOHEOTSOHESCSOHEOT

字節(jié)填光/字節(jié)金充；字填'充''字等填充

SOHESCEOTESCSOHESCESCESCSOHEOT

--------------------經(jīng)過字節(jié)填充后發(fā)送的數(shù)據(jù)-----------------

發(fā)送

在前

3,差錯檢測

■在傳輸過程中可能會產(chǎn)生比特差錯：1可能會

變成。而o也可能變成lo

■在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特

總數(shù)的比率稱為誤碼率BER(BitErrorRate)o

■誤碼率與信噪比有很大的關(guān)系。

■為了保證數(shù)據(jù)傳輸?shù)目煽啃裕谟嬎銠C網(wǎng)絡(luò)傳

輸數(shù)據(jù)時，必須采用各種差錯檢測措施。

循環(huán)冗余檢驗的原理

■在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循

環(huán)冗余檢驗CRC的檢錯技術(shù)。

■在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組k

個比特。

■假設(shè)待傳送的一組數(shù)據(jù)M=101001（現(xiàn)在

攵=6）。我們在M的后面再添加供差錯檢

測用的〃位冗余碼一起發(fā)送。

冗余碼的計算

■用二進制的模2運算進行2〃乘”的運算,

這相當于在M后面添加〃個0。

■得到的依+〃)位的數(shù)除以事先選定好的

長度為(/7+1)位的除數(shù)P,得出商是Q

而余數(shù)是此余數(shù)/?比除數(shù)戶少1位，

即/?是〃位。

冗余碼的計算舉例

■現(xiàn)在k=6,M=101001c

■設(shè)〃=3,除數(shù)P=1101,

■被除數(shù)是101001000c

■模2運算的結(jié)果是：商Q=110101,

余數(shù)/?=001。

■把余數(shù)/?作為冗余碼添加在數(shù)據(jù)附的后面發(fā)

送出去。發(fā)送的數(shù)據(jù)是：2〃"+R

即:101001001,共（攵+〃）位。

循環(huán)冗余檢驗的原理說明

110101—Q（商）

尸（除數(shù)）一1101|10除Q1.Q00-（被除數(shù)）

1101jHH

1110HH

1101j紜

0111：:：

0000H

1110”

1101；:

"0110j

0000j

Iwo

1101

兩—R（余數(shù)），作為FCS

幀檢驗序列FCS

■在數(shù)據(jù)后面添加上的冗余碼稱為幀檢驗

序歹UFCS(FrameCheckSequence)□

■循環(huán)冗余檢驗CRC和幀檢驗序列FCS并

不等同。

■CRC是一種常用的檢錯方法，而FCS是添

加在數(shù)據(jù)后面的冗余碼。

■FCS可以用CRC這種方法得出，但CRC

并非用來獲得FCS的唯一方法。

(接收端對收到的每一幀進行CRC檢驗

■把收到的幀除以同樣的P,得出余數(shù)兄

■(1)若得出的余數(shù)R=0,則判定這個幀沒有

差錯，就接受(accept)。

■(2)若余數(shù)0,則判定這個幀有差錯，就丟

棄。

■但這種檢測方法并不能確定究竟是哪一個或哪

幾個比特出現(xiàn)了差錯。

■只要經(jīng)過嚴格的挑選，并使用位數(shù)足夠多的除

數(shù)2那么出現(xiàn)檢測不到的差錯的概率就很小

很小。

應(yīng)當注意

■僅用循環(huán)冗余檢驗CRC差錯檢測技術(shù)只能做

到無差錯接受（accept）o

■“無差錯接受”是指：“凡是接受的幀（即不

包括丟棄的幀），我們都能以非常接近于1的

概率認為這些幀在傳輸過程中沒有產(chǎn)生差錯”。

■也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀

都沒有傳輸差錯”（有差錯的幀就丟棄而不接

受）。

■要做到“可靠傳輸”（即發(fā)送什么就收到什么）

就必須再加上確認和重隹機制。

3.3停止等待協(xié)議

完全理想化的數(shù)據(jù)傳輸

發(fā)送方接收方

I

高層

數(shù)據(jù)鏈路層

完全理想化的數(shù)據(jù)傳輸

所基于的兩個假定

■假定1：鏈路是理想的傳輸信道，所傳

送的任何數(shù)據(jù)既不會出差錯也不會丟失。

假定

2：不管發(fā)方以多快的速率發(fā)送數(shù)

據(jù)

，收方總是來得及收下，并及時上交

主

機

■這個假定就相當于認為：接收端向主機交

付數(shù)據(jù)的速率永遠不會低于發(fā)送端發(fā)送數(shù)

據(jù)的速率。

具有最簡單流量控制的數(shù)據(jù)鏈

路層協(xié)議______

■現(xiàn)在去掉上述的第二個假定。但是，仍

然保留第一個假定，即主機A向主機B

傳輸數(shù)據(jù)的信道仍然是無差錯的理想信

道。然而現(xiàn)在不能保證接收端向主機交

付數(shù)據(jù)的速率永遠不低于發(fā)送端發(fā)送數(shù)

據(jù)的速率。

■由收方控制發(fā)方的數(shù)據(jù)流，乃是計算機

網(wǎng)絡(luò)中流量控制的一個基本方法。

具有最簡單流量控制的

數(shù)據(jù)鏈路層協(xié)議算法

行發(fā)送結(jié)點:

(1)從主機取一個數(shù)據(jù)幀。

(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。

(3)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(4)等待。

(5)若收到由接收結(jié)點發(fā)過來的信息(此信息

的格式與內(nèi)容可由雙方事先商定好)，則

從主機取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。

具有最簡單流量控制的

數(shù)據(jù)鏈路層協(xié)議算法(續(xù))

在接收結(jié)點：

(1)等待。

(2)若收到由發(fā)送結(jié)點發(fā)過來的數(shù)據(jù)幀,

則將其放入數(shù)據(jù)鏈路層的接收緩存。

(3)將接收緩存中的數(shù)據(jù)幀上交主機。

(4)向發(fā)送結(jié)點發(fā)一信息，表示數(shù)據(jù)幀

已經(jīng)上交給主機。

(5)轉(zhuǎn)到(1)。

實用的停止等待協(xié)議

四種情況

(a)正常情況(b)數(shù)據(jù)幀出錯(c)數(shù)據(jù)幀丟失(d)確認幀丟失

超時計時器的作用

■結(jié)點A發(fā)送完一個數(shù)據(jù)幀時,就啟動一個

超時計時器(timeouttimer)□

■計時器又稱為定時器。

■若到了超時計時器所設(shè)置的重傳時間tout

而仍收不到結(jié)點B的任何確認幀，則結(jié)

點A就重傳前面所發(fā)送的這一數(shù)據(jù)幀。

■一般可將重傳時間選為略大于“從發(fā)完

數(shù)據(jù)幀到收到確認幀所需的平均時間”。

解決重復(fù)幀的問題

■使每一個數(shù)據(jù)幀帶上不同的發(fā)送序號。每發(fā)送

一個新的數(shù)據(jù)幀就把它的發(fā)送序號加lo

■若結(jié)點B收到發(fā)送序號相同的數(shù)據(jù)幀，就表明

出現(xiàn)了重復(fù)幀。這時應(yīng)丟棄重復(fù)幀，因為已經(jīng)

收到過同樣的數(shù)據(jù)幀并且也交給了主機Bo

■但此時結(jié)點B還必須向A發(fā)送確認幀ACK,

因為B已經(jīng)知道A還沒有收到上一次發(fā)過去

的確認幀ACKo

幀的編號問題

■任何一個編號系統(tǒng)的序號所占用的比特數(shù)一定

是有限的。因此，經(jīng)過一段時間后，發(fā)送序號

就會重復(fù)。

■序號占用的比特數(shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷

就越小。

■對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就

停止等待，因此用一個比特來編號就夠了。

-一個比特可表示。和1兩種不同的序號。

幀的發(fā)送序號

■數(shù)據(jù)幀中的發(fā)送序號N(S)以。和1交

替的方式出現(xiàn)在數(shù)據(jù)幀中。

■每發(fā)一個新的數(shù)據(jù)幀，發(fā)送序號就和上

次發(fā)送的不一樣。用這樣的方法就可以

使收方能夠區(qū)分開新的數(shù)據(jù)幀和重傳的

數(shù)據(jù)幀了。

[應(yīng)當注意_

-僅用循環(huán)冗余檢驗CRC差錯檢測技術(shù)只能做

到無差錯接受（accept）o

■“無差錯接受”是指：“凡是接受的幀（即不

包括丟棄的幀），我們都能以非常接近于1的

概率認為這些幀在傳輸過程中沒有產(chǎn)生差錯”。

■也就是說：“凡是接受的幀都沒有傳輸差錯”

（有差錯的幀就丟棄而不接受）。

■要做到“可靠傳輸”（即發(fā)送什么就收到什么）

就必須再加上確認和重傳機制。

停止等待協(xié)議的算法

■這里不使用否認幀（實用的數(shù)據(jù)鏈路層協(xié)議大

都是這樣的），而且確認幀帶有序號

■按照習(xí)慣的表示法，ACK"表示"第〃-1號幀

已經(jīng)收到，現(xiàn)在期望接收第〃號幀”。

-ACK1表示“0號幀已收到，現(xiàn)在期望接收的下一

幀是1號幀"；

-ACK0表示“1號幀已收到，現(xiàn)在期望接收的下一

幀是。號幀”。

在發(fā)送結(jié)點

(1)從主機取一個數(shù)據(jù)幀，送交發(fā)送緩存。

(2)V(S)-O。

(3)N(S)-V(S)。

(4)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(5)設(shè)置超時計時器。

(6)等待。｛等待以下(7)和(8)這兩個事件中最先出現(xiàn)的一個｝

(7)收到確認幀ACK”,

若l-V(s),貝ij：

從主機取一個新的數(shù)據(jù)幀，放入發(fā)送緩存；

V(S)-[1-V(S)],轉(zhuǎn)到(3)。

否則，丟棄這個確認幀，轉(zhuǎn)到(6)。

(8)若超時計時器時間到，則轉(zhuǎn)到(4)。

在接收結(jié)點

(1)V(R)<-Oo

(2)等待。

(3)收到一個數(shù)據(jù)幀；

若N(S)=V(R),則執(zhí)行(4)；

否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到(6)。

(4)將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件

(也就是數(shù)據(jù)鏈路層模型中的主機)。

(5)V(R)-[1-V(R)]O

(6)/7-V(R)；

發(fā)送確認幀ACK",轉(zhuǎn)到(2)。

停止等待協(xié)議的要點

■只有收到序號正確的確認幀ACK/7后，才更新

發(fā)送狀態(tài)變量V(S)一次，并發(fā)送新的數(shù)據(jù)幀。

-接收端接收到數(shù)據(jù)幀時，就要將發(fā)送序號N(S)

與本地的接收狀態(tài)變量V(R)相比較。

-若二者相等就表明是新的數(shù)據(jù)幀，就收下，并發(fā)送

確認。

-否則為重復(fù)幀，就必須丟棄。但這時仍須向發(fā)送端

發(fā)送確認幀ACK。，而接收狀態(tài)變量V(R)和確認序

號〃都不變。

停止等待協(xié)議的要點（續(xù)）

■連續(xù)出現(xiàn)相同發(fā)送序號的數(shù)據(jù)幀，表明

發(fā)送端進行了超時重傳。連續(xù)出現(xiàn)相同

序號的確認幀，表明接收端收到了重復(fù)

幀。

■發(fā)送端在發(fā)送完數(shù)據(jù)幀時，必須在其發(fā)

送緩存中暫時保留這個數(shù)據(jù)幀的副本。

這樣才能在出差錯時進行重傳。只有確

認對方已經(jīng)收到這個數(shù)據(jù)幀時，才可以

清除這個副本。

停止等待協(xié)議的要點(續(xù))

■實用的CRC檢驗器都是用硬件完成的。

■CRC檢驗器能夠自動丟棄檢測到的出錯

幀。因此所謂的“丟棄出錯幀”，對上

層軟件或用戶來說都是感覺不到的。

■發(fā)送端對出錯的數(shù)據(jù)幀進行重傳是自動

進行的，因而這種差錯控制體制常簡稱

為ARQ(AutomaticRepeatreQuest),

直譯是自動重傳請求，但意思是自動請

求重傳。

3.3.3停止等待協(xié)議的定量分析

-設(shè)》是一個數(shù)據(jù)幀的發(fā)送時間，且數(shù)據(jù)幀的長度是固

定不變的。顯然，數(shù)據(jù)幀的發(fā)送時間》是數(shù)據(jù)幀的長

度)(bit)與數(shù)據(jù)的發(fā)送速率。(bit/s)之比，即

tf=lf/C=lf/C(s)(3-1)

-發(fā)送時間》也就是數(shù)據(jù)幀的發(fā)送時延。

■數(shù)據(jù)幀沿鏈路傳到結(jié)點B還要經(jīng)歷一個傳播時延tpO

■結(jié)點B收到數(shù)據(jù)幀要花費時間進行處理，此時間稱為

處理時間中發(fā)送確認幀ACK的發(fā)送時間為taO

停止等待協(xié)議中數(shù)據(jù)幀和確認幀

1的發(fā)送時間關(guān)系

工］專播時延tp

功

0甚a

』

時

間

I重傳時間

-重傳時間的作用是：數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過了這樣

長的時間還沒有收到確認幀，就重傳這個數(shù)據(jù)幀。

■為方便起見，我們設(shè)重傳時間為

=。+3+〃+。%(3-2)

■設(shè)上式右端的處理時間G和確認幀的發(fā)送時間《都遠

小于傳播時延tp,因此可將重傳時間取為兩倍的傳播

時延，即

tout=2tp(3-3)

簡單的數(shù)學(xué)分析

-兩個發(fā)送成功的數(shù)據(jù)幀之間的最小時間間隔是

tT=tf+t0"t=tf+2tp（3-4）

■設(shè)數(shù)據(jù)幀出現(xiàn)差錯（包括幀丟失）的概率為p,

但假設(shè)確認幀不會出現(xiàn)差錯。

■設(shè)正確傳送一個數(shù)據(jù)幀所需的平均時間tav

〃=%（1+一個幀的平均重傳次數(shù)）

簡單的數(shù)學(xué)分析(續(xù))

一幀的平均重傳次數(shù)

={1XP［重傳次數(shù)為l］+2xP［重傳次數(shù)為2］+3XP［重傳次數(shù)為3］+...}

={1xP［第1次發(fā)送出錯］xP［第2次發(fā)送成功］

+2xP［第1,2次發(fā)送出錯］xP［第3次發(fā)送成功］

+3xP［第1,2,3次發(fā)送出錯］xP［第4次發(fā)送成功］+...)

=p(l—p)+2P2(1—p)+3p3(l-p)+...

這里P［X］是出現(xiàn)事件X的概率。

簡單的數(shù)學(xué)分析(續(xù))

得出正確傳送一個數(shù)據(jù)幀所需的平均時間：

00

l

tav=tT+(l-2)ZiptT=G/(I—P)(3-5)

i=i

當傳輸差錯率增大時，心也隨之增大。當無差錯時，p=0，G=%。

簡單的數(shù)學(xué)分析(續(xù))

每秒成功發(fā)送的最大幀數(shù)就是鏈路的最大吞吐量4nax。顯然，

Anax=l%=(l-P)/%(3-6)

在發(fā)送端，設(shè)數(shù)據(jù)幀的實際到達率為九貝氏不應(yīng)超過最大吞吐量4nax，即

2<(1-p)/tT(3-7)

用時間與進行歸一化，得出歸一化的吞吐量夕為

p=Atf<(1-p)/a<\(3-8)

其中參數(shù)a是卬的歸一化時間：

a=tT/tf>l(3-9)

當重傳時間遠小于發(fā)送時間時，此時的歸一化吞吐量

P&\—P(3-10)

［停止等待協(xié)議ARQ的優(yōu)缺點

-優(yōu)點：比較簡單。

.缺點：通信信道的利用率不高，也就是說，信

道還遠遠沒有被數(shù)據(jù)比特填滿。

-為了克服這一缺點，就產(chǎn)生了另外兩種協(xié)議，

即連續(xù)ARQ和選擇重傳ARQ。這將在后面進

一步討論。

34發(fā)送窗口大于1的ARQ協(xié)議

[3.4.1連續(xù)ARQ協(xié)議的工作原理

-在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確認

幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀。

-如果這時收到了接收端發(fā)來的確認幀，那么還

可以接著發(fā)送數(shù)據(jù)幀。

-由于減少了等待時間，整個通信的吞吐量就提

高了。

連續(xù)ARQ協(xié)議的工作原理

B

A

DATAOJJ^確認

ACK1DATAO送交主機

ACK!確認

超ACK2DATA1

時5__3fDATA2出錯，丟棄

重_PATA3_JDATA3不按序，丟棄，重傳ACK2

傳,out

__ACK2DATA4不按序，丟棄，重傳ACK2

時p

間t—一旦領(lǐng)2一ACK!DATA5不按序，丟棄，重傳ACK2

一重傳氏亞也

-EACK3確認DATA2]

L?t_DAJA3^ACK4確認DATA31送交主機

---

重傳DA7A5

(1)接收端只按序接收數(shù)據(jù)幀。雖然在有差錯的2號幀之

后接著又收到了正確的3個數(shù)據(jù)幀，但接收端都必須

將這些幀丟棄，因為在這些幀前面有一個2號幀還沒

有收到。雖然丟棄了這些不按序的無差錯幀，但應(yīng)重

復(fù)發(fā)送已發(fā)送過的最后一個確認幀(防止確認幀丟

失)。

(2)ACK1表示確認0號幀DATAO,并期望下次收到1

號幀；ACK2表示確認1號幀DATA1,并期望下次收

到2號幀。依此類推。

(3)結(jié)點A在每發(fā)送完一個數(shù)據(jù)幀時都要設(shè)置該幀的超時

計時器。如果在所設(shè)置的超時時間內(nèi)收到確認幀，就

立即將超時計時器清零。但若在所設(shè)置的超時時間到

了而未收到確認幀，就要重傳相應(yīng)的數(shù)據(jù)幀(仍需重

新設(shè)置超時計時器)。

在等不到2號幀的確認而重傳2號數(shù)據(jù)幀時，雖

然結(jié)點A已經(jīng)發(fā)完了5號幀，但仍必須向回走，將2

號幀及其以后的各幀全部進行重傳。連續(xù)ARQ又稱為

Go-back-NARQ,意思是當出現(xiàn)差錯必須重傳時，要

向回走N個幀，然后再開始重傳。

需要注意:

(4)以上講述的僅僅是連續(xù)ARQ協(xié)議的工作原理。協(xié)議

在具體實現(xiàn)時還有許多的細節(jié)。例如，用一個計時器

就可實現(xiàn)相當于/V個獨立的超時計時器的功能。

3.3.2連續(xù)ARQ協(xié)議的吞吐量

-可以很方便地導(dǎo)出連續(xù)ARQ協(xié)議的吞吐

量公式。

3A2滑動窗口的概念

■連續(xù)ARQ需要首先解決兩個問題：

(1)當未被確認的數(shù)據(jù)幀數(shù)目太多，有一幀錯誤,

就要重傳許多幀。浪費。

(2)發(fā)送序號占用比特數(shù)，增加開銷。

-發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口。

-發(fā)送窗口用來對發(fā)送端進行流量控制。

■發(fā)送窗口的大小竹代表在還沒有收到對方確認信

息的情況下發(fā)送端最多可以發(fā)送多少個數(shù)據(jù)幀。

WT

(d)|O|1|2|3|4|5|6|7|O|1|2

'獲許發(fā)送不允許爰送這些幀

并已收到確認3個幀

接收端設(shè)置接收窗口

T在接收端只仃當收到的數(shù)據(jù)幀的發(fā)送序號落入接收

窗口內(nèi)才允許將該數(shù)據(jù)幀收下。

■若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其

丟棄。

■在連續(xù)ARQ協(xié)議中，接收窗口的大小1。

-只有當收到的幀的序號與接收窗口一致時才能接收該幀。

否則，就丟棄它。

-每收到一個序號正確的幀，接收窗口就向前（即向右方）

滑動一個幀的位置。同時發(fā)送對該幀的確認。

*

(a)01234567012

——--、―---____/

準備3收o號幀不允許接收這些幀

=>

(b)I012|3|4|5|6|7|O|1|2

已U1到

準備接收不允許接收這些幀

1號幀

-----------------?喙

：=>

⑹01234567012

"-------------------▼-------------------"------------------------------▽-----------------------------)

已收到I不允許接收這些幀

準備接收4號幀

滑動窗口的重要特性

■只有在接收窗口向前滑動時（與此同時

也發(fā)送了確認），發(fā)送窗口才有可能向

前滑動。

■收發(fā)兩端的窗口按照以上規(guī)律不斷地向

前滑動，因此這種協(xié)議又稱為滑動窗口

協(xié)議。

■當發(fā)送窗口和接收窗口的大小都等于1

時，就是停止等待協(xié)議。

發(fā)送窗口的最大值

■當用〃個比特進行編號時，若接收窗口

的大小為1，則只有在發(fā)送窗口的大小

叫（2〃-1時，連續(xù)ARQ協(xié)議才能正確

運行。

■例如，當采用3bit編碼時，發(fā)送窗口的

最大值是7而不是8。

3A3連續(xù)ARQ的信道利用率

■信道利用率：扣除控制信息的數(shù)據(jù)率與

信道容量之比。

■由于每個數(shù)據(jù)幀都必須包括一定的控制

信息（如幀的序號、地址、同步信息以及

其他的一些控制信息），所以即使連續(xù)不

停地發(fā)送數(shù)據(jù)幀，信道利用率（即扣除全

部的控制信息后的數(shù)據(jù)率與信道容量之

比）也不可能達到100%o

■當出現(xiàn)差錯時（這是不可避免的），數(shù)據(jù)幀

的不斷重傳將進一步使信道利用率降低。

■要定量地分析這問題，就必須知道鏈路的差錯

特性。對于衛(wèi)星信道，每人比特的出錯可視為

獨立的(因為差錯主要是由衛(wèi)星到地座的傳輸

途徑中的隨機噪聲引起的)。記誤比醇率為

以O(shè)設(shè)數(shù)據(jù)幀長為If(即數(shù)據(jù)部分加上控制信

心、,則數(shù)據(jù)幀的差錯率或誤幀率(即1幀中

至少有1個比特出錯的概率)為：

■p=\—Q—p)f(3-12)

■對于很小的兒，上式可近似為：

■p口1fpb?1(3-13)

■設(shè)每幀中數(shù)據(jù)為4bit而控制信息為4

bito

■那么不產(chǎn)生差錯時，實際信道利用率為:

u=wi

-如出現(xiàn)差錯，假設(shè)1幀需重傳a次：

U=4/M+4)(l+a)

I最佳幀長

■若數(shù)據(jù)幀的幀長取得很短，那么控制信

息在每一幀中所占的比例就增大，因而

額外開銷增大，這就導(dǎo)致信道利用率的

下降。

■若幀長取得太長，則數(shù)據(jù)幀在傳輸過程

中出錯的概率就增大，于是重傳次數(shù)將

增大，這也會使信道利用率下降。

■由此可見，存在一個最佳幀長，在此幀

長下信道的利用率最高。

信道利用率與數(shù)據(jù)長度的關(guān)系曲線

信道利用率與數(shù)據(jù)長度的關(guān)系曲線

3A4選擇重傳ARQ協(xié)議

■可加大接收窗口，先收下發(fā)送序號不連續(xù)但仍

處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號

的數(shù)據(jù)幀收到后再一并送交主機。

■選擇重傳ARQ協(xié)議可避免重復(fù)傳送那些本來

已經(jīng)正確到達接收端的數(shù)據(jù)幀。

■但我們付出的代價是在接收端要設(shè)置具有相當

容量的緩存空間。

■對于選擇重傳ARQ協(xié)議，若用n比特進行編

號，則接收窗口的最大值受下式的約束

n

WR<2/2(3-18)

WT<,接收窗口股最大時%=%=2加，

3.5因特網(wǎng)的點對點協(xié)議PPP

3.5.1PPP協(xié)議的工作原理

■現(xiàn)在全世界使用得最多的數(shù)據(jù)鏈路層協(xié)

議是點對點協(xié)議PPP(Point-to-Point

Protocol)o

-用戶使用撥號電話線接入因特網(wǎng)時，一

般都是使用PPP協(xié)議。

用戶撥號入網(wǎng)的示意圖

用戶家庭因特網(wǎng)服務(wù)提供者(ISP)

至

使用TCP/IP的,因

特

網(wǎng)

撥號電話線

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

口］使用TCP/IP的

PPP連接

1.ppp協(xié)議應(yīng)滿足的需求

■簡單——這是首要的要求

■封裝成幀

■透明性

■多種網(wǎng)絡(luò)層協(xié)議

■多種類型鏈路

■差錯檢測

■檢測連接狀態(tài)

■最大傳送單元MTU

■網(wǎng)絡(luò)層地址協(xié)商

■數(shù)據(jù)壓縮協(xié)商

2.PPP協(xié)議不需要的功能

■糾錯

-流量控制

■序號

-多點線路

■半雙工或單工鏈路

3.PPP協(xié)議的組成

■1992年制訂了PPP協(xié)議。經(jīng)過1993年

和1994年的修訂，現(xiàn)在的PPP協(xié)議已

成為因特網(wǎng)的正式標準[RFC1661]O

■ppp協(xié)議有三個組成部分

■一個將IP數(shù)據(jù)報封裝到串行鏈路的方法。

■鏈路控制協(xié)議LCP(LinkControlProtocol)o

■網(wǎng)絡(luò)控制協(xié)議NCP(NetworkControl

Protocol)o

352PPP協(xié)議的幀格式

-標志字段F仍為0x7E（符號“Ox”表示

后面的字符是用十六進制表示。十六進

制的7E的二進制表示是01111110）。

■地址字段A只置為OxFFo地址字段實際

上并不起作用。

-控制字段C通常置為0x03。

■PPP是面向字節(jié)的，所有的PPP幀的長

度都是整數(shù)字節(jié)。

ppp協(xié)議的幀格式

先發(fā)送

字節(jié)1112不超過1500字節(jié)21

<------------------------------------PPP幀---------------------------?

■PPP有一個2個字節(jié)的協(xié)議字段。

-當協(xié)議字段為0x0021時，PPP幀的信息字段就是

IP數(shù)據(jù)報。

-若為0xC021,則信息字段是PPP鏈路控制數(shù)據(jù)。

-若為0x8021,則表示這是網(wǎng)絡(luò)控制數(shù)據(jù)。

透明傳輸問題

■當PPP用在同步傳輸鏈路時，協(xié)議規(guī)定

采用硬件來完成比特填充（和HDLC的

做法一樣）。

■當PPP用在異步傳輸時，就使用一種特

殊的字節(jié)填充法。

■字節(jié)填充法

-將信息字段中出現(xiàn)的每一個0x7E字節(jié)轉(zhuǎn)

變成為字節(jié)序列

2(0x7D,0x5E)o

■若信息字段中出現(xiàn)一個0x7D的字節(jié)，則將

其轉(zhuǎn)變成為字節(jié)序列

2(0x7D,0x5D)o

■若信息字段中出現(xiàn)ASCII碼的控制字符

(即數(shù)值小于0x20的字符)，則在該字

符前面要加入一個0x7D字節(jié)，同時將該

字符的編碼加以改變。

零比特填充

■PPP協(xié)議用在SONET/SDH鏈路時,是

使用同步傳輸（一連串的比特連續(xù)傳

送）。這時PPP協(xié)議采用零比特填充方

法來實現(xiàn)透明傳輸。

■在發(fā)送端，只要發(fā)現(xiàn)有5個連續(xù)1,則

立即填入一個0。接收端對幀中的比特

流進行掃描。每當發(fā)現(xiàn)5個連續(xù)1時，就

把這5個連續(xù)1后的一個0刪除，

零比特填充

寧段中出現(xiàn)了和—0^001111110001010

7

藤字段F完全一樣V

的8比特組合會被誤認為是標志字段F

ooidid1iddiO-XOOO-XO-XO

發(fā)送端在5個連1之后01F

填入。比特再發(fā)送出去

發(fā)送端填入0比特

010011111010001010

在接收端把5個連1

之后的0比特刪除

接收端刪除填入的o比特

不提供使用序號和確認

j的可靠傳輸