第二章

端到端的傳輸協(xié)議FundamentalofCommunicationNetworks通信網(wǎng)絡(luò)根底2024/1/181引言(1)不同層次的傳輸協(xié)議均期望提供可靠的數(shù)據(jù)傳輸；〔1〕標(biāo)識(shí)高層送下來的數(shù)據(jù)分組的起止位置；〔2〕發(fā)現(xiàn)傳輸中的錯(cuò)誤。根據(jù)通信雙方所處位置的不同，采用的消除錯(cuò)誤的解決方法〔協(xié)議〕不同：〔1〕通信雙方通過一條物理鏈路直接相連，鏈路層協(xié)議解決數(shù)據(jù)幀的傳輸錯(cuò)誤；〔2〕通信雙方處于一個(gè)子網(wǎng)內(nèi)，通過多條數(shù)據(jù)鏈路相連，網(wǎng)絡(luò)層的端到端傳輸協(xié)議解決分組的傳輸錯(cuò)誤；〔3〕通信雙方處于不同子網(wǎng)內(nèi)，需要采用運(yùn)輸層的端到端傳輸協(xié)議解決報(bào)文的傳輸錯(cuò)誤。2024/1/182引言—數(shù)據(jù)鏈路層物理層通常只負(fù)責(zé)比特的傳輸，而不比照特的含義和作用進(jìn)行區(qū)分。當(dāng)數(shù)據(jù)鏈路層將網(wǎng)絡(luò)層的分組連續(xù)送到物理層進(jìn)行傳輸時(shí)，或是接收到來自物理層的比特?cái)?shù)據(jù)送至網(wǎng)絡(luò)層時(shí)，需要解決幾個(gè)問題：〔1〕什么時(shí)刻是一幀的開始？〔2〕什么時(shí)刻是一幀的結(jié)束？〔3〕那一段傳輸?shù)氖怯糜谶^失校驗(yàn)的比特？解決方法：數(shù)據(jù)鏈路層的組幀技術(shù)。組幀面向上層〔封裝〕和下層。2024/1/183第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/184第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議*重點(diǎn)：掌握組幀的思想。2024/1/1852.1.1面向字符的組幀技術(shù)

(1)面向字符的組幀技術(shù)：指物理層傳輸?shù)母締卧且粋€(gè)字符，并形成具有一定格式的字符串。〔1字符=1字節(jié)=8比特〕在物理層，有多種方式實(shí)現(xiàn)字符的傳輸。例如：RS-232C異步串行接口協(xié)議。該協(xié)議在傳送每個(gè)字符前后分別加上起始位〔D起〕、停止位〔D止〕，以便區(qū)分不同的字符。2024/1/1862.1.1面向字符的組幀技術(shù)

(2)RS-232：個(gè)人計(jì)算機(jī)上的通訊接口之一，由電子工業(yè)協(xié)會(huì)EIA所制定的異步傳輸標(biāo)準(zhǔn)接口。通常RS-232接口有9個(gè)引腳(DB-9)或是25個(gè)引腳(DB-25)。一般個(gè)人計(jì)算機(jī)上會(huì)有兩組RS-232接口，稱為COM1和COM2。民用領(lǐng)域：投影儀工業(yè)領(lǐng)域：電力電子設(shè)備的通訊，例如DCS、PLC、電動(dòng)執(zhí)行器、單片機(jī)、電機(jī)保護(hù)器、電氣后臺(tái)、繼電保護(hù)裝置。2024/1/1872.1.1面向字符的組幀技術(shù)

(3)Internet網(wǎng)中常用的面向字符的組幀技術(shù)的協(xié)議：SLIP(SerialLineInternetProtocol)串行線路的Internet數(shù)據(jù)鏈路層協(xié)議PPP〔PointtoPointProtocol〕點(diǎn)-點(diǎn)協(xié)議SLIP和PPP用于串行通信的撥號(hào)線路上，家庭計(jì)算機(jī)或公司用戶通過ISP接到Internet的主要協(xié)議。ISP：互聯(lián)網(wǎng)效勞提供商，即向廣闊用戶綜合提供互聯(lián)網(wǎng)接入業(yè)務(wù)、信息業(yè)務(wù)、和增值業(yè)務(wù)的電信運(yùn)營(yíng)商。2024/1/188SLIP協(xié)議

(1)SLIP幀運(yùn)載的是高層IP數(shù)據(jù)報(bào)。SLIP采用兩個(gè)特殊字符：END〔十六進(jìn)制C0H，H表示十六進(jìn)制〕和ESC〔十六進(jìn)制DBH〕。C0的二進(jìn)制編碼比特序列是10000110000000END用于表示一幀的開始和結(jié)束。2024/1/189SLIP協(xié)議

(2)IP數(shù)據(jù)報(bào)中出現(xiàn)相同END字符時(shí)，為防止收端錯(cuò)誤地終止一幀的接收，SLIP中使用轉(zhuǎn)義字符ESC〔DBH〕。END字符轉(zhuǎn)換成〔ESC，ESC-END〕兩個(gè)字符〔其中ESC-END=DCH〕；ESC字符轉(zhuǎn)換成〔ESC，ESC-ESC〕兩個(gè)字符〔其中ESC-ESC=DDH〕。2024/1/1810SLIP協(xié)議

(3)發(fā)送端：完成將IP數(shù)據(jù)報(bào)組成幀之后，即可送到物理層進(jìn)行傳輸。物理層協(xié)議在傳送每個(gè)字符前后分別加上起始位〔D起〕、停止位〔D止〕。在接收端：收到END字符即表示一幀的開始或結(jié)束。每當(dāng)遇到ESC字符就進(jìn)行字符轉(zhuǎn)換，恢復(fù)IP報(bào)文中的原有的END和ESC字符。這樣就可以完全以一個(gè)IP數(shù)據(jù)報(bào)的形式向IP層提交數(shù)據(jù)。2024/1/1811SLIP協(xié)議

