第四章數(shù)據(jù)鏈路控制數(shù)據(jù)鏈路層定義和功能差錯(cuò)控制流量控制常用的數(shù)據(jù)鏈路層協(xié)議

為什么要設(shè)計(jì)數(shù)據(jù)鏈路層？在原始的物理傳輸線路上傳輸數(shù)據(jù)信號(hào)是有差錯(cuò)的，存在一定的誤碼率；設(shè)計(jì)數(shù)據(jù)鏈路層的目的就是如何在有差錯(cuò)的線路上，進(jìn)行無差錯(cuò)傳輸。向網(wǎng)絡(luò)層提供高質(zhì)量的服務(wù)。從網(wǎng)絡(luò)參考來看，物理層之上的各層都有改善數(shù)據(jù)傳輸質(zhì)量的要求，數(shù)據(jù)鏈路層是重要的一層。4.1 定義和功能要解決的問題：如何在有差錯(cuò)的線路上，進(jìn)行無差錯(cuò)傳輸。ISO關(guān)于數(shù)據(jù)鏈路層的定義：數(shù)據(jù)鏈路層的目的是為了提供功能上和規(guī)程上的方法，以便建立、維護(hù)和釋放網(wǎng)絡(luò)實(shí)體間的數(shù)據(jù)鏈路。數(shù)據(jù)鏈路：從數(shù)據(jù)發(fā)送點(diǎn)到數(shù)據(jù)接收點(diǎn)（點(diǎn)到點(diǎn)pointtopoint）所經(jīng)過的傳輸途徑。

虛擬數(shù)據(jù)通路，實(shí)際數(shù)據(jù)通路分組和幀的關(guān)系二、數(shù)據(jù)鏈路層基本功能數(shù)據(jù)鏈路控制規(guī)程為使數(shù)據(jù)能迅速、正確、有效地從發(fā)送點(diǎn)到達(dá)接收點(diǎn)所采用的控制方式。數(shù)據(jù)鏈路層協(xié)議應(yīng)提供的最基本功能：數(shù)據(jù)在數(shù)據(jù)鏈路上的正常傳輸（建立、維護(hù)和釋放）幀定界（幀同步）差錯(cuò)控制流量控制尋址數(shù)據(jù)鏈路層協(xié)議的位置幀分組幀分組數(shù)據(jù)鏈路連接數(shù)據(jù)鏈路層為網(wǎng)絡(luò)層提供三種基本服務(wù)：無確認(rèn)無連接服務(wù)

由上層完成差錯(cuò)控制，適合于誤碼率低、實(shí)時(shí)性要求高的場合，如大部分有線局域網(wǎng)。有確認(rèn)無連接服務(wù)進(jìn)行簡單的差錯(cuò)控制。適用于不可靠的信道，如無線網(wǎng)。面向連接確認(rèn)服務(wù)在發(fā)送前需要建立連接，保證了幀的正確按序傳輸，適合于可靠性要求較高的場合。適合于大多數(shù)廣域網(wǎng)。應(yīng)答方式正向應(yīng)答:只對(duì)正確的信息應(yīng)答。負(fù)向應(yīng)答:只對(duì)錯(cuò)誤的信息應(yīng)答。雙向應(yīng)答:既對(duì)正確的信息應(yīng)答，也對(duì)錯(cuò)誤的信息應(yīng)答。問題1：在數(shù)據(jù)鏈路層，最常采用哪種應(yīng)答方式？問題2：在數(shù)據(jù)傳輸過程中，數(shù)據(jù)會(huì)出現(xiàn)哪些情況？正向應(yīng)答工作方式A0D0D1A1D0D0A0D1A1D1啟動(dòng)計(jì)時(shí)器計(jì)時(shí)器超時(shí)啟動(dòng)計(jì)時(shí)器計(jì)時(shí)器超時(shí)D0A0D1A1D1A1(1)正常的數(shù)據(jù)傳送 （2）數(shù)據(jù)幀丟失及出錯(cuò)（3）應(yīng)答幀丟失4.2成幀（Framing）將比特流分成離散的幀，并計(jì)算每個(gè)幀的校驗(yàn)和。成幀方法：1）字符計(jì)數(shù)法在幀頭中用一個(gè)域來表示整個(gè)幀的字符個(gè)數(shù)缺點(diǎn)：若計(jì)數(shù)出錯(cuò)，對(duì)本幀和后面的幀有影響。 因此很少采用。555343224521355成幀（2）2）帶字符填充的首尾字符定界法用DLESTX標(biāo)示幀的開始用DLEETX標(biāo)示幀的結(jié)束用DLEDLE標(biāo)示傳送數(shù)據(jù)信息中的DLE例如：信息DLESTXADLEBDLEETX在網(wǎng)絡(luò)中傳送時(shí)表示為：DLESTXDLEDLESTXADLEDLEBDLEDLEETXDLEETX

