計(jì)算機(jī)網(wǎng)絡(luò)第三章1

1、第三章數(shù)據(jù)鏈路層主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實(shí)例 一、數(shù)據(jù)鏈路層的定義和功能1、定義數(shù)據(jù)鏈路層主要討論的是在相鄰兩個(gè)節(jié)點(diǎn)之間如何進(jìn)行可靠且有效的通信的問題。局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng) 點(diǎn)到點(diǎn) 端到端 端到端節(jié)點(diǎn)鏈路link（物理鏈路）：是一條無源的點(diǎn)到點(diǎn)的物理路段，中間沒有任何其他的交換節(jié)點(diǎn)。路徑path：從源端到目的端的一條通路，可能經(jīng)由許多中間節(jié)點(diǎn)。數(shù)據(jù)鏈路：物理鏈路傳輸兩端的硬件相關(guān)的通信協(xié)議路徑鏈路網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層一、數(shù)據(jù)鏈路層的定義和功能2、功能（設(shè)計(jì)要點(diǎn)）數(shù)

2、據(jù)鏈路層的主要功能包括以下三個(gè)方面：為網(wǎng)絡(luò)層提供一個(gè)良好定義的服務(wù)接口；處理傳輸錯(cuò)誤（差錯(cuò)控制）；調(diào)節(jié)數(shù)據(jù)流，確保慢速的接收方不會(huì)被快速的發(fā)送方淹沒（流量控制）。網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層分 組凈荷域頭尾3、數(shù)據(jù)鏈路層的服務(wù)數(shù)據(jù)鏈路層的功能之一是向網(wǎng)絡(luò)層提供服務(wù)。最主要的服務(wù)是將數(shù)據(jù)從源主機(jī)的網(wǎng)絡(luò)層傳輸?shù)侥康闹鳈C(jī)的網(wǎng)絡(luò)層。IP 數(shù)據(jù)報(bào)1010 0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點(diǎn) A結(jié)點(diǎn) B物理層IP 數(shù)據(jù)報(bào)1010 0110幀裝入數(shù)據(jù)鏈路層傳送的是幀數(shù)據(jù)鏈路層的傳輸過程 把從網(wǎng)絡(luò)層獲取到的分組封裝到幀中，加一定的校驗(yàn)信息，然后交給物理層用某種信號(hào)表示二進(jìn)制數(shù)據(jù)位傳送到目的節(jié)點(diǎn)； 在目的節(jié)點(diǎn)，再

3、通過目的節(jié)點(diǎn)的物理層和數(shù)據(jù)鏈路層上傳到網(wǎng)絡(luò)層。數(shù)據(jù)鏈路層的作用 為網(wǎng)絡(luò)層提供一條可靠的數(shù)據(jù)鏈路。局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層傳輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層傳輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從網(wǎng)絡(luò)層次上來看數(shù)據(jù)的流動(dòng)局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R

4、3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動(dòng)虛擬數(shù)據(jù)通路實(shí)際數(shù)據(jù)通路數(shù)據(jù)鏈路層可以提供多種不同的服務(wù)，但一般情況下，通常會(huì)提供以下三種服務(wù)： 無確認(rèn)的無連接服務(wù)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送獨(dú)立的幀，傳輸前不需要建立邏輯連接，傳輸后也不要求目的節(jié)點(diǎn)進(jìn)行確認(rèn)，即不保證幀的正確傳輸。這類服務(wù)適用于誤碼率非常低的傳輸環(huán)境及一些實(shí)時(shí)業(yè)務(wù)，如以太網(wǎng)有確認(rèn)的無連接服務(wù)傳輸前不需要建立邏輯連接，但目的節(jié)點(diǎn)對(duì)于收到的每個(gè)幀都必須進(jìn)行確認(rèn)，它保證每個(gè)幀都能被正確接收。這類服務(wù)適用于誤碼率較高的傳輸環(huán)境，如無線系統(tǒng)。有確認(rèn)的面向連接的服務(wù)傳輸前需要建立邏輯連接，每個(gè)幀被編上序號(hào)按序發(fā)送，目的節(jié)點(diǎn)對(duì)收到的幀進(jìn)行檢錯(cuò)、確認(rèn)與排序，它保

