數(shù)據(jù)鏈路控制及其協(xié)議教學(xué)課件

第五章

數(shù)據(jù)鏈路控制及其協(xié)議1a第五章

數(shù)據(jù)鏈路控制及其協(xié)議1a主要內(nèi)容5.1 定義和功能5.1.1 定義5.1.2 為網(wǎng)絡(luò)層提供服務(wù)5.1.3 成幀5.1.4 差錯(cuò)控制5.1.5 流量控制5.2 錯(cuò)誤檢測和糾正5.2.1 糾錯(cuò)碼5.2.2 檢錯(cuò)碼5.3 基本的數(shù)據(jù)鏈路層協(xié)議 5.3.1 無約束單工協(xié)議 5.3.2 單工停等協(xié)議 5.3.3 有噪聲信道的單工協(xié)議2a主要內(nèi)容5.1 定義和功能2a5.4 滑動(dòng)窗口協(xié)議 5.4.1 一比特滑動(dòng)窗口協(xié)議 5.4.2 退后n幀協(xié)議 5.4.3 選擇重傳協(xié)議5.5 協(xié)議說明與驗(yàn)證 5.5.1 通信協(xié)議中的形式化描述技術(shù) 5.5.2 有限狀態(tài)機(jī)模型 5.5.3 Petri網(wǎng)模型5.6 常用的數(shù)據(jù)鏈路層協(xié)議5.6.1 高級數(shù)據(jù)鏈路控制規(guī)程HDLC5.6.2 X.25的鏈路層協(xié)議LAPB5.6.3 Internet數(shù)據(jù)鏈路層協(xié)議5.6.4 ATM數(shù)據(jù)鏈路層協(xié)議3a5.4 滑動(dòng)窗口協(xié)議3a5.1 定義和功能（1）5.1.1定義要解決的問題如何在有差錯(cuò)的線路上，進(jìn)行無差錯(cuò)傳輸。ISO關(guān)于數(shù)據(jù)鏈路層的定義數(shù)據(jù)鏈路層的目的是為了提供功能上和規(guī)程上的方法，以便建立、維護(hù)和釋放網(wǎng)絡(luò)實(shí)體間的數(shù)據(jù)鏈路。結(jié)點(diǎn)（node）：網(wǎng)絡(luò)中的主機(jī)（host）和路由器（router）稱為結(jié)點(diǎn)鏈路（link）：通信路徑上連接相鄰結(jié)點(diǎn)的通信信道稱為鏈路。數(shù)據(jù)鏈路層協(xié)議定義了一條鏈路的兩個(gè)結(jié)點(diǎn)間交換的數(shù)據(jù)單元格式，以及結(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)單元的動(dòng)作。4a5.1 定義和功能（1）5.1.1定義4a5.1 定義和功能（2）端到端（endtoend）與點(diǎn)到點(diǎn)（pointtopoint）從源結(jié)點(diǎn)（sourcenode）到目的結(jié)點(diǎn)（destinationnode）的通信稱為端到端通信，通信路徑（path）可能由多個(gè)鏈路組成。在相鄰結(jié)點(diǎn)間的一條鏈路上的通信稱為點(diǎn)到點(diǎn)通信。虛擬數(shù)據(jù)通路，實(shí)際數(shù)據(jù)通路Fig.3-15a5.1 定義和功能（2）端到端（endtoend）與點(diǎn)到6a6a5.1 定義和功能（2）數(shù)據(jù)鏈路控制規(guī)程為使數(shù)據(jù)能迅速、正確、有效地從發(fā)送點(diǎn)到達(dá)接收點(diǎn)所采用的控制方式。數(shù)據(jù)鏈路層協(xié)議應(yīng)提供的最基本功能數(shù)據(jù)在數(shù)據(jù)鏈路上的正常傳輸（建立、維護(hù)和釋放）定界與同步，也處理透明性問題差錯(cuò)控制順序控制流量控制7a5.1 定義和功能（2）數(shù)據(jù)鏈路控制規(guī)程7a5.1 定義和功能（3）5.1.2為網(wǎng)絡(luò)層提供服務(wù)為網(wǎng)絡(luò)層提供三種合理的服務(wù)無確認(rèn)無連接服務(wù)，適用于誤碼率很低的線路，錯(cuò)誤恢復(fù)留給高層；實(shí)時(shí)業(yè)務(wù)大部分局域網(wǎng)有確認(rèn)無連接服務(wù)，適用于不可靠的信道，如無線網(wǎng)。有確認(rèn)有連接服務(wù)8a5.1 定義和功能（3）5.1.2為網(wǎng)絡(luò)層提供服務(wù)8a5.1 定義和功能（4）5.1.3成幀（Framing）將比特流分成離散的幀，并計(jì)算每個(gè)幀的校驗(yàn)和。成幀方法：字符計(jì)數(shù)法在幀頭中用一個(gè)域來表示整個(gè)幀的字符個(gè)數(shù)缺點(diǎn)：若計(jì)數(shù)出錯(cuò)，對本幀和后面的幀有影響。Fig.3-3帶字符填充的首尾字符定界法起始字符DLESTX，結(jié)束字符DLEETX字符填充 Fig.3-4缺點(diǎn)：局限于8位字符和ASCII字符傳送。9a5.1 定義和功能（4）5.1.3成幀（Framing）5.1 定義和功能（5）帶位填充的首尾標(biāo)記定界法幀的起始和結(jié)束都用一個(gè)特殊的位串“01111110”，稱為標(biāo)記(flag)“0”比特插入刪除技術(shù)Fig.3-5物理層編碼違例法只適用于物理層編碼有冗余的網(wǎng)絡(luò)802LAN：ManchesterencodingorDifferentialManchesterencoding用high-lowpair/low-highpair表示1/0，high-high/low-low不表示數(shù)據(jù)，可以用來做定界符。注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計(jì)數(shù)法和一種其它方法的組合。10a5.1 定義和功能（5）帶位填充的首尾標(biāo)記定界法10a11a11a12a12a13a13a5.1 定義和功能（6）5.1.4差錯(cuò)控制一般方法：接收方給發(fā)送方一個(gè)反饋（響應(yīng)）。出錯(cuò)情況幀（包括發(fā)送幀和響應(yīng)幀）出錯(cuò)；幀（包括發(fā)送幀和響應(yīng)幀）丟失通過計(jì)時(shí)器和序號(hào)保證每幀最終交給目的網(wǎng)絡(luò)層僅一次是數(shù)據(jù)鏈路層的一個(gè)主要功能。5.1.5流量控制基于反饋機(jī)制流量控制主要在傳輸層實(shí)現(xiàn)14a5.1 定義和功能（6）5.1.4差錯(cuò)控制14a5.2 錯(cuò)誤檢測和糾正（1）差錯(cuò)出現(xiàn)的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)（burst）處理差錯(cuò)的兩種基本策略使用糾錯(cuò)碼：發(fā)送方在每個(gè)數(shù)據(jù)塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數(shù)據(jù)是否有錯(cuò)，并能糾正錯(cuò)誤。使用檢錯(cuò)碼：發(fā)送方在每個(gè)數(shù)據(jù)塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數(shù)據(jù)是否有錯(cuò)，但不能判斷哪里有錯(cuò)。5.2.1 糾錯(cuò)碼碼字（codeword）：一個(gè)幀包括m個(gè)數(shù)據(jù)位，r個(gè)校驗(yàn)位，n=m+r，則此n比特單元稱為n位碼字。海明距離（Hammingdistance）：兩個(gè)碼字之間不同的比特位數(shù)目。15a5.2 錯(cuò)誤檢測和糾正（1）差錯(cuò)出現(xiàn)的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)（5.2 錯(cuò)誤檢測和糾正（2）例：0000000000與0000011111的海明距離為5如果兩個(gè)碼字的海明距離為d，則需要d個(gè)單比特錯(cuò)就可以把一個(gè)碼字轉(zhuǎn)換成另一個(gè)碼字；為了檢查出d個(gè)錯(cuò)（單比特錯(cuò)），需要使用海明距離為d+1的編碼；為了糾正d個(gè)錯(cuò)，需要使用海明距離為2d+1的編碼；最簡單的例子是奇偶校驗(yàn)，在數(shù)據(jù)后填加一個(gè)奇偶位（paritybit）例：使用偶校驗(yàn)（“1”的個(gè)數(shù)為偶數(shù)） 10110101 ——> 101101011 10110001 ——> 101100010奇偶校驗(yàn)可以用來檢查單個(gè)錯(cuò)誤。16a5.2 錯(cuò)誤檢測和糾正（2）例：0000000000與005.2 錯(cuò)誤檢測和糾正（3）設(shè)計(jì)糾錯(cuò)碼要求：m個(gè)信息位，r個(gè)校驗(yàn)位，糾正單比特錯(cuò)；對2m個(gè)有效信息中任何一個(gè)，有n個(gè)與其距離為1的無效碼字，因此有：(n+1)2m

2n 利用n=m+r，得到(m+r+1)2r 給定m，利用該式可以得出校正單比特誤碼的校驗(yàn)位數(shù)目的下界海明碼碼位從左邊開始編號(hào)，從“1”開始；位號(hào)為2的冪的位是校驗(yàn)位，其余是信息位；每個(gè)校驗(yàn)位使得包括自己在內(nèi)的一些位的奇偶值為偶數(shù)（或奇數(shù)）。為看清數(shù)據(jù)位k對哪些校驗(yàn)位有影響，將k寫成2的冪的和。例：11=1+2+817a5.2 錯(cuò)誤檢測和糾正（3）設(shè)計(jì)糾錯(cuò)碼17a5.2 錯(cuò)誤檢測和糾正（4）海明碼工作過程每個(gè)碼字到來前，接收方計(jì)數(shù)器清零；接收方檢查每個(gè)校驗(yàn)位k(k=1,2,4…)的奇偶值是否正確；若第k位奇偶值不對，計(jì)數(shù)器加k；所有校驗(yàn)位檢查完后，若計(jì)數(shù)器值為0，則碼字有效；若計(jì)數(shù)器值為m，則第m位出錯(cuò)。若校驗(yàn)位1、2、8出錯(cuò)，則第11位變反。Fig.3-6使用海明碼糾正突發(fā)錯(cuò)誤可采用k個(gè)碼字（n=m+r）組成kn矩陣，按列發(fā)送，接收方恢復(fù)成kn矩陣kr個(gè)校驗(yàn)位，km個(gè)數(shù)據(jù)位，可糾正最多為k個(gè)的突發(fā)性連續(xù)比特錯(cuò)。18a5.2 錯(cuò)誤檢測和糾正（4）海明碼工作過程18a12345678

