【大學】本科網絡課程講義：數(shù)據(jù)鏈路層(,50頁)

1、.1Chapter 4 數(shù)據(jù)鏈路層n4.4滑動窗口（Slide Windows）協(xié)議n4.6 Internet中的數(shù)據(jù)鏈路層.2n向網絡層提供良好的服務接口n將物理層的比特流編成幀n差錯檢測.3n無確認、無連接的服務n源端可以不需要建立連接就向目的端發(fā)送獨立的數(shù)據(jù)幀，而目的端也不需要對收到的幀進行確認。n有確認、無連接的服務n源端可以不需要建立連接就向目的端發(fā)送獨立的數(shù)據(jù)幀，但目的端需要對收到的幀進行確認。n面向連接的服務n源端與目的端在通信前要先建立連接，然后在此連接上互相傳輸數(shù)據(jù)幀，每一個幀都被編號，數(shù)據(jù)鏈路層保證傳送的幀被對方收到，且只收到一次，雙方通信完畢后拆除連接。.4用OSI服務原

2、語表示服務接口請求證實響應指示網絡層數(shù)據(jù)鏈路層物理層時間發(fā)送方網絡層接收方網絡層服務提供者數(shù)據(jù)鏈路層請求證實響應指示.54.1.2成幀(framing)n每一個幀的頭上描述幀的長度識別或表示一個幀的起始和結尾5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 7第一幀第二幀第三幀缺點：幀頭出錯不光影響本數(shù)據(jù)幀，還影響后續(xù)的幀。.64.1.2成幀(framing)n在幀的起始和結尾用特殊的字符標志例如：用ASCII字符DLE STX表示幀的起始，DLE ETX表示結尾。識別或表示一個幀的起始和結尾在發(fā)送端檢查數(shù)據(jù)中是否有DLE字樣，如果有的話，就在它前面插入DLE，到接收端的鏈路

3、層再將兩個或兩個以上的DLE，去掉一個DLE還原。.7.84.1.2成幀(framing)n用特殊的位序列表示幀的起始和結尾例如，用01111110表示幀的起始和結尾識別或表示一個幀的起始和結尾為了避免起始、結尾標志與幀中的數(shù)據(jù)混淆，發(fā)送端的數(shù)據(jù)鏈路層在檢測到數(shù)據(jù)比特流中有連續(xù)5個1出現(xiàn)時，就在其后加一個0，接收端的數(shù)據(jù)鏈路層在將5個1后面的0取走還原。.9.104.1.2成幀(framing)n在物理層用1.5或2個物理位表示一個數(shù)據(jù)位來表示幀的起始與結尾。例如在物理層編碼中，用 表示1，用 表示0則可用 ， 作為起始、結尾標志。識別或表示一個幀的起始和結尾.11n在有確認的服務中，接收方需

4、要對收到的數(shù)據(jù)幀進行確認，通常以返回特別控制幀來告訴發(fā)送方收到的數(shù)據(jù)有沒有出錯，也可以通過返回的數(shù)據(jù)幀中的某些位來捎帶地進行確認。n如果發(fā)送的數(shù)據(jù)丟失，那么接收端是不可能進行確認的，怎么辦呢？n在發(fā)送端引入計數(shù)器，進行超時重發(fā)。為了避免相同的幀收到多次，需要對幀進行編號。.12n當發(fā)送端的發(fā)送速度大于接收端的接收速度，或發(fā)送端所在的網絡傳輸速率大于接收端所在的網絡傳輸速率時，就需要流量控制。n窗口機制n在任意時刻，發(fā)送方發(fā)出n幀，其中有l(wèi)幀已得到確認。而同一時刻，接收方收到并應答了m幀，顯然l=m = n，等待確認的幀的數(shù)目不允許超過W，即n-l =W，該W就是窗口。ll+WWn發(fā)送方mm+W