5、證向網(wǎng)絡(luò)層遞交正確有序的數(shù)據(jù)流。數(shù)據(jù)鏈路層使用的信道主要有以下兩種類型：點(diǎn)對(duì)點(diǎn)信道。這種信道使用一對(duì)一的點(diǎn)對(duì)點(diǎn)通信方式。廣播信道。這種信道使用一對(duì)多的廣播通信方式，因此過程比較復(fù)雜。廣播信道上連接的主機(jī)很多，因此必須使用專用的共享信道協(xié)議來協(xié)調(diào)這些主機(jī)的數(shù)據(jù)發(fā)送。介質(zhì)訪問控制子層（MAC）：它是數(shù)據(jù)鏈路層上特有的一個(gè)子層，用于解決共享信道的分配問題 主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實(shí)例 二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個(gè)節(jié)點(diǎn)的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯(cuò)控制 流量控制將傳輸?shù)男畔⒔M合成幀成幀封裝成幀(fra

6、ming)就是在一段數(shù)據(jù)的前后分別添加首部和尾部，然后就構(gòu)成了一個(gè)幀。確定幀的界限-首部和尾部的重要作用之一就是進(jìn)行幀定界。 幀結(jié)束幀首部IP 數(shù)據(jù)報(bào)幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長開始發(fā)送幀開始成幀 (framing) 字符計(jì)數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 字符計(jì)數(shù)法：每一個(gè)幀的第一個(gè)字段攜帶幀的長度信息。 5123456789801234568第一幀第二幀第三幀缺點(diǎn)：幀頭出錯(cuò)不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀。a 無差錯(cuò)512347678980123456第一幀第二幀第三幀b 有一個(gè)差錯(cuò)成幀 (framing) 字符計(jì)數(shù)法帶字節(jié)

7、填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 帶字節(jié)填充的分界符法 分界符法：使用特殊的字節(jié)（標(biāo)志字節(jié)flagbyte）來表示幀的開始與結(jié)束，當(dāng)失去同步后，只需要搜索特定的標(biāo)志字節(jié)就可以了。-具有再同步能力當(dāng)標(biāo)志字節(jié)的位模式FLAG出現(xiàn)在數(shù)據(jù)中怎么辦？成幀 (framing) 帶字節(jié)填充的分界符法：為避免在幀的其它部分出現(xiàn)與標(biāo)志字節(jié)相同的位模式，采用了字節(jié)填充的方法，即在與標(biāo)志字節(jié)相同的字符前插入轉(zhuǎn)義字符ESC，如圖。（PPP協(xié)議） 成幀 (framing) 帶字節(jié)填充的分界符法 缺點(diǎn)：依賴于特定的字符編碼集（如ASCII字符中，F(xiàn)LAG用7E H表示，ESC用1

8、B H表示，只能是8位字符模式），靈活性差（實(shí)際中，并不是所有字符碼都采用8位字符表示，UNICODE使用的是16位字符）成幀 (framing) 字符計(jì)數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 帶位填充的分界標(biāo)志法： 使用一個(gè)特殊的比特模式（如：01111110）作為幀的起始與結(jié)束標(biāo)志（Flag）。 -具有再同步能力當(dāng)標(biāo)志符的位模式FLAG出現(xiàn)在數(shù)據(jù)中怎么辦？成幀 (framing) 為避免在幀的其它部分出現(xiàn)與此標(biāo)志相同的比特模式，采用了比特填充的方法，即在5個(gè)連續(xù)的1后插入一個(gè)0，如圖。（HDLC協(xié)議） 原始數(shù)據(jù)傳輸線路上的數(shù)據(jù)刪除填充位之后接收

9、存儲(chǔ)的數(shù)據(jù)成幀 (framing) 字符計(jì)數(shù)法帶字節(jié)填充的分界符法帶位填充的分界標(biāo)志法物理層編碼違例法成幀 (framing) 物理層編碼違例法：這種方法只適用于那些在物理層編碼中使用冗余技術(shù)的網(wǎng)絡(luò)。例如：以太網(wǎng)的物理層采用曼徹斯特編碼，它將比特“1”表示成高-低電平對(duì)，將比特“0”表示成低-高電平對(duì)，而高-高電平對(duì)和低-低電平對(duì)在編碼中沒有使用，這樣可以用這兩種無效的編碼標(biāo)識(shí)幀的邊界。注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計(jì)數(shù)法和一種其它方法的組合。二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個(gè)節(jié)點(diǎn)的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯(cuò)控制 流量控制差錯(cuò)控制傳輸過程出錯(cuò)情況：幀（包括發(fā)送

