上海交大計算機網(wǎng)絡課件Chap3

第3章數(shù)據(jù)鏈路層定義和功能數(shù)據(jù)幀的組成可靠性傳輸數(shù)據(jù)鏈路層示例為網(wǎng)絡層提供一個較好的服務接口定義一個合適的傳輸差錯率對傳輸?shù)臄?shù)據(jù)流進行管理，以免快速的發(fā)送淹沒慢速的接收端數(shù)據(jù)鏈路層的定義數(shù)據(jù)鏈路層的上層是網(wǎng)絡層，數(shù)據(jù)鏈路層將借助于物理層為網(wǎng)絡層提供服務數(shù)據(jù)鏈路層的協(xié)議數(shù)據(jù)單元（PDU）是幀數(shù)據(jù)鏈路層的功能數(shù)據(jù)鏈路層的任務是把網(wǎng)絡層的數(shù)字數(shù)據(jù)組合成幀，并加上一定的校驗碼后交物理層物理層用不同的信號表示二進制數(shù)據(jù)位，從而把幀用一段連續(xù)的信號串表示并傳送到目的主機通過目的主機的物理層和數(shù)據(jù)鏈路層送到網(wǎng)絡層，也就是為源和目的主機的網(wǎng)絡層之間提供一條可靠的數(shù)據(jù)鏈路相連、物理鏈路和數(shù)據(jù)鏈路所謂相連，可以理解為物理介質的連接，但當采用多路復用技術時也可以是信道的連接，其特征為：所傳輸?shù)臄?shù)據(jù)是按序的物理鏈路：一段無源的點到點的物理連接，中間沒有任何交換節(jié)點數(shù)據(jù)鏈路：包括一條物理連接和為實現(xiàn)數(shù)據(jù)傳輸而在兩端配置的硬件及其相關的通信協(xié)議數(shù)據(jù)鏈路層服務的區(qū)分規(guī)則數(shù)據(jù)鏈路層的服務是通過有無連接、有無確認來區(qū)分的無確認無連接的服務有確認無連接的服務有確認有連接的服務確認和連接確認：接收方在收到數(shù)據(jù)幀后，必須給發(fā)送方發(fā)回一個確認面向連接：發(fā)送方和接收方在傳輸數(shù)據(jù)之前必須建立一條數(shù)據(jù)鏈路，傳輸結束后必須釋放該鏈路數(shù)據(jù)鏈路層的服務無確認無連接的服務有確認無連接的服務有確認有連接的服務無確認面向無連接的服務

無確認是指接收方在收到數(shù)據(jù)幀后，毋需發(fā)回一個確認無連接的服務是指在數(shù)據(jù)傳輸前毋需建立數(shù)據(jù)鏈路物理線路的連接并非意味著提供了有連接的服務無確認并非不可靠，其可靠性可由上層負責 例如：局域網(wǎng)共享信道不需要、也不允許建立連接信道較為理想，數(shù)據(jù)傳輸?shù)恼`碼率很低即使出錯或丟失由上層負責恢復數(shù)據(jù)鏈路層的服務無確認無連接的服務有確認無連接的服務有確認有連接的服務有確認面向無連接的服務

使用前不建立連接，即不建立數(shù)據(jù)鏈路，但每幀傳輸必須得到確認這在信號傳播延時較大、線路狀態(tài)不一定很可靠的情況下是有效的 例如：無線通信如建立連接，則信道使用率很低然而，由于數(shù)據(jù)傳輸?shù)恼`碼率相對較高，所以確認是必要的數(shù)據(jù)鏈路層的服務無確認無連接的服務有確認無連接的服務有確認有連接的服務有確認的面向連接服務

使用前先建立連接，即先建立數(shù)據(jù)鏈路，并且每幀的傳輸必須得到確認有連接的服務必須在使用前先建立連接（即建立數(shù)據(jù)鏈路），然后使用，最后釋放連接 例如：電話電話是一種實時的應用，如不是面向連接，則實時性難以得到保證電話是一對一的、雙向的數(shù)據(jù)傳輸數(shù)據(jù)的可靠傳輸將傳輸?shù)男畔⒔M合成幀校驗和重發(fā)流量控制保證直接相連的兩臺主機的可靠性傳輸?shù)?章數(shù)據(jù)鏈路層定義和功能數(shù)據(jù)幀的組成可靠性傳輸數(shù)據(jù)鏈路層示例數(shù)據(jù)幀的組成字符計數(shù)法帶字符填充的首尾界符法帶位填充的首尾標志法

物理層編碼違例法幀的組成必須保證能識別一個完整的幀，并保證一旦出現(xiàn)傳輸差錯而導致前一個幀丟失時，也必須能識別后一個幀，即具有幀再同步能力字符計數(shù)法假設幀的長度用一個字節(jié)表示，并作為幀的頭部一旦幀長度計數(shù)被誤讀，將無法再同步，所以不能采用

第1幀第2幀幀長度計數(shù)錯幀長度計數(shù)第1幀第4幀第3幀第2幀5123456789801234568789012351234767898012345687890123TnbmP188Fig.3-4字符計數(shù)成幀法數(shù)據(jù)幀的組成字符計數(shù)法帶字符填充的首尾界符法帶位填充的首尾標志法

物理層編碼違例法幀的組成必須保證能識別一個完整的幀，并保證一旦出現(xiàn)傳輸差錯而導致前一個幀丟失時，也必須能識別下一個幀，即具有幀再同步能力帶字符填充的首尾界符法

用特殊的字符作為幀頭和幀尾界符FLAGHeaderPayloadfieldTrailerFLAG這是一種面向字符的幀格式，所傳輸?shù)臄?shù)據(jù)都是字符（ASCII或EBCDIC字符），但幀中不允許出現(xiàn)幀界符標志，在面向字符的串型通信中常使用這種格式(PPP)接收方一旦丟失了一個FLAG，只要繼續(xù)搜索下一個FLAG，就可重新確定幀邊界，即具有再同步能力TnbmP189Fig.3-5(a)由Flag標志的一個幀面向字符的幀格式面向字符的幀格式不適宜傳輸數(shù)據(jù)中包含二進制數(shù)的幀，因為在包含二進制數(shù)的幀中很可能出現(xiàn)與FLAG相同的bit序列（通常FLAG用ASCII字符7EH定義）一種方法是在二進制數(shù)中偶然出現(xiàn)的FLAG前再插入一個ESC（ASCII字符1BH），這種方法稱為字符填充法41337E5C4B0C41331B5C4B0C41331B