5、接收方.13n信號在任何信道上傳輸都存在著傳輸差錯，這些差錯由多種物理現(xiàn)象引起，解決差錯問題的方法有兩種：n一種是在要發(fā)送的數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯，但不知道是哪里出錯，這種編碼方法叫差錯檢測碼，或簡稱檢錯碼。n另一種是在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯的位，這種編碼方法叫差錯校正碼，或簡稱糾錯碼。.14n定義：一幀由m個數(shù)據(jù)位（即報文）和r個冗余位（即校驗位）組成，設總長度為n（n=m+r)，此長度為n的單元常稱為n位碼字。n定義：兩個碼字不同的位的數(shù)目稱為海明距離例如，10001001 與10110001它們的海明距離為3。n對于n位碼字的集合

6、，只有2m個碼字是有效的，在任意兩個有效碼字間找出具有最小海明距離的兩個碼字，該海明距離便定義為全部碼字的海明距離。.15n一種編碼的檢錯和糾錯能力取決于編碼后碼字的海明距離的大小。n為了檢測出d個比特的錯，需要使用距離為d+1的編碼。例如：數(shù)據(jù)后加奇偶校驗位，編碼后的海明距離為2，能檢測1比特錯。n為了糾正d個比特的錯，必須用距離為2d+1的編碼。例如有4個有效碼字：它們是0000000000，0000011111，1111100000，1111111111，海明距離為5，能糾正2比特錯。.16糾正單比特錯的校驗位下界n設計一種編碼，它有m個信息位和r個校驗位，當r滿足什么條件時，能糾正所有

7、單比特錯？ 對2m個有效碼字的任何一個而言，有n個與該碼字距離為1的無效碼字，所以2m個有效碼字每一個都對應有n+1個各不相同的位圖，n位碼字的總的位圖是2n個。（n+1）2m=2n，n=m+r代入（m+r+1）2m=n+1 糾正單比特誤碼的校驗位下界.17海明編碼n海明在1950年提出一種編碼來糾正單比特錯的編碼。該編碼是將碼字內的位從左到右依次編號，編號為2的冪的位是校驗位（如第1，2，4，8），其余為信息位。n每個校驗位的取值應使得包括自己在內的一些集合服從規(guī)定的奇偶性。n集合的選取如下：n對編號為K的信息位來說，K可以分解成2的冪的和，如編號為11，11=1+2+8，即第11位由1，2

8、，8校驗位校驗，它同時屬于1，2，8所在的集合。.18海明編碼舉例上例中，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位出錯，.19n在實際通信中使用糾錯碼好還是檢錯碼好呢？n例題：假設一個信道誤碼率是10-6，且出錯是孤立產生的（即只有單比特錯），數(shù)據(jù)塊長度為1000比特，如果采用糾錯編碼，需要10個校驗位

9、（2101011），傳送1M數(shù)據(jù)需要10000個校驗位；如果采用檢錯編碼，每個數(shù)據(jù)塊只需一個奇偶校驗位，傳送1M數(shù)據(jù)只需1000個校驗位和一個重傳的數(shù)據(jù)1001位，共需要2001比特。n在多數(shù)通信中采用檢錯編碼，但在單工信道中需要糾錯編碼。.20改進的奇偶校驗n對數(shù)據(jù)位組成一個L位寬，K位高的長方形距陣來發(fā)送，然后對每一列單獨計算奇偶位，并附在最后一行作為冗余位。X X X X X XXX X X X X XXX 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.假設L列中

10、任意一列檢測出錯的概率為1/2，那么，整個數(shù)據(jù)塊的錯判率為（1/2）L 。該方法用在ICMP報頭檢驗中。.21多項式編碼（循環(huán)冗余碼CRC）nCRC（Cyclic Redundancy Check)nCRC編碼的一般操作：給定一個m比特的幀或報文，發(fā)送方生成r比特的序列（也稱為幀檢驗序列FCS，F(xiàn)rame Check Series），形成（m+r）的碼字，該碼字能被某個事先確定的數(shù)整除。接收方用相同的數(shù)去除收到的幀，如果無余數(shù)，則認為數(shù)據(jù)幀無差錯。.22CRC也稱多項式編碼n多項式表示：即將k比特的數(shù)據(jù)用k項多項式表示，它的各項為X k-1X0，它的系數(shù)為數(shù)據(jù)中對應位的0或1。n例如：1100

