協議工程之協議實現技術課件

第七章協議實現技術7.1概述

計算機網絡各層協議實現結果的集合形成計算機網絡軟件和硬件。計算機網絡軟件和計算機操作系統(tǒng)密切相關，它往往是操作系統(tǒng)的一部分，計算機網絡硬件和計算機硬件系統(tǒng)密切相關，它是計算機I/O系統(tǒng)的一部分。圖7.1為DEC公司的DNA在VAX/VMS中的實現結構。DNA（DigitalNetworkArchitecture）是DEC公司所采用的各層網絡協議的總稱，它在VAX/VMS之中實現后軟件和硬件的總稱為DECNET/VMS。第七章協議實現技術7.1概述第七章協議實現技術第七章協議實現技術第七章協議實現技術DNA的物理層和數據鏈路層協議實現于網絡適配器（deviceadaptor）中，DECnet/VMS包括許多網絡適配器，即DNA支持許多種低層通信協議。DNA的網絡層和傳輸層協議主要實現于偽驅動程序NETDRIVER中，它和網絡適配器的設備驅動程序(devicedriver)接口。DNA的高層協議以網絡目標模塊形式或實用程序的形式實現，DECnet/VMS包括許多這樣的目標模塊（object）和實用程序(utility)，這表示它向用戶提供豐富的網絡服務。這里，NETDRIVER和devicedriver是VMS內核一部分，DNA高層和VMS的文件系統(tǒng)，作業(yè)調度，用戶登陸（login）等密切聯系，網絡適配器是VAX硬件系統(tǒng)的一部分，計算機網絡各層協議在其它機器和操作系統(tǒng)中實現形式和實現結構都類似于DECnet/VMS。第七章協議實現技術DNA的物理層和數據鏈路層協議實現于網第七章協議實現技術計算機網絡協議是復雜的協議，將它們付諸實現更是一個復雜的技術過程，這是因為計算機網絡硬件和軟件與計算機硬件操作系統(tǒng)的關系非常密切的原故。一個計算機網絡的研制要經歷下述七步工作。(1)網絡體系結構的制定網絡體系結構（NetworkArchitecture）的制定包括許多決策工作：網絡支持哪些通訊線路和局域網？向用戶提供哪些網絡服務？網絡劃分成多少層？各層的協議功能是什么？各層協議規(guī)范和服務規(guī)范是什么？第七章協議實現技術計算機網絡協議是復雜的協第七章協議實現技術(2)實現環(huán)境的研究實現環(huán)境指計算機的機型和運行的操作系統(tǒng)。實現環(huán)境的研究是協議實現者必須進行的一項工作，這包括計算機硬件結構和I/O總線的詳細了解，操作系統(tǒng)結構和操作系統(tǒng)服務的詳細了解等等。(3)實現結構的設計在(1)和(2)的工作完成之后，協議設計者就可以著手網絡實現結構設計。實現結構的設計包括一系列的決策工作：哪幾層協議在網絡適配器中實現，哪幾層協議在操作系統(tǒng)中實現？操作系統(tǒng)的網絡軟件劃分成幾個進程，每個進程實現哪幾層協議？如果幾層協議在同一個進程實現時，各層協議之間怎樣相互調用？為了提高網絡軟件執(zhí)行效率和連接響應速度應采用哪些措施等等。第七章協議實現技術(2)實現環(huán)境的研究第七章協議實現技術(4)各層協議實體之間通訊機制設計當n層協議和(n-1)層協議在不同的進程或驅動程序之間實現時，n層協議實體和n-1層協議實體之間通訊必須借助操作系統(tǒng)服務來實現。當n層協議和(n-1)層協議在同一個進程或驅動程序之內實現時，兩層協議實體之間通訊可直接借助于程序設計語言(c,pascal)來實現。(5)數據緩沖方案的設計協議數據單元PDU(protocoldataunit)在各層協議實體之間的傳遞是通過緩沖器來實現的。數據緩沖方案的設計包括一系列的決策工作：緩沖器中的數據怎樣傳遞？是否采用共享緩沖器方案？緩沖器定義多大？緩沖器怎樣分配管理？緩沖器的分配管理怎樣對網絡流控制和交通擁塞控制施加影響等等。第七章協議實現技術(4)各層協議實體之間通訊機制設計第七章協議實現技術(6)各層協議代碼的產生協議代碼可分為兩部分：與實現環(huán)境相關的協議代碼和獨立于實現環(huán)境的協議代碼。前者必須由協議實現者手工完成，后者可手工完成也可以借助形式語言的編輯程序（如ESTELLEcompiler）自動產生。(7)網絡軟件的調試由于網絡軟件的分布性，異步性和實時性，傳統(tǒng)的靜態(tài)調試工具是不適應的，因此設計者必須研制多種動態(tài)調試工具以提高網絡軟件調試效率。這些調試工具包括各種模擬環(huán)境，閉環(huán)測試軟件，PDU追蹤，時間標簽，事件記錄等。第七章協議實現技術(6)各層協議代碼的產生第七章協議實現技術限于篇幅，本章只討論(4)、(5)、(6)步驟的有關問題，首先介紹協議代碼半自動生成技術，然后討論上下層協議實體之間通訊的實現方法，最后討論數據緩沖技術。如果我們掌握了第(4)和第(5)步的設計方法，那么與實現環(huán)境相關的協議代碼就可以手工完成了。計算機網絡研制工作中第（1）、（2）、（3）和（7）步工作的討論請參見文獻資料[42]和[34]。第七章協議實現技術限于篇幅，本章只討論(4第七章協議實現技術7.2協議代碼半自動生成技術

協議代碼半自動生成技術試圖將協議規(guī)范文本（用ESTELLE、LOTOS等語言描述)直接轉換成協議代碼（c.pascal等程序設計語言）。如果所產生的代碼不需要人工修改就可以編譯成機器可執(zhí)行的程序，這是最理想的。但由于計算機網絡軟件和操作系統(tǒng)結合緊密，這實際上是不現實的。由協議規(guī)范直接轉換的協議代碼只能占全部代碼的一部分，約50%左右[33]，這部分代碼稱之為獨立于實現環(huán)境的代碼，另外一部分代碼由于和實現環(huán)境相關，必須由手工完成。協議代碼的這種生成方法稱之為協議代碼的半自動生成技術。關于協議代碼半自動生成技術是否值得深入研究的問題，人們尚有不同的看法。然而，半自動生成技術顯然有如下一些好處：第七章協議實現技術7.2協議代碼半自動生成技術第七章協議實現技術（1）利用同一個翻譯程序從同一個協議規(guī)范中產生的協議代碼總是一致的，它不隨協議實現者的不同而不同。這就是說，所有協議實現者都能夠獲得一份相同的協議代碼。雖然這一部分協議代碼只占總代碼的50%左右，但它包括協議的主體部分。它確定了協議的所有邏輯關系，因此它為協議的不同實現版本的互連提供了良好的基礎。（2）協議規(guī)范的更新修改不會給協議實現者帶來太多的麻煩，它只要重新運行一次翻譯程序就可以了。（3）由此減少手工編程的錯誤，縮短網絡軟件的開發(fā)周期，提高網絡軟件可維護性。第七章協議實現技術（1）利用同一個翻譯程序從同一個協議規(guī)范第七章協議實現技術

