1、信息網絡理論基礎NANJING UNIVERSITY of Science & Technology第2章 點到點傳輸協議鏈路層的差錯控制技術組幀技術數據鏈路控制協議及其初始化網絡層和傳輸層的點對點傳輸協議信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.1 鏈路層的差錯控制技術差錯檢測（奇偶校驗碼、CRC校驗） ARQ協議（等待式ARQ、返回式n-ARQ、選擇重傳式ARQ、ARPANET并行ARQ）一段鏈路達到的最佳效率、所獲得的最佳幀長度信息網絡理論基礎NANJING UNIVERSITY of Science & Technology

2、2.1.1 差錯檢測目的：發現一個傳輸幀經過物理信道傳輸后是否正確。常用的方法：一類是奇偶校驗、另一類是CRC循環冗余碼校驗。基本思路：發端按照給定的規則在K個信息比特后面增加L個校驗比特；接收端對收到的信息比特重新計算L個校驗比特，比較接收到的校驗比特和本地重新計算的校驗比特，如果相同，則認為傳輸無誤，否則，認為傳輸出錯。 1. 奇偶校驗碼 奇偶校驗的種類很多，這里給出K=3，L=4，即輸入信息比特為S1，S2，S3校驗比特為C1，C2，C3，C4校驗的規則如下表：信息網絡理論基礎NANJING UNIVERSITY of Science & Technology如果L=1，123kCSSS

