第三章數(shù)據(jù)鏈路層zb2009

第三章 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層需要考慮的問題數(shù)據(jù)鏈路層的位置：物理層之上，網(wǎng)絡層之下利用物理層提供的服務（對網(wǎng)絡層屏蔽物理層的差異和實現(xiàn)細節(jié)）向網(wǎng)絡層提供可靠有效的通信目標：在數(shù)據(jù)鏈路層上，兩臺相鄰的機器之間實現(xiàn)可靠、有效的通信定位：解決點到點鏈路上傳輸信息存在的問題。鏈路：相鄰結(jié)點構(gòu)成的一條線路。對比：端到端3.1數(shù)據(jù)鏈路層的設(shè)計要點向網(wǎng)絡層提供一個定義良好的服務接口處理傳輸錯誤：差錯控制調(diào)節(jié)數(shù)據(jù)流，確保慢速的接收方不會被快速的發(fā)送方淹沒，并保證高效傳輸：流控這些機制并非只在鏈路層出現(xiàn)。3.1.1為網(wǎng)絡層提供的服務目標：將數(shù)據(jù)從源機器的網(wǎng)絡層傳輸?shù)侥繕藱C器的網(wǎng)絡層。服務3.1.1為網(wǎng)絡層提供的服務無確認的無連接服務不建立點到點間的邏輯連接不保證幀能夠被接收方正確接收適用于服務質(zhì)量較好的信道和實時性業(yè)務e.g.大多數(shù)的LAN有確認的無連接服務不建立點到點之間的邏輯連接接收方對收到的每一幀進行確認，提供可靠性。適用于不可靠的信道e.g.無線系統(tǒng)缺點：可能收到多個重復幀（如ACK報文丟失）注：在數(shù)據(jù)鏈路層上提供確認只是一種優(yōu)化而不是要求。有確認的有連接服務三個階段：連接建立；數(shù)據(jù)幀傳送；連接釋放需要建立源機器和目標機器之間的邏輯連接保證該連接上的每一幀都被正確接收，并且只接收一次保證接收幀的順序和發(fā)送幀的順序一致相當于為網(wǎng)絡層提供一個可靠的比特流面向連接的服務執(zhí)行的三個階段建立連接（初始化變量、計數(shù)器以及緩沖區(qū)）變量和計數(shù)器記錄哪些幀收到或未收到；緩沖區(qū)用于暫存要發(fā)送和剛收到的幀。傳送數(shù)據(jù)（幀）拆除連接（資源回收）例3.1.2成幀（framing）成幀：將物理層的位流分解成離散的幀數(shù)據(jù)鏈路層成幀的原因傳輸距離越長，越有可能發(fā)生錯誤,就需要重發(fā)整個數(shù)據(jù)塊，用較小的數(shù)據(jù)塊，每個數(shù)據(jù)塊出錯的可能就會減少，需要重發(fā)的數(shù)據(jù)隨之亦少判斷錯誤：源端機器計算每一幀的校驗和，目的端機器收到幀后重新計算校驗和在一個多點線路上,一般較理想的做法是不讓一個工作站長期占有線路,否則會引起其它工作站的長時間延遲接收器的緩存大小也有限制成幀方法字符計數(shù)法含字節(jié)填充的分界符法含位填充的分界標志法物理層編碼違例法字符計數(shù)法含字節(jié)填充的分界符法幀利用特殊的標志字節(jié)（FLAG）作為幀的開始和結(jié)束兩個連續(xù)的FLAG代表當前幀結(jié)束和下一幀開始。如果數(shù)據(jù)中出現(xiàn)FLAG，則進行字節(jié)填充（ESC）如果ESC出現(xiàn)在數(shù)據(jù)中，同樣進行字節(jié)填充含位填充的分解標志法數(shù)據(jù)幀可以包含任意長度的位（bit），每個字符也可以有任意的長度的位每一幀開始和結(jié)束都有一個特殊的位模式01111110（即flag）當數(shù)據(jù)中出現(xiàn)連續(xù)5個位“1”，發(fā)送方自動在其后插入一個位“0”接收方看到5個連續(xù)的“1”，自動刪去其后的“0”物理層編碼違例法只適用于物理介質(zhì)上的編碼方法含有冗余信息的網(wǎng)絡例：若數(shù)據(jù)采用曼徹斯特編碼，則可利用1-1或0-0用于幀分界。注：實際中，許多數(shù)據(jù)鏈路層協(xié)議聯(lián)合采用字符計數(shù)法和其他方法，以保證更大的可靠性3.1.3差錯控制（errorcontrol）問題：如何保證所有的幀最終被提交給目標機器的網(wǎng)絡層，并保持正確的順序解決方法接收方對所接收到的幀進行確認發(fā)送方使用定時器發(fā)送方對幀分配序號3.1.4流控制（flowcontrol）問題如何確保慢速的接收方不被快速的發(fā)送方淹沒解決基于反饋的流控制（feedback-basedflowcontrol）基于速率的流控制（rate-basedflowcontrol）3.2錯誤檢測和糾正傳輸錯誤一直存在。模擬線路，無線鏈路傳輸錯誤的分類：突發(fā)性錯誤、孤立錯誤。孤立錯誤影響面廣；突發(fā)性錯誤難以糾正。錯誤處理的策略：糾錯碼（error-correctioncode）：在發(fā)送的數(shù)據(jù)塊中包含足夠冗余信息，以便接收方可以推斷（識別）出原本發(fā)送的數(shù)據(jù)信息。FEC（forwarderrorcorrection）前向糾錯技術(shù)。廣泛用于無線鏈路檢錯碼（error-detectioncode）：所包含的冗余信息只能讓接收方判斷出發(fā)生了錯誤，但不能推斷出哪里發(fā)生了錯誤。通常接收方通過請求重傳來獲得正確數(shù)據(jù)塊。以上兩種不同的技術(shù)有不同的適用環(huán)境可靠信道，可使用檢錯碼：光纖鏈路錯誤頻發(fā)信道，更適于使用糾錯碼：無線鏈路3.2.2檢錯碼：用于誤碼率很低的鏈路CRC（CyclicRedundancyCheck，循環(huán)冗余校驗碼），也叫多項式編碼（Polynomialcode）基本思想：將位串看作是系數(shù)為0或1的多項式。1個k位的幀看作k-1次多項式的系數(shù)列表，該多項式共有k項，從xk-1到x0。(k-1)階多項式。110001-->x5+

