CRC碼算法設(shè)G(x)為r階，在幀的末尾加r個0，使幀為m+r位，相應(yīng)多項式為xrM(x)；按模2除法用對應(yīng)于G(x)的位串去除對應(yīng)于xrM(x)的位串；按模2減法從對應(yīng)于xrM(x)的位串中減去余數(shù)（等于或小于r位），結(jié)果就是要傳送的帶校驗和的多項式T(x)。CRC碼算法CRC的檢錯能力發(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，則差錯不能發(fā)現(xiàn)；否則，可以發(fā)現(xiàn)。四個多項式已成為國際標(biāo)準(zhǔn)CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32硬件實現(xiàn)CRC校驗。CRC的檢錯能力信息位串1010001101， K(x)＝x9+x7+x3+x2+1生成多項式110101， G(x)＝x5+x4+x2+1CRC計算例程信息位串1010001101，CRC計算例程CRC檢測方法的特點相比于奇偶校驗法，CRC校驗碼的檢錯能力很強，而奇偶校驗法實現(xiàn)簡單，檢錯能力低，一般只適合于通信要求較低環(huán)境；CRC校驗碼除了能查出離散錯外，還能檢查出突發(fā)錯，主要包括：所有單個錯；全部離散的二位錯；全部奇數(shù)個錯；全部長度小于或等于K位的突發(fā)錯（K是生成多項式的最高冪）；CRC檢測方法的特點相比于奇偶校驗法，CRC校驗碼的檢錯能檢驗和(checksum)算法檢驗字段初值置0；待檢驗的數(shù)據(jù)拆分成一個個與檢驗字段等長的分片，不足部分補0以滿足長度要求；將所有分片逐位取反，并連續(xù)累加，丟棄最高進(jìn)位；計算結(jié)果置入檢驗字段；填充的0僅參與計算，不參與傳輸；檢驗字段自身不參與計算；接收段執(zhí)行相同的過程，并將計算結(jié)果和傳輸過來的檢驗和進(jìn)行比較以決定數(shù)據(jù)是否出現(xiàn)差錯；適用于高層的字節(jié)型協(xié)議，如IP、TCP、UDP等；常見分片長度：8位、16位和32位。檢驗和(checksum)算法檢驗字段初值置0；檢驗和算法舉例待傳輸數(shù)據(jù)為：10010100,01110110,1100計算過程~(10010100)+~(01110110)=1111010011110100+~(11000000)=00110011帶檢驗和的傳輸數(shù)據(jù)是10010100,01110110,110000110011檢驗和算法舉例待傳輸數(shù)據(jù)為：10010100,0111011數(shù)據(jù)鏈路層通信模型數(shù)據(jù)鏈路層通信模型數(shù)據(jù)鏈路層通信模型數(shù)據(jù)鏈路層通信模型數(shù)據(jù)鏈路層控制機制數(shù)據(jù)鏈路層功能：通過該層協(xié)議的作用，在一條不太可靠的通訊鏈路上實現(xiàn)可靠的數(shù)據(jù)傳輸；數(shù)據(jù)鏈路：在數(shù)據(jù)鏈路層，通訊的對等實體之間的數(shù)據(jù)傳輸通道，包括物理鏈路和必要的傳輸控制規(guī)程；理想的數(shù)據(jù)鏈路基于以下兩個假設(shè)：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總能夠來得及接收、處理并上交。也就是說收方有足夠的接收緩存區(qū)和處理速度；鏈路是理想的傳輸通道，傳輸?shù)娜魏螖?shù)據(jù)既不會出現(xiàn)差錯也不會丟失；數(shù)據(jù)鏈路層控制機制數(shù)據(jù)鏈路層功能：通過該層協(xié)議的作用，在一條數(shù)據(jù)鏈路層控制機制流量控制：保證發(fā)送數(shù)據(jù)在如何情況下都不會“淹沒”收方接收緩存區(qū)，而且還應(yīng)使傳輸達(dá)到理想的吞吐率，由收方控制發(fā)方的數(shù)據(jù)流量是計算機網(wǎng)絡(luò)中流量控制的一個基本思路；一個重要的方法是滑動窗口機制。差錯控制：使得鏈路傳輸出現(xiàn)差錯時等到補救。主要有兩種差錯發(fā)生，幀丟失和幀損壞。基本方式是確定－重發(fā)機制（反饋重發(fā)糾錯）數(shù)據(jù)鏈路層控制機制數(shù)據(jù)鏈路層控制機制數(shù)據(jù)鏈路層控制機制4.5滑動窗口機制機制：在發(fā)送方和接收方分別設(shè)置發(fā)送窗口和接收窗口，在數(shù)據(jù)傳輸過程中受控的向前滑動，從而控制傳輸過程。發(fā)送窗口：對發(fā)方進(jìn)行流量控制，其大小WT指明在收到對方ACK之前發(fā)方最多可以發(fā)送多少個數(shù)據(jù)幀，落在窗口內(nèi)的幀可以連續(xù)發(fā)送。接收窗口：控制哪些數(shù)據(jù)幀可以接收，只有到達(dá)的數(shù)據(jù)幀的序號落在接收窗口內(nèi)時才可以被接收，否則將被丟棄。當(dāng)收方收到一個有序且無差錯的幀后，接收窗口想起滑動，準(zhǔn)備接收下一幀，并向發(fā)方發(fā)送一個確認(rèn)（ACK）。為了提高效率收方可以采用累積確認(rèn)或捎帶確認(rèn)。4.5滑動窗口機制機制：在發(fā)送方和接收方分別設(shè)置發(fā)送窗口發(fā)送方的滑動窗口作用設(shè)發(fā)送序號用3個比特編碼，WT＝5發(fā)送方的滑動窗口作用設(shè)發(fā)送序號用3個比特編碼，WT＝54.6停等協(xié)議差錯控制的基本方式是確認(rèn)－重發(fā)機制，即反饋重發(fā)糾錯，收方對收到的數(shù)據(jù)予以某種形式的反饋信息，發(fā)方根據(jù)反饋信息對出錯的幀進(jìn)行重發(fā)。一般基于以下措施：差錯發(fā)現(xiàn)確認(rèn)ACK累積確認(rèn)負(fù)確認(rèn)（NAK）超時重發(fā)

