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

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

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

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

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

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

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

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

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

9、件的開發(fā)周期，提高網(wǎng)絡(luò)軟件可維護(hù)性。第七章 協(xié)議實(shí)現(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é)議實(shí)現(xiàn)技術(shù)1.協(xié)議規(guī)范的預(yù)處理 用形式描述語言描述的協(xié)議規(guī)范中往往存在許多沒有具體數(shù)值的符號定義。例如用ESTELLE描述的AB協(xié)議中（參見第四章4.2.

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

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

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

13、括郵箱、共享存貯區(qū)、事件、共享文件，其中郵箱是常用的通訊方法。第七章 協(xié)議實(shí)現(xiàn)技術(shù)郵箱是VMS的一種偽設(shè)備，用戶程序通過標(biāo)準(zhǔn)的QIO服務(wù)就可以讀寫郵箱。郵箱名是系統(tǒng)邏輯符號，為所有進(jìn)程所認(rèn)識。當(dāng)多個進(jìn)程對名字相同的郵箱進(jìn)行讀寫時，它們實(shí)際上就進(jìn)行通訊。下面列出有關(guān)郵箱服務(wù)和c語言調(diào)用。（1）定義郵箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name為放置郵箱名字符串MBX_NAME的變量。第七章 協(xié)議實(shí)現(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)服務(wù)crembx創(chuàng)建一個郵箱（如果該郵箱不存在），并賦于一個通道號，&表示傳遞變量的地址值。第七章 協(xié)議實(shí)現(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服務(wù)（記作QIO(write)）向郵箱發(fā)一個郵件，第二個QIO服務(wù)（記作QIO(read)）從郵箱讀一個郵件，mail為發(fā)出的郵件，buf為放置接收郵件的緩沖器。QIO(read)

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

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

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

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

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

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

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

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

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

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

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

26、已經(jīng)達(dá)到限額，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é)議實(shí)現(xiàn)技術(shù)圖7.8間接死鎖第七章 協(xié)議實(shí)現(xiàn)技術(shù) 間接死鎖的解決辦法之一基于分類報文概念。網(wǎng)絡(luò)層處理輸入報文時按照一定的分類方法將它們分成不同類別的報文，給每個報文打上類別標(biāo)記，并按照報文類別分配接收緩沖器的限額。 報文分類的第一種方法是按照輸出線路進(jìn)行。例如，假如某結(jié)點(diǎn)有三條輸出線路a，b，c，當(dāng)網(wǎng)絡(luò)層處理報文時發(fā)現(xiàn)報文需經(jīng)線路a轉(zhuǎn)發(fā)，那么它的類別為a;經(jīng)b轉(zhuǎn)發(fā)，它的類別就為b。這

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

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

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

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

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

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

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