91011111112222244488819a123456785.2 錯(cuò)誤檢測和糾正（5）5.2.2檢錯(cuò)碼使用糾錯(cuò)碼傳數(shù)據(jù)，效率低，適用于不可能重傳的場合；大多數(shù)情況采用檢錯(cuò)碼加重傳。循環(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碼基本思想校驗(yàn)和（checksum）加在幀尾，使帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)除盡；收方接收時(shí)，用G(x)去除它，若有余數(shù)，則傳輸出錯(cuò)。20a5.2 錯(cuò)誤檢測和糾正（5）5.2.2檢錯(cuò)碼20a5.2 錯(cuò)誤檢測和糾正（6）校驗(yàn)和計(jì)算算法設(shè)G(x)為r階，在幀的末尾加r個(gè)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-7CRC的檢錯(cuò)能力發(fā)送：T(x)；接收：T(x)+E(x)；余數(shù)((T(x)+E(x))/G(x))=0+余數(shù)(E(x)/G(x))若余數(shù)(E(x)/G(x))=0，則差錯(cuò)不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。21a5.2 錯(cuò)誤檢測和糾正（6）校驗(yàn)和計(jì)算算法21a5.2 錯(cuò)誤檢測和糾正（7）如果只有單比特錯(cuò)，即E(x)=xi，而G(x)中至少有兩項(xiàng)，余數(shù)(E(x)/G(x))

0，所以可以查出單比特錯(cuò)；如果發(fā)生兩個(gè)孤立單比特錯(cuò)，即E(x)=xi+xj=xj(xi-j+1)，假定G(x)不能被x整除，那么能夠發(fā)現(xiàn)兩個(gè)比特錯(cuò)的充分條件是：xk+1不能被G(x)整除(ki-j)；如果有奇數(shù)個(gè)比特錯(cuò)，即E(x)包括奇數(shù)個(gè)項(xiàng)，G(x)選(x+1)的倍數(shù)就能查出奇數(shù)個(gè)比特錯(cuò)；具有r個(gè)校驗(yàn)位的多項(xiàng)式能檢查出所有長度r的突發(fā)性差錯(cuò)。長度為k的突發(fā)性連續(xù)差錯(cuò)（并不表示有k個(gè)單比特錯(cuò)）可表示為xi(xk-1+…+1)，若G(x)包括x0項(xiàng)，且k-1小于G(x)的階，則余數(shù)(E(x)/G(x))0;如果突發(fā)差錯(cuò)長度為r+1，當(dāng)且僅當(dāng)突發(fā)差錯(cuò)和G(x)一樣時(shí)，余數(shù)(E(x)/G(x))=0，概率為1/2r-1;長度大于r+1的突發(fā)差錯(cuò)或幾個(gè)較短的突發(fā)差錯(cuò)發(fā)生后，壞幀被接收的概率為1/2r。22a5.2 錯(cuò)誤檢測和糾正（7）如果只有單比特錯(cuò)，即E(x)=5.2 錯(cuò)誤檢測和糾正（8）四個(gè)多項(xiàng)式已成為國際標(biāo)準(zhǔn)CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32硬件實(shí)現(xiàn)CRC校驗(yàn)網(wǎng)卡NIC（NetworkInterfaceCard）23a5.2 錯(cuò)誤檢測和糾正（8）四個(gè)多項(xiàng)式已成為國際標(biāo)準(zhǔn)23a24a24a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（1）5.3.1無約束單工協(xié)議（AnUnrestrictedSimplexProtocol）工作在理想情況，幾個(gè)前提：單工傳輸發(fā)送方無休止工作（要發(fā)送的信息無限多）接收方無休止工作（緩沖區(qū)無限大）通信線路（信道）不損壞或丟失信息幀工作過程發(fā)送程序:取數(shù)據(jù)，構(gòu)成幀，發(fā)送幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層Fig.3-925a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（1）5.3.1無約束單工協(xié)26a26a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（2）5.3.2單工停等協(xié)議（ASimplexStop-and-WaitProtocol）增加約束條件：接收方不能無休止接收。解決辦法：接收方每收到一個(gè)幀后，給發(fā)送方回送一個(gè)響應(yīng)。工作過程發(fā)送程序：取數(shù)據(jù)，成幀，發(fā)送幀，等待響應(yīng)幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層，回送響應(yīng)幀。Fig.3-1027a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（2）5.3.2單工停等協(xié)議28a28a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（3）5.3.3有噪聲信道的單工協(xié)議（ASimplexProtocolforaNoisyChannel）增加約束條件：信道（線路）有差錯(cuò)，信息幀可能損壞或丟失。解決辦法：出錯(cuò)重傳。帶來的問題：什么時(shí)候重傳——定時(shí)響應(yīng)幀損壞怎么辦（重復(fù)幀）——發(fā)送幀頭中放入序號(hào)為了使幀頭精簡，序號(hào)取多少位——1位發(fā)方在發(fā)下一個(gè)幀之前等待一個(gè)肯定確認(rèn)的協(xié)議叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）29a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（3）5.3.3有噪聲信道的5.3 基本的數(shù)據(jù)鏈路層協(xié)議（4）工作過程Fig.3-11注意協(xié)議3的漏洞由于確認(rèn)幀中沒有序號(hào)，超時(shí)時(shí)間不能太短，否則協(xié)議失敗。因此假設(shè)協(xié)議3的發(fā)送和接收嚴(yán)格交替進(jìn)行。Fig.3-11（與教材不同）的實(shí)現(xiàn)是正確的，確認(rèn)幀有序號(hào)發(fā)送接收001ACKACK30a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（4）工作過程001ACKACK31a31a5.4 滑動(dòng)窗口協(xié)議（1）單工——>全雙工捎帶/載答（piggybacking）：暫時(shí)延遲待發(fā)確認(rèn)，以便附加在下一個(gè)待發(fā)數(shù)據(jù)幀的技術(shù)。優(yōu)點(diǎn)：充分利用信道帶寬，減少幀的數(shù)目意味著減少“幀到達(dá)”中斷；帶來的問題：復(fù)雜。本節(jié)的三個(gè)協(xié)議統(tǒng)稱滑動(dòng)窗口協(xié)議，都能在實(shí)際（非理想）環(huán)境下正常工作，區(qū)別僅在于效率、復(fù)雜性和對緩沖區(qū)的要求。32a5.4 滑動(dòng)窗口協(xié)議（1）單工——>全雙工32a5.4 滑動(dòng)窗口協(xié)議（2）滑動(dòng)窗口協(xié)議（SlidingWindowProtocol）工作原理：發(fā)送的信息幀都有一個(gè)序號(hào)，從0到某個(gè)最大值，0~2n-1，一般用n個(gè)二進(jìn)制位表示；發(fā)送端始終保持一個(gè)已發(fā)送但尚未確認(rèn)的幀的序號(hào)表，稱為發(fā)送窗口。發(fā)送窗口的上界表示要發(fā)送的下一個(gè)幀的序號(hào)，下界表示未得到確認(rèn)的幀的最小編號(hào)。發(fā)送窗口大小=上界-下界，大小可變；發(fā)送端每發(fā)送一個(gè)幀，序號(hào)取上界值，上界加1；每接收到一個(gè)正確響應(yīng)幀，下界加1；接收端有一個(gè)接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號(hào)最大的幀，下界表示希望接收的幀；接收窗口容納允許接收的信息幀，落在窗口外的幀均被丟棄。序號(hào)等于下界的幀被正確接收，并產(chǎn)生一個(gè)響應(yīng)幀，上界、下界都加1。接收窗口大小不變。Fig.3-1233a5.4 滑動(dòng)窗口協(xié)議（2）滑動(dòng)窗口協(xié)議（SlidingWi34a34a5.4 滑動(dòng)窗口協(xié)議（3）5.4.1 一比特滑動(dòng)窗口協(xié)議（AOneBitSlidingWindowProtocol）協(xié)議特點(diǎn)窗口大?。篘=1，發(fā)送序號(hào)和接收序號(hào)的取值范圍：0，1；可進(jìn)行數(shù)據(jù)雙向傳輸，信息幀中可含有確認(rèn)信息（piggybacking技術(shù)）；信息幀中包括兩個(gè)序號(hào)域：發(fā)送序號(hào)和接收序號(hào)（已經(jīng)正確收到的幀的序號(hào)）工作過程Fig.3-1335a5.4 滑動(dòng)窗口協(xié)議（3）5.4.1 一比特滑動(dòng)窗口協(xié)議（A36a36a37a37a5.4 滑動(dòng)窗口協(xié)議（4）存在問題能保證無差錯(cuò)傳輸，但是基于停等方式；若雙方同時(shí)開始發(fā)送，則會(huì)有一半重復(fù)幀；Fig.3-14（書上圖有誤）效率低，傳輸時(shí)間長。38a5.4 滑動(dòng)窗口協(xié)議（4）存在問題38a39a39a5.4 滑動(dòng)窗口協(xié)議（5）5.4.2退后n幀協(xié)議（AProtocolUsingGoBackn）為提高傳輸效率而設(shè)計(jì)例：衛(wèi)星信道傳輸速率50kbps，往返傳輸延遲500ms，若傳1000bit的幀，使用協(xié)議4，則傳輸一個(gè)幀所需時(shí)間為：發(fā)送時(shí)間+信息信道延遲+確認(rèn)信道延遲（確認(rèn)幀很短，忽略發(fā)送時(shí)間）=1000bit/50kbps+250ms+250ms=520ms信道利用率=20/5204%一般情況信道帶寬b比特/秒，幀長度L比特，往返傳輸延遲R秒，則信道利用率為(L/b)/(L/b+R)=L/(L+Rb)結(jié)論傳輸延遲大，信道帶寬高，幀短時(shí)，信道利用率低。40a5.4 滑動(dòng)窗口協(xié)議（5）5.4.2退后n幀協(xié)議（AP5.4 滑動(dòng)窗口協(xié)議（6）解決辦法連續(xù)發(fā)送多幀后再等待確認(rèn)，稱為流水線技術(shù)（pipelining）。帶來的問題信道誤碼率高時(shí)，對損壞幀和非損壞幀的重傳非常多兩種基本方法退后n幀（gobackn）接收方從出錯(cuò)幀起丟棄所有后繼幀；接收窗口為1；對于出錯(cuò)率較高的信道，浪費(fèi)帶寬。Fig.3-15(a)