10、幀和響應(yīng)幀）出錯(cuò)；校驗(yàn)和確認(rèn)幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時(shí)和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號(hào) 幀出錯(cuò)信號(hào)在任何信道上傳輸都存在著傳輸差錯(cuò)，這些差錯(cuò)由多種物理現(xiàn)象引起，解決差錯(cuò)問題的方法有兩種：一種是在要發(fā)送的數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯(cuò)，但不知道是哪里出錯(cuò)，這種編碼方法叫差錯(cuò)檢測碼，或簡稱檢錯(cuò)碼。另一種是在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯(cuò)的位，這種編碼方法叫差錯(cuò)校正碼，或簡稱糾錯(cuò)碼。使用糾錯(cuò)碼傳數(shù)據(jù)，效率低，適用于不可能重傳的場合；大多數(shù)情況采用檢錯(cuò)碼加重傳。檢錯(cuò)碼奇偶校驗(yàn)碼多項(xiàng)式編碼，又叫循環(huán)冗余校驗(yàn)碼CRC（Cyclic Redunda

11、ncy Check）奇偶校驗(yàn)碼在每個(gè)字符的數(shù)據(jù)位傳輸之前，先檢測并計(jì)算奇偶校驗(yàn)位，然后附加在其后；接收機(jī)重新計(jì)算收到字符的奇偶校驗(yàn)位，確定該字符是否出現(xiàn)傳輸差錯(cuò)；注：只能發(fā)現(xiàn)奇數(shù)個(gè)錯(cuò)誤，如果有偶數(shù)比特出錯(cuò)，奇偶校驗(yàn)位無效；檢錯(cuò)碼奇偶校驗(yàn)碼多項(xiàng)式編碼，又叫循環(huán)冗余校驗(yàn)碼CRC（Cyclic Redundancy Check）多項(xiàng)式編碼（循環(huán)冗余校驗(yàn)碼CRC）基本原理：它先將要發(fā)送的信息數(shù)據(jù)與一個(gè)通信雙方共同約定的數(shù)據(jù)進(jìn)行除法運(yùn)算，并根據(jù)余數(shù)得出一個(gè)校驗(yàn)碼，然后將這個(gè)校驗(yàn)碼附加在信息數(shù)據(jù)幀之后發(fā)送出去。 接收端接收數(shù)據(jù)后，將包括校驗(yàn)碼在內(nèi)的數(shù)據(jù)幀再與約定的數(shù)據(jù)進(jìn)行除法運(yùn)算，若余數(shù)為“0”，就表示接

12、收的數(shù)據(jù)正確，若余數(shù)不為“0”，則表明數(shù)據(jù)在傳輸?shù)倪^程中出錯(cuò)。 定義：它將位串看成是某個(gè)一元多項(xiàng)式的系數(shù)。如果一個(gè)m位的幀，可以看作是一個(gè)m1次多項(xiàng)式的系數(shù)列表，該多項(xiàng)式用M(x)表示,共有m項(xiàng)，從Xm1到X0。 如1011001看成是一元多項(xiàng)式X6 + X4 + X3 + 1的系數(shù)；生成多項(xiàng)式G(x)：雙方預(yù)先確定的一個(gè)多項(xiàng)式,共有r項(xiàng)；冗余多項(xiàng)式R(x)： xrM(x)/G(X)的余數(shù)；碼多項(xiàng)式T(x)：T(x) 等于 xrM(x) 減去 余數(shù)R(x)；具體實(shí)現(xiàn)步驟：1、若G(x)為r階。原始數(shù)據(jù)為m位，其多項(xiàng)式為M(x)，則在原始數(shù)據(jù)后面添加r個(gè)0，實(shí)際傳輸數(shù)據(jù)為m+r位，相應(yīng)多項(xiàng)式為x

