第三講數(shù)據(jù)鏈路層

1第三講數(shù)據(jù)鏈路層2本講要求1理解數(shù)據(jù)鏈路層解決的基本問題2掌握數(shù)據(jù)幀的基本原理和方法3掌握出錯(cuò)處理的幾種方式4掌握數(shù)據(jù)鏈路層的基本協(xié)議5掌握數(shù)據(jù)鏈路層的滑動(dòng)窗口協(xié)議6了解典型的數(shù)據(jù)鏈路協(xié)議3基本問題

如何利用物理層的0-1比特流傳輸能力在相鄰機(jī)器間進(jìn)行數(shù)據(jù)傳輸？問題分析◆信道問題廣播信道點(diǎn)對(duì)點(diǎn)信道每對(duì)連接對(duì)應(yīng)一對(duì)機(jī)器4問題分析（續(xù)1）◆地址問題—通信主機(jī)標(biāo)識(shí)問題（*）◆面向連接還是非連接？□面向連接——是基于電話系統(tǒng)模型。也就是說，在數(shù)據(jù)傳輸前，有一個(gè)連接建立的過程，通信結(jié)束后，有一個(gè)連接斷開的過程。（服務(wù)質(zhì)量高）□面向非連接——是基于郵政系統(tǒng)模型。也就是說，任何時(shí)候數(shù)據(jù)都可以直接發(fā)送。（服務(wù)質(zhì)量低）5問題分析（續(xù)2）◆數(shù)據(jù)封裝問題—幀格式□開始、結(jié)束標(biāo)志□通信地址：面向連接時(shí)，建立連接過程需要地址；面向非連接時(shí)，數(shù)據(jù)傳輸時(shí)需要地址?！鯏?shù)據(jù)及編碼□遞交對(duì)象——數(shù)據(jù)鏈路是數(shù)據(jù)傳輸服務(wù)層，到達(dá)目的機(jī)器后，數(shù)據(jù)必須遞交給其他功能函數(shù)來處理?！袅髁靠刂茊栴}—發(fā)送者、接收者能力不對(duì)等問題◆出錯(cuò)處理—什么是錯(cuò)？糾錯(cuò)？檢錯(cuò)？不管？結(jié)論：數(shù)據(jù)傳輸需要協(xié)調(diào)雙方的行為——協(xié)議6數(shù)據(jù)鏈路層的地址問題◆隨機(jī)分配—管理員分配配置◆固化設(shè)置—將地址固化到物理器械中如令牌環(huán)網(wǎng)等如以太網(wǎng)卡

一般來說，通信主體都應(yīng)該擁有一個(gè)標(biāo)識(shí)

——稱為地址。小探索：查看以太網(wǎng)卡的物理地址，并修改它。7數(shù)據(jù)封裝問題—幀格式（1）◆問題分析：什么是一個(gè)好的幀格式？（1）容易生成（2）重新實(shí)現(xiàn)幀同步的難度（3）普遍的適應(yīng)性■將要傳輸?shù)臄?shù)據(jù)分成很多小段數(shù)據(jù)發(fā)送出去。8數(shù)據(jù)封裝問題—幀格式（2）◆字符計(jì)數(shù)法□原理：在頭部中的一個(gè)域指定該幀中的字符數(shù)。5個(gè)字符5個(gè)字符8個(gè)字符8個(gè)字符512345678901234568790123第一幀8第二幀第三幀第四幀8字符計(jì)數(shù)□問題：出錯(cuò)后的幀無法同步512347678901234568790123第一幀8第二幀8字符計(jì)數(shù)？9數(shù)據(jù)封裝問題—幀格式（3）◆字節(jié)填充法□分析：字符計(jì)數(shù)法失去幀同步后，恢復(fù)很難。原因是很難區(qū)分計(jì)數(shù)的字符和數(shù)據(jù)字符?！踉恚菏褂锰厥獾淖址鳛閹拈_始和結(jié)束標(biāo)志payloadFLAGFLAGheadertrailer□新的問題：如果負(fù)載重出現(xiàn)了FLAG了怎么辦？AFLAGBFLAGFLAG10數(shù)據(jù)封裝問題—幀格式（4）◆字節(jié)填充法□轉(zhuǎn)義字節(jié)技術(shù)stuffing“ESC”ESCSamewithflagFLAGAFLAGBFLAGFLAGAFLAGBFLAG□新問題：數(shù)據(jù)中包含了ESC怎么辦？11數(shù)據(jù)封裝問題—幀格式（5）◆字節(jié)填充法□轉(zhuǎn)義字節(jié)技術(shù)data“ESC”stuffing“ESC”ESCFLAGAESCBFLAGFLAGAESCBFLAG□其他問題？遇到第一個(gè)ESC，表示后面的是正常數(shù)據(jù)，不是特殊字符12數(shù)據(jù)封裝問題—幀格式（6）◆字節(jié)填充法□字節(jié)填充法存在什么問題？