41a5.4 滑動(dòng)窗口協(xié)議（6）解決辦法41a5.4 滑動(dòng)窗口協(xié)議（7）選擇重傳（selectiverepeat）接收窗口大于1，先暫存出錯(cuò)幀的后繼幀；只重傳壞幀；對最高序號(hào)的幀進(jìn)行確認(rèn)；接收窗口較大時(shí)，需較大緩沖區(qū)。Fig.3-15(b)注意：Fig.3-15(b)中可能出現(xiàn)的錯(cuò)誤42a5.4 滑動(dòng)窗口協(xié)議（7）選擇重傳（selectivere43a43a5.4 滑動(dòng)窗口協(xié)議（8）退后n幀協(xié)議發(fā)送方有流量控制，為重傳設(shè)緩沖；發(fā)送窗口未滿，EnableNetworkLayer發(fā)送窗口滿，DisableNetworkLayer發(fā)送窗口大小<序號(hào)個(gè)數(shù)（MaxSeq+1）；考慮MaxSeq=7的情況1發(fā)送方發(fā)送幀0~7；2序號(hào)為7的幀的確認(rèn)被捎帶回發(fā)送方；3發(fā)送方發(fā)送另外8個(gè)幀，序號(hào)為0~7；4另一個(gè)對幀7的捎帶確認(rèn)返回。問題：第二次發(fā)送的8個(gè)幀成功了還是丟失了？退后n幀重發(fā)；由于有多個(gè)未確認(rèn)幀，設(shè)多個(gè)計(jì)時(shí)器。44a5.4 滑動(dòng)窗口協(xié)議（8）退后n幀協(xié)議44a5.4 滑動(dòng)窗口協(xié)議（9）工作過程 Fig.3-16計(jì)時(shí)器實(shí)現(xiàn) Fig.3-1745a5.4 滑動(dòng)窗口協(xié)議（9）工作過程 45a46a46a47a47a48a48a49a49a50a50a5.4 滑動(dòng)窗口協(xié)議（10）P5協(xié)議實(shí)現(xiàn)分析事件驅(qū)動(dòng)Network_layer_ready（內(nèi)部事件）發(fā)送幀（幀序號(hào)，確認(rèn)序號(hào)，數(shù)據(jù)）Frame_arrival（外部事件）檢查幀序號(hào)，落在接收窗口內(nèi)則接收，否則丟棄；檢查確認(rèn)序號(hào)，落在發(fā)送窗口內(nèi)則移動(dòng)發(fā)送窗口，否則不做處理。Cksum_err（外部事件）丟棄timeout（內(nèi)部事件）退后n幀重傳計(jì)時(shí)器處理啟動(dòng)，發(fā)送幀時(shí)啟動(dòng)停止，收到正確確認(rèn)時(shí)停止超時(shí)則產(chǎn)生timeout事件51a5.4 滑動(dòng)窗口協(xié)議（10）P5協(xié)議實(shí)現(xiàn)分析51a5.4 滑動(dòng)窗口協(xié)議（11）5.4.3選擇重傳協(xié)議（AProtocolUsingSelectiveRepeat）目的在不可靠信道上有效傳輸時(shí)，不會(huì)因重傳而浪費(fèi)信道資源，采用選擇重傳技術(shù)。基本原理發(fā)送窗口大?。篗axSeq，接收窗口大小：(MaxSeq+1)/2保證接收窗口前移后與原窗口沒有重疊；設(shè)MaxSeq=7,若接收窗口=7，發(fā)方發(fā)幀0~6，收方全部收到，接收窗口前移（7~5），確認(rèn)幀丟失，發(fā)方重傳幀0，收方作為新幀接收，并對幀6確認(rèn)，發(fā)方發(fā)新幀7~5，收方已收過幀0，丟棄新幀0，協(xié)議出錯(cuò)。Fig.3-1952a5.4 滑動(dòng)窗口協(xié)議（11）5.4.3選擇重傳協(xié)議（A5.4 滑動(dòng)窗口協(xié)議（12）發(fā)送窗口下界：AckExpected，上界：NextFrameToSend接收窗口下界：FrameExpected，上界：TooFar緩沖區(qū)設(shè)置發(fā)送方和接收方的緩沖區(qū)大小應(yīng)等于各自窗口大?。辉黾哟_認(rèn)計(jì)時(shí)器，解決兩個(gè)方向負(fù)載不平衡帶來的阻塞問題；可隨時(shí)發(fā)送否定性確認(rèn)幀NAK。工作過程Fig.3-1853a5.4 滑動(dòng)窗口協(xié)議（12）發(fā)送窗口下界：AckExpect54a54a55a55a56a56a57a57a58a58a5.4 滑動(dòng)窗口協(xié)議（13）P6協(xié)議實(shí)現(xiàn)分析事件驅(qū)動(dòng)Network_layer_ready（內(nèi)部事件）發(fā)送幀（幀類型，幀序號(hào)，確認(rèn)序號(hào)，數(shù)據(jù)）Frame_arrival（外部事件）若是數(shù)據(jù)幀，則檢查幀序號(hào)，落在接收窗口內(nèi)則接收，否則丟棄；不等于接收窗口下界還要發(fā)NAK若是NAK，則選擇重傳；檢查確認(rèn)序號(hào)，落在發(fā)送窗口內(nèi)則移動(dòng)發(fā)送窗口，否則不做處理。Cksum_err（外部事件）發(fā)送NAKtimeout（內(nèi)部事件）選擇重傳Ack_timeout（內(nèi)部事件）發(fā)送確認(rèn)幀ACK59a5.4 滑動(dòng)窗口協(xié)議（13）P6協(xié)議實(shí)現(xiàn)分析59a5.4 滑動(dòng)窗口協(xié)議（14）計(jì)時(shí)器處理啟動(dòng)，發(fā)送數(shù)據(jù)幀時(shí)啟動(dòng)停止，收到正確確認(rèn)時(shí)停止超時(shí)則產(chǎn)生timeout事件Ack計(jì)時(shí)器處理啟動(dòng)，收到幀的序號(hào)等于接收窗口下界或已經(jīng)發(fā)過NAK時(shí)啟動(dòng)停止，發(fā)送幀時(shí)停止超時(shí)則產(chǎn)生ack_timeout事件60a5.4 滑動(dòng)窗口協(xié)議（14）計(jì)時(shí)器處理60a小結(jié)可靠傳輸通過確認(rèn)和重傳機(jī)制傳輸層協(xié)議，如TCP，也提供可靠傳輸服務(wù)鏈路層的可靠傳輸服務(wù)通常用于高誤碼率的連路上，如無線鏈路。61a小結(jié)可靠傳輸61a5.5協(xié)議說明與驗(yàn)證（1）5.5.1協(xié)議工程與協(xié)議的形式化描述技術(shù)協(xié)議工程：協(xié)議說明（ProtocolSpecification）協(xié)議驗(yàn)證（ProtocolVerification）協(xié)議實(shí)現(xiàn)（ProtocolImplementation）協(xié)議測試（ProtocolTesting）一致性測試（ConformanceTesting）互操作性測試（InteroperabilityTesting）性能測試（PerformanceTesting）協(xié)議說明必須既定義一個(gè)協(xié)議實(shí)體提供給它的用戶的服務(wù)，又定義該協(xié)議實(shí)體的內(nèi)部操作。62a5.5協(xié)議說明與驗(yàn)證（1）5.5.1協(xié)議工程與協(xié)議的5.5協(xié)議說明與驗(yàn)證（2）協(xié)議驗(yàn)證驗(yàn)證協(xié)議說明是否完整、正確。協(xié)議實(shí)現(xiàn)用硬件和/或軟件實(shí)現(xiàn)協(xié)議說明中規(guī)定的功能。協(xié)議測試用測試的方法來檢查協(xié)議實(shí)現(xiàn)是否滿足要求，包括：協(xié)議實(shí)現(xiàn)是否與協(xié)議說明一致（一致性測試）、協(xié)議實(shí)現(xiàn)之間的互操作能力（互操作性測試）和協(xié)議實(shí)現(xiàn)的性能（性能測試）等。在協(xié)議的說明、驗(yàn)證、實(shí)現(xiàn)和測試過程中使用形式化描述技術(shù)，不僅可以比較容易地理解協(xié)議，而且可以使協(xié)議描述更加精確，大大簡化了協(xié)議的研究工作。63a5.5協(xié)議說明與驗(yàn)證（2）協(xié)議驗(yàn)證63a5.5協(xié)議說明與驗(yàn)證（3）形式化描述的意義實(shí)際使用的協(xié)議非常復(fù)雜，給協(xié)議的理解、驗(yàn)證、實(shí)現(xiàn)和測試等工作帶來困難，需要采用形式化的、數(shù)學(xué)的描述方法來描述協(xié)議。但是目前大多數(shù)協(xié)議還是采用自然語言描述。自然語言描述協(xié)議的缺點(diǎn)冗余；多義性；結(jié)構(gòu)性不好；不便于自動(dòng)驗(yàn)證、測試、實(shí)現(xiàn)。形式化描述技術(shù)FDT（FormalDescriptionTechnique）/形式化方法FM（FormalMethod）廣泛應(yīng)用于協(xié)議工程研究中64a5.5協(xié)議說明與驗(yàn)證（3）形式化描述的意義64a5.5協(xié)議說明與驗(yàn)證（4）一種形式化方法總是以一種形式體系為基礎(chǔ)，只是在具體應(yīng)用時(shí)，大都做了便于描述的改進(jìn)和擴(kuò)充。常用的形式化方法有限狀態(tài)機(jī)FSM（FiniteStateMachine）擴(kuò)展：EFSM形式化語言模型LOTOS，Estelle，SDL都有相應(yīng)擴(kuò)展Petri網(wǎng)擴(kuò)展：時(shí)間Petri網(wǎng)，隨機(jī)Petri網(wǎng)，高級Petri網(wǎng)過程代數(shù)（ProcessAlgebra）擴(kuò)展：隨機(jī)過程代數(shù)65a5.5協(xié)議說明與驗(yàn)證（4）一種形式化方法總是以一種形式體5.5協(xié)議說明與驗(yàn)證（5）5.5.2有限狀態(tài)機(jī)模型定義一個(gè)有限狀態(tài)機(jī)是一個(gè)四元組(S,M,I,T)，其中S是狀態(tài)的集合，M是標(biāo)號(hào)的集合，I是初始狀態(tài)的集合，T是變遷的集合。通信協(xié)議建?；境霭l(fā)點(diǎn)：認(rèn)為通信協(xié)議主要是由響應(yīng)多個(gè)“事件”的相對簡單的處理過程組成；事件命令（來自用戶）信息到達(dá)（來自低層）內(nèi)部超時(shí)66a5.5協(xié)議說明與驗(yàn)證（5）5.5.2有限狀態(tài)機(jī)模型65.5協(xié)議說明與驗(yàn)證（6）優(yōu)點(diǎn)：簡單明了，比較精確；缺點(diǎn)：對許多復(fù)雜的協(xié)議，事件數(shù)和狀態(tài)數(shù)會(huì)劇增，處理困難。例協(xié)議3 每個(gè)狀態(tài)用三個(gè)字母表示：XYZ X：發(fā)送方正發(fā)送的幀序號(hào)，為0或1； Y：接收方正等待的幀序號(hào)，為0或1； Z：信道狀態(tài)，為0，1，A或-（空）。 初始狀態(tài)為（000） 半雙工信道 Fig.3-20 全雙工信道 Fig.3-2167a5.5協(xié)議說明與驗(yàn)證（6）優(yōu)點(diǎn)：簡單明了，比較精確；6768a68a69a69a70a70a5.5協(xié)議說明與驗(yàn)證（7）協(xié)議驗(yàn)證驗(yàn)證協(xié)議說明是否完整正確，以協(xié)議說明為基礎(chǔ)，涉及邏輯證明。主要用于系統(tǒng)實(shí)現(xiàn)前的設(shè)計(jì)階段，為了避免可能出現(xiàn)的設(shè)計(jì)錯(cuò)誤。原則上驗(yàn)證涉及協(xié)議所有可能的狀態(tài)?？蛇_(dá)性分析是一種常用的驗(yàn)證方法利用圖論知識(shí)可以解決狀態(tài)的可達(dá)性問題；可達(dá)性分析能夠用來解決協(xié)議的不完整性、死鎖和無關(guān)變遷等問題。71a5.5協(xié)議說明與驗(yàn)證（7）協(xié)議驗(yàn)證71a5.5協(xié)議說明與驗(yàn)證（8）5.5.3Petri網(wǎng)模型Petri網(wǎng)模型最早在1962年CarlAdamPetri的博士論文中提出來，主要特性是具有較強(qiáng)的對并行、不確定性、異步和分布的描述能力和分析能力。Petri網(wǎng)研究的系統(tǒng)模型行為特性包括狀態(tài)的可達(dá)（reachability）位置的限界（boundedness）變遷的活性（liveness）初始狀態(tài)的可逆達(dá)（reversibility）標(biāo)識(shí)（marking）之間的可達(dá)（reachability）事件之間的同步距離（synchronicdistance）公平性（fairness）72a5.5協(xié)議說明與驗(yàn)證（8）5.5.3Petri網(wǎng)模型5.5協(xié)議說明與驗(yàn)證（9）定義一個(gè)Petri網(wǎng)的結(jié)構(gòu)元素包括：位置（place）：描述系統(tǒng)狀態(tài)，用一個(gè)圓圈表示；變遷（transition）：描述修改系統(tǒng)狀態(tài)的事件，用一個(gè)長方形或線段表示；?。╝rc）：描述狀態(tài)與事件之間的關(guān)系，包括輸入弧和輸出弧，用有向弧表示?；顒?dòng)元素——標(biāo)記（token）：包含在位置中，用點(diǎn)表示；用來表示處理的信息單元、資源單元和顧客、用戶等對象；如果位置用來描述條件，它可以包含一個(gè)標(biāo)記或不包含標(biāo)記，當(dāng)包含標(biāo)記時(shí)，條件為真，否則，為假；如果位置用來定義狀態(tài)，位置中的標(biāo)記個(gè)數(shù)用于規(guī)定這個(gè)狀態(tài)；73a5.5協(xié)議說明與驗(yàn)證（9）定義73a5.5協(xié)議說明與驗(yàn)證（10）變遷實(shí)施規(guī)則（firingrule）：如果一個(gè)變遷的所有輸入位置至少包含一個(gè)標(biāo)記，則這個(gè)變遷可能實(shí)施；一個(gè)可實(shí)施變遷的實(shí)施導(dǎo)致從它所有輸入位置中都清除一個(gè)標(biāo)記，在它所有輸出位置中產(chǎn)生一個(gè)標(biāo)記；當(dāng)使用大于1的弧權(quán)（weight）時(shí)，在變遷的所有輸入位置中都要包含至少等于連接弧權(quán)的標(biāo)記個(gè)數(shù)它才可實(shí)施，并根據(jù)弧權(quán)，在每個(gè)輸出位置中產(chǎn)生相應(yīng)標(biāo)記個(gè)數(shù)；變遷的實(shí)施是一個(gè)原子操作，輸入位置清除標(biāo)記和輸出位置產(chǎn)生標(biāo)記是一個(gè)不可分割的完整操作。Fig.3-22主要分析方法可達(dá)樹關(guān)聯(lián)矩陣和狀態(tài)方程不變量分析化簡規(guī)則74a5.5協(xié)議說明與驗(yàn)證（10）變遷實(shí)施規(guī)則（firing75a75a5.5協(xié)議說明與驗(yàn)證（11）Petri網(wǎng)的擴(kuò)展條件/事件（C/E）網(wǎng)最簡單，每個(gè)位置最多一個(gè)標(biāo)記，表示條件。位置/變遷（P/T）網(wǎng)每個(gè)位置中的標(biāo)記可以有多個(gè)。高級Petri網(wǎng)（包括謂詞/變遷網(wǎng)和著色網(wǎng)）給標(biāo)記以屬性，即標(biāo)記有區(qū)別從沒有參數(shù)的網(wǎng)，發(fā)展到時(shí)間Petri網(wǎng)和隨機(jī)Petri網(wǎng)；從一般有向弧發(fā)展到可變??；從自然數(shù)標(biāo)記個(gè)數(shù)發(fā)展到概率標(biāo)記個(gè)數(shù)；從原子變遷發(fā)展到謂詞變遷和子網(wǎng)變遷。76a5.5協(xié)議說明與驗(yàn)證（11）Petri網(wǎng)的擴(kuò)展76a5.5協(xié)議說明與驗(yàn)證（12）例：協(xié)議3（半雙工信道）Fig.3-23可達(dá)圖（部分）關(guān)于形式化方法的幾點(diǎn)注意事項(xiàng)模型描述能力的增強(qiáng)會(huì)在某種程度上增加模型分析的難度；模型僅僅是手段，不是目的。Modelingisabridge.77a5.5協(xié)議說明與驗(yàn)證（12）例：協(xié)議3（半雙工信道）7778a78aM0=ACG(000)ADF(0A1)BEF(111)BDG(1A0)10311179aM0=ACG(000)ADF(5.6 常用的數(shù)據(jù)鏈路層協(xié)議（1）ISO和CCITT在數(shù)據(jù)鏈路層協(xié)議的標(biāo)準(zhǔn)制定方面做了大量工作，各大公司也形成了自己的標(biāo)準(zhǔn)。數(shù)據(jù)鏈路層協(xié)議分類面向字符的鏈路層協(xié)議ISO的IS1745，基本型傳輸控制規(guī)程及其擴(kuò)充部分（BM和XBM）IBM的二進(jìn)制同步通信規(guī)程（BSC）DEC的數(shù)字?jǐn)?shù)據(jù)通信報(bào)文協(xié)議（DDCMP）PPP面向比特的鏈路層協(xié)議IBM的SNA使用的數(shù)據(jù)鏈路協(xié)議SDLC（SynchronousDataLinkControlprotocol）；ANSI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作為X.25網(wǎng)絡(luò)接口標(biāo)準(zhǔn)的一部分，后來改為LAPB。80a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（1）ISO和CCITT在數(shù)據(jù)鏈5.6 常用的數(shù)據(jù)鏈路層協(xié)議（2）5.6.1高級數(shù)據(jù)鏈路控制規(guī)程HDLC1976年，ISO提出HDLC（High-levelDataLinkControl）HDLC的組成幀結(jié)構(gòu)規(guī)程元素規(guī)程類型 語義使用HDLC的語法可以定義多種具有不同操作特點(diǎn)的鏈路層協(xié)議。HDLC的適用范圍計(jì)算機(jī)——計(jì)算機(jī)計(jì)算機(jī)——終端終端——終端}語法81a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（2）5.6.1高級數(shù)據(jù)鏈路5.6 常用的數(shù)據(jù)鏈路層協(xié)議（3）數(shù)據(jù)站（簡稱站station），由計(jì)算機(jī)和終端組成，負(fù)責(zé)發(fā)送和接收幀。HDLC涉及三種類型的站：主站（primarystation）：主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響應(yīng)，負(fù)責(zé)整個(gè)鏈路的控制（如系統(tǒng)的初始、流控、差錯(cuò)恢復(fù)等）；次站（secondarystation）：主要功能是接收命令，發(fā)送響應(yīng)，配合主站完成鏈路的控制；組合站（combinedstation）：同時(shí)具有主、次站功能，既發(fā)送又接收命令和響應(yīng)，并負(fù)責(zé)整個(gè)鏈路的控制。HDLC適用的鏈路構(gòu)型非平衡型點(diǎn)—點(diǎn)式82a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（3）數(shù)據(jù)站（簡稱站stati5.6 常用的數(shù)據(jù)鏈路層協(xié)議（4）多點(diǎn)式適合把智能和半智能的終端連接到計(jì)算機(jī)。平衡型主站—次站式組合式適合于計(jì)算機(jī)和計(jì)算機(jī)之間的連接83a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（4）多點(diǎn)式83a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（5）HDLC的基本操作模式正規(guī)響應(yīng)模式NRM（NormalResponseMode）適用于點(diǎn)—點(diǎn)式和多點(diǎn)式兩種非平衡構(gòu)型。只有當(dāng)主站向次站發(fā)出探詢后，次站才能獲得傳輸幀的許可。異步響應(yīng)模式ARM（AsynchronousResponseMode）適用于點(diǎn)—點(diǎn)式非平衡構(gòu)型和主站—次站式平衡構(gòu)型。次站可以隨時(shí)傳輸幀，不必等待主站的探詢。異步平衡模式ABM（AsynchronousBalancedMode）適用于通信雙方都是組合站的平衡構(gòu)型，也采用異步響應(yīng)，雙方具有同等能力。84a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（5）HDLC的基本操作模式845.6 常用的數(shù)據(jù)鏈路層協(xié)議（6）幀結(jié)構(gòu)定界符01111110空閑的點(diǎn)到點(diǎn)線路上連續(xù)傳定界符地址域（Address）多終端線路，用來區(qū)分終端；點(diǎn)到點(diǎn)線路，有時(shí)用來區(qū)分命令和響應(yīng)。若幀中的地址是接收該幀的站的地址，則該幀是命令幀；若幀中的地址是發(fā)送該幀的站的地址，則該幀是響應(yīng)幀。85a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（6）幀結(jié)構(gòu)85a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（7）控制域（Control）序號(hào)使用滑動(dòng)窗口技術(shù)，3位序號(hào)，發(fā)送窗口大小為7確認(rèn)其它數(shù)據(jù)域（Data）任意信息，任意長度（上層協(xié)議SDU有上限）校驗(yàn)和（Checksum）CRC校驗(yàn)生成多項(xiàng)式：CRC-CCITT86a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（7）控制域（Control）85.6 常用的數(shù)據(jù)鏈路層協(xié)議（8）幀類型信息幀（Information）監(jiān)控幀（Supervisory）無序號(hào)幀（Unnumbered）控制域Fig.3-25序號(hào)（Seq）使用滑動(dòng)窗口技術(shù)，3位序號(hào)，發(fā)送窗口大小為7捎帶確認(rèn)（Next）捎帶第一個(gè)未收到的幀序號(hào)，而不是最后一個(gè)已收到的幀序號(hào)87a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（8）幀類型87a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（9）探詢/結(jié)束P/F位（Poll/Final）命令幀置“P”，響應(yīng)幀置“F”。有些協(xié)議，P/F位用來強(qiáng)迫對方機(jī)器立刻發(fā)控制幀；多終端系統(tǒng)中，計(jì)算機(jī)置“P”，允許終端發(fā)送數(shù)據(jù)；終端發(fā)向計(jì)算機(jī)的幀中，最后一個(gè)幀置為“F”，其它置為“P”。類型（Type）“0”表示確認(rèn)幀RR（RECEIVEREADY）；“1”表示否定性確認(rèn)幀REJ（REJECT）?！?”表示接收未準(zhǔn)備好RNR（RECEIVENOTREADY）“3”表示選擇拒絕SREJ（SELECTIVEREJECT）HDLC和ADCCP允許選擇拒絕，SDLC和LAPB不允許。88a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（9）探詢/結(jié)束P/F位（Po5.6 常用的數(shù)據(jù)鏈路層協(xié)議（10）無序號(hào)幀可以用來傳控制信息，也可在不可靠無連接服務(wù)中傳數(shù)據(jù)。命令DISC（DISConnect）SNRM（SetNormalResponseMode）SARM（SetAsynchronousResponseMode）SABM（SetAsynchronousBalancedMode）HDLC和LAPB使用。SABMESABM的擴(kuò)展SNRMESNRM的擴(kuò)展FRMR（FRaMeReject）校驗(yàn)和正確，語義錯(cuò)誤89a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（10）無序號(hào)幀89a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（11）無序號(hào)確認(rèn)UA（UnnumberedAcknowledgement）對控制幀進(jìn)行確認(rèn)，用于確認(rèn)模式建立和接受拆除命令。UI（UnnumberedInformation）HDLC的功能組合三種站，兩種構(gòu)型，三種操作模式，以及規(guī)程元素中定義的各種幀的各種組合產(chǎn)生多種鏈路層協(xié)議。HDLC定義了選擇構(gòu)成鏈路層協(xié)議的良序結(jié)構(gòu)：選擇站構(gòu)型——>基本操作模式——>基本幀種類——>12種任選功能——>得到協(xié)議90a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（11）無序號(hào)確認(rèn)UA（Unnu91a91a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（12）5.6.2X.25的鏈路層協(xié)議LAPBX.25協(xié)議分組級，PLP幀級，X.25LAP（LinkAccessProcedure），X.25LAPB（Balanced）物理級，X.21“X.25協(xié)議規(guī)程使用HDLC規(guī)程的原理和術(shù)語”X.25LAP：HDLC非平衡規(guī)程幀的基本清單+任選功能2、8、12，也可組成主站—次站式平衡規(guī)程。X.25LAPB：HDLC組合站平衡規(guī)程幀的基本清單+任選功能2、8、11、12。因此，X.25LAP、LAPB是HDLC的子集。92a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（12）5.6.2X.25的5.6 常用的數(shù)據(jù)鏈路層協(xié)議（13）X.25的幀格式與HDLC完全相同X.25鏈路級的命令和響應(yīng)93a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（13）X.25的幀格式與HDL5.6 常用的數(shù)據(jù)鏈路層協(xié)議（14）X.25LAPB的各種檢錯(cuò)和糾錯(cuò)措施a幀格式上采用CRC校驗(yàn)，只檢錯(cuò)，不糾錯(cuò)，丟棄出錯(cuò)幀；b設(shè)立超時(shí)機(jī)制，計(jì)時(shí)器超時(shí)重傳，重傳N次，則向上層協(xié)議報(bào)告。超時(shí)機(jī)制用來檢錯(cuò)，重傳用來糾錯(cuò)。c幀序號(hào)若接收方發(fā)現(xiàn)幀序號(hào)錯(cuò)，就發(fā)拒絕幀給發(fā)送方，發(fā)送方重傳，既檢錯(cuò)也糾錯(cuò)。d采用P/F位來進(jìn)行校驗(yàn)指示發(fā)送置為P的命令幀，等待置為F的響應(yīng)幀，能及時(shí)發(fā)現(xiàn)遠(yuǎn)程數(shù)據(jù)站是否收到命令幀。規(guī)程規(guī)定：a必須使用；b,c,d組合使用。94a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（14）X.25LAPB的各種5.6 常用的數(shù)據(jù)鏈路層協(xié)議（15）5.6.3Internet數(shù)據(jù)鏈路層協(xié)議點(diǎn)到點(diǎn)通信的兩種主要情形路由器到路由器（router-routerleasedlineconnection）通過modem撥號(hào)上網(wǎng)，連到路由器或接入服務(wù)器（AccessServer）（dial-uphost-routerconnection）95a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（15）5.6.3Inter5.6 常用的數(shù)據(jù)鏈路層協(xié)議（16）SLIP——SerialLineIP1984年，RickAdams提出，RFC1055，發(fā)送原始IP包，用一個(gè)標(biāo)記字節(jié)來定界，采用字符填充技術(shù)；新版本提供TCP和IP頭壓縮技術(shù)，RFC1144存在的問題不提供差錯(cuò)校驗(yàn)只支持IPIP地址不能動(dòng)態(tài)分配不提供認(rèn)證多種版本并存，互連困難96a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（16）SLIP——Seri5.6 常用的數(shù)據(jù)鏈路層協(xié)議（17）點(diǎn)到點(diǎn)協(xié)議PPP——Point-to-PointProtocolRFC1661，RFC1662，RFC1663與SLIP相比，PPP有很大的提高，提供差錯(cuò)校驗(yàn)、支持多種協(xié)議、允許動(dòng)態(tài)分配IP地址、支持認(rèn)證等。以幀為單位發(fā)送，而不是原始IP包；包括兩部分鏈路控制協(xié)議LCP（LinkControlProtocol）可使用多種物理層服務(wù)：modem，HDLC串線，SDH/SONET等網(wǎng)絡(luò)控制協(xié)議NCP（NetworkControlProtocol）可支持多種網(wǎng)絡(luò)層協(xié)議幀格式與HDLC相似，區(qū)別在于PPP是面向字符的，采用字符填充技術(shù)97a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（17）點(diǎn)到點(diǎn)協(xié)議PPP——5.6 常用的數(shù)據(jù)鏈路層協(xié)議（18）標(biāo)記域：01111110，字符填充；地址域：11111111控制域：缺省值為00000011，表示無序號(hào)幀，不提供使用序號(hào)和確認(rèn)的可靠傳輸；不可靠線路上，也可使用有序號(hào)的可靠傳輸。協(xié)議域：指示凈負(fù)荷中是何種包，缺省大小為2個(gè)字節(jié)。凈負(fù)荷域：變長，缺省為1500字節(jié)；校驗(yàn)和域：2或4個(gè)字節(jié)總結(jié)：PPP具有多協(xié)議成幀機(jī)制，可以在modem,HDLCbit-seriallines,SDH/SONET等物理層上運(yùn)行，支持差錯(cuò)檢測、選項(xiàng)協(xié)商和包頭壓縮功能，并具有利用HDLC幀進(jìn)行可靠傳輸?shù)目蛇x功能。98a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（18）標(biāo)記域：011111105.6 常用的數(shù)據(jù)鏈路層協(xié)議（19）PPP鏈路up/down過程（簡單狀態(tài)圖）99a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（19）PPP鏈路up/d5.6 常用的數(shù)據(jù)鏈路層協(xié)議（20）LCP用來在ESTABLISH狀態(tài)協(xié)商數(shù)據(jù)鏈路協(xié)議選項(xiàng)，并不關(guān)心選項(xiàng)內(nèi)容，而是提供一種協(xié)商機(jī)制，并且提供檢測鏈路質(zhì)量的方法。RFC1661定義了11種LCP幀類型：100a5.6 常用的數(shù)據(jù)鏈路層協(xié)議（20）LCP用來在ESTABL小結(jié)介紹三種主要數(shù)據(jù)鏈路層協(xié)議：HDLC、LAPB（面向比特）和PPP（面向字符）HDLC具有三種站，兩種構(gòu)型，三種操作模式X.25LAPB是HDLC的子集PPP提供差錯(cuò)校驗(yàn)、支持多種協(xié)議、允許動(dòng)態(tài)分配IP地址、支持認(rèn)證PPP包括兩部分：LCP和NCPPPP幀沒有序號(hào)域，不使用滑動(dòng)窗口技術(shù)。101a小結(jié)介紹三種主要數(shù)據(jù)鏈路層協(xié)議：HDLC、LAPB（面向比特第五章