13、rM(x)。2、按模2除法用對(duì)應(yīng)于G(x)的位串去除對(duì)應(yīng)于xrM(x)的位串。3、按模2減法從對(duì)應(yīng)于xrM(x)的位串中減去余數(shù)（等于或小于r位），結(jié)果就是要傳送的帶校驗(yàn)和的多項(xiàng)式T(x)。檢錯(cuò)方法：用對(duì)應(yīng)于G(x)的位串去除對(duì)應(yīng)于T(x)的位串，若余式為0則認(rèn)為傳輸正確，否則認(rèn)為傳輸錯(cuò)誤例1 取G（X）X4+X+1，假設(shè)欲發(fā)送的一段信息101100110，問在線路上傳輸?shù)拇a字是？ 10101100010011 1011001100000 10011 10101 10011 11010 10011 10010 10011 1000解：由G（X）X4+X+1得 生成的碼字為：10011，r為4

14、原始信息101100110對(duì)應(yīng)的多項(xiàng)式 M(x)=X8+X6+X5+X2+X, XrM(x)=X4 (X8+X6+X5+X2+X)= X12+X10+X9+X6+X5,則XrM(x)對(duì)應(yīng)的碼字為：1011001100000 用對(duì)應(yīng)的G（X）的碼字去除對(duì)應(yīng)的XrM(x)的位串得余數(shù)為1000.把XrM(x)位串與余數(shù)相加就是實(shí)際要傳送的碼字，為： 1011001101000例2.已知：接收碼字:1100111001多項(xiàng)式: T(X)=X9+X8+X5+X4+X3+1 生成多項(xiàng)式:G(X)=X4+X3+1(r=4)求：碼字的正確性。若正確，則指出冗余碼和信息碼。解： 1）用接收碼字除以生成碼，余數(shù)

15、為0，所以碼字正確。 2)因r=4，所以冗余碼是：1001，信息碼是:110011 生成多項(xiàng)式G(x)的選擇四個(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= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗(yàn) CRC 差錯(cuò)檢測技術(shù)只能做到無差錯(cuò)接受(accept)。 “無差錯(cuò)接受”是指：凡是

16、接受的幀（即不包括丟棄的幀），我們都能以非常接近于 1 的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯(cuò)。 也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒有傳輸差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機(jī)制。 什么樣的錯(cuò)誤可以被檢測到？ 在接收方收到帶校驗(yàn)和的幀后，用G(x)來除它。如果E（x）表示一個(gè)錯(cuò)誤多項(xiàng)式，則在接收方要計(jì)算: T（x） E（x）/ G（x）因?yàn)門（x）/ G（x）=0，所以就是要計(jì)算E（x）/ G（x）的值。如果錯(cuò)誤多項(xiàng)式E（x）恰好包含G（x）作為它的一個(gè)因子，則這樣的錯(cuò)誤將無法檢測出來；否則其他錯(cuò)誤都可以檢測得到。 差

17、錯(cuò)控制傳輸過程出錯(cuò)情況：幀（包括發(fā)送幀和響應(yīng)幀）出錯(cuò)；校驗(yàn)和確認(rèn)幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時(shí)和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號(hào) ACK（ Acknowledgement ）NAK（Negative Acknowledgement）幀丟失通過發(fā)送方的計(jì)時(shí)器解決超時(shí)、重傳超時(shí)（TimeOut）：發(fā)送方一旦發(fā)送一個(gè)幀，就啟動(dòng)一個(gè)計(jì)時(shí)器，如果在規(guī)定的時(shí)間內(nèi)，收不到回應(yīng)，則在計(jì)時(shí)器溢出時(shí)，在重發(fā)此幀。注： 超時(shí)時(shí)間的設(shè)置 差錯(cuò)控制傳輸過程出錯(cuò)情況：幀（包括發(fā)送幀和響應(yīng)幀）出錯(cuò)；校驗(yàn)和確認(rèn)幀（包括發(fā)送幀和響應(yīng)幀）丟失；超時(shí)和重發(fā)幀（包括發(fā)送幀和響應(yīng)幀）重復(fù)；加序號(hào) 幀重復(fù)如果接收方發(fā)送的確認(rèn)

