7協(xié)議工程之協(xié)議實現(xiàn)技術(shù)

1、第七章 協(xié)議實現(xiàn)技術(shù)7.1概述 計算機網(wǎng)絡各層協(xié)議實現(xiàn)結(jié)果的集合形成計算機網(wǎng)絡軟件和硬件。計算機網(wǎng)絡軟件和計算機操作系統(tǒng)密切相關(guān)，它往往是操作系統(tǒng)的一部分，計算機網(wǎng)絡硬件和計算機硬件系統(tǒng)密切相關(guān)，它是計算機I/O系統(tǒng)的一部分。圖7.1為DEC公司的DNA在VAX/VMS中的實現(xiàn)結(jié)構(gòu)。DNA（Digital Network Architecture）是DEC公司所采用的各層網(wǎng)絡協(xié)議的總稱，它在VAX/VMS之中實現(xiàn)后軟件和硬件的總稱為DECNET/VMS。第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù) DNA的物理層和數(shù)據(jù)鏈路層協(xié)議實現(xiàn)于網(wǎng)絡適配器（device adaptor）中，DECnet/VM

2、S包括許多網(wǎng)絡適配器，即DNA支持許多種低層通信協(xié)議。DNA的網(wǎng)絡層和傳輸層協(xié)議主要實現(xiàn)于偽驅(qū)動程序NETDRIVER中，它和網(wǎng)絡適配器的設備驅(qū)動程序(device driver)接口。DNA的高層協(xié)議以網(wǎng)絡目標模塊形式或?qū)嵱贸绦虻男问綄崿F(xiàn)，DECnet/VMS包括許多這樣的目標模塊（object）和實用程序(utility)，這表示它向用戶提供豐富的網(wǎng)絡服務。這里，NETDRIVER和device driver是VMS內(nèi)核一部分，DNA高層和VMS的文件系統(tǒng)，作業(yè)調(diào)度，用戶登陸（login）等密切聯(lián)系，網(wǎng)絡適配器是VAX硬件系統(tǒng)的一部分，計算機網(wǎng)絡各層協(xié)議在其它機器和操作系統(tǒng)中實現(xiàn)形式和實現(xiàn)

3、結(jié)構(gòu)都類似于DECnet/VMS。第七章 協(xié)議實現(xiàn)技術(shù) 計算機網(wǎng)絡協(xié)議是復雜的協(xié)議，將它們付諸實現(xiàn)更是一個復雜的技術(shù)過程，這是因為計算機網(wǎng)絡硬件和軟件與計算機硬件操作系統(tǒng)的關(guān)系非常密切的原故。一個計算機網(wǎng)絡的研制要經(jīng)歷下述七步工作。(1) 網(wǎng)絡體系結(jié)構(gòu)的制定 網(wǎng)絡體系結(jié)構(gòu)（Network Architecture）的制定包括許多決策工作：網(wǎng)絡支持哪些通訊線路和局域網(wǎng)？向用戶提供哪些網(wǎng)絡服務？網(wǎng)絡劃分成多少層？各層的協(xié)議功能是什么？各層協(xié)議規(guī)范和服務規(guī)范是什么？第七章 協(xié)議實現(xiàn)技術(shù)(2) 實現(xiàn)環(huán)境的研究 實現(xiàn)環(huán)境指計算機的機型和運行的操作系統(tǒng)。實現(xiàn)環(huán)境的研究是協(xié)議實現(xiàn)者必須進行的一項工作，這包括

4、計算機硬件結(jié)構(gòu)和I/O總線的詳細了解，操作系統(tǒng)結(jié)構(gòu)和操作系統(tǒng)服務的詳細了解等等。(3) 實現(xiàn)結(jié)構(gòu)的設計 在(1)和(2)的工作完成之后，協(xié)議設計者就可以著手網(wǎng)絡實現(xiàn)結(jié)構(gòu)設計。實現(xiàn)結(jié)構(gòu)的設計包括一系列的決策工作：哪幾層協(xié)議在網(wǎng)絡適配器中實現(xiàn)，哪幾層協(xié)議在操作系統(tǒng)中實現(xiàn)？操作系統(tǒng)的網(wǎng)絡軟件劃分成幾個進程，每個進程實現(xiàn)哪幾層協(xié)議？如果幾層協(xié)議在同一個進程實現(xiàn)時，各層協(xié)議之間怎樣相互調(diào)用？為了提高網(wǎng)絡軟件執(zhí)行效率和連接響應速度應采用哪些措施等等。第七章 協(xié)議實現(xiàn)技術(shù)(4) 各層協(xié)議實體之間通訊機制設計 當n層協(xié)議和(n-1)層協(xié)議在不同的進程或驅(qū)動程序之間實現(xiàn)時，n層協(xié)議實體和n-1層協(xié)議實體之間通訊