必須緊緊依賴于8位字符模式

不是所有的字符都是8位字符模式，如Unicode使用16位字符。結(jié)論：非8位字符模式，需要轉(zhuǎn)換為8位字符模式才能順利傳輸□字符填充法分析13數(shù)據(jù)封裝問題—幀格式（7）◆位填充法□

原理：幀開始和結(jié)束都有一個(gè)特殊的位模式01111110□問題：當(dāng)傳輸數(shù)據(jù)中有01111110如何處理？□

解決辦法：碰到連續(xù)5連續(xù)的位“1”的時(shí)候，自動(dòng)填充一位00111111001011111111011101111110123456123456781234560111111001011111011101110111111012345678□位填充法分析14數(shù)據(jù)封裝問題—幀格式（8）◆物理層編碼違例法□原理：使用非數(shù)據(jù)編碼信號(hào)來表示幀的邊界。如以太網(wǎng)（MAC子層中介紹）——曼徹斯特編碼方式傳輸數(shù)據(jù)“1”的編碼“0”的編碼

其他編碼方式，可以用作幀的邊界□物理層編碼違例法分析15流控制問題

◆問題描述發(fā)送方的速度超過了接受方能夠接受這些幀的速度◆基本處理方法□基于反饋的流控制□基于速率的流控制定義規(guī)則，規(guī)范發(fā)送者什么時(shí)候可以發(fā)送幀。（具體協(xié)議中介紹）限制發(fā)送方的速率。（后面章節(jié)中詳細(xì)介紹）16出錯(cuò)處理（1）

◆定義—什么是錯(cuò)誤？□嚴(yán)格意義：凡是接收到的數(shù)據(jù)和發(fā)送的數(shù)據(jù)不一致□不一致：錯(cuò)誤數(shù)據(jù)*、丟失數(shù)據(jù)、數(shù)據(jù)亂序◆基本措施□糾錯(cuò)（錯(cuò)誤糾正）：就是將不一致的數(shù)據(jù)恢復(fù)到一致□檢錯(cuò)（錯(cuò)誤發(fā)現(xiàn)）：檢查數(shù)據(jù)中是否存在不一致□不作為先看看錯(cuò)誤數(shù)據(jù)的基本措施，丟失和亂序問題在協(xié)議中介紹17出錯(cuò)處理（2）

◆糾錯(cuò)—糾錯(cuò)碼□原理：在發(fā)送的數(shù)據(jù)中包含冗余信息，以便接收者可以推斷出數(shù)據(jù)中肯定有哪些內(nèi)容。包含m個(gè)數(shù)據(jù)位和r個(gè)校驗(yàn)位的n-位單元，通常稱為n位碼字（n=m+r）。mbitsDatabitsrbitsCheckbitsnbitscodeword（n=m+r）—有這么神奇的事情嗎？18出錯(cuò)處理（3）

◆糾錯(cuò)碼□海明距離——兩個(gè)碼字不相同的位的個(gè)數(shù)10001001（碼字1）10110001（碼字2）XOR00111000海明距離d=3

含義理解：如果碼字1出錯(cuò)后，變?yōu)榇a字2，則至少要3位數(shù)據(jù)發(fā)生錯(cuò)誤

海明距離用來度量最少出錯(cuò)的位數(shù)19□海明距離用來度量最少出錯(cuò)的位數(shù)出錯(cuò)處理（4）

◆糾錯(cuò)碼□糾正d位錯(cuò)誤的基本原理即假設(shè)傳輸過程中，最多d位出錯(cuò)。（1）對(duì)于傳輸數(shù)據(jù)m位，合法的報(bào)文有2m種情況；（2）對(duì)于傳輸?shù)膎位碼字，可能的碼字有2n種情況（n=m+r）；（3）從2n中選擇2m個(gè)n位碼字來表示合法的傳輸數(shù)據(jù)，并且保證每?jī)蓚€(gè)n位碼間的距離至少為2d+1;（4）接收到數(shù)據(jù)A時(shí)，與所有的n位合法碼字求解海明距離，海明距離小于d的，就是傳輸?shù)臄?shù)據(jù)。20出錯(cuò)處理（5）