數(shù)據(jù)鏈路控制及其協(xié)議102a第五章

數(shù)據(jù)鏈路控制及其協(xié)議1a主要內(nèi)容5.1 定義和功能5.1.1 定義5.1.2 為網(wǎng)絡(luò)層提供服務(wù)5.1.3 成幀5.1.4 差錯(cuò)控制5.1.5 流量控制5.2 錯(cuò)誤檢測和糾正5.2.1 糾錯(cuò)碼5.2.2 檢錯(cuò)碼5.3 基本的數(shù)據(jù)鏈路層協(xié)議 5.3.1 無約束單工協(xié)議 5.3.2 單工停等協(xié)議 5.3.3 有噪聲信道的單工協(xié)議103a主要內(nèi)容5.1 定義和功能2a5.4 滑動(dòng)窗口協(xié)議 5.4.1 一比特滑動(dòng)窗口協(xié)議 5.4.2 退后n幀協(xié)議 5.4.3 選擇重傳協(xié)議5.5 協(xié)議說明與驗(yàn)證 5.5.1 通信協(xié)議中的形式化描述技術(shù) 5.5.2 有限狀態(tài)機(jī)模型 5.5.3 Petri網(wǎng)模型5.6 常用的數(shù)據(jù)鏈路層協(xié)議5.6.1 高級數(shù)據(jù)鏈路控制規(guī)程HDLC5.6.2 X.25的鏈路層協(xié)議LAPB5.6.3 Internet數(shù)據(jù)鏈路層協(xié)議5.6.4 ATM數(shù)據(jù)鏈路層協(xié)議104a5.4 滑動(dòng)窗口協(xié)議3a5.1 定義和功能（1）5.1.1定義要解決的問題如何在有差錯(cuò)的線路上，進(jìn)行無差錯(cuò)傳輸。ISO關(guān)于數(shù)據(jù)鏈路層的定義數(shù)據(jù)鏈路層的目的是為了提供功能上和規(guī)程上的方法，以便建立、維護(hù)和釋放網(wǎng)絡(luò)實(shí)體間的數(shù)據(jù)鏈路。結(jié)點(diǎn)（node）：網(wǎng)絡(luò)中的主機(jī)（host）和路由器（router）稱為結(jié)點(diǎn)鏈路（link）：通信路徑上連接相鄰結(jié)點(diǎn)的通信信道稱為鏈路。數(shù)據(jù)鏈路層協(xié)議定義了一條鏈路的兩個(gè)結(jié)點(diǎn)間交換的數(shù)據(jù)單元格式，以及結(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)單元的動(dòng)作。105a5.1 定義和功能（1）5.1.1定義4a5.1 定義和功能（2）端到端（endtoend）與點(diǎn)到點(diǎn)（pointtopoint）從源結(jié)點(diǎn)（sourcenode）到目的結(jié)點(diǎn)（destinationnode）的通信稱為端到端通信，通信路徑（path）可能由多個(gè)鏈路組成。在相鄰結(jié)點(diǎn)間的一條鏈路上的通信稱為點(diǎn)到點(diǎn)通信。虛擬數(shù)據(jù)通路，實(shí)際數(shù)據(jù)通路Fig.3-1106a5.1 定義和功能（2）端到端（endtoend）與點(diǎn)到107a6a5.1 定義和功能（2）數(shù)據(jù)鏈路控制規(guī)程為使數(shù)據(jù)能迅速、正確、有效地從發(fā)送點(diǎn)到達(dá)接收點(diǎn)所采用的控制方式。數(shù)據(jù)鏈路層協(xié)議應(yīng)提供的最基本功能數(shù)據(jù)在數(shù)據(jù)鏈路上的正常傳輸（建立、維護(hù)和釋放）定界與同步，也處理透明性問題差錯(cuò)控制順序控制流量控制108a5.1 定義和功能（2）數(shù)據(jù)鏈路控制規(guī)程7a5.1 定義和功能（3）5.1.2為網(wǎng)絡(luò)層提供服務(wù)為網(wǎng)絡(luò)層提供三種合理的服務(wù)無確認(rèn)無連接服務(wù)，適用于誤碼率很低的線路，錯(cuò)誤恢復(fù)留給高層；實(shí)時(shí)業(yè)務(wù)大部分局域網(wǎng)有確認(rèn)無連接服務(wù)，適用于不可靠的信道，如無線網(wǎng)。有確認(rèn)有連接服務(wù)109a5.1 定義和功能（3）5.1.2為網(wǎng)絡(luò)層提供服務(wù)8a5.1 定義和功能（4）5.1.3成幀（Framing）將比特流分成離散的幀，并計(jì)算每個(gè)幀的校驗(yàn)和。成幀方法：字符計(jì)數(shù)法在幀頭中用一個(gè)域來表示整個(gè)幀的字符個(gè)數(shù)缺點(diǎn)：若計(jì)數(shù)出錯(cuò)，對本幀和后面的幀有影響。Fig.3-3帶字符填充的首尾字符定界法起始字符DLESTX，結(jié)束字符DLEETX字符填充 Fig.3-4缺點(diǎn)：局限于8位字符和ASCII字符傳送。110a5.1 定義和功能（4）5.1.3成幀（Framing）5.1 定義和功能（5）帶位填充的首尾標(biāo)記定界法幀的起始和結(jié)束都用一個(gè)特殊的位串“01111110”，稱為標(biāo)記(flag)“0”比特插入刪除技術(shù)Fig.3-5物理層編碼違例法只適用于物理層編碼有冗余的網(wǎng)絡(luò)802LAN：ManchesterencodingorDifferentialManchesterencoding用high-lowpair/low-highpair表示1/0，high-high/low-low不表示數(shù)據(jù)，可以用來做定界符。注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計(jì)數(shù)法和一種其它方法的組合。111a5.1 定義和功能（5）帶位填充的首尾標(biāo)記定界法10a112a11a113a12a114a13a5.1 定義和功能（6）5.1.4差錯(cuò)控制一般方法：接收方給發(fā)送方一個(gè)反饋（響應(yīng)）。出錯(cuò)情況幀（包括發(fā)送幀和響應(yīng)幀）出錯(cuò)；幀（包括發(fā)送幀和響應(yīng)幀）丟失通過計(jì)時(shí)器和序號(hào)保證每幀最終交給目的網(wǎng)絡(luò)層僅一次是數(shù)據(jù)鏈路層的一個(gè)主要功能。5.1.5流量控制基于反饋機(jī)制流量控制主要在傳輸層實(shí)現(xiàn)115a5.1 定義和功能（6）5.1.4差錯(cuò)控制14a5.2 錯(cuò)誤檢測和糾正（1）差錯(cuò)出現(xiàn)的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)（burst）處理差錯(cuò)的兩種基本策略使用糾錯(cuò)碼：發(fā)送方在每個(gè)數(shù)據(jù)塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數(shù)據(jù)是否有錯(cuò)，并能糾正錯(cuò)誤。使用檢錯(cuò)碼：發(fā)送方在每個(gè)數(shù)據(jù)塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數(shù)據(jù)是否有錯(cuò)，但不能判斷哪里有錯(cuò)。5.2.1 糾錯(cuò)碼碼字（codeword）：一個(gè)幀包括m個(gè)數(shù)據(jù)位，r個(gè)校驗(yàn)位，n=m+r，則此n比特單元稱為n位碼字。海明距離（Hammingdistance）：兩個(gè)碼字之間不同的比特位數(shù)目。116a5.2 錯(cuò)誤檢測和糾正（1）差錯(cuò)出現(xiàn)的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)（5.2 錯(cuò)誤檢測和糾正（2）例：0000000000與0000011111的海明距離為5如果兩個(gè)碼字的海明距離為d，則需要d個(gè)單比特錯(cuò)就可以把一個(gè)碼字轉(zhuǎn)換成另一個(gè)碼字；為了檢查出d個(gè)錯(cuò)（單比特錯(cuò)），需要使用海明距離為d+1的編碼；為了糾正d個(gè)錯(cuò)，需要使用海明距離為2d+1的編碼；最簡單的例子是奇偶校驗(yàn)，在數(shù)據(jù)后填加一個(gè)奇偶位（paritybit）例：使用偶校驗(yàn)（“1”的個(gè)數(shù)為偶數(shù)） 10110101 ——> 101101011 10110001 ——> 101100010奇偶校驗(yàn)可以用來檢查單個(gè)錯(cuò)誤。117a5.2 錯(cuò)誤檢測和糾正（2）例：0000000000與005.2 錯(cuò)誤檢測和糾正（3）設(shè)計(jì)糾錯(cuò)碼要求：m個(gè)信息位，r個(gè)校驗(yàn)位，糾正單比特錯(cuò)；對2m個(gè)有效信息中任何一個(gè)，有n個(gè)與其距離為1的無效碼字，因此有：(n+1)2m

