本科網(wǎng)絡(luò)課程講義：數(shù)據(jù)鏈路層ppt課件

1、Chapter 4 數(shù)據(jù)鏈路層n4.1數(shù)據(jù)鏈路層的功能n4.2差錯檢測與校正n4.3基本數(shù)據(jù)鏈路協(xié)議n4.4滑動窗口Slide Windows協(xié)議n4.5面向位的協(xié)議HDLCn4.6 Internet中的數(shù)據(jù)鏈路層4.1數(shù)據(jù)鏈路層的功能n向網(wǎng)絡(luò)層提供良好的服務(wù)接口n將物理層的比特流編成幀n差錯檢測4.1.1為網(wǎng)絡(luò)層提供服務(wù)n無確認(rèn)、無連接的服務(wù)n源端可以不需要建立連接就向目的端發(fā)送獨立的數(shù)據(jù)幀，而目的端也不需要對收到的幀進行確認(rèn)。n有確認(rèn)、無連接的服務(wù)n源端可以不需要建立連接就向目的端發(fā)送獨立的數(shù)據(jù)幀，但目的端需要對收到的幀進行確認(rèn)。n面向連接的服務(wù)n源端與目的端在通信前要先建立連接，然后在此

2、連接上互相傳輸數(shù)據(jù)幀，每一個幀都被編號，數(shù)據(jù)鏈路層保證傳送的幀被對方收到，且只收到一次，雙方通信完畢后拆除連接。用OSI服務(wù)原語表示服務(wù)接口懇求證實響應(yīng)指示網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層時間發(fā)送方網(wǎng)絡(luò)層接收方網(wǎng)絡(luò)層服務(wù)提供者數(shù)據(jù)鏈路層懇求證實響應(yīng)指示4.1.2成幀(framing)n1.字符計數(shù)n每一個幀的頭上描述幀的長度識別或表示一個幀的起始和結(jié)尾5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 7第一幀第二幀第三幀缺點：幀頭出錯不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀。4.1.2成幀(framing)n2.字符標(biāo)志n在幀的起始和結(jié)尾用特殊的字符標(biāo)志n例如：用ASCII字符DLE STX表

3、示幀的起始，DLE ETX表示結(jié)尾。識別或表示一個幀的起始和結(jié)尾在發(fā)送端檢查數(shù)據(jù)中是否有DLE字樣，如果有的話，就在它前面插入DLE，到接收端的鏈路層再將兩個或兩個以上的DLE，去掉一個DLE還原。4.1.2成幀(framing)n3.位標(biāo)志n用特殊的位序列表示幀的起始和結(jié)尾n例如，用01111110表示幀的起始和結(jié)尾識別或表示一個幀的起始和結(jié)尾為了避免起始、結(jié)尾標(biāo)志與幀中的數(shù)據(jù)混淆，發(fā)送端的數(shù)據(jù)鏈路層在檢測到數(shù)據(jù)比特流中有連續(xù)5個1出現(xiàn)時，就在其后加一個0，接收端的數(shù)據(jù)鏈路層在將5個1后面的0取走還原。4.1.2成幀(framing)n4.物理層編碼n在物理層用1.5或2個物理位表示一個數(shù)據(jù)

4、位來表示幀的起始與結(jié)尾。n例如在物理層編碼中，用 表示1，用 表示0n則可用 ， 作為起始、結(jié)尾標(biāo)志。識別或表示一個幀的起始和結(jié)尾4.1.3出錯控制n在有確認(rèn)的服務(wù)中，接收方需要對收到的數(shù)據(jù)幀進行確認(rèn)，通常以返回特別控制幀來告訴發(fā)送方收到的數(shù)據(jù)有沒有出錯，也可以通過返回的數(shù)據(jù)幀中的某些位來捎帶地進行確認(rèn)。n如果發(fā)送的數(shù)據(jù)丟失，那么接收端是不可能進行確認(rèn)的，怎么辦呢？n在發(fā)送端引入計數(shù)器，進行超時重發(fā)。為了避免相同的幀收到多次，需要對幀進行編號。4.1.4流量控制n當(dāng)發(fā)送端的發(fā)送速度大于接收端的接收速度，或發(fā)送端所在的網(wǎng)絡(luò)傳輸速率大于接收端所在的網(wǎng)絡(luò)傳輸速率時，就需要流量控制。n窗口機制n在任意