5、必須借助操作系統(tǒng)服務來實現(xiàn)。當n層協(xié)議和(n-1)層協(xié)議在同一個進程或驅(qū)動程序之內(nèi)實現(xiàn)時，兩層協(xié)議實體之間通訊可直接借助于程序設計語言(c,pascal)來實現(xiàn)。(5) 數(shù)據(jù)緩沖方案的設計 協(xié)議數(shù)據(jù)單元PDU(protocol data unit)在各層協(xié)議實體之間的傳遞是通過緩沖器來實現(xiàn)的。數(shù)據(jù)緩沖方案的設計包括一系列的決策工作：緩沖器中的數(shù)據(jù)怎樣傳遞？是否采用共享緩沖器方案？緩沖器定義多大？緩沖器怎樣分配管理？緩沖器的分配管理怎樣對網(wǎng)絡流控制和交通擁塞控制施加影響等等。第七章 協(xié)議實現(xiàn)技術(shù)(6) 各層協(xié)議代碼的產(chǎn)生協(xié)議代碼可分為兩部分：與實現(xiàn)環(huán)境相關(guān)的協(xié)議代碼和獨立于實現(xiàn)環(huán)境的協(xié)議代碼。前

6、者必須由協(xié)議實現(xiàn)者手工完成，后者可手工完成也可以借助形式語言的編輯程序（如ESTELLE compiler）自動產(chǎn)生。(7) 網(wǎng)絡軟件的調(diào)試由于網(wǎng)絡軟件的分布性，異步性和實時性，傳統(tǒng)的靜態(tài)調(diào)試工具是不適應的，因此設計者必須研制多種動態(tài)調(diào)試工具以提高網(wǎng)絡軟件調(diào)試效率。這些調(diào)試工具包括各種模擬環(huán)境，閉環(huán)測試軟件，PDU追蹤，時間標簽，事件記錄等。第七章 協(xié)議實現(xiàn)技術(shù) 限于篇幅，本章只討論(4)、(5)、(6)步驟的有關(guān)問題，首先介紹協(xié)議代碼半自動生成技術(shù)，然后討論上下層協(xié)議實體之間通訊的實現(xiàn)方法，最后討論數(shù)據(jù)緩沖技術(shù)。如果我們掌握了第(4)和第(5)步的設計方法，那么與實現(xiàn)環(huán)境相關(guān)的協(xié)議代碼就可以

7、手工完成了。計算機網(wǎng)絡研制工作中第（1）、（2）、（3）和（7）步工作的討論請參見文獻資料42和34。第七章 協(xié)議實現(xiàn)技術(shù)7.2 協(xié)議代碼半自動生成技術(shù) 協(xié)議代碼半自動生成技術(shù)試圖將協(xié)議規(guī)范文本（用ESTELLE、LOTOS等語言描述)直接轉(zhuǎn)換成協(xié)議代碼（c.pascal等程序設計語言）。如果所產(chǎn)生的代碼不需要人工修改就可以編譯成機器可執(zhí)行的程序，這是最理想的。但由于計算機網(wǎng)絡軟件和操作系統(tǒng)結(jié)合緊密，這實際上是不現(xiàn)實的。由協(xié)議規(guī)范直接轉(zhuǎn)換的協(xié)議代碼只能占全部代碼的一部分，約50%左右33，這部分代碼稱之為獨立于實現(xiàn)環(huán)境的代碼，另外一部分代碼由于和實現(xiàn)環(huán)境相關(guān)，必須由手工完成。協(xié)議代碼的這種生成