7E5C4B0C41331B

1B5C4B0C41331B

7E5C4B0C41331B1B5C4B0C41331B

1B1B

7E5C4B0C41331B

1B1B1B5C4B0C數(shù)據(jù)幀的組成字符計數(shù)法帶字符填充的首尾界符法帶位填充的首尾標志法

物理層編碼違例法幀的組成必須保證能識別一個完整的幀，并保證一旦出現(xiàn)傳輸差錯而導致前一個幀丟失時，也必須能識別下一個幀，即具有幀再同步能力帶位填充的首尾標志法

在面向二進制位的同步串行通信中常使用帶位填充的首尾標志格式，如HDLC這是一種面向二進制位的幀格式，把所有需傳輸?shù)臄?shù)據(jù)（不論是字符或表示一個浮點數(shù)的二進制位串，還是一個MP3的文件）一字排開，并以特殊的位模式01111110作為幀標志，即一個幀的開始（同時標志前一個幀的結束）如果由于干擾，一個幀標志沒有被正確接收，則繼續(xù)掃描接收串，一旦掃描到01111110，即新的一幀從此開始，即具有再同步能力即使字符也并非都是8位的，東方文字是16位，UNICODE是16位面向bit的幀格式當幀中出現(xiàn)一個與幀標志相同的位串01111110，則在連續(xù)5個1后自動插入一個0，即變成01111101，接收方將自動刪除第5個1后的0這稱為位插入法，也稱為透明傳輸011011111111111111110010011011111011111011111010010011011111111111111110010TnbmP190Fig.3-6(a)(b)(c)位插入法示例數(shù)據(jù)幀的組成字符計數(shù)法帶字符填充的首尾界符法帶位填充的首尾標志法

物理層編碼違例法幀的組成必須保證能識別一個完整的幀，并保證一旦出現(xiàn)傳輸差錯而導致前一個幀丟失時，也必須能識別下一個幀，即具有幀再同步能力物理層編碼違例法

在曼切斯特編碼中，連續(xù)高電平或連續(xù)低電平可用作幀界符采用冗余編碼技術，如曼切斯特編碼，即對連續(xù)兩個信號進行采樣，可得到一個二進制位數(shù)據(jù)0：低-高電平對數(shù)據(jù)1：高-低電平對高-高電平對和低-低電平對沒有使用，如在二進制編碼中出現(xiàn)則稱為編碼違例，但這兩種違例編碼正好可用作幀界符，在令牌環(huán)網(wǎng)中使用編碼違例格式第3章數(shù)據(jù)鏈路層定義和功能數(shù)據(jù)幀的組成可靠性傳輸數(shù)據(jù)鏈路層示例可靠性傳輸差錯控制：校驗、重發(fā)和序號避免幀錯誤的保證：幀的校驗避免幀丟失的保證：超時和重發(fā)避免幀重復的保證：幀有序號流量控制：窗口協(xié)議發(fā)送方和接收方之間傳輸速率的協(xié)調協(xié)議描述和驗證差錯控制

確認數(shù)據(jù)幀丟失重復幀如何保證數(shù)據(jù)幀的正常傳輸，將通過三種手段處理三種可能出現(xiàn)的情況：確認

接收方在收到了正確的幀后向發(fā)送方發(fā)肯定性確認；如收到的幀有問題，則發(fā)否定性確認，此時發(fā)送方將重發(fā)此幀確認的前提是必須經(jīng)過差錯檢測差錯檢測和校正

差錯的產(chǎn)生主要是在傳輸時，數(shù)據(jù)中的一位或幾位因噪聲干擾而出錯噪聲分兩種：

信道所固有的、持續(xù)存在的熱噪聲外界突發(fā)原因而造成的隨機的沖擊噪聲通常接收方應能檢錯，甚至糾錯糾錯碼和檢錯碼糾錯碼：海明（Hamming）碼檢錯碼：校驗和（CheckSum）塊校驗碼（BlockCheckCode）循環(huán)冗余檢錯碼CRC

（CyclicRedundancyCheck）校驗和

算法簡單、實現(xiàn)容易，但檢錯強度較弱以16位為例：4865H+6C6CH+6F20H+776FH+726CH+642EH+進位=71FCHHelloworld.48656C6C6F20776F726C642E71FC將發(fā)送的數(shù)據(jù)看成是二進制整數(shù)序列，并劃分成一段段規(guī)定的長度（如8位、16位、32位等），計算它們的和，如計算和時有進位，則將進位加到最后的校驗和中，并將校驗和與數(shù)據(jù)一起發(fā)送；在接收端，重新計算校驗和，并與接收到的原校驗和比較，如要傳輸“Helloworld.”糾錯碼和檢錯碼糾錯碼：海明（Hamming）碼檢錯碼：校驗和（CheckSum）塊校驗碼（BlockCheckCode）循環(huán)冗余檢錯碼CRC

（CyclicRedundancyCheck）塊校驗碼塊校驗碼BCC（BlockCheckCode）簡單常用，但檢錯的強度較弱，如在同一列上有偶數(shù)位錯，則不能檢測 如傳輸?shù)臄?shù)據(jù)都是ASCII字符（即面向字符，這在應用中很多），每個字符進行奇偶校驗，然后把所有的字符（連同奇偶位）進行異或運算，運算結果即為其塊校驗碼，通常發(fā)送端在發(fā)送完數(shù)據(jù)區(qū)的結束標志后發(fā)送BCC，接收端一邊接收數(shù)據(jù)一邊計算BCC，最后與接收到的BCC比較，以確認所接收到的數(shù)據(jù)正確與否 如“Helloworld.”，采用偶校驗，校驗后的字符序列為：48H65H6CH6CH6FHA0H77H6FH72H6CHE4H2EH=2EHHelloworld.48656C6C6FA0776F726CE42E2E糾錯碼和檢錯碼糾錯碼：海明（Hamming）碼檢錯碼：校驗和（CheckSum）塊校驗碼（BlockCheckCode）循環(huán)冗余檢錯碼CRC