x4+1多項式算法運算：模2運算（無進位借位）。等同于異或。如何使用CRC法發(fā)送方和接收方必須先約定一個生成多項式（generatorpolynomial）G(x)。其最高位和最低位必須為1。設(shè)一幀為m位，對應于多項式M(x)。在其后追加一個校驗和（checksum），使得追加校驗和之后的幀所對應的多項式能夠被G(x)除盡。當接收方收到帶校驗和的幀后，用G(x)去除它。如果余數(shù)不為0，則表明傳輸過程中有錯誤。計算校驗和的方法：設(shè)生成多項式G(x)為r階。在m位幀的尾部加上r個0位。對應多項式為xrM(x)利用模2除法，用G(x)去除xrM(x)。利用模2減法，從xrM(x)的位串中減去余數(shù)（小于等于r位）。結(jié)果就是將被傳輸?shù)膸ｒ炍坏膸?。其對應多項式為T(x)。CRC方法性能：可以檢測任何一位錯誤。一些特殊的多項式已經(jīng)成為國際標準。CRC-32用于IEEE802。實踐中計算CRC的方法：硬件構(gòu)造移位寄存器電路。多項式編碼校驗和的計算過程3.3基本數(shù)據(jù)鏈路協(xié)議基本假設(shè)假設(shè)物理層、數(shù)據(jù)鏈路層和網(wǎng)絡層都是獨立的進程，通過來回傳遞報文進行通信(各層協(xié)議的獨立性)假設(shè)機器A希望使用一個可靠的、面向連接的服務，向機器B發(fā)送一個長的數(shù)據(jù)流假設(shè)A的數(shù)據(jù)鏈路層在向網(wǎng)絡層請求數(shù)據(jù)總能夠成功假設(shè)機器不會崩潰，協(xié)議僅僅處理通信錯誤，不處理因為機器崩潰和重啟而引起的問題目的主機的數(shù)據(jù)鏈路層僅僅將數(shù)據(jù)遞交給網(wǎng)絡層就可以了，不進行其他處理數(shù)據(jù)鏈路層不考慮校驗和的計算假設(shè)數(shù)據(jù)鏈路層總是（通過查詢）等待事件發(fā)生關(guān)鍵數(shù)據(jù)類型數(shù)據(jù)類型boolean 表示“真”或“假”seq_nr 幀序號，總是在0到MAX_SEQ之間packet 數(shù)組，表示一個網(wǎng)絡層的分組frame_kind 幀類型（數(shù)據(jù)，ACK，NAK）frame 數(shù)據(jù)鏈路層的幀結(jié)構(gòu)