(4)SLIP協(xié)議的特點(diǎn)：C0的使用將影響SLIP幀數(shù)據(jù)的透明性;沒有校驗(yàn)字段，過失控制功能由高層的協(xié)議承擔(dān)；SLIP協(xié)議并不是Internet的協(xié)議標(biāo)準(zhǔn)，因此不同版本的之間就會(huì)存在著差異，使得互連變得困難。2024/1/18122.1.1面向字符的組幀技術(shù)

(3)Internet網(wǎng)中常用的面向字符的組幀技術(shù)的協(xié)議：SLIP(SerialLineInternetProtocol)串行線路的Internet數(shù)據(jù)鏈路層協(xié)議PPP〔PointtoPointProtocol〕點(diǎn)-點(diǎn)協(xié)議2024/1/1813PPP協(xié)議

(1)RFC1660、RFC1661定義了PPP協(xié)議與幀結(jié)構(gòu)，它的格式與HDLC〔高級(jí)鏈路層控制協(xié)議〕的格式相同。PPP協(xié)議處理了過失檢測(cè)。PPP協(xié)議不僅在撥號(hào)線，并且在路由器─路由器之間的專用線上廣泛應(yīng)用；PPP協(xié)議是在大多數(shù)家庭個(gè)人計(jì)算機(jī)和ISP之間使用的協(xié)議，它可以作為在高速廣域網(wǎng)和社區(qū)寬帶網(wǎng)協(xié)議族的一局部。2024/1/1814PPP協(xié)議

(2)7EH作一幀的開始和結(jié)束標(biāo)志〔F〕；地址域〔A〕：取固定值FFH〔11111111〕，表示網(wǎng)中所有的站都接收該幀；控制域〔C〕：取固定值03H〔00000011〕。2024/1/1815PPP協(xié)議

(3)協(xié)議域〔兩個(gè)字節(jié)〕：標(biāo)識(shí)出不同協(xié)議數(shù)據(jù)域的類型。取0021H表示該幀運(yùn)載的信息是IP數(shù)據(jù)報(bào)；取C021H表示該幀的信息是鏈路控制數(shù)據(jù)；〔鏈路控制幀〕取8021H表示該幀的信息是網(wǎng)絡(luò)控制數(shù)據(jù)；〔網(wǎng)絡(luò)控制幀〕幀校驗(yàn)域〔FCS〕也為兩個(gè)字節(jié)，它用于對(duì)信息域的校驗(yàn)。2024/1/1816PPP協(xié)議

(4)假設(shè)信息域中出現(xiàn)7EH，那么轉(zhuǎn)換為〔7DH，5EH〕兩個(gè)字符；當(dāng)信息流中出現(xiàn)ASCII碼的控制字符〔即小于20H〕，即在該字符前參加一個(gè)7DH字符。當(dāng)信息域出現(xiàn)7DH時(shí)，那么轉(zhuǎn)換為〔7DH，5DH〕兩個(gè)字符；2024/1/18172.1.1面向字符的組幀技術(shù)

(4)Internet網(wǎng)中常用的面向字符的組幀技術(shù)的協(xié)議：SLIP(SerialLineInternetProtocol)串行線路的Internet數(shù)據(jù)鏈路層協(xié)議PPP〔PointtoPointProtocol〕點(diǎn)-點(diǎn)協(xié)議面向字符的組幀技術(shù)特點(diǎn)：幀結(jié)構(gòu)在處理時(shí)非常簡(jiǎn)單；效率較低，插入了許多轉(zhuǎn)義字符；數(shù)據(jù)長(zhǎng)度以字節(jié)為單位。2024/1/1818第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/18192.1.2面向比特的組幀技術(shù)

(1)在面向比特的組幀技術(shù)中，通常采用一個(gè)特殊的比特串，稱為Flag,如0160〔1j表示連續(xù)j個(gè)“1〞〕來表示一幀的正常結(jié)束和開始。01111110…………..01111110與面向字符的組幀技術(shù)面臨相同的問題，即當(dāng)信息比特流中出現(xiàn)與Flag相同的比特串〔如連續(xù)出現(xiàn)6個(gè)“1〞〕如何處理？解決方法：比特插入技術(shù)2024/1/18202.1.2面向比特的組幀技術(shù)

(2)比特插入技術(shù)發(fā)端信息流中，每出現(xiàn)連續(xù)的5個(gè)“1〞就插入一個(gè)“0〞。這樣被插“0〞后的信息比特流中就不會(huì)有多于5個(gè)“1〞的比特串。接收端在收到5個(gè)“1〞以后，如果收到的是“0〞就將該“0〞刪去；如果是“1〞就表示一幀結(jié)束。2024/1/18212.1.2面向比特的組幀技術(shù)

(3)比特插入技術(shù)采用比特插入技術(shù)，除了消除信息幀中出現(xiàn)Flag的作用以外，它還帶來其他作用。如要丟棄或中止一幀，那么可連續(xù)發(fā)送7個(gè)或7個(gè)以上的“1〞。當(dāng)鏈路連續(xù)出現(xiàn)15個(gè)“1〞那么認(rèn)為鏈路空閑。因此016是一個(gè)結(jié)束標(biāo)志，如果016后面是0表示正常結(jié)束，如果016后面是1表示非常中止。2024/1/1822第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/18232.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)