（CyclicRedundancyCheck）循環(huán)冗余檢錯碼CRC任何一個k位的幀都可看成為一個k-1次的多項式M(x)的系數(shù)列表

如：1011001看成是多項式x6+x4+x3+x0的系數(shù)列表設定一個生成多項式G(x)，G(x)為r階，k>r如xrM(x)/G(x)=Q(x)+R(x)/G(x)其中Q(x)為商、R(x)為余數(shù)，R(x)即為M(x)的CRC碼將CRC碼接在幀后一起發(fā)送，即發(fā)送數(shù)據(jù)為xrM(x)+R(x)

二進制運算中，減法和加法都做異或運算：0+1=1,1+1=0

因為(xrM(x)-R(x))一定能被G(x)整除，即余數(shù)為0，則接收方只要計算CRC，并所得余數(shù)為0即為正確CRC碼計算舉例如一幀為1101011011即：M(x)=x9+x8+x6+x4+x3+x+1

G(x)=x4+x+1

T(x)=x4M(x) =x4(x9+x8+x6+x4+x3+x+1) =x13+x12+x10+x8+x7+x5+x4

CRC碼計算舉例（續(xù)1）幀：1101011011除數(shù)：10011實際傳輸幀：11000010101001111010110110000100111001110011000010000000010000000010100000010110000010110100110101000000101001001101110000001110余數(shù)11010110111110幀數(shù)據(jù)余數(shù)TnbmP198Fig.3-8CRC碼計算舉例CRC碼計算舉例（續(xù)2）

11010110110000/10011=1100001010……1110

即11010110110000+1110能被10011整除（注：模2運算的加、減和異或，其運算結果相同）發(fā)送方發(fā)送的是T(x)+R(x)[能被G(x)整除]，如接收方收到的是T(x)+R(x)+E(x)，除非E(x)是G(x)的整倍數(shù)，否則不能被整除，即都能被檢測到已出錯三個生成多項式國際標準

CRC-12：x12+x11+x3+x2+x1+1

用于字符長度為6位

CRC-16：x16+x15+x2+1

用于字符長度為8位

CRC-CCITT

：x16+x12+x5+1

用于字符長度為8位

IEEE802：x32+x26+x23+x22+x16+x12+x11+x10+x8 +x7+x5+x4+x2+x1+1CCITT：ConsultativeCommitteeonInternationalTelegraphyandTelephone國際電報和電話咨詢委員會，即現(xiàn)在的ITU-TITU-T：InternationalTelecommunicationsUnion–TelecommunicationsStandardizationSector國際電信聯(lián)盟–電信標準分部差錯控制

確認數(shù)據(jù)幀丟失重復幀如何保證數(shù)據(jù)幀的正常傳輸：通過三種手段處理三種可能出現(xiàn)的情況：數(shù)據(jù)幀丟失

通過發(fā)送方的重發(fā)定時器（超時）解決超時（TimeOut）：在傳輸過程中，如果所發(fā)送的幀丟失，接收方根本沒有收到，不可能發(fā)送確認幀（包括否定性確認），當然發(fā)送方也不可能等待收到如何信息，所以發(fā)送方每發(fā)送一幀，就啟動一個重發(fā)定時器，在所設定的時間內，一般都應該收到確認，如收不到確認，則在重發(fā)定時器溢出后，再重發(fā)此幀差錯控制

確認數(shù)據(jù)幀丟失重復幀如何保證數(shù)據(jù)幀的正常傳輸：通過三種手段處理三種可能出現(xiàn)的情況：重復幀

重發(fā)機制也包括當接收方發(fā)送的確認幀丟失而導致發(fā)送方的重發(fā)定時器超時而重發(fā)由于接收方確認幀的丟失，導致發(fā)送方多次發(fā)送同一幀，接收方也將多次收到同一幀，為能識別是否為相同的幀，應該在幀格式中增加一個幀的編號（序號）幀的格式基于上述討論，一個數(shù)據(jù)鏈路層的幀至少應該包括下列內容：信息校驗信息

infoCRC確認號Ack_no幀序號Seq_no幀類型type幀頭可靠性傳輸差錯控制：校驗、重發(fā)和序號避免幀錯誤的保證：幀的校驗避免幀丟失的保證：超時和重發(fā)避免幀重復的保證：幀有序號流量控制：窗口協(xié)議發(fā)送方和接收方之間的協(xié)調協(xié)議描述和驗證流量控制

發(fā)送速率和接收速率的匹配即流量控制如接收方的處理能力低于發(fā)送方，即使傳輸中沒有出錯，也可能被“淹沒”，所以通常在接收方的緩沖區(qū)到達一定量時，應及時通知發(fā)送方，暫停發(fā)送，等候通知，這就是流量控制機制基本數(shù)據(jù)鏈路協(xié)議滑動窗口協(xié)議A、B兩臺主機要求可靠的、面向連接的通信，在接收方的數(shù)據(jù)鏈路層，目前正運行的是wait_for_event(&event)，即等待某個事件發(fā)生基本數(shù)據(jù)鏈路協(xié)議可以這樣理解：在一臺主機中，物理層、數(shù)據(jù)鏈路層、網(wǎng)絡層等，都有各自的進程在運行，并且假設：wait_for_event(&event)的參數(shù)如event=checksum_err，意即所接收幀的校驗和錯，應考慮不發(fā)送確認幀ACK，或發(fā)送否定性確認幀NAK如event=frame_arrival，即幀已到達并校驗正確，應調用from_physical_layer，從物理層取得幀，并檢查幀頭的控制信息，如一切正常，則僅把其中的分組交網(wǎng)絡層一系列過程和數(shù)據(jù)結構的定義：TnbmP202Fig.3-9

如發(fā)生了某個事件，此過程將返回參數(shù)event，

event有兩個取值：checksum_err（CRC錯） frame_arrival（正確收到）三個基本數(shù)據(jù)鏈路協(xié)議（協(xié)議1-3）無限制的單工協(xié)議（協(xié)議1）

TnbmP205Fig.

3-10一種無限制的單工協(xié)議單工的停–等協(xié)議（協(xié)議2）

TnbmP207Fig.

3-11一個單工的停–等協(xié)議噪聲信道的單工協(xié)議（協(xié)議3）