目前，世界上已開發(fā)了多種協議代碼半生成軟件，它們大都基于ESTELLE，LOTOS和SDL語言，翻譯后的協議代碼大都為C代碼。下面簡單介紹EDS（EstelleDevelopmentSystem）中協議代碼半自動生成的基本過程[33]，它將協議代碼半自動生成過程分為四步。第七章協議實現技術目前，世界上已開發(fā)了多種ESTELLE半自動生成過程可用圖7.2表示，圖中.e表示類型為.e的文件，.m表示類型為.m文件······。fESTELLE半自動生成過程可用圖7.2表第七章協議實現技術1.協議規(guī)范的預處理用形式描述語言描述的協議規(guī)范中往往存在許多沒有具體數值的符號定義。例如用ESTELLE描述的AB協議中（參見第四章4.2.4)，常數low,high,retran-time未給出具體數值，預處理要求實現者給出具體數值。又例如，在ESTELLE:描述的AB協議中，數據類型定義U一data一type是含糊的(它用······表示)，這要求協議實現者給出它的具體定義（如定義為stringofcharacters）。預處理要做的工作包括原語primitive的標識等工作。預處理的第二項重要工作是將協議規(guī)范文本(.e)分割成三個文件：模塊描述文件(.m)，實現描述文件(.i)和格式描述文件(.f)。模塊描述文件即為原協議規(guī)范中的模塊頭定義和模塊體定義。實現描述文件將原協議規(guī)范中有關各模塊的性質定義，模塊之間組織關系描述，模塊之間通訊機制描述等全局性內容抽取出來，形成一個描述整個協議的框架文件。格式描述文件完整地描述模塊之間報文交換的格式，它也是從原協議規(guī)范文件中抽出來的。第七章協議實現技術1.協議規(guī)范的預處理第七章協議實現技術2.翻譯預處理后的協議規(guī)范直接送入ESTELLEcompiler翻譯，翻譯包括語法校對、C代碼生成等工作。對模塊體文件，翻譯結果是對應于每一個ESTELLE模塊體產生一個C代碼的模塊頭文件(headfile)和一個C代碼的模塊體文件(bodyfile)。模塊頭文件包含模塊體內所有數據結構和變量（如交互點ip和ep、隊列等）。模塊體文件包含模塊體內所有函數、過程的代碼，除模塊體原有的函數和過程定義之外，模塊體的每一個轉換都翻譯成過程。第七章協議實現技術2.翻譯第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術3.手工程序的編寫凡是與系統(tǒng)相關的部分（通訊機制、緩沖器管理、文件訪問、訪問控制等等)必須由協議實現者根據實現環(huán)境手工編寫。4.執(zhí)行代瑪的產生上述所有C程序文件編譯后鏈接成一個或幾個系統(tǒng)可執(zhí)行的文件，每個可執(zhí)行的文件對應于一個進程或用戶啟動的實用程序。第七章協議實現技術3.手工程序的編寫第七章協議實現技術7.3模塊通訊的實現方法

ESTELLE模塊之間的通訊的實現很大程度上依賴于操作系統(tǒng)所提供的服務。在VAX/VMS環(huán)境中，如果兩個模塊體分別用兩個進程實現，那么VMS所提供的進程通訊服務就成為模塊通訊實現的基礎。VAX/VMS提供的進程通訊機制包括郵箱、共享存貯區(qū)、事件、共享文件，其中郵箱是常用的通訊方法。第七章協議實現技術7.3模塊通訊的實現方法第七章協議實現技術郵箱是VMS的一種偽設備，用戶程序通過標準的QIO服務就可以讀寫郵箱。郵箱名是系統(tǒng)邏輯符號，為所有進程所認識。當多個進程對名字相同的郵箱進行讀寫時，它們實際上就進行通訊。下面列出有關郵箱服務和c語言調用。（1）定義郵箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name為放置郵箱名字符串MBX_NAME的變量。第七章協議實現技術郵箱是VMS的一種偽設備，用戶程序通過標第七章協議實現技術(2)定義郵箱通道

intmbx_ch; mbx_ch為32位的長字，它放置郵箱通道號。(3)創(chuàng)建郵箱通道

sys$crembx(1,&mbx_ch,0,0,0,0,&mbx_name); VMS系統(tǒng)服務crembx創(chuàng)建一個郵箱（如果該郵箱不存在），并賦于一個通道號，&表示傳遞變量的地址值。第七章協議實現技術(2)定義郵箱通道第七章協議實現技術(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)可以通過AST(AsyncTrap)形成異步地進行（類似中斷方式），這給用戶程序的設計帶來很多好處。(5)取消郵箱sys$delmbx(mbx_ch);切斷用戶程序和郵箱之間建立的通路。第七章協議實現技術(4)QIO操作第七章協議實現技術熟悉了VMS郵箱的使用方法，我們就很容易找到怎樣實現ESTELLE模塊之間通訊的實現途徑。下面簡述郵箱服務和ESTELLE模塊通訊語句之間對應關系。(1)channel定義 一個channel對應一個VMS郵箱，channel名用$DESCRIPTOR來說明，channel定義中交互用過程表示，每個過程負責向郵箱發(fā)出一個郵件，郵件內容包括交互名和傳遞的參數。下面的例子說明AB協議channelN-access-point定義翻譯成C語言的情況第七章協議實現技術熟悉了VMS郵箱的使用方法，我們就很容易第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術7.4數據緩沖技術