◆糾錯(cuò)碼0000000000（碼字1）0000011111（碼字2）1111100000（碼字3）1111111111（碼字4）□例子編碼距離為5，因此2d+1=5，可得d=2，該方案可以糾錯(cuò)2位以下的錯(cuò)誤。接收到數(shù)據(jù)0000000111，與上面的碼字計(jì)算海明距離，和碼字2距離最小，為2，因此該數(shù)據(jù)有兩位出錯(cuò)了，原始數(shù)據(jù)應(yīng)該是000001111121出錯(cuò)處理（6）

◆檢錯(cuò)—檢錯(cuò)碼□原理：在發(fā)送的數(shù)據(jù)中包含冗余信息，以便接收者可以推斷出數(shù)據(jù)中是否發(fā)生了錯(cuò)誤?！跗媾紮z錯(cuò)方案——檢測(cè)單個(gè)錯(cuò)誤□檢錯(cuò)原理：在數(shù)據(jù)后面加上一個(gè)奇偶位，如果碼字中的“1”的位為偶數(shù)，則填0，如果是奇數(shù)，則填1。22出錯(cuò)處理（7）

senderreceivererror□奇偶校驗(yàn)例子□針對(duì)突發(fā)性長(zhǎng)錯(cuò)誤，可采用交錯(cuò)奇偶校驗(yàn)位來處理。23出錯(cuò)處理（8）

□

循環(huán)冗余校驗(yàn)（CyclicRedundancyCheck,CRC）也稱多項(xiàng)式編碼（PolynomialCode）

基本思想○前提條件（1）將位串看成是系數(shù)為0或1的多項(xiàng)式。如10001011*x6+0*x5+0*x4+0*x3+1*x2+1*x1（2）發(fā)送方和接收在數(shù)據(jù)傳輸前商定一個(gè)生成多項(xiàng)式G(x).如G(x)=x4+x+1------10011（3）傳輸幀有m位，對(duì)應(yīng)的多項(xiàng)式為M(x)?！?/p>

校驗(yàn)和（Checksum）TCP/IP協(xié)議中使用的一種校驗(yàn)方法。24出錯(cuò)處理（9）

○CRC校驗(yàn)和計(jì)算算法（1）假設(shè)G(x)的階為r。在幀的低位端加上r個(gè)0，此時(shí)幀長(zhǎng)為m+r，對(duì)應(yīng)多項(xiàng)式為xrM(x)；（2）利用模2除法，用對(duì)應(yīng)的G(x)的位串去除xrM(x)對(duì)應(yīng)的位串，余數(shù)記為P(x)；（3）利用模2減法，xrM(x)-除法運(yùn)算中的余數(shù)P(x)，結(jié)果記為T(x)就是帶校驗(yàn)和的幀。25出錯(cuò)處理（10）

○CRC校驗(yàn)和計(jì)算例子問題：發(fā)送數(shù)據(jù)幀1101011011m=10，M(x)為(m–1=9)階多項(xiàng)式M(x)＝x9+x8+x6+x4+x3+x+1第一步：選擇生成多項(xiàng)式G(x)=x4+x+1r=4，10011

第二步：形成多項(xiàng)式xrM(x)n=m+r=10+4=14，xrM(x)為13階多項(xiàng)式x4M(x)＝x13+x12+x10+x8+x7+x5+x411010110110000

26出錯(cuò)處理（11）

○CRC校驗(yàn)和計(jì)算例子第三步：用以2為模的除法求余數(shù) 余數(shù)[11010110110000/10011]=1110第四步：用以2為模的減法計(jì)算校驗(yàn)和 發(fā)送幀T(x)＝1101011011111027出錯(cuò)處理（12）

○

CRC檢錯(cuò)能力說明（1）如果傳輸過程出錯(cuò)了，即有一些位的0或1發(fā)生了變化。把發(fā)生變化的位記錄為1，其他位置為0，它對(duì)應(yīng)一個(gè)多項(xiàng)式E(x)。（2）接收者的信息則為T(x)+E(x)；（3）校驗(yàn)時(shí)候計(jì)算為[T(x)+E(x)]/G(x)=E(x)/G(x)○CRC校驗(yàn)和驗(yàn)證