確認(rèn)－重發(fā)機制又稱為自動請求重發(fā)（ARQ），根據(jù)確認(rèn)－重發(fā)方式不同，分為停等ARQ、回退-NARQ、選擇重傳ARQ。4.6停等協(xié)議差錯控制的基本方式是確認(rèn)－重發(fā)機制停等ARQ停等ARQ機制：在發(fā)方發(fā)出一個數(shù)據(jù)幀后停下來不再發(fā)送，等待收方ACK到達(dá)后再發(fā)送下一幀。（實際使用滑動窗口技術(shù)，發(fā)送窗口WT=1，接收窗口也是1）處理的差錯問題：收方收到發(fā)來的數(shù)據(jù)幀，但檢測出幀有差錯；發(fā)方發(fā)出的數(shù)據(jù)幀丟失，收方不可能發(fā)出ACK；收方收到數(shù)據(jù)幀，但ACK丟失；（重復(fù)幀處理，對數(shù)據(jù)幀和確認(rèn)幀邊上序號，對于停等ARQ，用0和1交替編號。發(fā)方正確收到0/1號數(shù)據(jù)幀，發(fā)回ACK1/ACK0，確認(rèn)序號表明期待收到的下一個序號）停等ARQ停等ARQ機制：在發(fā)方發(fā)出一個數(shù)據(jù)幀后停下來不再發(fā)在無差錯的正常情況下，停等ARQ把流量控制在每往返時間一個數(shù)據(jù)幀的水平，一個往返時間為：TDATA+TACK+2τ+TPRO鏈路利用率?=TDATA/(TDATA+TACK+2τ+TPRO)≈TDATA/(TDATA+2τ)=1/(1+2α)

