數(shù)據(jù)鏈路層知識概述課件

數(shù)據(jù)鏈路層

第三章1linwei@數(shù)據(jù)鏈路層第三章1linwei@主要內容3.1數(shù)據(jù)鏈路層設計要點3.2錯誤檢測和糾正3.3基本數(shù)據(jù)鏈路層協(xié)議3.4滑窗協(xié)議3.5協(xié)議驗證3.6數(shù)據(jù)鏈路層協(xié)議示例2linwei@主要內容3.1數(shù)據(jù)鏈路層設計要點2linwei@cuc.e3.1數(shù)據(jù)鏈路層的設計要點為網絡層提供的服務成幀差錯控制流量控制3linwei@3.1數(shù)據(jù)鏈路層的設計要點為網絡層提供的服務3linwei鏈路層基本功能向網絡層提供一個服務接口處理傳輸錯誤調節(jié)數(shù)據(jù)流（流控）4linwei@鏈路層基本功能向網絡層提供一個服務接口4linwei@cuc分組與幀之間的關系5linwei@分組與幀之間的關系5linwei@虛擬通信和實際通信(a)虛擬通信.(b)實際通信.6linwei@虛擬通信和實際通信(a)虛擬通信.6linwei@cuc.數(shù)據(jù)鏈路層提供的服務無確認的無連接服務用于低誤碼率鏈路或對誤碼不敏感的業(yè)務.(fiber,utp,real-time)有確認的無連接服務用于高誤碼率鏈路(Wireless)有確認的面向連接的服務保證每個幀真正接收到且只接收一次。為網絡層進程提供一個可靠的位流。7linwei@數(shù)據(jù)鏈路層提供的服務無確認的無連接服務7linwei@cuc例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@

DLL將原始碼流分解為離散的單元，該單元稱為幀。那么接收端如何檢測幀的邊界呢？或者說接收端如何界定幀的開始和結束呢？討論4種方法：字符計數(shù)法含字節(jié)填充的分界符法含位填充的分界標志法編碼違例

成幀9linwei@DLL將原始碼流分解為離散的單元，該單元字符計數(shù)法一個字符流(a)無差錯.(b)有一個差錯.10linwei@字符計數(shù)法一個字符流(a)無差錯.(b)有一個字符填充(a)有標志字節(jié)作為分界的幀.(b)字節(jié)填充前后的4個字節(jié)序列例子.11linwei@字符填充(a)有標志字節(jié)作為分界的幀.11linwei@c比特填充Bit填充，

標記01111110(a)原始數(shù)據(jù).(b)線路上的數(shù)據(jù).(c)刪除填充后存儲在接收方存儲器中的數(shù)據(jù).12linwei@比特填充Bit填充，標記0111111012linw編碼違例適用于“物理介質上的編碼方法中包含冗余信息”的網絡。例如有些LAN用2個物理位來編碼1位數(shù)據(jù)?！?”位是“高-低”電平對，“0”位是“低-高”電平對。而“高高”“低低”電平對不用于數(shù)據(jù)，則可用于幀定界。優(yōu)點是沒有額外帶寬開銷13linwei@編碼違例適用于“物理介質上的編碼方法中包含冗余信息”的網絡。為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:當接收端正確接收一個幀，它會向發(fā)送端返回一個ACK幀用于指示發(fā)端該幀已正確接收。在某些系統(tǒng)，如果接收的幀不正確，接收端會發(fā)端返回一個NACK（NegativeACK）用于指示該幀沒有正確接收.提示發(fā)端不用等待定時器超時就立即發(fā)送（重傳）一個幀.

錯誤控制14linwei@為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個部Timers:

如果沒有定時器，當幀丟失或者

ACK/NACK丟失，會出現(xiàn)什么情況？定時器怎么工作呢？當發(fā)送一個幀的時候，發(fā)端開啟一個定時器，當在約定的時間內，發(fā)端接收到ACK/NACK，則立即發(fā)送（重發(fā)）一個幀，且重置定時器，否則當定時超時時，重發(fā)該幀。

SequenceNumbers:

主要解決接收端接收到重復幀的問題.為了避免接收重復幀的問題，給發(fā)送的幀分配序列號，這樣接收端就能夠區(qū)分原始幀和重傳幀。.ErrorControl15linwei@Timers:ErrorControl15linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控是個動態(tài)的過程，取決于負載強度、接收端緩存大小等，常用的方法：

基于反饋的流控制基于速率的流控制（從來沒有用于DDL）16linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控3.2錯誤檢測和糾正糾錯碼檢錯碼17linwei@3.2錯誤檢測和糾正糾錯碼17linwei@錯誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起的比特錯誤通常是突發(fā)性的，而不是獨立的，單比特錯誤，例如：閃電會引起短暫的突發(fā)比特錯誤。18linwei@錯誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起糾錯碼檢測和糾正數(shù)據(jù)中的錯誤

冗余（redundancy）-在數(shù)據(jù)中加入附加的信息。兩種策略：檢錯碼:

包含足夠的冗余比特檢錯，然后使用NACK告知發(fā)端重傳。糾錯碼:包含足夠的冗余比特檢測和糾正錯誤。19linwei@糾錯碼檢測和糾正數(shù)據(jù)中的錯誤19linwei@海明距離給定兩個碼子，對其進行異或運算，然后計算出異或結果中1的個數(shù)，兩個碼子中不相同的位的個數(shù)稱為海明距離.

它的意義在于：如果兩個碼子的海明距離為d，則需要d個1位錯誤才能將一個碼子轉變成另一個碼子。

20linwei@海明距離給定兩個碼子，對其進行異或運算，然后計算出異或結果中

海明距離通常，所有2m

種可能的數(shù)據(jù)報文都是合法的，但是并非所有的2n（n=m+r；m為數(shù)據(jù)位，r為冗余位）種碼子都被用到。給定計算校驗位的算法后，可以構造合法碼子列表，并且可以從該表中找到海明距離最小的兩個碼子，此距離是整個編碼方案的海明距離。為了檢測d個錯誤，需要一個距離為d+1

的編碼方案為了糾正t個錯誤，需要一個距離為2t+1

的編碼方案21linwei@

海明距離通常，所有2m種可能的數(shù)據(jù)報文都是合法的，但是奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.1000000(1)1111101(0)奇偶位的海明距離為2，因此它可以檢測單比特錯誤，但是不能糾錯考慮以下的例子，4個有效碼子的編碼："0000000000","0000011111","1111100000",and"1111111111".

編碼距離為5,可以糾正2個錯誤。22linwei@奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.22li糾錯

設計一種編碼方案，每個碼子有m個報文位和r個校驗位，并且能夠糾正所有的單個錯誤。對于2m

合法報文，任一個報文都對應有n個非法的碼子，它們與該報文的距離為1。因此每個合法的報文都要求n+1個位模式供他使用。由于總共有2n個位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，給定m的情況下，這個條件給出了用于糾正單個錯誤所需要的校驗位數(shù)目的下界

例如m=10，r>423linwei@糾錯設計一種編碼方案，每個碼子有m檢錯碼

糾錯碼代價很大（計算量和帶寬），因此用在無線通信較為合適，但是在銅線或者光纜，錯誤檢測和重傳機制往往更加有效。

例如，若誤碼是獨立的，誤碼率為10-6。則對于1000bit的數(shù)據(jù)塊，需要10個校驗位糾正1個單bit錯誤，1Mbit的需要10Kbit，顯然如果僅僅檢測錯誤，每個數(shù)據(jù)塊1個奇偶位就足夠了，每一千個數(shù)據(jù)塊額外傳輸一個塊，因此開銷小，利用檢錯/重傳機制，則1Mbit只需2001位，相比之下，海明碼需要10000位。

最廣泛使用的檢錯碼是多項式編碼，也稱CRC。24linwei@檢錯碼

24linwei@CyclicRedundancyCheck基本思想：將位串看成系數(shù)為0或1的多項式。多項式的算術運算以2為模完成，加減法等同于異或，除法為長除運算。生成多項式G(x)：事先約定的，最低位，最高位必須是1。校驗和：添加到幀序列多項式中，用于檢測傳輸是否有錯誤。25linwei@CyclicRedundancyCheck基本思想：將位CyclicRedundancyCheck校驗和的計算方法：(1)假設G(x)的階為r。在幀的低位端加上r個0位，所以該幀現(xiàn)在包含m+r位。對應的多項式為xrM(x)。(2)利用模2除法，用對應于G(x)的位串去除xrM(x)的位串。(3)利用模2減法，從對應于xrM(x)的位串中減去余數(shù)，結果就是將被傳輸?shù)膸ｒ灪偷膸?，記為：T(x)。

26linwei@CyclicRedundancyCheck校驗和的計算方CyclicRedundancy

Check校驗和的計算過程27linwei@CyclicRedundancy

Check校驗和的計算CyclicRedundancyCheck分析：1.所有的錯誤都能檢測出嗎？

錯誤多項式E(x)能被G(x)除盡，則這類錯誤無法被檢測。2.所有的一位錯誤都將被檢測到。

低階的多項式可以保護長的幀（K<=i–j,兩個獨立的一位錯誤）

奇數(shù)項多項式不可能被x+1除盡(奇數(shù)個位發(fā)生錯誤)。帶r個校驗位的多項式編碼可以檢測到所有長度小于等于r的突發(fā)性錯誤。28linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3種CRC生成多項式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

盡管復雜，可以用硬件構造出來29linwei@CyclicRedundancyCheck通常用到的3種3.3基本數(shù)據(jù)鏈路協(xié)議一個無限制的單工協(xié)議一個單工的?！葏f(xié)議有噪聲信道的單工協(xié)議30linwei@3.3基本數(shù)據(jù)鏈路協(xié)議一個無限制的單工協(xié)議30linwei基本數(shù)據(jù)鏈路協(xié)議幾個假設：物理層、數(shù)據(jù)鏈路層和網絡層都是獨立的進程，它們通過報文來相互通信。可靠的、面向連接的服務機器不會崩潰31linwei@基本數(shù)據(jù)鏈路協(xié)議幾個假設：31linwei@.協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.32linwei@協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.33linwei@協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含無限制的單工協(xié)議假設條件:數(shù)據(jù)單向傳輸物理信道無誤碼，即無幀損壞或丟失發(fā)/接收端緩存無限大發(fā)端/收端的網絡層總是處于準備就緒狀態(tài)34linwei@無限制的單工協(xié)議假設條件:34linwei@.無限制的