TnbmP210Fig.

3-12一個肯定性確認和超時重發(fā)協(xié)議無限制的單工協(xié)議鏈路是理想的傳輸通道，所傳輸?shù)娜魏螖?shù)據(jù)既不會出錯也不會丟失

即：不需校驗，也不可能出現(xiàn)重發(fā)，毋需差錯控制不管發(fā)送方以怎樣的速率發(fā)送數(shù)據(jù)，接收方都能及時接收并處理

即接收端處理器的處理速度無限高，處理時間可忽略不計，緩沖區(qū)空間無限大，毋需流量控制TnbmP205Fig.

3-10一種無限制的單工協(xié)議

一種理想的環(huán)境，理想的協(xié)議，假定：協(xié)議1：SENDERvoidsender1(void){frames;packetbuffer;

while(true){ from_network_layer(&buffer); =buffer; to_physical_layer(&s); }}協(xié)議1：RECEIVERvoidreceiver1(void){framer;

event_typeevent;

while(true){

wait_for_event(&event);

from_physical_layer(&r);

to_network_layer(&); }}三個基本數(shù)據(jù)鏈路協(xié)議（協(xié)議1-3）無限制的單工協(xié)議（協(xié)議1）

TnbmP205Fig.

3-10一種無限制的單工協(xié)議單工的停–等協(xié)議（協(xié)議2）

TnbmP207Fig.

3-11一個單工的停–等協(xié)議噪聲信道的單工協(xié)議（協(xié)議3）

TnbmP210Fig.

3-12一個肯定性確認和超時重發(fā)協(xié)議單工的停

–等協(xié)議鏈路是理想的傳輸通道，所傳輸?shù)娜魏螖?shù)據(jù)既不會出錯也不會丟失 考慮實際情況，接收方不可能具有足夠高的CPU處理能力來及時處理所有的接收幀，也不可能具有永不溢出的緩沖區(qū) 即：毋需差錯控制，但必須進行流量控制這里的單工，其實是半雙工，所謂流量控制是發(fā)送方必須收到前一幀的確認后才允許發(fā)送下一幀，接收方發(fā)出確認，意味著前一幀已接收并交網(wǎng)絡層，準備接收下一幀TnbmP207Fig.

3-11一個單工的停

–等協(xié)議

協(xié)議1中第一個假設保留，第二個假設撤消，假定：協(xié)議2：SENDERvoidsender2(void){frames;packetbuffer;

event_typeevent;

while(true){

from_network_layer(&buffer);

=buffer;

to_physical_layer(&s);

wait_for_event(&event);}}協(xié)議2：RECEIVERvoidreceiver2(void){framer,s;

event_typeevent;

while(true){

wait_for_event(&event);

from_physical_layer(&r);

to_network_layer(&);

to_physical_layer(&s);}}協(xié)議2說明協(xié)議2是一個半雙工協(xié)議，即發(fā)送方和接收方使用同一信道，但發(fā)送方發(fā)送數(shù)據(jù)幀的過程和接收方發(fā)送確認幀的過程是嚴格交替的協(xié)議2中，發(fā)送方發(fā)送的數(shù)據(jù)幀和接收方發(fā)送的確認幀采用相同的幀格式，發(fā)送方發(fā)送的數(shù)據(jù)幀中僅包含數(shù)據(jù)，接收方發(fā)送的確認幀數(shù)據(jù)為空，僅為一個信號由于協(xié)議2定義的是一個理想的傳輸通道，所以不考慮傳輸差錯問題三個基本數(shù)據(jù)鏈路協(xié)議（協(xié)議1-3）無限制的單工協(xié)議（協(xié)議1）

TnbmP205Fig.

3-10一種無限制的單工協(xié)議單工的停–等協(xié)議（協(xié)議2）

TnbmP207Fig.

3-11一個單工的停–等協(xié)議噪聲信道的單工協(xié)議（協(xié)議3）

TnbmP210Fig.

3-12一個肯定性確認和超時重發(fā)協(xié)議噪聲信道的單工協(xié)議噪聲信道的差錯控制采用定時器實現(xiàn)差錯控制簡單的重發(fā)機制存在的問題較為實用的噪聲信道單工協(xié)議噪聲信道的差錯控制幀的數(shù)據(jù)出錯：

幀數(shù)據(jù)中若干位出錯，通常CRC都能檢測到

幀的丟失：

一旦幀頭出錯，則該幀丟失幀的重復：

如發(fā)送方有重發(fā)機制，當接收方發(fā)出的ACK丟失時，接收方將收到發(fā)送方重發(fā)的重復幀

在噪聲信道中應考慮傳輸有差錯的情況，所謂差錯：噪聲信道的單工協(xié)議噪聲信道的差錯控制采用定時器實現(xiàn)差錯控制簡單的重發(fā)機制存在的問題較為實用的噪聲信道單工協(xié)議采用定時器實現(xiàn)差錯控制如在協(xié)議2的基礎上增加一個重發(fā)定時器，當發(fā)送方發(fā)送完一幀后啟動一個重發(fā)定時器并等待確認無論是由于接收方收到一個錯幀而不發(fā)ACK（無否定性確認機制），還是由于幀標志錯而導致幀的丟失，接收方不可能發(fā)送ACK，或者接收方所發(fā)送的ACK丟失，發(fā)送方的重發(fā)定時器都將超時，重發(fā)定時器一旦超時則立即重發(fā)，以實現(xiàn)差錯控制噪聲信道的單工協(xié)議噪聲信道的差錯控制采用定時器實現(xiàn)差錯控制簡單的重發(fā)機制存在的問題較為實用的噪聲信道單工協(xié)議簡單的重發(fā)機制存在的問題效率較低如接收方收到的幀出錯或者整個數(shù)據(jù)幀丟失，則不發(fā)ACK（無否定性確認機制），發(fā)送方將在重發(fā)定時器超時后重發(fā)，直至正確，然而重發(fā)定時器的設定時間可能是正常ACK返回時間的2倍、3倍和更多，所以效率極低接收方會收到重復幀