缺點(diǎn)：局限于8位字符和ASCII字符傳送，也不被普遍采用。成幀（3）3）帶位填充的首尾標(biāo)記定界法幀的起始和結(jié)束都用一個(gè)特殊的位串“01111110”，稱為標(biāo)記(flag)“0”比特插入刪除技術(shù)，在傳送的數(shù)據(jù)信息中每遇到5個(gè)連續(xù)的1在其后加0例如：0110111111011111001在網(wǎng)絡(luò)中傳送時(shí)表示為：01111110011011111010111110001011111104）物理層編碼違例法只適用于物理層編碼有冗余的網(wǎng)絡(luò)，如曼徹斯特編碼注意：在很多數(shù)據(jù)鏈路協(xié)議中，使用字符計(jì)數(shù)法和一種其它方法的組合。4.3差錯(cuò)控制差錯(cuò)出現(xiàn)的特點(diǎn)：隨機(jī)，連續(xù)突發(fā)（burst）差錯(cuò)產(chǎn)生的原因信道的電氣特性引起信號(hào)幅度、頻率、相位的畸變；信號(hào)反射；串?dāng)_；閃電、大功率電機(jī)的啟停等。

出錯(cuò)情況幀（包括發(fā)送幀和響應(yīng)幀）出錯(cuò)幀（包括發(fā)送幀和響應(yīng)幀）丟失差錯(cuò)控制的目的保證幀正確，按序送交上層。在接收方能夠判斷接收的數(shù)據(jù)是否正確，若錯(cuò)誤還可能要恢復(fù)錯(cuò)誤。差錯(cuò)控制的方法自動(dòng)糾錯(cuò)機(jī)制檢錯(cuò)反饋重發(fā)機(jī)制差錯(cuò)控制的方法糾錯(cuò)碼和檢錯(cuò)碼碼字codeword一個(gè)幀包括m個(gè)數(shù)據(jù)位，r個(gè)校驗(yàn)位，稱為n

位碼字（n=m+r）。

糾錯(cuò)碼error-correctingcode加入了足夠多的冗余位，使接收方不僅知道有差錯(cuò)發(fā)生，并知道哪些位發(fā)生差錯(cuò)。檢錯(cuò)碼error-detectingcode加入了冗余位，使接收方知道有差錯(cuò)發(fā)生，但不知道什么差錯(cuò)，然后請(qǐng)求重發(fā)。

海明定理海明距離兩個(gè)編碼的海明距離：兩個(gè)編碼不相同位的個(gè)數(shù)。編碼方案的海明距離：編碼方案中任兩個(gè)編碼海明距離的最小值。例：0000000000與0000011111的海明距離為5海明定理為檢測d位錯(cuò)，編碼方案的海明距離應(yīng)至少為d+1；當(dāng)發(fā)生d位錯(cuò)時(shí)，不會(huì)由一種合法編碼變?yōu)榱硪环N合法編碼。為糾正d位錯(cuò)，編碼方案的海明距離應(yīng)至少為2d+1；當(dāng)發(fā)生d位錯(cuò)時(shí)，出錯(cuò)編碼仍然最接近于原始的正確編碼。差錯(cuò)碼舉例奇偶校驗(yàn)碼在數(shù)據(jù)后填加一個(gè)奇偶位（paritybit）例：使用偶校驗(yàn)（“1”的個(gè)數(shù)為偶數(shù)） 10110101 ——> 101101011 10110001 ——> 101100010若接收方收到的字節(jié)奇偶結(jié)果不正確，就可以知道傳輸中發(fā)生了錯(cuò)誤。增加奇偶校驗(yàn)位后海明距離由1變?yōu)?，因此可以檢查出一位二進(jìn)制位的差錯(cuò)循環(huán)冗余碼(CRC)循環(huán)冗余碼（CRC碼，多項(xiàng)式編碼）110001，表示成多項(xiàng)式x5+x4+1生成多項(xiàng)式G(x)發(fā)方、收方事前約定；生成多項(xiàng)式的高位和低位必須為1生成多項(xiàng)式必須比傳輸信息對(duì)應(yīng)的多項(xiàng)式短。CRC校驗(yàn)基本思想：CRC碼（即校驗(yàn)和）加在幀尾，使帶CRC碼的幀的多項(xiàng)式能被G(x)除盡；接收方接收時(shí)，用G(x)去除它，若有余數(shù)，則傳輸出錯(cuò)。設(shè)G(x)為r階，在幀的末尾加r個(gè)0，使幀為