18、幀丟失，導(dǎo)致發(fā)送方多次發(fā)送同一幀，接收方多次收到同一幀，造成了幀重復(fù)；要區(qū)別是否是同一幀，在每一幀中加入一個(gè)幀的編號(hào)二、數(shù)據(jù)的可靠傳輸數(shù)據(jù)鏈路層的主要目的：保證相鄰兩個(gè)節(jié)點(diǎn)的可靠性傳輸。將傳輸?shù)男畔⒔M合成幀差錯(cuò)控制（校驗(yàn)、重傳）流量控制流量控制當(dāng)發(fā)送端的發(fā)送速度大于接收端的接收速度，或發(fā)送端所在的網(wǎng)絡(luò)傳輸速率大于接收端所在的網(wǎng)絡(luò)傳輸速率時(shí)，就需要流量控制。常見的方法有兩種： 基于反饋的流控制窗口機(jī)制 基于速率的流控制幀的數(shù)據(jù)結(jié)構(gòu)（一般意義上）：確認(rèn)號(hào)ack幀的數(shù)據(jù)部分（分組）info幀序號(hào)seq幀類型kind幀頭主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)

19、據(jù)鏈路層協(xié)議實(shí)例 三、基本的數(shù)據(jù)鏈路層協(xié)議通信模型的基本假設(shè)：1、假設(shè)一臺(tái)主機(jī)上，物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層都是獨(dú)立的進(jìn)程；2、A、B兩臺(tái)主機(jī)要求可靠的、面向連接的服務(wù)。3、在接收方的數(shù)據(jù)鏈路層，正在運(yùn)行wait_for_event(&event),即等待某個(gè)事件發(fā)生數(shù)據(jù)鏈路層主機(jī) A緩存主機(jī) B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀 數(shù)據(jù)鏈路層通過過程調(diào)用wait_for_event(&event),來等待事情的發(fā)生。 當(dāng)一個(gè)數(shù)據(jù)幀到達(dá)接收方時(shí)（可看作有一個(gè)事件發(fā)生 event），硬件會(huì)計(jì)算校驗(yàn)和。 如果校驗(yàn)和不正確，令eventchecksum_err； 如果校驗(yàn)和正確，令event

20、frame_arrival幀的數(shù)據(jù)結(jié)構(gòu)（一般意義上）：確認(rèn)號(hào)ack幀的數(shù)據(jù)部分（分組）info幀序號(hào)seq幀類型kind幀頭基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：有噪音信道的單工協(xié)議協(xié)議1：一種無限制的單工協(xié)議理想環(huán)境下的理想的協(xié)議，假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。不需要校驗(yàn)、確認(rèn)，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時(shí)上交主機(jī)。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控發(fā)送端：接收端：基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：

21、有噪音信道的單工協(xié)議協(xié)議2：一個(gè)單工的停等協(xié)議增加約束條件：接收方不可能具有足夠高的CPU處理能力來及時(shí)處理所有的接收幀，也不可能具有足夠大的緩沖區(qū)。協(xié)議2：一個(gè)單工的停等協(xié)議 假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。不需要校驗(yàn)，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時(shí)上交主機(jī)。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控 解決方法：發(fā)送方每發(fā)出一個(gè)幀后，等待接收方發(fā)回的一個(gè)確認(rèn)，接到確認(rèn)后，再繼續(xù)發(fā)送停等協(xié)議發(fā)送端：接收端：基本的數(shù)據(jù)鏈路層協(xié)議協(xié)議1：一種無限制的單工協(xié)議協(xié)議2：一種單工的停-等協(xié)議協(xié)議3：有噪音信道的單工協(xié)

22、議協(xié)議3：有噪音信道的單工協(xié)議理想環(huán)境下的理想的協(xié)議，假定1： 鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。不需要校驗(yàn)，不要重傳假定2： 不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時(shí)上交主機(jī)。接收端處理速度無限高，緩沖區(qū)無限大，不需要流控?cái)?shù)據(jù)幀可能被損壞，也可能丟失 需要校驗(yàn)和重傳需要流控 時(shí)間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a) 正常情況ABDATA0DATA0送主機(jī)ACK(c) 數(shù)據(jù)幀丟失重傳tout丟失 ！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d) 確認(rèn)幀丟失（數(shù)據(jù)幀重復(fù)）重傳tout丟失 ！噪聲信道傳輸過程中出錯(cuò)的三種情況協(xié)議3