typedefstruct { frame_kindkind; /*幀類型*/ seq_nrseq; /*幀序號*/ seq_nrack; /*確認序號*/ packetinfo; /*幀的載荷，即網(wǎng)絡層分組*/}frame;/*數(shù)據(jù)鏈路層的幀。“幀頭＋凈荷”結(jié)構(gòu)*/關(guān)鍵函數(shù)wait_for_event 等待事件發(fā)生frame_arrival 幀到達事件cksum_err 收到一個校驗和出錯的幀timeout 定時器超時network_layer_ready 網(wǎng)絡層就緒ack_timeout ACK定時器超時to_network_layer 將數(shù)據(jù)遞交給網(wǎng)絡層;2、3層接口from_network_layer 申請網(wǎng)絡層數(shù)據(jù);2、3層接口to_physical_layer 將數(shù)據(jù)發(fā)送到物理線路上；1、2層接口from_physical_layer 從物理線路上獲取一個幀；1、2層接口start_timer 啟動（或重啟）定時器end_timer 關(guān)閉定時器start_ack_timer 啟動產(chǎn)生ACK的定時器end_ack_timer 結(jié)束產(chǎn)生ACK的定時器enable_network_layer 允許網(wǎng)絡層有分組發(fā)送時中斷鏈路層disable_network_layer 禁止網(wǎng)絡層有分組發(fā)送時中斷鏈路層3.1.1無限制單工協(xié)議假設(shè)數(shù)據(jù)只是單向傳送發(fā)送方和接收方的網(wǎng)絡層一直處于就緒狀態(tài)忽略處理時間緩存空間無限大通信信道永遠不會損壞或丟失幀一個無限制的單工協(xié)議3.3.2單工的停-等協(xié)議去掉協(xié)議1中接收方網(wǎng)絡層永遠就緒的假設(shè)通信信道無錯數(shù)據(jù)流量單向如何避免快的發(fā)送方淹沒慢的接收方接收方向發(fā)送方反饋信息發(fā)送方減速：每發(fā)一幀，就暫停發(fā)送，等待對方確認。Stop-and-wait.一個單工的停-等協(xié)議停-等協(xié)議的信道利用率Tf：數(shù)據(jù)發(fā)送時延（傳輸時延）Td：在線路上的傳播時延信道利用率Cr示例：衛(wèi)星鏈路例。單程傳播時間為270ms。數(shù)字傳輸服務用32Mbps,典型的4000位/幀。傳輸時間tf=4000/32M=125us,得：

a=270ms/125us=2160。對于簡單停止-等待應答通訊協(xié)議,效率只有0.00023!局域網(wǎng)例。距離范圍d＝1Km,數(shù)據(jù)速率為10Mbps。信號在銅線中的傳輸速率為V=2108m/s和500位/幀,tf=500/10M=50us,有：a=5us/50us=0.1,利用率0.833.通過Modem在語音級線路上傳輸數(shù)據(jù)例。數(shù)據(jù)速率9600bps,同樣V=2108m/s和500位/幀。傳輸距離任意,如d＝100Km,則：