m+r位，相應(yīng)多項(xiàng)式為xrM(x)；按模2除法用對(duì)應(yīng)于G(x)的位串去除對(duì)應(yīng)于xrM(x)的位串；按模2減法從對(duì)應(yīng)于xrM(x)的位串中減去余數(shù)（等于或小于r位），結(jié)果就是要傳送的帶校驗(yàn)和的多項(xiàng)式T(x)。CRC碼計(jì)算算法CRC的檢錯(cuò)能力發(fā)送：T(x)；接收：T(x)+E(x)；余數(shù)((T(x)+E(x))/G(x))=0+余數(shù)(E(x)/G(x))若余數(shù)(E(x)/G(x))=0，則差錯(cuò)不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。四個(gè)多項(xiàng)式已成為國際標(biāo)準(zhǔn)CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1硬件實(shí)現(xiàn)CRC校驗(yàn)。循環(huán)冗余校驗(yàn)法CRC碼計(jì)算算法檢驗(yàn)和(checksum)算法檢驗(yàn)字段初值置0；數(shù)據(jù)拆分成與檢驗(yàn)字段等長的分片，不足部分補(bǔ)0；將所有分片逐位取反，并連續(xù)累加，丟棄最高進(jìn)位；計(jì)算結(jié)果置入檢驗(yàn)字段；接收段執(zhí)行相同的過程，并將計(jì)算結(jié)果和傳輸過來的檢驗(yàn)和進(jìn)行比較以決定數(shù)據(jù)是否出現(xiàn)差錯(cuò)；適用于高層協(xié)議，如IP、TCP、UDP等；檢驗(yàn)和算法舉例待傳輸數(shù)據(jù)為：10010100,01110110,1100計(jì)算過程~(10010100)+~(01110110)=1111010011110100+~(11000000)=00110011帶檢驗(yàn)和的傳輸數(shù)據(jù)是10010100,01110110,1100001100114.4 流量控制假設(shè)單工傳輸發(fā)送方無休止工作（要發(fā)送的信息無限多）；接收方無休止工作（緩沖區(qū)無限大）；發(fā)送數(shù)據(jù)的速率低于接收數(shù)據(jù)的速率；通信線路（信道）不損壞或丟失信息幀（無錯(cuò)）。工作過程發(fā)送程序取數(shù)據(jù)，構(gòu)成幀，發(fā)送幀；接收程序等待，接收幀，送數(shù)據(jù)給高層。單工停等協(xié)議（理想情況）增加約束條件：接收方不能無休止接收。例如：緩沖區(qū)數(shù)量有限，接收速率比發(fā)送速率低等。解決辦法：

