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

1、 軟件學(xué)院楊巍3Unit 3數(shù)據(jù)鏈路層物理層(physical layer 以比特為單位,透明的傳送比特流數(shù)據(jù)鏈路層(data link layer以幀為單位,無差錯(cuò)傳輸應(yīng)用層應(yīng)用層運(yùn)輸層運(yùn)輸層網(wǎng)絡(luò)層網(wǎng)絡(luò)層鏈路層鏈路層物理層物理層數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路鏈路(link物理鏈路一條無源的點(diǎn)到點(diǎn)的物理線路段,中間沒有任何其他的交換結(jié)點(diǎn)數(shù)據(jù)鏈路(data link 邏輯鏈路物理連接與鏈路控制規(guī)程形成的數(shù)據(jù)管道軟件學(xué)院楊巍4幀幀數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路層的主要功能鏈路管理:數(shù)據(jù)鏈路的連接、維護(hù)、釋放幀同步:幀的概念:網(wǎng)上傳輸數(shù)據(jù)的最基本單元幀與分組:幀是在第二層協(xié)議中定義的分組。高層分組被幀當(dāng)

2、作數(shù)據(jù)部分,物理層不封裝幀同步:區(qū)分幀的開始和結(jié)束軟件學(xué)院楊巍6數(shù)據(jù)鏈路層的基本概念數(shù)據(jù)鏈路層的主要功能流量控制:解決緩沖區(qū)的問題差錯(cuò)控制區(qū)分?jǐn)?shù)據(jù)和控制信息透明比特流傳輸能夠傳輸任意比特流,不會(huì)出現(xiàn)數(shù)據(jù)和控制信息出現(xiàn)二義性的問題尋址軟件學(xué)院楊巍7 停-等協(xié)議完全理想化的數(shù)據(jù)傳輸假定1:鏈路是理想的傳輸信道,無差錯(cuò)和丟失假定2:接受方能及時(shí)接收發(fā)送方的數(shù)據(jù)含義接收方緩沖區(qū)無限大或接收速率與發(fā)送速率絕對(duì)相等結(jié)論:此時(shí)不需要數(shù)據(jù)鏈路層軟件學(xué)院楊巍9停-等協(xié)議具有簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議保留假定1:鏈路是理想的傳輸信道,無差錯(cuò)和丟失緩沖區(qū)大小有限,且發(fā)送方和接收方速度不同。需要解決接收緩存不會(huì)溢出

3、問題解決方案:由接收方告訴發(fā)送方何時(shí)可以發(fā)送下一幀。由接收方控制發(fā)送方的流量軟件學(xué)院楊巍10 停-等協(xié)議實(shí)用的停-等協(xié)議傳輸數(shù)據(jù)的信道不能保證所傳的數(shù)據(jù)不產(chǎn)生差錯(cuò),并且還需要對(duì)數(shù)據(jù)的發(fā)送端進(jìn)行流量控制正常情況數(shù)據(jù)幀出錯(cuò)數(shù)據(jù)幀丟失確認(rèn)幀丟失軟件學(xué)院楊巍13 停-等協(xié)議實(shí)用的停-等協(xié)議物理層在傳輸比特時(shí)會(huì)出現(xiàn)差錯(cuò)數(shù)據(jù)鏈路層的停-等協(xié)議采用了有效的檢錯(cuò)重傳機(jī)制,數(shù)據(jù)鏈路層對(duì)上面的網(wǎng)絡(luò)層提供了可靠傳輸?shù)姆?wù)。應(yīng)答幀/否認(rèn)幀CRC校驗(yàn)超時(shí)重傳編號(hào)軟件學(xué)院楊巍18運(yùn)算運(yùn)算停-等協(xié)議幀檢驗(yàn)序列FCS在數(shù)據(jù)后面添加上的冗余碼循環(huán)冗余檢驗(yàn)CRC 和幀檢驗(yàn)序列FCS并不等同。CRC 是一種常用的檢錯(cuò)方法,而FCS

