協(xié)議開發(fā)的理論和方法

1、1計算機網(wǎng)絡計算機網(wǎng)絡n計算機學科發(fā)展的一個特征：n計算機網(wǎng)絡：應用和工程技術(shù)科學n理論和方法：體系結(jié)構(gòu)與協(xié)議，2協(xié)議研究協(xié)議研究nRoutingnQoSnMulticastnAdmission Control & Congestion ControlnSwitchingnMiddlewaren3協(xié)議發(fā)展協(xié)議發(fā)展nIBM SNA、ISO OSI/RM和DoD TCP/IP等著名體系結(jié)構(gòu)和協(xié)議已發(fā)揮了不可估量的作用；nSNA是協(xié)議體系結(jié)構(gòu)的開拓者；nOSI/RM是協(xié)議的指路燈塔；nTCP/IP是目前盛行的實事上的工業(yè)標準；nXTP、VMTP、Delta-t和NETBLT的出現(xiàn)，將使計算機

2、網(wǎng)絡進入一個高性能的時代。 4協(xié)議工程協(xié)議工程n隨著網(wǎng)絡服務要求的提高，網(wǎng)絡系統(tǒng)的復雜性在協(xié)議方面體現(xiàn)出空間分布性、并發(fā)性、異步性、不穩(wěn)定性和多樣性，高質(zhì)量的通信協(xié)議再也不可能靠工程直覺方法來設計了；n協(xié)議工程（Protocol Engineering）用形式化的方法來描述在協(xié)議設計和維護中的各個活動，建立一套嚴格的協(xié)議設計方法，使協(xié)議開發(fā)的整個過程一體化、系統(tǒng)化和形式化，從而保證協(xié)議的完整性、正確性、安全性和可移植性。 5協(xié)議開發(fā)主要活動間的關(guān)系協(xié)議開發(fā)主要活動間的關(guān)系6n完整的語法和語義定義； n體系結(jié)構(gòu)、服務和協(xié)議的可表達性； n協(xié)議重要特性的可分析性；n支持復雜協(xié)議的管理；n支持逐步求

3、精的方法；n支持實現(xiàn)獨立性；n支持協(xié)議生命期的各環(huán)節(jié)（描述、驗證、實現(xiàn)、一致性測試、）；n支持自動設計、驗證、實現(xiàn)和維護方法。形式描述技術(shù)形式描述技術(shù)FDT的特征的特征7n狀態(tài)變遷模型n有限狀態(tài)機FSMn通信有限狀態(tài)機CFSMnPetri網(wǎng) n程序設計語言模型n抽象程序nCCS，CSPn時態(tài)邏輯FDT種類種類8n進程代數(shù)（Process Algebra）：用代數(shù)的方法來研究協(xié)議，它有一套完善的等價理論，如果與網(wǎng)論相結(jié)合，可以用一套完善的分析技術(shù)，提供一個結(jié)構(gòu)清晰的模型。進程代數(shù)與隨機模型相結(jié)合（如馬爾可夫模型），被應用到協(xié)議的性能評價。n混合模型（如擴展的FSM）：擴展的FSM過于復雜并且缺乏

4、形式語義，分析功能較弱。FDT種類種類9國際標準國際標準 FDTSDLnSDL (Specification and Description Language)：FSM + extensions 1976年由CCITT(ITU)頒布 ，一種基于擴展狀態(tài)變遷和抽象數(shù)據(jù)類型的混合技術(shù)，被電信公司廣泛用于描述電子分組交換系統(tǒng)，最近已發(fā)布了SDL-2000的新版本 。10國際標準國際標準 FDT LOTOSnLOTOS (Language Of Temporal Ordering Specification)：CCS+ADT n80年代ISO制訂OSI參考模型時發(fā)布，1988年確立了最后的國際標準文本

