1、 數據鏈路層 第三章主要內容容3.1數數據鏈鏈路層設設計要點點3.2錯錯誤檢檢測和糾糾正3.3基基本數數據鏈路路層協議議3.4滑滑窗協協議3.5協協議驗驗證3.6數數據鏈鏈路層協協議示例例3.1數數據鏈鏈路層的的設計要要點為網絡層層提供的的服務成幀差錯控制制流量控制制鏈路層基基本功能能向網絡層層提供一一個服務務接口處理傳輸輸錯誤調節數據據流（流流控）分組與幀幀之間的的關系虛擬通信信和實際際通信(a)虛擬通信信.(b)實際通信信數據鏈路路層提供供的服務務無確認的的無連接接服務用于低誤誤碼率鏈鏈路或對對誤碼不不敏感的的業務. (fiber,utp,real-time)有確認的的無連接接服務用于高誤

2、誤碼率鏈鏈路(Wireless)有確認的的面向連連接的服服務保證每個個幀真正正接收到到且只接接收一次次。為網絡層層進程提提供一個個可靠的的位流。例子數據鏈路路協議的的位置DLL將原始碼碼流分解解為離散散的單元元，該單單元稱為為幀。那么接接收端如如何檢測測幀的邊邊界呢？或者說說接收端端如何界界定幀的的開始和和結束呢呢？討論論4種方法：字符計數數法含字節填填充的分分界符法法含位填充充的分界界標志法法編碼違例例成幀字符計數數法一個字符符流(a)無差錯.(b)有一個差差錯字符填充充(a)有標志字字節作為為分界的的幀.(b)字節填充充前后的的4個字節序序列例子子比特填充充Bit填充，標記01111110

3、(a)原始數據據.(b)線路上的的數據.(c)刪除填充充后存儲儲在接收收方存儲儲器中的的數據編碼違例例適用于“物理介介質上的的編碼方方法中包包含冗余余信息”的網絡。例如有有些LAN用2個物理位位來編碼碼1位數據。“1”位是“高高-低”電平對，“0”位是“低低-高”電平對。而“高高高”“低低”電平對不不用于數數據，則則可用于于幀定界界。優點是沒沒有額外外帶寬開開銷為了保證證所有的的幀最終終傳送到到（有可可能順序序的）目目的端，需要三三個部件件。Acknowledgments,Timers,SequenceNumbersAcknowledgments:當接收端端正確接接收一個個幀，它它會向發發送端

4、返返回一個個ACK幀用于指指示發端端該幀已已正確接接收。在某些系系統，如如果接收收的幀不不正確，接收端端會發端端返回一一個NACK（NegativeACK）用于指指示該幀幀沒有正正確接收收.提示發端端不用等等待定時時器超時時就立即即發送（重傳）一個幀幀.錯誤控制制Timers:如果沒有有定時器器，當幀幀丟失或或者ACK/NACK丟失，會會出現什什么情況況？定時器怎怎么工作作呢？當當發送一一個幀的的時候，發端開開啟一個個定時器器，當在在約定的的時間內內，發端端接收到到ACK/NACK，則立即即發送（重發）一個幀幀，且重重置定時時器，否否則當定定時超時時時，重重發該幀幀。SequenceNumbe

5、rs:主要解決決接收端端接收到到重復幀幀的問題題.為了避免免接收重重復幀的的問題，給發送送的幀分分配序列列號，這這樣接收收端就能能夠區分分原始幀幀和重傳傳幀。.ErrorC流控流控主要要是處理理發端與與接收端端之間速速率匹配配的問題題。通常常，流控控是個動動態的過過程，取取決于負負載強度度、接收收端緩存存大小等等，常用用的方法法：基于反饋饋的流控控制基于速率率的流控控制（從從來沒有有用于DDL）3.2錯誤檢測測和糾正正糾錯碼檢錯碼錯誤數據通信信中，鏈鏈路噪聲聲無處不不在，并并且研究究發現，鏈路噪噪聲引起起的比特特錯誤通通常是突發性的，而不不是獨立立的，單單比特錯錯誤，例例如：閃閃電會引引起短暫

