通信網(wǎng)絡基礎(chǔ)2-1

第二章端到端的傳輸協(xié)議通信與信息工程學院2024/10/31第2章端到端的傳輸協(xié)議本章將討論在物理層的比特管道上如何形成一條可靠的業(yè)務通道為上層提供可靠的服務。要解決的問題：如何標識高層送下來的數(shù)據(jù)塊（分組）的起止位置；如何發(fā)現(xiàn)傳輸中的比特錯誤；發(fā)現(xiàn)錯誤后，如何消除這些錯誤。2024/10/31第2章端到端的傳輸協(xié)議

2.1組幀技術(shù)2.2鏈路層的差錯控制技術(shù)

2.3標準數(shù)據(jù)鏈路控制協(xié)議及其初始化

2.4網(wǎng)絡層和運輸層的點對點傳輸協(xié)議2024/10/312.1組幀技術(shù)當數(shù)據(jù)鏈路層將網(wǎng)絡層的分組連續(xù)送到物理層進行傳輸時，有一個問題要解決，如何決定什么時刻是一幀開始？什么時刻是一幀結(jié)束？哪一段是差錯校驗的比特？這就是組幀技術(shù)需解決的問題。

1010101111001101101110100011100101010011011100010011101101101開始點？結(jié)束點？校驗比特？2024/10/312.1組幀技術(shù)面向字符的組幀技術(shù)面向比特的組幀技術(shù)采用長度計數(shù)的組幀技術(shù)2024/10/312.1.1面向字符的組幀技術(shù)(1)面向字符的組幀技術(shù)是指物理層傳輸?shù)幕締卧且粋€字符（通常用一個字節(jié)表示一個字符），并在此基礎(chǔ)上形成具有一定格式的字符串例如：RS-232C異步串行接口協(xié)議。該協(xié)議在傳送每個字符前后分別加上起始位D起、停止位D止，以便區(qū)分不同的字符。2024/10/312.1.1面向字符的組幀技術(shù)(2)Internet網(wǎng)中常用的面向字符的組幀技術(shù)的協(xié)有SLIP(SerialLineInternetProtocol)和PPP（PointtoPointProtocol）。2024/10/31SLIP協(xié)議（1）SLIP幀運載的是高層IP數(shù)據(jù)報。它采用兩個特殊字符；END（十六進制C0H，H表示十六進制）和ESC（十六進制DBH）。END用于表示一幀的開始和結(jié)束。C0C0IP數(shù)據(jù)報2024/10/31SLIP協(xié)議（2）為了防止IP數(shù)據(jù)報中出現(xiàn)相同的END字符而使收端錯誤地終止一幀的接收，SLIP中使用了轉(zhuǎn)義字符ESC。當IP數(shù)據(jù)報中出現(xiàn)END字符時，就轉(zhuǎn)換成ESC和ESC-END（其中ESC-END=DCH）兩個字符。當IP數(shù)據(jù)報中出現(xiàn)ESC時，就轉(zhuǎn)換成為ESC和ESC-ESC（其中ESC-ESC=DDH）兩個字符。C0DBC0DBDCDDC0DB11111111IP數(shù)據(jù)報2024/10/31SLIP協(xié)議（3）收端只要收到END字符即表示一幀的開始或結(jié)束。每當遇到ESC字符就進行字符轉(zhuǎn)換，恢復IP報文中的原有的END和ESC字符。這樣就可以完全以一個IP數(shù)據(jù)報的形式向IP層提交數(shù)據(jù)。2024/10/31PPP協(xié)議（1）PPP中，采用7EH作一幀的開始和結(jié)束標志（F）；其中地址域（A）和控制域（C）取固定值（A=FFH，C=03H）。IP數(shù)據(jù)報F7EAFFC03FCSF7E協(xié)議2024/10/31PPP協(xié)議（2）協(xié)議域（兩個字節(jié)）取0021H表示該幀運載的信息是IP數(shù)據(jù)報，取C021H表示該幀的信息是鏈路控制數(shù)據(jù)，取8021H表示該幀的信息是網(wǎng)絡控制數(shù)據(jù)；幀校驗域（FCS）也為兩個字節(jié)，它用于對信息域的校驗2024/10/31PPP協(xié)議（3）若信息域中出現(xiàn)7EH，則轉(zhuǎn)換為（7DH，5EH）兩個字符。當信息域出現(xiàn)7DH時，則轉(zhuǎn)換為（7DH，5DH）兩個字符。當信息流中出現(xiàn)ASCII碼的控制字符（即小于20H），即在該字符前加入一個7DH字符。2024/10/312.1.1面向字符的組幀技術(shù)(3)上述幀格式均支持數(shù)據(jù)的透明傳輸，這些幀結(jié)構(gòu)在處理時非常簡單，但缺點是效率較低，插入了許多轉(zhuǎn)義字符。另外，數(shù)據(jù)長度必須以字節(jié)為單位。2024/10/312.1.2面向比特的組幀技術(shù)(1)在面向比特的組幀技術(shù)中，通常采用一個特殊的比特串，稱為Flag,如0160（1j表示連續(xù)j個“1”）來表示一幀的正常結(jié)束和開始。與面向字符的組幀技術(shù)面臨相同的問題，即當信息比特流中出現(xiàn)與Flag相同的比特串（如連續(xù)出現(xiàn)6個“1”）如何處理？2024/10/312.1.2面向比特的組幀技術(shù)(2)這里采用的辦法是比特插入技術(shù)，發(fā)端信息流中，每出現(xiàn)連續(xù)的5個“1”就插入一個“0”。這樣被插“0”后的信息比特流中就不會有多于5個“1”的比特串。接收端在收到5個“1”以后，如果收到的是“0”就將該“0”刪去；如果是“1”就表示一幀結(jié)束。2024/10/312.1.2面向比特的組幀技術(shù)(3)采用比特插入技術(shù)，除了消除信息幀中出現(xiàn)Flag的作用以外，它還帶來其他作用，如要丟棄或中止一幀，則可連續(xù)發(fā)送7個或7個以上的“1”。當鏈路連續(xù)出現(xiàn)15個“1”則認為鏈路空閑。因此016是一個結(jié)束標志，如果016后面是0表示正常結(jié)束，如果016后面是1表示非常中止。2024/10/31幀的開銷(1)設輸入的信息比特流是獨立同分布的二進制變量，其“0”和“1”等概出現(xiàn)。假定采用01j作為結(jié)束標志，現(xiàn)在來求j為多少時效率最高或插入比特開銷最小。2024/10/31幀的開銷(2)首先考察在第i位要插入“0”的情況及相應概率。如果原始數(shù)據(jù)從i-(j-1)位到i位（i≥j）的比特為01j-1，則在第i位后面將要插入一個“0”，其概率為2-j。(它等效為出現(xiàn)01j-1序列的概率)XXXXXXXXXXXXXXXXXX011111

