計算機(jī)網(wǎng)絡(luò)與通信第4章.pptx

1、 第4章 數(shù)據(jù)鏈路控制1 第4章 數(shù)據(jù)鏈路控制4.1 概述4.2 數(shù)據(jù)鏈路控制的基本機(jī)制4.3 自動請求重傳4.4 差錯校驗(yàn)2 4.1 概述數(shù)據(jù)鏈路層負(fù)責(zé)在單個鏈路上的發(fā)送和接收結(jié)點(diǎn)之間傳送幀3 4.1 概述數(shù)據(jù)鏈路層的通信對等實(shí)體之間的數(shù)據(jù)傳輸通道稱為數(shù)據(jù)鏈路(Data Link)，包括物理鏈路和必要的傳輸控制規(guī)程。理想的數(shù)據(jù)鏈路應(yīng)該滿足以下兩個條件：不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總能夠來得及接收、處理并上交主機(jī)；傳輸?shù)娜魏螖?shù)據(jù)，既不會出現(xiàn)差錯也不會丟失。第1個條件不滿足就必須進(jìn)行流量控制(Flow Control)。第2個條件不滿足就必須進(jìn)行差錯控制(Error Control)。

2、44.1 概述實(shí)現(xiàn)流量控制的一個重要方法是滑動窗口(Sliding Window)機(jī)制。實(shí)現(xiàn)差錯控制的一個基本方式是反饋重傳糾錯。自動請求重傳ARQ (Automatic Repeat reQuest)，ARQ綜合了滑動窗口機(jī)制和確認(rèn)-重傳機(jī)制，進(jìn)行流量控制和差錯控制，實(shí)現(xiàn)可靠傳輸。媒體接入控制(Medium Access Control, MAC)。54.2 數(shù)據(jù)鏈路控制的基本機(jī)制6 4.2.1 滑動窗口發(fā)送方和接收方分別設(shè)置發(fā)送窗口和接收窗口。發(fā)送窗口用來對發(fā)送方進(jìn)行流量控制，落在窗口內(nèi)的幀是可以連續(xù)發(fā)送的，其大小WT指明在收到對方確認(rèn)(ACK)之前發(fā)送方最多可以發(fā)送多少個幀。只有到達(dá)的數(shù)

3、據(jù)幀的序號落在接收窗口之內(nèi)時才可以被接收，否則將被丟棄。一般地，當(dāng)接收方收到一個有序且無差錯的幀后，接收窗口向前滑動，準(zhǔn)備接收下一幀，并向發(fā)送方發(fā)送出一個ACK。當(dāng)發(fā)送方收到接收方的ACK后，發(fā)送窗口才能向前滑動，滑動的長度取決于接收方確認(rèn)的序號。7 4.2.1 滑動窗口發(fā)送方的滑動窗口 84.2.2 反饋重傳反饋重傳機(jī)制可以采用以下措施：差錯發(fā)現(xiàn)反饋確認(rèn)信息正確認(rèn)/肯定確認(rèn)(Positive Acknowledgement)累計確認(rèn)(Cumulative Acknowledgement)捎帶確認(rèn)(Piggybacking)負(fù)確認(rèn)(Negative AcKnowledgement, NAK)重

4、傳超時重傳(Timeout Retransmission)負(fù)確認(rèn)重傳9 4.3 自動請求重傳10 4.3.1 停等自動請求重傳發(fā)送方發(fā)出一個數(shù)據(jù)幀后停下來不再發(fā)送，等待接收方的ACK到達(dá)，ACK到達(dá)后才發(fā)送下一幀。發(fā)送窗口大小是WT=1，接收窗口大小也是1。處理 3 種傳輸差錯：接收方收到了發(fā)來的數(shù)據(jù)幀，但檢測出差錯；發(fā)送方發(fā)出的數(shù)據(jù)幀丟失；接收方收到正確的數(shù)據(jù)幀，但發(fā)出的ACK丟失。對于差錯1，即收方丟棄此幀，并可采取下面兩種方式進(jìn)行重傳。負(fù)確認(rèn)重傳。超時重傳。11 4.3.1 停等自動請求重傳對于2和3這兩種差錯，可采取超時重傳。但對于差錯3，超時重傳會使接收方收到兩個同樣的數(shù)據(jù)幀。解決重