接收方每收到一個(gè)幀，給發(fā)送方回送應(yīng)答。工作過程發(fā)送程序取數(shù)據(jù)，成幀，發(fā)送幀，等待響應(yīng)幀；接收程序等待，接收幀，數(shù)據(jù)送高層，發(fā)送應(yīng)答幀。單工停等協(xié)議（無錯(cuò)情況）（a）簡單停等協(xié)議；（b）帶流量控制停等協(xié)議增加約束條件：信道（線路）有差錯(cuò)，信息幀可能損壞或丟失。解決方法常使用正向應(yīng)答+重發(fā)機(jī)制來解決差錯(cuò)控制。數(shù)據(jù)序號(hào)采用循環(huán)序號(hào)機(jī)制。應(yīng)答幀的兩種方式：單幀應(yīng)答：應(yīng)答序號(hào)為某一個(gè)正確幀的序號(hào)成批應(yīng)答：應(yīng)答序號(hào)為下一個(gè)期望接收的序號(hào)通常采用附載應(yīng)答方式：將數(shù)據(jù)幀攜帶應(yīng)答信息的通信方式稱為附載應(yīng)答。可以把應(yīng)答幀的序號(hào)加在信息幀中一并發(fā)送，以提高效率。單工停等協(xié)議（有錯(cuò)情況）數(shù)據(jù)幀在鏈路上傳輸?shù)目赡芮闆r從網(wǎng)絡(luò)層取數(shù)，成幀發(fā)送幀幀到否應(yīng)答到否超時(shí)否重復(fù)否正確否接收幀，送網(wǎng)絡(luò)層發(fā)應(yīng)答發(fā)送幀應(yīng)答幀YNYNYNNY定時(shí)器丟棄丟棄NY有噪聲信道的單工停等協(xié)議示意圖停等協(xié)議效率連續(xù)ARQ協(xié)議工作原理連續(xù)停等協(xié)議是指不需要收到應(yīng)答幀就可連續(xù)不斷的發(fā)下面的幀出錯(cuò)后處理全部重發(fā)流水線協(xié)議當(dāng)一幀出錯(cuò)時(shí)，需重發(fā)出錯(cuò)幀之后的所有幀；接收方的緩沖區(qū)數(shù)量只需要一個(gè)。選擇重發(fā)流水線協(xié)議當(dāng)一幀出錯(cuò)時(shí)，只重發(fā)出錯(cuò)幀；接收方的緩沖區(qū)數(shù)量足夠多。連續(xù)ARQ協(xié)議的工作原理滑動(dòng)窗口協(xié)議滑動(dòng)窗口協(xié)議是對(duì)連續(xù)停等協(xié)議的改進(jìn)，它能夠控制已發(fā)送但未確認(rèn)的數(shù)據(jù)幀的個(gè)數(shù)（滑動(dòng)窗口的大小）。發(fā)送窗口窗口尺寸：允許連續(xù)發(fā)送未應(yīng)答的幀的個(gè)數(shù)數(shù)據(jù)允許發(fā)送的條件：上界－下界<窗口尺寸窗口滑動(dòng)的條件窗口上限移動(dòng)：發(fā)送數(shù)據(jù)幀；窗口下限移動(dòng)：收到應(yīng)答幀滑動(dòng)窗口協(xié)議（接收窗口）接收窗口窗口尺寸：允許連續(xù)接收未處理的幀的個(gè)數(shù)數(shù)據(jù)允許接收的條件：數(shù)據(jù)序號(hào)落在接收窗口中窗口滑動(dòng)的條件發(fā)送應(yīng)答幀后上下界同時(shí)移動(dòng)窗口大小與序號(hào)關(guān)系出錯(cuò)全部重傳WT>WR

，WR=1WT≤2n-1

選擇性重傳WT

=WR