5、。n LOTOS提供形式語義，保證描述不存在二義性，便于分析和一致性測試理論的研究。LOTOS有二個組成部分，一部分基于過程代數(shù)，另一部分是基于ACT ONE的抽象數(shù)據(jù)類型。 11FDT的國際標準的國際標準EstellenEstelle(Extended State Transition Model Language)：EFSM + extended Pascal nEstelle也是基于擴展的狀態(tài)變遷模型，但使用PASCAL語法和數(shù)據(jù)類型，它有一個形式化的獨立于實現(xiàn)的語義。 nEstelle標準頒布以后， 一直到1994年，Estelle研究小組主要致力工具包的研制，1996年以后， Est

6、elle標準又被改進了50多處，不過直到現(xiàn)在也沒有見到Estelle 的升級版本。 12FDT與與UML的結(jié)合的結(jié)合 近年來UML (Unified Modeling Language) 被應用到協(xié)議開發(fā)中。nUML簡介簡介 UML統(tǒng)一各種面向?qū)ο蠓治龊驮O計方法的差異。1995年10月發(fā)布了第一個版本，現(xiàn)在UML2.0已經(jīng)推出。如今UML已成為一個流行的、標準化的、通用目的面向?qū)ο蟮目梢暬Ｐ驼Z言，許多大的軟件開發(fā)組織開始用它進行系統(tǒng)建模。 13FDT與與UML的結(jié)合的結(jié)合nUML用于協(xié)議開發(fā)的優(yōu)勢 n當今的形式化的協(xié)議開發(fā)技術(shù)缺少可視化； n不支持協(xié)議開發(fā)的整個生命周期； 而上述兩點正是UM

7、L的優(yōu)勢所在。nUML用于協(xié)議開發(fā)的不足 UML缺少定義復雜通信系統(tǒng)協(xié)議的形式化語義，不能直接用它來開發(fā)協(xié)議，必須給UML增加一些語義功能。14FDT與與UML相結(jié)合相結(jié)合 BDLnBDL (Behavioural Description Language)n一個能夠描述異步并發(fā)行為的語言BDL（把UML的面向?qū)ο蠹夹g(shù)引入到形式化的協(xié)議驗證中）；n利用BDL可以一致性的操縱包含序列或協(xié)同圖的UML行為視圖，并且不同UML行為視圖可以相互轉(zhuǎn)換；n在BDL中，用事件的偏序集合來表示對象間的相互交互，用對象間的一些基本的交互來描述整個系統(tǒng)的行為。 15FDT與與UML相結(jié)合相結(jié)合GPDLnGPDL

8、(Graphical Protocol Description Language )n一個圖形化的協(xié)議設計語言，描述協(xié)議的結(jié)構(gòu)和行為； nGPDL的重要性在于把UML的圖形引入到了協(xié)議設計中，使之可視化；nGPDL包含兩部分：一是圖和文本，圖的結(jié)構(gòu)使協(xié)議設計形象化，當圖形不能表示時，就用文字說明；另一部分是GAEL (Generic Action Extension Language)用來表達協(xié)議的語義信息，以彌補UML的不足。 16FDT與與UML相結(jié)合相結(jié)合GPDL GPDL主要用于協(xié)議的設計和實現(xiàn)，用GPDL描述的協(xié)議可以比較容易地轉(zhuǎn)換成SDL標準。 17 在三種主要的國際標準FDT中，