8、方法稱之為協(xié)議代碼的半自動生成技術(shù)。 關(guān)于協(xié)議代碼半自動生成技術(shù)是否值得深入研究的問題，人們尚有不同的看法。然而，半自動生成技術(shù)顯然有如下一些好處： 第七章 協(xié)議實現(xiàn)技術(shù)（1）利用同一個翻譯程序從同一個協(xié)議規(guī)范中產(chǎn)生的協(xié)議代碼總是一致的，它不隨協(xié)議實現(xiàn)者的不同而不同。這就是說，所有協(xié)議實現(xiàn)者都能夠獲得一份相同的協(xié)議代碼。雖然這一部分協(xié)議代碼只占總代碼的50%左右，但它包括協(xié)議的主體部分。它確定了協(xié)議的所有邏輯關(guān)系，因此它為協(xié)議的不同實現(xiàn)版本的互連提供了良好的基礎。（2）協(xié)議規(guī)范的更新修改不會給協(xié)議實現(xiàn)者帶來太多的麻煩，它只要重新運行一次翻譯程序就可以了。（3）由此減少手工編程的錯誤，縮短網(wǎng)絡軟

9、件的開發(fā)周期，提高網(wǎng)絡軟件可維護性。第七章 協(xié)議實現(xiàn)技術(shù) 目前，世界上已開發(fā)了多種協(xié)議代碼半生成軟件，它們大都基于ESTELLE，LOTOS和SDL語言，翻譯后的協(xié)議代碼大都為C代碼。下面簡單介紹EDS（Estelle Development System）中協(xié)議代碼半自動生成的基本過程33，它將協(xié)議代碼半自動生成過程分為四步。 ESTELLE半自動生成過程可用圖7.2表示，圖中.e表示類型為.e 的文件，.m表示類型為.m文件。f第七章 協(xié)議實現(xiàn)技術(shù)1.協(xié)議規(guī)范的預處理 用形式描述語言描述的協(xié)議規(guī)范中往往存在許多沒有具體數(shù)值的符號定義。例如用ESTELLE描述的AB協(xié)議中（參見第四章4.2.

10、4) ，常數(shù)low,high,retran-time未給出具體數(shù)值，預處理要求實現(xiàn)者給出具體數(shù)值。又例如，在ESTELLE:描述的AB協(xié)議中，數(shù)據(jù)類型定義U一data一type是含糊的(它用表示)，這要求協(xié)議實現(xiàn)者給出它的具體定義（如定義為string of characters）。預處理要做的工作包括原語primitive的標識等工作。 預處理的第二項重要工作是將協(xié)議規(guī)范文本(.e)分割成三個文件：模塊描述文件(.m)，實現(xiàn)描述文件(.i)和格式描述文件(.f)。模塊描述文件即為原協(xié)議規(guī)范中的模塊頭定義和模塊體定義。實現(xiàn)描述文件將原協(xié)議規(guī)范中有關(guān)各模塊的性質(zhì)定義，模塊之間組織關(guān)系描述，模塊之

11、間通訊機制描述等全局性內(nèi)容抽取出來，形成一個描述整個協(xié)議的框架文件。格式描述文件完整地描述模塊之間報文交換的格式，它也是從原協(xié)議規(guī)范文件中抽出來的。第七章 協(xié)議實現(xiàn)技術(shù)2.翻譯 預處理后的協(xié)議規(guī)范直接送入ESTELLE compiler翻譯，翻譯包括語法校對、C代碼生成等工作。對模塊體文件，翻譯結(jié)果是對應于每一個ESTELLE模塊體產(chǎn)生一個C代碼的模塊頭文件(head file)和一個C代碼的模塊體文件(body file)。模塊頭文件包含模塊體內(nèi)所有數(shù)據(jù)結(jié)構(gòu)和變量（如交互點ip和ep、隊列等）。模塊體文件包含模塊體內(nèi)所有函數(shù)、過程的代碼，除模塊體原有的函數(shù)和過程定義之外，模塊體的每一個轉(zhuǎn)換都

12、翻譯成過程。 第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)3.手工程序的編寫 凡是與系統(tǒng)相關(guān)的部分（通訊機制、緩沖器管理、文件訪問、訪問控制等等)必須由協(xié)議實現(xiàn)者根據(jù)實現(xiàn)環(huán)境手工編寫。4.執(zhí)行代瑪?shù)漠a(chǎn)生 上述所有C程序文件編譯后鏈接成一個或幾個系統(tǒng)可執(zhí)行的文件，每個可執(zhí)行的文件對應于一個進程或用戶啟動的實用程序。第七章 協(xié)議實現(xiàn)技術(shù) 7.3 模塊通訊的實現(xiàn)方法 ESTELLE模塊之間的通訊的實現(xiàn)很大程度上依賴于操作系統(tǒng)所提供的服務。在VAX/VMS環(huán)境中，如果兩個模塊體分別用兩個進程實現(xiàn)，那么VMS所提供的進程通訊服務就成為模塊通訊實現(xiàn)的基礎。VAX/VMS提供的進程通訊機制包