23、的要點(diǎn)發(fā)送方要記錄下一個(gè)準(zhǔn)備發(fā)送的順序號(hào)接收方要記錄下一個(gè)期望接收的順序號(hào)發(fā)送過程和接收過程是嚴(yán)格交替的PAR（Positive Acknowledgement with Retransmission）支持重傳的肯定確認(rèn)協(xié)議 或者ARQ（Automatic Repeat reQuest）自動(dòng)重復(fù)請(qǐng)求協(xié)議 在協(xié)議3中，發(fā)送方應(yīng)重發(fā)當(dāng)前幀還是發(fā)下一幀，可以根據(jù)超時(shí)和是否收到確認(rèn)來判定，即它僅僅與前一幀和后一幀有關(guān)，所以，在協(xié)議中，只需要一位（0或1）就可以表示順序號(hào)發(fā)送端：等待應(yīng)答接收端：注意協(xié)議3重發(fā)機(jī)制的缺陷效率較低： 如接收方收到的幀出錯(cuò)或者整個(gè)數(shù)據(jù)幀丟失，則不發(fā)送確認(rèn)幀，發(fā)送方在超時(shí)后重發(fā)

24、，直至正確（效率低）； 前面的協(xié)議都假定數(shù)據(jù)幀沿著一個(gè)方向傳輸，但事實(shí)上大多數(shù)的通信都是雙向的。 雙向傳輸解決方案兩條線路（四根信道）： 兩根數(shù)據(jù) 兩根應(yīng)答 信道利用率低一條線路（兩根信道）：一根A到B，一根B到A問題是如何區(qū)分?jǐn)?shù)據(jù)和應(yīng)答？用不同的幀類型用捎帶（piggybacking）確認(rèn)滑動(dòng)窗口協(xié)議收發(fā)使用兩條信道 發(fā)送方可以連續(xù)發(fā)送多幀，接收方接受到一組幀后就從另一個(gè)信道發(fā)一個(gè)確認(rèn)，為提高信道使用效率，可使用捎帶確認(rèn)；幀是有序號(hào)的 在滑動(dòng)窗口協(xié)議中，每一個(gè)要發(fā)送的幀都包含一個(gè)序號(hào)，范圍是從0到某個(gè)最大值，最大值通常是2n-1，n為幀序號(hào)的長度。 即使過早的超時(shí)而導(dǎo)致的重發(fā)，也可以根據(jù)幀的

25、序號(hào)來避免幀的重復(fù)滑動(dòng)窗口協(xié)議的要點(diǎn)： 任何時(shí)刻發(fā)送進(jìn)程都要維護(hù)一組幀序號(hào)，對(duì)應(yīng)于一組已經(jīng)發(fā)送但尚未被確認(rèn)的幀，這些幀稱為落在發(fā)送窗口內(nèi)； 類似地，接收進(jìn)程也要維護(hù)一組幀序號(hào)，對(duì)應(yīng)于一組允許接收的幀，這些幀稱為落在接收窗口內(nèi)。發(fā)送窗口發(fā)送窗口中的序號(hào)代表已發(fā)送但尚未確認(rèn)的幀，其中窗口下沿代表最早發(fā)送但至今尚未確認(rèn)的幀。當(dāng)發(fā)送窗口尚未達(dá)到最大值時(shí)，可以從網(wǎng)絡(luò)層接收一個(gè)新的分組，然后將窗口上沿加1，并將新的上沿序號(hào)分配給新的幀；當(dāng)收到對(duì)窗口下沿幀的確認(rèn)時(shí)，窗口下沿加1。由于每一個(gè)幀都有可能傳輸出錯(cuò)，所以發(fā)送窗口中的幀都必須保留在緩沖區(qū)里以備重傳，直至收到確認(rèn)為止。當(dāng)發(fā)送窗口達(dá)到最大值時(shí)，停止從網(wǎng)絡(luò)