協議數據單元(PDU)在機器中的存貯以及上下層協議實體之間的傳遞是通過緩沖器來實現的，因此緩沖器的使用、分配和管理成為協議實現中關鍵技術之一。數據緩沖技術涉及三個問題：存貯空間的利用率，對協議執(zhí)行速度的影響，對協議機制和網絡性能的影響。(1)存貯空間利用率協議數據單元的大小不是固定的，小到幾個字節(jié)，大到數千個字節(jié)。如果按最大的單元固定劃分緩沖器，對于小報文，存貯空間利用率很低。一個網絡中總是存在許多用戶，在多用戶情況下，一個機器中的邏輯鏈路數是隨用戶而動態(tài)變化的。如果按照最大用戶數給每條邏輯鏈路分配固定的緩沖器，那么在用戶少的情況下，存貯空間浪費較大。第七章協議實現技術7.4數據緩沖技術第七章協議實現技術(2)協議執(zhí)行速度協議數據單元在上下層的傳遞可采用兩種方法：緩沖器指針傳遞法和緩沖器復制法。很顯然，前者的額外開銷小，協議執(zhí)行速度高。問題(l)和(2)是有矛盾的。為了提高存貯空間利用率，緩沖器長度設定要小，但對于大數據單元則需要多個緩沖器來容納，多個緩沖器容納一個數據單元的處理將給軟件帶來許多麻煩。(3)協議機制和網絡性能緩沖器是網絡的最重要的資源，許多協議機制的執(zhí)行依賴于緩沖器的可用度。例如，傳輸層在實行窗口流控制時，發(fā)送窗口的寬度是由對方的接收能力決定的（主要是可用的緩沖器的數口）。對于有路由功能的網絡層協議實體來說，緩沖器的分配管理算法與網絡擁塞控制策略和死鎖防止方法密切相關。第七章協議實現技術(2)協議執(zhí)行速度第七章協議實現技術7.4.1緩沖器指針傳遞方法數據單元在上下層協議實體之間的傳遞采用緩沖器指針傳遞方法時所要解決的一個重要問題是數據單元的分段與合段。例如，當會晤層的一個協議數據單元SPDU(sessionprotocoldataunit)用指針傳遞方法送給傳輸層協議實體后，可能要將它分成三段，即一個TSDU變成三個TPDU(transportprotocoldataunit)，這里的TSDU(transportservicedataunit)就是SPDU。由于傳輸層必須給每段數據添加一個傳輸層報文頭TH(transporthead)，因此除第一個TPDU之后，后兩個TPDU的形成都避免不了數據的復制，圖7.3示出這一個過程。圖7.3數據分段引起數據復制第七章協議實現技術7.4.1緩沖器指針傳遞方法圖7.3數第七章協議實現技術為了解決分段引起的數據復制，我們可以采用這樣的一種方法：如果設傳輸層允許的TPDU最大長度為l，它的報文頭TH最大長度為n，那么會晤層可使用長度為l的多個緩沖器，將一個SPDU分割成多個長度小于（l-n）的段分別放在不同的緩沖器中，然后將緩沖器鏈傳遞給傳輸層，圖7.4示出緩沖器鏈傳遞方法。圖7.4緩沖器鏈傳遞第七章協議實現技術為了解決分段引起的數據復制，我們可以采用第七章協議實現技術上述方法仍然有一個缺點，即會晤層交給傳輸層的緩沖器，其頭部必須留足夠的空間以便傳輸層（還包括網絡層及底層）填寫它的報文頭。這樣不但存儲空間有浪費，而且緩沖器指針要隨報文頭的添加數而修改。圖7.5所示的方法中，各層協議頭使用專門的小緩沖器，用戶數據分放在多個大緩沖器中。圖7.5用戶數據和報文頭分別用不同的緩沖器第七章協議實現技術上述方法仍然有一個缺點，即會晤層交給傳輸第七章協議實現技術7.4.2共享緩沖區(qū)的分配和管理為了提高存儲空間的利用率，人們往往采用共享緩沖器的方法。圖7.6為共享緩沖區(qū)示意圖。傳輸層提供n條邏輯鏈路服務，每個應用層協議實體（如a,b,c）通過表示層協議實體P和會晤層協議實體S使用一條邏輯鏈路。N條邏輯鏈路共享發(fā)送緩沖區(qū).

例如當應用層實體a要發(fā)送一個報文時，它從發(fā)送緩沖區(qū)獲取一個或多個緩沖器，然后將裝載報文的緩沖鏈逐層傳遞給P層，S層，傳輸層和網絡層。網絡層將報文從指定通訊網絡或線路發(fā)出之后，將空緩沖器歸給發(fā)送緩沖區(qū)。接收緩沖區(qū)向各個通訊網絡端口或點對點線路端口提供接收緩沖器。裝填有接收報文的緩沖器首先由網絡層處理，網絡層或將緩沖器上交傳輸層處理（如果報文的目的地址是本地地址），或將緩沖器交給另外的通訊網絡端口轉發(fā)（如果報文的目的地址不是本地結點），或將緩沖器歸還給接收緩沖區(qū)（如果報文是網絡層報文）。第七章協議實現技術7.4.2共享緩沖區(qū)的分配和管理圖7.6共享緩沖區(qū)圖7.6共享緩沖區(qū)第七章協議實現技術共享緩沖區(qū)固然可以提高存儲空間利用率，但如果沒有合理的分配管理算法，將帶來嚴重的副作用。第一個嚴重的副作用是緩沖器的枯竭。當某條邏輯鏈路通訊流量特別大時，它可能獨占所有發(fā)送緩沖器，以致其它應用層協議實體不能獲得緩沖器，造成緩沖器枯竭現象。第二個嚴重的副作用是不合理的接收緩沖器分配管理算法將會造成網絡死鎖現象。第七章協議實現技術共享緩沖區(qū)固然可以提高存儲空間利用率，但第七章協議實現技術

本節(jié)討論緩沖器的公平分配問題，下節(jié)討論接收緩沖器分配管理與網絡性能的關系。對于發(fā)送緩沖器，最常用的分配算法是平方根法。設發(fā)送緩沖區(qū)所能提供的緩沖器數目為B，當前活躍的邏輯鏈路數為n，那么每條鏈路所能占用的發(fā)送緩沖器的最高限額不應大于B/。對于接收緩沖器，緩沖器的占用者的概念不同于發(fā)送緩沖器。當一個通訊子網接收一個報文，并將報文放入緩沖器之后并不能立刻確定該緩沖器由誰占用。裝填接收報文的緩沖器經由網絡層處理之后，報文的占用者就確定了第七章協議實現技術本節(jié)討論緩沖器的公平分配問題第七章協議實現技術

例如，當圖7.6中的net1收到一個報文并將緩沖器交網絡層之后；網絡層處理該報文，如果該報文向net2轉發(fā)，那么緩沖器占用者是net2；如果該報文上交傳輸層，那么緩沖器的占用者是本地結點。這樣，如果網絡層有路由功能，并且它支持m路輸出線路（通訊子網端口），那么接收緩沖器要在m+1個對象中分配；如果網絡層沒有路由功能，那么所有接收緩沖區(qū)都歸本地結點所有。如果本地結點當前有n條活躍邏輯鏈路，那么對于分配給本地結點的那份接收緩沖器再按n個對象分配（或平均分配，或按平方根分配）。第七章協議實現技術例如，當圖7.6中的net1第七章協議實現技術7.4.3接收緩沖器的分配管理如果網絡層有路由功能，那么接收緩沖區(qū)的分配管理算法就比較復雜，不合理的分配算法還將產生死鎖等副作用。下面分別討論三個副作用及解決辦法。1.直接死鎖（directdeadlock）假定接收緩沖區(qū)的分配是任意的，即每一條輸出線路端口可以占用任意多緩沖器，直至接收緩沖區(qū)枯竭為止，那么圖7.7所示的直接死鎖現象就可能出現。圖中，由于結點A的所有接收緩沖器已被端口a所占用，它不能再接收b的報文，而B的所有緩沖器已被端口b所占用，它也不能接收A發(fā)出的報文，死鎖發(fā)生！直接死鎖產生的原因是雙方接收緩沖區(qū)同時枯竭，解決的辦法是避免接收緩沖區(qū)枯竭。假定結點的接收緩沖區(qū)的緩沖器總數為C，對于有m條輸出線路（端口）同時活躍的情況，各條輸出線路所能占用的接收緩沖器限額應小于Ct=C/（m+1），本地結點看作一路輸出，它所分配的限額也為Ct。按照這種平均法則分配接收緩沖器枯竭現象永不會發(fā)生，直接死鎖就消除了。第七章協議實現技術7.4.3接收緩沖器的分配管理第七章協議實現技術圖7.7直接死鎖第七章協議實現技術圖7.7直接死鎖第七章協議實現技術2.間接死鎖（indirectdeadlock）即便是對輸出線路所占用的緩沖器進行限制圖7.8所示的死鎖還可能發(fā)生。這種由多個結點的輸出隊列所形成的環(huán)路死鎖稱為間接死鎖。間接死鎖發(fā)生時各個結點的接收緩沖區(qū)并沒有枯竭。圖7.8中，A中的輸出線路a的所有報文的目的地址不是B，但必須經過B的端口b轉發(fā)，由于b的輸出隊列長度已經達到限額，B無法接收A發(fā)來的必須經過端口b轉發(fā)的報文。由于同樣情況，C無法接收B發(fā)來的必須經端口c轉發(fā)的報文，D無法接收C發(fā)來的必須經端口d轉發(fā)的報文，A無法接收D發(fā)來必須經端口a轉發(fā)的報文，死鎖發(fā)生！第七章協議實現技術2.間接死鎖（indirectdead第七章協議實現技術圖7.8間接死鎖第七章協議實現技術圖7.8間接死鎖第七章協議實現技術間接死鎖的解決辦法之一基于分類報文概念。網絡層處理輸入報文時按照一定的分類方法將它們分成不同類別的報文，給每個報文打上類別標記，并按照報文類別分配接收緩沖器的限額。報文分類的第一種方法是按照輸出線路進行。例如，假如某結點有三條輸出線路a，b，c，當網絡層處理報文時發(fā)現報文需經線路a轉發(fā)，那么它的類別為a;經b轉發(fā)，它的類別就為b。這是最簡單的分類法，但不能解決間接死鎖問題。第七章協議實現技術間接死鎖的解決辦法之一基第七章協議實現技術