接收者接收到T(X)后，用T(x)/G(x)，余數(shù)應(yīng)該為0，否則就判定為有錯(cuò)誤。T(X)=xrM(x)-P(x)如果E(x)不被G(x)除盡，則可以檢測(cè)到傳輸過程中出錯(cuò)了，如果剛好被除盡了，則該錯(cuò)誤沒有被檢測(cè)到。所以G(x)很重要。28基本數(shù)據(jù)鏈路協(xié)議（1）◆應(yīng)用情況點(diǎn)到點(diǎn)信道，也就是只有一個(gè)發(fā)送者和接收者?！魩讉€(gè)重要功能函數(shù)□from_network_layer□to_network_layer□from_physical_layer□to_physical_layer29基本數(shù)據(jù)鏈路協(xié)議（2）◆無限制的單工協(xié)議□前提條件：

單方向數(shù)據(jù)傳輸（即只有一個(gè)發(fā)送者和接收者）

理想信道（信道不出錯(cuò)，傳輸速度極快）

通信雙方能力無窮（發(fā)送者不停發(fā)送，接收者不停接收）□發(fā)送者基本過程第一步：從網(wǎng)絡(luò)層獲得數(shù)據(jù)第二步：發(fā)送到物理層。□接收者基本過程第一步：等待數(shù)據(jù)到達(dá)第二步：從物理層提取數(shù)據(jù)第三步：把數(shù)據(jù)遞交給網(wǎng)絡(luò)層30基本數(shù)據(jù)鏈路協(xié)議（3）SENDER:from_network_layerframingto_physical_layerto_network_layerRECEIVER:wait_for_eventfrom_physical_layer31基本數(shù)據(jù)鏈路協(xié)議（4）◆什么是協(xié)議？通信雙方關(guān)于如何進(jìn)行通信的一種約定◆什么是服務(wù)？實(shí)體為它的用戶提供的功能。如無限制單工協(xié)議規(guī)范雙方的行為來完成數(shù)據(jù)的傳輸如數(shù)據(jù)鏈路層為網(wǎng)絡(luò)層提供傳輸數(shù)據(jù)的功能如物理層為數(shù)據(jù)鏈路層提供0-1比特流傳輸功能◆什么是接口？定義調(diào)用服務(wù)的原語操作如from_physical_layer和to_physical_layer等□服務(wù)是用戶的功能需求（該層要解決的問題）□協(xié)議是完成服務(wù)功能的實(shí)現(xiàn)過程（解決問題的程序）□接口是程序的交互界面（用戶操作界面）32基本數(shù)據(jù)鏈路協(xié)議（5）◆無限制的單工協(xié)議分析現(xiàn)實(shí)問題：接收方的接收能力是有限制的?！魺o限制的單工協(xié)議改進(jìn)□

問題分析：假設(shè)接收者處理一幀的時(shí)間是t，則希望發(fā)送者在t時(shí)間后，再發(fā)送下一幀。t如何確定？如何知道接收者的t？（很難估計(jì)）□解決辦法：因?yàn)樾诺朗抢硐胄诺溃俣群芸斓?，讓接收者在處理完畢一幀后，反饋一個(gè)信息告訴發(fā)送繼續(xù)發(fā)送數(shù)據(jù)（基于反饋的流控制機(jī)制）—單工停-等協(xié)議

關(guān)鍵問題：如何避免大量數(shù)據(jù)淹沒接收方？——流控制33基本數(shù)據(jù)鏈路協(xié)議（6）◆單工的停-等協(xié)議□前提條件：

單方向數(shù)據(jù)傳輸（即只有一個(gè)發(fā)送者和接收者）

理想信道（信道不出錯(cuò)，傳輸速度極快）

接收者能力有限34A

Bf1ack□發(fā)送者基本過程第一步：從網(wǎng)絡(luò)層獲得數(shù)據(jù)第二步：發(fā)送到物理層第三步：等待對(duì)方的反饋第一步：等待數(shù)據(jù)到達(dá)第二步：從物理層提取數(shù)據(jù)第三步：把數(shù)據(jù)遞交給網(wǎng)絡(luò)層第四步：發(fā)送反饋幀□接收者基本過程基本數(shù)據(jù)鏈路協(xié)議（7）等待時(shí)間35基本數(shù)據(jù)鏈路協(xié)議（8）SENDER:from_network_layerframingto_physical_layerRECEIVER:wait_for_eventto_network_layerwait_for_eventfrom_physical_layerto_physical_layerWaitforacksendack36基本數(shù)據(jù)鏈路協(xié)議（9）◆單工的停-等協(xié)議分析□問題1：理想信道是不存在的，信道有噪聲，即傳輸過程中，幀可能會(huì)出錯(cuò)。