3、S（偶校驗）即為最簡單的單比特奇偶校驗碼，可發現奇數個比特錯，但不能發現偶數個比特錯。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 2. CRC校驗1DDDDDD DDDDDDDDg(D) 32)32(L-CRC1DDDg(D) 16)CCITT(L-CRC1DDDg(D) 16)16(L-CRCg(D)CRCLCDCDCDCg(D)S(D)DRemainderC(D)LCCC(CSDSDSDSS(D)K SSS SCRC2457810111216222326325121621516012- l2- l1 - l1 - lL012- l1

4、 - l012-k2-k1 -k1 -k012-k1 -k 的階常用個比特校驗序列），校驗比特數：表示為下列多項式的系個比特信息序列，），校驗將輸入比特（信息網絡理論基礎NANJING UNIVERSITY of Science & Technology CRC碼能檢測所有奇數個錯誤。 當信息比特（K）的長度小于等于2L-1，CRC檢測所有的兩個錯誤。 CRC碼可以檢測長度為L的突發錯，碼字最小距離為4。 CRC的漏檢概率為2-L信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.1.2 ARQ協議重傳（自動請求發端重發）對于一個重傳協議，要

5、從兩個方面對其進行評價：一是正確性，二是有效性。正確性：鏈路層（DLC）能從接收到的幀中，成功地向網絡層輸送每一個分組，并且每個分組僅送一次。有效性（效率）：物理層的比特管道的多少容量被用于必要的傳輸。被等待和不必要的重傳所浪費的容量越少，效率越高。對物理比特管道作如下的假定： （1）在物理信道上傳輸的幀到達接收端前被時延了任意可變的時間 （2）幀在傳輸過程中可能會丟失，也可能出錯 （3）幀到達的順序與發送的順序相同信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 1. 等待式ARQ（Stop-and-Wait ARQ）Stop-and-Wa

6、it ARQ的基本思想與定時器的設置（溢出）在ARQ幀中，必須有RN和SN（接收序號和發送序號）假定A向B發送分組，節點A的發送算法如下： （1）置SN=0 （2）如果從上層接收到一個分組，則將SN指配個該分組，如果沒有上層分組則等待 （3）將第SN個分組裝入物理幀中發給接收節點B （4）如果從B接收的RNSN，則將SN加1，返回（2）；如果在規定的有限時間內，沒有從B接收到RNSN的幀，則返回（3）。信息網絡理論基礎NANJING UNIVERSITY of Science & TechnologyARQ幀結構等待式ARQ的工作過程信息網絡理論基礎NANJING UNIVERSITY of

7、Science & Technology節點B的接收算法： （1）置RN0 （2）無論何時從A接收到一個SN=RN的分組，將該分組送給上層，并將AN+1 （3）在接收到該分組后的一個規定的有限長時間內，將RN放入一幀的RN域中，發給A，返回（2）穩妥性：節點B能按照順序將分組呈現給高層活動性：不會死循環假定SN和RN是隨時間任意增加的，這樣就需要很大的比特域來表示發送序號，但實際上是不需要的，可以采用一個整數的模值（mod N）來表示，如SN mod 8，SN mod 128，也很容易看出，停等式 ARQ SN mod 2就足夠了。信息網絡理論基礎NANJING UNIVERSITY of S

8、cience & Technology 2. 返回式nARQ由于等待式ARQ的效率很低，想要發端在等待對方應答時，應當做更多的事情，提出三種改進方案：返回式nARQ（Go Back n ARQ），選擇重復式ARQ（Selective Repeat ARQ），和并行等待式ARQ（ARPANET ARQ）。 返回式nARQ的基本思路：發端沒有收到對方應答的情況下，可以連續發送n個分組，收端僅接收正確順序的分組，其應答中的RN表示RN以前的所有分組都已正確接收。這里的n是一個重要的參數，叫做滑動窗口寬度。返回nARQ算法的具體描述如下：設發端使用SNmin表示A目前沒有收到應答的分組中序號最小的分組

9、（即發端窗口的低端），SNmax表示它將要從高層接收的分組序號，節點將試圖傳送SNmin到SNmax1之間的分組。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology信息網絡理論基礎NANJING UNIVERSITY of Science & Technology在序號取m（mod m）的情況下，返回nARQ 的算法如下：發端（A節點）的算法： （1）置模m的變量SNmin和SNmax等于0 （2）算法從任意順序重復執行第（3）、（4）、（5）步，但在每步的條件滿足時刻到該步被執行的時刻之間的時延是任意的，但該時延是一個有限的值 （3）如果（S

10、NmaxSNmin）mod mn，且上層有個分組到達，則將SNmax指定給該分組，并將SNmax增加至（SNmax+1）mod m （4）如果SNmin不等于SNmax，且當前沒有幀在傳輸，選擇一個滿足（SNSNmin）mod mn，會引起接收數據序號的混淆。 4. ARPANET ARQ采用8個并行等待式ARQ，每一個等待式ARQ對應一個虛擬信道，8個虛擬信道分別為AH，輸入分組可以任意分配到空閑的虛擬信道AH上。信息網絡理論基礎NANJING UNIVERSITY of Science & TechnologyARPANET ARQ信息網絡理論基礎NANJING UNIVERSITY of

11、 Science & Technology2.2 組幀技術面向字符的組幀技術面向比特的組幀技術最佳幀長度信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.2.1 面向字符的組幀技術傳輸的基本單元是一個字符（字節），他們都支持數據的透明傳輸，這些幀結構在處理時非常簡單，但缺點是效率較低，插入了許多轉換字符，另外數據的長度必須以字節為單位（n整數倍Byte）SLIP協議的幀格式信息網絡理論基礎NANJING UNIVERSITY of Science & TechnologyPPP的幀格式用于ARPANET的幀格式信息網絡理論基礎NANJING

12、 UNIVERSITY of Science & Technology 2.2.2 面向比特的組幀技術通常采用一個特殊的比特稱為Flag，如0160（1j表示連續j個“1”）來表示一幀的正常結束，如何解決比特流中連續出現6個“1”，即“0”比特插入技術。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.2.3 采用長度計數的組幀技術DECNET采用了此方案組幀技術的關鍵是正確的表示一幀的何時結束，這里采用了幀長度來指示一幀何時結束，如果最大長度為Kmax，則長度域的比特數至少為：Intlb Kmax + 1其中 lb = Log2長度分組數

13、據信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.2.4 最佳幀長度n在2.1.3 中討論的是為了實現最佳的信道效率，在ARQ協議中使用的最佳幀長度ldopt；下面要討論的是在分組經過多次中轉才能到達目的節點時，能使得網絡開銷最小和時延最小情況下的最佳幀長。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology網絡開銷與時延最小情況下的最佳幀長n一條消息分成不同長度的分組經過中轉到達目的節點的過程如圖，可以看出，圖（b）中分組的傳輸時延為2倍的分組長度，在圖（c）中我們將分組的長度減少一半，則

14、此時的時延僅為原來分組長度的1.5倍。信息網絡理論基礎NANJING UNIVERSITY of Science & Technologyn設消息的長度為M，分組的長度為K，通常每一幀都包含固定的開銷V（含頭和尾），這樣每一條消息要分成 分組， 表示大于或等于x的最小整數。KMInt xIntVKMIntMKKKMInt特數為一條消息要傳輸的總比之間，到數在而最后一個分組的比特個比特，個分組均有在傳輸過程中，前1n從降低時延的角度出發，分組應盡可能地小，而幀長K的減小會導致幀數的增加，會引起傳輸開銷增加和網絡處理負荷的增加，因此應當增加幀長以降低開銷，綜合考慮時延和開銷兩個方面，存在一個最佳幀

15、長。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 0 121) 1)(1)(1(1dKTdEjVMEKKMEKMIntEVKMIntEMEjVKCTEMCVKjVKMIntMTjTTbpsCopt令：最小的最佳幀長為代入上式，并使得上式用求平均值，得對）條鏈路引起的時延（的傳輸時間消息在最后一條鏈路上：和緩存時延的情況下有，在忽略各節點的處理的總時間為繼傳到目的節點），將一條消息經過中（設每條鏈路的容量為信息網絡理論基礎NANJING UNIVERSITY of Science & Technologyn在以上的討論中，未討論打包的時延，

16、只關心消息進入系統后到達目的節點的時延，而對于某些流型業務，將要關心給定的某一個比特進入網絡到該比特離開網絡的時延，這時必須考慮打包的時延。iiCVKRKTVRCCKR .21各鏈路的傳輸時延打包的時延時延為個比特，則一個比特的）分組的開銷為（均大于，為：，收發之間各鏈路容量，分組長度為設輸入的比特速率為n可以看出，當鏈路速率Ci提高后，T主要由K/R決定。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.3 數據鏈路控制協議及其初始化標準的數據鏈路控制協議數據鏈路層協議的初始化信息網絡理論基礎NANJING UNIVERSITY of S

17、cience & Technology2.3.1 標準的數據鏈路層協議IBM提出的SDLCISO建議的HDLCANSI規定的ADCCPCCITT（ITU-T）建議的LAPB其中HDLC與ADCCP功能相同，SDLC是HDLC的功能子集，LAPB是X.25網的DLC協議，也是HDLC的一個子集。HDLC（ADCCP）是多種鏈路設計的：多址鏈路、點對點鏈路、全雙工和半雙工鏈路，它包含有三種模式：NRM，ARM，ABM信息網絡理論基礎NANJING UNIVERSITY of Science & Technology標準DLC的幀結構，控制域的格式與DLC的工作過程，為了簡化描述，采用以下命令格式：

18、X（Y）Z其中X表示地址，Y表示信息幀的SN和RN，或監控幀的類型及參數，或無編號幀的類型，Z表示P/F是否置位。信息網絡理論基礎NANJING UNIVERSITY of Science & TechnologyNRM、ABM的工作過程：信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.3.2 數據鏈路層協議的初始化鏈路正常工作時稱為UP狀態；鏈路故障時稱為DOWN狀態，當鏈路出現故障一段時間后，為保證端到端的可靠傳輸，網絡層和傳輸層通常采取一定的措施，另選一條新的鏈路來傳輸舊鏈路上未傳輸的分組，當舊鏈路恢復工作以后，高層會在該鏈路中建立

19、一條新的通路來傳輸新的分組流，因此在一條鏈路上會出現UP和DOWN交替的情況。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 1. 主從模式下鏈路的初始化，并在HDLC中SNRM對應于上述協議中的INIT，DISC幀對應于上述的DISC，ACK對應于上述的ACKI和ACKD 信息網絡理論基礎NANJING UNIVERSITY of Science & TechnologyHDLC的初始化、數據傳輸及出現的問題信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 2. 平衡模式中，通信雙方是平

20、等的，即A站發送數據時，A是主站，B是從站；當B站發送數據時，B是主站，A是從站，因而相當于兩個主從協議在工作。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.4 網絡層和傳輸層 的點對點傳輸協議網絡層的點對點傳輸協議網際層（互連層）的傳輸協議IP協議傳輸層的點對點傳輸協議信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.4.1 網絡層的點對點傳輸協議 1. 會話過程（Session）和分組編號不同的會話過程會共享同一鏈路同一個Session中的分組進行標識編號分組的編號可以采用K個b

21、it，表示一個分組中所含的比特數、字符數或字數（多個字節）組成，采用mod 2K的方式對分組進行循環編號信息網絡理論基礎NANJING UNIVERSITY of Science & Technology虛電路中不同會話過程的標識方法信息網絡理論基礎NANJING UNIVERSITY of Science & Technology 2. 網絡層的差錯控制與DLC的差錯控制方式類似，采用ARQ方式，但是有所區別： 使用位置不同 分組編號的方式不同 傳輸順序的差別 時延不同采用mod m 的編號方式，則序號為l mod m和（l+m）mod m 的分組在接收端是無法區分的，特別在數據報方式中，任

22、意的時延造成重發拷貝是多余的，因為前一個拷貝潛伏在網絡中；在發（l+m）mod m時，有可能l mod m的分組的拷貝先于（l+m）mod m到達，導致接收節點出現不可糾正的錯誤，盡管可能性會很小。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology解決的方法：（1）網絡層最好采用虛電路方式；（2）分組的編號的模值應足夠大；（3）給每個分組規定一個最大的生存時間，在該區間內，使得分組的序號在使用mod m時不可能出現一個循環。在TCP協議中，使用（2）、（3）兩種方法。信息網絡理論基礎NANJING UNIVERSITY of Science &

23、 Technology 3. 網絡層的流量控制這里討論如何用于網絡層流量控制，當網絡發生擁塞或傳輸時延增加，則應答將被時延，將信源的發送速率降低，稱之為端到端的流量控制，因此，目的節點如想減緩接收分組的速率，則可以將含有RN的應答分組適當延遲即可。 采用應答延時來減少擁塞，但是發端無法區分下列三種情況： 如果傳輸出錯而導致未到達發端，發端會在超時后重發對應分組。 如果應答因網絡擁塞而被延時。則發端會在超時后重發，加重網絡的擁塞。 如果因為目的節點處在過載狀態而導致應答被推遲發送，則發端也會在超時后重發，加重網絡的擁塞。信息網絡理論基礎NANJING UNIVERSITY of Science

24、& Technology解決上述問題的方法是將應答和流控的功能適當分開，兩個思路：思路一：不減緩應答，而使發端減緩發送速度。思路二：采用許可機制，目的節點向原節點發送兩個反饋信息，RN+Permit（j），其中，RN是常規應答，許可證（Permit）使得允許原節點發送的分組序號為RN+j+1，實際上改變了窗口的大小。 4. X.25網絡標準 X.25標準是由ITU-T制定的外部設備（DTE）之間的接口標準，其物理層為X.21，DLC層為LAPB，X.25網絡層標準有時也稱為分組層標準。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.4.2

25、 網際層（互連層）的傳輸協議IP協議網絡的互連需解決的問題：包含有尋址方式、最大分組長度、網絡與用戶接入機制、控制與狀態報告方式、路由選擇技術、服務與管理方式等。Internet設計目標是使所有的網絡盡可能容易的加入到Internet中，Internet假定實際的子網缺少可靠性的保障，所以IP采用了數據報協議，子網內部采用什么樣的協議與IP無關，IP的主要功能如下： 為數據報通過Internet提供路由。 尋址，為源和目的節點提供地址信息。 將數據分段，重裝以適應不同的網絡對分組長度的限制。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology I

26、P地址分為IPV4和IPV6地址類型IPV4地址分為A、B、C、D、E五類，長度32bit，8bit為一個基本單元，采用10進制表示，用“.”相連；IPV6地址長度為128bit，采用16進制表示，16bit作為一個基本單元，相互間用“:”相連，分為三類：單播、組播、選播地址。 在IP中，數據報的原始長度是用戶確定的，IP根據需要將一個數據報分成若干較小的段，在網絡中自由的傳輸，到達目的節點后，再組裝成分組交給應用層。 在IP分組中，分段有四個參量：分段的起始位置；段長度；MF=0表示數據報的最后一段，MF=1中間段；DF=1表示不允許分段，DF=0表示可以分段；數據報的標識ID。信息網絡理論基礎NANJING UNIVERSITY of Science & Technology信息網絡理論基礎NANJING UNIVERSITY of Science & Technology2.4.3 傳輸層的點對點傳輸協議 1. TCP中的尋址和復接尋址：一般TCP之上有很多進程，為了區分這些進程，需要對他們進行編址，每一個進程稱之為一個端口（Port）16bit表示，一個完整的地址應當包含三個部分：網絡號、主機號、端口，稱之為套接