網(wǎng)絡(luò)協(xié)議工程總結(jié)

1、衿 For pers onal use only in study and research; not for commercial use羂第二章協(xié)議設(shè)計(jì)技術(shù)芁1協(xié)議層次模型：(主要是描述n與n+1實(shí)體間的關(guān)系)(H + 1)層(n+1)實(shí)體(n+1)實(shí)體(n)SPs(n)SPs 盲(M實(shí)體世X (n)實(shí)體 * (nPDUs；(nd)SPsnSAPnSAP(n-l)Sh :(n-l)SAP提做Ibl)服務(wù)：(n-1)SAP ；(n r 1)層通過mi)連接進(jìn)彳亍通信(n)服務(wù)提供者蟻 芆 莆 螞 聿 艿 莆 肅 螁肇蒆蒄 艿 袇薅實(shí)體(entity):表示任何可以發(fā)送和接收信息的硬件或軟件進(jìn)

2、程。在許多情況下，實(shí)體就是一個(gè)特定的模塊。蚆n服務(wù)：兩個(gè)(n)實(shí)體在(n)協(xié)議的控制下的通信，使(n)層能夠向上一層(n+1)提供服務(wù)。 這種服務(wù)就是(n)服務(wù)。羈一個(gè)(n)實(shí)體向上一層所提供的服務(wù)由以下三部分構(gòu)成：(1)(2) 莈(n)實(shí)體自己提供的某些功能。(3)(3) 蚈從(n-1)層及其以下各層以及本地系統(tǒng)環(huán)境得到的服務(wù)。(5)(6)螆通過與處在另一系統(tǒng)中的對(duì)等(n)實(shí)體的通信而得到的服務(wù)。莂 PDU 通常由 2 部分構(gòu)成：用戶數(shù)據(jù)和協(xié)議控制信息 PCI(Protocol Control Information) 。膀PCI般作為首部加在用戶數(shù)據(jù)的前面，但有時(shí)也可作為尾部加在用戶數(shù)據(jù)的

3、后面， 例如檢驗(yàn)和(checksum)常放在尾部。莇兩種類型：袆數(shù)據(jù) PDU螃控制PDU,不攜帶用戶數(shù)據(jù)。薈在不同的協(xié)議層次中，PDU還有一些其它的表示法。膆物理層：比特 (bit)；羅數(shù)據(jù)鏈路層：幀 (frame) 或信元 (cell)；袀 網(wǎng)絡(luò)層 ：分組或包 (packet)芀 運(yùn)輸層 ：報(bào)文 (Message)羅SDUQSI將層與層之間交換的數(shù)據(jù)的單元稱為服務(wù)數(shù)據(jù)單元SDU(Service Data Un it)。羅一個(gè)(n)服務(wù)數(shù)據(jù)單元就是(n)服務(wù)所要傳送的邏輯數(shù)據(jù)單元。芁SDU就是數(shù)據(jù)PDU中的用戶數(shù)據(jù)，但不一定是一一對(duì)應(yīng)關(guān)系。螈可以是多個(gè)SDU合成為一個(gè)PDU(稱為拼裝”)也可以

4、是將一個(gè) SDU劃 分為幾個(gè)PDU(稱為分段”。羈PDU的裝配與拆裝：在發(fā)送數(shù)據(jù)之前，(n)協(xié)議需要裝配 PDU,即按照給定格式附上協(xié)議控制信息PC。對(duì)于接收后的 PDU要對(duì)之拆裝，拆出PC。芅pciD拓螞SAP:同一系統(tǒng)中相鄰兩層的實(shí)體進(jìn)行交互（即交換信息）之處，通常稱為服務(wù)訪問點(diǎn)SAP（Serivce Access Point）蒀SP（服務(wù)原語）：在進(jìn)行交互時(shí)所要交換的一些必須信息（或命令）稱為服務(wù)原語（ServicePrimitives），以表明需要本地的或遠(yuǎn)端的對(duì)等實(shí)體做哪些事情。螇每層均可使用的4種服務(wù)原語：（P17）膅Request （請(qǐng)求）:一個(gè)實(shí)體希望得到某種服務(wù)肅Indica

5、tion （指示）：把關(guān)于某一事件的信息告訴某一實(shí)體羈Response響應(yīng)）：一個(gè)實(shí)體愿意響應(yīng)某一事件 薆Confirm （證實(shí)）：把一個(gè)實(shí)體的服務(wù)請(qǐng)求加以確認(rèn)并告訴它系統(tǒng)八蒄過程描述：蠆：用戶A先發(fā)出Request原語，以調(diào)用服務(wù)提供者的某個(gè)進(jìn)程蕿To：Request原語就引起系統(tǒng) A的(n)實(shí)體向某對(duì)等實(shí)體發(fā)出一個(gè)協(xié)議數(shù)據(jù) 單元PDU蒞：當(dāng)系統(tǒng)B的(n)實(shí)體收到這個(gè)PDU后，就向其服務(wù)用戶發(fā)出In dication原語蝕To ：通常對(duì)應(yīng)于:莁(1)表示系統(tǒng)B的(n)服務(wù)用戶應(yīng)當(dāng)調(diào)用一個(gè)適當(dāng)?shù)膮f(xié)議過程，或者莇(2)表示服務(wù)提供者已經(jīng)調(diào)用了一個(gè)必要的過程。蒅：接著，服務(wù)用戶B發(fā)出Respo n