單工協(xié)議35linwei@無限制的

單工協(xié)議35linwei@一個單工的停/等協(xié)議

假設:不再假設收端能夠無限快速的處理到來的數(shù)據(jù).基本思想和特點發(fā)端發(fā)送一個幀，然后等待確認(stopandwait.)確認幀的內容并不重要

數(shù)據(jù)傳輸是單向的，但是必須是雙向鏈路，因此用一個半雙工的物理信道就足夠了36linwei@一個單工的停/等協(xié)議

假設:36linwei@單工的等/停協(xié)議37linwei@單工的等/停協(xié)議37linwei@有噪聲信道的單工協(xié)議假設:信道有噪聲，因此可能會丟/損壞幀簡單的方法:發(fā)端設置一個定時器，如果在規(guī)定的時間內沒有接收到ACK，則重發(fā)該幀.這種方法有沒有問題？38linwei@有噪聲信道的單工協(xié)議假設:38linwei@.有噪聲信道的單工協(xié)議考慮下面的場景：

A傳輸一個幀

B接收到A傳來的幀A1B產生ACKACK丟失A定時器超時,重傳B得到A1的副本(將會把副本送到網絡層.)(另外一種出現(xiàn)副本的情況是長的時延)使用序列號在這個例子里，1bit就夠了。在協(xié)議中，發(fā)送方在準備下一個數(shù)據(jù)項目之前先等待一個肯定的確認，則這樣的協(xié)議稱為（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

39linwei@有噪聲信道的單工協(xié)議考慮下面的場景：

39linwei@cu有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議Continued40linwei@有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議Continu有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議41linwei@有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議41linwe3.4滑窗協(xié)議用于雙向通信使用同一條線路來傳輸兩個方向上的數(shù)據(jù)反向信道與前向信道有相同的容量.有兩種類型的幀("kind"field):數(shù)據(jù)（Data）ACK(含有最新接收幀的序號).42linwei@3.4滑窗協(xié)議用于雙向通信42linwei@捎帶確認（Piggybacking）Piggybacking–確認信息附在往外（反向鏈路）發(fā)送的數(shù)據(jù)幀上的行為。優(yōu)點:更好的利用信道帶寬。

問題:為了更好的利用帶寬，數(shù)據(jù)鏈路層應該等待下一個分組多長時間?43linwei@捎帶確認（Piggybacking）Piggybacking滑窗協(xié)議每個外發(fā)的幀都包含一個序列號，其范圍為0~MaxSeq(2n–1).這樣的序列號正好可以填到一個n位的域中。等-?；瑒哟翱趨f(xié)議使用n=1?；皡f(xié)議的本質：在任何時刻，發(fā)送方總是維持著一組序列號，分別對應于允許它發(fā)送的幀。稱這些幀落在發(fā)送窗口內，接受方也維持一個接收窗口，對應一組允許他接收的幀。窗口大小可以固定或者不固定。44linwei@滑窗協(xié)議44linwei@滑窗協(xié)議(2)滑窗大小為1，有3個序列號的滑動窗口(a)初始化(b)第1幀發(fā)送以后(c)第1幀接收以后(d)第一個確認收到后45linwei@滑窗協(xié)議(2)滑窗大小為1，有3個序列號的滑動窗口45li滑窗協(xié)議1位滑窗協(xié)議GoBackN協(xié)議選擇性重傳協(xié)議46linwei@滑窗協(xié)議1位滑窗協(xié)議46linwei@1位滑窗協(xié)議Continued47linwei@1位滑窗協(xié)議Continued47linwei@cuc.1位滑窗協(xié)議(ctd.)48linwei@1位滑窗協(xié)議(ctd.)48linwei@.1位滑窗協(xié)議(2)針對協(xié)議4的兩種情況.(a)正常情況.(b)異常情況.

記號為(seq,ack,packetnumber).星號表示網絡層接受一個分組.49linwei@1位滑窗協(xié)議(2)針對協(xié)議4的兩種情況.Gobackn協(xié)議

停/等協(xié)議的一個問題是：往返時延過長

1000bitframes50kbpschannel，往返傳播時延500ms(satellite)

發(fā)送1000bit的幀到接收方完全接收需要270ms，520ms后收端才能接收到確認（忽略ACK帶來的時延）。只有4%的有效帶寬被利用，效率很差！

50linwei@Gobackn協(xié)議