報文分類的第二種方法是按照報文已走過的鏈路數或到達目的結點之前還需走過的鏈路數進行，前者稱之為后向鏈分類法，后者稱之為前向分類法。按照前向鏈分類法，到達目的結點之前還要走n條鏈路的報文為n類報文，n類報文邏輯上放入n隊列。1類報文的目的結點就是鄰近結點。按照這種方法對報文分類從根本上消除了圖7.8所示的輸入隊列環(huán)路，因此不會發(fā)生間接死鎖。圖7.9中，各個輸出端口邏輯上有三個隊列q1，q2，q3。q1放1類報文（到達目的結點的鏈路數為1），q2放2類報文，q3放3類報文。當圖7.8所示的情況出現時（各個結點的q2的長度已到達限額），死鎖不會出現，這是因為B能接收A從q2發(fā)出的報文，并將報文放入B的q1隊列（A中的2類報文到達B后變成1類報文）。如果假定B的q1隊列也已到達限額，但由于B將q1隊列中的報文發(fā)往C之后，C總是能接收目的結點就是C的報文（B的q1隊列很快就會倒空）死鎖就不會出現。第七章協議實現技術報文分類的第二種方法是第七章協議實現技術圖7.9前向鏈分類法第七章協議實現技術圖7.9前向鏈分類法第七章協議實現技術3.交通流量控制接收緩沖區(qū)的分配管理與網絡報文流量控制有關，或者說某些交通流量控制算法是通過接收緩沖器的分配管理來實現的。其中最常用的做法是對不同類別的報文實行優(yōu)先級別控制（優(yōu)先界別高的報文可獲得多的接收緩沖器），以提高網絡流通量，減少交通堵塞發(fā)生率。例如，當采用前向鏈分類法時，如果使類別低的報文優(yōu)先級別高（即1類報文優(yōu)先于2類報文）就能使接近于目的結點報文盡快離開網絡，避免交通堵塞。第七章協議實現技術3.交通流量控制第七章協議實現技術7.5協議并行處理技術隨著數據通訊速率的提高，計算機網絡各層協議的執(zhí)行速度也必須提高。例如，當數據傳輸速率為1Gbps（1000Mbps）時，如果傳輸層的平均報文長度為128字節(jié)，那么它每秒要處理一百萬個報文。如果每個報文的處理要花費50條指令（不包括CRC校驗），那么傳輸層協議處理器的速度應大于50Mips。如果傳輸層報文包含CRC碼，處理器速度要更高（約100Mips）。MIPS-------MillionInstructionsPerSecond每秒百萬條指令第七章協議實現技術7.5協議并行處理技術第七章協議實現技術提高協議執(zhí)行速度的辦法之一是協議并行處理技術，即用多個CPU并行執(zhí)行某層協議。文獻【14】以傳輸層協議為例，定義了三種粒度（grains）不同的協議并行處理;粗粒度（coarsegrain）并行，中粒度（mediumgrain）并行和細粒度（finegrain）并行。

按粗粒度并行處理協議時，協議實體按功能劃分成多個任務，各個任務分配給不同的CPU處理。例如，傳輸層協議可劃分成聯接處理，數據接收處理。數據發(fā)送處理等多個任務。如果協議功能劃分更細一點（如圖3.16描述的ISOTP4數據發(fā)送模型那樣），這些任務可分配給更多的CPU執(zhí)行。第七章協議實現技術提高協議執(zhí)行速度的辦法之第七章協議實現技術

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

按細粒度并行處理協議時。多個處理器同時處理一個報文。例如，多個處理器同時分析處理一個報文頭時，每個處理器分析報文頭的一個字段。第七章協議實現技術按中較度并行處理協議時，第七章協議實現技術粗粒度并行處理易于實現，這是因為各個任務界限清晰，相關性小。但粗粒度并行度小，速度提高有限。細粒度可獲得很高并行度，但實現困難。中粒度并行處理技術兼有兩者優(yōu)點，值得人們深人研究。第七章協議實現技術粗粒度并行處理易于實現，這是因為各個任務第七章協議實現技術作為例子，圖7.10示出傳輸層報文發(fā)送的并行模型，圖7.11示出傳輸層報文接收的并行模型。圖7.10中，會晤層交給傳輸層的報文流（TSDU流）按輪循法則分配繪m個處理器（P1，P2，……，Pm），并放在各個處理器的局部存貯器隊列（q1，12，……qm）中。報文發(fā)出之后，它進入Rctran隊列。由處理器R負責報文的重發(fā)。圖7.11中，網絡層交給傳輸層的輸人報文流（TPDU流）按輪循的方法分配給n個處理器（P1，P2，……，Pn），并放在各個處理器的局部存貯器隊列（q1，q2，……qn）中。正確的報文收到之后產生一個ACK信息放人ACK隊列。處理器Q專門負責發(fā)送入ACK報文。圖7.10和圖7.11只是一個傳輸層協議并行處理的模型，將它們付諸實現還必須解決以下一些問題。第七章協議實現技術作為例子，圖7.10示出圖7.10傳輸層報文發(fā)送并行模型圖7.11傳輸層報文接收并行模型第七章協議實現技術圖7.10傳輸層報文發(fā)送并行模型第七章協議實現技術1．發(fā)送窗口問題RTD（RoundTimeDelay）指報文從一個傳愉層協議實體到另外一個傳愉層協議實體之間來回傳送一次的延遲時問，它是傳愉層窗口流控制的重要參數。當兩臺機器距1000千米時，RTD近似于10ms。在數據傳輸1Gbps時，一個長度為512字節(jié)的報文只需4us傳送時間，這意味著發(fā)送方可在RTD=10ms時間內連續(xù)發(fā)生2500個報文。如果要最大限度地利用高速數據信道，那么發(fā)送窗口應大于2500。第七章協議實現技術1．發(fā)送窗口問題第七章協議實現技術如此大的發(fā)送窗口會帶來什么問題呢?首先，傳輸層協議實休必須要有足夠的存貯空間容納2500個報文，在認可報文來到之前，它們都停留在Retran隊列中。其次每個報文設置一個超時時鐘。那么傳愉層需要2500個定時器口如果超時時間設定為1ms，每個超時時鐘要耗費3條指令，那么專門負責定時器的處理器的速度必須大于10Mips。另外一個問題，按照傳輸層協議，如界某個報文有錯，它后面的所有報文都重發(fā)（極端下，2500個報文都重發(fā)，這將大大降低信道的利用率。第七章協議實現技術如此大的發(fā)送窗口會帶來什么問題呢?第七章協議實現技術2．報文處理時間差異問題雖然報文按輪詢方法分配給各個處理器，但由于報文內容的差異，報文處理時間長度差異就會很大（例如，連接報文的處理時間比正常數據報文的處理時間就會大很多；錯誤報文的處理時間就比正常報文的處理時間常）。處理時間的差異必定產生后到報文處理的現象，例如順序號大的數據報文先于順序號小的數據報文處理，斷聯報文的處理先于最后數據報文的處理等等。數據傳輸要求很好的順序，如果順序有混亂，傳輸層協議認為是一種錯誤。那么在協議并行處理時，怎樣判定數據傳輸順序有錯還是報文處理時間差異呢？第七章協議實現技術2．報文處理時間差異問題第七章協議實現技術3．聯接數據塊的共享問題對于每一條聯接傳輸層實體的共享區(qū)中都存在一個聯接數據塊。聯接數據塊包含有關聯接的所有信息，如源地址，目的地址，聯接標識號，聯接狀態(tài)，發(fā)送窗口寬度，下一個待接收報文的順序號等等。當多個處理器同時處理同一條聯接的不同報文時，它們必然要訪問聯接數據塊，這就可能引起存貯訪問沖突問題。這里，數據一致性是最重要的問題。例如，當每個處理器處理完順序號為11的輸人報文之后，‘它將下一個待接收報文的順序號置成12，如果另外一個處理器晚處理順序號為10的報文，那么它就會將下一個待接收報文的順序號改變成11。這就引起順序號的混亂。聯接數據塊共享還會降低處理速度。第七章協議實現技術3．聯接數據塊的共享問題第七章協議實現技術

