計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)鏈路層

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

主要研究

兩臺(tái)相連的機(jī)器數(shù)據(jù)鏈路層實(shí)現(xiàn)可靠、

有效通信的算法

InI

1

主要內(nèi)容

11數(shù)據(jù)鏈路層設(shè)計(jì)問(wèn)題

口差錯(cuò)檢測(cè)和校正

II基本數(shù)據(jù)鏈路協(xié)議

口滑動(dòng)窗口協(xié)議

口數(shù)據(jù)鏈路層示例

2

3.1數(shù)據(jù)鏈路層的功能及所提供的服務(wù)

?鏈路：是一條無(wú)源的點(diǎn)到點(diǎn)的物理線路段，中間沒(méi)

有任何其他的交換接點(diǎn)。

?數(shù)據(jù)鏈路：把實(shí)現(xiàn)這些規(guī)程的硬件和軟件加到鏈

路上，就構(gòu)成了數(shù)據(jù)鏈路。

?數(shù)據(jù)鏈路層最重要的作用：通過(guò)一些數(shù)據(jù)鏈路

層協(xié)議（即鏈路控制規(guī)程），在不太可靠的物理鏈

路上實(shí)現(xiàn)可靠的數(shù)據(jù)傳輸。

在數(shù)據(jù)鏈路層數(shù)據(jù)傳輸?shù)膯挝皇菐?/p>

3

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

?為網(wǎng)絡(luò)層提供良好的服務(wù)接口

?將物理層的比特流組織成幀

?差錯(cuò)控制

?流量控制

4

3.1.1為網(wǎng)絡(luò)層提供的服務(wù)

U無(wú)確認(rèn)的無(wú)連接服務(wù)

國(guó)有確認(rèn)的無(wú)連接服務(wù)

口有確認(rèn)的面向連接服務(wù)

5

通信過(guò)程

Host1Host2Host1Host2

4

(3

Virtual

datapath

2

1

(a)(b)

無(wú)確認(rèn)的無(wú)連接服務(wù)

口源機(jī)器向目的機(jī)器發(fā)送獨(dú)立的幀，而目的機(jī)器對(duì)

收到的幀不作確認(rèn)。

＞不存在連接的建立和釋放過(guò)程；

＞數(shù)據(jù)鏈路層對(duì)丟失的幀不作恢復(fù)工作

口適用于：

A誤碼率很低；

A實(shí)時(shí)性要求高，如語(yǔ)音傳輸；

7

有確認(rèn)的無(wú)連接服務(wù)

E對(duì)發(fā)送的每一幀進(jìn)行單獨(dú)確認(rèn)，讓發(fā)送方

知道幀是否安全到達(dá)°

A不存在連接的建立和釋放過(guò)程；

A可提高可靠性；

口適用于：

A不可靠信道。

8

有確認(rèn)的面向連接服務(wù)

口源機(jī)器和目的機(jī)器在傳遞任何數(shù)據(jù)之前，

先建立一條連接；

口在這條連接上所發(fā)送的每一幀都編上號(hào)，

數(shù)據(jù)鏈路層保證所發(fā)送的每一幀都確實(shí)已

到達(dá)；

U保證每幀只收到一次，且所有幀都按正確

順序接收；

9

口分三個(gè)階段

A建立連接，對(duì)雙方變量和計(jì)數(shù)器初始化，

用于追蹤幀，哪個(gè)幀接收到了，哪個(gè)幀

未接收；

A實(shí)際的幀傳輸；

A斷開(kāi)連接，釋放用于維護(hù)連接的變量、

緩沖區(qū)及其它資源；

10

El數(shù)據(jù)鏈路層向網(wǎng)絡(luò)層提供服務(wù)，并且使用物理層

提供給它的服務(wù)。

■物理層的工作是接收一個(gè)原始比特流，并準(zhǔn)備把

它交給目的端，不保證比特流無(wú)差錯(cuò)；

■數(shù)據(jù)鏈路層對(duì)物理層傳輸?shù)牟铄e(cuò)進(jìn)行檢測(cè)或糾錯(cuò),

一般把比特流分成離散的幀，并對(duì)每一幀計(jì)算出

校驗(yàn)和，當(dāng)幀到達(dá)目的地后重新計(jì)算校驗(yàn)和，相

