清華大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)ch學(xué)習(xí)教案

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

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

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

4、cu)，則第11位變反。nFig. 3-6n使用海明碼糾正突發(fā)錯(cuò)誤n可采用k個(gè)碼字（n = m + r）組成 k n 矩陣，按列發(fā)送，接收方恢復(fù)成 k n 矩陣nkr個(gè)校驗(yàn)位，km個(gè)數(shù)據(jù)位，可糾正最多為k個(gè)的突發(fā)性連續(xù)比特錯(cuò)。第16頁(yè)/共97頁(yè)第十七頁(yè)，共97頁(yè)。第17頁(yè)/共97頁(yè)第十八頁(yè)，共97頁(yè)。第18頁(yè)/共97頁(yè)第十九頁(yè)，共97頁(yè)。n生成多項(xiàng)式必須比傳輸信息對(duì)應(yīng)的多項(xiàng)式短。nCRC碼基本思想：校驗(yàn)和（checksum）加在幀尾，使帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)除盡；收方接收時(shí)，用G(x)去除它，若有余數(shù)，則傳輸出錯(cuò)。第19頁(yè)/共97頁(yè)第二十頁(yè)，共97頁(yè)。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，則差錯(cuò)不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。第20頁(yè)/共97頁(yè)第二十一頁(yè)，共97頁(yè)。若G(x)包括x0項(xiàng)，且 k - 1小于G(x)的階，則 E(x) / G(x) 0;n如果突發(fā)差錯(cuò)長(zhǎng)度為 r + 1，當(dāng)且僅當(dāng)突發(fā)差錯(cuò)和G(x)一樣時(shí)， E(x) / G(x) = 0，概率(gil)為1/2r-1;n長(zhǎng)度大于 r + 1的突發(fā)差錯(cuò)或幾個(gè)較短的突發(fā)差錯(cuò)發(fā)生后，壞幀被接收的概率(gil)為 1/2r。第21頁(yè)/共97頁(yè)第二十二頁(yè)，共97頁(yè)。第22頁(yè)/共97頁(yè)第二十三頁(yè)

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

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

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

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

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

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

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

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

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

15、入(shr)位置清除標(biāo)記和輸出位置產(chǎn)生標(biāo)記是一個(gè)不可分割的完整操作。nFig. 3-22n主要分析方法n可達(dá)樹(shù)n關(guān)聯(lián)矩陣和狀態(tài)方程n不變量n分析化簡(jiǎn)規(guī)則第69頁(yè)/共97頁(yè)第七十頁(yè)，共97頁(yè)。第70頁(yè)/共97頁(yè)第七十一頁(yè)，共97頁(yè)。n從一般有向弧發(fā)展到可變??；n從自然數(shù)標(biāo)記個(gè)數(shù)發(fā)展到概率標(biāo)記個(gè)數(shù)；n從原子變遷發(fā)展到謂詞變遷和子網(wǎng)變遷。第71頁(yè)/共97頁(yè)第七十二頁(yè)，共97頁(yè)。第72頁(yè)/共97頁(yè)第七十三頁(yè)，共97頁(yè)。第73頁(yè)/共97頁(yè)第七十四頁(yè)，共97頁(yè)。M0 = ACG (000) ADF (0A1) BEF (111) BDG (1A0)103111第74頁(yè)/共97頁(yè)第七十五頁(yè)，共97頁(yè)。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)絡(luò)接口標(biāo)準(zhǔn)的一部分，后來(lái)改為L(zhǎng)APB。第75頁(yè)/共97頁(yè)第七十六頁(yè)，共97頁(yè)。第76頁(yè)/共97頁(yè)第七十七頁(yè)，共97頁(yè)。nHDLC的適用

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

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

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