上述問題的解決要從兩方面著手，第一是研究更好的并行處理模型。第二是研究適合于并行處理的協議。上面的同題反映出，現在的傳輸層協議不適合于并行處理，例如它過份強調數據傳輸的順序性;不適應大窗流量控制，重發(fā)機制效率低（一個報文出錯，它后面所有報文重發(fā)），無發(fā)送速串控制，報文頭長度可變等等。為此。人們提出了一些適合于高速計算機網絡以及并行處理的傳輸層協議，如XTP（eXpressTrarsportProtocol}，RGP（ReliaGramtransportProtocol）等等。第七章協議實現技術上述問題的解決要從兩方面第七章協議實現技術7.1概述

計算機網絡各層協議實現結果的集合形成計算機網絡軟件和硬件。計算機網絡軟件和計算機操作系統(tǒng)密切相關，它往往是操作系統(tǒng)的一部分，計算機網絡硬件和計算機硬件系統(tǒng)密切相關，它是計算機I/O系統(tǒng)的一部分。圖7.1為DEC公司的DNA在VAX/VMS中的實現結構。DNA（DigitalNetworkArchitecture）是DEC公司所采用的各層網絡協議的總稱，它在VAX/VMS之中實現后軟件和硬件的總稱為DECNET/VMS。第七章協議實現技術7.1概述第七章協議實現技術第七章協議實現技術第七章協議實現技術DNA的物理層和數據鏈路層協議實現于網絡適配器（deviceadaptor）中，DECnet/VMS包括許多網絡適配器，即DNA支持許多種低層通信協議。DNA的網絡層和傳輸層協議主要實現于偽驅動程序NETDRIVER中，它和網絡適配器的設備驅動程序(devicedriver)接口。DNA的高層協議以網絡目標模塊形式或實用程序的形式實現，DECnet/VMS包括許多這樣的目標模塊（object）和實用程序(utility)，這表示它向用戶提供豐富的網絡服務。這里，NETDRIVER和devicedriver是VMS內核一部分，DNA高層和VMS的文件系統(tǒng)，作業(yè)調度，用戶登陸（login）等密切聯系，網絡適配器是VAX硬件系統(tǒng)的一部分，計算機網絡各層協議在其它機器和操作系統(tǒng)中實現形式和實現結構都類似于DECnet/VMS。第七章協議實現技術DNA的物理層和數據鏈路層協議實現于網第七章協議實現技術計算機網絡協議是復雜的協議，將它們付諸實現更是一個復雜的技術過程，這是因為計算機網絡硬件和軟件與計算機硬件操作系統(tǒng)的關系非常密切的原故。一個計算機網絡的研制要經歷下述七步工作。(1)網絡體系結構的制定網絡體系結構（NetworkArchitecture）的制定包括許多決策工作：網絡支持哪些通訊線路和局域網？向用戶提供哪些網絡服務？網絡劃分成多少層？各層的協議功能是什么？各層協議規(guī)范和服務規(guī)范是什么？第七章協議實現技術計算機網絡協議是復雜的協第七章協議實現技術(2)實現環(huán)境的研究實現環(huán)境指計算機的機型和運行的操作系統(tǒng)。實現環(huán)境的研究是協議實現者必須進行的一項工作，這包括計算機硬件結構和I/O總線的詳細了解，操作系統(tǒng)結構和操作系統(tǒng)服務的詳細了解等等。(3)實現結構的設計在(1)和(2)的工作完成之后，協議設計者就可以著手網絡實現結構設計。實現結構的設計包括一系列的決策工作：哪幾層協議在網絡適配器中實現，哪幾層協議在操作系統(tǒng)中實現？操作系統(tǒng)的網絡軟件劃分成幾個進程，每個進程實現哪幾層協議？如果幾層協議在同一個進程實現時，各層協議之間怎樣相互調用？為了提高網絡軟件執(zhí)行效率和連接響應速度應采用哪些措施等等。第七章協議實現技術(2)實現環(huán)境的研究第七章協議實現技術(4)各層協議實體之間通訊機制設計當n層協議和(n-1)層協議在不同的進程或驅動程序之間實現時，n層協議實體和n-1層協議實體之間通訊必須借助操作系統(tǒng)服務來實現。當n層協議和(n-1)層協議在同一個進程或驅動程序之內實現時，兩層協議實體之間通訊可直接借助于程序設計語言(c,pascal)來實現。(5)數據緩沖方案的設計協議數據單元PDU(protocoldataunit)在各層協議實體之間的傳遞是通過緩沖器來實現的。數據緩沖方案的設計包括一系列的決策工作：緩沖器中的數據怎樣傳遞？是否采用共享緩沖器方案？緩沖器定義多大？緩沖器怎樣分配管理？緩沖器的分配管理怎樣對網絡流控制和交通擁塞控制施加影響等等。第七章協議實現技術(4)各層協議實體之間通訊機制設計第七章協議實現技術(6)各層協議代碼的產生協議代碼可分為兩部分：與實現環(huán)境相關的協議代碼和獨立于實現環(huán)境的協議代碼。前者必須由協議實現者手工完成，后者可手工完成也可以借助形式語言的編輯程序（如ESTELLEcompiler）自動產生。(7)網絡軟件的調試由于網絡軟件的分布性，異步性和實時性，傳統(tǒng)的靜態(tài)調試工具是不適應的，因此設計者必須研制多種動態(tài)調試工具以提高網絡軟件調試效率。這些調試工具包括各種模擬環(huán)境，閉環(huán)測試軟件，PDU追蹤，時間標簽，事件記錄等。第七章協議實現技術(6)各層協議代碼的產生第七章協議實現技術限于篇幅，本章只討論(4)、(5)、(6)步驟的有關問題，首先介紹協議代碼半自動生成技術，然后討論上下層協議實體之間通訊的實現方法，最后討論數據緩沖技術。如果我們掌握了第(4)和第(5)步的設計方法，那么與實現環(huán)境相關的協議代碼就可以手工完成了。計算機網絡研制工作中第（1）、（2）、（3）和（7）步工作的討論請參見文獻資料[42]和[34]。第七章協議實現技術限于篇幅，本章只討論(4第七章協議實現技術7.2協議代碼半自動生成技術

協議代碼半自動生成技術試圖將協議規(guī)范文本（用ESTELLE、LOTOS等語言描述)直接轉換成協議代碼（c.pascal等程序設計語言）。如果所產生的代碼不需要人工修改就可以編譯成機器可執(zhí)行的程序，這是最理想的。但由于計算機網絡軟件和操作系統(tǒng)結合緊密，這實際上是不現實的。由協議規(guī)范直接轉換的協議代碼只能占全部代碼的一部分，約50%左右[33]，這部分代碼稱之為獨立于實現環(huán)境的代碼，另外一部分代碼由于和實現環(huán)境相關，必須由手工完成。協議代碼的這種生成方法稱之為協議代碼的半自動生成技術。關于協議代碼半自動生成技術是否值得深入研究的問題，人們尚有不同的看法。然而，半自動生成技術顯然有如下一些好處：第七章協議實現技術7.2協議代碼半自動生成技術第七章協議實現技術（1）利用同一個翻譯程序從同一個協議規(guī)范中產生的協議代碼總是一致的，它不隨協議實現者的不同而不同。這就是說，所有協議實現者都能夠獲得一份相同的協議代碼。雖然這一部分協議代碼只占總代碼的50%左右，但它包括協議的主體部分。它確定了協議的所有邏輯關系，因此它為協議的不同實現版本的互連提供了良好的基礎。（2）協議規(guī)范的更新修改不會給協議實現者帶來太多的麻煩，它只要重新運行一次翻譯程序就可以了。（3）由此減少手工編程的錯誤，縮短網絡軟件的開發(fā)周期，提高網絡軟件可維護性。第七章協議實現技術（1）利用同一個翻譯程序從同一個協議規(guī)范第七章協議實現技術