12 ii-(j-1)02024/10/31幀的開銷(3)如果原始數(shù)據(jù)從i-2(j-1)到i位（i≥2j-1）的比特為012(j-1)，則也將在第i位后面插入一個“0”，其概率為2-2j+1。XXXXXXXXXXXXX01111111111

12 ii-2(j-1)002024/10/31幀的開銷(4)可以繼續(xù)考察在第i位前連續(xù)出現(xiàn)n(j-1)個“1”的情況及相應的概率。在后面的討論中，將忽略第二次插“0”及更長連續(xù)“1”的插“0”情況。這里需要注意的是：如果輸入比特流的前j-1個比特均為“1”，則將要在第j位插入一個“0”，其概率為2-(j-1)。2024/10/31幀的開銷(5)設原始數(shù)據(jù)的長度為k,k≥j-1時的平均插入“0”的數(shù)目為1?2?(j?1)+[k?(j?1)]?2?j

=(k?j+3)2?j加上一個結(jié)束標志，總的開銷為OV=(k?j+3)2?j

+j+1對上式取均值，有E{OV}=(E{k}?j+3)2?j

+j+12024/10/31幀的開銷(7)通常E{k}>>j，所以上式可以用一個上界來表示(j>3)，即E{OV}≤E{k}2?j

+j+1上式右邊對應的最小j值為j=Int[log2{E{k}}]式中，Int[x]表示取x的整數(shù)部分。2024/10/31幀的開銷(7)2024/10/31幀的開銷(8)化簡得:E{OV}≤log2{E{k}}+2例如：E{k}=1000bit時，最佳的j=9，平均一幀的開銷小于12bit。而在標準的DLC協(xié)議，取j=6，平均一幀的開銷約為23bit。因此，從理論上講，應當改變現(xiàn)有標準DLC的幀標志位的長度。2024/10/312.1.3采用長度計數(shù)的組幀技術(shù)組幀技術(shù)的關(guān)鍵是正確地表示一幀何時結(jié)束除前面采用Flag和特殊字符外，還可以采用幀長度來指示一幀何時結(jié)束。2024/10/312.2鏈路層的差錯控制技術(shù)2.2.1差錯檢測2.2.2ARQ協(xié)議2.2.3最佳幀長2024/10/312.2.1差錯檢測鏈路層差錯檢測的目的是：如何有效地發(fā)現(xiàn)一幀數(shù)據(jù)比特經(jīng)過物理信道傳輸后是否正確。常用的檢錯方法奇偶校驗循環(huán)冗余校驗CRC（CyclicRedundancyCheck）檢錯的基本思路是發(fā)端按照給定的規(guī)則，在K個信息比特后面增加L個按照某種規(guī)則計算的校驗比特；在接收端對收到的信息比特重新計算L個校驗比特。比較接收到的校驗比較和本地重新計算的校驗比特，如果相同則認為傳輸無誤，否則認為傳輸有錯。2024/10/311.奇偶校驗碼例：信息序列長K=3，校驗序列長L=4。輸入信息比特為｛S1，S2，S3｝，校驗比特為｛C1，C2，C3，C4｝，校驗的規(guī)則為C1=S1⊕S3，C2=S1⊕S2⊕S3，C3=S1⊕S2，C4=S2⊕S32024/10/311.奇偶校驗碼例如：設發(fā)送的信息比特為{100}，經(jīng)過奇偶校驗碼生成的校驗序列為{1110}，則發(fā)送的信息序列為{1001110}。若經(jīng)過物理信道傳輸后，接收的序列為{1011110}，則本地根據(jù)收到的信息比特{101}計算出的校驗序列應為{0011}。顯然該序列與接收到的校驗序列{1110}不同，表明接收的信息序列有錯。2024/10/311.奇偶校驗碼如果L取1，即C=S1⊕S2⊕S3⊕…⊕SK為最簡單的單比特的奇偶校驗碼，它使得生成的碼字（信息比特+校驗比特）所含“1”的個數(shù)為偶數(shù)。該碼可以發(fā)現(xiàn)所有奇數(shù)個比特錯誤，但是不能發(fā)現(xiàn)任何偶數(shù)個錯誤。2024/10/31CRC校驗CRC（循環(huán)冗余校驗）是根據(jù)輸入比特序列(SK-1,SK-2,…,S1,S0)通過下列CRC算法產(chǎn)生L位的校驗比特序列(CL-1,CL-2,…,C1,C0)2024/10/31CRC校驗將輸入比特序列表示為下列多項式的系數(shù)：S(D)=SK-1DK-1+SK-2DK-2+…+S1D+S0式中：D可以看成為一個時延因子，Di對應比特Si所處的位置。例如：10101100，S(D)=D7+D5+D3+D22024/10/31CRC校驗(3)設CRC校驗比特的生成多項式為則校驗比特對應下列多項式的系數(shù)式中，Remainder[?]表示取余數(shù)。式中的除法與普通的多項式長除相同，其差別是系數(shù)是二進制，其運算以模2為基礎(chǔ)。2024/10/31CRC校驗（4）例如(D5+D3)/(D3+D2+1)的商為D2+D余數(shù)為D2+D最終形成的發(fā)送序列為2024/10/31CRC校驗（5）常用的幾個L階CRC生成多項式為：CRC-16（L=16）：CRC-CCITT（L=16）：CRC-32（L=32）：2024/10/31CRC校驗（6）例2.1：設輸入比特序列為（10110111），采用CRC-16生成多項式，求其校驗比特序列。解：輸入比特序列可表示為2024/10/31CRC校驗(7)由此式可得校驗比特序列為：（0000001110110010）。最終形成的經(jīng)過校驗后的發(fā)送序列為101101110000001110110010。2024/10/31CRC校驗(8)在接收端，將接收到的序列與生成多項式g(D)相除，并求其余數(shù)。如果則認為接收無誤。2024/10/31CRC校驗(9)注意：