錯(cuò)誤類型：（1）數(shù)據(jù)位出錯(cuò)；（2）數(shù)據(jù)丟失

處理錯(cuò)誤方式分析：（1）數(shù)據(jù)位出錯(cuò)：糾錯(cuò)，檢錯(cuò)+重傳（如何選擇？）（2）數(shù)據(jù)丟失：將丟失的數(shù)據(jù)重傳（解決問題效果如何？）37基本數(shù)據(jù)鏈路協(xié)議（10）◆單工的停-等協(xié)議分析□問題2：發(fā)送方如何知道數(shù)據(jù)丟失？——沒有接收到對(duì)方的反饋幀，則認(rèn)為數(shù)據(jù)丟失！□后續(xù)問題：如果數(shù)據(jù)并沒有丟失，而是反饋幀丟失了呢？接收到兩個(gè)A幀，都遞交給了上層協(xié)議數(shù)據(jù)重復(fù)，協(xié)議出錯(cuò)了。發(fā)送者接收者AA反饋幀丟失BAA解決辦法：每一幀都帶上一個(gè)編號(hào)，稱為序列號(hào)定時(shí)器！38◆單工的停-等協(xié)議分析基本數(shù)據(jù)鏈路協(xié)議（11）□序列號(hào)幾位合適？發(fā)送者接收者ABCBBCQ

發(fā)送B幀時(shí)，A幀以及之前的幀已經(jīng)發(fā)送并正確接收。

如果要重傳，則發(fā)送B幀，否則發(fā)送C幀。

對(duì)于接收到的Q幀，它可能是B幀或C幀。結(jié)論：對(duì)于停-等協(xié)議接收者而言，可能引起混淆的幀最多是2幀，因此需要1位的序列號(hào)。39基本數(shù)據(jù)鏈路協(xié)議（12）◆有噪聲的單工協(xié)議□前提條件：

單方向數(shù)據(jù)傳輸（即只有一個(gè)發(fā)送者和接收者）

噪聲信道（信道會(huì)出錯(cuò)：數(shù)據(jù)位錯(cuò)或丟失）

接收者能力有限□基本思想

在停-等協(xié)議的基礎(chǔ)上，增加出錯(cuò)處理機(jī)制（超時(shí)重傳輸機(jī)制）40基本數(shù)據(jù)鏈路協(xié)議（13）◆有噪聲的單工協(xié)議□發(fā)送者基本過程第一步：從網(wǎng)絡(luò)層獲得數(shù)據(jù)第二步：將幀編號(hào)，發(fā)送到物理層，啟動(dòng)超時(shí)定時(shí)器第三步：等待對(duì)方的反饋第四步：如果當(dāng)前幀的確認(rèn)幀到達(dá)，則跳到第一步第五步：如果超時(shí)定時(shí)器超時(shí)，則重傳當(dāng)前幀，并跳到第三步。第一步：等待數(shù)據(jù)到達(dá)第二步：從物理層提取數(shù)據(jù)，查看幀編號(hào)，確定是否是新的數(shù)據(jù)幀，如果不是，則跳到第一步，否則第三步，第三步：把數(shù)據(jù)遞交給網(wǎng)絡(luò)層第四步：發(fā)送反饋幀□接收者基本過程41next_frame_tosend=0from_network_layerframingto_physical_layerstart_timerstop_timer(next_frame_to_send

+1)mod2timeoutframe_arrivalwaitfrom_network_layer●SENDER42frame_expected=0waitfrom_physical_layerexpected?to_network_layer(frame_expected+1)mod2sendackYNframe_arrivalCksum_err●RECEIVER43基本數(shù)據(jù)鏈路協(xié)議（14）◆基本數(shù)據(jù)鏈路協(xié)議分析□