除前面采用Flag和特殊字符外，還可以采用幀長(zhǎng)度來指示一幀何時(shí)結(jié)束。2024/1/1824第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/18252.2.1過失控制(1)鏈路層過失檢測(cè)的功能：有效地發(fā)現(xiàn)一幀數(shù)據(jù)比特經(jīng)過物理信道傳輸后是否正確。過失控制是以降低信息傳輸速率為代價(jià)提高傳輸?shù)目煽啃?。為了在接收端識(shí)別接收到的比特〔信息碼元〕是否存在錯(cuò)誤，需要發(fā)送端在信息碼元序列中增加一些過失控制碼元，它們稱為監(jiān)督〔check〕碼元〔或校驗(yàn)比特〕。監(jiān)督碼元和信息碼元之間有某種確定的關(guān)系〔某種函數(shù)關(guān)系〕，使得接收端可以利用這種關(guān)系發(fā)現(xiàn)或糾正可能存在的錯(cuò)碼。這種具有過失控制能力的編碼稱為糾錯(cuò)編碼。不同的編碼方法，有不同的檢錯(cuò)〔檢錯(cuò)碼〕和糾錯(cuò)〔糾錯(cuò)碼〕能力。2024/1/18262.2.1過失控制(2)針對(duì)不同的應(yīng)用和信道，過失控制技術(shù)不同：檢錯(cuò)重發(fā)(ErrorDetectionRetransmission)：在接收端檢測(cè)到有錯(cuò)碼時(shí)，利用反向信道通知發(fā)送端，要求發(fā)送端重發(fā)，直到正確接收為止。這種技術(shù)需要雙向信道傳送重發(fā)指令。前向糾錯(cuò)FEC(ForwardErrorCorrection)：接收端利用發(fā)送端參加的監(jiān)督碼元，不但能夠發(fā)現(xiàn)錯(cuò)碼，還能將錯(cuò)碼恢復(fù)其正確值。采用FEC時(shí)，不需要反向信道傳送重發(fā)指令，也沒有因反復(fù)重發(fā)而產(chǎn)生的時(shí)延，故實(shí)時(shí)性好。但是為了能夠糾正錯(cuò)誤，需要參加更多的監(jiān)督碼元。FEC被應(yīng)用于衛(wèi)星與外層空間通信。2024/1/18272.2.1過失控制(3)針對(duì)不同的應(yīng)用和信道，過失控制技術(shù)不同：反響校驗(yàn)(FeedbackCheckout)：不需要在發(fā)送序列中參加監(jiān)督碼元。接收端將接收到的碼元原封不動(dòng)地轉(zhuǎn)發(fā)給發(fā)送端。發(fā)送端進(jìn)行比較，發(fā)現(xiàn)有錯(cuò)，立即重發(fā)。檢錯(cuò)刪除(Deletion)：與檢錯(cuò)重發(fā)的區(qū)別在于，接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除，不要求重發(fā)。適用于特定場(chǎng)合，例如循環(huán)重復(fù)發(fā)送某些遙測(cè)數(shù)據(jù)時(shí)。又如，用于屢次重發(fā)仍然錯(cuò)在錯(cuò)碼時(shí)，為了提高傳輸效率不再重發(fā)，采取刪除的方法。2024/1/18282.2.1過失控制(4)常將檢錯(cuò)重發(fā)和前向糾錯(cuò)結(jié)合起來，形成混合糾錯(cuò)方式〔HEC〕。當(dāng)接收端出現(xiàn)少量錯(cuò)碼并有能力糾正的時(shí)候，采用前向糾錯(cuò)技術(shù)；當(dāng)接收端出現(xiàn)較多錯(cuò)碼，超出了碼的糾錯(cuò)能力的時(shí)候，那么要求發(fā)送端重新傳輸。

