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

1、第七章 協(xié)議實(shí)現(xiàn)技術(shù)7.1概述 計(jì)算機(jī)網(wǎng)絡(luò)各層協(xié)議實(shí)現(xiàn)結(jié)果的集合形成計(jì)算機(jī)網(wǎng)絡(luò)軟件和硬件。計(jì)算機(jī)網(wǎng)絡(luò)軟件和計(jì)算機(jī)操作系統(tǒng)密切相關(guān)，它往往是操作系統(tǒng)的一部分，計(jì)算機(jī)網(wǎng)絡(luò)硬件和計(jì)算機(jī)硬件系統(tǒng)密切相關(guān)，它是計(jì)算機(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ū)動(dòng)程序NETDRIVER中，它和網(wǎng)絡(luò)適配器的設(shè)備驅(qū)動(dòng)程序(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ì)算機(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ì)算機(jī)網(wǎng)絡(luò)協(xié)議是復(fù)雜的協(xié)議，將它們付諸實(shí)現(xiàn)更是一個(gè)復(fù)雜的技術(shù)過(guò)程，這是因?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)硬件和軟件與計(jì)算機(jī)硬件操作系統(tǒng)的關(guān)系非常密切的原故。一個(gè)計(jì)算機(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ī)的機(jī)型和運(yùn)行的操作系統(tǒng)。實(shí)現(xiàn)環(huán)境的研究是協(xié)議實(shí)現(xiàn)者必須進(jìn)行的一項(xiàng)工作，這包括

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

5、必須借助操作系統(tǒng)服務(wù)來(lái)實(shí)現(xiàn)。當(dāng)n層協(xié)議和(n-1)層協(xié)議在同一個(gè)進(jìn)程或驅(qū)動(dòng)程序之內(nèi)實(shí)現(xiàn)時(shí)，兩層協(xié)議實(shí)體之間通訊可直接借助于程序設(shè)計(jì)語(yǔ)言(c,pascal)來(lái)實(shí)現(xiàn)。(5) 數(shù)據(jù)緩沖方案的設(shè)計(jì) 協(xié)議數(shù)據(jù)單元PDU(protocol data unit)在各層協(xié)議實(shí)體之間的傳遞是通過(guò)緩沖器來(lái)實(shí)現(xiàn)的。數(shù)據(jù)緩沖方案的設(shè)計(jì)包括一系列的決策工作：緩沖器中的數(shù)據(jù)怎樣傳遞？是否采用共享緩沖器方案？緩沖器定義多大？緩沖器怎樣分配管理？緩沖器的分配管理怎樣對(duì)網(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)者手工完成，后者可手工完成也可以借助形式語(yǔ)言的編輯程序（如ESTELLE compiler）自動(dòng)產(chǎn)生。(7) 網(wǎng)絡(luò)軟件的調(diào)試由于網(wǎng)絡(luò)軟件的分布性，異步性和實(shí)時(shí)性，傳統(tǒng)的靜態(tài)調(diào)試工具是不適應(yīng)的，因此設(shè)計(jì)者必須研制多種動(dòng)態(tài)調(diào)試工具以提高網(wǎng)絡(luò)軟件調(diào)試效率。這些調(diào)試工具包括各種模擬環(huán)境，閉環(huán)測(cè)試軟件，PDU追蹤，時(shí)間標(biāo)簽，事件記錄等。第七章 協(xié)議實(shí)現(xiàn)技術(shù) 限于篇幅，本章只討論(4)、(5)、(6)步驟的有關(guān)問(wèn)題，首先介紹協(xié)議代碼半自動(dòng)生成技術(shù)，然后討論上下層協(xié)議實(shí)體之間通訊的實(shí)現(xiàn)方法，最后討論數(shù)據(jù)緩沖技術(shù)。如果我們掌握了第(4)和第(5)步的設(shè)計(jì)方法，那么與實(shí)現(xiàn)環(huán)境相關(guān)的協(xié)議代碼就可以

7、手工完成了。計(jì)算機(jī)網(wǎng)絡(luò)研制工作中第（1）、（2）、（3）和（7）步工作的討論請(qǐng)參見(jiàn)文獻(xiàn)資料42和34。第七章 協(xié)議實(shí)現(xiàn)技術(shù)7.2 協(xié)議代碼半自動(dòng)生成技術(shù) 協(xié)議代碼半自動(dòng)生成技術(shù)試圖將協(xié)議規(guī)范文本（用ESTELLE、LOTOS等語(yǔ)言描述)直接轉(zhuǎn)換成協(xié)議代碼（c.pascal等程序設(shè)計(jì)語(yǔ)言）。如果所產(chǎn)生的代碼不需要人工修改就可以編譯成機(jī)器可執(zhí)行的程序，這是最理想的。但由于計(jì)算機(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é)議代碼的半自動(dòng)生成技術(shù)。 關(guān)于協(xié)議代碼半自動(dòng)生成技術(shù)是否值得深入研究的問(wèn)題，人們尚有不同的看法。然而，半自動(dòng)生成技術(shù)顯然有如下一些好處： 第七章 協(xié)議實(shí)現(xiàn)技術(shù)（1）利用同一個(gè)翻譯程序從同一個(gè)協(xié)議規(guī)范中產(chǎn)生的協(xié)議代碼總是一致的，它不隨協(xié)議實(shí)現(xiàn)者的不同而不同。這就是說(shuō)，所有協(xié)議實(shí)現(xiàn)者都能夠獲得一份相同的協(xié)議代碼。雖然這一部分協(xié)議代碼只占總代碼的50%左右，但它包括協(xié)議的主體部分。它確定了協(xié)議的所有邏輯關(guān)系，因此它為協(xié)議的不同實(shí)現(xiàn)版本的互連提供了良好的基礎(chǔ)。（2）協(xié)議規(guī)范的更新修改不會(huì)給協(xié)議實(shí)現(xiàn)者帶來(lái)太多的麻煩，它只要重新運(yùn)行一次翻譯程序就可以了。（3）由此減少手工編程的錯(cuò)誤，縮短網(wǎng)絡(luò)軟

