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

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

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

一般來說，通信主體都應該擁有一個標識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

senderreceivererror□奇偶校驗例子□針對突發(fā)性長錯誤，可采用交錯奇偶校驗位來處理。23出錯處理（8）

□

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

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

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

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

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

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

26出錯處理（11）

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

○

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

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

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

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

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

問題分析：假設接收者處理一幀的時間是

t，則希望發(fā)送者在t時間后，再發(fā)送下一幀。t如何確定？如何知道接收者的t？（很難估計）□解決辦法：因為信道是理想信道，速度很快的，讓接收者在處理完畢一幀后，反饋一個信息告訴發(fā)送繼續(xù)發(fā)送數(shù)據(jù)（基于反饋的流控制機制）—單工停-等協(xié)議

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

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

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

接收者能力有限34A

Bf1ack□發(fā)送者基本過程第一步：從網(wǎng)絡層獲得數(shù)據(jù)第二步：發(fā)送到物理層第三步：等待對方的反饋第一步：等待數(shù)據(jù)到達第二步：從物理層提取數(shù)據(jù)第三步：把數(shù)據(jù)遞交給網(wǎng)絡層第四步：發(fā)送反饋幀□接收者基本過程基本數(shù)據(jù)鏈路協(xié)議（7）等待時間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：理想信道是不存在的，信道有噪聲，即傳輸過程中，幀可能會出錯。

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

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

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

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

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

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

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

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

在停-等協(xié)議的基礎上，增加出錯處理機制（超時重傳輸機制）40基本數(shù)據(jù)鏈路協(xié)議（13）◆有噪聲的單工協(xié)議□發(fā)送者基本過程第一步：從網(wǎng)絡層獲得數(shù)據(jù)第二步：將幀編號，發(fā)送到物理層，啟動超時定時器第三步：等待對方的反饋第四步：如果當前幀的確認幀到達，則跳到第一步第五步：如果超時定時器超時，則重傳當前幀，并跳到第三步。第一步：等待數(shù)據(jù)到達第二步：從物理層提取數(shù)據(jù)，查看幀編號，確定是否是新的數(shù)據(jù)幀，如果不是，則跳到第一步，否則第三步，第三步：把數(shù)據(jù)遞交給網(wǎng)絡層第四步：發(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é)議分析□

問題：單工或半雙工（即任何時候，線路上只有一個傳輸者和一個接收者），造成帶寬浪費?！跣枨螅簡喂f(xié)議的雙工改造，即支持雙向數(shù)據(jù)傳輸□方法1：雙獨立信道+2單