6、se原語，用以完成剛才In dication 原語所調(diào)用的過程肁To：這時(shí)，協(xié)議又產(chǎn)生一個(gè)協(xié)議數(shù)據(jù)單元PDU通過網(wǎng)絡(luò)到達(dá)系統(tǒng) A。衿：最后，系統(tǒng) A的(n)實(shí)體發(fā)出Confirm原語，表示完成了先前由服務(wù)用戶A發(fā)出的Request原語所調(diào)用的過程。薅2.連接于非連接:蒂面向連接的(connection-oriented)服務(wù)薁三個(gè)階段：連接建立、數(shù)據(jù)傳輸和連接釋放 裊在傳送數(shù)據(jù)時(shí)是按序傳送的薄網(wǎng)絡(luò)層：虛電路服務(wù)袃比較適合于在一定期間內(nèi)要向同一目的地發(fā)送許多報(bào)文的情況罿永久虛電路：適于兩個(gè)用戶需要經(jīng)常進(jìn)行頻繁的通信的情況袈無連接的(connectionless服務(wù)蚄不能保證報(bào)文的丟失、重復(fù)、失序

7、羀三種類型：數(shù)據(jù)報(bào)(datagram)、證實(shí)交付(confirmed delivery,可靠的數(shù)據(jù)報(bào))、 請(qǐng)求回答(request-reply)?蟻數(shù)據(jù)報(bào)：不需要接收端做任何響應(yīng)。盡最大努力交會(huì)(best effort delivery)?蚇證實(shí)交付：又稱“可靠的數(shù)據(jù)報(bào)”。對(duì)每一個(gè)報(bào)文產(chǎn)生一個(gè)證實(shí)給發(fā)方用戶，不過這個(gè)證實(shí)不是來自接收端的用戶而是來自提供服務(wù)的層?螄請(qǐng)求回答：收端用戶每收到一個(gè)報(bào)文，就向發(fā)端用戶發(fā)送一個(gè)應(yīng)答報(bào)文。適于“事務(wù)(transaction)中的通信。莁適于傳送少量零星的報(bào)文腿蒆3.通道：(基于三種通道的FSM模型)襖主要有三類：螂空通道(empty channels)?袁

8、報(bào)文的發(fā)送時(shí)間和延時(shí)時(shí)間為0的通道?葿報(bào)文一旦從輸入端進(jìn)入就立即在輸出端出現(xiàn)羄非緩沖通道(non-buffered channels)?膃在任何時(shí)刻，最多只有一個(gè)正在傳送中的報(bào)文的通道莈緩沖通道(buffered channels)?羋允許有多個(gè)報(bào)文停留的通道肄形成方式和隊(duì)列性質(zhì)（次要）（p12）薃肀4.幾種控制:羆差錯(cuò)控制膄主要概念?螀在網(wǎng)絡(luò)上進(jìn)行通信會(huì)造成數(shù)據(jù)PDU以一定的概率被損壞、丟失、重復(fù)和亂序。協(xié)議的差錯(cuò)控制功能負(fù)責(zé)這些差錯(cuò)的檢測(cè)及恢復(fù)，保 證數(shù)據(jù)的可靠傳輸。?蒈n層協(xié)議的差錯(cuò)控制機(jī)制與它的服務(wù)提供者提供的（n-1）通道的性質(zhì)有很大關(guān)系，（n-1）通道提供的數(shù)據(jù)通道的可靠性越高，則

9、n層協(xié)議需實(shí)現(xiàn)的差錯(cuò)控制機(jī)制則越少。螅主要技術(shù)有：（檢錯(cuò)重傳或丟棄、糾錯(cuò)）? 膄確認(rèn)（Ack）? 賺計(jì)時(shí)器（Timer）?芀重傳（Retransmit）?螈序號(hào)（Sequenee Number）芃差錯(cuò)控制的層次關(guān)系?薂從通信和信息處理的角度看，物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層和運(yùn)輸 層屬于面向通信部分，因而網(wǎng)絡(luò)中的絕大部分差錯(cuò)控制功能要在這 幾層中實(shí)現(xiàn)。?蚈處于不同層次的協(xié)議所采用的差錯(cuò)控制機(jī)制是有差別的。薇流量控制莃流量控制是指“收端控制發(fā)端的發(fā)送數(shù)據(jù)速率以使收端來得及接收，并且使網(wǎng)絡(luò)不致過載”羃 Why?莀接收方的接收能力有限莆緩存不夠蒃處理能力不夠莄 Examples:?袈 Stop and

10、Wait? 荿 Slidi ng wi ndow薃擁塞控制蒁在某段時(shí)間，若對(duì)網(wǎng)絡(luò)中某一資源的需求超過了該資源所能提供的可用部 分，網(wǎng)絡(luò)的性能就要變壞。這種情況就叫做擁塞(congestion)。薀資源(resources):?膈鏈路容量?蚃交換結(jié)點(diǎn)中的緩沖區(qū)(buffer)?袂處理機(jī)芁擁塞控制的主要功能?羆防止網(wǎng)絡(luò)因過載而引起吞吐量下降和遲延增加?蚃避免死鎖?節(jié)在互相競(jìng)爭(zhēng)的各用戶之間公平地分配資源蝿蚅第三章形式化描述技術(shù)螃 1.FSM蚃定義蒁 FSM = (S, sO, I,、; F), where螈 S = sO, s1, 定的狀態(tài)si。待限狀態(tài)集合。在任一確定時(shí)刻，F(xiàn)SM只能處于一個(gè)確FS

11、M只能接收袃I = aO, a1,有限輸入字符集合。在任一確定的時(shí)刻,一個(gè)確定的輸入aj。初：S IS是狀態(tài)轉(zhuǎn)換函數(shù)，如果在某一確定的時(shí)刻，F(xiàn)SM處于某一狀態(tài)si S,并接收一個(gè)輸入字符 aj I，那么下一時(shí)刻將處于一個(gè)確定的狀態(tài)s'=;.（si, aj） S。在這里規(guī)定，s =；.（s ,；）,即對(duì)任何狀態(tài)s,當(dāng)讀入空字符；時(shí)，有限狀態(tài)機(jī)不發(fā)生任何狀態(tài)轉(zhuǎn)移。衿sO - S是初始狀態(tài)，F(xiàn)SM由此狀態(tài)開始接收輸入蕆F S是一個(gè)終態(tài)集（可空），F(xiàn)SM到達(dá)終態(tài)后不再接收輸入羂實(shí)例一：開關(guān)莆switch off/ stay quietswitch off/ make click sound蟻s

12、tate eventOnOffSwitch onclick, onSwitch offclick, off-芆實(shí)例二：電話螞聿艿 IDLE莆 DIALING肅RINGING螁PATHACTIVE肇 On-hook蒆-蒄 IDLE艿-袇 IDLE薆 Off-hook薁 Send Dial Tone, DIALING羀-薅 PATHACTIVE蚆-羈Dial-digit(Note1)莈-蚈 DIALING PATHACTIVE螆-莂-膀 Call-Alert莇 Ring Pho ne,RINGING祎/螃/薈/膆 2.PETRI NET:羅概念Petri網(wǎng)可定義為一個(gè) 4元組(P T , I, 0

13、),其中:袀 P = p1, p2,是位置(places)的有限集合；芀 T = t1, t2,=一。是變遷(transitions)的有限集合，且 T與P不相交，即TA P羅1是輸入函數(shù)，I(tk)=pi, pj,。是變遷T到位置的映射。對(duì)于每一個(gè)tk T,可得出相應(yīng)的羅O是輸出函數(shù)，也是一種變遷 T到位置的映射。對(duì)于每一個(gè)tk T,可以得出相應(yīng)的 0(tj)=pr, ps,。芁M = ml, m2,m標(biāo)記（tokens,旗標(biāo)'"或 托肯”的集合螈變遷類型斗順序變遷。如圖所示。只有當(dāng)-點(diǎn)火后$才能點(diǎn)火。 卻并發(fā)變遷，如圖（b）所示.耳和®！同時(shí)（當(dāng)然也可以單獨(dú)）點(diǎn)

14、 火*斗互斥變遷#如圖所示口 q和$中只能有一個(gè)點(diǎn)火。一個(gè)點(diǎn) 火后另一個(gè)就不能再點(diǎn)火了°蒀CHB變遷6Pi位置的名稱變遷名稱肅例子:標(biāo)記。每個(gè) 位置中有。個(gè)或多個(gè)標(biāo)I記/=(2,0,0,0,0)螇p" = <0, 2, 2, 2,0) 鳥開始具備點(diǎn)火條件膅蒄例子二(行為性質(zhì)與結(jié)構(gòu)性質(zhì)見p58)(a)無界、不活、不可逆(b)無界、不活、可逆(e)無界、活性、可逆(d)有界、不活、不可逆(h)有界、活性、可逆(g)有界、活性、不可逆蠆蕿第四章 形式描述語言(三選二)蒞 1.SDL:蝕系統(tǒng)描述(p84)SYSTEM sample1(1)SIGNAL SHS2,S3,S4,S

15、5;|C】S1,S2|UlC2S3C3 S414C4 S5(a)用SDL/GR表小的系統(tǒng)例子SYSTEMsample;莇SIGNAL S1, S2, S3, S4, S5;蒅CHANNEL C1 FROM ENV TO B1 WITH S1, S2;肁ENDCHANNEL C1;衿CHANNEL C2 FROM B1 TO B2 WITH S3;肆ENDCHANNEL C2;薅CHANNEL C3 FROM B2 TO B1 WITH S4;蒂ENDCHANNEL C3;薁CHANNEL C4 FROM B2 TO ENV WITH S5;裊ENDCHANNEL C4;薄BLOCK B1 RE

16、FERENCED;袃BLOCK B2 REFERENCED;罿 ENDSYSTEM sample;袈(b)用SDL/PR表示的系統(tǒng)例子羀功能塊描述：(p85)肀C2C3(a)用SDL/GR表示的功能塊例子蚇 BLOCK B1;螄SIGNAL Sa, Sb;莁SIGNALROUTE R1 FROM ENV TO P1 WITH S1;腿SIGNALROUTE R2 FROM ENV TO P2 WITH S2;蒆SIGNALROUTE R3 FROM P1 TO ENV WITH S3;襖SIGNALROUTE R4 FROM ENV TO P2 WITH S4;螂SIGNALROUTE R5

17、FROM P1 TO P2 WITH Sa;袁F(xiàn)ROM P2 TO P1 WITH Sb;葿CONNECT C1 AND R1, R2;羄CONNECT C2 AND R3;膃CONNECT C3 AND R4;莈PROCESS P1REFERENCED;羋PROCESS P2REFERENCED;肄 ENDBLOCK B1;薃(b)用SDL/PF表示的功能塊例子羆 膄 螀 蒈螅膄賺芀螈芃進(jìn)程描述：(p87)薂蚈PROCESS P1(1,10);DCL num Natural;START;TASK num :=0;NEXTSTATE State_A;STATE State_A;INPUT S1

18、;NEXTSTATE State_B;SAVE Sa;ENDSTATE;STATE State_B:INPUT Sa;DECISION num;(0:9):TASK num := num+1; NEXTSTATE State_B; (=10):OUTPUT S3;STOP;ELSEOUTPUT Sb;STOP;ENDDECISION;ENDSTATE;ENDPROCESS; 用SDL/G表示的進(jìn)程例子(b) 用SDL/PF表示的進(jìn)程例子蟻蒁薀膈蚃袂-+- 芁羆蚃節(jié)蚅宏定義螃DD蕆s2CCSTATE s1;INPUT Inp;DECISION x>1; (FALSE) : JOIN BB;

19、 (TRUE): TASK x:=0;JOIN AA;ENDDECISION;MACRO m(x+y, AA, BB, CC, DD); CC: NEXTSTATE s2;DD: NEXTSTATE -;(c) SDL/GF芁表示的宏定義調(diào)用例子(d) SDL/PR表示的宏定義調(diào)用例子芆莆螞聿MACRODEFINITION mFPAR e.a(TRU E)e > 1">(FALSE)MACRODEFINITION m FPAR e a. b. cn d: a： DECISION e>1 (TRUE) JOIN b: (FALSE) : JOIN c: ENDDECI

20、SION;b: TASK x := y.JOIN d;ENDMACRO m(a) SDUGR 上小的世進(jìn)乂例j(b) SDUPR盤示的宅定又蒆 2.ESTELLE:冠注意點(diǎn)：艿類別為systemprocess的模塊的子模塊的類別可以是process或activity ;而類別為systemactivity的模塊的子模塊的類別必須是activity。袇類別為process的模塊的子模塊的類別必須是process；同樣，類別為activity的模塊的子模塊的類別必須是activity。薆兩種并行方式:薁異步并行(asynchronous parallelism)。異步并行性只能存在于不同系統(tǒng)模塊

21、之間羀同步并行(synchronous parallelism)。同步并行性只能存在于一個(gè)系統(tǒng)模塊內(nèi)。薅例子一：模塊嵌套舉例S(specification IPlp!6A( system pintx沾)A1 (process)B(syslcinactivily)右卩kl (activity)A2(aciivit>)pl211 net h itv)-v fp8pig p20A22| acdv itv)p21“pl IA3( process)帀tJ-Th?-Pl?B2( activity)P22羈例子二：滑動(dòng)窗口協(xié)議螆祎螃薈膆羅袀芀羅羅-+-芁螈羈肅交互點(diǎn)的位置，可以將IP分為兩種：螞內(nèi)部交