2n 利用n=m+r，得到(m+r+1)2r 給定m，利用該式可以得出校正單比特誤碼的校驗(yàn)位數(shù)目的下界海明碼碼位從左邊開始編號(hào)，從“1”開始；位號(hào)為2的冪的位是校驗(yàn)位，其余是信息位；每個(gè)校驗(yàn)位使得包括自己在內(nèi)的一些位的奇偶值為偶數(shù)（或奇數(shù)）。為看清數(shù)據(jù)位k對哪些校驗(yàn)位有影響，將k寫成2的冪的和。例：11=1+2+8118a5.2 錯(cuò)誤檢測和糾正（3）設(shè)計(jì)糾錯(cuò)碼17a5.2 錯(cuò)誤檢測和糾正（4）海明碼工作過程每個(gè)碼字到來前，接收方計(jì)數(shù)器清零；接收方檢查每個(gè)校驗(yàn)位k(k=1,2,4…)的奇偶值是否正確；若第k位奇偶值不對，計(jì)數(shù)器加k；所有校驗(yàn)位檢查完后，若計(jì)數(shù)器值為0，則碼字有效；若計(jì)數(shù)器值為m，則第m位出錯(cuò)。若校驗(yàn)位1、2、8出錯(cuò)，則第11位變反。Fig.3-6使用海明碼糾正突發(fā)錯(cuò)誤可采用k個(gè)碼字（n=m+r）組成kn矩陣，按列發(fā)送，接收方恢復(fù)成kn矩陣kr個(gè)校驗(yàn)位，km個(gè)數(shù)據(jù)位，可糾正最多為k個(gè)的突發(fā)性連續(xù)比特錯(cuò)。119a5.2 錯(cuò)誤檢測和糾正（4）海明碼工作過程18a12345678

