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

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

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

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

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

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

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

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

，WR=1WT≤2n-1

選擇性重傳WT

=WR

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