6、暫的突發發比特錯錯誤。糾錯碼檢測和糾糾正數據據中的錯錯誤冗余（redundancy）-在數據中中加入附附加的信信息。兩種策略略：檢錯碼:包含足夠夠的冗余余比特檢檢錯，然然后使用用NACK告知發端端重傳。糾錯碼:包含足夠夠的冗余余比特檢檢測和糾糾正錯誤誤。海明距離離給定兩個個碼子，對其進進行異或或運算，然后計計算出異異或結果果中1的個數，兩個碼碼子中不不相同的的位的個個數稱為為海明距距離.它的意義義在于：如果兩兩個碼子子的海明明距離為為d，則需要要d個1位錯誤才才能將一一個碼子子轉變成成另一個個碼子。海明距離離通常，所所有2m種可能的的數據報報文都是是合法的的，但是是并非所所有的2n（n =m+

7、r；m為數據位位，r為冗余位位）種碼碼子都被被用到。給定計計算校驗驗位的算算法后，可以構構造合法法碼子列列表，并并且可以以從該表表中找到到海明距距離最小小的兩個個碼子，此距離離是整個個編碼方方案的海海明距離離。為了檢測測d個錯誤，需要一一個距離離為d +1的編碼方方案為了糾正正t個錯誤，需要一一個距離離為2t+ 1的編碼方方案奇偶位保證碼子子中“1”位的數目目是偶數數（或者者奇數）。.1000000(1)1111101(0)奇偶位的的海明距距離為2，因此它它可以檢檢測單比比特錯誤誤，但是是不能糾糾錯考慮以下下的例子子，4個有效碼碼子的編編碼：0000000000, 0000011111,111

8、1100000,and1111111111.編碼距離離為5,可以糾正正2個錯誤。糾錯設計一種種編碼方方案，每每個碼子子有m個報文位位和r個校驗位位，并且且能夠糾糾正所有有的單個個錯誤。對于2m合法報文文，任一一個報文文都對應應有n個非法的的碼子，它們與與該報文文的距離離為1。因此每每個合法法的報文文都要求求n+1個位模式式供他使使用。由由于總共共有2n個位模式式，所以以有( n+1 )*2m2n,利用n =m+ r,有：( m+r +1)檢錯碼糾錯碼代代價很大大（計算算量和帶帶寬），因此用用在無線線通信較較為合適適，但是是在銅線線或者光光纜，錯錯誤檢測測和重傳傳機制往往往更加加有效。例如，若若

9、誤碼是是獨立的的，誤碼碼率為10-6。則對于于1000bit的數據塊塊，需要要10個校驗位位糾正1個單bit錯誤，1Mbit的需要10Kbit，顯然如如果僅僅僅檢測錯錯誤，每每個數據據塊1個奇偶位位就足夠夠了，每每一千個個數據塊塊額外傳傳輸一個個塊，因因此開銷銷小，利利用檢錯錯/重傳機制制，則1Mbit只需2001位，相比比之下，海明碼碼需要10000位。最廣泛使使用的檢檢錯碼是是多項式式編碼，也稱CRC。CyclicRedundancyCheck基本思想想：將位位串看成成系數為為0或1的多項式式。多項式的的算術運運算以2為模完成成，加減減法等同同于異或或，除法法為長除除運算。生成多項項式G(

10、x)：事先約約定的，最低位位，最高高位必須須是1。校驗和：添加到到幀序列列多項式式中，用用于檢測測傳輸是是否有錯錯誤。CyclicRedundancyCheck校驗和的的計算方方法：(1)假設G(x)的階為r。在幀的的低位端端加上r個0位，所以以該幀現現在包含含m+r位。對應應的多項項式為xrM(x)。(2)利用模2除法，用用對應于于G(x)的位串去去除xrM(x)的位串。(3)利用模2減法，從從對應于于xrM(x)的位串中中減去余余數，結結果就是是將被傳傳輸的帶帶校驗和和的幀，記為：T(x)。 CyclicRedundancyCheck校驗和的的計算過過程CyclicRedundancyCh

11、eck分析：1.所有的錯錯誤都能能檢測出出嗎？錯誤多項項式E(x)能被G(x)除盡，則則這類錯錯誤無法法被檢測測。2.所有的一一位錯誤誤都將被被檢測到到。低階的多多項式可可以保護護長的幀幀（K=i j,兩個獨立立的一位位錯誤）奇數項多多項式不不可能被被x+1除盡(奇數個位位發生錯錯誤)。帶r個校驗位位的多項項式編碼碼可以檢檢測到所所有長度度小于等等于r的突發性性錯誤。CyclicRedundancyCheck通常用到到的3種CRC生成多項項式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+ x22