如接收方收到了正確的數(shù)據(jù)幀并發(fā)送了ACK，但此ACK丟失，發(fā)送方在重發(fā)定時器超時后重發(fā)此幀，這樣，接收方的數(shù)據(jù)鏈路層會收到兩個完全相同的幀，其網(wǎng)絡層將收到兩個完全相同的分組，這是不允許的噪聲信道的單工協(xié)議噪聲信道的差錯控制采用定時器實現(xiàn)差錯控制簡單的重發(fā)機制存在的問題較為實用的噪聲信道單工協(xié)議較為實用的噪聲信道單工協(xié)議這里的噪聲信道單工協(xié)議，其實是噪聲信道半雙工協(xié)議協(xié)議3的幀格式中定義一個幀序號字段發(fā)送方要記錄下一個準備發(fā)送的順序號接收方要記錄下一個期待接收的順序號由于是半雙工噪聲信道，發(fā)送和接收過程將嚴格交替協(xié)議3只定義了肯定性確認幀ACK，而沒有定義否定性確認NAK接收方收到一個正確（CRC正確）的幀，即便不是所期待的幀（即重復幀），都必須發(fā)送一個確認幀ACK也稱為ARQ協(xié)議：AutomaticRepeatreQuest協(xié)議3中幀格式幀類型：有數(shù)據(jù)幀DATA和確認幀ACK（肯定性確認）兩種類型幀序號：僅一個bit，在發(fā)送方的數(shù)據(jù)幀中是該幀的序號0/1，在接收方的確認幀中是接收方期待接收的下一幀的序號1/0協(xié)議3:SENDERvoidsender3(void){

next_frame_to_send=0;

from_network_layer(&buffer);while(true){=buffer;s.seq=next_frame_to_send;

to_physical_layer(&s)；start_timer(s.seq) ；

wait_for_event(&event); if(event==frame_arrival){from_physical_layer(&s);if(s.ack==next_frame_to_send){

stop_timer(s.ack);

from_network_layer(&buffer);

inc(next_frame_to_send);}}}}TnbmP210Fig.3-12一個肯定性確認和超時重發(fā)協(xié)議

協(xié)議3:RECEIVERvoidreceiver3(void){frame_expected=0;while(true){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);

inc(frame_expected);}

s.ack=1-frame_expected;

to_physical_layer(&s);}}}}流量控制

發(fā)送速率和接收速率的匹配即流量控制如接收方的處理能力低于發(fā)送方，即使傳輸中沒有出錯，也可能被“淹沒”，所以通常在接收方的緩沖區(qū)到達一定量時，應及時通知發(fā)送方，暫停發(fā)送，等候通知，這就是流量控制機制基本數(shù)據(jù)鏈路協(xié)議滑動窗口協(xié)議協(xié)議3尚存的問題由于數(shù)據(jù)是單向傳輸?shù)?，?shù)據(jù)傳輸和應答不會同時傳輸，因此可使用半雙工信道（通常半雙工僅需單信道），但不能實現(xiàn)同時雙向傳輸。也可以用兩根信道，但傳輸應答的信道效率較低如發(fā)送方的重發(fā)定時器設定的初始值較小，可能出現(xiàn)系統(tǒng)死鎖雙向傳輸解決方案但在實際情況下，一般需要的是雙向傳輸雙向傳輸?shù)慕鉀Q方案：用四條信道：兩條數(shù)據(jù)，兩條應答

但信道利用率很低用兩條信道：一條A到B，另一條B到A用不同的幀類型標志區(qū)分數(shù)據(jù)幀和確認幀采用捎帶確認（piggybacking）進一步提高信道效率滑動窗口協(xié)議收、發(fā)使用兩條信道

發(fā)送方可連續(xù)發(fā)送多幀，接收方接收到一幀后就從另一個信道發(fā)回一個ACK，為提高信道使用效率，接收方可使用捎帶確認幀是有序號的

即使過早超時而導致的重發(fā)也可根據(jù)幀的序號來避免幀的重復滑動窗口原理（設WT=1，WR=1）發(fā)送方接收方TnbmP213Fig.3-13一個大小為1、有3位序列號的滑動窗口

(a)(b)(c)(d)1652437016524370652437016524370116524370165243701652437065243701正發(fā)送0#幀等待0#幀ACK收到ACK正在處理正發(fā)送1#幀三個滑動窗口協(xié)議（協(xié)議4-6）發(fā)送窗口WT=1，接收窗口WR=1TnbmP215Fig.

3-14一位滑動窗口協(xié)議（協(xié)議4）發(fā)送窗口WT=7，接收窗口WR=1TnbmP220Fig.

3-17后退n幀的滑動窗口協(xié)議（協(xié)議5）發(fā)送窗口WT=4，接收窗口WR=4TnbmP224Fig.

3-19選擇性重發(fā)滑動窗口協(xié)議（協(xié)議6）一位滑動窗口協(xié)議A和B之間的通信是雙向的，A和B都正運行一個滑動窗口協(xié)議，其中包含了發(fā)送和接收的功能幀序號僅用1bit表示，A和B的發(fā)送窗口WT=1、接收窗口WR=1，窗口大小即緩沖區(qū)的個數(shù)發(fā)送方發(fā)送下一個數(shù)據(jù)幀必須在收到接收方的確認之后接收方采用捎帶確認，并假設需確認時，接收方總能從網(wǎng)絡層取到待發(fā)送的數(shù)據(jù)，以便捎帶確認凡接收到一個正確的幀，即便不是所期待的幀（可能是重復幀），也必須發(fā)一個確認一位滑動窗口協(xié)議voidprotocol4(void){next_frame_to_send=0;

frame_expected=0;

from_network_layer(&buffer);

=buffer;

s.seq=next_frame_to_send;

s.ack=1-frame_expected;

to_physical_layer(&s);

start_timer(s.seq);TnbmP215Fig.

3-14（協(xié)議4）while(true){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);inc(frame_expected);}if(r.ack==next_frame_to_send){stop_timer(r.ack);from_network_layer(&buffer); inc(next_frame_to_send);}}

=buffer;s.seq=next_frame_to_send; s.ack=1-frame_expected to_physical_layer(&s);

start_timer(s.seq)}}三個滑動窗口協(xié)議（協(xié)議4-6）發(fā)送窗口WT=1，接收窗口WR=1TnbmP215Fig.

3-14一位滑動窗口協(xié)議（協(xié)議4）發(fā)送窗口WT=7，接收窗口WR=1TnbmP220Fig.