符無(wú)差錯(cuò)，不相符則有差錯(cuò)。

11

3.1.2成幀方法

數(shù)據(jù)鏈路層要把比特流分成離散的幀。

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

字符計(jì)數(shù)法

帶字節(jié)填充的分界符法

帶位填充的分界標(biāo)志法

物理層編碼違例法

在數(shù)據(jù)鏈路層，接收端應(yīng)能從收到的比特流

中準(zhǔn)確的識(shí)別一個(gè)幀的開(kāi)始和結(jié)束。

12

字符計(jì)數(shù)法

口在幀頭部中使用一個(gè)字段來(lái)標(biāo)明幀

內(nèi)字符數(shù)

口缺點(diǎn)

計(jì)數(shù)值有可能由于傳輸差錯(cuò)而被“篡

改”，已很少采用。

13

字符計(jì)數(shù)法

5characters5characters8characters8characters

14

帶字節(jié)填充的分界符法

口每一幀以標(biāo)志字節(jié)FLAG作為開(kāi)頭和結(jié)束分

界符；

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

口在傳輸數(shù)據(jù)中出現(xiàn)FLAG時(shí)，在字符前插入

一個(gè)ESC的ASCII碼一一字節(jié)填充

口缺點(diǎn)

完全依賴于8位ASCII字符

15

帶位填充的分界標(biāo)志法

u每一幀使用一個(gè)特殊的位模式,即

01111110作為開(kāi)始和結(jié)束標(biāo)志字節(jié)；

口當(dāng)發(fā)送方的數(shù)據(jù)鏈路層在數(shù)據(jù)中遇到5

個(gè)連續(xù)的1時(shí)，它自動(dòng)在其后插入一個(gè)

。到輸出比特流中；

17

帶位填充的分界標(biāo)志法

(a)011011111111111111110010

(b)011011111011111011111010010

、t/

Stuffedbits

(c)011011111111111111110010

(a)原始數(shù)據(jù)(b)線上數(shù)據(jù)

(c)刪除填充位后接收方存儲(chǔ)器內(nèi)的數(shù)據(jù)

18

物理層編碼違例法

口每個(gè)數(shù)值位都要在中間進(jìn)行一次電平

變換，如數(shù)據(jù)位。編碼為低-高電平對(duì),

數(shù)據(jù)位1編碼為高-低電平對(duì)，確定位

邊界。

19

3.1.3差錯(cuò)控制

口怎樣保證所有的幀最終都按正確的順

序交付給目的機(jī)器的網(wǎng)絡(luò)層？

A發(fā)送幀錯(cuò)誤

A發(fā)送幀丟失

A確認(rèn)幀丟失

A重復(fù)幀

為了保證數(shù)據(jù)傳輸?shù)恼_性，在計(jì)算機(jī)通

信過(guò)程中通常采用檢錯(cuò)重發(fā)。

20

3.1.4流量控制

■如何處理發(fā)送方的傳送能力比接收方

接收能力大的問(wèn)題？

A發(fā)送方運(yùn)行在相對(duì)快速或負(fù)載較輕的機(jī)

器上，接收方運(yùn)行在相對(duì)慢速或負(fù)載較重

的機(jī)器

21

思考題

口在大多數(shù)網(wǎng)絡(luò)中，數(shù)據(jù)鏈路層通過(guò)請(qǐng)求重傳

壞幀來(lái)處理傳輸錯(cuò)誤.如果一個(gè)幀被損壞的

概率為P,在確認(rèn)幀永遠(yuǎn)不會(huì)被丟失的情況

下，發(fā)送一幀所需要的平均傳輸次數(shù)是多

少？

22

3.2基本數(shù)據(jù)鏈路協(xié)議

口一種無(wú)限制的單工協(xié)議

?一個(gè)單工的停.等協(xié)議

口有噪聲信道的單工協(xié)議

23

3.3.1一種無(wú)限制的單工協(xié)議

一種不現(xiàn)實(shí)的理想?yún)f(xié)議，也稱為“烏托邦”

(utopia)+辦議。假定:

?傳送和接收方的網(wǎng)絡(luò)層一直處于就緒狀態(tài)；

A處理時(shí)間忽略不計(jì)，

?緩沖空間無(wú)限大；