5、時刻，發(fā)送方發(fā)出n幀，其中有l(wèi)幀已得到確認(rèn)。而同一時刻，接收方收到并應(yīng)答了m幀，顯然l=m = n，等待確認(rèn)的幀的數(shù)目不允許超過W，即n-l =W，該W就是窗口。ll+WWn發(fā)送方mm+W接收方4.2差錯檢測與校正n信號在任何信道上傳輸都存在著傳輸差錯，這些差錯由多種物理現(xiàn)象引起，解決差錯問題的方法有兩種：n一種是在要發(fā)送的數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯，但不知道是哪里出錯，這種編碼方法叫差錯檢測碼，或簡稱檢錯碼。n另一種是在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯的位，這種編碼方法叫差錯校正碼，或簡稱糾錯碼。4.2.1糾錯碼n定義：一幀由m個數(shù)據(jù)位即報文和r個

6、冗余位即校驗位組成，設(shè)總長度為nn=m+r)，此長度為n的單元常稱為n位碼字。n定義：兩個碼字不同的位的數(shù)目稱為海明距離n例如，10001001 與10110001它們的海明距離為3。n對于n位碼字的集合，只有2m個碼字是有效的，在任意兩個有效碼字間找出具有最小海明距離的兩個碼字，該海明距離便定義為全部碼字的海明距離。n一種編碼的檢錯和糾錯能力取決于編碼后碼字的海明距離的大小。n為了檢測出d個比特的錯，需要使用距離為d+1的編碼。n例如：數(shù)據(jù)后加奇偶校驗位，編碼后的海明距離為2，能檢測1比特錯。n為了糾正d個比特的錯，必須用距離為2d+1的編碼。n例如有4個有效碼字：它們是0000000000

7、，0000011111，1111100000，1111111111，海明距離為5，能糾正2比特錯。糾正單比特錯的校驗位下界n設(shè)計一種編碼，它有m個信息位和r個校驗位，當(dāng)r滿足什么條件時，能糾正所有單比特錯？n 對2m個有效碼字的任何一個而言，有n個與該碼字距離為1的無效碼字，所以2m個有效碼字每一個都對應(yīng)有n+1個各不相同的位圖，n位碼字的總的位圖是2n個。n（n+12m=2n，n=m+r代入n（m+r+12m=n+1 糾正單比特誤碼的校驗位下界海明編碼n海明在1950年提出一種編碼來糾正單比特錯的編碼。該編碼是將碼字內(nèi)的位從左到右依次編號，編號為2的冪的位是校驗位如第1，2，4，8），其余為

8、信息位。n每個校驗位的取值應(yīng)使得包括自己在內(nèi)的一些集合服從規(guī)定的奇偶性。n集合的選取如下：n對編號為K的信息位來說，K可以分解成2的冪的和，如編號為11，11=1+2+8，即第11位由1，2，8校驗位校驗，它同時屬于1，2，8所在的集合。海明編碼舉例上例中，m=7，r=4，n=11，顯然24=11+1，采用偶校驗 3=1+2，5=1+46=2+4，7=1+2+49=1+8，10=2+811=1+2+8校驗位：1（3，5，7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11）能糾正單比特錯！在接收方，如果校驗位1不滿足偶校驗，而其他校驗位都滿足，則第1位出錯，

9、4.2.2檢錯碼n在實際通信中使用糾錯碼好還是檢錯碼好呢？n例題：假設(shè)一個信道誤碼率是10-6，且出錯是孤立產(chǎn)生的即只有單比特錯），數(shù)據(jù)塊長度為1000比特，如果采用糾錯編碼，需要10個校驗位2101011），傳送1M數(shù)據(jù)需要10000個校驗位；如果采用檢錯編碼，每個數(shù)據(jù)塊只需一個奇偶校驗位，傳送1M數(shù)據(jù)只需1000個校驗位和一個重傳的數(shù)據(jù)1001位，共需要2019比特。n在多數(shù)通信中采用檢錯編碼，但在單工信道中需要糾錯編碼。改進的奇偶校驗n對數(shù)據(jù)位組成一個L位寬，K位高的長方形距陣來發(fā)送，然后對每一列單獨計算奇偶位，并附在最后一行作為冗余位。X X X X X XXX X X X X XXX