3-17后退n幀的滑動窗口協(xié)議（協(xié)議5）發(fā)送窗口WT=4，接收窗口WR=4TnbmP224Fig.

3-19選擇性重發(fā)滑動窗口協(xié)議（協(xié)議6）后退n幀的滑動窗口協(xié)議協(xié)議4的主要問題是信道利用率太低

發(fā)送端等待發(fā)送下一幀的時間至少是發(fā)送端到接收端信號傳播時間的兩倍，沒有充分利用兩條信道的傳輸能力信道的利用率定義為 數(shù)據(jù)發(fā)送時間/從數(shù)據(jù)開始發(fā)送到ACK返回的總耗時協(xié)議5是一個發(fā)送管道化（pipelining）的協(xié)議

在等待ACK的時間內連續(xù)發(fā)送出錯后重發(fā)必須后退n幀 一旦重發(fā)定時器超時，必須將已發(fā)的n幀全部重發(fā)后退n幀的滑動窗口協(xié)議圖例有一個差錯時后退n幀（WT=7，WR=1）超時間隔出錯時間被數(shù)據(jù)鏈路層丟棄的幀發(fā)收0ACK0ACK1ACK2ACK3ACK4ACK512543287654387601EDDDDDD25436TnbmP218Fig.3-16(a)

退后n幀協(xié)議（gobackn）設幀序號由3個bit表示，即0~7，并且WT=7

,WR=1設發(fā)送方有大量數(shù)據(jù)待發(fā)送給對方，由于WT=7，即有7個發(fā)送緩沖區(qū)，所以可連續(xù)發(fā)送7幀，并每發(fā)送一幀將啟動一個重發(fā)定時器，但緩沖區(qū)的覆蓋（窗口的旋轉）必須在收到ACK之后，因為一旦該幀的重發(fā)定時器超時，必須將原緩沖區(qū)內的幀重發(fā)退后n幀協(xié)議（gobackn）續(xù)接收方采用捎帶確認，并假設需確認時，接收方總能從網(wǎng)絡層取到待發(fā)送給發(fā)送方的的數(shù)據(jù)，以便捎帶確認(piggybacking)由于接收方的WR=1，如期待接收的幀出錯，則丟棄此幀及以后所有收到的幀，不發(fā)確認（無NAK機制）當發(fā)送方出現(xiàn)超時（錯幀的TimeOut）后，重發(fā)自該幀起的所有已發(fā)送幀（在當前的緩沖區(qū)中），如發(fā)送方連續(xù)發(fā)送了7幀（2~8），而2#幀無確認，超時后，必須從2#幀起全部重發(fā)后退n幀的滑動窗口協(xié)議程序01234567Next_frame_to_sendack_expectednbuffered=3voidprotocol5(void){

enable_network_layer();

ack_expected=0;next_frame_to_send=0;frame_expected=0;

nbuffered=0;TnbmP220Fig.3-17（協(xié)議5）while(true){wait_for_event(&event);switch(event){casenetwork_layer_ready：

network_layer_ready處理；

caseframe_arrival:frame_arrival處理；

casecksum_err:break；忽略壞幀

casetimeout：timeout處理；

}if(nbuffered<MAX_SEQ)enable_network_layer();elsedisable_network_layer();}}network_layer_ready處理:裝配一個數(shù)據(jù)幀并發(fā)送，發(fā)送緩沖區(qū)數(shù)+1，準備發(fā)送下一數(shù)據(jù)幀from_network_layer(&buffer[next_frame_to_send]);nbuffered=nbuffered+1;send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);frame_arrival處理：如收到一個數(shù)據(jù)幀則交網(wǎng)絡層，并期待接收下一數(shù)據(jù)幀如收到一個ACK則釋放一個緩沖區(qū)定時器復位，并期待接收下一ACKfrom_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);

inc(frame_expected); }while(between(ack_expected,r.ack,next_frame_to_send)){nbuffered=nbuffered-1;

stop_timer(ack_expected);

inc(ack_expected);}TimeOut處理：從等待確認的幀開始全部重發(fā)next_frame_to_send=ack_expected;for(i=1;i<=nbuffered;i++){

send_data(next_frame_to_send,frame_expected,buffer);

inc(next_frame_to_send);}后退n幀的滑動窗口協(xié)議總結

（WT=2n-1

,WR=1）協(xié)議5，即管道化（pipelining）協(xié)議是一個很實用的點對點可靠傳輸?shù)膮f(xié)議，特別適用于差錯率較低的信道，此時，信道利用率很高如果幀序號由n位組成，則發(fā)送窗口WT=2n-1

，接收窗口WR=1三個滑動窗口協(xié)議（協(xié)議4-6）發(fā)送窗口WT=1，接收窗口WR=1TnbmP215Fig.

3-14一位滑動窗口協(xié)議（協(xié)議4）發(fā)送窗口WT=7，接收窗口WR=1TnbmP220Fig.

3-17后退n幀的滑動窗口協(xié)議（協(xié)議5）發(fā)送窗口WT=4，接收窗口WR=4TnbmP224Fig.

3-19選擇性重發(fā)滑動窗口協(xié)議（協(xié)議6）選擇性重發(fā)的滑動窗口協(xié)議在差錯率較高的信道上，使用協(xié)議5可能導致大量的重發(fā)，從而使信道利用率大幅度降低

設幀長為1500Byte，連續(xù)發(fā)送7幀共84000bits，當信道的誤碼率高于1.2x10-5

，信道的利用率將非常低協(xié)議6是一個選擇性重發(fā)的滑動窗口協(xié)議

發(fā)送方在某幀的重發(fā)定時器超時（沒有收到該幀的ACK）后，只要重發(fā)該幀即可，而不必重發(fā)所有已發(fā)送的幀發(fā)送方可根據(jù)所定義的發(fā)送窗口大小，連續(xù)發(fā)送

通常發(fā)送方將當前緩沖區(qū)內的幀連續(xù)發(fā)送完后，等待確認，發(fā)送緩沖區(qū)的覆蓋（窗口的旋轉）將依據(jù)收到的ACK的序號，該序號的幀及其以前的所有幀都可被覆蓋選擇性重發(fā)窗口協(xié)議圖例有一個差錯時僅重發(fā)一幀（WT=4,WR=

