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

1、第二章 協(xié)議設計技術1.協(xié)議層次模型：（主要是描述n與n+1實體間的關系）l 實體(entity)：表示任何可以發(fā)送和接收信息的硬件或軟件進程。在許多情況下，實體就是一個特定的模塊。l n服務：兩個(n)實體在(n)協(xié)議的控制下的通信，使(n)層能夠向上一層(n+1)提供服務。這種服務就是(n)服務。 l 一個(n)實體向上一層所提供的服務由以下三部分構成： (1) (n)實體自己提供的某些功能。 (2) 從(n-1)層及其以下各層以及本地系統(tǒng)環(huán)境得到的服務。 (3) 通過與處在另一系統(tǒng)中的對等(n)實體的通信而得到的服務。 l PDU通常由2部分構成：用戶數(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)絡層 ：分組或包(packet) 運輸層 ：報文(Message)l SDU:OSI將層與層之間交換的數(shù)據(jù)的單元稱為服務數(shù)據(jù)單元SDU(Service Data Unit)。 一個(n)服務數(shù)據(jù)單元就是(n)服務所要傳送的邏輯數(shù)據(jù)單元。Ø S

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

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

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

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

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

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

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

10、容量 交換結點中的緩沖區(qū)（buffer） 處理機 Ø 擁塞控制的主要功能 防止網(wǎng)絡因過載而引起吞吐量下降和遲延增加 避免死鎖 在互相競爭的各用戶之間公平地分配資源 第三章 形式化描述技術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)轉換函數(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，當讀入空字符e時，有限狀態(tài)機不發(fā)生任何狀態(tài)轉移。Ø s0 Î S是初始狀態(tài)，F(xiàn)SM由此狀態(tài)開始接收輸入Ø F Í S是一個終態(tài)集（可空），F(xiàn)SM到達終態(tài)后不再接收輸入l 實例一：開關 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，可得出相應的I(tk)=pi, pj,。&

13、#216; O是輸出函數(shù)，也是一種變遷T到位置的映射。對于每一個tkT，可以得出相應的 O(tj)=pr, ps,。 Ø M = m1, m2, mn是標記(tokens, “旗標”或“托肯”)的集合l 變遷類型l 例子：l 例子二（行為性質與結構性質見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)等概念。 進程被當作一個黑盒子，我們只關心它的外顯行為。 事件則是發(fā)生于進程之間的交互原語的實例，是由相關進程共同執(zhí)行的。 事件門就是交互點，通信雙方利用事件門互相傳遞事件值。 Ø LOTOS規(guī)定了一組進程的重寫規(guī)則。進程間交互時發(fā)生的事件會使一個

19、進程被重寫為另外一個進程。系統(tǒng)狀態(tài)與事件的關系為樹形結構：樹結點表示狀態(tài)，樹的邊表示在某狀態(tài)下可能發(fā)生的事件。Ø 進程間的交互是全同步的: 所謂全同步是指只有在互相交互的各個進程都處于就緒狀態(tài)下，一個事件才有可能發(fā)生。 事件是原子的，即不能再細分為子事件的。各事件在時間上是互不重疊的。Ø Part與進程都可以逐步細分。 第五章 驗證技術1.一般性質和特殊性質：Ø 一般性質（著重理解：可達性、沒有死鎖、沒有活鎖）Ø 特殊性質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é)議、描述方法和可用的計算資源。特別是當系統(tǒng)狀態(tài)的數(shù)目非常大時會發(fā)生

21、狀態(tài)空間爆炸，應用范圍有限。 當狀態(tài)空間大于存儲空間時，全搜索策略將變成部分搜索，且不能保證檢查協(xié)議中最重要的部分，而搜索質量變得更差。 對于復雜的協(xié)議，窮盡性可達性分析的效果只能算作是一種低質量的部分搜索。 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)錯誤。Ø 缺點：必須能夠預先判斷出協(xié)議中的錯誤的大概位置，然而這很難預先做到；雖然這些方法能夠減小狀態(tài)空間的大小，但它們都沒有提供任何工具，將狀態(tài)空間的大小與可用內(nèi)存相匹配。Ø 使用這些方法時，有效搜索的部分狀態(tài)空間的大小是協(xié)議相關的，只能通過實驗確定，要想找到一種最優(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)的大小和復雜性無關，即使是無限大小的系統(tǒng)，也可以應用。因此，對于復雜的驗證問題，這種算法也許是唯一可用的方法。Ø 缺點： 它沒有明確的終止，無法判斷是否已經(jīng)訪問過系統(tǒng)的所有可達狀態(tài)； 由于沒有算法的終止，也就無法判斷是否已經(jīng)發(fā)現(xiàn)了系統(tǒng)的所有錯誤 因此只能發(fā)現(xiàn)協(xié)議中的錯誤，而不能證明協(xié)議中沒有

24、錯誤。 第七章 一致性測試技術(需要看ppt p33，掌握9個圖+相應的描述)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í)行的服務原語和LT執(zhí)行的服務原語來描述。在這里，LT相當于低層服務提供者。 n 圖三：分布式測試法(Distributed Method) Ø 在這種

25、方法中，IUT和UT處于同一臺機器中，而LT則分布在其它機器中。Ø LT和IUT之間利用(n-1)層服務交換報文(可以在線測試)。Ø 與本地方法相比，LT和IUT之間的接口PCO從IUT中轉換到LT中，LT相當于(n-1)層服務的使用者Ø 測試協(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)層服務來傳送。圖 (c)所示的是帶內(nèi)傳送法。Ø 同樣，分布式測試法的測試例不能用于協(xié)同測試法。 n 圖五：遠程測試法(Remote Method)ØØ 這種測試方法中沒有UT，因此也不存在UT和LT之間的協(xié)同問題。Ø 在這種方法中，測試例完全用(n-1)ASP描述。Ø 遠程方法比較適用于

27、被動式協(xié)議實現(xiàn)或服務型協(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)層服務直接傳送給渡船軟件。Ø 最大優(yōu)點是：由于UT和LT處于同一臺機器中，測試協(xié)同過程像本地方法一樣容易實現(xiàn)，被測試系統(tǒng)中只要增加簡單的渡船軟件即可。Ø 只是協(xié)同測試法的一種變種，是協(xié)同測試法在實現(xiàn)技術上的一種改進，它們之間沒有本質區(qū)別。n 圖八、