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

1、第二章 協(xié)議設(shè)計技術(shù)1.協(xié)議層次模型：（主要是描述n與n+1實體間的關(guān)系）l 實體(entity)：表示任何可以發(fā)送和接收信息的硬件或軟件進程。在許多情況下，實體就是一個特定的模塊。l n服務(wù)：兩個(n)實體在(n)協(xié)議的控制下的通信，使(n)層能夠向上一層(n+1)提供服務(wù)。這種服務(wù)就是(n)服務(wù)。 l 一個(n)實體向上一層所提供的服務(wù)由以下三部分構(gòu)成： (1) (n)實體自己提供的某些功能。 (2) 從(n-1)層及其以下各層以及本地系統(tǒng)環(huán)境得到的服務(wù)。 (3) 通過與處在另一系統(tǒng)中的對等(n)實體的通信而得到的服務(wù)。 l PDU通常由2部分構(gòu)成：用戶數(shù)據(jù)和協(xié)議控制信息PCI(Proto

2、col Control Information)。PCI一般作為首部加在用戶數(shù)據(jù)的前面，但有時也可作為尾部加在用戶數(shù)據(jù)的后面，例如檢驗和(checksum)常放在尾部。 兩種類型：數(shù)據(jù)PDU 控制PDU，不攜帶用戶數(shù)據(jù)。 在不同的協(xié)議層次中，PDU還有一些其它的表示法。 物理層：比特(bit)； 數(shù)據(jù)鏈路層：幀(frame)或信元(cell)；網(wǎng)絡(luò)層 ：分組或包(packet) 運輸層 ：報文(Message)l SDU:OSI將層與層之間交換的數(shù)據(jù)的單元稱為服務(wù)數(shù)據(jù)單元SDU(Service Data Unit)。 一個(n)服務(wù)數(shù)據(jù)單元就是(n)服務(wù)所要傳送的邏輯數(shù)據(jù)單元。Ø S

3、DU就是數(shù)據(jù)PDU中的用戶數(shù)據(jù)，但不一定是一一對應(yīng)關(guān)系。 Ø 可以是多個SDU合成為一個PDU(稱為“拼裝”)，也可以是將一個SDU劃分為幾個PDU(稱為“分段”)。 Ø PDU的裝配與拆裝: 在發(fā)送數(shù)據(jù)之前，(n)協(xié)議需要裝配PDU，即按照給定格式附上協(xié)議控制信息PCI。對于接收后的PDU要對之拆裝，拆出PCI。 l SAP:同一系統(tǒng)中相鄰兩層的實體進行交互(即交換信息)之處，通常稱為服務(wù)訪問點SAP (Serivce Access Point) l SP（服務(wù)原語）：在進行交互時所要交換的一些必須信息(或命令)稱為服務(wù)原語(Service Primitives)，以表明

4、需要本地的或遠端的對等實體做哪些事情。每層均可使用的4 種服務(wù)原語：（P17）Ø Request (請求): 一個實體希望得到某種服務(wù) Ø Indication (指示)：把關(guān)于某一事件的信息告訴某一實體 Ø Response (響應(yīng))：一個實體愿意響應(yīng)某一事件 Ø Confirm (證實)：把一個實體的服務(wù)請求加以確認并告訴它 過程描述： ：用戶A先發(fā)出Request原語，以調(diào)用服務(wù)提供者的某個進程 To ：Request原語就引起系統(tǒng)A的(n)實體向某對等實體發(fā)出一個協(xié)議數(shù)據(jù)單元PDU ：當(dāng)系統(tǒng)B的(n)實體收到這個PDU后，就向其服務(wù)用戶發(fā)出Ind

5、ication原語 To ：通常對應(yīng)于： (1)表示系統(tǒng)B的(n)服務(wù)用戶應(yīng)當(dāng)調(diào)用一個適當(dāng)?shù)膮f(xié)議過程，或者(2)表示服務(wù)提供者已經(jīng)調(diào)用了一個必要的過程。 ：接著，服務(wù)用戶B發(fā)出Response原語，用以完成剛才Indication原語所調(diào)用的過程 To ：這時，協(xié)議又產(chǎn)生一個協(xié)議數(shù)據(jù)單元PDU，通過網(wǎng)絡(luò)到達系統(tǒng)A。 ：最后，系統(tǒng)A的(n)實體發(fā)出Confirm原語，表示完成了先前由服務(wù)用戶A發(fā)出的Request原語所調(diào)用的過程。 2.連接于非連接：l 面向連接的(connection-oriented) 服務(wù)Ø 三個階段：連接建立、數(shù)據(jù)傳輸和連接釋放Ø 在傳送數(shù)據(jù)時是按序傳