26、層接收數(shù)據(jù)，直到有一個(gè)緩沖區(qū)空出來為止。 接收窗口接收窗口中的序號(hào)代表允許接收的幀，任何落在窗口外的幀都被丟棄，落在窗口內(nèi)的幀存放到緩沖區(qū)里。當(dāng)收到窗口下沿幀時(shí)，將其交給網(wǎng)絡(luò)層，并產(chǎn)生一個(gè)確認(rèn)，然后窗口整體向前移動(dòng)一個(gè)位置。和發(fā)送窗口不同，接收窗口的大小是不變的，總是保持初始時(shí)的大小。接收窗口大小為1，意味著數(shù)據(jù)鏈路層只能順序接收數(shù)據(jù)，當(dāng)接收窗口大于1時(shí)不是這樣，但無論如何，數(shù)據(jù)鏈路層必須按順序?qū)?shù)據(jù)遞交給網(wǎng)絡(luò)層。 發(fā)送窗口和接收窗口圖示要發(fā)送的下一個(gè)幀的序號(hào)未得到確認(rèn)的幀的最小編號(hào)允許接收的序號(hào)最大的幀希望接收的幀三個(gè)窗口協(xié)議（協(xié)議46）1位滑動(dòng)窗口協(xié)議回退n幀的滑動(dòng)窗口協(xié)議選擇性重傳的滑動(dòng)

27、窗口協(xié)議1位滑動(dòng)窗口協(xié)議(協(xié)議4) 發(fā)送窗口 WT1，接收窗口WR1該協(xié)議使用停-等方式，所以只需要1比特長的幀序號(hào)。幀頭中至少包括seq和ack兩個(gè)域，ack用于對(duì)正確收到的幀的序號(hào)進(jìn)行確認(rèn)。由于支持雙向傳輸，所以每個(gè)協(xié)議實(shí)體需要同時(shí)完成發(fā)送和接收兩個(gè)功能。 1位滑動(dòng)窗口協(xié)議(協(xié)議4)接收方發(fā)送方比較兩種情況正常情況：發(fā)送方和接收方交替發(fā)送異常情況：當(dāng)發(fā)送方和接收方同時(shí)向?qū)Ψ桨l(fā)送，會(huì)造成不必要的重發(fā)，但協(xié)議也能夠正常運(yùn)行1位滑動(dòng)窗口協(xié)議(協(xié)議4)的缺點(diǎn)信道利用率低協(xié)議4：發(fā)送端的等待時(shí)間至少是發(fā)送端到接收端信號(hào)傳播時(shí)間的兩倍例：衛(wèi)星信道傳輸速率50kbps，往返傳輸延遲500ms，若傳100

28、0bit的幀，使用協(xié)議4，則傳輸一個(gè)幀所需時(shí)間為： 發(fā)送時(shí)間 + 信息信道延遲 + 確認(rèn)信道延遲（確認(rèn)幀很短，忽略發(fā)送時(shí)間）= 1000bit / 50kbps + 250ms + 250ms = 520ms 所以 ，信道利用率 = 20 / 520 4%如果我們?cè)诘却_認(rèn)的時(shí)候多發(fā)送一些幀（連續(xù)發(fā)送多幀后再等待確認(rèn)），就可以提高線路的效率。事實(shí)上就是允許發(fā)送窗口包含多個(gè)未被確認(rèn)的幀，這種技術(shù)稱為管道化（pipelining）。當(dāng)信號(hào)傳播延遲遠(yuǎn)大于幀的傳輸時(shí)間時(shí)，適合采用這個(gè)技術(shù)。 比如，如果位于幀流中的某個(gè)幀丟失或損壞了，會(huì)發(fā)生什么情況在發(fā)送進(jìn)程發(fā)現(xiàn)出錯(cuò)前，大量的后繼幀會(huì)到達(dá)接收方；當(dāng)一個(gè)壞