13、括郵箱、共享存貯區(qū)、事件、共享文件，其中郵箱是常用的通訊方法。第七章 協(xié)議實現(xiàn)技術(shù)郵箱是VMS的一種偽設備，用戶程序通過標準的QIO服務就可以讀寫郵箱。郵箱名是系統(tǒng)邏輯符號，為所有進程所認識。當多個進程對名字相同的郵箱進行讀寫時，它們實際上就進行通訊。下面列出有關(guān)郵箱服務和c語言調(diào)用。（1）定義郵箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name為放置郵箱名字符串MBX_NAME的變量。第七章 協(xié)議實現(xiàn)技術(shù)(2) 定義郵箱通道int mbx_ch;mbx_ch為32位的長字，它放置郵箱通道號。(3) 創(chuàng)建郵箱通道sys$crembx(1,&mbx_ch,0,

14、0,0,0,&mbx_name);VMS系統(tǒng)服務crembx創(chuàng)建一個郵箱（如果該郵箱不存在），并賦于一個通道號，&表示傳遞變量的地址值。第七章 協(xié)議實現(xiàn)技術(shù)(4) QIO操作sys$qio(0,mbx_ch,IO$_WRITEVBLK,0,0,0,&mail,mail_size,0,0,0,0);sys$qio(0,mbx_ch,IO$_READVBLK,0,0,0,&buf_size,0,0,0,0);第一個QIO服務（記作QIO(write)）向郵箱發(fā)一個郵件，第二個QIO服務（記作QIO(read)）從郵箱讀一個郵件，mail為發(fā)出的郵件，buf為放置接收郵件的緩沖器。QIO(read)

15、可以通過AST(AsyncTrap)形成異步地進行（類似中斷方式），這給用戶程序的設計帶來很多好處。(5) 取消郵箱sys$delmbx(mbx_ch);切斷用戶程序和郵箱之間建立的通路。第七章 協(xié)議實現(xiàn)技術(shù)熟悉了VMS郵箱的使用方法，我們就很容易找到怎樣實現(xiàn)ESTELLE模塊之間通訊的實現(xiàn)途徑。下面簡述郵箱服務和ESTELLE模塊通訊語句之間對應關(guān)系。(1) channel定義一個channel對應一個VMS郵箱，channel名用$DESCRIPTOR來說明，channel定義中交互用過程表示，每個過程負責向郵箱發(fā)出一個郵件，郵件內(nèi)容包括交互名和傳遞的參數(shù)。下面的例子說明AB協(xié)議chann

16、el N-access-point定義翻譯成C語言的情況 第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)7.4 數(shù)據(jù)緩沖技術(shù) 協(xié)議數(shù)據(jù)單元(PDU )在機器中的存貯以及上下層協(xié)議實體之間的傳遞是通過緩沖器來實現(xiàn)的，因此緩沖器的使用、分配和管理成為協(xié)議實現(xiàn)中關(guān)鍵技術(shù)之一。 數(shù)據(jù)緩沖技術(shù)涉及三個問題：存貯空間的利用率，對協(xié)議執(zhí)行速度的影響，對協(xié)議機制和網(wǎng)絡性能的影響。(1)存貯空間利用率 協(xié)議數(shù)據(jù)單元的大小不是固定的，小到幾個字節(jié)，大到數(shù)千個字節(jié)。如果按最大的單元固定劃分緩沖器，對于小報文，存貯空間利用率很低。一個網(wǎng)絡中總是存在許多用戶，在多用戶情況下，一個機器中