4）TnbmP218Fig.3-16(b)出錯將分組2~5交網(wǎng)絡層被數(shù)據(jù)鏈路層緩存的幀發(fā)收0ACK0ACK1ACK8ACK9ACK10ACK111211109876254314131201E34526781110912ACK5ACK1ACK1NAK2ACK7ACK6

選擇性重發(fā)窗口協(xié)議說明設幀序號由3個bit表示，即0~7，并且假設WT=4

,WR=4設發(fā)送方有大量數(shù)據(jù)等待發(fā)送給對方，由于WT=

4，即有4個發(fā)送緩沖區(qū)，所以可連續(xù)發(fā)送4幀，并每發(fā)送一幀將啟動一個（帶幀序號的）重發(fā)定時器，但緩沖區(qū)的覆蓋必須在收到確認之后，因為一旦該幀的重發(fā)定時器超時，必須將原緩沖區(qū)內的幀重發(fā)協(xié)議6中，由于接收方的WR=4，如期待接收的幀n#丟失，然而對后繼到達的正確的(n+1)#幀可照常接收，由于(n+1)#幀正確接收，也需要確認，但此確認應有別于對正期待幀的確認，這就是肯定性確認ACK和否定性確認NAK的區(qū)別，但無論是ACK或NAK，其中的確認號都必須為n，即期待接收的第n幀輔助定時器和否定性確認協(xié)議6中接收方定義了一個輔助定時器 接收方采用捎帶確認的前提是有數(shù)據(jù)幀發(fā)送給發(fā)送方，然而并非需要捎帶確認時，接收方上層總是有數(shù)據(jù)需發(fā)送的，所以接收方定義了一個輔助定時器，凡收到一個正確的數(shù)據(jù)幀并需發(fā)送確認時，立即啟動輔助定時器，在輔助定時器溢出前，上層有數(shù)據(jù)幀發(fā)送，則可捎帶確認，如輔助定時器溢出，則立即發(fā)送一個單獨的確認，以免發(fā)送方的重發(fā)定時器超時而導致的數(shù)據(jù)幀的重發(fā)協(xié)議6中定義了一個否定性確認的幀格式

當接收方接收到一個有問題的幀時（包括兩種情況：1.CRC校驗錯；2.CRC校驗正確但幀序號錯），發(fā)送一個否定性確認NAK選擇性重發(fā)窗口協(xié)議程序voidprotocol6(void){

enable_network_layer();

ack_expected=0; next_frame_to_send=0; frame_expected=0;

too_far=NR_BUFS;

nbuffered=0;

for(i=0;i<NR_BUFS;i++)arrived[i]=false;TnbmP224Fig.

3-19（協(xié)議6）while(true) {wait_for_event(&event)；

switch(event) {casenetwork_layer_ready:發(fā)送處理；

caseframe_arrival：幀到達處理；

casecksum_err：收到一個壞幀且沒有發(fā)過nak，則發(fā)nak；

if(no_nak)send_frame(nak,0,frame_expected,out_buf)；

casetimeout: 等待確認幀的超時，重發(fā)；

send_frame(data,oldest_frame,frame_expected,out_buf); caseack_timeout：輔助定時器超時，發(fā)一單獨的ack；

send_frame(ack,0,frame_expected,out_buf); } if(nbuffered<NR_BUFS) enable_network_layer()；如窗口未滿，則允許網(wǎng)絡層事件；

else disable_network_layer()；如窗口滿，則不允許網(wǎng)絡層事件；

}}

發(fā)送數(shù)據(jù)處理數(shù)據(jù)幀本發(fā)送幀序號捎帶確認序號幀的數(shù)據(jù)nbuffered=nbuffered+1; /*已用窗口數(shù)+1*/from_network_layer(&out_buf[next_frame_to_send%NR_BUFS]);/*取新的分組*/send_frame(data,next_frame_to_send,frame_expected,out_buf);/*發(fā)送該幀*/inc(next_frame_to_send); /*發(fā)送窗口的前沿+1*/幀到達處理如序號錯則發(fā)nak，否則啟動輔助定時器如序號在接收窗口范圍內，接受該幀如順序正確，則交網(wǎng)絡層，調整參數(shù)，啟動輔助定時器from_physical_layer(&r);

if(r.kind==data){if((r.seq!=frame_expected)&&no_nak)

send_frame(nak,0,frame_expected,out_buf);elsestart_ack_timer();if(between(frame_expected,r.seq,too_far)&&(arrived[r.seq%NR_BUFS]==false)){arrived[r.seq%NR_BUFS]=true;

in_buf[r.seq%NR_BUFS]=; while(arrived[frame_expected%NR_BUFS]){to_network_layer(&in_buf[frame_expected%NR_BUFS]);

no_nak=true;arrived[frame_expected%NR_BUFS]=false;

inc(frame_expected);inc(too_far);start_ack_timer(); }}}if(r.kind==nak)&&(between(ack_expected,(r.ack+1)%(MAX_SEQ+1),next_frame_to_send))

send_frame(data,(r.ack+1)%(MAX_SEQ+1),

frame_expected,out_buf);while(between(ack_expected,r.ack,next_frame_to_send)){nbuffered=nbuffered-1;

stop_timer(ack_expected%NR_BUFS)；

inc(ack_expected);}r.ack+1正是接收方期待接收的幀處理ack已用窗口數(shù)-1，啟動輔助定時器，等待下一個ack協(xié)議6中極端情況的分析發(fā)送方當前的發(fā)送窗口為0123456，連續(xù)發(fā)送了7幀，幀號為0123456，然后等待確認接收方在初始化后，接收窗口為0123456，在正確收到0#幀后，由于捎帶確認，所以立即啟動輔助定時器，并且在輔助定時器沒有超時之前，發(fā)送方發(fā)送的7幀都正確地收到后，然后輔助定時器超時，接收方立即發(fā)送了ACK7，意即0~6幀全部收到并期待接收第7幀，然后取出分組交網(wǎng)絡層、清緩沖區(qū)并調整窗口為7012345

發(fā)送方一直在等待確認，但接收方發(fā)送的ACK7由于某種原因丟失了，在重發(fā)定時器陸續(xù)超時的過程中，發(fā)送方又陸續(xù)重發(fā)了0123456幀，并繼續(xù)等待確認