a=(9600bps100Km)/(2108500bits)=9.610-3。效率等于0.981結(jié)論在部分場合(小a)，如低速、長幀、短距，簡單的停止-等待過程可提供較高的線路利用率。對除此之外的另一些場合，則希望有更巧妙的處理過程以提高傳輸效率。3.3.3有噪聲信道的單工協(xié)議前提：一個可能會出現(xiàn)錯誤的通信信道定時器：發(fā)送方經(jīng)過一段時間后仍然收不到幀的確認后，將再次重發(fā)該幀幀序號：供接收方區(qū)分重復幀；停等方式下，用1比特表示即可。ARQ（AutomaticRepeatreQuest，自動重復請求協(xié)議，或自動請求重發(fā)）s.seq:表示當前發(fā)送幀的序號一個支持重傳的肯定確認（ACK）協(xié)議-Senders.ack:表示已收到幀的序號一個支持重傳的肯定確認（ACK）協(xié)議-Receiver3.4滑動窗口協(xié)議：雙工數(shù)據(jù)傳送滑動窗口（slidingwindow）機制發(fā)送的每一個幀都被編號（保證幀順序接收）如果幀中的序號位為n，則幀編號的范圍是從0到2n-1，2n-1后從0重新開始在發(fā)送方和接收方分別設(shè)立兩個窗口：發(fā)送窗口（sendingwindow）和接收窗口（receivingwindow），每個窗口內(nèi)含有一個或一組序號的幀。發(fā)送窗口的大小WT代表在還沒有收到對方確認（ACK）信息的情況下發(fā)送端最多可以發(fā)送多少個數(shù)據(jù)幀。接收窗口的大小WR表示接收端只有當收到的數(shù)據(jù)幀的發(fā)送序號落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。接收方應具有一定的緩沖能力發(fā)送窗口的規(guī)則歸納如下：（1）發(fā)送窗口內(nèi)的幀是允許發(fā)送的幀，而不考慮有沒有收到確認。發(fā)送窗口右側(cè)所有的幀都是不允許發(fā)送的幀。（2）每發(fā)送完一個幀，允許發(fā)送的幀數(shù)就減1。但發(fā)送窗口的位置不變。（3）如果所允許發(fā)送的WT個幀都發(fā)送完了，但還沒有收到任何確認，那么就停止發(fā)送新的數(shù)據(jù)幀。這時，發(fā)送端就進入等待狀態(tài)。（4）每收到一個對窗口內(nèi)最小序號幀的確認，發(fā)送窗口就向前(即向右方)滑動一個幀的位置。接收窗口的規(guī)則歸納如下：（1）在接收端只有當收到的數(shù)據(jù)幀的發(fā)送序號落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。否則，就丟棄它。（2）每按序收到一個序號正確的幀，接收窗口就向前(即向右方)滑動一個幀的位置。發(fā)送窗口和接收窗口可以有不同的上下界、甚至可以有不同的大小。 捎帶確認（piggybacking）技術(shù)在雙向通信中經(jīng)常使用捎帶確認技術(shù)將確認幀延遲一小段時間，以便可以和本方下一個要發(fā)送的數(shù)據(jù)幀一起合并發(fā)送的技術(shù)。捎帶確認更好的利用了信道帶寬。3.4.11位滑動窗口協(xié)議：雙向即停等式：發(fā)送和接收窗口均等于1。3.3.2使用回退n幀（gobackn）技術(shù)的協(xié)議窗口大?。喊l(fā)送窗口為w（w最大為2n-1），接收窗口為1。接收方除了按序接收的那一幀外，不接收任何幀（丟棄）。發(fā)送方超時后，按順序重傳所有未確認幀。發(fā)送窗口大小為7Go-back-n方式下，發(fā)送窗口的大小限制如果序號位為n，則發(fā)送窗口w最大為2n-1ABF0.1RR1F1.1F1.2F2.2F3.2F7.2F0.2RR1::ABF0.xRR1F1.xF2.xF3.xF7.xF0.xRR1::Timeout=?窗口大小=8＝23窗口大小=8＝23注：這里，（F0.1)代表正發(fā)送第0幀，并期待對方的第1幀（已收到第0幀）。RR1表示收到第0幀，期待第1幀。ABF0.1RR1F1.1F1.2F2.2F3.2F7.2RR0::ABF0.xRR1F1.xF2.xF3.xF7.xRR1::Timeout窗口大小=7＝23-13.4.3使用選擇性重傳(SelectiveRepeat)的協(xié)議接收端接收所有序號落在接收窗口內(nèi)的幀，對于丟失或錯誤的幀，利用NAK指示發(fā)送端出錯，發(fā)送端僅僅發(fā)送丟失或錯誤的幀接收端需要設(shè)置緩沖區(qū)，來緩沖非順序到達的幀，以便順序提交給網(wǎng)絡層窗口大?。喊l(fā)送窗口和接收窗口都大于1。發(fā)送窗口大小為6選擇性重傳方式下，最大接收窗口的大小限制如果序號位為n，最大接收窗口大小≤2n/2=2n-1通常，發(fā)送窗口和接收窗口取一樣大。(a.b)發(fā)送窗口大小為7(c.d)發(fā)送窗口大小為43.6數(shù)據(jù)鏈路層協(xié)議示例3.6.1高級數(shù)據(jù)鏈路控制HDLC兩種鏈路配置：非平衡配置和平衡配置非平衡配置 平衡配置非平衡配置：支持點對點和點對多點平衡配置：支持點對點面向位（bit），使用位填充幀格式：地址域：用于多個終端的線路上區(qū)分不同終端控制域：序列號、確認等數(shù)據(jù)域：任何信息，可以任意長校驗和域：循環(huán)冗余碼，生成多項式16bit，CRC-CCITT幀分界：01111110（0x7E）三種類型的幀：通過控制域區(qū)分信息幀管理幀（監(jiān)控幀）：差錯控制和流控無序號幀：主要用于控制目的；在提供不可靠的無連接服務時，也可承載數(shù)據(jù)。3種幀的控制域：（a）信息幀（b）管理幀（c）無序號幀Modifier控制域：管理幀：4種ReceiveReady（RR）幀類型0（Type0）：正確接收，確認下一個希望收到的幀Reject（REJ）幀類型1：發(fā)生差錯，發(fā)送方將重傳該幀和其后所有未確認幀ReceiveNotReady（RNR）幀類型2：暫停接收，并確認下一個希望收到的幀。用于流控SelectiveReject（SREJ）幀類型3：選擇性拒絕，要求只重傳指定幀。只用于選擇性重傳無編號幀：指明幀類型，5比特（最多32種）。常用作鏈路建立/拆除：SABM（SetAsynchronousBalancedMode）：初始化線路DISC（Disconnect）：拆除連接UA（UnnumberedAcknowledgement）：對控制幀的確認UI（UnnumberedInformation）：無編號信息幀F(xiàn)RMR（FRaMeReject）：所收到的幀語義不正確(如非法幀，長度不對等)。舉例：復合站的鏈路建立與釋放數(shù)據(jù)傳輸階段：傳送信息幀，并結(jié)合RR、RNR、REJ等管理幀實現(xiàn)信息傳送、流控和差錯控制。P/F（Poll/Final,查詢/結(jié)束）比特。用法：用法1（非平衡方式下）：主站利用P=1請求從站發(fā)送數(shù)據(jù)，從站在傳輸結(jié)束后設(shè)置F=1；用法2（平衡方式下）：P=1時強迫對方立即返回管理幀，而不是等待一個捎帶確認。3.6.2Internet中的數(shù)據(jù)鏈路層點到點通信的應用場合本地路由器和遠端路由器的點到點連接主機到路由器的撥號連接。點到點鏈路PPP——點到點協(xié)議（PointtoPointProt