6、送的Ø 網(wǎng)絡(luò)層：虛電路服務(wù)Ø 比較適合于在一定期間內(nèi)要向同一目的地發(fā)送許多報文的情況Ø 永久虛電路：適于兩個用戶需要經(jīng)常進行頻繁的通信的情況 l 無連接的(connectionless)服務(wù)Ø 不能保證報文的丟失、重復(fù)、失序Ø 三種類型：數(shù)據(jù)報(datagram)、證實交付(confirmed delivery, 可靠的數(shù)據(jù)報)、請求回答(request-reply) 數(shù)據(jù)報：不需要接收端做任何響應(yīng)。盡最大努力交會(best effort delivery) 證實交付：又稱“可靠的數(shù)據(jù)報”。對每一個報文產(chǎn)生一個證實給發(fā)方用戶，不過這個證實不是來

7、自接收端的用戶而是來自提供服務(wù)的層 請求回答：收端用戶每收到一個報文，就向發(fā)端用戶發(fā)送一個應(yīng)答報文。適于“事務(wù)(transaction)”中的通信。Ø 適于傳送少量零星的報文3.通道：(基于三種通道的FSM模型)l 主要有三類：Ø 空通道(empty channels) 報文的發(fā)送時間和延時時間為0的通道 報文一旦從輸入端進入就立即在輸出端出現(xiàn) Ø 非緩沖通道(non-buffered channels) 在任何時刻，最多只有一個正在傳送中的報文的通道 Ø 緩沖通道(buffered channels) 允許有多個報文停留的通道l 形成方式和隊列性質(zhì)（次

8、要）（p12）4.幾種控制：l 差錯控制Ø 主要概念 在網(wǎng)絡(luò)上進行通信會造成數(shù)據(jù)PDU以一定的概率被損壞、丟失、重復(fù)和亂序。協(xié)議的差錯控制功能負責(zé)這些差錯的檢測及恢復(fù)，保證數(shù)據(jù)的可靠傳輸。 n層協(xié)議的差錯控制機制與它的服務(wù)提供者提供的(n-1)通道的性質(zhì)有很大關(guān)系，(n-1)通道提供的數(shù)據(jù)通道的可靠性越高，則n層協(xié)議需實現(xiàn)的差錯控制機制則越少。 Ø 主要技術(shù)有：（檢錯重傳或丟棄、糾錯） 確認 (Ack) 計時器 (Timer) 重傳 (Retransmit) 序號 (Sequence Number)Ø 差錯控制的層次關(guān)系 從通信和信息處理的角度看，物理層、數(shù)據(jù)鏈路

9、層、網(wǎng)絡(luò)層和運輸層屬于面向通信部分，因而網(wǎng)絡(luò)中的絕大部分差錯控制功能要在這幾層中實現(xiàn)。 處于不同層次的協(xié)議所采用的差錯控制機制是有差別的。l 流量控制流量控制是指“收端控制發(fā)端的發(fā)送數(shù)據(jù)速率以使收端來得及接收，并且使網(wǎng)絡(luò)不致過載” Ø Why? 接收方的接收能力有限 緩存不夠 處理能力不夠Ø Examples: Stop and Wait Sliding window l 擁塞控制Ø 在某段時間，若對網(wǎng)絡(luò)中某一資源的需求超過了該資源所能提供的可用部分，網(wǎng)絡(luò)的性能就要變壞。這種情況就叫做擁塞(congestion)。 Ø 資源(resources)： 鏈路

10、容量 交換結(jié)點中的緩沖區(qū)（buffer） 處理機 Ø 擁塞控制的主要功能 防止網(wǎng)絡(luò)因過載而引起吞吐量下降和遲延增加 避免死鎖 在互相競爭的各用戶之間公平地分配資源 第三章 形式化描述技術(shù)1.FSM：l 定義FSM = (S, s0, I, d, F), whereØ S = s0, s1, , sn: 有限狀態(tài)集合。在任一確定時刻，F(xiàn)SM只能處于一個確定的狀態(tài)si。Ø I = a0, a1, , am: 有限輸入字符集合。在任一確定的時刻，F(xiàn)SM只能接收一個確定的輸入aj。Ø d ：S ´ I ® S是狀態(tài)轉(zhuǎn)換函數(shù)，如果在某一確定的時

