第五章 數(shù)字鏈路控制及其協(xié)議

1、第五章 數(shù)字鏈路控制及其協(xié)議 網(wǎng)絡(luò)原理 課程講義 第五章 數(shù)據(jù)鏈路掌握及其協(xié)議 網(wǎng)絡(luò)原理 課程講義 主要內(nèi)容5.1 定義和功能5.1.1 5.1.2 5.1.3 5.1.4 5.1.5 定義 為網(wǎng)絡(luò)層供應(yīng)服務(wù) 成幀 差錯掌握 流量掌握糾錯碼 檢錯碼 無約束單工協(xié)議 單工停等協(xié)議 有噪聲信道的單工協(xié)議 5.2 錯誤檢測和訂正5.2.1 5.2.2 5.3 基本的數(shù)據(jù)鏈路層協(xié)議5.3.1 5.3.2 5.3.3 網(wǎng)絡(luò)原理 課程講義 5.4 滑動窗口協(xié)議5.4.1 5.4.2 5.4.3 一比特滑動窗口協(xié)議 退后n幀協(xié)議 選擇重傳協(xié)議通信協(xié)議中的形式化描述技術(shù) 有限狀態(tài)機(jī)模型 petri網(wǎng)模型 高級

2、數(shù)據(jù)鏈路掌握規(guī)程 hdlc x.25的鏈路層協(xié)議lapb internet數(shù)據(jù)鏈路層協(xié)議 atm數(shù)據(jù)鏈路層協(xié)議 5.5 協(xié)議說明與驗(yàn)證5.5.1 5.5.2 5.5.3 5.6 常用的數(shù)據(jù)鏈路層協(xié)議5.6.1 5.6.2 5.6.3 5.6.4 網(wǎng)絡(luò)原理 課程講義 5.1 定義和功能(1)5.1.1 定義 要解決的問題- 如何在有差錯的線路上，進(jìn)行無差錯傳輸。 iso關(guān)于數(shù)據(jù)鏈路層的定義- 數(shù)據(jù)鏈路層的目的是為了供應(yīng)功能上和規(guī)程上的方法 ，以便建立、維護(hù)和釋放網(wǎng)絡(luò)實(shí)體間的數(shù)據(jù)鏈路。 數(shù)據(jù)鏈路- 從數(shù)據(jù)發(fā)送點(diǎn)到數(shù)據(jù)接收點(diǎn)(點(diǎn)到點(diǎn) point to point) 所經(jīng)過的傳輸途徑。 虛擬數(shù)據(jù)通路，

3、實(shí)際數(shù)據(jù)通路- fig. 3-14 網(wǎng)絡(luò)原理 課程講義 網(wǎng)絡(luò)原理 課程講義 5.1 定義和功能(2)數(shù)據(jù)鏈路掌握規(guī)程- 為使數(shù)據(jù)能快速、正確、有效地從發(fā)送點(diǎn)到達(dá)接收點(diǎn)所 采納的掌握方式。 數(shù)據(jù)鏈路層協(xié)議應(yīng)供應(yīng)的最基本功能數(shù)據(jù)在數(shù)據(jù)鏈路上的正常傳輸(建立、維護(hù)和釋放) 定界與同步，也處理透亮性問題 差錯掌握 挨次掌握 流量掌握 網(wǎng)絡(luò)原理 課程講義 5.1 定義和功能(3)5.1.2 為網(wǎng)絡(luò)層供應(yīng)服務(wù) 為網(wǎng)絡(luò)層供應(yīng)三種合理的服務(wù)- 無確認(rèn)無連接服務(wù)，適用于 誤碼率很低的線路，錯誤恢復(fù)留給高層； 實(shí)時業(yè)務(wù) 大部分局域網(wǎng) - 有確認(rèn)無連接服務(wù)，適用于不行靠的信道，如無線網(wǎng)。 - 有確認(rèn)有連接服務(wù) 網(wǎng)絡(luò)