?數(shù)據(jù)鏈路層信道中不存在丟失幀和損壞幀的

情況。

24

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

:1鏈路是理想的傳輸信道。即傳輸?shù)娜魏螖?shù)

據(jù)都不會(huì)出錯(cuò)也不會(huì)丟失。

口不論發(fā)方的發(fā)送速率多快，收方均能收下

并及時(shí)上交主機(jī)。

25

烏托邦協(xié)議實(shí)現(xiàn)

工作過(guò)程

口發(fā)送程序：取數(shù)據(jù)，構(gòu)成幀，發(fā)送幀;

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烏托邦協(xié)議實(shí)現(xiàn)

[■接收程序：等待，接收幀，送數(shù)據(jù)給高層

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一個(gè)單工的停-等協(xié)議

U現(xiàn)在的情況是：主機(jī)A向主機(jī)B傳輸數(shù)據(jù)

的信道是無(wú)差錯(cuò)的理想信道。

口問(wèn)題：如何防止發(fā)送方發(fā)送數(shù)據(jù)過(guò)快,

而使接收方來(lái)不及處理？

28

一個(gè)單工的停-等協(xié)議

國(guó)如何防止發(fā)送過(guò)快，使接收過(guò)程來(lái)不及處理。

A如果接收過(guò)程需要△t的時(shí)間來(lái)執(zhí)行from-

physicalTayer和to-network-layer,則發(fā)送

過(guò)程必須以低于每At時(shí)間一幀的平均速率進(jìn)行

傳輸；

A或者說(shuō)，如果在接收方的硬件中沒(méi)有自動(dòng)的緩

沖和排隊(duì)功能，那么發(fā)送方只有當(dāng)前一個(gè)幀被

from-physical-layer取走后才能傳輸新的幀，

否則新的幀就會(huì)把前一個(gè)幀覆蓋；

29

一個(gè)單工的停-等協(xié)議

■要求接收方向發(fā)送方提供反饋。

A當(dāng)接收方把一個(gè)分組傳給本地的網(wǎng)絡(luò)層后，向

發(fā)送方返回一個(gè)短幀（確認(rèn)幀），允許發(fā)送方

發(fā)送下一幀；

?發(fā)送方在發(fā)送完一幀之后，要求等待一段時(shí)間,

直到該短幀（確認(rèn)幀）到達(dá)。

發(fā)送方發(fā)送一個(gè)幀，不繼續(xù)發(fā)送幀而等待一個(gè)確認(rèn),

這種協(xié)議就稱為停一等協(xié)議。

發(fā)方發(fā)送數(shù)據(jù)的流量受收方的控制。

30

m單工停-等協(xié)議實(shí)現(xiàn)

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單工停-等協(xié)議實(shí)現(xiàn)

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

在這種方式中，收方向發(fā)方反饋的信息，

只是回送給發(fā)送方的幀的到達(dá)的確認(rèn)，而不需

要有任何具體的內(nèi)容。只要發(fā)回一個(gè)沒(méi)有內(nèi)容

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

33

3.3.3有噪聲信道的單工協(xié)議

在實(shí)際中，傳輸信道并不是可靠的，并且還

需要對(duì)數(shù)據(jù)的發(fā)送端進(jìn)行流量控制。

心"、必”接收方正確接收后，發(fā)回一個(gè)

發(fā)普什發(fā)送確認(rèn)幀，發(fā)方發(fā)送下一個(gè)幀。

一個(gè)幀后

發(fā)方在一定時(shí)間內(nèi)未收到確認(rèn)幀

則發(fā)方重發(fā)此幀1

即有一個(gè)定時(shí)器進(jìn)行計(jì)時(shí)，“一定時(shí)間”由

發(fā)

收約定長(zhǎng)短。這個(gè)時(shí)間要定的合適，若太短

那么就會(huì)發(fā)生確認(rèn)正在路上，而又發(fā)了一個(gè)

34

*若發(fā)方未收到確認(rèn)幀，是接收方未能正確接收到這

個(gè)數(shù)據(jù)幀呢，還是發(fā)回確認(rèn)幀丟失了呢

接收方要有能力判斷是否重復(fù)地接收一個(gè)同樣的

幀。即能區(qū)分接到的某一幀是新幀還是重發(fā)的幀。

發(fā)方的每個(gè)待發(fā)的數(shù)據(jù)幀都帶上不同的發(fā)送序號(hào)。

如發(fā)送一個(gè)新幀序號(hào)001,那么收方通過(guò)檢查這個(gè)序號(hào)

就可判別：

/是新幀--------接收-

〈是重復(fù)幀--------拋棄

（序號(hào)相同）

35

對(duì)于停等協(xié)議，數(shù)據(jù)幀中的發(fā)送序號(hào)

以0和1交替出現(xiàn)在數(shù)據(jù)幀中。

發(fā)送方在發(fā)送下一個(gè)數(shù)據(jù)項(xiàng)之前，等待一個(gè)

肯定的確認(rèn)的協(xié)議，稱為PAR或ARQ。

發(fā)送端對(duì)出錯(cuò)的數(shù)據(jù)幀進(jìn)行

重發(fā)是自動(dòng)進(jìn)行的，所以稱為

自動(dòng)請(qǐng)求重發(fā)。

在這個(gè)協(xié)議下，在發(fā)方發(fā)送傳輸一幀并啟動(dòng)

計(jì)時(shí)器之后，發(fā)方所等待發(fā)生的情況有3種：

36

①在定時(shí)內(nèi)確認(rèn)幀無(wú)損到達(dá)：則發(fā)送方發(fā)送

下一個(gè)數(shù)據(jù)幀（連同其序列號(hào)）。

②受損的確認(rèn)幀到達(dá)，那么發(fā)方重發(fā)此幀（序

號(hào)不會(huì)發(fā)生變化）。

③計(jì)時(shí)器超時(shí)，還未有確認(rèn)幀到達(dá)，則發(fā)方

“超時(shí)重發(fā)”。

在接收方，在接收到一個(gè)數(shù)據(jù)幀時(shí)，即檢查

數(shù)據(jù)幀有無(wú)差錯(cuò)，同時(shí)檢查此幀的序號(hào)是否是一

個(gè)重復(fù)的幀。若是重復(fù)幀則拋棄。

37

發(fā)送方:

1.取一個(gè)數(shù)據(jù)幀；

2.發(fā)送狀態(tài)變量初始化（清0）；

3.將發(fā)送狀態(tài)變量的數(shù)值寫(xiě)入發(fā)送序號(hào)，將數(shù)據(jù)幀送交

發(fā)送緩沖區(qū)；

4.將發(fā)送緩沖區(qū)中的數(shù)據(jù)幀發(fā)送出去；

5.設(shè)置超時(shí)定時(shí)器（選擇適當(dāng)?shù)某瑫r(shí)重發(fā)時(shí)間）；