50linwei@.管道化利用管道:使得多個幀可以同時在一條鏈路上傳輸.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI51linwei@管道化利用管道:51linwei@GoBackN協(xié)議Gobackn–對用于“接收窗口尺寸為1”的情況如果接收端收到壞幀，則后續(xù)的幀（管道中的）無論正確與否全部丟棄丟棄的幀沒有ACKs.52linwei@GoBackN協(xié)議Gobackn–對用于“接收窗GoBackN滑窗協(xié)議Continued53linwei@GoBackN滑窗協(xié)議Continued53linwGoBackN滑窗協(xié)議Continued54linwei@GoBackN滑窗協(xié)議Continued54linwGoBackN滑窗協(xié)議Continued55linwei@GoBackN滑窗協(xié)議Continued55linwGoBackN滑窗協(xié)議56linwei@GoBackN滑窗協(xié)議56linwei@.窗口尺寸問題考慮MAX_SEQ=7的場景：發(fā)送方發(fā)送0~7幀.第7幀的捎帶確認最終被送回到發(fā)送方.發(fā)送方送出另外8幀，其序號仍然是0~7現(xiàn)在第7幀的另一個捎帶確認也回來了問題是：屬于第二批的8幀全部成功到達了嗎？或者是說這8幀全部丟失了（把出錯之后丟棄的幀也算作丟失了）？在這兩種情況下，接收方都會發(fā)送第7幀的確認。而發(fā)送方無從分辨。由于這個原因，未確認幀（即窗口大?。┍仨毾拗茷镸AX_SEQ.57linwei@窗口尺寸問題考慮MAX_SEQ=7的場景：57linwGoBackN滑窗協(xié)議用軟件模擬多個定時器.58linwei@GoBackN滑窗協(xié)議用軟件模擬多個定時器.58linw選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.緩存壞幀以后所有的幀.只對最后一個正確接收的幀進行確認。59linwei@選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.59li選擇性重傳協(xié)議接收側帶寬與鏈路層緩存之間的折中

這兩種情況下，發(fā)送側需要緩存，只有接收到ACK后占用的緩存才能釋放。

為了強制執(zhí)行“任何時候未確認幀的個數(shù)都不應該超過Max_Seq”的流控規(guī)則，DLL應該能夠enable/disable網絡層60linwei@選擇性重傳協(xié)議接收側帶寬與鏈路層緩存之間的折中

60linw使用選擇性重傳的滑動窗口協(xié)議Continued61linwei@使用選擇性重傳的滑動窗口協(xié)議Continued61linContinued使用選擇性重傳的滑動窗口協(xié)議(2)62linwei@Continued使用選擇性重傳的滑動窗口協(xié)議(2)62使用選擇性重傳的滑動窗口協(xié)議(3)Continued63linwei@使用選擇性重傳的滑動窗口協(xié)議(3)Continued63使用選擇性重傳的滑動窗口協(xié)議(4)64linwei@使用選擇性重傳的滑動窗口協(xié)議(4)64linwei@cuc.非順序接收問題(a)窗口大小為7的初始狀態(tài).(b)7幀都已送出并接收，但是均未被確認(c)窗口大小為4的初始狀態(tài)(d)4幀都已送出并接收，但是均未被確認.65linwei@非順序接收問題(a)窗口大小為7的初始狀態(tài).65linwe數(shù)據(jù)重疊（overlap）問題的本質是，當接收方向前移動窗口后，新的有效序列號與老的有效序列號之間有重疊，因此后續(xù)的幀可能是重復的幀，也有可能是新的幀，但是接收端無法區(qū)分。解決的方法：最大的窗口尺寸應該不超過序列號范圍的一半，即(MAX_SEQ+1)/2.

因此對3位序列號，窗口尺寸為466linwei@數(shù)據(jù)重疊（overlap）問題的本質是，當接收方向前移動窗口反向流量輕的問題之前的假設反向信道負載較重（因為采用捎帶確認）如果反向業(yè)務輕會如何？確認信息會滯留很長時間極端情況，如果在一個方向上有很大的流量，而另一個方向上根本沒有流量，則只有MAX_SEQ個分組被發(fā)出去，協(xié)議就阻塞了。啟用start_ack_timer輔助定時器，如果定時器到期前沒有出現(xiàn)反向流量，則發(fā)送一個單獨的確認幀。67linwei@反向流量輕的問題之前的假設反向信道負載較重（因為采用捎帶確認3.5協(xié)議驗證有限狀態(tài)機模型Petri網模型68linwei@3.5協(xié)議驗證有限狀態(tài)機模型68linwei@cuc.ed有限狀態(tài)機模型

協(xié)議規(guī)范和驗證:

本節(jié)的目的是學習驗證協(xié)議的方法狀態(tài)圖對于驗證協(xié)議的正確性和完整性是非常重要的協(xié)議機；狀態(tài)；轉換，死鎖一個協(xié)議的有限狀態(tài)機模型可以看作是一個四元組（S，M，I，T），其中：S是指進程和信道可能的狀態(tài)集合M是指能在信道上進行交換的幀的集合I是指進程的初始狀態(tài)集合T是狀態(tài)之間轉換的集合69linwei@有限狀態(tài)機模型

協(xié)議規(guī)范和驗證:

69linwei@cuc.FiniteStateMachinedModels（a）協(xié)議3的狀態(tài)圖(b)轉換.70linwei@FiniteStateMachinedModels（aPetri網模型包含兩個庫所和2個轉換的Petri網.庫所，變遷，弧和標記71linwei@Petri網模型包含兩個庫所和2個轉換的Petri網.7Petri網模型(2)協(xié)議3的Petri網模型72linwei@Petri網模型(2)協(xié)議3的Petri網模型72li3.6數(shù)據(jù)鏈路層協(xié)議示例HDLC–High-LevelDataLinkControlInternet中的數(shù)據(jù)鏈路層73linwei@3.6數(shù)據(jù)鏈路層協(xié)議示例HDLC–High-LevelHigh-LevelDataLinkControl面向位的協(xié)議的幀格式.74linwei@High-LevelDataLinkControl面向HDLCControlField三種幀的控制域