11、01可表示成X5+X4+1.23多項式編碼的推導設數(shù)據(jù)幀多項式表示為M（X） m位序列 事先約定的除數(shù)為G（X） r+1位序列 幀檢驗序列FCS為F（X） r位序列加了檢驗序列的幀為T（X）=X r M（X）+F（X） m+r位序列設X r M（X）/G（X）=P（X）+R（X）/G（X）X r M（X）-R（X）/G（X）=P（X）在模2運算中，加法與減法等同，取F（X）=R（X）就能使T（X）被G（X）整除.24.25CRC的檢錯率n能檢驗出所有長度小于等于r的錯誤n如果突發(fā)長度為r+1，當且僅當差錯與G（X）相同時才被整除。根據(jù)突發(fā)錯誤長度的定義，其第1位和最后1位必須是1，因此與G（X

12、）完全相同的概率為（1/2）r-1。n對于長度大于r+1的差錯，其錯判率為1/2 r。.26常用的多項式國際標準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+1.27n4.3.1一種無限制的單工協(xié)議（An Unrestricted Simplex Protocol）n4.3.2停-等協(xié)議（Stop-and-Wait Protocol）n4.3.3有噪音信道的

13、停-等協(xié)議（Stop-and-Wait Protocol for a Noisy Channel）.28n完全理想的條件：數(shù)據(jù)單向傳輸，收發(fā)雙方的網絡層一直處于就緒狀態(tài)，處理時間可忽略不計，接收緩沖空間無限大，信道不會損壞或丟失幀。n發(fā)送端無限循環(huán)地重復三個動作：n從網絡層取分組。n構造幀。n發(fā)出幀。無需任何差錯控制和流量控制。n接收端也是無限循環(huán)地重復三個動作：n等待事件（唯一的未損壞幀的到達）發(fā)生。n幀到達后，從硬件緩沖中取出新到的幀。n將幀的數(shù)據(jù)部分傳給網絡層。無需做其它任何處理。.29n條件基本同協(xié)議1，只是接收緩沖只能存放一個幀且接收端需要一定的接收處理時間。n為了防止發(fā)送快于接收而

14、造成數(shù)據(jù)丟失，發(fā)送端在發(fā)送一幀后必須停止發(fā)送，等待接收端發(fā)回的反饋確認短幀；接收端在收到一個幀并發(fā)送網絡層后，需向發(fā)送端發(fā)一反饋確認短幀（不需包含任何信息，因為信道是無差錯的），表示可發(fā)新幀。n由于需要反饋，且?guī)陌l(fā)送和反饋是嚴格交替進行的，所以一般采用半雙工信道。.30有噪音信道所涉及的問題n進一步考慮實際的會出錯的信道，幀既可能損壞（接收端可通過校驗檢查出錯誤），也可能完全丟失。n發(fā)送端仍通過接收端的反饋來決定怎么做。但由于幀會丟失，發(fā)送端可能收不到反饋的確認幀，因此發(fā)送端必須引入超時機制（time out），即增加一個定時計數(shù)器，在一定時間后對沒有確認的幀進行重發(fā)，也稱作ARQ（Auto

15、matic Retransmit reQuest）。n時間值應選擇稍大于兩倍端到端的信號傳輸時間和接收端的接收處理時間之和。n當接收端的反饋確認幀丟失時，必須通過為幀編制序號來解決重復幀的問題。n幀的序號位數(shù)應盡量的短從而少占用幀頭的空間，在簡單停-等協(xié)議中只需1個比特位（“0”“1”，“1”“0”）即可。這是由于在本協(xié)議中，發(fā)送端每發(fā)送一個幀都是建立在此幀之前的所有幀都已正確發(fā)送的基礎上，只需區(qū)分相鄰的兩個連續(xù)幀即可避免重復的可能。.31n收發(fā)雙方都需維護各自的幀序號（sequence number）。發(fā)送端維護的幀序號N(S)表示當前所發(fā)幀的序號，接收端維護的幀序號N(R)表示接收端當前所