11、刻，F(xiàn)SM處于某一狀態(tài)si Î S, 并接收一個輸入字符ajÎ I，那么下一時刻將處于一個確定的狀態(tài) s´ = d(si , aj) Î S。在這里規(guī)定，s = d(s , e)，即對任何狀態(tài)s，當(dāng)讀入空字符e時，有限狀態(tài)機不發(fā)生任何狀態(tài)轉(zhuǎn)移。Ø s0 Î S是初始狀態(tài)，F(xiàn)SM由此狀態(tài)開始接收輸入Ø F Í S是一個終態(tài)集（可空），F(xiàn)SM到達終態(tài)后不再接收輸入l 實例一：開關(guān) l 實例二：電話IDLEDIALINGRINGINGPATHACTIVEOn-hook-IDLE-IDLEOff-hookSend Dial

12、 Tone,DIALING-PATH ACTIVE-Dial-digit(Note 1)-DIALING PATH ACTIVE-Call-AlertRing Phone,RINGING/2.PETRI NET:l 概念Petri網(wǎng)可定義為一個4元組 (P, T , I, O)，其中：Ø P = p1, p2, pn是位置(places)的有限集合；Ø T = t1, t2, tm是變遷(transitions)的有限集合，且T與P不相交，即TP = Æ。Ø I是輸入函數(shù)，是變遷T到位置的映射。對于每一個tkT，可得出相應(yīng)的I(tk)=pi, pj,。&

13、#216; O是輸出函數(shù)，也是一種變遷T到位置的映射。對于每一個tkT，可以得出相應(yīng)的 O(tj)=pr, ps,。 Ø M = m1, m2, mn是標(biāo)記(tokens, “旗標(biāo)”或“托肯”)的集合l 變遷類型l 例子：l 例子二（行為性質(zhì)與結(jié)構(gòu)性質(zhì)見p58）第四章 形式描述語言（三選二）1.SDL:l 系統(tǒng)描述（p84）SYSTEM sample; 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; EN

14、DCHANNEL C2; CHANNEL C3 FROM B2 TO B1 WITH S4; ENDCHANNEL C3; CHANNEL C4 FROM B2 TO ENV WITH S5; ENDCHANNEL C4; BLOCK B1 REFERENCED; BLOCK B2 REFERENCED;ENDSYSTEM sample;(b) 用SDL/PR表示的系統(tǒng)例子l 功能塊描述：（p85）BLOCK B1; SIGNAL Sa, Sb; SIGNALROUTE R1 FROM ENV TO P1 WITH S1; SIGNALROUTE R2 FROM ENV TO P2 WITH

15、S2; SIGNALROUTE R3 FROM P1 TO ENV WITH S3; SIGNALROUTE R4 FROM ENV TO P2 WITH S4; SIGNALROUTE R5 FROM P1 TO P2 WITH Sa; FROM P2 TO P1 WITH Sb; CONNECT C1 AND R1, R2; CONNECT C2 AND R3; CONNECT C3 AND R4; PROCESS P1 REFERENCED; PROCESS P2 REFERENCED;ENDBLOCK B1;(b) 用SDL/PR表示的功能塊例子l 進程描述：（p87）l 宏定義2.E

16、STELLE:l 注意點：Ø 類別為systemprocess的模塊的子模塊的類別可以是process或activity；而類別為systemactivity的模塊的子模塊的類別必須是activity。 Ø 類別為process的模塊的子模塊的類別必須是process；同樣，類別為activity的模塊的子模塊的類別必須是activity。 l 兩種并行方式：Ø 異步并行(asynchronous parallelism)。異步并行性只能存在于不同系統(tǒng)模塊之間 Ø 同步并行(synchronous parallelism)。同步并行性只能存在于一個系統(tǒng)模

17、塊內(nèi)。l 例子一：模塊嵌套舉例l 例子二：滑動窗口協(xié)議l 交互點的位置，可以將IP分為兩種：Ø 內(nèi)部交互點，如p19,p20, p21,UX,UY Ø 外部交互點(external IP)。其余的都為外部交互點l 優(yōu)先級：Ø 如果一個系統(tǒng)模塊的類型為systemprocess，則該系統(tǒng)模塊內(nèi)的各個子模塊可以并行執(zhí)行，而父模塊則優(yōu)先于子模塊執(zhí)行。 Ø 如果一個系統(tǒng)模塊的類型為systemactivity，則該系統(tǒng)模塊內(nèi)的各個子模塊只能串行運行，具體哪個子模塊執(zhí)行則是隨機選擇的，父模塊仍然優(yōu)先于子模塊執(zhí)行。 3.LOTOS（傳說不會考）Ø 在LOT