22、互點(diǎn)，女口 p19,p20, p21,UX,UY袀外部交互點(diǎn)(external IP)。其余的都為外部交互點(diǎn)腿優(yōu)先級(jí)：薅如果一個(gè)系統(tǒng)模塊的類型為systemprocess，則該系統(tǒng)模塊內(nèi)的各個(gè)子模塊可以并行執(zhí)行，而父模塊則優(yōu)先于子模塊執(zhí)行。蒃如果一個(gè)系統(tǒng)模塊的類型為systemactivity，則該系統(tǒng)模塊內(nèi)的各個(gè)子模塊只能串行運(yùn)行，具體哪個(gè)子模塊執(zhí)行則是隨機(jī)選擇的，父模塊仍然優(yōu)先于子模塊執(zhí)行。莈祎3.LOTOS(傳說不會(huì)考)type BasicBooleans is$ort$ boolopns T# F : -> boolnot : -> bool->baoleqns of

23、 sort boolnot(T) = F;riotF) = T;endty petype Booleans Is BaskBooleans op ins and: bool, bool -> bool r : boat baol -> bool eqn& of sort boolT and T =T;T and F - F;Fand T-F;F and F =F;T or T = T; Tor F =T; F or T = T; For F = F;enrltype襖在LOTOS中，信息系統(tǒng)或系統(tǒng)都是從整體上體現(xiàn)信息活動(dòng)的。例如信息的 傳輸、加工、存儲(chǔ)等操作都是系統(tǒng)的信息活