2024/1/1829檢錯(cuò)碼糾錯(cuò)編碼按照實(shí)現(xiàn)的功能可以分為：只能檢錯(cuò)錯(cuò)誤的檢錯(cuò)碼和不僅能發(fā)現(xiàn)錯(cuò)誤而且能自動(dòng)糾正錯(cuò)誤的糾錯(cuò)碼。常用的檢錯(cuò)碼有：奇偶校驗(yàn)循環(huán)冗余校驗(yàn)〔CRC，CyclicRedundancyCheck〕檢錯(cuò)的根本思路：發(fā)端按照給定的規(guī)那么，在K個(gè)信息比特后面增加L個(gè)按照某種規(guī)那么計(jì)算的校驗(yàn)比特；在接收端對(duì)收到的信息比特重新計(jì)算L個(gè)校驗(yàn)比特。比較接收到的校驗(yàn)比特和本地重新計(jì)算的校驗(yàn)比特，如果相同那么認(rèn)為傳輸無誤，否那么認(rèn)為傳輸有錯(cuò)。2024/1/1830奇偶校驗(yàn)(1)奇偶校驗(yàn)碼是一種通過增加冗余位使得碼字中“1〞的個(gè)數(shù)恒為奇數(shù)或偶數(shù)的編碼方法，它是一種檢錯(cuò)碼。漢明距離：任意兩個(gè)相同長(zhǎng)度的碼字比特取值不同的位置數(shù)。碼的最小漢明距離〔最小距離〕：任意兩個(gè)碼字之間距離的最小值。例如：有四個(gè)碼字〔000,011,101,110，最小距離為d=2〕2024/1/1831奇偶校驗(yàn)(2)奇偶校驗(yàn)的種類很多，這里給出一個(gè)例子。例：信息序列長(zhǎng)K=3，校驗(yàn)序列長(zhǎng)L=4。輸入信息比特為｛S1，S2，S3｝，校驗(yàn)比特為｛C1，C2，C3，C4｝。設(shè)發(fā)送的信息比特為{100},經(jīng)過奇偶校驗(yàn)碼生成的校驗(yàn)序列為{1110},那么發(fā)送的信息序列為{1001110}。假設(shè)經(jīng)過物理信道傳輸后，接收的序列為{1011110}，那么本地根據(jù)收到的信息比特{101}計(jì)算出的校驗(yàn)序列應(yīng)為{0011}。顯然該序列與接收到的校驗(yàn)序列{1110}不同，說明接收的信息序列有錯(cuò)。2024/1/1832奇偶校驗(yàn)(3)如果L取1，即C=S1⊕S2⊕S3⊕…⊕SK為最簡(jiǎn)單的單比特的奇偶校驗(yàn)碼，它使得生成的碼字〔信息比特+校驗(yàn)比特〕所含“1〞的個(gè)數(shù)為偶數(shù)。該碼可以發(fā)現(xiàn)所有奇數(shù)個(gè)比特錯(cuò)誤，但是不能發(fā)現(xiàn)任何偶數(shù)個(gè)錯(cuò)誤。在實(shí)際應(yīng)用奇偶校驗(yàn)碼時(shí)，每個(gè)碼字中K個(gè)信息比特可以是輸入信息比特流中K個(gè)連續(xù)的比特，也可以按一定的間隔〔如一個(gè)字節(jié)〕取K個(gè)比特。為了提高檢測(cè)錯(cuò)誤的能力，可將上述兩種取法重復(fù)使用。2024/1/1833檢錯(cuò)碼糾錯(cuò)編碼按照實(shí)現(xiàn)的功能可以分為：只能檢錯(cuò)錯(cuò)誤的檢錯(cuò)碼和不僅能發(fā)現(xiàn)錯(cuò)誤而且能自動(dòng)糾正錯(cuò)誤的糾錯(cuò)碼。常用的檢錯(cuò)碼有：奇偶校驗(yàn)循環(huán)冗余校驗(yàn)〔CRC，CyclicRedundancyCheck〕〔**重點(diǎn)掌握〕2024/1/1834循環(huán)冗余校驗(yàn)(1)CRC〔循環(huán)冗余校驗(yàn)〕是根據(jù)輸入比特序列(SK-1,SK-2,…,S1,S0)通過CRC算法產(chǎn)生L位的校驗(yàn)比特序列(CL-1,CL-2,…,C1,C0)CRC算法：步驟1將輸入比特序列表示為時(shí)延多項(xiàng)式的系數(shù)；S(D)=SK-1DK-1+SK-2DK-2+…+S1D+S0式中：D可以看成為一個(gè)時(shí)延因子，Di對(duì)應(yīng)比特Si所處的位置。舉例2024/1/1835循環(huán)冗余校驗(yàn)(2)步驟2根據(jù)給定的CRC校驗(yàn)比特的生成多項(xiàng)式〔即用于產(chǎn)生CRC比特的多項(xiàng)式〕產(chǎn)生校驗(yàn)比特的多項(xiàng)式系數(shù)：那么校驗(yàn)比特對(duì)應(yīng)以下多項(xiàng)式的系數(shù)式中，Remainder[?]表示取余數(shù)。式中的除法與普通的多項(xiàng)式長(zhǎng)除相同，其差異是系數(shù)是二進(jìn)制，其運(yùn)算以模2為根底?！才e例〕最終形成的發(fā)送序列為：(SK-1,SK-2,…,S1,S0，CL-1,…,C1,C0)2024/1/1836循環(huán)冗余校驗(yàn)(3)生產(chǎn)多項(xiàng)式的選擇不是任意的，它必須使得生產(chǎn)的校驗(yàn)序列有很強(qiáng)的檢錯(cuò)能力。常用的幾個(gè)L階CRC生產(chǎn)多項(xiàng)式為：CRC-16〔L=16〕CRC-CCITT〔L=16〕CRC-32〔L=32〕〔舉例〕2024/1/1837循環(huán)冗余校驗(yàn)(4)在接收端，將接收到的序列R(D)與生成多項(xiàng)式g(D)相除，并求其余數(shù)。如果，那么認(rèn)為接收無誤。針對(duì)CRC而言，當(dāng)K<2L-1比特時(shí)，剛剛介紹的三種生成多項(xiàng)式構(gòu)成的校驗(yàn)碼可以檢測(cè)出長(zhǎng)度不超過L的突發(fā)錯(cuò)誤。2024/1/18382.2.1過失控制(5)總結(jié)：奇偶檢驗(yàn)和CRC編碼僅能檢錯(cuò)，在接收端檢測(cè)到有錯(cuò)碼時(shí)，利用反向信道通知發(fā)送端，要求發(fā)送端重發(fā)，直到正確接收為止。---即自動(dòng)請(qǐng)求重發(fā)協(xié)議〔ARQ，AutomaticRetransmissionreQuest〕。通常情況下，這種技術(shù)需要雙向信道傳送重發(fā)指令。2024/1/1839第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/18402.2.2ARQ協(xié)議(1)前面解決了如何發(fā)現(xiàn)傳輸比特的錯(cuò)誤〔檢錯(cuò)〕，下面要解決當(dāng)接收端發(fā)現(xiàn)傳輸幀有錯(cuò)如何處理的方法。最簡(jiǎn)單的處理方法是〔收端〕自動(dòng)請(qǐng)求發(fā)端重發(fā)〔ARQ〕，也即是一種過失控制技術(shù)：檢錯(cuò)重發(fā)。收端通過反響信道〔該信道可以與前向傳輸相同，也可以不同〕以某種反響規(guī)那么通知發(fā)端重復(fù)上述過程，直到收端收到正確的幀為止。ARQ被廣泛地應(yīng)用于使用線的計(jì)算機(jī)通信系統(tǒng)中。對(duì)反響規(guī)那么和重傳規(guī)那么的設(shè)計(jì)，要保證整個(gè)自動(dòng)重傳協(xié)議的正確性和有效性。2024/1/18412.2.2ARQ協(xié)議(2)為了研究ARQ協(xié)議，我們對(duì)物理比特管道〔物理鏈路〕作如下假定：〔1〕在物理信道上傳輸?shù)膸竭_(dá)接收端前被時(shí)延了一個(gè)任意可變的時(shí)間；〔2〕幀在傳輸過程中可能會(huì)喪失，也可能出錯(cuò)；〔3〕幀到達(dá)的順序與發(fā)送的順序相同。2024/1/18422.2.2ARQ協(xié)議(3)有四種不同形式的ARQ重傳協(xié)議停等式ARQ返回n-ARQ選擇重發(fā)式ARQ并行等待式ARQ2024/1/1843停等式ARQ