α=τ/TDATA=鏈路比特長度/幀比特長度出錯差錯而重傳情況下，停等ARQ引起的重傳時間等于超時重傳的定時時間TOUT解決鏈路利用率低的辦法：回退-NARQ和選擇重傳ARQ停等ARQ的效率分析在無差錯的正常情況下，停等ARQ把流量控制在每往返時間一個數(shù)回退-NARQ使用滑動窗口機制，WT>1,WR=1,發(fā)方在每收到一個ACK之前不用等待，可以連續(xù)發(fā)送窗口內(nèi)的多個幀，如果這時收到ACK，還可以則調(diào)整發(fā)方窗口，繼續(xù)發(fā)送后續(xù)的幀；（連續(xù)ARQ）對于發(fā)送的每一幀設(shè)置超時定時器，發(fā)方發(fā)出一個幀后啟動該定時器。若因幀效驗錯誤、幀丟失、ACK丟失使定時器超時后還沒有收到ACK，發(fā)方則要重復(fù)此幀，而且還必須重發(fā)此幀后面所有的已發(fā)幀;（回退-NARQ）收方每收到一次失序的數(shù)據(jù)幀時都重發(fā)上次發(fā)送過的ACK，這可彌補上次已發(fā)送的確認(rèn)幀的丟失；回退-NARQ使用滑動窗口機制，WT>1,WR=1,發(fā)方在回退-NARQ回退-NARQ選擇重傳ARQ接收窗口WR>1,這樣可以接收和保存正確到達(dá)的失序幀出現(xiàn)傳輸差錯時只重傳出錯的幀，后續(xù)的正確到達(dá)的幀不再重傳，提高了信道的利用率WT=WR<=2n/2選擇重傳ARQ接收窗口WR>1,這樣可以接收和保存正確到達(dá)的4.5停等協(xié)議前面介紹了幀邊界的劃分辦法和檢查幀是否錯誤的方法，如果幀在傳輸過程中出現(xiàn)錯誤，發(fā)送方就要重發(fā)錯誤幀，如何控制幀重發(fā)？簡單停等協(xié)議帶流量控制的停等協(xié)議帶差錯控制的停等協(xié)議4.5停等協(xié)議前面介紹了幀邊界的劃分辦法和檢查幀是否簡單停等協(xié)議假設(shè)：通信線路（信道）不損壞或丟失信息幀。發(fā)送數(shù)據(jù)的速率低于接受數(shù)據(jù)的速率

理想傳輸協(xié)議、單工傳輸工作過程發(fā)送程序:取數(shù)據(jù)，構(gòu)成幀，發(fā)送幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層。簡單停等協(xié)議假設(shè)：帶流量控制的停等協(xié)議－－無差錯單工停等協(xié)議增加約束條件：接收方不能無休止接收。例如：緩沖區(qū)數(shù)量有限，接受速率比發(fā)送速率低等。解決辦法：

接收方每收到一個幀后，給發(fā)送方回送一個響應(yīng)。工作過程發(fā)送程序：取數(shù)據(jù)，成幀，發(fā)送幀，等待響應(yīng)幀；接收程序：等待，接收幀，送數(shù)據(jù)給高層，回送響應(yīng)幀。帶流量控制的停等協(xié)議－－無差錯單工停等協(xié)議增加約束條件：接收帶差錯控制的停等協(xié)議增加約束條件：信道（線路）有差錯，信息幀可能損壞或丟失。使用正向應(yīng)答+重發(fā)機制來解決差錯的控制問題。使用超時重發(fā)計時器解決數(shù)據(jù)幀、確認(rèn)幀丟失問題。為判斷重復(fù)幀，必須在數(shù)據(jù)幀附加上不同的發(fā)送序號，數(shù)據(jù)序號采用循環(huán)序號機制。協(xié)議效率低帶差錯控制的停等協(xié)議增加約束條件：信道（線路）有差錯，信息幀數(shù)據(jù)幀差錯情況數(shù)據(jù)幀差錯情況有噪聲信道單工停等協(xié)議流程圖從網(wǎng)絡(luò)層取數(shù)，成幀發(fā)送幀幀到否應(yīng)答到否超時否重復(fù)正確否接收幀，送網(wǎng)絡(luò)層發(fā)應(yīng)答發(fā)送幀應(yīng)答幀YNYNYNNY定時器丟棄丟棄NY注：P127有噪聲信道單工停等協(xié)議流程圖從網(wǎng)絡(luò)層取數(shù)，成幀發(fā)送幀幀到否應(yīng)數(shù)據(jù)幀間時序關(guān)系數(shù)據(jù)幀間時序關(guān)系停等協(xié)議的效率分析重傳時間兩個發(fā)送成功的數(shù)據(jù)幀間最小時間間隔