24、動(dòng)。肀而系統(tǒng)則由一組互相交互的部分(Part)所組成。在Part中發(fā)出的信息活動(dòng)稱為動(dòng)作(Action)。涉及到兩個(gè)或多個(gè) Part的共同動(dòng)作則稱為交互。罿為了說明一個(gè)系統(tǒng)，LOTOS采用了進(jìn)程、事件和事件門(gate)等概念。螅進(jìn)程被當(dāng)作一個(gè)黑盒子，我們只關(guān)心它的外顯行為。肁事件則是發(fā)生于進(jìn)程之間的交互原語的實(shí)例，是由相關(guān)進(jìn)程共同執(zhí)行的。螂事件門就是交互點(diǎn)，通信雙方利用事件門互相傳遞事件值。螈LOTOS規(guī)定了一組進(jìn)程的重寫規(guī)則。進(jìn)程間交互時(shí)發(fā)生的事件會(huì)使一個(gè)進(jìn) 程被重寫為另外一個(gè)進(jìn)程。系統(tǒng)狀態(tài)與事件的關(guān)系為樹形結(jié)構(gòu)：樹結(jié)點(diǎn)表示狀態(tài)，樹的邊表示在某狀態(tài)下可能發(fā)生的事件。裊進(jìn)程間的交互是全同步的