有兩種情況：一是接收的序列正確無誤；二是有錯，但此時的錯誤使得接收序列等同于某一個可能的發(fā)送序列。后一種情況稱為漏檢。2024/10/312.2.2ARQ協(xié)議(1)前面解決了如何發(fā)現(xiàn)傳輸幀的錯誤問題，下面要解決當接收端發(fā)現(xiàn)傳輸幀有錯如何處理的方法。最簡單的處理方法是（收端）自動請求發(fā)端重發(fā)（ARQ，AutomaticRetransmissionRequest）。收端收到一幀后，經(jīng)過CRC檢驗，如果發(fā)現(xiàn)該幀傳輸有誤，則通過反饋信道（該信道可以與前向傳輸相同，也可以不同）以某種反饋規(guī)則通知發(fā)端重復上述過程，直到收端收到正確的幀為止。對反饋規(guī)則和重傳規(guī)則的設計，要保證整個自動重傳協(xié)議的正確性和有效性。2024/10/312.2.2ARQ協(xié)議(2)為了研究ARQ協(xié)議，我們對物理比特管道（物理鏈路）作如下假定：（1）在物理信道上傳輸?shù)膸竭_接收端前被時延了一個任意可變的時間；（2）幀在傳輸過程中可能會丟失，也可能出錯；（3）幀到達的順序與發(fā)送的順序相同。2024/10/312.2.2ARQ協(xié)議(3)有四種不同形式的ARQ重傳協(xié)議停等式ARQ返回n-ARQ選擇重發(fā)式ARQ并行等待式ARQ2024/10/311.停等式ARQ（1）停等式ARQ（Stop-and-WaitARQ）的基本思想是在開始下一幀傳送以前，必須確保當前幀已被正確接收。2024/10/311.停等式ARQ（1）假定A發(fā)，B收。具體的傳送過程如下：A發(fā)送一幀后，B如果接收正確，則B向A返回一個肯定的應答ACK；B如果接收錯誤，則B向A返回一個否定應答NAK。A必須在收到B的正確ACK后，方可發(fā)送下一幀。如果A發(fā)送一幀后（并給定時器設置一個初值），在一個規(guī)定的時間內(nèi)（定時器溢出），沒有收到對方的ACK，則重發(fā)該幀；如果收到了NAK，也要重發(fā)該幀。2024/10/311.停等式ARQ（2）由于A到B之間的雙向鏈路都可能出錯，上述協(xié)議能否正常工作？或者說如何保證該協(xié)議能夠正確工作呢？基本的方法是在傳輸?shù)膸性黾影l(fā)送序號（SN）和接收序號（RN）。接收序號RN通常用接收端希望接收的下一個發(fā)送幀的序號SN(也可以是下一幀的第一個字節(jié)的編號)2024/10/31無發(fā)送序號情況2024/10/31無接收序號情況2024/10/31假定A向B發(fā)送分組（A→B），節(jié)點A的發(fā)送算法如下：（1）置SN=0。（2）如果從高層接收到一個分組，則將SN指配給該分組；如果沒有高層分組，則等待。（3）將發(fā)送序號為SN的分組裝入物理幀中發(fā)送給接收節(jié)點B。（4）如果從B接收的RN>SN，則將SN加1，返回（2）。如果在規(guī)定的有限長時間內(nèi)，沒有從B接收到RN>SN的幀（應答），則返回（3）進行重傳。等待式ARQ協(xié)議的嚴格描述2024/10/31等待式ARQ協(xié)議的嚴格描述節(jié)點B的接收算法如下：（1）置RN=0。（2）無論何時從A正確接收一個SN=RN的幀，將該幀中的分組送給高層，并將RN加1。（3）在接收到該分組后的一個規(guī)定的有限長時間內(nèi)，將RN放入一幀的RN域中發(fā)給A。返回（2）。2024/10/31等待式ARQ協(xié)議性能評估算法（協(xié)議）的正確性算法（協(xié)議）的有效性2024/10/31等待式算法（協(xié)議）的正確性所謂算法的正確性是指算法始終能夠正常工作，正確接收輸入的數(shù)據(jù)和狀態(tài)，產(chǎn)生正確的動作和正確的輸出結(jié)果。對于不同的算法，其正確性有不同的描述。對于停等式ARQ協(xié)議而言，所謂“該算法是正確的”是指：A能夠始終不斷地從高層接收數(shù)據(jù)分組，B能夠始終按照發(fā)端的順序向B的高層呈送接收到的分組，既不重復，也不丟失。2024/10/31等待式算法的正確性證明算法的正確性證明可分為兩部分：一是穩(wěn)妥性（Safety），即算法決不會產(chǎn)生不正確的結(jié)果（在這里是指提交給上層分組的順序不對）；二是活動性（Liveness），即算法會永遠不停地產(chǎn)生結(jié)果（不會產(chǎn)生死循環(huán)，一旦進入死循環(huán)，將不會進行進一步的處理），在這里指在A節(jié)點能夠不停地接收高層的分組，在B節(jié)點能夠不停地將這些分組呈送給高層2024/10/31等待式ARQ協(xié)議穩(wěn)妥性證明在停等式ARQ中，穩(wěn)妥性是很明顯的。在算法開始時，SN=0，RN=0，節(jié)點B等待RN=0的幀，因而僅會有SN=0幀中的分組送上高層。由于RN是將要接收的下一個幀的序號，接收到一個新的幀后RN加1，這樣重發(fā)幀的序號小于RN，因而其中的分組不可能送給高層。所以，節(jié)點B能按順序?qū)⒎纸M呈現(xiàn)給高層。2024/10/31等待式ARQ算法活動性證明（1）為了考察該算法的活動性，假定A在t1時刻開始發(fā)送給定的分組i，B在t2時刻正確接收到該分組，A在t3時刻正確接收到B的應答。顯然，如果t2＝∞，則表示B收不到A的分組；如果t3＝∞，則表示A收不到B的應答。因而，要證明該算法的活動性就要證明2024/10/31等待式ARQ算法活動性證明（2）為了證明該協(xié)議的正確性，我們假定：①所有錯誤的分組都能被CRC檢出；②一個分組能夠被正確接收的概率為q，q>0。2024/10/31等待式ARQ算法活動性證明（3）令t時刻的RN和SN為RN(t)和SN(t)，顯然它們是時間t的非降函數(shù)。由于SN(t)是t時刻以前，從B接收到的最大請求序號，所以SN(t)≤RN(t)。由于分組i在t1時刻開始第一次傳輸（A在t1以前從未傳送過分組i），則根據(jù)穩(wěn)妥性（算法不會產(chǎn)生不正確的結(jié)果）有RN(t1)≤i，又因為SN(t1)＝i，所以有2024/10/31等待式ARQ算法活動性證明(4)又根據(jù)假定：在t=t2時，根據(jù)RN(t)的非降特性，有t1<t2。在t=t3時，利用RN(t)和SN(t)的非降特性和SN(t)≤RN(t)，則有t2<t32024/10/31等待式ARQ算法活動性證明(5)根據(jù)算法，A將會重復發(fā)送分組i，其重發(fā)的間隔是有限的。又由于分組被成功接收的概率q>0，因而分組i會在有限次傳輸后被正確接收。也就是說，從t1至t2的間隔是有限的。由于A不停地以有限長的間隔發(fā)送分組i，這將導致節(jié)點B以有限的間隔發(fā)送應答（包括RN的分組）。由于B成功傳輸?shù)母怕蕅>0，所以應答在有限的時間內(nèi)到達A，即t3是有限的。證畢。2024/10/31等待式ARQ算法在前面的討論中，假定SN和RN是隨時間任意增加的。這樣就需要很大的比特域來表示發(fā)送序號。但實際上是不需要的，可以采用一個整數(shù)的模值（modN）來表示，如SNmod8,SNmod128等。很容易看出對于停等式ARQ，取模2就足夠了。2024/10/31等待式ARQ算法有效性(1)算法的有效性可以從三個主要方面來表述：一是吞吐量（或通過量），二是鏈路的利用率，三是分組延遲。吞吐量是指在給定的物理信道和輸入分組流的條件下，接收端能夠呈送給高層的分組速率（分組/秒或比特/秒）。鏈路的利用率是指物理層（比特管道）的傳輸容量中用于有效分組傳輸所占的比例。在信道中，如果被等待、重傳和其它不必要的傳輸所占的比例越少，則信道利用率越高。分組延遲是指鏈路層從發(fā)端收到高層的分組開始到收端將該分組呈送給高層為止所需的時間。2024/10/31等待式ARQ算法有效性(2)設數(shù)據(jù)幀是固定幀長，其傳輸時間為TD秒，肯定和否定應答幀長為TACK秒，物理信道的傳播時延為Tp秒，則在忽略算法的處理時延的情況下，一幀的傳輸周期為假定任意一個數(shù)據(jù)幀平均需要發(fā)送NT次（一次初發(fā)，NT－1次重發(fā)）才能成功2024/10/31等待式ARQ算法有效性(2)則該幀平均一共需要NT個傳輸周期，物理鏈路的最大平均利用率為：（即物理鏈路以最大可能的負荷在傳輸時的平均利用率）令，忽略應答幀的傳輸時間（認為TACK＝0），則有2024/10/31等待式ARQ算法有效性(3)又假定數(shù)據(jù)幀的誤幀率為p=1-q，應答幀因長度很短從而其出錯的可能性可以忽略，即認為應答幀總是可以正確傳輸，則一個數(shù)據(jù)幀發(fā)送i次成功的概率為從而有鏈路的最大平均利用率2024/10/31等待式ARQ算法有效性(4)等待式ARQ的最大平均吞吐量為（分組/秒）等待式ARQ的平均分組延遲為：D＝組幀時延＋