910111111122222444888120a123456785.2 錯(cuò)誤檢測和糾正（5）5.2.2檢錯(cuò)碼使用糾錯(cuò)碼傳數(shù)據(jù)，效率低，適用于不可能重傳的場合；大多數(shù)情況采用檢錯(cuò)碼加重傳。循環(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碼基本思想校驗(yàn)和（checksum）加在幀尾，使帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)除盡；收方接收時(shí)，用G(x)去除它，若有余數(shù)，則傳輸出錯(cuò)。121a5.2 錯(cuò)誤檢測和糾正（5）5.2.2檢錯(cuò)碼20a5.2 錯(cuò)誤檢測和糾正（6）校驗(yàn)和計(jì)算算法設(shè)G(x)為r階，在幀的末尾加r個(gè)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-7CRC的檢錯(cuò)能力發(fā)送：T(x)；接收：T(x)+E(x)；余數(shù)((T(x)+E(x))/G(x))=0+余數(shù)(E(x)/G(x))若余數(shù)(E(x)/G(x))=0，則差錯(cuò)不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。122a5.2 錯(cuò)誤檢測和糾正（6）校驗(yàn)和計(jì)算算法21a5.2 錯(cuò)誤檢測和糾正（7）如果只有單比特錯(cuò)，即E(x)=xi，而G(x)中至少有兩項(xiàng)，余數(shù)(E(x)/G(x))