目前，世界上已開發(fā)了多種協議代碼半生成軟件，它們大都基于ESTELLE，LOTOS和SDL語言，翻譯后的協議代碼大都為C代碼。下面簡單介紹EDS（EstelleDevelopmentSystem）中協議代碼半自動生成的基本過程[33]，它將協議代碼半自動生成過程分為四步。第七章協議實現技術目前，世界上已開發(fā)了多種ESTELLE半自動生成過程可用圖7.2表示，圖中.e表示類型為.e的文件，.m表示類型為.m文件······。fESTELLE半自動生成過程可用圖7.2表第七章協議實現技術1.協議規(guī)范的預處理用形式描述語言描述的協議規(guī)范中往往存在許多沒有具體數值的符號定義。例如用ESTELLE描述的AB協議中（參見第四章4.2.4)，常數low,high,retran-time未給出具體數值，預處理要求實現者給出具體數值。又例如，在ESTELLE:描述的AB協議中，數據類型定義U一data一type是含糊的(它用······表示)，這要求協議實現者給出它的具體定義（如定義為stringofcharacters）。預處理要做的工作包括原語primitive的標識等工作。預處理的第二項重要工作是將協議規(guī)范文本(.e)分割成三個文件：模塊描述文件(.m)，實現描述文件(.i)和格式描述文件(.f)。模塊描述文件即為原協議規(guī)范中的模塊頭定義和模塊體定義。實現描述文件將原協議規(guī)范中有關各模塊的性質定義，模塊之間組織關系描述，模塊之間通訊機制描述等全局性內容抽取出來，形成一個描述整個協議的框架文件。格式描述文件完整地描述模塊之間報文交換的格式，它也是從原協議規(guī)范文件中抽出來的。第七章協議實現技術1.協議規(guī)范的預處理第七章協議實現技術2.翻譯預處理后的協議規(guī)范直接送入ESTELLEcompiler翻譯，翻譯包括語法校對、C代碼生成等工作。對模塊體文件，翻譯結果是對應于每一個ESTELLE模塊體產生一個C代碼的模塊頭文件(headfile)和一個C代碼的模塊體文件(bodyfile)。模塊頭文件包含模塊體內所有數據結構和變量（如交互點ip和ep、隊列等）。模塊體文件包含模塊體內所有函數、過程的代碼，除模塊體原有的函數和過程定義之外，模塊體的每一個轉換都翻譯成過程。第七章協議實現技術2.翻譯第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術3.手工程序的編寫凡是與系統(tǒng)相關的部分（通訊機制、緩沖器管理、文件訪問、訪問控制等等)必須由協議實現者根據實現環(huán)境手工編寫。4.執(zhí)行代瑪的產生上述所有C程序文件編譯后鏈接成一個或幾個系統(tǒng)可執(zhí)行的文件，每個可執(zhí)行的文件對應于一個進程或用戶啟動的實用程序。第七章協議實現技術3.手工程序的編寫第七章協議實現技術7.3模塊通訊的實現方法

ESTELLE模塊之間的通訊的實現很大程度上依賴于操作系統(tǒng)所提供的服務。在VAX/VMS環(huán)境中，如果兩個模塊體分別用兩個進程實現，那么VMS所提供的進程通訊服務就成為模塊通訊實現的基礎。VAX/VMS提供的進程通訊機制包括郵箱、共享存貯區(qū)、事件、共享文件，其中郵箱是常用的通訊方法。第七章協議實現技術7.3模塊通訊的實現方法第七章協議實現技術郵箱是VMS的一種偽設備，用戶程序通過標準的QIO服務就可以讀寫郵箱。郵箱名是系統(tǒng)邏輯符號，為所有進程所認識。當多個進程對名字相同的郵箱進行讀寫時，它們實際上就進行通訊。下面列出有關郵箱服務和c語言調用。（1）定義郵箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name為放置郵箱名字符串MBX_NAME的變量。第七章協議實現技術郵箱是VMS的一種偽設備，用戶程序通過標第七章協議實現技術(2)定義郵箱通道

intmbx_ch; mbx_ch為32位的長字，它放置郵箱通道號。(3)創(chuàng)建郵箱通道