4、 是添加在數(shù)據(jù)后面的冗余碼。FCS 可以用CRC 這種方法得出,但CRC 并非用來獲得FCS 的唯一方法。軟件學(xué)院楊巍20 運(yùn)算運(yùn)算停-等協(xié)議CRC校驗(yàn)M=1010001101 K=10P= 110101n+1=6n=5被除數(shù)應(yīng)該為:軟件學(xué)院楊巍23 停-等協(xié)議1101010110Q商11010111101111010111101011010111111011010110110011010111001011010101110R余數(shù)軟件學(xué)院楊巍24 停-等協(xié)議CRC校驗(yàn)接收端的運(yùn)算Q(x!=0檢測(cè)到差錯(cuò)Q(x=0?嚴(yán)格挑選并使用位數(shù)足夠多的除數(shù)PP(xCRC-16CRC-CCITT CRC-32

5、軟件學(xué)院楊巍27停-等協(xié)議CRC校驗(yàn)檢錯(cuò)方法檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。一旦檢測(cè)出差錯(cuò),就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。實(shí)用的CRC檢驗(yàn)器都是用硬件完成的。CRC 檢驗(yàn)器能夠自動(dòng)丟棄檢測(cè)到的出錯(cuò)幀,對(duì)上層軟件或用戶來說都是感覺不到的。ARQ(Automatic Repeat reQuest自動(dòng)請(qǐng)求重傳flash演示軟件學(xué)院楊巍28停-等協(xié)議停-等協(xié)議的算法發(fā)送結(jié)點(diǎn)和接收結(jié)點(diǎn)的算法V(s:發(fā)送狀態(tài)變量N(s:發(fā)送序號(hào)V(r:接收狀態(tài)變量應(yīng)該接收的序號(hào)ACK n表示“第n1號(hào)幀已經(jīng)收到,現(xiàn)在期望接收第n號(hào)幀”。ACK1 表示“0 號(hào)幀已收到,現(xiàn)在期望接收的下一幀是1 號(hào)幀”;AC

6、K0 表示“1 號(hào)幀已收到,現(xiàn)在期望接收的下一幀是0 號(hào)幀”。軟件學(xué)院楊巍29 停-等協(xié)議停-等協(xié)議ARQ 的優(yōu)缺點(diǎn)優(yōu)點(diǎn):比較簡(jiǎn)單缺點(diǎn):通信信道的利用率不高,也就是說,信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。為了克服這一缺點(diǎn),就產(chǎn)生了另外兩種協(xié)議,即連續(xù)ARQ 和選擇重傳ARQ。軟件學(xué)院楊巍32連續(xù)ARQ協(xié)議連續(xù)ARQ 協(xié)議的工作原理在發(fā)送完一個(gè)數(shù)據(jù)幀后,不是停下來等待確認(rèn)幀,而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。邊發(fā)送邊接收確認(rèn)應(yīng)答幀幀編號(hào)CRC校驗(yàn)超時(shí)重傳軟件學(xué)院楊巍33 連續(xù)ARQ協(xié)議連續(xù)ARQ 協(xié)議的工作原理接收端只按序接收發(fā)送端發(fā)幀以后設(shè)置計(jì)時(shí)器若出現(xiàn)錯(cuò)誤,出錯(cuò)幀的后續(xù)幀要重傳軟件學(xué)院楊巍35連續(xù)A

7、RQ協(xié)議連續(xù)ARQ協(xié)議的優(yōu)缺點(diǎn)特點(diǎn)連續(xù)發(fā)送提高效率可能會(huì)重傳已發(fā)的正確幀不適用于信道質(zhì)量比較差的時(shí)候缺點(diǎn)重傳開銷大,降低效率,time out期間發(fā)送的越多,出錯(cuò)后的效率就越低發(fā)送序號(hào)需要占用比特?cái)?shù)軟件學(xué)院楊巍36滑動(dòng)窗口協(xié)議連續(xù)ARQ協(xié)議應(yīng)當(dāng)將已發(fā)送出去但未被確認(rèn)的數(shù)據(jù)幀的數(shù)目加以限制滑動(dòng)窗口協(xié)議循環(huán)使用已經(jīng)確認(rèn)的序號(hào)加入控制機(jī)制,避免二義性窗口:發(fā)送窗口:對(duì)發(fā)送端進(jìn)行流量控制接收窗口:對(duì)接收端的接收方式進(jìn)行控制軟件學(xué)院楊巍37滑動(dòng)窗口協(xié)議滑動(dòng)窗口協(xié)議發(fā)送窗口:只有在發(fā)送窗口內(nèi)的幀,才能被發(fā)送發(fā)送窗口的大小W T代表在還沒有收到對(duì)方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。在接收端只有

8、當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。接收窗口:只有在接收窗口內(nèi)的幀,才能被接收軟件學(xué)院楊巍38 滑動(dòng)窗口協(xié)議滑動(dòng)窗口協(xié)議連續(xù)ARQ協(xié)議,接收窗口大小為1在連續(xù)ARQ中,發(fā)送序號(hào)3bit,發(fā)送窗口大小為5在連續(xù)ARQ中,接收窗口大小為1當(dāng)發(fā)送窗口和接收窗口的大小都等于1時(shí),就是停止等待協(xié)議。滑動(dòng)窗口的工作軟件學(xué)院楊巍41滑動(dòng)窗口協(xié)議思考當(dāng)幀的序號(hào)占用的bit數(shù)一定時(shí),發(fā)送窗口的最大值應(yīng)該為多少?從接收端看問題所有確認(rèn)幀都到達(dá)所有確認(rèn)幀都丟失結(jié)論:編碼時(shí)序號(hào)占用n bit,窗口大小最大為2n-1個(gè)窗口大小與緩沖區(qū)的關(guān)系窗口越大,緩沖區(qū)越大軟件學(xué)院楊巍42選擇重傳ARQ協(xié)議選擇重傳ARQ協(xié)議發(fā)送端選擇未被確認(rèn)的序號(hào)進(jìn)行重發(fā),接收端等待所有幀按序到達(dá)后在一并提交。優(yōu)點(diǎn):不用重傳已經(jīng)確認(rèn)的幀代價(jià):接收端需要有相當(dāng)容量的緩沖區(qū)軟件學(xué)院楊巍43HDLC協(xié)議HDLC協(xié)議概述經(jīng)常誤碼的實(shí)際鏈路+合適的控制規(guī)程=比較可靠的數(shù)據(jù)通信早期的鏈路層協(xié)議ARPANET:IMP-IMP協(xié)議IBM:BISYNC (Binary SYNchronousCommunication規(guī)程軟件學(xué)院楊巍44HDLC協(xié)議HDLC協(xié)議概述早期的鏈路層協(xié)議全部是面向字符的數(shù)據(jù)以及控制信息必須分別由規(guī)定的字符集中的字符所組成缺點(diǎn)效率低,使用停-等協(xié)議