25、：蒂所謂全同步是指只有在互相交互的各個(gè)進(jìn)程都處于就緒狀態(tài)下，一個(gè)事 件才有可能發(fā)生。腿事件是原子的，即不能再細(xì)分為子事件的。各事件在時(shí)間上是互不重疊 的。蕆Part與進(jìn)程都可以逐步細(xì)分。袂第五章驗(yàn)證技術(shù)羈1.一般性質(zhì)和特殊性質(zhì)：芅一般性質(zhì)(著重理解：可達(dá)性、沒有死鎖、沒有活鎖) 羅特殊性質(zhì)芃2.可達(dá)性搜索法(三選一)荿窮盡性可達(dá)性分析算法 (exhaustive or full search)羋 start()肅 W = 初始狀態(tài); /*工作集：分析的狀態(tài)*/莀 A = ； /*已分析過的狀態(tài)*/肁an alyze();肇膅analyze() /*全局搜索*/螁蕿if (W 為空)return

26、;祎q =取自W的元素；芄將q加入到A中膂if (q是錯(cuò)誤狀態(tài))report_error(); /*報(bào)告錯(cuò)誤 */芁else 衿for (q的每一個(gè)后繼狀態(tài) s)莄if (s不在A或W中)把s加入到 W中；analyze();螀蚈 從W中刪除q；蒄羄優(yōu)點(diǎn)：驗(yàn)證覆蓋范圍 全面，可以證明協(xié)議中沒有錯(cuò)誤。蒁缺點(diǎn)：?莇算法能分析的最大狀態(tài)數(shù)目依賴于協(xié)議、描述方法和可用的計(jì)算資源。特別是當(dāng)系統(tǒng)狀態(tài)的數(shù)目非常大時(shí)會(huì)發(fā)生狀態(tài)空間爆炸，應(yīng)用范圍有限。?蒄當(dāng)狀態(tài)空間大于存儲(chǔ)空間時(shí)，全搜索策略將 變成部分搜索，且不能保證檢查協(xié)議中最重要的部分，而搜索 質(zhì)量變得更差。?賺對(duì)于復(fù)雜的協(xié)議，窮盡性可達(dá)性分析的效果只能算