問題：?jiǎn)喂せ虬腚p工（即任何時(shí)候，線路上只有一個(gè)傳輸者和一個(gè)接收者），造成帶寬浪費(fèi)?！跣枨螅?jiǎn)喂f(xié)議的雙工改造，即支持雙向數(shù)據(jù)傳輸□方法1：雙獨(dú)立信道+2單工協(xié)議信道1（A數(shù)據(jù)信道/B確認(rèn)信道）信道2（B數(shù)據(jù)信道/A確認(rèn)信道）主機(jī)A主機(jī)B帶寬浪費(fèi)！主機(jī)A租用兩條信道，實(shí)際使用的只有一條的容量44基本數(shù)據(jù)鏈路協(xié)議（15）□方法2：一條線路+2邏輯信道+2單工協(xié)議主機(jī)A主機(jī)B

方法分析：對(duì)于主機(jī)A，發(fā)送兩種獨(dú)立數(shù)據(jù)：○主機(jī)A數(shù)據(jù)幀○主機(jī)B確認(rèn)幀｝幀結(jié)構(gòu)很相似，如目的地址、源地址等。

改進(jìn)思路：將數(shù)據(jù)幀和確認(rèn)幀合并一起發(fā)送？也就是發(fā)送數(shù)據(jù)的同時(shí)，將確認(rèn)信息附到外發(fā)的數(shù)據(jù)幀上?！訋Т_認(rèn)技術(shù)（Piggybacking）

新的問題：如果主機(jī)暫時(shí)沒有數(shù)據(jù)幀發(fā)送呢？——等待一段時(shí)間后，獨(dú)立確認(rèn)45基本數(shù)據(jù)鏈路協(xié)議（16）□方法3一條線路+2邏輯信道+（2單工協(xié)議+捎帶技術(shù)）雙工協(xié)議

數(shù)據(jù)幀和確認(rèn)幀使用同一種格式（捎帶技術(shù)）

收到數(shù)據(jù)幀后，等待一段時(shí)間后，發(fā)送獨(dú)立確認(rèn)幀□方法3分析發(fā)送方接收方分組1分組1ACK1分組2分組2ACK2分組3確認(rèn)機(jī)制發(fā)送方接收方分組1定時(shí)器分組1ACK1分組1定時(shí)器分組1ACK1分組2定時(shí)器重傳機(jī)制任何時(shí)候，線路上只有一個(gè)方向的數(shù)據(jù)。效率低！46滑動(dòng)窗口協(xié)議（1）發(fā)送方接收方數(shù)據(jù)幀1數(shù)據(jù)幀1ACK1數(shù)據(jù)幀2數(shù)據(jù)幀2ACK2數(shù)據(jù)幀3數(shù)據(jù)幀3ACK3◆基本思想在等待確認(rèn)的時(shí)候，繼續(xù)發(fā)送數(shù)據(jù)幀

一次最多能發(fā)送多少幀數(shù)據(jù)？——窗口值如上例中，窗口值為347滑動(dòng)窗口協(xié)議（2）□數(shù)據(jù)傳輸?shù)幕具^程12345678910111213141516數(shù)據(jù)幀WindowSize=8已發(fā)并得到確認(rèn)不能發(fā)送已發(fā)未得到確認(rèn)未發(fā)但可以發(fā)——滑動(dòng)窗口的來由！48滑動(dòng)窗口協(xié)議（3）◆