sys$crembx(1,&mbx_ch,0,0,0,0,&mbx_name); VMS系統(tǒng)服務crembx創(chuàng)建一個郵箱（如果該郵箱不存在），并賦于一個通道號，&表示傳遞變量的地址值。第七章協議實現技術(2)定義郵箱通道第七章協議實現技術(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)可以通過AST(AsyncTrap)形成異步地進行（類似中斷方式），這給用戶程序的設計帶來很多好處。(5)取消郵箱sys$delmbx(mbx_ch);切斷用戶程序和郵箱之間建立的通路。第七章協議實現技術(4)QIO操作第七章協議實現技術熟悉了VMS郵箱的使用方法，我們就很容易找到怎樣實現ESTELLE模塊之間通訊的實現途徑。下面簡述郵箱服務和ESTELLE模塊通訊語句之間對應關系。(1)channel定義 一個channel對應一個VMS郵箱，channel名用$DESCRIPTOR來說明，channel定義中交互用過程表示，每個過程負責向郵箱發(fā)出一個郵件，郵件內容包括交互名和傳遞的參數。下面的例子說明AB協議channelN-access-point定義翻譯成C語言的情況第七章協議實現技術熟悉了VMS郵箱的使用方法，我們就很容易第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術第七章協議實現技術7.4數據緩沖技術

協議數據單元(PDU)在機器中的存貯以及上下層協議實體之間的傳遞是通過緩沖器來實現的，因此緩沖器的使用、分配和管理成為協議實現中關鍵技術之一。數據緩沖技術涉及三個問題：存貯空間的利用率，對協議執(zhí)行速度的影響，對協議機制和網絡性能的影響。(1)存貯空間利用率協議數據單元的大小不是固定的，小到幾個字節(jié)，大到數千個字節(jié)。如果按最大的單元固定劃分緩沖器，對于小報文，存貯空間利用率很低。一個網絡中總是存在許多用戶，在多用戶情況下，一個機器中的邏輯鏈路數是隨用戶而動態(tài)變化的。如果按照最大用戶數給每條邏輯鏈路分配固定的緩沖器，那么在用戶少的情況下，存貯空間浪費較大。第七章協議實現技術7.4數據緩沖技術第七章協議實現技術(2)協議執(zhí)行速度協議數據單元在上下層的傳遞可采用兩種方法：緩沖器指針傳遞法和緩沖器復制法。很顯然，前者的額外開銷小，協議執(zhí)行速度高。問題(l)和(2)是有矛盾的。為了提高存貯空間利用率，緩沖器長度設定要小，但對于大數據單元則需要多個緩沖器來容納，多個緩沖器容納一個數據單元的處理將給軟件帶來許多麻煩。(3)協議機制和網絡性能緩沖器是網絡的最重要的資源，許多協議機制的執(zhí)行依賴于緩沖器的可用度。例如，傳輸層在實行窗口流控制時，發(fā)送窗口的寬度是由對方的接收能力決定的（主要是可用的緩沖器的數口）。對于有路由功能的網絡層協議實體來說，緩沖器的分配管理算法與網絡擁塞控制策略和死鎖防止方法密切相關。第七章協議實現技術(2)協議執(zhí)行速度第七章協議實現技術7.4.1緩沖器指針傳遞方法數據單元在上下層協議實體之間的傳遞采用緩沖器指針傳遞方法時所要解決的一個重要問題是數據單元的分段與合段。例如，當會晤層的一個協議數據單元SPDU(sessionprotocoldataunit)用指針傳遞方法送給傳輸層協議實體后，可能要將它分成三段，即一個TSDU變成三個TPDU(transportprotocoldataunit)，這里的TSDU(transportservicedataunit)就是SPDU。由于傳輸層必須給每段數據添加一個傳輸層報文頭TH(transporthead)，因此除第一個TPDU之后，后兩個TPDU的形成都避免不了數據的復制，圖7.3示出這一個過程。圖7.3數據分段引起數據復制第七章協議實現技術7.4.1緩沖器指針傳遞方法圖7.3數第七章協議實現技術為了解決分段引起的數據復制，我們可以采用這樣的一種方法：如果設傳輸層允許的TPDU最大長度為l，它的報文頭TH最大長度為n，那么會晤層可使用長度為l的多個緩沖器，將一個SPDU分割成多個長度小于（l-n）的段分別放在不同的緩沖器中，然后將緩沖器鏈傳遞給傳輸層，圖7.4示出緩沖器鏈傳遞方法。圖7.4緩沖器鏈傳遞第七章協議實現技術為了解決分段引起的數據復制，我們可以采用第七章協議實現技術上述方法仍然有一個缺點，即會晤層交給傳輸層的緩沖器，其頭部必須留足夠的空間以便傳輸層（還包括網絡層及底層）填寫它的報文頭。這樣不但存儲空間有浪費，而且緩沖器指針要隨報文頭的添加數而修改。圖7.5所示的方法中，各層協議頭使用專門的小緩沖器，用戶數據分放在多個大緩沖器中。圖7.5用戶數據和報文頭分別用不同的緩沖器第七章協議實現技術上述方法仍然有一個缺點，即會晤層交給傳輸第七章協議實現技術7.4.2共享緩沖區(qū)的分配和管理為了提高存儲空間的利用率，人們往往采用共享緩沖器的方法。圖7.6為共享緩沖區(qū)示意圖。傳輸層提供n條邏輯鏈路服務，每個應用層協議實體（如a,b,c）通過表示層協議實體P和會晤層協議實體S使用一條邏輯鏈路。N條邏輯鏈路共享發(fā)送緩沖區(qū).

例如當應用層實體a要發(fā)送一個報文時，它從發(fā)送緩沖區(qū)獲取一個或多個緩沖器，然后將裝載報文的緩沖鏈逐層傳遞給P層，S層，傳輸層和網絡層。網絡層將報文從指定通訊網絡或線路發(fā)出之后，將空緩沖器歸給發(fā)送緩沖區(qū)。接收緩沖區(qū)向各個通訊網絡端口或點對點線路端口提供接收緩沖器。裝填有接收報文的緩沖器首先由網絡層處理，網絡層或將緩沖器上交傳輸層處理（如果報文的目的地址是本地地址），或將緩沖器交給另外的通訊網絡端口轉發(fā)（如果報文的目的地址不是本地結點），或將緩沖器歸還給接收緩沖區(qū)（如果報文是網絡層報文）。第七章協議實現技術7.4.2共享緩沖區(qū)的分配和管理圖7.6共享緩沖區(qū)圖7.6共享緩沖區(qū)第七章協議實現技術共享緩沖區(qū)固然可以提高存儲空間利用率，但如果沒有合理的分配管理算法，將帶來嚴重的副作用。第一個嚴重的副作用是緩沖器的枯竭。當某條邏輯鏈路通訊流量特別大時，它可能獨占所有發(fā)送緩沖器，以致其它應用層協議實體不能獲得緩沖器，造成緩沖器枯竭現象。第二個嚴重的副作用是不合理的接收緩沖器分配管理算法將會造成網絡死鎖現象。第七章協議實現技術共享緩沖區(qū)固然可以提高存儲空間利用率，但第七章協議實現技術