27、作是一種低質(zhì)量 的部分搜索。袈受控部分搜索算法(controlled partial search)膆/* start()與算法5.1中的相同*/薄analyze() /*部分搜索*/薁薀if (W 為空)return;膈q =取自W的元素；蚄將q加入到A中羂if (q是錯(cuò)誤狀態(tài))report_error(); /*報(bào)告錯(cuò)誤*/肇else 羇for (q的某些后繼狀態(tài)s)螄if (s不在A或W中)把s加入到 W中；analyze();螆 從 W 中刪除 q ；袃螄受控部分搜索算法的目的是證明錯(cuò)誤的存在，而不是證明沒有錯(cuò)誤。羋優(yōu)點(diǎn)： 與窮盡性可達(dá)性分析相比，這種算法可以有效地解決狀態(tài)空間爆炸問題

28、，同時(shí)利用有限的資源來驗(yàn)證協(xié)議的最重要的部分， 從而 最大限度 地發(fā) 現(xiàn)錯(cuò)誤。蝿缺點(diǎn) ：必須能夠預(yù)先判斷出協(xié)議中的錯(cuò)誤的大概位置 ，然而這很難預(yù)先做到；雖然這些方法能夠減小狀態(tài)空間的大小，但它們都 沒有提供任何工具 將狀態(tài)空間的大小與可用內(nèi)存相匹配。羃使用這些方法時(shí)，有效搜索的部分狀態(tài)空間的大小是協(xié)議相關(guān)的，只能通 過實(shí)驗(yàn)確定， 要想找到一種最優(yōu)的方法， 必須按照不同的選擇策略進(jìn)行多次 驗(yàn)證。袁隨機(jī)模擬算法 (random simulation) 。羀 analyze() /* 隨機(jī)模擬 */薈 q = 初始狀態(tài) ;肅 while (1) 節(jié) if (q = 錯(cuò)誤狀態(tài) )螞 report_er