(1)停等式ARQ〔Stop-and-WaitARQ〕的根本思想：在開始下一幀傳送以前，必須確保當(dāng)前幀已被正確接收。2024/1/1844停等式ARQ工作過程A發(fā)送一幀后，B如果接收正確，那么B向A返回一個(gè)肯定的應(yīng)答ACK〔ACKnowledgeCharacter〕；A必須在收到B的正確ACK后，方可發(fā)送下一幀。B如果接收錯(cuò)誤，那么B向A返回否認(rèn)應(yīng)答NAK〔NegativeAcknowledge〕。如果A發(fā)送一幀后〔并給定時(shí)器設(shè)置一個(gè)初值〕，在一個(gè)規(guī)定的時(shí)間內(nèi)〔定時(shí)器溢出〕，沒有收到對(duì)方的ACK，那么重發(fā)該幀。2024/1/1845停等式ARQ

(3)由于A到B之間的雙向鏈路都可能出錯(cuò)，上述協(xié)議能否正常工作？或者說如何保證該協(xié)議能夠正確工作呢？根本的方法是在傳輸?shù)膸性黾影l(fā)送序號(hào)〔SN〕和接收序號(hào)〔RN〕。接收序號(hào)RN通常用接收端希望接收的下一個(gè)發(fā)送幀的序號(hào)SN(也可以是下一幀的第一個(gè)字節(jié)的編號(hào))，即告訴發(fā)送端，正在等待的下一幀的序號(hào)。SN和RN是隨時(shí)間任意增加的，這樣就需要很大的比特域來發(fā)送序號(hào)。但實(shí)際上，可以用一個(gè)模值〔modN〕來表示。對(duì)于停等式ARQ，取模2就夠了。2024/1/1846停等式ARQ

(4)假設(shè)沒有發(fā)送序號(hào)SNAB丟失或延時(shí)發(fā)送端應(yīng)該增加一個(gè)發(fā)送序號(hào)2024/1/1847停等式ARQ

(5)假設(shè)沒有接收序號(hào)RN〔1〕接收端應(yīng)該增加一個(gè)接收序號(hào)；時(shí)延〔2〕通常情況下，A和B之間雙向都有幀傳輸，因而可將RN附帶在反向傳輸幀中。如果B再無其他數(shù)據(jù)傳送，那么單獨(dú)傳輸包含RN的無數(shù)據(jù)幀給A。2024/1/1848停等式ARQ算法描述(1)假定A向B發(fā)送分組〔A→B〕，A的發(fā)送算法如下：〔1〕置SN=0?！?〕如果從高層接收到一個(gè)分組，那么將SN指配給該分組；如果沒有高層分組，那么等待?！?〕將發(fā)送序號(hào)為SN的分組裝入物理幀中發(fā)送給接收節(jié)點(diǎn)B?！?〕如果從B接收的RN>SN，那么將SN加1，返回〔2〕。如果在規(guī)定的有限長(zhǎng)時(shí)間內(nèi)，沒有從B接收到RN>SN的幀〔應(yīng)答〕，那么返回〔3〕進(jìn)行重傳。2024/1/1849停等式ARQ算法描述(2)節(jié)點(diǎn)B的接收算法如下：〔1〕置RN=0。〔2〕無論何時(shí)從A正確接收一個(gè)SN=RN的幀，將該幀中的分組送給高層，并將RN加1?！?〕在接收到該分組后的一個(gè)規(guī)定的有限長(zhǎng)時(shí)間內(nèi)，將RN放入一幀的RN域中發(fā)給A。返回〔2〕。2024/1/1850停等式ARQ協(xié)議性能評(píng)估任何協(xié)議都可以從兩方面對(duì)其進(jìn)行評(píng)估：〔1〕正確性：協(xié)議始終能夠正常工作；可分為兩局部：穩(wěn)妥性〔Safety〕和活動(dòng)性〔Liveness〕?！?〕有效性：可用三個(gè)具體的值來表示：吞吐量、鏈路的利用率、分組延遲?！?*重點(diǎn)掌握〕2024/1/1851停等式ARQ算法描述吞吐量是指在給定的物理信道和輸入分組流的條件下，接收端能夠呈送給高層的分組速率〔分組/秒或比特/秒〕。鏈路的利用率是指物理層〔比特管道〕的傳輸容量中用于有效分組傳輸所占的比例。在信道中，如果被等待、重傳和其它不必要的傳輸分組所占的比例越少，那么信道的利用率就越高。分組延遲是指鏈路層從發(fā)端收到高層的分組開始到收端將該分組呈送給高層為止所需的時(shí)間。2024/1/1852停等式ARQ算法有效性分析(1)設(shè)數(shù)據(jù)幀是固定幀長(zhǎng)，其傳輸時(shí)間為TD秒，肯定和否認(rèn)應(yīng)答幀長(zhǎng)為TACK秒，物理信道的傳播時(shí)延為Tp秒，那么在忽略算法的處理時(shí)延的情況下，一幀的傳輸周期為〔TD+TP+TACK+TP〕假定任意一個(gè)數(shù)據(jù)幀平均需要發(fā)送NT次〔一次初發(fā)，NT－1次重發(fā)〕才能成功，那么該幀平均需要NT個(gè)傳輸周期。2024/1/1853停等式ARQ算法有效性分析(2)那么物理鏈路的最大平均利用率〔傳輸一幀的效率〕：令，忽略應(yīng)答幀的傳輸時(shí)間〔認(rèn)為TACK＝0〕，有2024/1/1854停等式ARQ算法有效性分析(3)假定又假定數(shù)據(jù)幀的誤幀率為p=1-q，應(yīng)答幀因長(zhǎng)度很短從而其出錯(cuò)的可能性可以忽略，即認(rèn)為應(yīng)答幀總是可以正確傳輸，那么一個(gè)數(shù)據(jù)幀發(fā)送i次成功的概率為：求NT〔需要多少次數(shù)發(fā)送才能將一幀數(shù)據(jù)正確送出〕代入求得鏈路的最大平均利用率：p,TP與U的關(guān)系2024/1/1855停等式ARQ算法有效性分析(4)平均吞吐量〔接收端能呈現(xiàn)給高層的分組速率〕：停等式ARQ的平均分組延遲為：D=組幀時(shí)延+NT(TD+TP+TACK+TP)組幀時(shí)延是指從高層分組的第一比特到達(dá)鏈路層開始，到鏈路層將該分組的所有比特收齊，經(jīng)過增加控制頭〔如幀起止標(biāo)志發(fā)送序號(hào)，接收序號(hào)等〕和校驗(yàn)比特〔CRC〕形成可傳輸?shù)臄?shù)據(jù)幀為止。2024/1/1856停等式ARQ算法有效性分析(5)組幀時(shí)延取決于網(wǎng)絡(luò)層與鏈路層之間的接口速率和方式，以及鏈路層的處理速度和方式。例如：假設(shè)網(wǎng)絡(luò)層與鏈路層運(yùn)行在相同的微處理器或計(jì)算機(jī)系統(tǒng)上，采用數(shù)據(jù)塊傳遞的方式來傳遞分組，那么組幀時(shí)延可以相當(dāng)小，且可以忽略。如果網(wǎng)絡(luò)層與鏈路層采用傳輸速率為R〔比特/秒〕的接口交換數(shù)據(jù)，那么組幀的時(shí)延為K/R〔這里K為分組的長(zhǎng)度〔比特?cái)?shù)〕〕。2024/1/1857停等式ARQ算法有效性分析(6)例：有三條物理鏈路及其傳輸特性一條是衛(wèi)星鏈路，信道速率為64Kbps，傳播時(shí)延為Tp=270ms;一條是經(jīng)過網(wǎng)鏈路，長(zhǎng)為5000km，信道傳輸速率為9600bps；一條是同軸電纜提供的長(zhǎng)為500m的鏈路，信道速率為10Mbps。試求幀長(zhǎng)為L(zhǎng)=1000bit，10000bit時(shí)停等式ARQ的鏈路最大平均利用率U，最大平均吞吐量和分值時(shí)延。2024/1/1858停等式ARQ算法有效性分析(7)例：有三條物理鏈路及其傳輸特性從表中可以看出傳播時(shí)延相對(duì)于幀長(zhǎng)的比例a越小，鏈路的利用率越高，吞吐量也越大，時(shí)延也越小。結(jié)論：在衛(wèi)星鏈路上采用停等式ARQ協(xié)議效率較低?！舶腚p工〕2024/1/18592.2.2ARQ協(xié)議(3)有四種不同形式的ARQ重傳協(xié)議停等式ARQ返回n-ARQ選擇重發(fā)式ARQ并行等待式ARQ2024/1/1860返回n-ARQ