10、 X X X X XXX X X X X XXR R R R R R.R奇偶位K行L列檢錯率：1.該方法可以檢測長度為L的突發(fā)性錯誤，但不能檢測長度為L+1的突發(fā)性錯誤。2.假設(shè)L列中任意一列檢測出錯的概率為1/2，那么，整個數(shù)據(jù)塊的錯判率為1/2L 。該方法用在ICMP報頭檢驗中。多項式編碼循環(huán)冗余碼CRC）nCRCCyclic Redundancy Check)nCRC編碼的一般操作：給定一個m比特的幀或報文，發(fā)送方生成r比特的序列也稱為幀檢驗序列FCS，F(xiàn)rame Check Series），形成m+r的碼字，該碼字能被某個事先確定的數(shù)整除。接收方用相同的數(shù)去除收到的幀，如果無余數(shù)，則認(rèn)

11、為數(shù)據(jù)幀無差錯。CRC也稱多項式編碼n多項式表示：即將k比特的數(shù)據(jù)用k項多項式表示，它的各項為X k-1X0，它的系數(shù)為數(shù)據(jù)中對應(yīng)位的0或1。n例如：110001可表示成X5+X4+1多項式編碼的推導(dǎo)設(shè)數(shù)據(jù)幀多項式表示為MX） m位序列 事先約定的除數(shù)為GX） r+1位序列 幀檢驗序列FCS為FX） r位序列加了檢驗序列的幀為TX）=X r MX）+FX） m+r位序列設(shè)X r MX）/GX）=PX）+RX）/GX）X r MX）-RX）/GX）=PX）在模2運算中，加法與減法等同，取FX）=RX就能使TX被GX整除CRC的檢錯率n能檢驗出所有長度小于等于r的錯誤n如果突發(fā)長度為r+1，當(dāng)且僅

12、當(dāng)差錯與GX相同時才被整除。根據(jù)突發(fā)錯誤長度的定義，其第1位和最后1位必須是1，因此與GX完全相同的概率為1/2r-1。n對于長度大于r+1的差錯，其錯判率為1/2 r。常用的多項式國際標(biāo)準(zhǔn)nCRC-12=X12+X11+X3+X2+X+1nCRC-16= X16 +X15 +X2 +1nCRC-CCITT= X16 +X15 +X5 +1nCRC-32=X32+X26+X23 +X22 +X16 +X12 +X11 +X10 +X8 +X7 +X5 +X4 +X2+X+14.3基本數(shù)據(jù)鏈路協(xié)議n4.3.1一種無限制的單工協(xié)議An Unrestricted Simplex Protocol）n

13、4.3.2停-等協(xié)議Stop-and-Wait Protocol）n4.3.3有噪音信道的停-等協(xié)議Stop-and-Wait Protocol for a Noisy Channel）4.3.1一種無限制的單工協(xié)議n完全理想的條件：數(shù)據(jù)單向傳輸，收發(fā)雙方的網(wǎng)絡(luò)層一直處于就緒狀態(tài)，處理時間可忽略不計，接收緩沖空間無限大，信道不會損壞或丟失幀。n發(fā)送端無限循環(huán)地重復(fù)三個動作：n從網(wǎng)絡(luò)層取分組。n構(gòu)造幀。n發(fā)出幀。n無需任何差錯控制和流量控制。n接收端也是無限循環(huán)地重復(fù)三個動作：n等待事件唯一的未損壞幀的到達發(fā)生。n幀到達后，從硬件緩沖中取出新到的幀。n將幀的數(shù)據(jù)部分傳給網(wǎng)絡(luò)層。n無需做其它任何處