12、+x16+x12+x11+x10+x8+x7+x5+x4+ x2+x1+1(usedinEthernet)盡管復雜雜，可以以用硬件件構造出出來3.3基基本數數據鏈路路協議一個無限限制的單單工協議議一個單工工的停等協議有噪聲信信道的單單工協議議基本數據據鏈路協協議幾個假設設：物理層、數據鏈鏈路層和和網絡層層都是獨獨立的進進程，它它們通過過報文來來相互通通信。可靠的、面向連連接的服服務機器不會會崩潰協議定義義Continued協議中需需要用到到的一些些定義。這些定定義包含含在頭文文件protocol.h中協議定義義(ctd.)協議中需需要用到到的一些些定義。這些定定義包含含在頭文文件protoco

13、l.h中無限制的的單工協協議假設條件件:數據單向向傳輸物理信道道無誤碼碼，即無無幀損壞壞或丟失失發/接收端緩緩存無限限大發端/收端的網網絡層總總是處于于準備就就緒狀態態無限制的的單工工協議一個單工工的停/等協議假設:不再假設設收端能能夠無限限快速的的處理到到來的數數據.基本思想想和特點點發端發送送一個幀幀，然后后等待確確認(stopandwait.)確認幀的的內容并并不重要要數據傳輸輸是單向向的，但但是必須須是雙向向鏈路，因此用用一個半半雙工的的物理信信道就足足夠了單工的等等/停協協議有噪聲信信道的單單工協議議假設:信道有噪噪聲，因因此可能能會丟/損壞幀簡單的方方法:發端設置置一個定定時器，如

14、果在在規定的的時間內內沒有接接收到ACK，則重發發該幀.這種方法法有沒有有問題？有噪聲信信道的單單工協議議考慮下面面的場景景：A傳輸一個個幀B接收到A傳來的幀幀A1B產生ACKACK丟失A定時器超超時,重傳B得到A1的副本(將會把副副本送到到網絡層層.)(另外一種種出現副副本的情情況是長長的時延延)使用序列列號在這個例例子里，1bit就夠了。在協議中中，發送送方在準準備下一一個數據據項目之之前先等等待一個個肯定的的確認，則這樣樣的協議議稱為（PositiveAcknowledgmentwith Retransmission (PAR)/AutomaticRepeatreQuest(ARQ)）有

15、噪聲信信道的單單工協議議一個支持持重傳的的肯定確確認協議議C有噪聲信信道的單單工協議議一個支持持重傳的的肯定確確認協議議3.4滑滑窗協協議用于雙向向通信使用同一一條線路路來傳輸輸兩個方方向上的的數據反向信道道與前向向信道有有相同的的容量.有兩種類類型的幀幀( kindfield):數據（Data）ACK(含有最新新接收幀幀的序號號)捎帶確認認（Piggybacking）Piggybacking確認信息息附在往往外（反反向鏈路路）發送送的數據據幀上的的行為。優點:更好的利利用信道道帶寬。問題:為了更好好的利用用帶寬，數據鏈鏈路層應應該等待待下一個個分組多多長時間間?滑窗協議議每個外發發的幀都都包

16、含一一個序列列號，其其范圍為為0 MaxSeq(2n 1).這樣的序序列號正正好可以以填到一一個n位的域中中。等-停滑動窗窗口協議議使用n =1。滑窗協議議的本質質：在任任何時刻刻，發送送方總是是維持著著一組序序列號，分別對對應于允允許它發發送的幀幀。稱這這些幀落落在發送送窗口內內，接受受方也維維持一個個接收窗窗口，對對應一組組允許他他接收的的幀。窗窗口大小小可以固固定或者者不固定定。滑窗協議議 (2)滑窗大小小為1，有3個序列號號的滑動動窗口(a)初始化(b)第1幀發送以以后(c)第1幀接收以以后(d)第一個確確認收到到后滑窗協議議1位滑窗協協議GoBack N協議選擇性重重傳協議議1位滑窗

17、窗協議C1位滑窗協協議(ctd.)1位滑窗協協議(2)針對協議議4的兩種情情況. (a)正常情況況. (b)異常情況況.記號為(seq,ack, packetnumber).星號表示示網絡層層接受一一個分組組Goback n協議停/等協議的的一個問問題是：往返時時延過長長1000 bitframes50kbpschannel，往返傳傳播時延延500ms(satellite)發送1000bit的幀到接接收方完完全接收收需要270ms，520ms后收端才才能接收收到確認認（忽略略ACK帶來的時時延）。只有4%的有效帶帶寬被利利用，效效率很差差！管道化利用管道道:使得多個個幀可以以同時在在一條鏈鏈路