(a)信息幀

(b)管理幀(c)無序號幀75linwei@HDLCControlField三種幀的控制域75liHigh-LevelDataLinkControl管理幀類型Type0

是一個確認幀，用于指示下一個期望的幀。Type1

是一個否定的確認幀，指示一個傳輸錯誤已經被檢測到，NEXT域指明了期望被重傳的幀的序列號。發(fā)送方必須重傳從NEXT開始的所有未被確認的幀。Type2

是接收尚未就緒，它確認直到Next的所有幀，但是不包含Next幀，告訴發(fā)端不要在發(fā)送了。Type3

是選擇性拒絕。它只要求重傳特定的幀。76linwei@High-LevelDataLinkControl管理

Internet中的數(shù)據(jù)鏈路層Point-to-point線路:路由器之間的租用線路，經由modem撥號登陸主機的線路

PPP-Point-to-PointProtocol:Standard(RFCs1661-1663)77linwei@

Internet中的數(shù)據(jù)鏈路層Point-to-pointPPP-Point-to-PointProtocol:PPP提供了3類功能:成幀方法，幀格式支持錯誤檢測。鏈路控制協(xié)議(LCP)

，可用于啟動線路、測試線路、協(xié)商參數(shù)以及當線路不再需要的時候關閉線路。網絡控制協(xié)議

：協(xié)商網絡層選項的方法。與HDLC類似,但是其是面向字符型的.78linwei@PPP-Point-to-PointProtocol:point-to-pointcommunication一臺家庭個人計算機成為一臺Internet主機79linwei@point-to-pointcommunication一臺PPP–PointtoPointProtocol無序號模式下PPP的完整的幀格式.80linwei@PPP–PointtoPointProtocol無狀態(tài)機線路啟動到關閉的狀態(tài)轉移圖81linwei@狀態(tài)機線路啟動到關閉的狀態(tài)轉移圖81linwei@cuc.eRFC1661:LCPFrametypesTheLCPframetypes.82linwei@RFC1661:LCPFrametypesTheLC數(shù)據(jù)鏈路層

第三章83linwei@數(shù)據(jù)鏈路層第三章1linwei@主要內容3.1數(shù)據(jù)鏈路層設計要點3.2錯誤檢測和糾正3.3基本數(shù)據(jù)鏈路層協(xié)議3.4滑窗協(xié)議3.5協(xié)議驗證3.6數(shù)據(jù)鏈路層協(xié)議示例84linwei@主要內容3.1數(shù)據(jù)鏈路層設計要點2linwei@cuc.e3.1數(shù)據(jù)鏈路層的設計要點為網絡層提供的服務成幀差錯控制流量控制85linwei@3.1數(shù)據(jù)鏈路層的設計要點為網絡層提供的服務3linwei鏈路層基本功能向網絡層提供一個服務接口處理傳輸錯誤調節(jié)數(shù)據(jù)流（流控）86linwei@鏈路層基本功能向網絡層提供一個服務接口4linwei@cuc分組與幀之間的關系87linwei@分組與幀之間的關系5linwei@虛擬通信和實際通信(a)虛擬通信.(b)實際通信.88linwei@虛擬通信和實際通信(a)虛擬通信.6linwei@cuc.數(shù)據(jù)鏈路層提供的服務無確認的無連接服務用于低誤碼率鏈路或對誤碼不敏感的業(yè)務.(fiber,utp,real-time)有確認的無連接服務用于高誤碼率鏈路(Wireless)有確認的面向連接的服務保證每個幀真正接收到且只接收一次。為網絡層進程提供一個可靠的位流。89linwei@數(shù)據(jù)鏈路層提供的服務無確認的無連接服務7linwei@cuc例子數(shù)據(jù)鏈路協(xié)議的位置90linwei@例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@

DLL將原始碼流分解為離散的單元，該單元稱為幀。那么接收端如何檢測幀的邊界呢？或者說接收端如何界定幀的開始和結束呢？討論4種方法：字符計數(shù)法含字節(jié)填充的分界符法含位填充的分界標志法編碼違例

成幀91linwei@DLL將原始碼流分解為離散的單元，該單元字符計數(shù)法一個字符流(a)無差錯.(b)有一個差錯.92linwei@字符計數(shù)法一個字符流(a)無差錯.(b)有一個字符填充(a)有標志字節(jié)作為分界的幀.(b)字節(jié)填充前后的4個字節(jié)序列例子.93linwei@字符填充(a)有標志字節(jié)作為分界的幀.11linwei@c比特填充Bit填充，