29、ror();芇 q = 初始狀態(tài) ;肅 else q = q 的一個(gè)后繼狀態(tài)；蚃膀優(yōu)點(diǎn)： 隨機(jī)模擬算法與協(xié)議系統(tǒng)的大小 和復(fù)雜性無關(guān) ，即使是無限大小的 系統(tǒng)，也可以應(yīng)用。因此，對(duì)于復(fù)雜的驗(yàn)證問題，這種算法也許是 唯一可用 的方法。肆缺點(diǎn)：?膃它沒有明確的終止，無法判斷是否已經(jīng)訪問過系統(tǒng)的 所有可達(dá)狀態(tài)；?肄由于沒有算法的終止，也就無法判斷是否已經(jīng)發(fā)現(xiàn)了系統(tǒng)的所有錯(cuò)誤?袁因此只能發(fā)現(xiàn)協(xié)議中的錯(cuò)誤，而不能證明協(xié)議中沒有錯(cuò)誤。芃第七章一致性測(cè)試技術(shù)(需要看ppt p33，掌握9個(gè)圖+相應(yīng)的描述)膀9個(gè)圖UT(Upper Tester)是上測(cè)試器(上層 測(cè)試軟件或硬件)0 是對(duì)IUT的上服務(wù) 邊界進(jìn)

30、行控制和觀 匕所提供的手塁丿I ri*( oTCP被測(cè)'51: *1(n-l>ASP«1對(duì)象J(n-l)Ser ice ProviderUTt(n)ASP*PCOIUTPCO(n-i)ASP是下測(cè)試器(下層 測(cè)試軟件或硬件h 是在測(cè)試執(zhí)行期 間，為了經(jīng)下層 JK務(wù)提供者而對(duì)1JT的下服務(wù)邊界 進(jìn)行間接控制和察所提供的手丿 段.薁圖二：本地測(cè)試法(LocalMehtod)羈在這種方法中，LT，UT，IUT 同處于一臺(tái)機(jī)器中，測(cè)試不需要低層通信系統(tǒng) 的支持。蚆由于UT和LT可以在同一個(gè) 程序中實(shí)現(xiàn)，因此，UT和LT的測(cè)試協(xié)同過程 TCP(Test Coordi nate P

31、rocedure)比較容易實(shí)現(xiàn)。蚇測(cè)試?yán)肬T執(zhí)行的服務(wù)原語和LT執(zhí)行的服務(wù)原語來描述。在這里，LT艿圖一：一致性測(cè)試模型LT何本地測(cè)試法相當(dāng)于低層服務(wù)提供者。葿 蠆 螇 蒃 賺 蒈 祎 襖 蠆 芇莁羆圖三：分布式測(cè)試法(Distributed Method)肆莂蝿聿膆螃在這種方法中，IUT和UT(b)分布測(cè)試法處于同一臺(tái)機(jī)器中，而 LT則分布在其它機(jī)器中。薀LT和IUT之間利用(n-1)層服務(wù)交換報(bào)文(可以在線測(cè)試)。螈與本地方法相比，LT和IUT之間的接口 PCO從IUT中轉(zhuǎn)換到LT中，LT相當(dāng) 于(n-1)層服務(wù)的使用者芆測(cè)試協(xié)同過程 TCP隱含在測(cè)試?yán)?，測(cè)試同步問題由 UT和LT的操

32、作者來 實(shí)現(xiàn)。膃適用于本地方法的測(cè)試?yán)仨毟膶懞蟛拍苡糜诜植际綔y(cè)試法。羈蒞圖四：協(xié)調(diào)測(cè)試法 (Coordi nation Mehtod)TM-PDU直接利用(n-1)層服務(wù)來傳送。圖(c)協(xié)同測(cè)試法所示的是帶內(nèi)傳送法。祎LT 4蚅(n)PDU碣* 占 i- * * i* -fa i *IUTPCO(n-l)ASPf(n-l)W務(wù)提供者蒃圖五：遠(yuǎn)程測(cè)試法(Remote Method)莈袀同樣，分布式測(cè)試法的測(cè)試?yán)荒苡糜趨f(xié)同測(cè)試法。襖這種測(cè)試方法中沒有UT,因此也不存在 UT和LT之間的協(xié)同問 題。肀在這種方法中，測(cè)試?yán)?完全用(n-1)ASP描述。罿遠(yuǎn)程方法比較適用于 被動(dòng)式協(xié)議實(shí)現(xiàn)或服務(wù)型協(xié)