0，所以可以查出單比特錯(cuò)；如果發(fā)生兩個(gè)孤立單比特錯(cuò)，即E(x)=xi+xj=xj(xi-j+1)，假定G(x)不能被x整除，那么能夠發(fā)現(xiàn)兩個(gè)比特錯(cuò)的充分條件是：xk+1不能被G(x)整除(ki-j)；如果有奇數(shù)個(gè)比特錯(cuò)，即E(x)包括奇數(shù)個(gè)項(xiàng)，G(x)選(x+1)的倍數(shù)就能查出奇數(shù)個(gè)比特錯(cuò)；具有r個(gè)校驗(yàn)位的多項(xiàng)式能檢查出所有長度r的突發(fā)性差錯(cuò)。長度為k的突發(fā)性連續(xù)差錯(cuò)（并不表示有k個(gè)單比特錯(cuò)）可表示為xi(xk-1+…+1)，若G(x)包括x0項(xiàng)，且k-1小于G(x)的階，則余數(shù)(E(x)/G(x))0;如果突發(fā)差錯(cuò)長度為r+1，當(dāng)且僅當(dāng)突發(fā)差錯(cuò)和G(x)一樣時(shí)，余數(shù)(E(x)/G(x))=0，概率為1/2r-1;長度大于r+1的突發(fā)差錯(cuò)或幾個(gè)較短的突發(fā)差錯(cuò)發(fā)生后，壞幀被接收的概率為1/2r。123a5.2 錯(cuò)誤檢測和糾正（7）如果只有單比特錯(cuò)，即E(x)=5.2 錯(cuò)誤檢測和糾正（8）四個(gè)多項(xiàng)式已成為國際標(biāo)準(zhǔn)CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32硬件實(shí)現(xiàn)CRC校驗(yàn)網(wǎng)卡NIC（NetworkInterfaceCard）124a5.2 錯(cuò)誤檢測和糾正（8）四個(gè)多項(xiàng)式已成為國際標(biāo)準(zhǔn)23a125a24a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（1）5.3.1無約束單工協(xié)議（AnUnrestrictedSimplexProtocol）工作在理想情況，幾個(gè)前提：單工傳輸發(fā)送方無休止工作（要發(fā)送的信息無限多）接收方無休止工作（緩沖區(qū)無限大）通信線路（信道）不損壞或丟失信息幀工作過程發(fā)送程序:取數(shù)據(jù)，構(gòu)成幀，發(fā)送幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層Fig.3-9126a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（1）5.3.1無約束單工協(xié)127a26a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（2）5.3.2單工停等協(xié)議（ASimplexStop-and-WaitProtocol）增加約束條件：接收方不能無休止接收。解決辦法：接收方每收到一個(gè)幀后，給發(fā)送方回送一個(gè)響應(yīng)。工作過程發(fā)送程序：取數(shù)據(jù)，成幀，發(fā)送幀，等待響應(yīng)幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層，回送響應(yīng)幀。Fig.3-10128a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（2）5.3.2單工停等協(xié)議129a28a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（3）5.3.3有噪聲信道的單工協(xié)議（ASimplexProtocolforaNoisyChannel）增加約束條件：信道（線路）有差錯(cuò)，信息幀可能損壞或丟失。解決辦法：出錯(cuò)重傳。帶來的問題：什么時(shí)候重傳——定時(shí)響應(yīng)幀損壞怎么辦（重復(fù)幀）——發(fā)送幀頭中放入序號(hào)為了使幀頭精簡，序號(hào)取多少位——1位發(fā)方在發(fā)下一個(gè)幀之前等待一個(gè)肯定確認(rèn)的協(xié)議叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）130a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（3）5.3.3有噪聲信道的5.3 基本的數(shù)據(jù)鏈路層協(xié)議（4）工作過程Fig.3-11注意協(xié)議3的漏洞由于確認(rèn)幀中沒有序號(hào)，超時(shí)時(shí)間不能太短，否則協(xié)議失敗。因此假設(shè)協(xié)議3的發(fā)送和接收嚴(yán)格交替進(jìn)行。Fig.3-11（與教材不同）的實(shí)現(xiàn)是正確的，確認(rèn)幀有序號(hào)發(fā)送接收001ACKACK131a5.3 基本的數(shù)據(jù)鏈路層協(xié)議（4）工作過程001ACKACK132a31a5.4 滑動(dòng)窗口協(xié)議（1）單工——>全雙工捎帶/載答（piggybacking）：暫時(shí)延遲待發(fā)確認(rèn)，以便附加在下一個(gè)待發(fā)數(shù)據(jù)幀的技術(shù)。優(yōu)點(diǎn)：充分利用信道帶寬，減少幀的數(shù)目意味著減少“幀到達(dá)”中斷；帶來的問題：復(fù)雜。本節(jié)的三個(gè)協(xié)議統(tǒng)稱滑動(dòng)窗口協(xié)議，都能在實(shí)際（非理想）環(huán)境下正常工作，區(qū)別僅在于效率、復(fù)雜性和對緩沖區(qū)的要求。133a5.4 滑動(dòng)窗口協(xié)議（1）單工——>全雙工32a5.4 滑動(dòng)窗口協(xié)議（2）滑動(dòng)窗口協(xié)議（SlidingWindowProtocol）工作原理：發(fā)送的信息幀都有一個(gè)序號(hào)，從0到某個(gè)最大值，0~2n-1，一般用n個(gè)二進(jìn)制位表示；發(fā)送端始終保持一個(gè)已發(fā)送但尚未確認(rèn)的幀的序號(hào)表，稱為發(fā)送窗口。發(fā)送窗口的上界表示要發(fā)送的下一個(gè)幀的序號(hào)，下界表示未得到確認(rèn)的幀的最小編號(hào)。發(fā)送窗口大小=上界-下界，大小可變；發(fā)送端每發(fā)送一個(gè)幀，序號(hào)取上界值，上界加1；每接收到一個(gè)正確響應(yīng)幀，下界加1；接收端有一個(gè)接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號(hào)最大的幀，下界表示希望接收的幀；接收窗口容納允許接收的信息幀，落在窗口外的幀均被丟棄。序號(hào)等于下界的幀被正確接收，并產(chǎn)生一個(gè)響應(yīng)幀，上界、下界都加1。接收窗口大小不變。Fig.3-12134a5.4 滑動(dòng)窗口協(xié)議（2）滑動(dòng)窗口協(xié)議（SlidingWi135a34a5.4 滑動(dòng)窗口協(xié)議（3）5.4.1 一比特滑動(dòng)窗口協(xié)議（AOneBitSlidingWindowProtocol）協(xié)議特點(diǎn)窗口大小：N=1，發(fā)送序號(hào)和接收序號(hào)的取值范圍：0，1；可進(jìn)行數(shù)據(jù)雙向傳輸，信息幀中可含有確認(rèn)信息（piggybacking技術(shù)）；信息幀中包括兩個(gè)序號(hào)域：發(fā)送序號(hào)和接收序號(hào)（已經(jīng)正確收到的幀的序號(hào)）工作過程Fig.3-13136a5.4 滑動(dòng)窗口協(xié)議（3）5.4.1 一比特滑動(dòng)窗口協(xié)議（A137a36a138a37a5.4 滑動(dòng)窗口協(xié)議（4）存在問題能保證無差錯(cuò)傳輸，但是基于停等方式；若雙方同時(shí)開始發(fā)送，則會(huì)有一半重復(fù)幀；Fig.3-14（書上圖有誤）效率低，傳輸時(shí)間長。139a5.4 滑動(dòng)窗口協(xié)議（4）存在問題38a140a39a5.4 滑動(dòng)窗口協(xié)議（5）5.4.2退后n幀協(xié)議（AProtocolUsingGoBackn）為提高傳輸效率而設(shè)計(jì)例：衛(wèi)星信道傳輸速率50kbps，往返傳輸延遲500ms，若傳1000bit的幀，使用協(xié)議4，則傳輸一個(gè)幀所需時(shí)間為：發(fā)送時(shí)間+信息信道延遲+確認(rèn)信道延遲（確認(rèn)幀很短，忽略發(fā)送時(shí)間）=1000bit/50kbps+250ms+250ms=520ms信道利用率=20/5204%一般情況信道帶寬b比特/秒，幀長度L比特，往返傳輸延遲R秒，則信道利用率為(L/b)/(L/b+R)=L/(L+Rb)結(jié)論傳輸延遲大，信道帶寬高，幀短時(shí)，信道利用率低。141a5.4 滑動(dòng)窗口協(xié)議（5）5.4.2退后n幀協(xié)議（AP5.4 滑動(dòng)窗口協(xié)議（6）解決辦法連續(xù)發(fā)送多幀后再等待確認(rèn)，稱為流水線技術(shù)（pipelining）。帶來的問題信道誤碼率高時(shí)，對損壞幀和非損壞幀的重傳非常多兩種基本方法退后n幀（gobackn）接收方從出錯(cuò)幀起丟棄所有后繼幀；接收窗口為1；對于出錯(cuò)率較高的信道，浪費(fèi)帶寬。Fig.3-15(a)