WR≤2n-14.5 常用的數(shù)據(jù)鏈路層協(xié)議面向字符的鏈路層協(xié)議ISO的IS1745，基本型傳輸控制規(guī)程及其擴(kuò)充部分（BM和XBM）IBM的二進(jìn)制同步通信規(guī)程（BSC）DEC的數(shù)字?jǐn)?shù)據(jù)通信報(bào)文協(xié)議（DDCMP）PPP—Point-to-PointProtocol，Internet的協(xié)議。4.5 常用的數(shù)據(jù)鏈路層協(xié)議面向比特的鏈路層協(xié)議IBM的SNA使用的數(shù)據(jù)鏈路協(xié)議SDLC（SynchronousDataLinkControlprotocol）；ANSI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作為X.25網(wǎng)絡(luò)接口標(biāo)準(zhǔn)的一部分，后來改為LAPB。高級(jí)數(shù)據(jù)鏈路控制規(guī)程HDLCHDLC的組成幀結(jié)構(gòu)（語法）規(guī)程元素（語法）規(guī)程類型（語義）使用HDLC的語法可以定義多種具有不同操作特點(diǎn)的鏈路層協(xié)議。HDLC的描述數(shù)據(jù)站：主站，次站，組合站鏈路構(gòu)型：平衡型和非平衡型操作模式：正規(guī)響應(yīng)模式，異步響應(yīng)模式，異步平衡模式HDLC的幀結(jié)構(gòu)定界符01111110空閑的點(diǎn)到點(diǎn)線路上連續(xù)傳定界符，說明物理連接已經(jīng)建立，能夠建立數(shù)據(jù)鏈路。地址字段（Address）多終端線路，用來區(qū)分終端；點(diǎn)到點(diǎn)線路，有時(shí)用來區(qū)分命令和響應(yīng)。若地址是接收該幀站的地址，則該幀是命令幀；若地址是發(fā)送該幀站的地址，則該幀是響應(yīng)幀。HDLC的幀結(jié)構(gòu)（續(xù)）控制字段（Control）8b：用作序號(hào)、確認(rèn)和其它目的數(shù)據(jù)字段（Data）任意信息，任意長度（長度由上層控制）校驗(yàn)和（Checksum）CRC校驗(yàn)生成多項(xiàng)式：CRC-CCITT=x16+x12+x5+1HDLC幀的類型幀類型信息幀（Information）完成信息傳送。監(jiān)控幀（Supervisory）差錯(cuò)控制和流量控制。無序號(hào)幀（Unnumbered）鏈路控制管理?？刂谱侄螏念愋图跋鄳?yīng)的信息用控制域的字段表示；信息幀序號(hào)（Seq）：滑動(dòng)窗口技術(shù)，3位序號(hào)，發(fā)送窗口大小為7捎帶確認(rèn)（Next）：下一個(gè)希望接收到的幀探詢/結(jié)束P/F位（Poll/Final）HDLC中的監(jiān)控幀監(jiān)控幀類型“0”表示確認(rèn)幀RR（RECEIVEREADY），接收準(zhǔn)備確認(rèn)。類型“1”表示否定性確認(rèn)幀REJ（REJECT），對(duì)應(yīng)于出錯(cuò)全部重傳類型“2”表示接收未準(zhǔn)備好RNR（RECEIVENOTREADY）類型“3”表示選擇拒絕SREJ（SELECTIVEREJECT），對(duì)應(yīng)選擇性重傳HDLC和ADCCP允許選擇拒絕，SDLC和LAPB不允許。HDLC中的無序號(hào)幀無序號(hào)幀可以用來傳控制信息，也可在不可靠無連接服務(wù)中傳數(shù)據(jù)。Type和Modifier聯(lián)合表示不同類型的無序號(hào)幀；命令DISC（DISConnect）SNRM（SetNormalResponseMode）SARM（SetAsynchronousResponseMode）SABM（SetAsynchronousBalancedMode）HDLC和LAPB使用。FRMR（FRaMeReject）無序號(hào)確認(rèn)UA（UnnumberedAcknowledgement）對(duì)控制幀進(jìn)行確認(rèn)，用于確認(rèn)模式建立和接受拆除命令。UI（UnnumberedInformation）HDLC的功能組合三種站，兩種構(gòu)型，三種操作模式，以及規(guī)程元素中定義的各種幀的各種組合產(chǎn)生多種鏈路層協(xié)議。HDLC定義了選擇構(gòu)成鏈路層協(xié)議的良序結(jié)構(gòu)：選擇站構(gòu)型——>基本操作模式——>基本幀種類——>12種任選功能——>得到協(xié)議X.25協(xié)議（自學(xué)）X.25協(xié)議分組級(jí)，PLP幀級(jí)，X.25LAP（LinkAccessProcedure），X.25LAPB（Balanced）物理級(jí)，X.21“X.25協(xié)議規(guī)程使用HDLC規(guī)程的原理和術(shù)語”X.25LAP：HDLC非平衡規(guī)程幀的基本清單+任選功能2、8、12，也可組成主站—次站式平衡規(guī)程。X.25LAPB：HDLC組合站平衡規(guī)程幀的基本清單+任選功能2、8、11、12。因此，X.25LAP、LAPB是HDLC的子集。X.25的幀格式與HDLC完全相同X.25鏈路級(jí)的命令和響應(yīng)X.25的鏈路層協(xié)議LA