≈組幀時延＋2024/10/31等待式ARQ算法有效性(5)組幀時延是指從高層分組的第一比特到達鏈路層開始，到鏈路層將該分組的所有比特收齊，經(jīng)過增加控制頭（如幀起止標志發(fā)送序號，接收序號等）和校驗比特（CRC）形成可傳輸?shù)臄?shù)據(jù)幀為止。它取決于網(wǎng)絡層與鏈路層之間的接口速率和方式，以及鏈路層的處理速度和方式。例如：若網(wǎng)絡層與鏈路層運行在相同的微處理器或計算機系統(tǒng)上，采用數(shù)據(jù)塊傳遞的方式來傳遞分組，則組幀時延可以相當小，且可以忽略。如果網(wǎng)絡層與鏈路層采用傳輸速率為R（比特/秒）的接口交換數(shù)據(jù)，則組幀的時延為K/R（這里K為分組的長度（比特數(shù)））。2024/10/31等待式ARQ算法有效性(6)2024/10/312.返回n-ARQ(1)返回n-ARQ(也稱為連續(xù)ARQ)的基本思路是：發(fā)端在沒有收到對方應答的情況下，可以連續(xù)發(fā)送n幀。收端僅接收正確且順序連續(xù)的幀，其應答中的RN表示RN以前的所有幀都已正確接收。（這里收端不需要每收到一個正確的幀就發(fā)出一個應答，可對接收到的正確順序的最大幀序號進行應答。）2024/10/312.返回n-ARQ(2)發(fā)送窗口寬度2024/10/312.返回n-ARQ(3)從圖中可以看出，如果收端能及時返回應答，則發(fā)端可連續(xù)不斷地全速連續(xù)發(fā)送幀。（如果我們減緩應答返回的速率，則可以控制發(fā)端發(fā)送幀的速率，從而達到速率控制的目的。）下面考察雙向都有數(shù)據(jù)傳輸并且?guī)L度不等長時，發(fā)送端窗口滑動的情況。2024/10/31傳輸錯誤對發(fā)送窗口的影響(n=4)盡管2，3，4號幀傳輸正確，但它們的序號與接收端期望的序號不符而不能被正確接收，因而仍需要重傳。2024/10/31反向幀長對發(fā)端窗口的影響0123413405134窗口[3,6][1,4][0,3][4,7]SN節(jié)點A節(jié)點BRN01234提交的分組2024/10/31反向幀出錯對發(fā)端的影響反向幀出錯可能對發(fā)端無影響，也可能對發(fā)端有影響。2024/10/312.返回n-ARQ算法描述返回n-ARQ算法的具體描述（假定A為發(fā)端、B為收端）設發(fā)端使用SNmin表示A目前沒有收到應答的幀中序號最小的幀（即發(fā)端窗口的低端），SNmax表示它將要指配給從高層新到達分組的幀序號。A節(jié)點將試圖傳送SNmin到SNmax－1之間的幀。2024/10/31返回n-ARQ算法的具體描述(2)發(fā)端（A節(jié)點）的算法：（1）置SNmin＝0，SNmax＝0（2）算法以任意順序重復執(zhí)行第（3）、（4）、（5）步。在每一步的條件滿足時刻到該步被執(zhí)行的時刻之間的時延是任意的，但是該時延是一個有限的值。（3）如果SNmax<SNmin+n，且上層有一個新分組到達，將SNmax指定給承載該分組的幀，并將SNmax加1。(繼續(xù)發(fā)送)（4）如果接收的RN>SNmin，則置SNmin=RN。（窗口右移）（5）如果SNmin<SNmax，且當前沒有幀在傳輸，從[SNmin，SNmax）中選擇一個或一組幀進行傳輸。當SNmin不再改變時，SNmin幀的重傳間隔應當小于一個規(guī)定的有限值。2024/10/31返回n-ARQ算法的具體描述(3)收端（B節(jié)點）的算法：（1）置RN=0，重復執(zhí)行（2）和（3）。（2）當接收到的SN=RN，將分組呈送給高層以，并將RN加1。（3）在接收到A的任何一個正確幀后，在一個有限的時間內(nèi)，將收端的RN發(fā)給A。2024/10/312.返回n-ARQ上述算法實際上是一個框架，它是指一類算法，其定時、操作順序可以根據(jù)需要來安排。例如，可以在發(fā)送完SNmin→SNmax-1的幀后，立即返回再次發(fā)送SNmin→SNmax-1的幀，而不是等到應答定時器超時后再重發(fā)。2024/10/312.返回n-ARQ返回n-ARQ的序號也可以用模為m(m>n)的整數(shù)來表示。例如，取模8則可用3比特來表示序號，此時最大的窗口取值只能為7。如果n=m，則系統(tǒng)無法正常工作。其原因如下：假設，發(fā)端發(fā)送8幀后，收到了對方的所有確認，則將發(fā)送新的8幀，其序號為0~7。如果發(fā)端發(fā)送8幀后，收端發(fā)送的應答未能到達發(fā)端，發(fā)端將重發(fā)這8幀，其序號仍為0~7。由于這兩種情況對收端而言是無法區(qū)分的，因而在接收到第二次序號為0~7的幀時，收端無法區(qū)分是新的幀還是重發(fā)的幀。2024/10/312.返回n-ARQ影響返回n－ARQ協(xié)議效率的原因反向幀長過長要求增加n反向應答出錯要求增加n正向傳輸出錯(n增加將導致重傳的內(nèi)容加大)加快出錯的反饋速度。即收端一旦接收到一個錯誤幀，立即返回一個短的應答幀（監(jiān)控幀），使發(fā)端盡快返回重發(fā)。2024/10/31返回n-ARQ的效率(1)假定數(shù)據(jù)幀長是一個固定值，且假定應答幀傳輸時間很小可以忽略。返回n-ARQ的效率與鏈路的傳輸時延(TP)，幀長(TD)，窗口n等參數(shù)緊密相關(guān)。令d=TD+2TP2024/10/31返回n-ARQ的效率(2)當nTD>d時，應答幀可以及時返回，在傳輸幀無差錯的情況下，鏈路的最大平均利用率為1。發(fā)端可連續(xù)不斷地向鏈路上發(fā)送幀。當nTD<d時，鏈路的最大平均利用率為nTD/d。即在d=TD+2TP時間內(nèi)，發(fā)端至多可以發(fā)送n個分組2024/10/31返回n-ARQ的效率(3)設傳輸過程中的誤幀率為p，每出現(xiàn)一個錯幀，發(fā)端就會重復n幀。若一幀經(jīng)過i次傳輸成功，則表明經(jīng)過了（i-1）次返回后該幀才傳輸成功，而每次返回需要傳輸n幀，因而總的所需傳輸?shù)膸瑪?shù)為1+(i-1)n，其出錯的概率為pi-1(1-p)。由此可得：成功傳輸一幀平均所需傳輸?shù)膸瑪?shù)為：