142a5.4 滑動(dòng)窗口協(xié)議（6）解決辦法41a5.4 滑動(dòng)窗口協(xié)議（7）選擇重傳（selectiverepeat）接收窗口大于1，先暫存出錯(cuò)幀的后繼幀；只重傳壞幀；對最高序號(hào)的幀進(jìn)行確認(rèn)；接收窗口較大時(shí)，需較大緩沖區(qū)。Fig.3-15(b)注意：Fig.3-15(b)中可能出現(xiàn)的錯(cuò)誤143a5.4 滑動(dòng)窗口協(xié)議（7）選擇重傳（selectivere144a43a5.4 滑動(dòng)窗口協(xié)議（8）退后n幀協(xié)議發(fā)送方有流量控制，為重傳設(shè)緩沖；發(fā)送窗口未滿，EnableNetworkLayer發(fā)送窗口滿，DisableNetworkLayer發(fā)送窗口大小<序號(hào)個(gè)數(shù)（MaxSeq+1）；考慮MaxSeq=7的情況1發(fā)送方發(fā)送幀0~7；2序號(hào)為7的幀的確認(rèn)被捎帶回發(fā)送方；3發(fā)送方發(fā)送另外8個(gè)幀，序號(hào)為0~7；4另一個(gè)對幀7的捎帶確認(rèn)返回。問題：第二次發(fā)送的8個(gè)幀成功了還是丟失了？退后n幀重發(fā)；由于有多個(gè)未確認(rèn)幀，設(shè)多個(gè)計(jì)時(shí)器。145a5.4 滑動(dòng)窗口協(xié)議（8）退后n幀協(xié)議44a5.4 滑動(dòng)窗口協(xié)議（9）工作過程 Fig.3-16計(jì)時(shí)器實(shí)現(xiàn) Fig.3-17146a5.4 滑動(dòng)窗口協(xié)議（9）工作過程 45a147a46a148a47a149a48a150a49a151a50a5.4 滑動(dòng)窗口協(xié)議（10）P5協(xié)議實(shí)現(xiàn)分析事件驅(qū)動(dòng)Network_layer_ready（內(nèi)部事件）發(fā)送幀（幀序號(hào)，確認(rèn)序號(hào)，數(shù)據(jù)）Frame_arrival（外部事件）檢查幀序號(hào)，落在接收窗口內(nèi)則接收，否則丟棄；檢查確認(rèn)序號(hào)，落在發(fā)送窗口內(nèi)則移動(dòng)發(fā)送窗口，否則不做處理。Cksum_err（外部事件）丟棄timeout（內(nèi)部事件）退后n幀重傳計(jì)時(shí)器處理啟動(dòng)，發(fā)送幀時(shí)啟動(dòng)停止，收到正確確認(rèn)時(shí)停止超時(shí)則產(chǎn)生timeout事件152a5.4 滑動(dòng)窗口協(xié)議（10）P5協(xié)議實(shí)現(xiàn)分析51a5.4 滑動(dòng)窗口協(xié)議（11）5.4.3選擇重傳協(xié)議（AProtocolUsingSelectiveRepeat）目的在不可靠信道上有效傳輸時(shí)，不會(huì)因重傳而浪費(fèi)信道資源，采用選擇重傳技術(shù)。基本原理發(fā)送窗口大?。篗axSeq，接收窗口大?。?MaxSeq+1)/2保證接收窗口前移后與原窗口沒有重疊；設(shè)MaxSeq=7,若接收窗口=7，發(fā)方發(fā)幀0~6，收方全部收到，接收窗口前移（7~5），確認(rèn)幀丟失，發(fā)方重傳幀0，收方作為新幀接收，并對幀6確認(rèn)，發(fā)方發(fā)新幀7~5，收方已收過幀0，丟棄新幀0，協(xié)議出錯(cuò)。Fig.3-19153a5.4 滑動(dòng)窗口協(xié)議（11）5.4.3選擇重傳協(xié)議（A5.4 滑動(dòng)窗口協(xié)議（12）發(fā)送窗口下界：AckExpected，上界：NextFrameToSend接收窗口下界：FrameExpected，上界：TooFar緩沖區(qū)設(shè)置發(fā)送方和接收方的緩沖區(qū)大小應(yīng)等于各自窗口大??；增加確認(rèn)計(jì)時(shí)器，解決兩個(gè)方向負(fù)載不平衡帶來的阻塞問題；可隨時(shí)發(fā)送否定性確認(rèn)幀NAK。工作過程Fig.3-18154a5.4 滑動(dòng)窗口協(xié)議（12）發(fā)送窗口下界：AckExpect155a54a156a55a157a56a158a57a159a58a5.4 滑動(dòng)窗口協(xié)議（13）P6協(xié)議實(shí)現(xiàn)分析事件驅(qū)動(dòng)Network_layer_ready（內(nèi)部事件）發(fā)送幀（幀類型，幀序號(hào)，確認(rèn)序號(hào)，數(shù)據(jù)）Frame_arrival（外部事件）若是數(shù)據(jù)幀，則檢查幀序號(hào)，落在接收窗口內(nèi)則接收，否則丟棄；不等于接收窗口下界還要發(fā)NAK若是NAK，則選擇重傳；檢查確認(rèn)序號(hào)，落在發(fā)送窗口內(nèi)則移動(dòng)發(fā)送窗口，否則不做處理。Cksum_err（外部事件）發(fā)送NAKtimeout（內(nèi)部事件）選擇重傳Ack_timeout（內(nèi)部事件）發(fā)送確認(rèn)幀ACK160a5.4 滑動(dòng)窗口協(xié)議（13）P6協(xié)議實(shí)現(xiàn)分析59a5.4 滑動(dòng)窗口協(xié)議（14）計(jì)時(shí)器處理啟動(dòng)，發(fā)送數(shù)據(jù)幀時(shí)啟動(dòng)停止，收到正確確認(rèn)時(shí)停止超時(shí)則產(chǎn)生timeout事件Ack計(jì)時(shí)器處理啟動(dòng)，收到幀的序號(hào)等于接收窗口下界或已經(jīng)發(fā)過NAK時(shí)啟動(dòng)停止，發(fā)送幀時(shí)停止超時(shí)則產(chǎn)生ack_timeout事件161a5.4 滑動(dòng)窗口協(xié)議（14）計(jì)時(shí)器處理60a