14、理。4.3.2停-等協(xié)議n條件基本同協(xié)議1，只是接收緩沖只能存放一個幀且接收端需要一定的接收處理時間。n為了防止發(fā)送快于接收而造成數(shù)據(jù)丟失，發(fā)送端在發(fā)送一幀后必須停止發(fā)送，等待接收端發(fā)回的反饋確認(rèn)短幀；接收端在收到一個幀并發(fā)送網(wǎng)絡(luò)層后，需向發(fā)送端發(fā)一反饋確認(rèn)短幀不需包含任何信息，因為信道是無差錯的），表示可發(fā)新幀。n由于需要反饋，且?guī)陌l(fā)送和反饋是嚴(yán)格交替進行的，所以一般采用半雙工信道。有噪音信道所涉及的問題n進一步考慮實際的會出錯的信道，幀既可能損壞接收端可通過校驗檢查出錯誤），也可能完全丟失。n發(fā)送端仍通過接收端的反饋來決定怎么做。但由于幀會丟失，發(fā)送端可能收不到反饋的確認(rèn)幀，因此發(fā)送端必

15、須引入超時機制time out），即增加一個定時計數(shù)器，在一定時間后對沒有確認(rèn)的幀進行重發(fā)，也稱作ARQAutomatic Retransmit reQuest）。n時間值應(yīng)選擇稍大于兩倍端到端的信號傳輸時間和接收端的接收處理時間之和。n當(dāng)接收端的反饋確認(rèn)幀丟失時，必須通過為幀編制序號來解決重復(fù)幀的問題。n幀的序號位數(shù)應(yīng)盡量的短從而少占用幀頭的空間，在簡單停-等協(xié)議中只需1個比特位（“0”“1”，“1”“0”）即可。這是由于在本協(xié)議中，發(fā)送端每發(fā)送一個幀都是建立在此幀之前的所有幀都已正確發(fā)送的基礎(chǔ)上，只需區(qū)分相鄰的兩個連續(xù)幀即可避免重復(fù)的可能。4.3.3有噪音信道的停-等協(xié)議n收發(fā)雙方都需維護

16、各自的幀序號sequence number）。發(fā)送端維護的幀序號N(S)表示當(dāng)前所發(fā)幀的序號，接收端維護的幀序號N(R)表示接收端當(dāng)前所期待接收的幀序號。發(fā)送端從網(wǎng)絡(luò)層取得第一個分組進行組幀，將N(S)=0的序號放入幀頭中作為第一個幀，通過物理層的發(fā)送緩存器發(fā)送出去，并啟動定時計數(shù)器，然后停下來等待其響應(yīng)幀。n接收端收到一個幀后，對其序號和N(R)進行比較：n若不等，則將其作為重復(fù)幀而丟棄；n若相等則對其接收，經(jīng)校驗正確并送交網(wǎng)絡(luò)層后，將N(R)加1模2運算并放入確認(rèn)幀中反饋回發(fā)送端；若校驗出錯，則丟棄出錯的幀，保持N(R)的值不變并放入確認(rèn)幀中反饋回發(fā)送端。n發(fā)送端若在規(guī)定的時間內(nèi)沒有收到接

17、收端的反饋確認(rèn)幀超時），就認(rèn)為數(shù)據(jù)幀丟失，在保持N(S)不變的情況下重新發(fā)送緩沖器中的舊幀；若接收到確認(rèn)幀后，比較確認(rèn)幀中的序號和N(S)：n若相等，則保持N(S)不變，重新發(fā)送緩沖器中的舊幀；n若不等，則將確認(rèn)幀中的序號賦予N(S)，從網(wǎng)絡(luò)層獲取新的分組并組成新幀N(S)作為序號放入幀頭中交由物理層發(fā)送出去。n發(fā)送端每發(fā)送一幀，都會重新啟動定時計數(shù)器，然后停下來等待其響應(yīng)幀。停-等協(xié)議對信道利用率的影響n在時延大的信道如衛(wèi)星通信中，停-等協(xié)議的效率是很低的。n考慮兩個地面站通過衛(wèi)星通信，典型的傳輸時間約為270ms。假設(shè)一個幀的發(fā)送時間為20ms，則從發(fā)送站開始發(fā)送算起，經(jīng)20ms+ 270