(1)返回n-ARQ(GoBacknARQ，GBN)的根本思路是：發(fā)端在沒有收到對(duì)方應(yīng)答的情況下，可以連續(xù)發(fā)送n幀。收端僅接收正確且順序連續(xù)的幀，其應(yīng)答中的RN表示RN以前的所有幀都已正確接收。這里收端不需要每收到一個(gè)正確的幀就發(fā)出一個(gè)應(yīng)答，可對(duì)接收到的正確順序的最大幀序號(hào)進(jìn)行應(yīng)答。返回n-ARQ是應(yīng)用最廣泛的ARQ協(xié)議，已經(jīng)應(yīng)用于HDLC等標(biāo)準(zhǔn)的DLC協(xié)議中。2024/1/1861返回n-ARQ

(2)返回n-ARQ參數(shù)n〔滑動(dòng)窗口寬度〕：從圖中可以看出，如果收端能及時(shí)返回應(yīng)答，那么發(fā)端可連續(xù)不斷地全速連續(xù)發(fā)送幀?！踩绻覀儨p緩應(yīng)答返回的速率，那么可以控制發(fā)端發(fā)送幀的速率，從而到達(dá)速率控制的目的。〕2024/1/1862返回n-ARQ

(2)下面考察雙向都有數(shù)據(jù)傳輸并且?guī)L(zhǎng)度不等長(zhǎng)時(shí)，發(fā)送端窗口滑動(dòng)的情況。情況一：傳輸錯(cuò)誤對(duì)發(fā)端的影響。盡管2,3,4號(hào)幀傳輸正確，但它們的序號(hào)與接收端期望的序號(hào)不符合，而不能被正確接收，因而還需要重傳。2024/1/1863返回n-ARQ

(3)情況一：傳輸錯(cuò)誤對(duì)發(fā)端的影響,改進(jìn)方法解決方法是可以縮短發(fā)送窗口n的大小，或是加快出錯(cuò)的反響速度。即收端一旦接收到一個(gè)錯(cuò)誤幀，立即返回一個(gè)短的應(yīng)答幀〔監(jiān)控幀〕，使發(fā)端盡快返回重發(fā)。2024/1/1864返回n-ARQ

(4)情況二：反向幀長(zhǎng)對(duì)發(fā)端的影響。應(yīng)答的超長(zhǎng)時(shí)延可能導(dǎo)致發(fā)端重發(fā)。改進(jìn)方法：增大n。只要n個(gè)正向傳輸幀長(zhǎng)之和大于反向幀長(zhǎng)，就能緩解帶來的影響。2024/1/1865返回n-ARQ

