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

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

2、ntrol)。4.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)。4.2 數(shù)據(jù)鏈路控制的基本機(jī)制 4.2.1 滑動(dòng)窗口 發(fā)送方和接收方分別設(shè)置發(fā)送窗口和接收窗口。 發(fā)送窗口用來(lái)對(duì)發(fā)送方進(jìn)行流量控制，落在窗口內(nèi)的幀是可以連續(xù)發(fā)送的，其大小wt指明在收到對(duì)方確認(rèn)(ack)之前發(fā)送方最多可以發(fā)送多

3、少個(gè)幀。 只有到達(dá)的數(shù)據(jù)幀的序號(hào)落在接收窗口之內(nèi)時(shí)才可以被接收，否則將被丟棄。一般地，當(dāng)接收方收到一個(gè)有序且無(wú)差錯(cuò)的幀后，接收窗口向前滑動(dòng)，準(zhǔn)備接收下一幀，并向發(fā)送方發(fā)送出一個(gè)ack。 當(dāng)發(fā)送方收到接收方的ack后，發(fā)送窗口才能向前滑動(dòng)，滑動(dòng)的長(zhǎng)度取決于接收方確認(rèn)的序號(hào)。 4.2.1 滑動(dòng)窗口發(fā)送方的滑動(dòng)窗口 4.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 ackno

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

5、3，超時(shí)重傳會(huì)使接收方收到兩個(gè)同樣的數(shù)據(jù)幀。解決重復(fù)幀的方法是為數(shù)據(jù)幀和確認(rèn)幀編上序號(hào)。 停等arq采用超時(shí)重傳的方式。 停等arq機(jī)制的問(wèn)題是可能產(chǎn)生嚴(yán)重的低效率。 鏈路的利用率：/2/2/2datadataackprodatadatatttttt 幀的比特長(zhǎng)度幀的比特長(zhǎng)度鏈路的比特長(zhǎng)度 4.3.1 停等自動(dòng)請(qǐng)求重傳停等arq傳輸過(guò)程示例 4.3.2 回退-n arq wt1，發(fā)送方在每收到一個(gè)ack之前不必等待，可以連續(xù)地發(fā)送窗口內(nèi)的多個(gè)幀，也稱(chēng)為連續(xù)arq，提高了傳輸?shù)耐掏铝亢蛡鬏斝省?也使用超時(shí)重傳機(jī)制。定時(shí)器超時(shí)仍未收到ack，則要重傳此幀，而且還必須重傳此幀后面所有的已發(fā)幀，這正

6、是這種 機(jī)制稱(chēng)為回退-n arq的原因。 接收方的接收窗口wr=1，當(dāng)接收方收到一個(gè)有序且無(wú)差錯(cuò)的幀后，接受窗口向前移動(dòng)，并向發(fā)送方發(fā)出一個(gè)ack。 發(fā)送窗口應(yīng)滿(mǎn)足：21ntw 最大序號(hào) 4.3.2 回退-n arq回退-n arq接收窗口 4.3.2 回退-n arq回退-n arq傳輸過(guò)程示例 4.3.3 選擇重傳arq 在回退-n arq機(jī)制的基礎(chǔ)上作了如下兩點(diǎn)改進(jìn)： 接收窗口wr1，這樣可以接收和保存正確到達(dá)的失序的幀； 出現(xiàn)差錯(cuò)時(shí)只重傳出錯(cuò)的幀，后續(xù)正確到達(dá)的幀不再重傳，從而提高了信道的利用率。 選擇重傳arq應(yīng)該滿(mǎn)足：2 / 21 / 2ntrww最大序號(hào) 4.4 差錯(cuò)校驗(yàn) 4.4

7、.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)的情況下常常采用。 4.4.2 循環(huán)冗余校驗(yàn) 碼多項(xiàng)式 n 位長(zhǎng)度的位串 可以用n -1次碼多項(xiàng)式表示： 例如，位串1010001的碼多項(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)稱(chēng)為生成多項(xiàng)式(generator polynom

8、ial)。 除法中使用模2減(無(wú)借位減，相當(dāng)于作異或(xor)運(yùn)算)。1210nncccc c 121210nnnnc xcxcxc xc641xx rc xx k xr x rx k x 4.4.2 循環(huán)冗余校驗(yàn) 生成冗余碼示例 信息段： 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 0 4.4.2 循環(huán)冗余校驗(yàn) 傳輸差錯(cuò)校驗(yàn) 接收方將接收到的c(x)除以生成多項(xiàng)式g(x)，只要余數(shù)不為零，則表明校驗(yàn)出傳輸差錯(cuò)，若余數(shù)為零，則可以認(rèn)為傳輸無(wú)誤。 常用的生成多項(xiàng)式 crc-8用于atm信元頭差錯(cuò)校驗(yàn)。 crc-16是hdlc規(guī)程中使用的。 crc-32是ieee802.3以太網(wǎng)中采用的。 4.4.3 校驗(yàn)和 ip、icmp、tcp和udp中廣泛使用校驗(yàn)和運(yùn)算的例子 二進(jìn)制反碼求和 對(duì)一個(gè)無(wú)符號(hào)的數(shù)，先求其反碼，然后從低位到高位，按位相加，有益處則向高位進(jìn)1(和一般的二進(jìn)制法則一樣),若最高位有進(jìn)位，則向最低位若最高位有進(jìn)位，則向最低位進(jìn)