標記01111110(a)原始數(shù)據(jù).(b)線路上的數(shù)據(jù).(c)刪除填充后存儲在接收方存儲器中的數(shù)據(jù).94linwei@比特填充Bit填充，標記0111111012linw編碼違例適用于“物理介質上的編碼方法中包含冗余信息”的網絡。例如有些LAN用2個物理位來編碼1位數(shù)據(jù)?！?”位是“高-低”電平對，“0”位是“低-高”電平對。而“高高”“低低”電平對不用于數(shù)據(jù)，則可用于幀定界。優(yōu)點是沒有額外帶寬開銷95linwei@編碼違例適用于“物理介質上的編碼方法中包含冗余信息”的網絡。為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:當接收端正確接收一個幀，它會向發(fā)送端返回一個ACK幀用于指示發(fā)端該幀已正確接收。在某些系統(tǒng)，如果接收的幀不正確，接收端會發(fā)端返回一個NACK（NegativeACK）用于指示該幀沒有正確接收.提示發(fā)端不用等待定時器超時就立即發(fā)送（重傳）一個幀.

錯誤控制96linwei@為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個部Timers:

如果沒有定時器，當幀丟失或者

ACK/NACK丟失，會出現(xiàn)什么情況？定時器怎么工作呢？當發(fā)送一個幀的時候，發(fā)端開啟一個定時器，當在約定的時間內，發(fā)端接收到ACK/NACK，則立即發(fā)送（重發(fā)）一個幀，且重置定時器，否則當定時超時時，重發(fā)該幀。

SequenceNumbers:

主要解決接收端接收到重復幀的問題.為了避免接收重復幀的問題，給發(fā)送的幀分配序列號，這樣接收端就能夠區(qū)分原始幀和重傳幀。.ErrorControl97linwei@Timers:ErrorControl15linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控是個動態(tài)的過程，取決于負載強度、接收端緩存大小等，常用的方法：

基于反饋的流控制基于速率的流控制（從來沒有用于DDL）98linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控3.2錯誤檢測和糾正糾錯碼檢錯碼99linwei@3.2錯誤檢測和糾正糾錯碼17linwei@錯誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起的比特錯誤通常是突發(fā)性的，而不是獨立的，單比特錯誤，例如：閃電會引起短暫的突發(fā)比特錯誤。100linwei@錯誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起糾錯碼檢測和糾正數(shù)據(jù)中的錯誤

冗余（redundancy）-在數(shù)據(jù)中加入附加的信息。兩種策略：檢錯碼:

包含足夠的冗余比特檢錯，然后使用NACK告知發(fā)端重傳。糾錯碼:包含足夠的冗余比特檢測和糾正錯誤。101linwei@糾錯碼檢測和糾正數(shù)據(jù)中的錯誤19linwei@海明距離給定兩個碼子，對其進行異或運算，然后計算出異或結果中1的個數(shù)，兩個碼子中不相同的位的個數(shù)稱為海明距離.

它的意義在于：如果兩個碼子的海明距離為d，則需要d個1位錯誤才能將一個碼子轉變成另一個碼子。

102linwei@海明距離給定兩個碼子，對其進行異或運算，然后計算出異或結果中

海明距離通常，所有2m

種可能的數(shù)據(jù)報文都是合法的，但是并非所有的2n（n=m+r；m為數(shù)據(jù)位，r為冗余位）種碼子都被用到。給定計算校驗位的算法后，可以構造合法碼子列表，并且可以從該表中找到海明距離最小的兩個碼子，此距離是整個編碼方案的海明距離。為了檢測d個錯誤，需要一個距離為d+1

的編碼方案為了糾正t個錯誤，需要一個距離為2t+1

的編碼方案103linwei@

海明距離通常，所有2m種可能的數(shù)據(jù)報文都是合法的，但是奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.1000000(1)1111101(0)奇偶位的海明距離為2，因此它可以檢測單比特錯誤，但是不能糾錯考慮以下的例子，4個有效碼子的編碼："0000000000","0000011111","1111100000",and"1111111111".

編碼距離為5,可以糾正2個錯誤。104linwei@奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.22li糾錯

設計一種編碼方案，每個碼子有m個報文位和r個校驗位，并且能夠糾正所有的單個錯誤。對于2m

合法報文，任一個報文都對應有n個非法的碼子，它們與該報文的距離為1。因此每個合法的報文都要求n+1個位模式供他使用。由于總共有2n個位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，給定m的情況下，這個條件給出了用于糾正單個錯誤所需要的校驗位數(shù)目的下界

例如m=10，r>4105linwei@糾錯設計一種編碼方案，每個碼子有m檢錯碼

糾錯碼代價很大（計算量和帶寬），因此用在無線通信較為合適，但是在銅線或者光纜，錯誤檢測和重傳機制往往更加有效。

例如，若誤碼是獨立的，誤碼率為10-6。則對于1000bit的數(shù)據(jù)塊，需要10個校驗位糾正1個單bit錯誤，1Mbit的需要10Kbit，顯然如果僅僅檢測錯誤，每個數(shù)據(jù)塊1個奇偶位就足夠了，每一千個數(shù)據(jù)塊額外傳輸一個塊，因此開銷小，利用檢錯/重傳機制，則1Mbit只需2001位，相比之下，海明碼需要10000位。

最廣泛使用的檢錯碼是多項式編碼，也稱CRC。106linwei@檢錯碼