18、ms=290ms，數(shù)據(jù)幀才能到達目的站。假設(shè)不考慮目的站的處理時間，且認(rèn)為確認(rèn)幀非常短，其發(fā)送時間可忽略不計，則又需270ms確認(rèn)幀才能被發(fā)送站收到。因此信道的利用率為：20ms/(290ms+270ms)=1/28，非常低。這是由于每發(fā)一個幀之前都必須等待前一個幀的確認(rèn)幀所造成的。n為了提高傳輸效率，可以設(shè)想讓發(fā)送站連續(xù)不斷地發(fā)送數(shù)據(jù)幀，當(dāng)發(fā)完第28個幀數(shù)據(jù)后，恰好第1幀的確認(rèn)幀到達，根據(jù)確認(rèn)可緊接著發(fā)第29幀或重發(fā)第1幀。以后，每過20ms發(fā)一個幀就有一個確認(rèn)幀到達，這樣信道的利用率就大大地提高了。n允許發(fā)送站連續(xù)發(fā)送多個幀而不需等待確認(rèn)的做法稱作管道化pipelining），屬于一種窗口

19、windows機制。4.4滑動窗口Slide Windows協(xié)議n滑動窗口協(xié)議是一種非?？煽?、適用于各種條件的通用流量控制協(xié)議，特別是在效率、復(fù)雜性及對緩沖區(qū)的需求等方面可作靈活調(diào)配。n主要的滑動窗口協(xié)議有出錯全部重發(fā)協(xié)議和選擇重發(fā)協(xié)議兩種。n實際上，有噪音信道的停-等協(xié)議就是滑動窗口協(xié)議的一個特例，將停-等協(xié)議中的幀序號從1位擴展到n位范圍為02n-1），收發(fā)雙方維護的序號也變?yōu)橐唤M序號表，分別稱作發(fā)送窗口sending window和接收窗口receiving window）。發(fā)送窗口n發(fā)送窗口就是發(fā)送端允許不等確認(rèn)而連續(xù)發(fā)送的幀的序號表。n允許連續(xù)發(fā)送的幀的數(shù)量稱為發(fā)送窗口尺寸，表示為W

20、。發(fā)送端必須有W個輸出緩沖區(qū)來存放W個數(shù)據(jù)幀的副本以備數(shù)據(jù)幀的重發(fā)。n當(dāng)發(fā)送端收到發(fā)送窗口下沿幀的肯定確認(rèn)時，將發(fā)送窗口整體向前滑動一個序號，并從輸出緩沖區(qū)中將相應(yīng)的數(shù)據(jù)幀副本刪除。ll+WWj發(fā)送方接收窗口n接收窗口是接收端允許接收的幀的序號表。n允許接收的幀的數(shù)量稱為接收窗口尺寸。同樣接收端也必須設(shè)置相應(yīng)數(shù)量的輸入緩沖區(qū)來支持接收窗口。n對接收端收到的幀的序號落在接收窗口外的幀被直接丟棄。只有落在接收窗口內(nèi)的幀才會被接收端進行校驗處理，若校驗正確：n當(dāng)接收的幀不是接收窗口下沿幀時，必須暫存在輸入緩沖區(qū)，不能交給網(wǎng)絡(luò)層。n當(dāng)接收到接收窗口下沿幀時，會將其連同后面連續(xù)的若干個檢驗過的正確幀按順

21、序交給網(wǎng)絡(luò)層，在發(fā)回確認(rèn)幀的同時將接收窗口向前滑動相應(yīng)的數(shù)量。ll+Wi接收方W滑動窗口示意圖012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567發(fā)送端發(fā)送端接收端接收端n幀的序號由3位組成07），發(fā)送窗口和接收窗口的尺寸都為3。停-等協(xié)議的窗口機制n幀的序號由1位組成01），發(fā)送窗口和接收窗口的尺寸都為1。010101010101010101010101發(fā)送端發(fā)送端接收端接收端數(shù)據(jù)的全雙工傳輸n在實際通信中，通常收發(fā)雙方都相互發(fā)送數(shù)據(jù)。n為了提高效率，可