6.等待。（等待以下3個(gè)事件中最早出現(xiàn)的一個(gè)）

7.若收到確認(rèn)幀，則：取一個(gè)新的數(shù)據(jù)幀；更新發(fā)送狀

態(tài)變量，設(shè)為下一個(gè)序號(hào)；轉(zhuǎn)到3。

8.若收到受損的確認(rèn)幀（即否認(rèn)幀），則轉(zhuǎn)到4。（重

發(fā)幀）

9.若超時(shí)定時(shí)器時(shí)間到，則轉(zhuǎn)到4。（重發(fā)幀）

38

接收方：

1.接收狀態(tài)變量初始化（其數(shù)值等于欲接收的數(shù)

據(jù)幀的發(fā)送序號(hào)）；

2等待

3：當(dāng)收至U一個(gè)數(shù)據(jù)幀，檢查有無(wú)產(chǎn)生傳輸差錯(cuò)。

若檢查結(jié)果正確無(wú)誤，則繼續(xù)4否則轉(zhuǎn)到8。

4.若收到發(fā)送序號(hào)正確的數(shù)據(jù)幀，則繼續(xù)5;否

則丟棄此幀，轉(zhuǎn)到7;

5.將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送上交。

6.更新接收狀態(tài)變量，準(zhǔn)備接收下一個(gè)數(shù)據(jù)幀。

7.發(fā)送確認(rèn)幀，并轉(zhuǎn)到2。

8.發(fā)送否認(rèn)幀，并轉(zhuǎn)到2。

39

對(duì)于狀態(tài)變量說(shuō)明:

