清華大學計算機網(wǎng)絡ch學習教案

1、會計學1清華大學清華大學(qn hu d xu)計算機網(wǎng)絡計算機網(wǎng)絡ch第一頁，共97頁。n5.3 基本的數(shù)據(jù)鏈路層協(xié)議n無約束單工協(xié)議n單工停等協(xié)議n有噪聲信道的單工協(xié)議第1頁/共97頁第二頁，共97頁。n高級數(shù)據(jù)鏈路控制規(guī)程 HDLCn的鏈路層協(xié)議LAPBn數(shù)據(jù)鏈路層協(xié)議n數(shù)據(jù)鏈路層協(xié)議第2頁/共97頁第三頁，共97頁。n（點到點 point to point）所經(jīng)過的傳輸途徑。n虛擬數(shù)據(jù)通路，實際數(shù)據(jù)通路。nFig. 3-1第3頁/共97頁第四頁，共97頁。第4頁/共97頁第五頁，共97頁。題n差錯控制n順序控制n流量控制第5頁/共97頁第六頁，共97頁。n有確認有連接服務第6頁/共97

2、頁第七頁，共97頁。n帶字符填充的首尾字符定界法n起始字符 DLE STX，結(jié)束字符DLE ETXn字符填充nFig. 3-4n缺點：局限于8位字符和ASCII字符傳送。第7頁/共97頁第八頁，共97頁。pair/low-high pair表示1/0，high-high/low-low不表示數(shù)據(jù)，可以用來做定界符。n注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計數(shù)法和一種其它方法的組合。第8頁/共97頁第九頁，共97頁。第9頁/共97頁第十頁，共97頁。第10頁/共97頁第十一頁，共97頁。第11頁/共97頁第十二頁，共97頁。n基于反饋機制n流量控制主要在傳輸層實現(xiàn)。第12頁/共97頁第十三頁，共9

3、7頁。n糾錯碼n碼字（codeword）：一個幀包括m個數(shù)據(jù)位，r個校驗位，n = m + r，則此n比特單元稱為n位碼字。n海明距離（Hamming distance）：兩個碼字之間不同的比特位數(shù)目。第13頁/共97頁第十四頁，共97頁。第14頁/共97頁第十五頁，共97頁。nm得出校正單比特誤碼的校驗位數(shù)目的下界。n海明碼n碼位從左邊開始編號；n位號為2的冪的位是校驗位，其余是信息(xnx)位；n每個校驗位使得包括自己在內(nèi)的一些位的奇偶值為偶數(shù)（或奇數(shù)）。第15頁/共97頁第十六頁，共97頁。器值為0，則碼字有效；若計數(shù)器值為m，則第m位出錯(ch cu)。n若校驗位1、2、8出錯(ch

4、cu)，則第11位變反。nFig. 3-6n使用海明碼糾正突發(fā)錯誤n可采用k個碼字（n = m + r）組成 k n 矩陣，按列發(fā)送，接收方恢復成 k n 矩陣nkr個校驗位，km個數(shù)據(jù)位，可糾正最多為k個的突發(fā)性連續(xù)比特錯。第16頁/共97頁第十七頁，共97頁。第17頁/共97頁第十八頁，共97頁。第18頁/共97頁第十九頁，共97頁。n生成多項式必須比傳輸信息對應的多項式短。nCRC碼基本思想：校驗和（checksum）加在幀尾，使帶校驗和的幀的多項式能被G(x)除盡；收方接收時，用G(x)去除它，若有余數(shù)，則傳輸出錯。第19頁/共97頁第二十頁，共97頁。n發(fā)送：T(x)接收：T(x)