正確傳送一個數(shù)據(jù)幀所需的平均時間: tav＝tT(1＋一個幀的平均重傳次數(shù))

停等協(xié)議的效率分析重傳時間停等協(xié)議的效率分析（續(xù)）每秒成功發(fā)送的最大幀數(shù)就是鏈路的最大吞吐量λmax，顯然：λmax＝1/tav＝(1-p)/tT。在發(fā)送方，設(shè)數(shù)據(jù)幀的實際到達(dá)率為λ（即每秒到達(dá)λ個幀），則λ不應(yīng)超過最大吞吐量λmax，即λ≤(1-p)/tT，用時間tf進(jìn)行規(guī)一化，得出規(guī)一化的吞吐量β為：β≡λtf≤(1-p)/α<1，其中參數(shù)α是tT的規(guī)一化時間：α≡tT/tf≥1。當(dāng)重傳時間小于發(fā)送時間時，α＝1，此時的規(guī)一化吞吐量β≤(1-p)。針對單工協(xié)議效率低，引入連續(xù)ARQ和選擇重傳ARQ。停等協(xié)議的效率分析（續(xù)）每秒成功發(fā)送的最大幀數(shù)就是鏈路的最大4.6連續(xù)ARQ協(xié)議1、工作原理

連續(xù)停等協(xié)議是指不需要等前面幀的應(yīng)答收到就可連續(xù)不斷的發(fā)下面的幀。1）全部重發(fā)流水線協(xié)議當(dāng)一幀出錯時，需重發(fā)出錯幀之后的所有幀；接收方的緩沖區(qū)數(shù)量只需要一個。2）選擇重發(fā)流水線協(xié)議當(dāng)一幀出錯時，只重發(fā)出錯幀；接收方的緩沖區(qū)數(shù)量足夠多。4.6連續(xù)ARQ協(xié)議1、工作原理連續(xù)ARQ協(xié)議的工作原理連續(xù)ARQ協(xié)議的工作原理滑動窗口協(xié)議滑動窗口協(xié)議是對連續(xù)停等協(xié)議的改進(jìn)，它能夠控制已發(fā)送但未確認(rèn)的數(shù)據(jù)幀的個數(shù)（滑動窗口的大小）。數(shù)據(jù)幀序號：0~2n-1；發(fā)送窗口窗口尺寸：允許連續(xù)發(fā)送未應(yīng)答的幀的個數(shù)數(shù)據(jù)允許發(fā)送的條件：上界－下界<窗口尺寸窗口滑動的條件窗口上限移動：發(fā)送數(shù)據(jù)幀；窗口下限移動：收到應(yīng)答幀接收窗口窗口尺寸：允許連續(xù)接收未處理的幀的個數(shù)數(shù)據(jù)允許接收的條件：數(shù)據(jù)序號落在接收窗口中窗口滑動的條件發(fā)送應(yīng)答幀后上下界同時移動滑動窗口協(xié)議滑動窗口協(xié)議是對連續(xù)停等協(xié)議的改進(jìn)，發(fā)送窗口作用發(fā)送窗口作用接收窗口作用接收窗口作用窗口大小與序號關(guān)系出錯全部重傳WT>WR

，WR=1WT≤2n-1

選擇性重傳WT

=WR