當n=3，即幀號為01234567，且發(fā)送窗口WT=接收窗口WR=7

協(xié)議6中極端情況的分析（續(xù)）接收方收到0123456幀，認為是第二批來的幀，按正常處理，發(fā)現(xiàn)012345均在其接收窗口內，當然接收并存入緩沖，6丟棄，但由于期待接收的第7幀未到，所以只能仍發(fā)ACK7，意即再次確認上次收到的0~6，但由于第7幀未到，所以，已收到的012345幀不能上交網(wǎng)絡層但在發(fā)送方來看，在收到了ACK7后才知道，重發(fā)的0~6總算收到了，于是，調整窗口為7012345，又從網(wǎng)絡層取分組，并發(fā)送第二批幀

接收方在收到7012345后，發(fā)現(xiàn)012345幀已在緩沖區(qū)中，是重復的，應丟棄，第7幀接收，發(fā)送ACK6，然后將7012345交網(wǎng)絡層，清緩沖區(qū)、調整接收窗口

此時，接收方的網(wǎng)絡層發(fā)現(xiàn)：數(shù)據(jù)鏈路層交來的第二批分組中的012345與原來的重復，協(xié)議失敗當WT=WR=7時協(xié)議6失敗的原因原因在于接收窗口過大，窗口中的有效順序號在調整前和調整后有重疊

所以，通常：發(fā)送窗口+接收窗口<=2n

且：發(fā)送窗口

=

接收窗口

發(fā)送窗口>接收窗口或者發(fā)送窗口<接收窗口都是不合適的協(xié)議6更具實用性協(xié)議6中：如果幀序號由n位組成，即0~2n-1發(fā)送窗口=接收窗口=(MAX_SEQ+1)/2協(xié)議6中：增加了否定性確認NAK，其中的確認號為當前所期待接收的幀的序號當收到一個CRC校驗錯的幀，則發(fā)一個NAK當首次收到一個CRC校驗正確、但序號錯的幀，則發(fā)送一個NAK協(xié)議6中：增加了一個輔助定時器，當輔助定時器超時，則立即發(fā)送一個ACK，其中的確認號為當前所期待接收的幀的序號當收到一個CRC校驗正確、序號也正確的幀，即正是所期待的幀，將啟動一個輔助定時器（為等待捎帶）當再次收到一個CRC校驗正確、但序號錯的幀，因為已發(fā)送過NAK

，所以不再發(fā)NAK，此時也將啟動一個輔助定時器（為等待捎帶）可靠性傳輸差錯控制：校驗、重發(fā)和序號避免幀錯誤的保證：幀的校驗避免幀丟失的保證：超時和重發(fā)避免幀重復的保證：幀有序號流量控制：窗口協(xié)議發(fā)送方和接收方之間的協(xié)調協(xié)議描述和驗證協(xié)議描述和驗證

有限狀態(tài)機模型（finitestatemachine）Petri網(wǎng)模型由于實際使用的協(xié)議非常復雜，需有形式化的和數(shù)學的方法來驗證協(xié)議的正確性第3章數(shù)據(jù)鏈路層定義和功能數(shù)據(jù)幀的組成可靠性傳輸數(shù)據(jù)鏈路層示例數(shù)據(jù)鏈路層示例

HDLC–高級數(shù)據(jù)鏈路控制因特網(wǎng)中的數(shù)據(jù)鏈路層SLIP---串型線路IPPPP---點對點協(xié)議HDLC的基本工作原理最早由IBMSNA提出SDLC（SynchronousDataLinkControl）ISO根據(jù)SDLC，提出了HDLC

（HighlevelDataLinkControl）HDLC是面向bit的同步通信協(xié)議HDLC的配置方式非平衡配置：又分為點對點和點對多點兩種，非平衡配置的特點是有一個主站及一個或多個從站組成，主站發(fā)出的幀叫命令，從站發(fā)出的幀叫響應平衡配置：兩個站都是復合站，同時具有主站和從站的功能HDLC的幀格式8bit88>=016801111110地址控制數(shù)據(jù)校驗和01111110幀標志序列即01111110，作為幀的分隔標志，如線路空閑，則用標志序列填充，用位插入方法實現(xiàn)透明傳輸?shù)刂酚蛟诳偩€型多終端情況下，是終端的站號；在點對點的情況下，用來標志命令和響應控制域定義幀的類型、序號等和其它一些功能數(shù)據(jù)域用戶數(shù)據(jù)，長度任意校驗和CRC碼，ISO和CCITT有相似的生成多項式HDLC的幀類型HDLC的幀有三種類型，不同的類型其控制域的定義有些不同信息幀（I）監(jiān)控幀（S）無序號幀（U）10TypeP/FNext11TypeP/FNext0SeqP/FNext信息幀InformationFrameP/F（Poll/Final）位：P主機查詢哪個終端要發(fā)送數(shù)據(jù)F終端發(fā)送數(shù)據(jù)的最后一幀用F捎帶確認幀號：即下一個期待接收幀號，意味著以前的幀的接收確認0當前發(fā)送幀號P/F捎帶確認幀號HDLC的幀類型HDLC的幀有三種類型，不同的類型其控制域的定義有些不同信息幀（I）監(jiān)控幀（S）無序號幀（U）10TypeP/FNext11TypeP/FNext0SeqP/FNext監(jiān)控幀SupervisoryFrame監(jiān)控幀有四種格式1000P/F捎帶確認號1001P/F捎帶確認號1010P/F捎帶確認號1011P/F捎帶確認號RRRNRREJSREJ接收準備好RR（ReceiveReady）：接收準備好即確認Next-1及Next-1幀以前的所有幀，并準備好接收Next幀監(jiān)控幀（S）監(jiān)控幀有四種格式1000P/F捎帶確認號1001P/F捎帶確認號1010P/F捎帶確認號1011P/F捎帶確認號RRRNRREJSREJ接收未準備好RNR（ReceiveNotReady）：接收未準備好即確認Next-1及Next-1幀以前的幀，并要求發(fā)送方停止發(fā)送監(jiān)控幀（S）監(jiān)控幀有四種格式1000P/F捎帶確認號1001P/F捎帶確認號1010P/F捎帶確認號10