(5)情況三：反向幀出錯(cuò)對(duì)發(fā)端的影響。〔可能沒有影響〕應(yīng)答的出錯(cuò)可能導(dǎo)致發(fā)端重發(fā)。改進(jìn)方法：可以增大n。增加n之后，出錯(cuò)的應(yīng)答幀被后來應(yīng)答幀補(bǔ)救的概率很大，降低出錯(cuò)帶來的影響。2024/1/1866返回n-ARQ

(6)返回n-ARQ的序號(hào)也可以用模為m(m>n)的整數(shù)來表示。例如，取模8那么可用3比特來表示序號(hào)〔0~7〕，此時(shí)最大的窗口取值只能為7，如果n=m，那么系統(tǒng)無法正常工作。其原因如下：假設(shè)，發(fā)端發(fā)送8幀后，收到了對(duì)方的所有確認(rèn)，那么將發(fā)送新的8幀，其序號(hào)為0~7。如果發(fā)端發(fā)送8幀后，收端發(fā)送的應(yīng)答未能到達(dá)發(fā)端，發(fā)端將重發(fā)這8幀，其序號(hào)仍為0~7。由于這兩種情況對(duì)收端而言是無法區(qū)分的，因而在接收到第二次序號(hào)為0~7的幀時(shí)，收端無法區(qū)分是新的幀還是重發(fā)的幀。2024/1/1867返回n-ARQ協(xié)議性能分析(1)**假定數(shù)據(jù)幀長(zhǎng)是一個(gè)固定值，且假定應(yīng)答幀傳輸時(shí)間很小可以忽略(TACK=0)。返回n-ARQ的效率與鏈路的傳輸時(shí)延(TP)，幀長(zhǎng)(TD)，窗口n等參數(shù)緊密相關(guān)。令d=TD+2TP+TACK=TD+2TP,d為一幀的發(fā)送〔接收〕周期。nTD為一次發(fā)送n幀的時(shí)間〔發(fā)送〕。2024/1/1868返回n-ARQ協(xié)議性能分析(2)通過比較nTD和d，得出不同的結(jié)果。情況1：當(dāng)nTD>d，應(yīng)答幀可以及時(shí)返回。情況2：當(dāng)nTD<d，應(yīng)答幀在定時(shí)器時(shí)間內(nèi)或溢出之后才到達(dá)發(fā)端。2024/1/1869返回n-ARQ協(xié)議性能分析(2)討論誤幀率〔p〕是否存在條件下的協(xié)議性能。2024/1/1870返回n-ARQ協(xié)議性能分析(3)情況1：當(dāng)nTD>d，應(yīng)答幀可以及時(shí)返回。發(fā)端不再需要空余的等待應(yīng)答時(shí)間，而是連續(xù)不斷地向鏈路上發(fā)送數(shù)據(jù)幀。由于誤幀率為0，鏈路的最大平均利用率

U=1。情況2：當(dāng)nTD<d

，應(yīng)答幀在發(fā)端的定時(shí)器時(shí)間內(nèi)或溢出之后到達(dá)發(fā)端，此時(shí)的鏈路最大平均利用率

U=nTD/d。即在時(shí)間d=TD+2TP內(nèi)，發(fā)端最多可以發(fā)送n個(gè)幀。2024/1/1871返回n-ARQ協(xié)議性能分析(4)討論誤幀率〔p〕是否存在條件下的協(xié)議性能。2024/1/1872返回n-ARQ協(xié)議性能分析(5)情況1：nTD>d設(shè)傳輸過程中的誤幀率為p，每出現(xiàn)一個(gè)錯(cuò)幀，發(fā)端就會(huì)重復(fù)n幀。假設(shè)發(fā)送一幀，平均需要i次才能傳輸成功〔其中成功傳輸1次，剩余i-1均是重傳，每一次重傳需要發(fā)送n個(gè)數(shù)據(jù)幀〕。那么i次傳輸所需要的總幀數(shù)為：1+(i-1)n；每一幀需要傳輸i次才能正確接收的概率為：2024/1/1873返回n-ARQ協(xié)議性能分析(6)情況1：nTD>d正確接收一幀需要傳輸?shù)拇螖?shù)：鏈路的信道利用率U：2024/1/1874返回n-ARQ協(xié)議性能分析(7)情況2：nTD<d鏈路的信道利用率U：

2024/1/1875返回n-ARQ協(xié)議性能分析(8)當(dāng)p=0.01時(shí)，鏈路利用率與相對(duì)傳輸時(shí)延、窗口n的大小緊密相關(guān)。當(dāng)相對(duì)傳輸時(shí)延相對(duì)較大〔如在衛(wèi)星鏈路中〕時(shí)，為了到達(dá)較高的鏈路利用率，應(yīng)選擇較大的n。從圖中可以看出，當(dāng)時(shí)，〔表示取大于等于x的最小整數(shù)〕，鏈路利用率最高。最正確的窗口寬度〔nTD〕近似等于d，即nTD=TD+2TP2024/1/18762.2.2ARQ協(xié)議(4)有四種不同形式的ARQ重傳協(xié)議停等式ARQ返回n-ARQ選擇重發(fā)式ARQ并行等待式ARQ2024/1/1877選擇重發(fā)式ARQ

(1)選擇重發(fā)式ARQ〔SelectiveRepeatARQ〕是對(duì)返回n-ARQ的改進(jìn)，其根本思想為：返回n-ARQ中，如果前向傳輸?shù)哪骋粋€(gè)幀出錯(cuò)，那么在收到對(duì)方的否認(rèn)應(yīng)答后，該幀及其后續(xù)的幀都要重傳，而不管這些后續(xù)是否傳輸正確。選擇重發(fā)式ARQ的思路與返回n-ARQ相同，其窗口仍為n，但僅僅重發(fā)有錯(cuò)的幀。2024/1/1878選擇重發(fā)式ARQ