9、件的開(kāi)發(fā)周期，提高網(wǎng)絡(luò)軟件可維護(hù)性。第七章 協(xié)議實(shí)現(xiàn)技術(shù) 目前，世界上已開(kāi)發(fā)了多種協(xié)議代碼半生成軟件，它們大都基于ESTELLE，LOTOS和SDL語(yǔ)言，翻譯后的協(xié)議代碼大都為C代碼。下面簡(jiǎn)單介紹EDS（Estelle Development System）中協(xié)議代碼半自動(dòng)生成的基本過(guò)程33，它將協(xié)議代碼半自動(dòng)生成過(guò)程分為四步。 ESTELLE半自動(dòng)生成過(guò)程可用圖7.2表示，圖中.e表示類型為.e 的文件，.m表示類型為.m文件。f第七章 協(xié)議實(shí)現(xiàn)技術(shù)1.協(xié)議規(guī)范的預(yù)處理 用形式描述語(yǔ)言描述的協(xié)議規(guī)范中往往存在許多沒(méi)有具體數(shù)值的符號(hào)定義。例如用ESTELLE描述的AB協(xié)議中（參見(jiàn)第四章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ù)處理要做的工作包括原語(yǔ)primitive的標(biāo)識(shí)等工作。 預(yù)處理的第二項(xiàng)重要工作是將協(xié)議規(guī)范文本(.e)分割成三個(gè)文件：模塊描述文件(.m)，實(shí)現(xiàn)描述文件(.i)和格式描述文件(.f)。模塊描述文件即為原協(xié)議規(guī)范中的模塊頭定義和模塊體定義。實(shí)現(xiàn)描述文件將原協(xié)議規(guī)范中有關(guān)各模塊的性質(zhì)定義，模塊之間組織關(guān)系描述，模塊之

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

12、翻譯成過(guò)程。 第七章 協(xié)議實(shí)現(xiàn)技術(shù)第七章 協(xié)議實(shí)現(xiàn)技術(shù)第七章 協(xié)議實(shí)現(xiàn)技術(shù)3.手工程序的編寫 凡是與系統(tǒng)相關(guān)的部分（通訊機(jī)制、緩沖器管理、文件訪問(wèn)、訪問(wèn)控制等等)必須由協(xié)議實(shí)現(xiàn)者根據(jù)實(shí)現(xiàn)環(huán)境手工編寫。4.執(zhí)行代瑪?shù)漠a(chǎn)生 上述所有C程序文件編譯后鏈接成一個(gè)或幾個(gè)系統(tǒng)可執(zhí)行的文件，每個(gè)可執(zhí)行的文件對(duì)應(yīng)于一個(gè)進(jìn)程或用戶啟動(dòng)的實(shí)用程序。第七章 協(xié)議實(shí)現(xiàn)技術(shù) 7.3 模塊通訊的實(shí)現(xiàn)方法 ESTELLE模塊之間的通訊的實(shí)現(xiàn)很大程度上依賴于操作系統(tǒng)所提供的服務(wù)。在VAX/VMS環(huán)境中，如果兩個(gè)模塊體分別用兩個(gè)進(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è)備，用戶程序通過(guò)標(biāo)準(zhǔn)的QIO服務(wù)就可以讀寫郵箱。郵箱名是系統(tǒng)邏輯符號(hào)，為所有進(jìn)程所認(rèn)識(shí)。當(dāng)多個(gè)進(jìn)程對(duì)名字相同的郵箱進(jìn)行讀寫時(shí)，它們實(shí)際上就進(jìn)行通訊。下面列出有關(guān)郵箱服務(wù)和c語(yǔ)言調(diào)用。（1）定義郵箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name為放置郵箱名字符串MBX_NAME的變量。第七章 協(xié)議實(shí)現(xiàn)技術(shù)(2) 定義郵箱通道int mbx_ch;mbx_ch為32位的長(zhǎng)字，它放置郵箱通道號(hào)。(3) 創(chuàng)建郵箱通道sys$crembx(1,&mbx_ch,0,

14、0,0,0,&mbx_name);VMS系統(tǒng)服務(wù)crembx創(chuàng)建一個(gè)郵箱（如果該郵箱不存在），并賦于一個(gè)通道號(hào)，&表示傳遞變量的地址值。第七章 協(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);第一個(gè)QIO服務(wù)（記作QIO(write)）向郵箱發(fā)一個(gè)郵件，第二個(gè)QIO服務(wù)（記作QIO(read)）從郵箱讀一個(gè)郵件，mail為發(fā)出的郵件，buf為放置接收郵件的緩沖器。QIO(read)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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