WR≤2n-1窗口大小與序號關(guān)系出錯全部重傳4.8HDLC協(xié)議面向比特的鏈路層協(xié)議IBM的SNA使用的數(shù)據(jù)鏈路協(xié)議SDLC（SynchronousDataLinkControlprotocol）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作為X.25網(wǎng)絡(luò)接口標(biāo)準(zhǔn)的一部分，后來改為LAPB。面向字符的鏈路層協(xié)議ISO的IS1745，基本型傳輸控制規(guī)程及其擴(kuò)充部分（BM和XBM）IBM的二進(jìn)制同步通信規(guī)程（BSC）DEC的數(shù)字?jǐn)?shù)據(jù)通信報文協(xié)議（DDCMP）PPP—Point-to-PointProtocol，Internet的協(xié)議。4.8HDLC協(xié)議面向比特的鏈路層協(xié)議4.8HDLCHDLC廣泛應(yīng)用于X.25（是ITU-T為廣域網(wǎng)WAN通信所建議的一種數(shù)據(jù)分組交換網(wǎng)絡(luò)協(xié)議）及其他許多協(xié)議中。HDLC是面向比特的同步通信協(xié)議，主要為全雙工點對點操作提供完整的數(shù)據(jù)透明度。HDLCLAPB是一種高效協(xié)議，為確保流量控制、差錯監(jiān)測和恢復(fù)它要求額外開銷最小。如果數(shù)據(jù)在兩個方向上（全雙工）相互傳輸，數(shù)據(jù)幀本身就會傳送所需的信息從而確保數(shù)據(jù)完整性。HDLC是X.25棧的一部分。4.8HDLCHDLC廣泛應(yīng)用于X.25（是ITU-T數(shù)據(jù)站（簡稱站station），由計算機和終端組成，負(fù)責(zé)發(fā)送和接收幀。HDLC涉及三種類型的站：主站（primarystation）：主要功能是發(fā)送命令（包括數(shù)據(jù)），接收響應(yīng)，負(fù)責(zé)整個鏈路的控制（如系統(tǒng)的初始、流控、差錯恢復(fù)等）；次站（secondarystation）：主要功能是接收命令，發(fā)送響應(yīng)，配合主站完成鏈路的控制；組合站（combinedstation）：同時具有主、次站功能，既發(fā)送又接收命令和響應(yīng)，并負(fù)責(zé)整個鏈路的控制。在一條公共通信鏈路上的一個主戰(zhàn)和一個次站或多個站之間交換數(shù)據(jù)，這是HDLC使用的典型鏈路結(jié)構(gòu)。HDLC數(shù)據(jù)站種類數(shù)據(jù)站（簡稱站station），由計算機和終端組成，負(fù)責(zé)發(fā)HDLC的鏈路配置非平衡配置：用于點對點鏈路和多點鏈路，鏈路上的站點分為主站和從站；平衡配置：用于點對點鏈路，鏈路兩端的站點平等；HDLC的鏈路配置非平衡配置：用于點對點鏈路和多點鏈路，鏈路HDLC操作模式正規(guī)響應(yīng)模式NRM（NormalResponseMode）適用于非平衡構(gòu)型。只有當(dāng)主站向次站發(fā)出探詢后，次站才能獲得傳輸幀的許可。異步響應(yīng)模式ARM（AsynchronousResponseMode）適用于非平衡構(gòu)型。次站可以隨時傳輸幀，不必等待主站的探詢。異步平衡模式ABM（AsynchronousBalancedMode）適用于通信雙方都是組合站的平衡構(gòu)型，雙方具有同等能力。HDLC操作模式正規(guī)響應(yīng)模式NRM（NormalResHDLC的幀結(jié)構(gòu)（1）定界符8bit01111110，采用0比特填充地址域（Address）8bit非平衡配置，寫入從站地址，用來區(qū)分終端；平衡配置，寫入應(yīng)答站地址，全1表示廣播地址，全0無效；HDLC的幀結(jié)構(gòu)（1）定界符8bitHDLC的幀結(jié)構(gòu)（2）控制域（Control）8b：用作序號、確認(rèn)和其它目的數(shù)據(jù)域（Data）任意信息，任意長度（上層協(xié)議SDU有上限，比如標(biāo)準(zhǔn)的TCP/IP分組是576字節(jié)。減去分組中固定為40字節(jié)大小的地址信息及其它信息，最多還包含512字節(jié)的數(shù)據(jù)。）校驗和（Checksum）CRC校驗生成多項式：CRC-CCITT=x16+x12+x5+1HDLC的幀結(jié)構(gòu)（2）控制域（Control）HDLC的幀類型信息幀（Information）：完成信息傳送。監(jiān)控幀（Supervisory）：差錯控制和流量控制。無序號幀（Unnumbered）：鏈路控制管理。HDLC的幀類型信息幀（Information）：完成信息4.9因特網(wǎng)數(shù)據(jù)鏈路接入控制點到點通信的兩種主要情形：路由器到路由器通過modem撥號上網(wǎng)，連到路由器或接入服務(wù)器4.9因特網(wǎng)數(shù)據(jù)鏈路接入控制點到點通信的兩種主要情形：SLIP－串行線路網(wǎng)際協(xié)議SLIP——SerialLineIP1984年，RickAdams提出，RFC1055，發(fā)送原始IP包，用一個標(biāo)記字節(jié)（0xC0）來定界，采用字符填充技術(shù)；新版本提供TCP和IP頭壓縮技術(shù)，RFC1144存在的問題不提供差錯校驗只支持IPIP地址不能動態(tài)分配不提供身份認(rèn)證多種版本并存，互連困難SLIP－串行線路網(wǎng)際協(xié)議SLIP——SerialLiPPP點到點協(xié)議PPP——Point-to-PointProtocol面向字符的鏈路協(xié)議RFC1661，RFC1662，RFC1663與SLIP相比，PPP有很大的提高，提供差錯校驗、支持多種協(xié)議、允許動態(tài)分配IP地址、支持認(rèn)證等。以幀為單位發(fā)送，而不是原始IP包；鏈路控制協(xié)議LCP（LinkControlProtocol）可使用多種物理層服務(wù)：modem，SDH/SONET等網(wǎng)絡(luò)控制協(xié)議NCP（NetworkControlProtocol）可支持多種網(wǎng)絡(luò)層協(xié)議PPP點到點協(xié)議PPP——Point-to-Point標(biāo)記域：01111110，字符填充；地址域：11111111控制域：缺省值為00000011，表示無序號幀，缺省情況下，PPP不提供使用序號和確認(rèn)的可靠傳輸；但是在不可靠線路上，也可使用有序號的可靠傳輸。協(xié)議域：指示凈負(fù)荷中是何種包，比如IP，IPX等。缺省大小為2個字節(jié)。凈負(fù)荷域：變長，缺省為1500字節(jié)；校驗和域：2或4個字節(jié)PPP幀標(biāo)記域：01111110，字符填充；PPP幀PPP通信過程為了建立點對點鏈路通信，PPP鏈路的每一端，必須首先發(fā)送LCP包以便設(shè)定和測試數(shù)據(jù)鏈路。在鏈路建立之后，LCP可選設(shè)備才可以被認(rèn)證。然后，PPP必須發(fā)送NCP包以便選擇和設(shè)定一個或更多的網(wǎng)絡(luò)層協(xié)議。一旦每個被選擇的網(wǎng)絡(luò)層協(xié)議都被設(shè)定好了，來自每個網(wǎng)絡(luò)層協(xié)議的數(shù)據(jù)報就能在鏈路上發(fā)送了。鏈路將保持通信設(shè)定不變，直到外在的LCP和NCP關(guān)閉鏈路，或者是發(fā)生一些外部事件的時候（如休止?fàn)顟B(tài)的定時器期滿或者網(wǎng)絡(luò)管理員干涉）。PPP通信過程為了建立點對點鏈路通信，PPP鏈路的每一端，PPP工作狀態(tài)遷移PPP工作狀態(tài)遷移本章作業(yè)有人認(rèn)為：每一幀的結(jié)束處是一個標(biāo)志字節(jié)，而下一個幀的開始處又是另外一個標(biāo)志字節(jié)，這種方法非常浪費空間。用一個標(biāo)志字節(jié)就可以完成同樣的任務(wù)，這樣就可以節(jié)省一個字節(jié)。你同意這種觀點嗎？位串01110111110011111101需要在數(shù)據(jù)鏈路層上被發(fā)送，請問：經(jīng)過位填充后實際被發(fā)送出去的什么？奇偶檢驗的一個改進(jìn)是按n行、每行k位來傳輸數(shù)據(jù)，并且在每行和每列上