5、+ E(x)n余數(shù)(T(x) + E(x) / G(x) = 0 + 余數(shù)(E(x) / G(x)n若 余數(shù)(E(x) / G(x) = 0，則差錯不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。第20頁/共97頁第二十一頁，共97頁。若G(x)包括x0項，且 k - 1小于G(x)的階，則 E(x) / G(x) 0;n如果突發(fā)差錯長度為 r + 1，當且僅當突發(fā)差錯和G(x)一樣時， E(x) / G(x) = 0，概率(gil)為1/2r-1;n長度大于 r + 1的突發(fā)差錯或幾個較短的突發(fā)差錯發(fā)生后，壞幀被接收的概率(gil)為 1/2r。第21頁/共97頁第二十二頁，共97頁。第22頁/共97頁第二十三頁

6、，共97頁。第23頁/共97頁第二十四頁，共97頁。失信息幀n工作過程n發(fā)送程序:取數(shù)據(jù)，構(gòu)成(guchng)幀，發(fā)送幀；n接收程序：等待，接收幀，送數(shù)據(jù)給高層nFig. 3-9第24頁/共97頁第二十五頁，共97頁。第25頁/共97頁第二十六頁，共97頁。n發(fā)送程序：取數(shù)據(jù)，成幀，發(fā)送幀，等待響應幀；n接收程序：等待，接收幀，送數(shù)據(jù)給高層，回送響應幀。nFig. 3-10第26頁/共97頁第二十七頁，共97頁。第27頁/共97頁第二十八頁，共97頁。n發(fā)方在發(fā)下一個幀之前等待一個肯定(kndng)確認的協(xié)議叫做PAR（Positive Acknowledgement with Retrans

7、mission）或ARQ（Automatic Repeat reQuest）第28頁/共97頁第二十九頁，共97頁。發(fā)送接收001ACKACK第29頁/共97頁第三十頁，共97頁。第30頁/共97頁第三十一頁，共97頁。n本節(jié)的三個協(xié)議統(tǒng)稱滑動窗口協(xié)議，都能在實際（非理想）環(huán)境下正常工作，區(qū)別僅在于效率、復雜性和對緩沖區(qū)的要求。第31頁/共97頁第三十二頁，共97頁。小編號。發(fā)送窗口 = 上界 - 下界，大小可變；n發(fā)送端每發(fā)送一個幀，序號取上界值，上界加1；每接收到一個正確響應幀，下界加1；n接收端有一個接收窗口，大小固定，但不一定與發(fā)送窗口相同。接收窗口的上界表示允許接收的序號最大的幀，下

8、界表示希望接收的幀；n接收窗口表示允許接收的信息幀，落在窗口外的幀均被丟棄。序號等于下界的幀被正確接收，并產(chǎn)生一個響應幀，上界、下界都加1。接收窗口大小不變。nFig. 3-12第32頁/共97頁第三十三頁，共97頁。第33頁/共97頁第三十四頁，共97頁。送序號和接收序號（已經(jīng)正確收到的幀的序號）n工作過程nFig. 3-13第34頁/共97頁第三十五頁，共97頁。第35頁/共97頁第三十六頁，共97頁。第36頁/共97頁第三十七頁，共97頁。第37頁/共97頁第三十八頁，共97頁。第38頁/共97頁第三十九頁，共97頁。n信道利用率 = 20 / 520 4%n一般情況n信道帶寬b比特/秒

9、，幀長度l比特，往返傳輸延遲R秒，則信道利用率為 (l/b) / (l/b + R) = l / (l + Rb)n結(jié)論n傳輸延遲大，信道帶寬高，幀短時，信道利用率低。第39頁/共97頁第四十頁，共97頁。n接收窗口為1；n對于出錯率較高的信道，浪費帶寬。nFig. 3-15(a)n第40頁/共97頁第四十一頁，共97頁。第41頁/共97頁第四十二頁，共97頁。第42頁/共97頁第四十三頁，共97頁。n 3 發(fā)送方發(fā)送另外 8 個幀，序號為 0 7；n 4 另一個對幀 7 的捎帶確認返回。n問題：第二次發(fā)送的 8 個幀成功了還是(hi shi)丟失了？n退后n幀重發(fā)；n由于有多個未確認幀，設(shè)多

10、個計時器。第43頁/共97頁第四十四頁，共97頁。第44頁/共97頁第四十五頁，共97頁。第45頁/共97頁第四十六頁，共97頁。第46頁/共97頁第四十七頁，共97頁。第47頁/共97頁第四十八頁，共97頁。第48頁/共97頁第四十九頁，共97頁。第49頁/共97頁第五十頁，共97頁。n設(shè) MaxSeq = 7, 若接收(jishu)窗口 = 7n發(fā)方發(fā)幀 0 6，收方全部收到，接收(jishu)窗口前移（7 5），確認幀丟失，發(fā)方重傳幀0，收方作為新幀接收(jishu)，并對幀6確認，發(fā)方發(fā)新幀 7 5，收方已收過幀 0，丟棄新幀 0，協(xié)議出錯。nFig. 3-19n發(fā)送窗口下界：AckE

11、xpected，上界：NextFrameToSendn接收(jishu)窗口下界：FrameExpected，上界：TooFar第50頁/共97頁第五十一頁，共97頁。第51頁/共97頁第五十二頁，共97頁。第52頁/共97頁第五十三頁，共97頁。第53頁/共97頁第五十四頁，共97頁。第54頁/共97頁第五十五頁，共97頁。第55頁/共97頁第五十六頁，共97頁。第56頁/共97頁第五十七頁，共97頁。n一致性測試（Conformance Testing）n互操作性測試（Interoperability Testing）n性能測試（Performance Testing）n協(xié)議說明n必須既定

12、義一個協(xié)議實體提供給它的用戶的服務，又定義該協(xié)議實體的內(nèi)部操作。第57頁/共97頁第五十八頁，共97頁。能（性能測試）等。n在協(xié)議的說明、驗證(ynzhng)、實現(xiàn)和測試過程中使用形式化描述技術(shù)，不僅可以比較容易地理解協(xié)議，而且可以使協(xié)議描述更加精確，大大簡化了協(xié)議的研究工作。第58頁/共97頁第五十九頁，共97頁。n不便于自動驗證(ynzhng)、測試、實現(xiàn)。n形式化描述技術(shù)FDT（Formal Description Technique）/形式化方法FM（Formal Method）廣泛應用于協(xié)議工程研究中第59頁/共97頁第六十頁，共97頁。nPetri網(wǎng)n擴展：時間Petri網(wǎng)，隨機P

13、etri網(wǎng)，高級Petri網(wǎng)n過程代數(shù)（Process Algebra）n擴展：隨機過程代數(shù)第60頁/共97頁第六十一頁，共97頁。n多個(du )“事件”的相對簡單的處理過程組成；n事件n命令（來自用戶）n信息到達（來自低層）n內(nèi)部超時第61頁/共97頁第六十二頁，共97頁。號，為0或1；nZ：信道狀態(tài)，為0，1，A或 -（空）。n初始狀態(tài)為（000）n半雙工信道Fig. 3-20n全雙工信道Fig. 3-21第62頁/共97頁第六十三頁，共97頁。第63頁/共97頁第六十四頁，共97頁。第64頁/共97頁第六十五頁，共97頁。第65頁/共97頁第六十六頁，共97頁。(wnzhng)性、死鎖

14、和無關(guān)變遷等問題。第66頁/共97頁第六十七頁，共97頁。n標識（marking）之間的可達（reachability）n事件之間的同步距離（synchronic distance）n公平性（fairness）第67頁/共97頁第六十八頁，共97頁。n用來表示處理的信息單元、資源單元和顧客、用戶等對象；n如果位置用來描述條件，它可以包含一個標記或不包含標記，當包含標記時，條件為真，否則，為假；n如果位置用來定義(dngy)狀態(tài)，位置中的標記個數(shù)用于規(guī)定這個狀態(tài)；第68頁/共97頁第六十九頁，共97頁。記個數(shù)它才可實施，并根據(jù)弧權(quán)，在每個輸出位置中產(chǎn)生相應標記個數(shù)；n變遷的實施是一個原子操作，輸

15、入(shr)位置清除標記和輸出位置產(chǎn)生標記是一個不可分割的完整操作。nFig. 3-22n主要分析方法n可達樹n關(guān)聯(lián)矩陣和狀態(tài)方程n不變量n分析化簡規(guī)則第69頁/共97頁第七十頁，共97頁。第70頁/共97頁第七十一頁，共97頁。n從一般有向弧發(fā)展到可變??；n從自然數(shù)標記個數(shù)發(fā)展到概率標記個數(shù)；n從原子變遷發(fā)展到謂詞變遷和子網(wǎng)變遷。第71頁/共97頁第七十二頁，共97頁。第72頁/共97頁第七十三頁，共97頁。第73頁/共97頁第七十四頁，共97頁。M0 = ACG (000) ADF (0A1) BEF (111) BDG (1A0)103111第74頁/共97頁第七十五頁，共97頁。n面向

16、比特的鏈路層協(xié)議nIBM的SNA使用的數(shù)據(jù)鏈路協(xié)議SDLC（Synchronous Data Link Control protocol）；nANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure）；nISO修改SDLC，提出HDLC（High-level Data Link Control）；nCCITT修改HDLC，提出LAP（Link Access Procedure）作為X.25網(wǎng)絡接口標準的一部分，后來改為LAPB。第75頁/共97頁第七十六頁，共97頁。第76頁/共97頁第七十七頁，共97頁。nHDLC的適用

17、范圍n計算機 計算機n計算機 終端n終端 終端語法(yf)第77頁/共97頁第七十八頁，共97頁。ncombined station次站功能，既發(fā)送又接收命令和響應，并負責整個鏈路的控制。nHDLC適用的鏈路構(gòu)型n非平衡型n點 點式主站次站第78頁/共97頁第七十九頁，共97頁。n適合于計算機和計算機之間的連接(linji)主站次站次站次站.主站主站次站次站邏輯(lu j)通道組合站組合站第79頁/共97頁第八十頁，共97頁。不必等待主站的探詢。n異步平衡模式 ABM（Asynchronous Balanced Mode）n適用于通信(tng xn)雙方都是組合站的平衡構(gòu)型，也采用異步響應，雙

18、方具有同等能力。n幀結(jié)構(gòu)nFig. 3-24n地址域（Address）n多終端線路，用來區(qū)分終端；第80頁/共97頁第八十一頁，共97頁。nCRC校驗n生成多項式：CRC-CCITTn定界符n01111110n空閑(kngxin)的點到點線路上連續(xù)傳定界符第81頁/共97頁第八十二頁，共97頁。第82頁/共97頁第八十三頁，共97頁。nNextn捎帶第一個未收到的幀序號，而不是最后一個已收到的幀序號n探詢/結(jié)束 P/F位（Poll/Final）n命令幀置P位，響應幀置F位。有些(yuxi)協(xié)議，P/F位用來強迫對方機器立刻發(fā)控制幀；n多終端，終端發(fā)向計算機的幀中，最后一個幀P/F位置為“F”，

19、其它置為“P”。第83頁/共97頁第八十四頁，共97頁。無連接服務中傳數(shù)據(jù)。n命令nDISC（DISConnect）n拆除連接請求nSNRM（Set Normal Response Mode）nSARM（Set Asynchronous Response Mode）第84頁/共97頁第八十五頁，共97頁。nHDLC的功能組合n三種站，兩種構(gòu)型，三種操作模式，以及規(guī)程元素中定義的各種幀的各種組合產(chǎn)生多種鏈路層協(xié)議。nHDLC定義了選擇構(gòu)成鏈路層協(xié)議的良序結(jié)構(gòu)：n選擇站構(gòu)型 基本操作模式 基本幀種類 12種任選功能 得到協(xié)議第85頁/共97頁第八十六頁，共97頁。第86頁/共97頁第八十七頁，共97頁。、 、主站 次站