24linwei@CyclicRedundancyCheck基本思想：將位串看成系數(shù)為0或1的多項式。多項式的算術運算以2為模完成，加減法等同于異或，除法為長除運算。生成多項式G(x)：事先約定的，最低位，最高位必須是1。校驗和：添加到幀序列多項式中，用于檢測傳輸是否有錯誤。107linwei@CyclicRedundancyCheck基本思想：將位CyclicRedundancyCheck校驗和的計算方法：(1)假設G(x)的階為r。在幀的低位端加上r個0位，所以該幀現(xiàn)在包含m+r位。對應的多項式為xrM(x)。(2)利用模2除法，用對應于G(x)的位串去除xrM(x)的位串。(3)利用模2減法，從對應于xrM(x)的位串中減去余數(shù)，結果就是將被傳輸?shù)膸ｒ灪偷膸?，記為：T(x)。

108linwei@CyclicRedundancyCheck校驗和的計算方CyclicRedundancy

Check校驗和的計算過程109linwei@CyclicRedundancy

Check校驗和的計算CyclicRedundancyCheck分析：1.所有的錯誤都能檢測出嗎？

錯誤多項式E(x)能被G(x)除盡，則這類錯誤無法被檢測。2.所有的一位錯誤都將被檢測到。

低階的多項式可以保護長的幀（K<=i–j,兩個獨立的一位錯誤）

奇數(shù)項多項式不可能被x+1除盡(奇數(shù)個位發(fā)生錯誤)。帶r個校驗位的多項式編碼可以檢測到所有長度小于等于r的突發(fā)性錯誤。110linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3種CRC生成多項式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

盡管復雜，可以用硬件構造出來111linwei@CyclicRedundancyCheck通常用到的3種3.3基本數(shù)據(jù)鏈路協(xié)議一個無限制的單工協(xié)議一個單工的?！葏f(xié)議有噪聲信道的單工協(xié)議112linwei@3.3基本數(shù)據(jù)鏈路協(xié)議一個無限制的單工協(xié)議30linwei基本數(shù)據(jù)鏈路協(xié)議幾個假設：物理層、數(shù)據(jù)鏈路層和網絡層都是獨立的進程，它們通過報文來相互通信?？煽康?、面向連接的服務機器不會崩潰113linwei@基本數(shù)據(jù)鏈路協(xié)議幾個假設：31linwei@.協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.114linwei@協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.115linwei@協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含無限制的單工協(xié)議假設條件:數(shù)據(jù)單向傳輸物理信道無誤碼，即無幀損壞或丟失發(fā)/接收端緩存無限大發(fā)端/收端的網絡層總是處于準備就緒狀態(tài)116linwei@無限制的單工協(xié)議假設條件:34linwei@.無限制的

單工協(xié)議117linwei@無限制的

單工協(xié)議35linwei@一個單工的停/等協(xié)議

假設:不再假設收端能夠無限快速的處理到來的數(shù)據(jù).基本思想和特點發(fā)端發(fā)送一個幀，然后等待確認(stopandwait.)確認幀的內容并不重要

數(shù)據(jù)傳輸是單向的，但是必須是雙向鏈路，因此用一個半雙工的物理信道就足夠了118linwei@一個單工的停/等協(xié)議

假設:36linwei@單工的等/停協(xié)議119linwei@單工的等/停協(xié)議37linwei@有噪聲信道的單工協(xié)議假設:信道有噪聲，因此可能會丟/損壞幀簡單的方法:發(fā)端設置一個定時器，如果在規(guī)定的時間內沒有接收到ACK，則重發(fā)該幀.這種方法有沒有問題？120linwei@有噪聲信道的單工協(xié)議假設:38linwei@.有噪聲信道的單工協(xié)議考慮下面的場景：

A傳輸一個幀

B接收到A傳來的幀A1B產生ACKACK丟失A定時器超時,重傳B得到A1的副本(將會把副本送到網絡層.)(另外一種出現(xiàn)副本的情況是長的時延)使用序列號在這個例子里，1bit就夠了。在協(xié)議中，發(fā)送方在準備下一個數(shù)據(jù)項目之前先等待一個肯定的確認，則這樣的協(xié)議稱為（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

121linwei@有噪聲信道的單工協(xié)議考慮下面的場景：

39linwei@cu有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議Continued122linwei@有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議Continu有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議123linwei@有噪聲信道的單工協(xié)議一個支持重傳的肯定確認協(xié)議41linwe3.4滑窗協(xié)議用于雙向通信使用同一條線路來傳輸兩個方向上的數(shù)據(jù)反向信道與前向信道有相同的容量.有兩種類型的幀("kind"field):數(shù)據(jù)（Data）ACK(含有最新接收幀的序號).124linwei@3.4滑窗協(xié)議用于雙向通信42linwei@捎帶確認（Piggybacking）Piggybacking–確認信息附在往外（反向鏈路）發(fā)送的數(shù)據(jù)幀上的行為。優(yōu)點:更好的利用信道帶寬。

