軟件工程的計算機網絡CH3.1 數據鏈路層

1、數據鏈路層-1Outline3.1 數據鏈路層的基本概念3.2 三個基本問題 幀定界 透明傳輸 差錯檢測局域網廣域網主機 H1主機 H2路由器 R1路由器 R2路由器 R3電話網局域網主機主機 H1 向向 H2 發(fā)送數據發(fā)送數據n用戶主機H1通過電話線上網，中間經過三個路由器接入到遠程主機H2。n所經過的網絡可以是多種的，如電話網、局域網和廣域網。數據鏈路層的模型鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2從層次上來看數據的流動從層次上來看數據的流動n主機H1和H2都有完整的五層協議棧，但路由器的協議棧只

2、有下面三層。n數據進入路由器后先從物理層上到網絡層，在路由表中找到下一跳的地址后，再下到物理層轉發(fā)出去。n因此，數據從H1到H2需要在路徑中各節(jié)點的協議棧向上和向下流動多次。數據鏈路層的模型數據鏈路層的模型鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2僅從數據鏈路層觀察幀的流動僅從數據鏈路層觀察幀的流動n可以想象數據就是在數據鏈路層從左向右沿水平方向傳送。n通過這樣的鏈路：H1的鏈路層，R1的鏈路層，R2的鏈路層，R3的鏈路層，H2的鏈路層。n數據鏈路層的任務：把網絡層交下來的數據發(fā)送到鏈路上，以及把接收到

3、的幀中的數據取出來并交給網絡層。網絡層101000110數據鏈路結點A比特流IP數據報 數據鏈路層物理層幀裝入裝入101000110IP數據報幀結點B取出取出鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2 當兩個主機進行通信時，應用進程要把數據從應用層逐層往下傳，經過運輸層再到網絡層，組成IP數據報，再往下傳到數據鏈路層組成幀，然后在經物理層形成比特流進入通信網絡。兩個主機進行通信的過程鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2

4、R3H1H2 數據傳輸的路徑可能有許多路由器。每一個路由器的物理層在收到比特流后，先由數據鏈路層將比特流恢復成幀，再從幀中提取出IP數據報。路由器在轉發(fā)IP數據報時，又再把它封裝成另一個新的幀，然后交給物理層發(fā)送給下一個路由器。兩個主機進行通信的過程鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2 經過許多路由器的轉發(fā)，數據最后到達了目的主機的物理層。以后目的主機的數據鏈路層提取出IP數據報，再逐層向上傳，最后由應用層交給遠程的應用進程。兩個主機進行通信的過程n現在為了把主要精力放在數據鏈路層的協議上，采用一

5、個簡化的模型：在該模型中，不管在哪一段鏈路上通信，都看成是結點和結點的通信，而每個結點只有三層。網絡層101000110數據鏈路結點A比特流IP數據報 數據鏈路層物理層幀裝入裝入101000110IP數據報幀結點B取出取出數據鏈路層的主要功能：n結點A的數據鏈路層把網絡層交下來的IP數據報封裝成幀。n結點A把封裝好的幀發(fā)送給結點B的數據鏈路層。n若結點B的數據鏈路層收到的幀無差錯，則從收到的幀中提取出數據報上交給網絡層，否則丟棄這個幀。網絡層101000110數據鏈路結點A比特流IP數據報 數據鏈路層物理層幀裝入裝入101000110IP數據報幀結點B取出取出鏈路與數據鏈路的區(qū)別：n鏈路(li

6、nk) 是一條無源的點到點的物理線路段，中間沒有任何其他的交換結點。n一條鏈路只是一條路徑的一個組成部分。n數據鏈路(data link) 除了物理線路外，還必須有通信協議來控制這些數據的傳輸。若把實現這些協議的硬件和軟件加到鏈路上，就構成了數據鏈路。n現在最常用的方法是使用適配器（即網卡）來實現這些協議的硬件和軟件。n一般的適配器都包括了數據鏈路層和物理層這兩層的功能。 數據鏈路層像個數字管道 n常常在兩個對等的數據鏈路層之間畫出一個數字管道，而在這條數字管道上傳輸的數據單位是幀。n早期的數據通信協議曾叫作通信規(guī)程(procedure)。因此在數據鏈路層，規(guī)程和協議是同義語。 結點結點幀幀數

7、據鏈路層的七個主要功能n鏈路管理：當網絡中的兩個結點要進行通信時，數據的發(fā)送方必須確認接收方是否已經處在準備接收的狀態(tài)。n通信的雙方必須要交換一些必要的信息，即必須先建立一條數據鏈路。n在傳輸數據時要維持數據鏈路，而在通信完畢時要釋放數據鏈路。n數據鏈路的建立、維持和釋放就叫做鏈路管理。n幀定界：在數據鏈路層，數據的傳送單位是幀。數據一幀一幀地傳送，就可以在出現差錯時，將有差錯的幀在重傳一次，而避免了將全部數據都進行重傳。n幀定界是指接收方應當能從收到的比特流中準確地區(qū)分出一幀的開始和結束在什么地方。n幀定界也可以稱為幀同步。n流量控制：發(fā)送方發(fā)送數據的速率必須使接收方來得及接收。當接收方來不