17、的邏輯鏈路數(shù)是隨用戶而動態(tài)變化的。如果按照最大用戶數(shù)給每條邏輯鏈路分配固定的緩沖器，那么在用戶少的情況下，存貯空間浪費較大。第七章 協(xié)議實現(xiàn)技術(shù)(2)協(xié)議執(zhí)行速度 協(xié)議數(shù)據(jù)單元在上下層的傳遞可采用兩種方法：緩沖器指針傳遞法和緩沖器復制法。很顯然，前者的額外開銷小，協(xié)議執(zhí)行速度高。問題(l)和(2)是有矛盾的。為了提高存貯空間利用率，緩沖器長度設定要小，但對于大數(shù)據(jù)單元則需要多個緩沖器來容納，多個緩沖器容納一個數(shù)據(jù)單元的處理將給軟件帶來許多麻煩。(3)協(xié)議機制和網(wǎng)絡性能 緩沖器是網(wǎng)絡的最重要的資源，許多協(xié)議機制的執(zhí)行依賴于緩沖器的可用度。例如，傳輸層在實行窗口流控制時，發(fā)送窗口的寬度是由對方的接

18、收能力決定的（主要是可用的緩沖器的數(shù)口）。對于有路由功能的網(wǎng)絡層協(xié)議實體來說，緩沖器的分配管理算法與網(wǎng)絡擁塞控制策略和死鎖防止方法密切相關(guān)。 第七章 協(xié)議實現(xiàn)技術(shù)7.4.1緩沖器指針傳遞方法 數(shù)據(jù)單元在上下層協(xié)議實體之間的傳遞采用緩沖器指針傳遞方法時所要解決的一個重要問題是數(shù)據(jù)單元的分段與合段。例如，當會晤層的一個協(xié)議數(shù)據(jù)單元SPDU(session protocol data unit)用指針傳遞方法送給傳輸層協(xié)議實體后，可能要將它分成三段，即一個TSDU變成三個TPDU(transport protocol data unit)，這里的TSDU(transport service data

19、 unit)就是SPDU。由于傳輸層必須給每段數(shù)據(jù)添加一個傳輸層報文頭TH(transport head)，因此除第一個TPDU之后，后兩個TPDU的形成都避免不了數(shù)據(jù)的復制，圖7.3示出這一個過程。圖7.3 數(shù)據(jù)分段引起數(shù)據(jù)復制第七章 協(xié)議實現(xiàn)技術(shù)為了解決分段引起的數(shù)據(jù)復制，我們可以采用這樣的一種方法：如果設傳輸層允許的TPDU最大長度為l，它的報文頭TH最大長度為n，那么會晤層可使用長度為l的多個緩沖器，將一個SPDU分割成多個長度小于（l-n）的段分別放在不同的緩沖器中，然后將緩沖器鏈傳遞給傳輸層，圖7.4示出緩沖器鏈傳遞方法。圖7.4緩沖器鏈傳遞第七章 協(xié)議實現(xiàn)技術(shù)上述方法仍然有一個缺

20、點，即會晤層交給傳輸層的緩沖器，其頭部必須留足夠的空間以便傳輸層（還包括網(wǎng)絡層及底層）填寫它的報文頭。這樣不但存儲空間有浪費，而且緩沖器指針要隨報文頭的添加數(shù)而修改。圖7.5所示的方法中，各層協(xié)議頭使用專門的小緩沖器，用戶數(shù)據(jù)分放在多個大緩沖器中。圖7.5用戶數(shù)據(jù)和報文頭分別用不同的緩沖器第七章 協(xié)議實現(xiàn)技術(shù)7.4.2共享緩沖區(qū)的分配和管理為了提高存儲空間的利用率，人們往往采用共享緩沖器的方法。圖7.6為共享緩沖區(qū)示意圖。傳輸層提供n條邏輯鏈路服務，每個應用層協(xié)議實體（如a,b,c）通過表示層協(xié)議實體P和會晤層協(xié)議實體S使用一條邏輯鏈路。N條邏輯鏈路共享發(fā)送緩沖區(qū). 例如當應用層實體a要發(fā)送一

21、個報文時，它從發(fā)送緩沖區(qū)獲取一個或多個緩沖器，然后將裝載報文的緩沖鏈逐層傳遞給P層，S層，傳輸層和網(wǎng)絡層。網(wǎng)絡層將報文從指定通訊網(wǎng)絡或線路發(fā)出之后，將空緩沖器歸給發(fā)送緩沖區(qū)。接收緩沖區(qū)向各個通訊網(wǎng)絡端口或點對點線路端口提供接收緩沖器。裝填有接收報文的緩沖器首先由網(wǎng)絡層處理，網(wǎng)絡層或?qū)⒕彌_器上交傳輸層處理（如果報文的目的地址是本地地址），或?qū)⒕彌_器交給另外的通訊網(wǎng)絡端口轉(zhuǎn)發(fā)（如果報文的目的地址不是本地結(jié)點），或?qū)⒕彌_器歸還給接收緩沖區(qū)（如果報文是網(wǎng)絡層報文）。圖7.6共享緩沖區(qū)第七章 協(xié)議實現(xiàn)技術(shù)共享緩沖區(qū)固然可以提高存儲空間利用率，但如果沒有合理的分配管理算法，將帶來嚴重的副作用。第一個嚴重的