問題:為了更好的利用帶寬，數(shù)據(jù)鏈路層應該等待下一個分組多長時間?125linwei@捎帶確認（Piggybacking）Piggybacking滑窗協(xié)議每個外發(fā)的幀都包含一個序列號，其范圍為0~MaxSeq(2n–1).這樣的序列號正好可以填到一個n位的域中。等-?；瑒哟翱趨f(xié)議使用n=1?；皡f(xié)議的本質：在任何時刻，發(fā)送方總是維持著一組序列號，分別對應于允許它發(fā)送的幀。稱這些幀落在發(fā)送窗口內，接受方也維持一個接收窗口，對應一組允許他接收的幀。窗口大小可以固定或者不固定。126linwei@滑窗協(xié)議44linwei@滑窗協(xié)議(2)滑窗大小為1，有3個序列號的滑動窗口(a)初始化(b)第1幀發(fā)送以后(c)第1幀接收以后(d)第一個確認收到后127linwei@滑窗協(xié)議(2)滑窗大小為1，有3個序列號的滑動窗口45li滑窗協(xié)議1位滑窗協(xié)議GoBackN協(xié)議選擇性重傳協(xié)議128linwei@滑窗協(xié)議1位滑窗協(xié)議46linwei@1位滑窗協(xié)議Continued129linwei@1位滑窗協(xié)議Continued47linwei@cuc.1位滑窗協(xié)議(ctd.)130linwei@1位滑窗協(xié)議(ctd.)48linwei@.1位滑窗協(xié)議(2)針對協(xié)議4的兩種情況.(a)正常情況.(b)異常情況.

記號為(seq,ack,packetnumber).星號表示網絡層接受一個分組.131linwei@1位滑窗協(xié)議(2)針對協(xié)議4的兩種情況.Gobackn協(xié)議

停/等協(xié)議的一個問題是：往返時延過長

1000bitframes50kbpschannel，往返傳播時延500ms(satellite)

發(fā)送1000bit的幀到接收方完全接收需要270ms，520ms后收端才能接收到確認（忽略ACK帶來的時延）。只有4%的有效帶寬被利用，效率很差！

132linwei@Gobackn協(xié)議

50linwei@.管道化利用管道:使得多個幀可以同時在一條鏈路上傳輸.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI133linwei@管道化利用管道:51linwei@GoBackN協(xié)議Gobackn–對用于“接收窗口尺寸為1”的情況如果接收端收到壞幀，則后續(xù)的幀（管道中的）無論正確與否全部丟棄丟棄的幀沒有ACKs.134linwei@GoBackN協(xié)議Gobackn–對用于“接收窗GoBackN滑窗協(xié)議Continued135linwei@GoBackN滑窗協(xié)議Continued53linwGoBackN滑窗協(xié)議Continued136linwei@GoBackN滑窗協(xié)議Continued54linwGoBackN滑窗協(xié)議Continued137linwei@GoBackN滑窗協(xié)議Continued55linwGoBackN滑窗協(xié)議138linwei@GoBackN滑窗協(xié)議56linwei@.窗口尺寸問題考慮MAX_SEQ=7的場景：發(fā)送方發(fā)送0~7幀.第7幀的捎帶確認最終被送回到發(fā)送方.發(fā)送方送出另外8幀，其序號仍然是0~7現(xiàn)在第7幀的另一個捎帶確認也回來了問題是：屬于第二批的8幀全部成功到達了嗎？或者是說這8幀全部丟失了（把出錯之后丟棄的幀也算作丟失了）？在這兩種情況下，接收方都會發(fā)送第7幀的確認。而發(fā)送方無從分辨。由于這個原因，未確認幀（即窗口大?。┍仨毾拗茷镸AX_SEQ.139linwei@窗口尺寸問題考慮MAX_SEQ=7的場景：57linwGoBackN滑窗協(xié)議用軟件模擬多個定時器.140linwei@GoBackN滑窗協(xié)議用軟件模擬多個定時器.58linw選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.緩存壞幀以后所有的幀.只對最后一個正確接收的幀進行確認。141linwei@選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.59li選擇性重傳協(xié)議接收側帶寬與鏈路層緩存之間的折中

這兩種情況下，發(fā)送側需要緩存，只有接收到ACK后占用的緩存才能釋放。

為了強制執(zhí)行“任何時候未確認幀的個數(shù)都不應該超過Max_Seq”的流控規(guī)則，DLL應該能夠enable/disable網絡層142linwei@選擇性重傳協(xié)議接收側帶寬與鏈路層緩存之間的折中

60linw使用選擇性重傳的滑動窗口協(xié)議Continued143linwei@使用選擇性重傳的滑動窗口協(xié)議Continued61linContinued使用選擇性重傳的滑動窗口協(xié)議(2)144linwei@Continued使用選擇性重傳的滑動窗口協(xié)議(2)62使用選擇性重傳的滑動窗口協(xié)議(3)Continued145linwei@使用選擇性重傳的滑動窗口協(xié)議(3)Continued63使用選擇性重傳的滑動窗口協(xié)議(4)146linwei@使用選擇性重傳的滑動窗口協(xié)議(4)64linwei@cuc.非順序接收問題(a)窗口大小為7的初始狀態(tài).(b)7幀都已送出并接收，但是均未被確認(c)窗口大小為4的初始狀態(tài)(d)4幀都已送出并接收，但是均未被確認.147linwei@非順序接