18、OS中，信息系統(tǒng)或系統(tǒng)都是從整體上體現(xiàn)信息活動的。例如信息的傳輸、加工、存儲等操作都是系統(tǒng)的信息活動。Ø 而系統(tǒng)則由一組互相交互的部分(Part)所組成。在Part中發(fā)出的信息活動稱為動作(Action)。涉及到兩個或多個Part的共同動作則稱為交互。 Ø 為了說明一個系統(tǒng)，LOTOS采用了進程、事件和事件門(gate)等概念。 進程被當(dāng)作一個黑盒子，我們只關(guān)心它的外顯行為。 事件則是發(fā)生于進程之間的交互原語的實例，是由相關(guān)進程共同執(zhí)行的。 事件門就是交互點，通信雙方利用事件門互相傳遞事件值。 Ø LOTOS規(guī)定了一組進程的重寫規(guī)則。進程間交互時發(fā)生的事件會使一個

19、進程被重寫為另外一個進程。系統(tǒng)狀態(tài)與事件的關(guān)系為樹形結(jié)構(gòu)：樹結(jié)點表示狀態(tài)，樹的邊表示在某狀態(tài)下可能發(fā)生的事件。Ø 進程間的交互是全同步的: 所謂全同步是指只有在互相交互的各個進程都處于就緒狀態(tài)下，一個事件才有可能發(fā)生。 事件是原子的，即不能再細分為子事件的。各事件在時間上是互不重疊的。Ø Part與進程都可以逐步細分。 第五章 驗證技術(shù)1.一般性質(zhì)和特殊性質(zhì)：Ø 一般性質(zhì)（著重理解：可達性、沒有死鎖、沒有活鎖）Ø 特殊性質(zhì)2.可達性搜索法（三選一）l 窮盡性可達性分析算法(exhaustive or full search)start() W = 初始狀

20、態(tài); /* 工作集：分析的狀態(tài) */ A = ; /* 已分析過的狀態(tài) */ analyze(); analyze() /* 全局搜索 */ if (W為空) return; q = 取自W的元素； 將q加入到A中 if (q是錯誤狀態(tài)) report_error(); /* 報告錯誤 */ else for (q的每一個后繼狀態(tài)s) if (s不在A或W中) 把s加入到W中；analyze(); 從W中刪除q； Ø 優(yōu)點：驗證覆蓋范圍全面，可以證明協(xié)議中沒有錯誤。Ø 缺點： 算法能分析的最大狀態(tài)數(shù)目依賴于協(xié)議、描述方法和可用的計算資源。特別是當(dāng)系統(tǒng)狀態(tài)的數(shù)目非常大時會發(fā)生

21、狀態(tài)空間爆炸，應(yīng)用范圍有限。 當(dāng)狀態(tài)空間大于存儲空間時，全搜索策略將變成部分搜索，且不能保證檢查協(xié)議中最重要的部分，而搜索質(zhì)量變得更差。 對于復(fù)雜的協(xié)議，窮盡性可達性分析的效果只能算作是一種低質(zhì)量的部分搜索。 l 受控部分搜索算法(controlled partial search)/* start()與算法5.1中的相同 */analyze() /* 部分搜索 */ if (W為空) return; q = 取自W的元素； 將q加入到A中 if (q是錯誤狀態(tài)) report_error(); /* 報告錯誤 */ else for (q的某些后繼狀態(tài)s) if (s不在A或W中) 把s加入

22、到W中；analyze(); 從W中刪除q； Ø 受控部分搜索算法的目的是證明錯誤的存在，而不是證明沒有錯誤。Ø 優(yōu)點：與窮盡性可達性分析相比，這種算法可以有效地解決狀態(tài)空間爆炸問題，同時利用有限的資源來驗證協(xié)議的最重要的部分，從而最大限度地發(fā)現(xiàn)錯誤。Ø 缺點：必須能夠預(yù)先判斷出協(xié)議中的錯誤的大概位置，然而這很難預(yù)先做到；雖然這些方法能夠減小狀態(tài)空間的大小，但它們都沒有提供任何工具，將狀態(tài)空間的大小與可用內(nèi)存相匹配。Ø 使用這些方法時，有效搜索的部分狀態(tài)空間的大小是協(xié)議相關(guān)的，只能通過實驗確定，要想找到一種最優(yōu)的方法，必須按照不同的選擇策略進行多次驗證。