22、以將確認(rèn)信息放在數(shù)據(jù)幀中作為一個控制字段連同數(shù)據(jù)一起發(fā)送給對方，這種方式稱為捎帶應(yīng)答piggybacking）。n當(dāng)一方收到對方的數(shù)據(jù)幀后：n若正好也有數(shù)據(jù)需發(fā)給對方，則立即可使用捎帶應(yīng)答。n若暫時沒有數(shù)據(jù)需發(fā)給對方或數(shù)據(jù)還未準(zhǔn)備好，則等待一定的時間，如果在該時間內(nèi)準(zhǔn)備好了數(shù)據(jù)，則可以使用捎帶應(yīng)答。如果未準(zhǔn)備好，為了防止對方等待時間過長而超時重發(fā)，必須立即發(fā)送一個單獨的確認(rèn)幀。n使用捎帶應(yīng)答就不可能對每一個幀都作確認(rèn)，可以用對某一個幀的確認(rèn)來代替對該幀之前的所有幀的確認(rèn)。出錯全部重發(fā)協(xié)議go-back-n）n出錯全部重發(fā)協(xié)議中，發(fā)送窗口的尺寸是大于1，而接收窗口的尺寸則等于1。n由于接收窗口的

23、尺寸為1，接收端只能按順序地接受數(shù)據(jù)幀，一旦某個幀出錯或丟失，只能簡單地丟棄該幀及其所有的后續(xù)幀因為發(fā)送窗口的尺寸是大于1的），不作任何確認(rèn)。發(fā)送端超時后需重發(fā)出錯或丟失的幀及其后續(xù)所有的幀。n發(fā)送端需要為每個待確認(rèn)的幀都各自設(shè)置一個定時計數(shù)器。n發(fā)送窗口的尺寸不能超過2n-1(這里的n為序號的編碼位數(shù))，否則會造成接收端無法分辨新、舊數(shù)據(jù)幀。n出錯全部重發(fā)協(xié)議只要求發(fā)送端保持一定數(shù)量的緩存來保存沒有確認(rèn)的數(shù)據(jù)幀，對接收端沒有緩存的要求。但在誤碼率高的情況下，會大大降低信道的利用率。選擇重發(fā)協(xié)議selective repeat）n選擇重發(fā)協(xié)議中，發(fā)送和接收窗口的尺寸都大于1。n由于接收窗口的尺

24、寸大于1，接收端可存儲壞幀之后的其它數(shù)據(jù)幀落在接收窗口），接收端對錯幀發(fā)否定確認(rèn)幀，因此發(fā)送端只需重發(fā)出錯的幀，而不需重發(fā)其后的所有后續(xù)幀。n接收端正確收到重發(fā)的幀后，可對其后連續(xù)的已接收的正確幀作一次總體確認(rèn)最大序號的確認(rèn)），并交送網(wǎng)絡(luò)層。大大提高了信道的利用率。n接收窗口的尺寸不能超過2n-1即序號范圍的1/2），否則可能造成幀的重疊。n發(fā)送窗口的尺寸一般和接收窗口的尺寸相同，發(fā)送端為每一個輸出緩存區(qū)設(shè)置一個定時計數(shù)器，定時器一旦超時，相應(yīng)輸出緩存區(qū)中的幀就被重發(fā)。出錯全部重發(fā)協(xié)議和選擇重發(fā)協(xié)議接收窗口的尺寸超過2n-1造成幀的重疊4.5面向位的協(xié)議HDLCn高級數(shù)據(jù)鏈路控制High-Level Data Link Control是由國際標(biāo)準(zhǔn)化組織制定的面向位的有序鏈路層協(xié)議。n是為非平衡的鏈路級操作而研制的，采用主從結(jié)構(gòu)，鏈路上一個主站控制多個從站，主站向從站發(fā)命令，從站向主站返回響應(yīng)。nHDLC中只有一個地址域，即從站的地址，在命令幀中，它是目的地址，在響應(yīng)幀中，它是源地址。HDLC的幀格式n幀標(biāo)志序列：01111110，作為起始和結(jié)束標(biāo)志，在數(shù)據(jù)位有5個連續(xù)的1出現(xiàn)時，就插入1個0位填充）n地址段：在命令幀中表示目的地址，在響應(yīng)幀中表示源地址，全1為廣播