16、期待接收的幀序號。發(fā)送端從網絡層取得第一個分組進行組幀，將N(S)=0的序號放入幀頭中作為第一個幀，通過物理層的發(fā)送緩存器發(fā)送出去，并啟動定時計數(shù)器，然后停下來等待其響應幀。n接收端收到一個幀后，對其序號和N(R)進行比較：n若不等，則將其作為重復幀而丟棄；n若相等則對其接收，經校驗正確并送交網絡層后，將N(R)加1（模2運算）并放入確認幀中反饋回發(fā)送端；若校驗出錯，則丟棄出錯的幀，保持N(R)的值不變并放入確認幀中反饋回發(fā)送端。n發(fā)送端若在規(guī)定的時間內沒有收到接收端的反饋確認幀（超時），就認為數(shù)據(jù)幀丟失，在保持N(S)不變的情況下重新發(fā)送緩沖器中的（舊）幀；若接收到確認幀后，比較確認幀中的序

17、號和N(S)：n若相等，則保持N(S)不變，重新發(fā)送緩沖器中的（舊）幀；n若不等，則將確認幀中的序號賦予N(S)，從網絡層獲取新的分組并組成新幀（N(S)作為序號放入幀頭中）交由物理層發(fā)送出去。發(fā)送端每發(fā)送一幀，都會重新啟動定時計數(shù)器，然后停下來等待其響應幀。.32停-等協(xié)議對信道利用率的影響n在時延大的信道（如衛(wèi)星通信）中，停-等協(xié)議的效率是很低的。n考慮兩個地面站通過衛(wèi)星通信，典型的傳輸時間約為270ms。假設一個幀的發(fā)送時間為20ms，則從發(fā)送站開始發(fā)送算起，經20ms+ 270ms=290ms，數(shù)據(jù)幀才能到達目的站。假設不考慮目的站的處理時間，且認為確認幀非常短，其發(fā)送時間可忽略不計，

18、則又需270ms確認幀才能被發(fā)送站收到。因此信道的利用率為：20ms/(290ms+270ms)=1/28，非常低。這是由于每發(fā)一個幀之前都必須等待前一個幀的確認幀所造成的。n為了提高傳輸效率，可以設想讓發(fā)送站連續(xù)不斷地發(fā)送數(shù)據(jù)幀，當發(fā)完第28個幀數(shù)據(jù)后，恰好第1幀的確認幀到達，根據(jù)確認可緊接著發(fā)第29幀或重發(fā)第1幀。以后，每過20ms（發(fā)一個幀）就有一個確認幀到達，這樣信道的利用率就大大地提高了。n允許發(fā)送站連續(xù)發(fā)送多個幀而不需等待確認的做法稱作管道化（pipelining），屬于一種窗口（windows）機制。.334.4滑動窗口（Slide Windows）協(xié)議n滑動窗口協(xié)議是一種非?？?/p>

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

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

21、i接收方W.36滑動窗口示意圖012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567發(fā)送端發(fā)送端接收端接收端n幀的序號由3位組成（07），發(fā)送窗口和接收窗口的尺寸都為3。.37停-等協(xié)議的窗口機制n幀的序號由1位組成（01），發(fā)送窗口和接收窗口的尺寸都為1。010101010101010101010101發(fā)送端發(fā)送端接收端接收端.38數(shù)據(jù)的全雙工傳輸n在實際通信中，通常收發(fā)雙方都相互發(fā)送數(shù)據(jù)。n為了提高效率，可以將確認信息放在數(shù)據(jù)幀中作為一個控制字段連同數(shù)據(jù)

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

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

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