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

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

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

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

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

5、復(fù)幀的方法是為數(shù)據(jù)幀和確認(rèn)幀編上序號(hào)。停等ARQ采用超時(shí)重傳的方式。停等ARQ機(jī)制的問題是可能產(chǎn)生嚴(yán)重的低效率。鏈路的利用率：12 4.3.1 停等自動(dòng)請(qǐng)求重傳停等ARQ傳輸過程示例 13 4.3.2 回退-N ARQWT1，發(fā)送方在每收到一個(gè)ACK之前不必等待，可以連續(xù)地發(fā)送窗口內(nèi)的多個(gè)幀，也稱為連續(xù)ARQ，提高了傳輸?shù)耐掏铝亢蛡鬏斝省Ｒ彩褂贸瑫r(shí)重傳機(jī)制。定時(shí)器超時(shí)仍未收到ACK，則要重傳此幀，而且還必須重傳此幀后面所有的已發(fā)幀，這正是這種 機(jī)制稱為回退-N ARQ的原因。接收方的接收窗口WR=1，當(dāng)接收方收到一個(gè)有序且無差錯(cuò)的幀后，接受窗口向前移動(dòng)，并向發(fā)送方發(fā)出一個(gè)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)差錯(cuò)時(shí)只重傳出錯(cuò)的幀，后續(xù)正確到達(dá)的幀不再重傳，從而提高了信道的利用率。選擇重傳ARQ應(yīng)該滿足：17 4.4 差錯(cuò)校驗(yàn)18 4.4.1 奇偶校驗(yàn)在發(fā)送數(shù)據(jù)后附加一個(gè)校驗(yàn)位，校驗(yàn)位的取值時(shí)的包括數(shù)據(jù)和校驗(yàn)位中的“1”的個(gè)數(shù)分別為奇數(shù)/偶數(shù)。奇偶校驗(yàn)檢錯(cuò)能力有限，只能校驗(yàn)出奇數(shù)個(gè)錯(cuò)但不能校驗(yàn)出偶數(shù)個(gè)錯(cuò)。優(yōu)點(diǎn)是簡(jiǎn)單、易實(shí)現(xiàn)，在位數(shù)不長(zhǎng)的情

7、況下常常采用。19 4.4.2 循環(huán)冗余校驗(yàn)碼多項(xiàng)式n 位長(zhǎng)度的位串 可以用n -1次碼多項(xiàng)式表示： 例如，位串的碼多項(xiàng)式為: 數(shù)據(jù)后面附加上冗余碼：k 位的信息碼后面附加上r 位的冗余碼:由信息碼生成冗余碼用一個(gè)特定的r 次多項(xiàng)式G(x)去除 ，其余數(shù)為r-1次的碼多項(xiàng)式R(x)，對(duì)應(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)傳輸差錯(cuò)校驗(yàn)接收方將接收到的C(