8、及接收時，就必須及時控制發(fā)送方發(fā)送數據的速率。這種功能稱作流量控制。n差錯控制：在計算機通信中，一般都要求有極低的比特差錯率。為此，廣泛地采用了編碼技術。n編碼技術有兩大類。一類是前向糾錯，即接收方收到有差錯的數據幀時，能夠自動將差錯改正過來。這種方法的開銷較大，不適合計算機通信。另一類是差錯檢測，即接收方可以檢測出收到的幀有差錯（但并不知道是哪幾個比特錯了）。n當檢測出有差錯的幀時就立即將它丟棄，但接下去有兩種選擇：n方法一不進行任何處理（由高層進行處理），n方法二則是由數據鏈路層負責重傳丟棄的幀。n將數據和控制信息區(qū)分開：在許多情況下，數據和控制信息處于同一幀中。因此一定要有相應的措施使接

9、收方能夠將它們區(qū)分開。n尋址：必須保證每一幀都能送到正確的目的站。接收方也應知道發(fā)送方的地址。n透明傳輸：不管所傳數據是什么樣的比特組合，都應當能夠在鏈路上傳送。當所傳數據中的比特組合恰巧出現了與某一個控制信息完全一樣時，必須有可靠的措施，使接收方不會將這種比特組合的數據誤認為是某種控制信息。三個基本問題 (1) 幀定界：確定幀開始和結束的位置。(2) 透明傳輸：數據鏈路層協議不能禁止傳輸某種特殊的比特組合。(3) 差錯控制 ：當接收端檢測出有差錯的幀時，根據協議的不同，可采用不同的處理方法。1. 幀定界n幀定界就是確定幀的界限。在發(fā)送幀時，發(fā)送端的數據鏈路層在幀的前后都各加入事先商定好的標記

10、，使得接收端能識別幀的開始和結束，以及幀中數據部分的準確位置。 幀結束幀首部IP 數據報幀的數據部分幀尾部 MTU數據鏈路層的幀長開始發(fā)送幀開始1.幀定界n網絡層的IP數據報傳送到數據鏈路層就成為幀的數據部分。n在幀的數據部分的前面和后面分別添加上首部和尾部，構成了一個完整的幀。 幀結束幀首部IP 數據報幀的數據部分幀尾部 MTU數據鏈路層的幀長開始發(fā)送幀開始1.幀定界n幀長就等于數據部分的長度加上幀首部和尾部的長度。n首部和尾部主要作用是進行幀定界，但還可包括一些其他控制信息。 幀結束幀首部IP 數據報幀的數據部分幀尾部 MTU數據鏈路層的幀長開始發(fā)送幀開始1.幀定界n在發(fā)送數據幀時，是從幀

11、首部開始發(fā)送。數據鏈路層的協議需明確規(guī)定幀首部和尾部的格式n協議還規(guī)定了幀的數據部分的長度上限最大傳送單元MTU。幀結束幀首部IP 數據報幀的數據部分幀尾部 MTU數據鏈路層的幀長開始發(fā)送幀開始用控制字符進行幀定界SOH裝在幀中的數據部分幀幀開始符幀結束符發(fā)送在前EOTn當數據是由可打印的ASCII碼組成的文本文件時，幀定界可使用幀定界字符。n控制字符SOH放在一幀的最前面，表示幀的首部開始；另一個控制字符EOT表示幀的結束。n注意：字符SOH和字符EOT的十六進制編碼分別是01和04，而不是由三個字符組成的。用控制字符進行幀定界 對幀進行定界是非常必要的：n當物理層采用異步傳送時(一次只傳送

12、一個字符)，接收端物理層是斷斷續(xù)續(xù)的接收到單個的字符，而不是一次就收到一個完整的幀。n利用幀定界的控制字符就可以準確界定幀開始和結束的位置。用控制字符進行幀定界n當物理層采用同步傳送時，發(fā)送端連續(xù)地發(fā)送數據幀。接收端要利用幀定界的控制字符從連續(xù)的比特流中找出幀開始和結束的位置。n假定發(fā)送端在沒有發(fā)送完一個幀時突然出故障，但隨后很快恢復正常，于是重新發(fā)送剛才未發(fā)完的幀(從頭開始發(fā)送)。由于使用了幀定界字符，在接收端就知道前面收到的數據是不完整的幀(只有SOH沒有EOT)，必須丟棄。而后面收到的數據有明確的幀定界符(SOH和EOT)，因此這是個完整的幀，應當收下。2.透明傳輸n由于幀的開始和結束的