22、副作用是緩沖器的枯竭。當某條邏輯鏈路通訊流量特別大時，它可能獨占所有發(fā)送緩沖器，以致其它應用層協(xié)議實體不能獲得緩沖器，造成緩沖器枯竭現(xiàn)象。第二個嚴重的副作用是不合理的接收緩沖器分配管理算法將會造成網(wǎng)絡死鎖現(xiàn)象。第七章 協(xié)議實現(xiàn)技術(shù) 本節(jié)討論緩沖器的公平分配問題，下節(jié)討論接收緩沖器分配管理與網(wǎng)絡性能的關(guān)系。 對于發(fā)送緩沖器，最常用的分配算法是平方根法。設發(fā)送緩沖區(qū)所能提供的緩沖器數(shù)目為B，當前活躍的邏輯鏈路數(shù)為n，那么每條鏈路所能占用的發(fā)送緩沖器的最高限額不應大于B/ 。 對于接收緩沖器，緩沖器的占用者的概念不同于發(fā)送緩沖器。當一個通訊子網(wǎng)接收一個報文，并將報文放入緩沖器之后并不能立刻確定該緩沖

23、器由誰占用。裝填接收報文的緩沖器經(jīng)由網(wǎng)絡層處理之后，報文的占用者就確定了 第七章 協(xié)議實現(xiàn)技術(shù) 例如，當圖7.6中的net1收到一個報文并將緩沖器交網(wǎng)絡層之后；網(wǎng)絡層處理該報文，如果該報文向net2轉(zhuǎn)發(fā)，那么緩沖器占用者是net2；如果該報文上交傳輸層，那么緩沖器的占用者是本地結(jié)點。這樣，如果網(wǎng)絡層有路由功能，并且它支持m路輸出線路（通訊子網(wǎng)端口），那么接收緩沖器要在m+1個對象中分配；如果網(wǎng)絡層沒有路由功能，那么所有接收緩沖區(qū)都歸本地結(jié)點所有。如果本地結(jié)點當前有n條活躍邏輯鏈路，那么對于分配給本地結(jié)點的那份接收緩沖器再按n個對象分配（或平均分配，或按平方根分配）。 第七章 協(xié)議實現(xiàn)技術(shù)7.4

24、.3 接收緩沖器的分配管理如果網(wǎng)絡層有路由功能，那么接收緩沖區(qū)的分配管理算法就比較復雜，不合理的分配算法還將產(chǎn)生死鎖等副作用。下面分別討論三個副作用及解決辦法。1.直接死鎖（direct deadlock） 假定接收緩沖區(qū)的分配是任意的，即每一條輸出線路端口可以占用任意多緩沖器，直至接收緩沖區(qū)枯竭為止，那么圖7.7所示的直接死鎖現(xiàn)象就可能出現(xiàn)。圖中，由于結(jié)點A的所有接收緩沖器已被端口a所占用，它不能再接收b的報文，而B的所有緩沖器已被端口b所占用，它也不能接收A發(fā)出的報文，死鎖發(fā)生！直接死鎖產(chǎn)生的原因是雙方接收緩沖區(qū)同時枯竭，解決的辦法是避免接收緩沖區(qū)枯竭。假定結(jié)點的接收緩沖區(qū)的緩沖器總數(shù)為C

25、，對于有m條輸出線路（端口）同時活躍的情況，各條輸出線路所能占用的接收緩沖器限額應小于Ct=C/（m+1），本地結(jié)點看作一路輸出，它所分配的限額也為Ct。按照這種平均法則分配接收緩沖器枯竭現(xiàn)象永不會發(fā)生，直接死鎖就消除了。第七章 協(xié)議實現(xiàn)技術(shù)圖7.7直接死鎖第七章 協(xié)議實現(xiàn)技術(shù)2.間接死鎖（indirect deadlock） 即便是對輸出線路所占用的緩沖器進行限制圖7.8所示的死鎖還可能發(fā)生。這種由多個結(jié)點的輸出隊列所形成的環(huán)路死鎖稱為間接死鎖。間接死鎖發(fā)生時各個結(jié)點的接收緩沖區(qū)并沒有枯竭。圖7.8中，A中的輸出線路a的所有報文的目的地址不是B，但必須經(jīng)過B的端口b轉(zhuǎn)發(fā)，由于b的輸出隊列長度