18、上傳傳輸.性能改善善F =framesize(bits)C =channelcapacity(bps)I =propagation delay plusprocessor servicetime(seconds)Time to transmit asingle frame=F/CTotalDelay=2Iline utilization=F/(F+2CI)50%if F2CIGoBack N協協議Goback n對用于“接收窗窗口尺寸寸為1”的情況如果接收收端收到到壞幀，則后續續的幀（管道中中的）無無論正確確與否全全部丟棄棄丟棄的幀幀沒有ACKGoBack N滑滑窗協議議CGoBack N滑窗

19、協議議CGoBack N滑窗協議議CGoBack N滑窗協議議窗口尺寸寸問題考慮MAX_SEQ =7的場景：發送方發發送0 7幀.第7幀的捎帶帶確認最最終被送送回到發發送方.發送方送送出另外外8幀，其序序號仍然然是07現在第7幀的另一一個捎帶帶確認也也回來了了問題是：屬于第第二批的的8幀全部成成功到達達了嗎？或者是是說這8幀全部丟丟失了（把出錯錯之后丟丟棄的幀幀也算作作丟失了了）？在在這兩種種情況下下，接收收方都會會發送第第7幀的確認認。而發發送方無無從分辨辨。由于于這個原原因，未未確認幀幀（即窗窗口大小小）必須須限制為為MAX_SEQGoBack N滑窗協議議用軟件模模擬多個個定時器器選擇性

20、重重傳協議議選擇性重重傳接收窗口口尺寸大大于1.緩存壞幀幀以后所所有的幀幀.只對最后后一個正正確接收收的幀進進行確認認。選擇性重重傳協議議接收側帶帶寬與鏈鏈路層緩緩存之間間的折中中這兩種情情況下，發送側側需要緩緩存，只只有接收收到ACK后占用的的緩存才才能釋放放。為了強制制執行“任何時時候未確確認幀的的個數都都不應該該超過Max_Seq”的流控控規則，DLL應該能夠夠enable/disable網絡層使用選擇擇性重傳傳的滑動動窗口協協議CContinued使用選擇擇性重傳傳的滑動動窗口協協議(2)使用選擇擇性重傳傳的滑動動窗口協協議(3)C使用選擇擇性重傳傳的滑動動窗口協協議(4)非順序接接收

21、問題題(a)窗口大小小為7的初始狀狀態.(b)7幀都已送送出并接接收，但但是均未未被確認認(c)窗口大小小為4的初始狀狀態(d)4幀都已送送出并接接收，但但是均未未被確認認數據重疊疊（overlap）問題的本本質是，當接收收方向前前移動窗窗口后，新的有有效序列列號與老老的有效效序列號號之間有有重疊，因此后后續的幀幀可能是是重復的的幀，也也有可能能是新的的幀，但但是接收收端無法法區分。解決的方方法：最最大的窗窗口尺寸寸應該不不超過序序列號范范圍的一一半，即即(MAX_SEQ+ 1)/2.因此對3位序列號號，窗口口尺寸為為反向流量量輕的問問題之前的假假設反向向信道負負載較重重（因為為采用捎捎帶確認

22、認）如果反向向業務輕輕會如何何？確認信息息會滯留留很長時時間極端情況況，如果果在一個個方向上上有很大大的流量量，而另另一個方方向上根根本沒有有流量，則只有有MAX_SEQ個分組被被發出去去，協議議就阻塞塞了。啟用start_ack_timer輔助定時時器，如如果定時時器到期期前沒有有出現反反向流量量，則發發送一個個單獨的的確認幀幀。3.5協協議驗驗證有限狀態態機模型型Petri網模型有限狀態態機模型型協議規范范和驗證證:本節的目目的是學學習驗證證協議的的方法狀態圖對對于驗證證協議的的正確性性和完整整性是非非常重要要的協議機；狀態；轉換，死鎖一個協議議的有限限狀態機機模型可可以看作作是一個個四元組組（S，M，I，T），其中中：S是指進程程和信道道可能的的狀態集集合M是指能在在信道上上進行交交換的幀幀的集合合I是指進程程的初始始狀態集集合T是狀態之之間轉換換的集合合FiniteStateMachinedModels（a）協議3的狀態圖圖(b)轉換Petri網網模型包含兩個個庫所和和2個轉換的的Petri網.庫所，變變遷，弧弧和標記記Petri網網模型(2)協議3的Petri網模型3.6數數據鏈鏈路層協協議示例例HDLC High-Level DataLinkControlInterne