33、議實(shí)體的測(cè)試。(c)遠(yuǎn)程測(cè)試法蕆圖六、七：渡船測(cè)試法(Ferry Method)(重點(diǎn)之中的重點(diǎn)，綜合性較強(qiáng))裊LT芅將.(n)PDU啪蝌TUT(n系)®務(wù)提供者r 1 JLTIUT(n)PDU pcop*IUT(n-l)ASP(nJ)服務(wù)提供者膅渡訓(xùn)測(cè)試島悄內(nèi)傳送)到LT(b)渡船測(cè)試法(帶外傳送)羅所在系統(tǒng)中，從而可將UT和LT合在一個(gè)程序中實(shí)現(xiàn)，因而有本地測(cè)試法的優(yōu)點(diǎn)。芃在被測(cè)試系統(tǒng)中需要一個(gè)代替UT的軟件，即渡船軟件。UT發(fā)送給IUT的(n)ASP和UT從IUT獲取的(n)ASP通過這個(gè)渡船軟件進(jìn)行。荿與協(xié)同測(cè)試法一樣，根據(jù)UT和渡船軟件之間交換 F-PDU方法的不同，渡船測(cè)

34、試法又可分為帶內(nèi)傳送法(圖(a)和帶外傳送法(圖(b)。羋在帶內(nèi)傳送法中，UT將測(cè)試事件通過 LT,再通過IUT傳送給渡船軟件。肅帶外傳送法中，UT通過(n-1)層服務(wù)直接傳送給渡船軟件。莀最大優(yōu)點(diǎn)是：由于UT和LT處于同一臺(tái)機(jī)器中，測(cè)試協(xié)同過程像本地方法 一樣容易實(shí)現(xiàn)，被測(cè)試系統(tǒng)中只要增加簡(jiǎn)單的渡船軟件即可。肁只是協(xié)同測(cè)試法的一種變種，是協(xié)同測(cè)試法在實(shí)現(xiàn)技術(shù)上的一種改進(jìn)，它們之間沒有本質(zhì)區(qū)別。肇圖八、圖九：中繼系統(tǒng)測(cè)試法(SI)閉環(huán)測(cè)試法(b)橫斷測(cè)試法螁和遠(yuǎn)程測(cè)試法一樣，中繼系統(tǒng)的測(cè)試也不需要UT。蕿閉環(huán)測(cè)試法的缺點(diǎn)是被測(cè)中繼系統(tǒng)只有一端的行為能被直接觀察到，而另一端的行為不能被正確地評(píng)價(jià)

35、。祎橫斷測(cè)試法則使中繼系統(tǒng)在正常操作模式下得到完全的測(cè)試，且兩端的行為都能夠被觀察到。芄膂理解CI,ASPPDU作用與傳輸過程芁LT和IUT通過(n-1)層服務(wù)交換(n-1)ASP,而UT和LT利用(n-1)層提供的另 外一條通道交換協(xié)同信息CI(Coordinated Information)。衿理解PCO莄PCO由下列三種因素標(biāo)識(shí)：? IUT內(nèi)對(duì)測(cè)試事件進(jìn)行 控制與觀察的服務(wù)邊界；? 在該點(diǎn)進(jìn)行控制和觀察的一組測(cè)試事件(ASPs或PDUS;? 對(duì)這些測(cè)試事件的控制和觀察是在SUT內(nèi)還是在測(cè)試系統(tǒng)中。如果IUT是運(yùn)輸層協(xié)議實(shí)體，那么? (n)ASP就是運(yùn)輸服務(wù)原語 TSP(Transport Service Primitives), UT 使用 的PCO就是運(yùn)輸服務(wù)訪問點(diǎn) TSAP? (n-1)ASP就是網(wǎng)絡(luò)服務(wù)原語 NSP(Network Service Primitives) , LT使用 的PCO就是網(wǎng)絡(luò)服務(wù)訪問點(diǎn) NSA