29、幀到達(dá)接收方時(shí)，顯然會(huì)被接收方丟棄，那么后面到來的幀如何處理？ 當(dāng)管道化技術(shù)建立在不可靠的信道上時(shí)會(huì)有一些問題有兩種基本的方法來處理以上問題：一種方法稱為 go back n（回退n幀） 接收進(jìn)程從出錯(cuò)幀起丟棄所有的后繼幀，并且不通知發(fā)送進(jìn)程。該策略對(duì)應(yīng)接收窗口為1的情況，即只能按順序接收幀，當(dāng)發(fā)送進(jìn)程超時(shí)后，必須按順序重傳所有未被確認(rèn)的幀，如圖3-16(a)。 有一個(gè)差錯(cuò)時(shí)，回退n幀 （WT7 WR1）三個(gè)窗口協(xié)議（協(xié)議46）1位滑動(dòng)窗口協(xié)議 發(fā)送窗口WT1，接收窗口WR1回退n幀的滑動(dòng)窗口協(xié)議 發(fā)送窗口WT1，接收窗口WR1選擇性重傳的滑動(dòng)窗口協(xié)議回退n幀的滑動(dòng)窗口協(xié)議程序（協(xié)議5）接收方

30、發(fā)送方回退n幀的滑動(dòng)窗口協(xié)議，如果編號(hào)由n 位組成，則 發(fā)送窗口WT2n1 接收窗口WR1缺陷：沒有考慮到當(dāng)某個(gè)方向上沒有數(shù)據(jù)要發(fā)送時(shí)，要對(duì)收到的幀進(jìn)行單獨(dú)確認(rèn)。在收到期待的幀后應(yīng)該啟動(dòng)一個(gè)ACK超時(shí)計(jì)時(shí)器，當(dāng)發(fā)生超時(shí)事件時(shí)，判斷哪個(gè)計(jì)時(shí)器超時(shí)，若是ACK計(jì)時(shí)器超時(shí)，應(yīng)該單獨(dú)發(fā)送一個(gè)確認(rèn)幀。而當(dāng)發(fā)送了一個(gè)數(shù)據(jù)包時(shí)，應(yīng)將被捎帶確認(rèn)的幀的ACK計(jì)時(shí)器終止。一旦數(shù)據(jù)幀丟失，在發(fā)送端意識(shí)到丟失（TimeOut）時(shí)，已經(jīng)有大量的數(shù)據(jù)幀到達(dá)接收端，被丟棄。這樣如果錯(cuò)誤率高的話，這種方法會(huì)浪費(fèi)很多帶寬，但對(duì)內(nèi)存需求不大。 圖三個(gè)窗口協(xié)議（協(xié)議46）1位滑動(dòng)窗口協(xié)議回退n幀的滑動(dòng)窗口協(xié)議選擇性重傳的滑動(dòng)窗口協(xié)

31、議另一種方法稱為選擇重傳（對(duì)應(yīng)接收窗口大于1的情況）只要是落入接收窗口且校驗(yàn)正確的幀，都要接收下來放到緩沖區(qū)里，這樣當(dāng)發(fā)送進(jìn)程意識(shí)到某個(gè)幀出錯(cuò)時(shí)，只是重傳此幀而不是所有的后繼幀，如圖3-16(b)。選擇重傳通常使用NAK對(duì)校驗(yàn)出錯(cuò)或疑為丟失的幀進(jìn)行確認(rèn)，以便發(fā)送進(jìn)程盡快重傳該幀。如果第二次重傳成功，接收方的數(shù)據(jù)鏈路層中會(huì)有許多按順序排列的正確幀，這些幀可以一起交給網(wǎng)絡(luò)層，并只對(duì)最高序號(hào)的幀進(jìn)行確認(rèn)。當(dāng)窗口很大時(shí)，這種方法需要大量的數(shù)據(jù)鏈路層內(nèi)存，但它不浪費(fèi)帶寬。 主要內(nèi)容一、數(shù)據(jù)鏈路層的定義和功能二、數(shù)據(jù)的可靠傳輸三、基本的數(shù)據(jù)鏈路層協(xié)議四、數(shù)據(jù)鏈路層協(xié)議實(shí)例 數(shù)據(jù)鏈路協(xié)議舉例高級(jí)數(shù)據(jù)鏈路控制 HDLC -High-Level Data Link Control因特網(wǎng)中的數(shù)據(jù)鏈路層 PPP-Point-to-Point Protocol高級(jí)數(shù)據(jù)鏈路控制HDLC最早在IBM大型機(jī)領(lǐng)域中使