①每發(fā)送一個(gè)數(shù)據(jù)幀，都必須將發(fā)送狀態(tài)設(shè)置

的值（0或1）寫(xiě)到數(shù)據(jù)幀的發(fā)送序號(hào)上。

但只有收到一個(gè)確認(rèn)幀后，才更新發(fā)送狀態(tài)

變量一次（0—1或1-0）,并發(fā)送新的數(shù)

據(jù)幀。

②在接收端，每接收到一個(gè)數(shù)據(jù)幀，就要將發(fā)

方在數(shù)據(jù)幀上設(shè)置的發(fā)送序號(hào)與本地的接收

狀態(tài)變量相比較。若兩者相等就表明是新的

數(shù)據(jù)幀，否則為重復(fù)幀。

40

③在接收端，若收到一個(gè)重復(fù)幀，則丟棄之

（不作任何處理），且接收狀態(tài)變量不變，

但此時(shí)仍需向發(fā)送端發(fā)送一個(gè)確認(rèn)幀。

④另外，發(fā)送端在發(fā)完一個(gè)數(shù)據(jù)幀時(shí)，必須在

其發(fā)送緩沖區(qū)中保留此幀的副本。這樣才能

在出錯(cuò)時(shí)進(jìn)行重發(fā)。只有在收到對(duì)方發(fā)來(lái)的

確認(rèn)幀后，方可清除副本。

41

3.4滑動(dòng)窗口協(xié)議

?使用同一條線路進(jìn)行數(shù)據(jù)的雙向傳輸。在這

種模式下：從A-〉B的數(shù)據(jù)幀和從B-〉A(chǔ)的確認(rèn)幀

混在一起，必須查看到達(dá)幀頭部分的kind字段加

以判斷是數(shù)據(jù)幀還是確認(rèn)幀。

一種改進(jìn)：當(dāng)一個(gè)數(shù)據(jù)幀到達(dá)后，接收過(guò)程

不是立即發(fā)送一個(gè)獨(dú)立的控制幀，而是維持等待，

直到其網(wǎng)絡(luò)層想發(fā)送下一個(gè)分組，確認(rèn)被附加到

即將發(fā)送的數(shù)據(jù)幀上，這種技術(shù)稱為“捎帶技

術(shù)”。

42

捎帶技術(shù)、單獨(dú)確認(rèn)幀

■捎帶技術(shù)有效利用信道的帶寬

口捎帶技術(shù)也帶來(lái)了單獨(dú)確認(rèn)幀所沒(méi)有的復(fù)

雜性。即數(shù)據(jù)鏈路層等待多長(zhǎng)時(shí)間才能把

捎帶確認(rèn)幀發(fā)出去?如果等待時(shí)間過(guò)長(zhǎng)，

造成發(fā)送方計(jì)時(shí)器超時(shí)，也就違背了確認(rèn)

的意義?？刹捎玫却粋€(gè)固定的毫秒數(shù)，

在這個(gè)時(shí)間范圍內(nèi)，新的分組到來(lái)則采用

捎帶技術(shù)，否則以單獨(dú)分組的形式發(fā)出確

次破。

43

滑動(dòng)窗口協(xié)議

[1滑動(dòng)窗口協(xié)議的關(guān)鍵在于：任何時(shí)刻發(fā)送

過(guò)程都保持著一組序列號(hào)，對(duì)應(yīng)于允許發(fā)

送的幀。這些幀稱作在發(fā)送窗口(sending

window)之內(nèi)。相類(lèi)似的，接收過(guò)程也維

持一個(gè)接收窗口(receivewindow)對(duì)應(yīng)于

一組允許接收的幀。

44

滑動(dòng)窗口的概念

動(dòng)

每

發(fā)

幀

含

中

在

窗

個(gè)

出

都

滑

包

的

要

B議

口

一

-一

，

列

刻

任

列

個(gè)

何

序

時(shí)

發(fā)

一

組

方

持

著

號(hào)

，

篇

號(hào)

口

送

許

可

序

幀

著

對(duì)

送

應(yīng)

的

內(nèi)

。

送

發(fā)

些

作

在

允

之

這

有

前

送

內(nèi)

的

。

當(dāng)

輸

傳

發(fā)

幀

所

終

在

能

窗

以