(2)為了實(shí)現(xiàn)選擇有錯(cuò)幀進(jìn)行重發(fā)的目的，這就要求接收節(jié)點(diǎn)具有對(duì)分組排序的能力〔因?yàn)檫@時(shí)接收到的分組是亂序的〕，并且在應(yīng)答時(shí)除了應(yīng)答RN以外，還要包括大于RN的哪些幀已被正確接收的信息。接收節(jié)點(diǎn)可以用RN+k個(gè)比特〔每個(gè)比特的位置的取值對(duì)應(yīng)于RN后面第n個(gè)幀的接收狀態(tài)是ACK或NAK〕來進(jìn)行應(yīng)答。當(dāng)RN和SN采用模m來表示時(shí)，要求m≥2n；否那么，如果取m>n，會(huì)引起接收數(shù)據(jù)的序號(hào)混淆。2024/1/1879選擇重發(fā)式ARQ

(3)選擇重發(fā)式ARQ的鏈路利用率同樣可用和返回n－ARQ同樣的方式來表示，但這里重傳的幀僅為出錯(cuò)的幀，即從而可得選擇重發(fā)式ARQ的鏈路利用率為：2024/1/18802.2.2ARQ協(xié)議(4)有四種不同形式的ARQ重傳協(xié)議停等式ARQ返回n-ARQ選擇重發(fā)式ARQ并行等待式ARQ2024/1/1881并行等待式ARQ

(1)ARPANETARQ采用了8個(gè)并行等待式ARQ，每一個(gè)等待式ARQ對(duì)應(yīng)一個(gè)虛似信道。輸入分組可以任意分配到空閑的虛擬信道A-H上。如果所有虛信道忙，分組將在DLC層外等待。2024/1/1882并行等待式ARQ

(2)處于忙狀態(tài)的虛擬信道上的分組被復(fù)接到物理比特管道上傳輸。可以采用輪詢的方法來循環(huán)查詢各個(gè)虛擬信道，當(dāng)輪詢到某一忙信道時(shí)，如果應(yīng)答還沒有收到，那么將該虛擬信道的分組再次發(fā)送到物理信道上。因此，該復(fù)接方式就不需要設(shè)置定時(shí)器來計(jì)算等待應(yīng)答的時(shí)間。2024/1/1883并行等待式ARQ

(3)由于采用mod2方式，僅需一位就可以表示SN和RN。為了區(qū)分不同的虛擬信道，在幀頭中還增加了3bit的虛擬信道號(hào)。2024/1/1884第二章內(nèi)容概述2.1組幀技術(shù)2.1.1面向字符的組幀技術(shù)2.1.2面向比特的組幀技術(shù)2.1.3采用長(zhǎng)度計(jì)數(shù)的組幀技術(shù)2.2鏈路層的過失控制技術(shù)2.2.1過失控制2.2.2ARQ協(xié)議2.2.3最正確幀長(zhǎng)2.2.4常用的糾錯(cuò)編碼2.3標(biāo)準(zhǔn)數(shù)據(jù)鏈路控制協(xié)議及其初始化2.4網(wǎng)絡(luò)層和運(yùn)輸層的點(diǎn)對(duì)點(diǎn)傳輸協(xié)議2024/1/18852.2.3最正確幀長(zhǎng)(1)從兩個(gè)方面來考察最正確幀長(zhǎng)：〔1〕在一條鏈路上使傳輸效率最高的最正確幀長(zhǎng)。〔2〕是在多條鏈路構(gòu)成的傳輸路徑上，使得傳輸效率最高的最正確幀長(zhǎng)。2024/1/18862.2.3最正確幀長(zhǎng)(2)在一條鏈路上使傳輸效率最高的最正確幀長(zhǎng)在實(shí)際傳輸過程中，每一幀數(shù)據(jù)〔lfbit〕通常包括數(shù)據(jù)負(fù)荷〔ldbit〕和控制信息〔lhbit〕，即lf=ld+lh。如果幀長(zhǎng)較短，控制比特所占用的比例較大，因而鏈路利用率下降。如果幀長(zhǎng)較長(zhǎng)，在數(shù)據(jù)幀傳輸過程中，因信道誤碼的存在而導(dǎo)致幀傳輸錯(cuò)誤的概率較大，重傳的次數(shù)將增大，這也會(huì)導(dǎo)致鏈路利用率的下降。因此存在一個(gè)最正確幀長(zhǎng)，使鏈路利用率最高。2024/1/18872.2.3最正確幀長(zhǎng)(3)鏈路的誤比特率為pb(信道錯(cuò)誤為隨機(jī)錯(cuò)誤)，那么數(shù)據(jù)幀的過失率或誤幀率p為：當(dāng)pb很小時(shí)，上式可以近似為：2024/1/18882.2.3最正確幀長(zhǎng)(4)以停等式ARQ為例，鏈路的有效利用率：其中Tb為比特寬度，。將代入并經(jīng)整理得到：2024/1/18892.2.3最正確幀長(zhǎng)(5)將上式對(duì)ld求導(dǎo)，并令其為零，可得最正確數(shù)據(jù)幀長(zhǎng)度為2024/1/18902.2.3最正確幀長(zhǎng)(6)從兩個(gè)方面來考察最正確幀長(zhǎng)：〔1〕在一條鏈路上使傳輸效率最高的最正確幀長(zhǎng)?！?〕是在多條鏈路構(gòu)成的傳輸路徑上，使得傳輸效率最高的最正確幀長(zhǎng)。2024/1/18912.2.3最正確幀長(zhǎng)(7)下面，我們將討論在分組經(jīng)過屢次中轉(zhuǎn)才能到達(dá)目的節(jié)點(diǎn)時(shí)，能使得網(wǎng)絡(luò)開銷最小和時(shí)延最小情況下的最正確幀長(zhǎng)。一條消息分成不同長(zhǎng)度的分組經(jīng)過中轉(zhuǎn)到達(dá)目的