13、標記是使用專門指明的控制字符，因此所傳輸的數據中任何一個字符一定不允許和用作幀定界的控制字符一樣，否則就會出現幀定界的錯誤。n 當傳送的幀是用ASCII文本文件組成的時，其數據部分顯然不會出現像SOH和EOT這樣的幀定界字符。n所以鍵盤上輸入的任何字符都可放在這樣的幀中傳輸過去，這樣的傳輸就是透明傳輸。SOHEOT出現了“EOT”(04)16被接收端當作無效幀而丟棄被接收端誤認為是一個幀數據部分EOT完整的幀發(fā)送在前n當數據部分是非ASCII碼的文本文件時（如二進制代碼的計算機程序或圖像等），如果數據中的某個字節(jié)的二進制代碼恰好和SOH或EOT一樣，數據鏈路層就會錯誤地“找到幀的邊界”，把部分

14、幀收下（誤認為是個完整的幀），而把剩下的那部分丟棄（這部分找不到幀定界符SOH）。解決透明傳輸問題n發(fā)送端的數據鏈路層在數據中出現控制字符“SOH”或“EOT”的前面插入一個轉義字符“ESC”(其十六進制編碼是 1B)。將其轉換為另一個字符，而這個字符不會被錯誤的解釋為控制字符。這種方法成為字節(jié)填充(byte stuffing)。n接收端的數據鏈路層在將數據上交網絡層之前刪除插入的轉義字符。n如果轉義字符也出現數據當中，那么應在轉義字符前面插入一個轉義字符。當接收端收到連續(xù)的兩個轉義字符時，就刪除其中前面的一個。 SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原

15、始數據EOTEOT經過字節(jié)填充后發(fā)送的數據字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開始符幀結束符用字節(jié)填充法解決透明傳輸的問題SOH3.差錯檢測n現實的通信鏈路不理想，比特在傳輸過程中可能出現差錯：1變成0或0變成1.n誤碼率BER 在一定時間內，傳輸錯誤的比特占所傳輸的比特總數的比率。n例：誤碼率為10-10時，表示平均傳送1010個比特就會出現一個比特的差錯。n誤碼率與信噪比成反比例關系。n為保證數據傳輸的可靠性，在計算機網絡傳輸數據時，都必須采用各種差錯檢測措施。循環(huán)冗余檢驗n在數據鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗 CRC 的檢錯技術。n假設待傳送的數據 M = 101001（

16、共k bit）。我們在M的后面再添加供差錯檢測用的 n bit 冗余碼一起發(fā)送（即一共發(fā)送k+n個比特）。 n bit冗余碼的求解方法：n用二進制的模 2 運算進行 2n 乘 M 的運算，這相當于在 M 后面添加 n 個 0。n得到的 (k + n) bit 的數2n M除以事先選定好的長度為 (n + 1) bit 的數 P，得出商是 Q 而余數是 R，其中余數 R 比除數 P 至少要少1 個比特。 n余數R就是添加在數據后面的冗余碼。模 2 乘n模2乘和10進制一樣，只是相加時用模2加，無進位。比如，n 1011 101： 1011 100 (22) 1011 1011 * 101 * 1

17、00 - - 1011 0000 0000 0000 1011 1011 - - 100111 101100 n設 n = 3, P = 1101，模 2 運算 2nM /P的結果是：商 Q = 110101， 余數R = 001。n將余數 R 作為冗余碼添加在數據 M = 101001 的后面發(fā)送出去，即發(fā)送的數據是101001001，或 2nM + R。 模 2 加減n 模2運算：就是除以2后取余數，結果就只有0或1。n模2加：0+0=0, 0+1=1, 1+0=1, 1+1=0 （無進位，借位）相當于異或運算。n模2減：0-0=0, 0-1=1, 1-0=1, 1-1=0 （無進位，借位

18、）n模2除與算術除法類似，但每一位除（減）的結果不影響其它位（不向上一位借位，實際上就是異或）。然后再移位做下一位的模2減。步驟如下： 用除數對被除數最高幾位做模2減，沒有借位。 除數右移一位，若余數最高位為1，商為1，并對余數做模2減。若余數最高位為0，商為0，除數繼續(xù)右移一位。一直做到余數的位數小于除數時，該余數就是最終余數。 110101 Q 商 除數 P 1101 101001000 2nM 被除數 1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R 余數已知：待發(fā)送的數據M=101001,冗余碼的長度n=3,事先商定的除數P=1101，求得余數R？幀檢驗序列 FCSn在數據后面添加上的冗余碼稱為幀檢驗序列 FCS (Frame Check Sequence)。n循環(huán)冗余檢驗 CRC 和幀檢驗序列 FCS并不等同。nCRC 是一種常用的檢錯方法，而 FCS 是添加在數據后面的冗余碼。nFCS 可以用 CRC 這種方法得出，但 CRC 并非用來獲得 FCS 的惟一方法。檢測出差錯 n在接收端對接收到的幀進行CRC檢驗。把收到的幀除以同樣的P（模2運算），得出余數R。n只要得出的余