26、已經(jīng)達到限額，B無法接收A發(fā)來的必須經(jīng)過端口b轉(zhuǎn)發(fā)的報文。由于同樣情況，C無法接收B發(fā)來的必須經(jīng)端口c轉(zhuǎn)發(fā)的報文，D無法接收C發(fā)來的必須經(jīng)端口d轉(zhuǎn)發(fā)的報文，A無法接收D發(fā)來必須經(jīng)端口a轉(zhuǎn)發(fā)的報文，死鎖發(fā)生！第七章 協(xié)議實現(xiàn)技術(shù)圖7.8間接死鎖第七章 協(xié)議實現(xiàn)技術(shù) 間接死鎖的解決辦法之一基于分類報文概念。網(wǎng)絡層處理輸入報文時按照一定的分類方法將它們分成不同類別的報文，給每個報文打上類別標記，并按照報文類別分配接收緩沖器的限額。 報文分類的第一種方法是按照輸出線路進行。例如，假如某結(jié)點有三條輸出線路a，b，c，當網(wǎng)絡層處理報文時發(fā)現(xiàn)報文需經(jīng)線路a轉(zhuǎn)發(fā)，那么它的類別為a;經(jīng)b轉(zhuǎn)發(fā)，它的類別就為b。這

27、是最簡單的分類法，但不能解決間接死鎖問題。 第七章 協(xié)議實現(xiàn)技術(shù) 報文分類的第二種方法是按照報文已走過的鏈路數(shù)或到達目的結(jié)點之前還需走過的鏈路數(shù)進行，前者稱之為后向鏈分類法，后者稱之為前向分類法。按照前向鏈分類法，到達目的結(jié)點之前還要走n條鏈路的報文為n類報文，n類報文邏輯上放入n隊列。1類報文的目的結(jié)點就是鄰近結(jié)點。按照這種方法對報文分類從根本上消除了圖7.8所示的輸入隊列環(huán)路，因此不會發(fā)生間接死鎖。圖7.9中，各個輸出端口邏輯上有三個隊列q1，q2，q3。q1放1類報文（到達目的結(jié)點的鏈路數(shù)為1），q2放2類報文 ，q3放3類報文。當圖7.8所示的情況出現(xiàn)時（各個結(jié)點的q2的長度已到達限額

28、），死鎖不會出現(xiàn)，這是因為B能接收A從q2發(fā)出的報文，并將報文放入B的q1隊列（A中的2類報文到達B后變成1類報文）。如果假定B的q1隊列也已到達限額，但由于B將q1隊列中的報文發(fā)往C之后，C總是能接收目的結(jié)點就是C的報文（B的q1隊列很快就會倒空）死鎖就不會出現(xiàn)。第七章 協(xié)議實現(xiàn)技術(shù)圖7.9前向鏈分類法第七章 協(xié)議實現(xiàn)技術(shù)3.交通流量控制 接收緩沖區(qū)的分配管理與網(wǎng)絡報文流量控制有關(guān)，或者說某些交通流量控制算法是通過接收緩沖器的分配管理來實現(xiàn)的。其中最常用的做法是對不同類別的報文實行優(yōu)先級別控制（優(yōu)先界別高的報文可獲得多的接收緩沖器），以提高網(wǎng)絡流通量，減少交通堵塞發(fā)生率。例如，當采用前向鏈分

29、類法時，如果使類別低的報文優(yōu)先級別高（即1類報文優(yōu)先于2類報文）就能使接近于目的結(jié)點報文盡快離開網(wǎng)絡，避免交通堵塞。第七章 協(xié)議實現(xiàn)技術(shù)7.5協(xié)議并行處理技術(shù) 隨著數(shù)據(jù)通訊速率的提高，計算機網(wǎng)絡各層協(xié)議的執(zhí)行速度也必須提高。例如，當數(shù)據(jù)傳輸速率為1Gbps（1000Mbps）時，如果傳輸層的平均報文長度為128字節(jié)，那么它每秒要處理一百萬個報文。如果每個報文的處理要花費50條指令（不包括CRC校驗），那么傳輸層協(xié)議處理器的速度應大于50Mips。如果傳輸層報文包含CRC碼，處理器速度要更高（約100Mips）。MIPS-Million Instructions Per Second 每秒百萬條