1位滑動(dòng)窗口協(xié)議——滑動(dòng)窗口大小為1□基本過程:發(fā)送一幀，等待確認(rèn)，然后下一幀（停-等協(xié)議）一切OK？next_frame_to_send=0;frame_expected=0;from_network_layer(&buffer);=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);while(true){…………49□問題1：如果通信雙方同時(shí)發(fā)送數(shù)據(jù)呢？A發(fā)送（0，1，A0）B發(fā)送（0，1，B0）B得到（0，1，A0）*B發(fā)送（0，0，B0）*A得到（0，1，B0）A發(fā)送（0，0，A0）B得到（0，0，A0）B發(fā)送（1，0，B1）B發(fā)送（0，0，B0）A發(fā)送（1，0，A1）即使沒有傳輸錯(cuò)誤，也會(huì)有一半的幀是重復(fù)的！如果提前超時(shí)，也會(huì)出現(xiàn)類型情況！HOW？滑動(dòng)窗口協(xié)議（4）1位滑動(dòng)窗口協(xié)議分析50滑動(dòng)窗口協(xié)議（5）◆

1位滑動(dòng)窗口協(xié)議分析□問題2：效率低下

衛(wèi)星通信的例子○

衛(wèi)星信道50kbps○

往返延時(shí)500ms（單程時(shí)間為250ms）○數(shù)據(jù)幀長(zhǎng)度為1000bits發(fā)送數(shù)據(jù)時(shí)間=1000b/50kbps=20ms確認(rèn)幀收到時(shí)間=500+20=520ms帶寬利用率=20/520=3.85%太浪費(fèi)了！51滑動(dòng)窗口協(xié)議（6）□那么窗口大小為多少幀合適呢？□理想狀態(tài)：當(dāng)窗口數(shù)據(jù)全部發(fā)送完畢時(shí)，正好第一幀的確認(rèn)到達(dá)！發(fā)送者接收者1幀2幀收到1幀，ACK1收到2幀，ACK2n-1幀n幀收到n-1幀，ACKn-1收到n幀，ACKn發(fā)送窗口值為nn+1幀n+2幀——管道化技術(shù)◆

滑動(dòng)窗口協(xié)議改進(jìn)52滑動(dòng)窗口協(xié)議（7）□理想的窗口值

假設(shè)信道帶寬為b位/秒、往返時(shí)間為r秒、幀長(zhǎng)為m位發(fā)送完窗口中n幀的時(shí)間=(m*n)/b第一幀確認(rèn)的時(shí)間=m/b+r(m*n)/b=m/b+rn=1+rb/m如衛(wèi)星通信例子中，理想窗口值n=1+rb/m=1+0.5*50K/1000=26◆

管道技術(shù)分析53滑動(dòng)窗口協(xié)議（8）◆

管道技術(shù)分析□問題如果在一個(gè)很長(zhǎng)的幀流中有一幀出錯(cuò)了，如何對(duì)待后續(xù)的正確幀？□兩種基本方法

方法1(回退n幀方法）接收方丟棄所有后續(xù)的幀，并且不為丟棄的幀發(fā)送確認(rèn)幀。

方法2(選擇性重傳）給所有正確接收的幀發(fā)送確認(rèn)幀，給檢查到錯(cuò)誤的幀發(fā)送否定的確認(rèn)。54滑動(dòng)窗口協(xié)議（9）◆回退n幀技術(shù)errordiscardacksendtimeout0

1

E

D

D

D

D

D

D

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

2

3

4

5

6

7

8

resend55滑動(dòng)窗口協(xié)議（10）◆使用回退n幀技術(shù)的協(xié)議

情況1：發(fā)送上層數(shù)據(jù)第一步：組裝幀，捎帶確認(rèn)；第二步：發(fā)送數(shù)據(jù)；第三步：?jiǎn)?dòng)定時(shí)器；

情況3：定時(shí)器超時(shí)第一步：將超時(shí)間數(shù)據(jù)幀重新發(fā)送一次。第二步：重新啟動(dòng)定時(shí)器

情況2：接收到一幀第一步：檢查數(shù)據(jù)是否是新鮮的，如果是，則將數(shù)據(jù)遞交給上層；第二步：檢查確認(rèn)信息，如果是已經(jīng)發(fā)送數(shù)據(jù)的確認(rèn)，將有關(guān)的定時(shí)器終止，發(fā)送窗口前移動(dòng)一格；通信進(jìn)程基本過程：56滑動(dòng)窗口協(xié)議（11）◆選擇性重傳技術(shù)數(shù)據(jù)發(fā)送方數(shù)據(jù)接收方1幀2幀3幀4幀ACK1ACK3ACK4NAK257滑動(dòng)窗口協(xié)議（12）◆使用選擇性重傳技術(shù)的協(xié)議通信進(jìn)程基本過程：

情況1：發(fā)送上層數(shù)據(jù)第一步：組裝幀，捎帶確認(rèn)；第二步：發(fā)送數(shù)據(jù)；第三步：?jiǎn)?dòng)定時(shí)器；

情況2：接收到一幀第一步：檢查數(shù)據(jù)是否是新鮮的，如果是，則將數(shù)據(jù)遞交給上層；如果數(shù)據(jù)出錯(cuò)，則發(fā)送否定確認(rèn)。第二步：檢查確認(rèn)信息，如果是已經(jīng)發(fā)送數(shù)據(jù)的確認(rèn)，將有關(guān)的定時(shí)器終止，發(fā)送窗口前移動(dòng)一格；第三步：如果是否定確認(rèn)，則將否定確認(rèn)對(duì)應(yīng)的幀重發(fā)；

情況3