23、l 隨機模擬算法(random simulation)。 analyze() /* 隨機模擬 */ q = 初始狀態(tài); while (1) if (q = 錯誤狀態(tài)) report_error(); q = 初始狀態(tài); else q = q的一個后繼狀態(tài)；Ø 優(yōu)點：隨機模擬算法與協(xié)議系統(tǒng)的大小和復(fù)雜性無關(guān)，即使是無限大小的系統(tǒng)，也可以應(yīng)用。因此，對于復(fù)雜的驗證問題，這種算法也許是唯一可用的方法。Ø 缺點： 它沒有明確的終止，無法判斷是否已經(jīng)訪問過系統(tǒng)的所有可達狀態(tài)； 由于沒有算法的終止，也就無法判斷是否已經(jīng)發(fā)現(xiàn)了系統(tǒng)的所有錯誤 因此只能發(fā)現(xiàn)協(xié)議中的錯誤，而不能證明協(xié)議中沒有

24、錯誤。 第七章 一致性測試技術(shù)(需要看ppt p33，掌握9個圖+相應(yīng)的描述)l 9個圖n 圖一：一致性測試模型n 圖二：本地測試法(Local Mehtod) Ø 在這種方法中，LT，UT，IUT同處于一臺機器中，測試不需要低層通信系統(tǒng)的支持。Ø 由于UT和LT可以在同一個程序中實現(xiàn)，因此，UT和LT的測試協(xié)同過程TCP(Test Coordinate Procedure)比較容易實現(xiàn)。Ø 測試例用UT執(zhí)行的服務(wù)原語和LT執(zhí)行的服務(wù)原語來描述。在這里，LT相當(dāng)于低層服務(wù)提供者。 n 圖三：分布式測試法(Distributed Method) Ø 在這種

25、方法中，IUT和UT處于同一臺機器中，而LT則分布在其它機器中。Ø LT和IUT之間利用(n-1)層服務(wù)交換報文(可以在線測試)。Ø 與本地方法相比，LT和IUT之間的接口PCO從IUT中轉(zhuǎn)換到LT中，LT相當(dāng)于(n-1)層服務(wù)的使用者Ø 測試協(xié)同過程TCP隱含在測試例中，測試同步問題由UT和LT的操作者來實現(xiàn)。Ø 適用于本地方法的測試例必須改寫后才能用于分布式測試法。 n 圖四：協(xié)調(diào)測試法(Coordination Mehtod) Ø 協(xié)同測試法和分布式測試法的根本區(qū)別在于協(xié)同測試法引入測試管理協(xié)議TMP(Test Management Pr

26、otocol)。Ø 有了TMP，UT和LT就通過交換TM-PDU實現(xiàn)測試協(xié)同過程。交換TM-PDU有兩種方法： 帶內(nèi)傳送法，即將TM-PDU作為(n)ASP的用戶數(shù)據(jù)傳送給IUT，IUT再將它傳送給LT； 帶外傳送法，即將TM-PDU直接利用(n-1)層服務(wù)來傳送。圖 (c)所示的是帶內(nèi)傳送法。Ø 同樣，分布式測試法的測試例不能用于協(xié)同測試法。 n 圖五：遠程測試法(Remote Method)ØØ 這種測試方法中沒有UT，因此也不存在UT和LT之間的協(xié)同問題。Ø 在這種方法中，測試例完全用(n-1)ASP描述。Ø 遠程方法比較適用于

27、被動式協(xié)議實現(xiàn)或服務(wù)型協(xié)議實體的測試。 n 圖六、七：渡船測試法(Ferry Method)（重點之中的重點，綜合性較強）Ø 將UT從被測系統(tǒng)中移到LTØ 所在系統(tǒng)中，從而可將UT和LT合在一個程序中實現(xiàn)，因而有本地測試法的優(yōu)點。 Ø 在被測試系統(tǒng)中需要一個代替UT的軟件，即渡船軟件。UT發(fā)送給IUT的(n)ASP和UT從IUT獲取的(n)ASP通過這個渡船軟件進行。 Ø 與協(xié)同測試法一樣，根據(jù)UT和渡船軟件之間交換F-PDU方法的不同，渡船測試法又可分為帶內(nèi)傳送法 (圖 (a)和帶外傳送法(圖 (b) 。 Ø 在帶內(nèi)傳送法中，UT將測試事件通過LT，再通過IUT傳送給渡船軟件。Ø 帶外傳送法中，UT通過(n-1)層服務(wù)直接傳送給渡船軟件。Ø 最大優(yōu)點是：由于UT和LT處于同一臺機器中，測試協(xié)同過程像本地方法一樣容易實現(xiàn)，被測試系統(tǒng)中只要增加簡單的渡船軟件即可。Ø 只是協(xié)同測試法的一種變種，是協(xié)同測試法在實現(xiàn)技術(shù)上的一種改進，它們之間沒有本質(zhì)區(qū)別。n 圖八、