4、原理 課程講義 5.1 定義和功能(4)5.1.3 成幀(framing) 將比特流分成離散的幀，并計(jì)算每個幀的校驗(yàn)和。 成幀方法：- 字符計(jì)數(shù)法 在幀頭中用一個域來表示整個幀的字符個數(shù) 缺點(diǎn)：若計(jì)數(shù)出錯，對本幀和后面的幀有影響。 fig. 3-3 - 帶字符填充的首尾字符定界法 起始字符 dle stx,結(jié)束字符dle etx 字符填充 fig. 3-4 缺點(diǎn)：局限于8位字符和ascii字符傳送。8 網(wǎng)絡(luò)原理 課程講義 5.1 定義和功能(5)- 帶位填充的首尾標(biāo)記定界法 幀的起始和結(jié)束都用一個特別的位串“01111110”, 稱為標(biāo)記(flag) “0”比特插入刪除技術(shù) fig. 3-5

5、- 物理層編碼違例法 只適用于物理層編碼有冗余的網(wǎng)絡(luò) 802 lan:manchester encoding or differential manchester encoding 用high-low pair/low-high pair 表示1/0,high-high/low-low不表示數(shù)據(jù)，可以用來 做定界符。 留意：在許多數(shù)據(jù)鏈路協(xié)議中，使用字符計(jì)數(shù)法 和一種 其它方法的組合。9 網(wǎng)絡(luò)原理 課程講義 網(wǎng)絡(luò)原理 課程講義 網(wǎng)絡(luò)原理 課程講義 網(wǎng)絡(luò)原理 課程講義 5.1 定義和功能(6)5.1.4 差錯掌握 一般方法：接收方給發(fā)送方一個反饋(響應(yīng))。 出錯狀況- 幀(包括發(fā)送幀和響應(yīng)幀)出

6、錯； - 幀(包括發(fā)送幀和響應(yīng)幀)丟失 通過計(jì)時器和序號保證每幀最終交給目的網(wǎng)絡(luò)層 僅一次是數(shù)據(jù)鏈路層的一個主要功能。 5.1.5 流量掌握 基于反饋機(jī)制 流量掌握主要在傳輸層實(shí)現(xiàn)13 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(1) 差錯消失的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)(burst) 處理差錯的兩種基本策略- 使用糾錯碼：發(fā)送方在每個數(shù)據(jù)塊中加入足夠的冗余信息 ，使得接收方能夠推斷接收到的數(shù)據(jù)是否有錯，并能訂正 錯誤。 - 使用檢錯碼：發(fā)送方在每個數(shù)據(jù)塊中加入足夠的冗余信息 ，使得接收方能夠推斷接收到的數(shù)據(jù)是否有錯，但不能判 斷哪里有錯。 5.2.1 糾錯碼 碼字(codeword):一個幀包括m

7、個數(shù)據(jù)位，r個 校驗(yàn)位，n = m + r,則此n比特單元稱為n位碼字。 海明距離(hamming distance):兩個碼字之間 不同的比特位數(shù)目。14 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(2)- 例：0000000000 與0000011111的海明距離為5 - 假如兩個碼字的海明距離為d,則需要d個單比特錯就可 以把一個碼字轉(zhuǎn)換成另一個碼字； - 為了檢查出d個錯(單比特錯),需要使用海明距離為 d + 1 的編碼； - 為了訂正d個錯，需要使用海明距離為 2d + 1 的編碼； 最簡潔的例子是奇偶校驗(yàn)，在數(shù)據(jù)后填加一個奇 偶位(parity bit)- 例：使用偶校驗(yàn)(“1”

8、的個數(shù)為偶數(shù)) 10110101 101101011 10110001 101100010 - 奇偶校驗(yàn)可以用來檢查單個錯誤。 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(3) 設(shè)計(jì)糾錯碼- 要求：m個信息位，r個校驗(yàn)位，訂正單比特錯； - 對2m個有效信息中任何一個，有n個與其距離為1的無效碼字，因 此有：(n + 1) 2m 2n 利用 n = m + r,得到 (m + r + 1) 2r 給定m,利用該式可以得出校正單比特誤碼的校驗(yàn)位數(shù)目的下界 海明碼- 碼位從左邊開頭編號，從“1”開頭； - 位號為2的冪的位是校驗(yàn)位，其余是信息位； - 每個校驗(yàn)位使得包括自己在內(nèi)的一些位的奇偶值為偶