5、復(fù)幀的方法是為數(shù)據(jù)幀和確認(rèn)幀編上序號。停等ARQ采用超時重傳的方式。停等ARQ機(jī)制的問題是可能產(chǎn)生嚴(yán)重的低效率。鏈路的利用率：12 4.3.1 停等自動請求重傳停等ARQ傳輸過程示例 13 4.3.2 回退-N ARQWT1，發(fā)送方在每收到一個ACK之前不必等待，可以連續(xù)地發(fā)送窗口內(nèi)的多個幀，也稱為連續(xù)ARQ，提高了傳輸?shù)耐掏铝亢蛡鬏斝?。也使用超時重傳機(jī)制。定時器超時仍未收到ACK，則要重傳此幀，而且還必須重傳此幀后面所有的已發(fā)幀，這正是這種 機(jī)制稱為回退-N ARQ的原因。接收方的接收窗口WR=1，當(dāng)接收方收到一個有序且無差錯的幀后，接受窗口向前移動，并向發(fā)送方發(fā)出一個ACK。發(fā)送窗口應(yīng)滿

6、足：14 4.3.2 回退-N ARQ回退-N ARQ接收窗口 15 4.3.2 回退-N ARQ回退-N ARQ傳輸過程示例 16 4.3.3 選擇重傳ARQ在回退-N ARQ機(jī)制的基礎(chǔ)上作了如下兩點(diǎn)改進(jìn)：接收窗口WR1，這樣可以接收和保存正確到達(dá)的失序的幀；出現(xiàn)差錯時只重傳出錯的幀，后續(xù)正確到達(dá)的幀不再重傳，從而提高了信道的利用率。選擇重傳ARQ應(yīng)該滿足：17 4.4 差錯校驗(yàn)18 4.4.1 奇偶校驗(yàn)在發(fā)送數(shù)據(jù)后附加一個校驗(yàn)位，校驗(yàn)位的取值時的包括數(shù)據(jù)和校驗(yàn)位中的“1”的個數(shù)分別為奇數(shù)/偶數(shù)。奇偶校驗(yàn)檢錯能力有限，只能校驗(yàn)出奇數(shù)個錯但不能校驗(yàn)出偶數(shù)個錯。優(yōu)點(diǎn)是簡單、易實(shí)現(xiàn)，在位數(shù)不長的情

7、況下常常采用。19 4.4.2 循環(huán)冗余校驗(yàn)碼多項(xiàng)式n 位長度的位串 可以用n -1次碼多項(xiàng)式表示： 例如，位串的碼多項(xiàng)式為: 數(shù)據(jù)后面附加上冗余碼：k 位的信息碼后面附加上r 位的冗余碼:由信息碼生成冗余碼用一個特定的r 次多項(xiàng)式G(x)去除 ，其余數(shù)為r-1次的碼多項(xiàng)式R(x)，對應(yīng)的r 位的位串作為冗余碼。G(x)稱為生成多項(xiàng)式(Generator Polynomial)。除法中使用模2減(無借位減，相當(dāng)于作異或(XOR)運(yùn)算)。20 4.4.2 循環(huán)冗余校驗(yàn) 生成冗余碼示例 21信息段： m(x) = 111111 生成多項(xiàng)式： g(x) = 1001 ，檢驗(yàn)位 r = 3，CRC多項(xiàng)式： r(x) = 111111000 求解 r(x) 除以 g(x) 的余數(shù)： 1 1 1 0 0 0 _ 1 0 0 1 / 1 1 1 1 1 1 0 0 0 1 0 0 1 - 1 1 0 1 1 0 0 1 - 1 0 0 1 1 0 0 1 - 0 0 022 4.4.2 循環(huán)冗余校驗(yàn)傳輸差錯校驗(yàn)接收方將接收到的C(