(2-19)2024/10/31返回n-ARQ的效率(4)利用該式可得返回n-ARQ方式中鏈路最大平均利用率為：

(2-20)式中的α=TP/TD為一幀的傳輸時延/幀長2024/10/31返回n-ARQ的效率(5)代入式（2-19）得從圖中可以看出，鏈路利用率與相對傳輸時延、窗口n的大小緊密相關(guān)。當相對傳輸時延相對較大（如在衛(wèi)星鏈路中）時，為了達到較高的鏈路利用率，應選擇較大的n。從圖中可以看出，當n=|(1+2α)|，（|x\表示取大于等于x的最小整數(shù)）時，鏈路利用率最高。也就是最佳的窗口寬度（nTD）近似等于一幀的傳輸時間+2倍的傳播時延。2024/10/31選擇重發(fā)式ARQ(1)選擇重發(fā)式ARQ（SelectiveRepeatARQ）是對返回n-ARQ的改進。在返回n-ARQ中，如果前向傳輸?shù)哪骋粋€幀出錯，則在收到對方的否定應答后，該幀及其后續(xù)的幀都要重傳，而不管這些后續(xù)是否傳輸正確。選擇重發(fā)式ARQ的思路與返回n-ARQ相同，其窗口仍為n，但僅僅重發(fā)有錯的幀。2024/10/31選擇重發(fā)式ARQ(2)為了實現(xiàn)選擇有錯幀進行重發(fā)的目的，這就要求接收節(jié)點具有對分組排序的能力（因為這時接收到的分組是亂序的），并且在應答時除了應答RN以外，還要包括大于RN的哪些幀已被正確接收的信息。接收節(jié)點可以用RN+k個比特（每個比特的位置的取值對應于RN后面第n個幀的接收狀態(tài)是ACK或NAK）來進行應答。2024/10/31選擇重發(fā)式ARQ(3)選擇重發(fā)式ARQ的鏈路利用率同樣可用和返回n－ARQ同樣的方式來表示，但這里重傳的幀僅為出錯的幀，即從而可得選擇重發(fā)式ARQ的鏈路利用率為：2024/10/31選擇重發(fā)式ARQ(4)當RN和SN采用模m來表示時，要求m≥2n；否則，如果取m>n，會引起接收數(shù)據(jù)的序號混淆。2024/10/314.ARPANETARQ(1)ARPANETARQ采用了8個并行等待式ARQ，每一個等待式ARQ對應一個虛似信道。輸入分組可以任意分配到空閑的虛擬信道A-H上。如果所有虛信道忙，分組將在DLC層外等待。2024/10/314.ARPANETARQ(2)處于忙狀態(tài)的虛擬信道上的分組被復接到物理比特管道上傳輸?？梢圆捎幂喸兊姆椒▉硌h(huán)查詢各個虛擬信道，當輪詢到某一忙信道時，如果應答還沒有收到，則將該虛擬信道的分組再次發(fā)送到物理信道上。因此，該復接方式就不需要設置定時器來計算等待應答的時間。2024/10/314.ARPANETARQ(3)2024/10/314.ARPANETARQ(4)使用該協(xié)議的一個問題：DLC層不負責排序，因而高層應當具有分組排序功能2024/10/312.2.3最佳幀長2024/10/312.2.3最佳幀長(1)從兩個方面來考察最佳幀長：一個方面是在一條鏈路上使傳輸效率最高的最佳幀長。另一個方面是在多條鏈路構(gòu)成的傳輸路徑上，使得傳輸效率最高的最佳幀長。2024/10/312.2.3最佳幀長(2)在實際傳輸過程中，每一幀數(shù)據(jù)通常包括數(shù)據(jù)負荷和控制信息。如果幀長較短，控制比特所占用的比例較大，因而鏈路利用率下降。如果幀長較長，在數(shù)據(jù)幀傳輸過程中，因信道誤碼的存在而導致幀傳輸錯誤的概率較大，重傳的次數(shù)將增大，這也會導致鏈路利用率的下降。因此存在一個最佳幀長，使鏈路利用率最高。2024/10/312.2.3最佳幀長(3)數(shù)據(jù)負荷的長度為ld比特控制信息的長度為lh比特總的數(shù)據(jù)長度為lf比特(lf=ld+lh)鏈路的誤比特率為pb(信道錯誤為隨機錯誤)數(shù)據(jù)幀的差錯率或誤幀率p為當Pb很小時，上式可近似為2024/10/312.2.3最佳幀長(4)以等待式ARQ為例，可得鏈路的有效利用率為式中Tb為比特寬度，將代入并經(jīng)整理得：2024/10/312.2.3最佳幀長(5)將上式對ld求導，并令其為零，可得最佳數(shù)據(jù)幀長度為例如，當2024/10/312.2.3最佳幀長(6)下面，我們將討論在分組經(jīng)過多次中轉(zhuǎn)才能到達目的節(jié)點時，能使得網(wǎng)絡開銷最小和時延最小情況下的最佳幀長。一條消息分成不同長度的分組經(jīng)過中轉(zhuǎn)到達目的節(jié)點的過程如右圖。2024/10/312.2.3最佳幀長(7)從降低時延的角度，分組的長度應盡可能小。分組長度較小會帶來什么問題？設消息的長度為M，分組的長度為K，通常每一幀都包含固定的開銷V（含頭和尾），這樣每一條消息要分成Int[M/K]+分組，Int[x]+表示大于或等于x的最小整數(shù)。在消息的傳輸過程中，前Int[M/K]個分組均有K個比特，而最后一個分組的比特數(shù)在1到K之間。一條消息要傳輸?shù)目偙忍財?shù)為M+Int[M/K]+×V。2024/10/312.2.3最佳幀長(8)2024/10/312.2.3最佳幀長(9)幀長K減小，會導致幀數(shù)增加，這會引起傳輸開銷增加和網(wǎng)絡處理負荷增加，因此應當增加幀長。在M→∞時，開銷所占的比例為V/(V+K)。因此，增加幀長會降低開銷。綜合考慮時延和開銷兩個方面，就存在一個最佳幀長。2024/10/312.2.3最佳幀長(10)設每條鏈路的容量為C（b/s），將一條消息經(jīng)過中繼傳到目的節(jié)點的總時間為T，在忽略各節(jié)點的處理和緩存時延的情況下有：T=消息在最后一條鏈路上的傳輸時間+(j-1)條鏈路引起的時延對M求均值得2024/10/312.2.3最佳幀長(11)2024/10/312.2.3最佳幀長(12)用代入上式，并使得上式最小的最佳幀長為:2024/10/312.2.3最佳幀長(13)在上面的討論中，我們未討論打包的時延，即只關(guān)心消息進入系統(tǒng)后到達目的節(jié)點的時延。而對于某些流型業(yè)務（如語音），將要關(guān)心給定的某一個比特進入網(wǎng)絡到該比特離開網(wǎng)絡的時延，這時就必須考慮打包的時延。2024/10/312.2.3最佳幀長(14)設輸入的比特速率為R，分組長度為K，收發(fā)之間各鏈路的容量分別為C1，C2，…（均大于R），分組的開銷為V個比特，則一個比特的時延為T=打包時延+各鏈路的傳輸時延2024/10/312.2.3最佳幀長(15)從上式可以看出，當鏈路速率提高后，T主要由K/R決定。例如：對于64kb/s的數(shù)字語音，通常要求打包時延小于10ms，因此K通常取500比特或更小。2024/10/312.2.3最佳幀長(16)上面都是從單個用戶的角度來討論網(wǎng)絡處于輕負荷狀態(tài)下，最佳幀長如何選取的問題。但是對于網(wǎng)絡而言，各個用戶的最佳長度各不相同。這就會出現(xiàn)當不同長度的分組在一條鏈路上傳輸時，長度很長的分組傳輸時延很大，從而阻礙了短分組的快速傳遞。這就像一條單行線上，一輛慢速行駛的貨車，阻塞了后面小車的快速行駛。這種現(xiàn)象稱為“slowtrunkeffect”（慢速貨車效應）。因此，最佳的幀長度應當由網(wǎng)絡來設定，而不是由各終端自行設計。2024/10/312.3標準數(shù)據(jù)鏈路控制協(xié)議及其初始化2.3.1標準的數(shù)據(jù)鏈路控制協(xié)議2.3.2數(shù)據(jù)鏈路層協(xié)議的初始化2024/10/312.3.1標準的數(shù)據(jù)鏈路控制協(xié)議目前常用的標準數(shù)據(jù)鏈路控制（DLC）協(xié)議有：IBM提出的SDLCISO建議的HDLCANSI規(guī)定的ADCCPCCITT建議的LAPB其中，HDLC與ADCCP功能相同，SDLC是HDLC的一個功能子集。LAPB也是HDLC的一個子集。HDLC（ADCCP）是為多種物理鏈路設計的。這些鏈路包括多址鏈路、點對點鏈路、全雙工和半雙工鏈路。2024/10/31鏈路的工作方式通信雙方鏈路的工作方式通常分為三類：全雙工、半雙工和單工方式。單工方式指通信雙方僅有單向數(shù)據(jù)流動，一方為發(fā)端，另一方為收端，鏈路上僅為一條單向物理信道；全雙工是指通信雙方可以同時向?qū)Ψ桨l(fā)送和接收對方的數(shù)據(jù)流，鏈路上同時有兩條不同流向的物理信道；半雙工通信指通信雙方可以向?qū)Ψ桨l(fā)送或從對方接收數(shù)據(jù)流，但不可以同時收發(fā)，任一方在發(fā)送時不能接收，在接收時不能發(fā)送。2024/10/312.3.1標準的數(shù)據(jù)鏈路控制協(xié)議HDLC包括三種工作模式：正常響應模式（NRM）用于主從式鏈路。即鏈路的一端是主站（節(jié)點），另一端是從站。主站負責控制和協(xié)調(diào)雙方的通信過程。典型的應用場合是一個計算機與多個外設之間的鏈路。采用輪詢（Polling）機制，實現(xiàn)主站與從站之間的通信。異步響應模式（ARM）也是采用主從模式，但對從站沒有嚴格的限制，該方式未被廣泛使用，后面將不再討論它。異步平衡模式（ABM）用于全雙工點對點的鏈路，鏈路兩端的節(jié)點具有相同的責任進行鏈路控制。這是應用最廣泛的協(xié)議之一。LAPB使用ABM，SDLC使用NRM和ARM模式。2024/10/31標準DLC的幀結(jié)構(gòu)(1)上面幾種協(xié)議都使用該幀結(jié)構(gòu)。Flag：011111102024/10/31標準DLC的幀結(jié)構(gòu)(2)地址域在常用情況下為一個字節(jié)（8比特），它用于多用戶共享一條鏈路時區(qū)分不同的節(jié)點。在不同的工作方式下，地址域的功能可以不同。例如：在NRM方式中，地址域總是從站的地址。當用于點對點通信時，地址域沒有作用。2024/10/31標準DLC的幀結(jié)構(gòu)(3)控制域用來區(qū)分不同的幀類型。它有三種格式：信息幀（Ⅰ）、監(jiān)控制（S）和無編號幀（U）2024/10/31標準DLC的幀結(jié)構(gòu)(4)信息幀(I)采用模8的返回n-ARQ方式進行傳輸，它對應的控制包括SN和RN。監(jiān)控幀(S)用于在無數(shù)據(jù)傳輸時返回ARQ的信息（如：RN）或加速返回ACK和NAK信息。無編號幀(U)用于鏈路的建立和終止以及附加信息的傳輸。2024/10/31標準DLC的幀結(jié)構(gòu)(5)控制信息種類的區(qū)分是靠控制域的第1和2比特來區(qū)分的。第1比特為0表示為信息幀，第1和2比特為“10”表示監(jiān)控幀，第1和2比特為“11”表示為無編號幀?？刂朴蛑械牡?個比特為查詢/結(jié)束（P/F）比特，在查詢時稱為P比特，在響應時稱為F比特2024/10/31標準DLC的幀結(jié)構(gòu)(6)在不同的工作模式中，P/F比特的用法不同。例如：在NRM模式中，主站查詢從站時，置P=1。從站響應如果有多個幀，則應將最后一個響應幀F(xiàn)置1，其余各響應幀置F=0。在ABM方式中，任一站均可主動發(fā)送S和I幀，此時將P置1，對方收到P=1的幀后，將F置1進行應答。2024/10/31標準DLC的幀結(jié)構(gòu)(7)監(jiān)控幀（S）有四種類型：RR－接收準備好RNR－接收未準備好REJ－拒絕SREJ－選擇拒絕它們通過控制域中的第3和4個比特來區(qū)分?！?0”對應RR，“10”對應RNR，“01”對應REJ，“11”對應SREJ。2024/10/31標準DLC的幀結(jié)構(gòu)(8)RR是正常的響應幀，它用于反向沒有數(shù)據(jù)幀時，攜帶RN對發(fā)端進行應答。RNR是用于收端暫不能接收更多幀（緩沖區(qū)滿）時給對方的提示，RNR中也包括RN。REJ用于剛接收的幀出錯或者幀的序號與期望的序號不符時，給發(fā)端的應答。發(fā)端將重發(fā)序號為RN及其后面的分組，同時表明RN以前的分組已正確接收。REJ可以改善返回n-ARQ的效率。SREJ是一種簡單的選擇重發(fā)方式，它要求發(fā)端重發(fā)序號為RN的分組。2024/10/31標準DLC的幀結(jié)構(gòu)(9)無編號幀（U）用于鏈路的建立、拆除和特殊控制。無編號幀是采用第3，4，6，7，8個比特來區(qū)分不同類型的。目前，只定義了15種無編號幀。無編號幀可用于設置工作模式，如置正常響應模式SNRM（SetNRM），置異步平衡模