9、數(shù)(或奇數(shù) )。 - 為看清數(shù)據(jù)位k對哪些校驗(yàn)位有影響，將k寫成2的冪的和。 - 例：11 = 1 + 2 + 816 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(4) 海明碼工作過程每個碼字到來前，接收方計(jì)數(shù)器清零； 接收方檢查每個校驗(yàn)位k (k = 1, 2, 4 )的奇偶值是否正確； 若第 k 位奇偶值不對，計(jì)數(shù)器加 k; 全部校驗(yàn)位檢查完后，若計(jì)數(shù)器值為0,則碼字有效；若計(jì)數(shù) 器值為m,則第m位出錯。 - 若校驗(yàn)位1、2、8出錯，則第11位變反。 - fig. 3-6 - 使用海明碼訂正突發(fā)錯誤- 可采納k個碼字(n = m + r)組成 k n 矩陣，按列發(fā)送，接收 方恢復(fù)成 k n

10、 矩陣 - kr個校驗(yàn)位，km個數(shù)據(jù)位，可訂正最多為k個的突發(fā)性連續(xù)比 特錯。17 網(wǎng)絡(luò)原理 課程講義 1 2 3 4 5 6 1 1 2 2 4 4 7 8 9 10 11 1 1 1 2 2 2 4 8 8 8 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(5)5.2.2 檢錯碼 使用糾錯碼傳數(shù)據(jù)，效率低，適用于不行能重傳 的場合；大多數(shù)狀況采納檢錯碼加重傳。 循環(huán)冗余碼(crc碼，多項(xiàng)式編碼)- 110001,表示成多項(xiàng)式 x5 + x4 + 1 生成多項(xiàng)式g(x)- 發(fā)方、收方事前商定； - 生成多項(xiàng)式的高位和低位必需為1 - 生成多項(xiàng)式必需比傳輸信息對應(yīng)的多項(xiàng)式短。 crc碼基本思想-

11、 校驗(yàn)和(checksum)加在幀尾，使帶校驗(yàn)和的幀的多項(xiàng) 式能被g(x)除盡；收方接收時，用g(x)去除它，若有余 數(shù)，則傳輸出錯。19 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(6) 校驗(yàn)和計(jì)算算法- 設(shè)g(x)為 r 階，在幀的末尾加 r 個0,使幀為m + r位，相應(yīng) 多項(xiàng)式為xrm(x); - 按模2除法用對應(yīng)于g(x)的位串去除對應(yīng)于xrm(x)的位串； - 按模2減法從對應(yīng)于xrm(x)的位串中減去余數(shù)(等于或小于r 位),結(jié)果就是要傳送的帶校驗(yàn)和的多項(xiàng)式t(x)。 - fig. 3-7 crc的檢錯力量- 發(fā)送：t(x);接收：t(x) + e(x); - 余數(shù)(t(x) +

12、 e(x) / g(x) = 0 + 余數(shù)(e(x) / g(x) - 若 余數(shù)(e(x) / g(x) = 0,則差錯不能發(fā)覺；否則，可以發(fā) 現(xiàn)。 網(wǎng)絡(luò)原理 課程講義 5.2 錯誤檢測和訂正(7)- 假如只有單比特錯，即e(x) = xi,而g(x)中至少有兩項(xiàng)， 余數(shù)(e(x) / g(x) 0,所以可以查出單比特錯； - 假如發(fā)生兩個孤立單比特錯，即e(x) = xi + xj = xj (xi-j + 1),假定g(x)不能被x整除，那么能夠發(fā)覺兩個比特錯的 充分條件是：xk + 1不能被g(x)整除 (k i - j); - 假如有奇數(shù)個比特錯，即e(x)包括奇數(shù)個項(xiàng)，g(x)選(x + 1)的倍數(shù)就能查特別數(shù)個比特錯； - 具有r個校驗(yàn)位的多項(xiàng)式能檢查出全部長度 r 的突發(fā)性 差錯。長度為k的突發(fā)性連續(xù)差錯(并不表示有k個單比 特錯