本節(jié)討論緩沖器的公平分配問題，下節(jié)討論接收緩沖器分配管理與網絡性能的關系。對于發(fā)送緩沖器，最常用的分配算法是平方根法。設發(fā)送緩沖區(qū)所能提供的緩沖器數目為B，當前活躍的邏輯鏈路數為n，那么每條鏈路所能占用的發(fā)送緩沖器的最高限額不應大于B/。對于接收緩沖器，緩沖器的占用者的概念不同于發(fā)送緩沖器。當一個通訊子網接收一個報文，并將報文放入緩沖器之后并不能立刻確定該緩沖器由誰占用。裝填接收報文的緩沖器經由網絡層處理之后，報文的占用者就確定了第七章協議實現技術本節(jié)討論緩沖器的公平分配問題第七章協議實現技術

例如，當圖7.6中的net1收到一個報文并將緩沖器交網絡層之后；網絡層處理該報文，如果該報文向net2轉發(fā)，那么緩沖器占用者是net2；如果該報文上交傳輸層，那么緩沖器的占用者是本地結點。這樣，如果網絡層有路由功能，并且它支持m路輸出線路（通訊子網端口），那么接收緩沖器要在m+1個對象中分配；如果網絡層沒有路由功能，那么所有接收緩沖區(qū)都歸本地結點所有。如果本地結點當前有n條活躍邏輯鏈路，那么對于分配給本地結點的那份接收緩沖器再按n個對象分配（或平均分配，或按平方根分配）。第七章協議實現技術例如，當圖7.6中的net1第七章協議實現技術7.4.3接收緩沖器的分配管理如果網絡層有路由功能，那么接收緩沖區(qū)的分配管理算法就比較復雜，不合理的分配算法還將產生死鎖等副作用。下面分別討論三個副作用及解決辦法。1.直接死鎖（directdeadlock）假定接收緩沖區(qū)的分配是任意的，即每一條輸出線路端口可以占用任意多緩沖器，直至接收緩沖區(qū)枯竭為止，那么圖7.7所示的直接死鎖現象就可能出現。圖中，由于結點A的所有接收緩沖器已被端口a所占用，它不能再接收b的報文，而B的所有緩沖器已被端口b所占用，它也不能接收A發(fā)出的報文，死鎖發(fā)生！直接死鎖產生的原因是雙方接收緩沖區(qū)同時枯竭，解決的辦法是避免接收緩沖區(qū)枯竭。假定結點的接收緩沖區(qū)的緩沖器總數為C，對于有m條輸出線路（端口）同時活躍的情況，各條輸出線路所能占用的接收緩沖器限額應小于Ct=C/（m+1），本地結點看作一路輸出，它所分配的限額也為Ct。按照這種平均法則分配接收緩沖器枯竭現象永不會發(fā)生，直接死鎖就消除了。第七章協議實現技術7.4.3接收緩沖器的分配管理第七章協議實現技術圖7.7直接死鎖第七章協議實現技術圖7.7直接死鎖第七章協議實現技術2.間接死鎖（indirectdeadlock）即便是對輸出線路所占用的緩沖器進行限制圖7.8所示的死鎖還可能發(fā)生。這種由多個結點的輸出隊列所形成的環(huán)路死鎖稱為間接死鎖。間接死鎖發(fā)生時各個結點的接收緩沖區(qū)并沒有枯竭。圖7.8中，A中的輸出線路a的所有報文的目的地址不是B，但必須經過B的端口b轉發(fā)，由于b的輸出隊列長度已經達到限額，B無法接收A發(fā)來的必須經過端口b轉發(fā)的報文。由于同樣情況，C無法接收B發(fā)來的必須經端口c轉發(fā)的報文，D無法接收C發(fā)來的必須經端口d轉發(fā)的報文，A無法接收D發(fā)來必須經端口a轉發(fā)的報文，死鎖發(fā)生！第七章協議實現技術2.間接死鎖（indirectdead第七章協議實現技術圖7.8間接死鎖第七章協議實現技術圖7.8間接死鎖第七章協議實現技術間接死鎖的解決辦法之一基于分類報文概念。網絡層處理輸入報文時按照一定的分類方法將它們分成不同類別的報文，給每個報文打上類別標記，并按照報文類別分配接收緩沖器的限額。報文分類的第一種方法是按照輸出線路進行。例如，假如某結點有三條輸出線路a，b，c，當網絡層處理報文時發(fā)現報文需經線路a轉發(fā)，那么它的類別為a;經b轉發(fā)，它的類別就為b。這是最簡單的分類法，但不能解決間接死鎖問題。第七章協議實現技術間接死鎖的解決辦法之一基第七章協議實現技術

報文分類的第二種方法是按照報文已走過的鏈路數或到達目的結點之前還需走過的鏈路數進行，前者稱之為后向鏈分類法，后者稱之為前向分類法。按照前向鏈分類法，到達目的結點之前還要走n條鏈路的報文為n類報文，n類報文邏輯上放入n隊列。1類報文的目的結點就是鄰近結點。按照這種方法對報文分類從根本上消除了圖7.8所示的輸入隊列環(huán)路，因此不會發(fā)生間接死鎖。圖7.9中，各個輸出端口邏輯上有三個隊列q1，q2，q3。q1放1類報文（到達目的結點的鏈路數為1），q2放2類報文，q3放3類報文。當圖7.8所示的情況出現時（各個結點的q2的長度已到達限額），死鎖不會出現，這是因為B能接收A從q2發(fā)出的報文，并將報文放入B的q1隊列（A中的2類報文到達B后變成1類報文）。如果假定B的q1隊列也已到達限額，但由于B將q1隊列中的報文發(fā)往C之后，C總是能接收目的結點就是C的報文（B的q1隊列很快就會倒空）死鎖就不會出現。第七章協議實現技術報文分類的第二種方法是第七章協議實現技術圖7.9前向鏈分類法第七章協議實現技術圖7.9前向鏈分類法第七章協議實現技術3.交通流量控制接收緩沖區(qū)的分配管理與網絡報文流量控制有關，或者說某些交通流量控制算法是通過接收緩沖器的分配管理來實現的。其中最常用的做法是對不同類別的報文實行優(yōu)先級別控制（優(yōu)先界別高的報文可獲得多的接收緩沖器），以提高網絡流通量，減少交通堵塞發(fā)生率。例如，當采用前向鏈分類法時，如果使類別低的報文優(yōu)先級別高（即1類報文優(yōu)先于2類報文）就能使接近于目的結點報文盡快離開網絡，避免交通堵塞。第七章協議實現技術3.交通流量控制第七章協議實現技術7.5協議并行處理技術隨著數據通訊速率的提高，計算機網絡各層協議的執(zhí)行速度也必須提高。例如，當數據傳輸速率為1Gbps（1000Mbps）時，如果傳輸層的平均報文長度為128字節(jié)，那么它每秒要處理一百萬個報文。如果每個報文的處理要花費50條指令（不包括CRC校驗），那么傳輸層協議處理器的速度應大于50Mips。如果傳輸層報文包含CRC碼，處理器速度要更高（約100Mips）。MIPS-------MillionInstructionsPerSecond每秒百萬條指令第七章協議實現技術7.5協議并行處理技術第七章協議實現技術提高協議執(zhí)行速度的辦法之一是協議并行處理技術，即用多個CPU并行執(zhí)行某層協議。文獻【14】以傳輸層協議為例，定義了三種粒度（grains）不同的協議并行處理;粗粒度（coarsegrain）并行，中粒度（mediumgrain）并行和細粒度（finegrain）并行。

按粗粒度并行處理協議時，協議實