9、SDL與UML結(jié)合的是較容易的，因為nSDL是基于狀態(tài)變遷技術(shù)的，而狀態(tài) 圖（state diagram）正是UML建模的5種圖之一；一個狀態(tài)圖就是一個狀態(tài)機 ；nSDL具有抽象數(shù)據(jù)類型，與UML的面向?qū)ο蠹夹g(shù)吻合。 SDL-200018SDL-2000 SDL-2000是SDL-96和UML技術(shù)有機結(jié)合的版本， SDL-2000 = SDL-96 + UML 19基于基于Petri網(wǎng)的網(wǎng)的FDT Petri網(wǎng)理論是在并發(fā)的概念上建立起來的，它直觀地表示了非確定性，可以用于表達不同抽象級上的系統(tǒng)概念。 Petri網(wǎng)有一套成熟的數(shù)學理論工具，建立了許多分析技術(shù)，包括可達性分析、不變量分析(使用線

10、性代數(shù)方法)、保持特性的變換(包括化簡)、構(gòu)造理論、形式語言理論、同步距離和網(wǎng)的分解和等價等。20基于基于Petri網(wǎng)的網(wǎng)的FDT 近幾年人們的注意力集中在如何將代數(shù)的抽象數(shù)據(jù)類型，融合在高級網(wǎng)結(jié)構(gòu)中，能夠大大地提高描述協(xié)議和服務所用的高級Petri網(wǎng)系統(tǒng)的表示能力。 21基于基于Petri網(wǎng)的網(wǎng)的FDT n三種標準的FDT只支持協(xié)議工程的一至二個活動 nEstelle是一種過程語言，可以描述協(xié)議細節(jié)，用它描述的協(xié)議僅便于實現(xiàn)；nLOTOS描述協(xié)議實體的外部行為，不關(guān)心實體內(nèi)部變化，描述的協(xié)議僅便于驗證；nSDL是一種混合式的FDT，缺乏形式語義，缺乏分析技術(shù)。SDL-2000也只是吸收了UM

11、L的一些概念、方法，增加了面向?qū)ο蟮目梢暬O計功能，使之更好用，并沒有從本質(zhì)上提升SDL的分析能力 。22基于基于Petri網(wǎng)的網(wǎng)的FDTnPetri網(wǎng)具有異步特性并發(fā)，決定了它的主要應用方向是分布式系統(tǒng) 根據(jù)外延公理，變遷的發(fā)生完全由它的外延決定，與系統(tǒng)全局狀態(tài)無關(guān)。因而網(wǎng)系統(tǒng)是異步并發(fā)的“自由王國”，沒有主宰全局的中央控制，這很適合網(wǎng)絡體系結(jié)構(gòu)、協(xié)議和服務的特點 。 23基于基于Petri網(wǎng)的網(wǎng)的FDTnPetri網(wǎng)的形式基礎使它與其它并發(fā)模型建立了連接，這有益于分布式系統(tǒng)的描述和分析。nPetri網(wǎng)用直觀的圖形表示形式，與物理系統(tǒng)相近，學習和理解這種語言相對容易。nPetri網(wǎng)最大的優(yōu)點

12、是具備一套嚴密的數(shù)學理論，各種技術(shù)極有利于驗證和分析。24基于基于Petri網(wǎng)的網(wǎng)的FDTnPetri網(wǎng)表現(xiàn)出面向?qū)ο蠹夹g(shù)的各個網(wǎng)表現(xiàn)出面向?qū)ο蠹夹g(shù)的各個特性，將是一種優(yōu)良的可用圖形表示特性，將是一種優(yōu)良的可用圖形表示的面向?qū)ο笳Z言。的面向?qū)ο笳Z言。 為適應不同規(guī)范及驗證的需求，從基本Petri網(wǎng)模型衍化出許多擴展模型系統(tǒng)，目前主要有：謂詞/動作Petri網(wǎng)、時間Petri網(wǎng)(TPN)、帶時態(tài)邏輯的Petri網(wǎng)、顏色Petri網(wǎng)(CPN)、面向?qū)ο驪etri網(wǎng)(OOPN)、隨機Petri網(wǎng)(SPN)、數(shù)字Petri網(wǎng)(NPN)等。 25協(xié)議開發(fā)面臨的挑戰(zhàn)協(xié)議開發(fā)面臨的挑戰(zhàn)n支持協(xié)議工程整個生命期的FDT？n協(xié)議的描述？n支持協(xié)議開發(fā)的工具？26基于基于Petri網(wǎng)的協(xié)議開發(fā)的問題網(wǎng)的協(xié)議開發(fā)的問題n自然語言描述的協(xié)議系統(tǒng)到Petri網(wǎng)系統(tǒng)的轉(zhuǎn)換，相應的計算機輔助工具的開發(fā)，中間語言、一般模型、轉(zhuǎn)換算法和規(guī)則的建立。n協(xié)議Petri網(wǎng)描述到協(xié)議實現(xiàn)的自動化，建立P