30、指令第七章 協(xié)議實現(xiàn)技術(shù) 提高協(xié)議執(zhí)行速度的辦法之一是協(xié)議并行處理技術(shù)，即用多個CPU并行執(zhí)行某層協(xié)議。 文獻【14】以傳輸層協(xié)議為例，定義了三種粒度（grains）不同的協(xié)議并行處理;粗粒度（coarse grain）并行，中粒度（medium grain）并行和細粒度（fine grain）并行。 按粗粒度并行處理協(xié)議時，協(xié)議實體按功能劃分成多個任務，各個任務分配給不同的CPU處理。例如，傳輸層協(xié)議可劃分成聯(lián)接處理，數(shù)據(jù)接收處理。數(shù)據(jù)發(fā)送處理等多個任務。如果協(xié)議功能劃分更細一點（如圖3.16描述的ISO TP4數(shù)據(jù)發(fā)送模型那樣），這些任務可分配給更多的CPU執(zhí)行。 第七章 協(xié)議實現(xiàn)技術(shù) 按

31、中較度并行處理協(xié)議時，多個輸人報文分配給多個CPU處理。輸入報文在多個CPU中分配的方法有兩種:隨機分配和輪循分配。對于隨機分配方法，當一個輸入報文來到時，如果處理器池子中有空閑的處理器，則隨機地占用一個處理器處理該報文；如果處理器池子中沒有空閑的處理器，該報文則進人等待隊列。對于輪循分配法，輸人報文輪詢分配法，輸入報文按先后次序輪循地分配給多個處理器。例如，設處理器池子有5個CPU，第1號報文分配給CPU1，第2號報文分配給CPU2，第6號報文分配CPU1， 按細粒度并行處理協(xié)議時。多個處理器同時處理一個報文。例如，多個處理器同時分析處理一個報文頭時，每個處理器分析報文頭的一個字段。第七章

32、協(xié)議實現(xiàn)技術(shù)粗粒度并行處理易于實現(xiàn)，這是因為各個任務界限清晰，相關(guān)性小。但粗粒度并行度小，速度提高有限。細粒度可獲得很高并行度，但實現(xiàn)困難。中粒度并行處理技術(shù)兼有兩者優(yōu)點，值得人們深人研究。第七章 協(xié)議實現(xiàn)技術(shù) 作為例子，圖7.10示出傳輸層報文發(fā)送的并行模型，圖7.11示出傳輸層報文接收的并行模型。圖7.10中，會晤層交給傳輸層的報文流（TSDU流）按輪循法則分配繪m個處理器（P1，P2，Pm），并放在各個處理器的局部存貯器隊列（q1，12，qm）中。報文發(fā)出之后，它進入Rctran隊列。由處理器R負責報文的重發(fā)。圖7.11中，網(wǎng)絡層交給傳輸層的輸人報文流（TPDU流）按輪循的方法分配給n個

33、處理器（P1，P2，Pn），并放在各個處理器的局部存貯器隊列（q1，q2，qn）中。正確的報文收到之后產(chǎn)生一個ACK信息放人ACK隊列。處理器Q專門負責發(fā)送入ACK報文。圖7.10和圖7.11只是一個傳輸層協(xié)議并行處理的模型，將它們付諸實現(xiàn)還必須解決以下一些問題。圖7.10 傳輸層報文發(fā)送并行模型 圖7.11 傳輸層報文接收并行模型第七章 協(xié)議實現(xiàn)技術(shù)第七章 協(xié)議實現(xiàn)技術(shù)1發(fā)送窗口問題 RTD（Round Time Delay）指報文從一個傳愉層協(xié)議實體到另外一個傳愉層協(xié)議實體之間來回傳送一次的延遲時問，它是傳愉層窗口流控制的重要參數(shù)。當兩臺機器距1000千米時，RTD近似于10ms。在數(shù)據(jù)傳輸1Gbps時，一個長度為512字節(jié)的報文只需4us傳送時