實驗 停止等待協(xié)議分析與協(xié)議模擬實現(xiàn)

1、實驗 停止等待協(xié)議分析與協(xié)議模擬實現(xiàn)一、實驗目的1了解停止等待協(xié)議的原理2掌握協(xié)議分析的方法和過程3通過程序模擬停止等待協(xié)議的工作過程二、實驗要求1根據(jù)例如，編寫停止等待協(xié)議的模擬程序，演示停止等待協(xié)議的工作過程。2撰寫實驗報告。三、協(xié)議概述如果鏈路是理想的傳輸信道，1所傳送的任何數(shù)據(jù)既不會出過失也不會喪失；2如果不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總是來得及收下，并及時上交主機。如果存在這樣的傳輸信道，數(shù)據(jù)鏈路層協(xié)議也是不需要的。信道不會出錯，而且接收方緩存的容量為無限大而永遠不會溢出；或接收速率與發(fā)送速率絕對精確相等。在上述兩個假定的情況下，數(shù)據(jù)鏈路層當然就不需要任何協(xié)議就可以保證數(shù)據(jù)傳

2、輸?shù)恼_。這就是說，傳輸數(shù)據(jù)的信道是不可靠的即不能保證所傳的數(shù)據(jù)不產(chǎn)生過失，并且還需要對數(shù)據(jù)的發(fā)送端進行流量控制。在大多數(shù)協(xié)議中，流量控制是一組過程，這組過程是用來告訴發(fā)送方在等待接收方的應答信號之前最多可以傳送多少數(shù)據(jù)。流量控制有兩個要點：1數(shù)據(jù)流不能使接收方過載。任何接收設備都有一個處理輸入數(shù)據(jù)的速率限制，并且存儲輸入數(shù)據(jù)的存儲器容量也是有限的。接收設備必須在到達這些限制之前通知發(fā)送設備并且請求發(fā)送設備發(fā)送較少的數(shù)據(jù)幀或是暫停一會兒。在使用輸入數(shù)據(jù)之前，需要對數(shù)據(jù)進行校驗和處理，因此，每個接收設備都有一塊存儲器，叫做緩沖區(qū)，用于存放未來得及處理的數(shù)據(jù)幀。如果緩沖區(qū)將滿，接收方也必須能夠通知

3、發(fā)送方暫停傳輸，直到接收方又能接收數(shù)據(jù)。2應答。隨著數(shù)據(jù)幀的到來，接收方對他們進行應答，可以每收到一幀給一個應答，也可以一次對假設干幀進行應答。如果一個幀到達時已經(jīng)被破壞，接收方發(fā)送一個否認應答幀NAK。在數(shù)據(jù)鏈路層，過失控制主要指錯誤檢測和重傳方法。在一個幀中出現(xiàn)任何一個錯誤，接收方就返回一個否認應答幀，出錯的幀就被發(fā)送方重新傳送。這個過程被稱作自動重復請求(ARQ)。數(shù)據(jù)被重傳的情況有三種：幀破壞、幀喪失和應答幀喪失。流量控制和過失控制是結合在一起實現(xiàn)的，共有兩種實現(xiàn)流量控制和過失控制的技術：停止等待協(xié)議和滑動窗口協(xié)議?！緢D解】【總結】使用的鏈路層傳輸控制協(xié)議發(fā)方：發(fā)送一個數(shù)據(jù)幀后，必須等

4、待收方確實認幀才可以發(fā)送下一個數(shù)據(jù)幀；為防止發(fā)送的數(shù)據(jù)或該數(shù)據(jù)確實認幀喪失，發(fā)方內(nèi)部設置一個定時器，當超過定時時間發(fā)方仍未收到確認幀時，發(fā)方重發(fā)該幀；為防止確認幀喪失而造成收方收到重復幀的情況，發(fā)方給每一個數(shù)據(jù)幀帶上一個序列號。1個比特位收方：在收方接收錯誤時，收方發(fā)一否認幀，要求發(fā)方重發(fā)該幀；收方收到相同的兩幀時，丟掉該數(shù)據(jù)幀并重發(fā)確認幀。【流程示意圖】發(fā)送數(shù)據(jù)包1接收正確認ACK發(fā)送數(shù)據(jù)包2重發(fā)數(shù)據(jù)包2發(fā)送數(shù)據(jù)包3接收負確認NAK接收正確認ACK接收正確認ACK接收數(shù)據(jù)包1正確發(fā)送正確認ACK接收數(shù)據(jù)包2錯誤發(fā)送負確認NAK接收數(shù)據(jù)包2正確發(fā)送正確認ACK接收數(shù)據(jù)包3正確發(fā)送正確認ACK發(fā)

5、送方接收方發(fā)送數(shù)據(jù)包0接收正確認ACK1發(fā)送數(shù)據(jù)包1超時重傳數(shù)據(jù)包1超時重傳數(shù)據(jù)包1接收正確認ACK0接收數(shù)據(jù)包0正確發(fā)送正確認ACK1接收數(shù)據(jù)包1正確發(fā)送正確認ACK0接收數(shù)據(jù)包1正確(拋棄)發(fā)送正確認ACK0發(fā)送方接收方發(fā)送數(shù)據(jù)包0超時超時圖a 停止等待協(xié)議的根本工作過程 圖b 數(shù)據(jù)包的喪失和確認信息的喪失示意圖四、協(xié)議分析可以用多種方法來表示一個有限狀態(tài)機，對協(xié)議進行描述。以下是在某種假定條件下的協(xié)議分析。1狀態(tài)遷移圖設甲、乙雙方進行半雙工通信，甲發(fā)信息幀，乙回送確認幀。雙方約定采用停止等待協(xié)議，因此甲方僅需用 1 比特來編號。下面將 0 號幀和 1 號幀分別記為 0 和 1 。當收到有

6、過失的幀時，那么丟棄此幀，同時不發(fā)任何應答幀。當收到無過失的幀但序號不正確時，要發(fā)確認幀，同時要丟棄此幀，不送主機。我們還假定收方在準備發(fā)送確認幀 ACK 時，暫不接收外面發(fā)來的幀。這樣，我們就得出甲乙雙方各自的有限狀態(tài)機，如下列圖所示。圖中橢圓形符號為狀態(tài)符號，其右方數(shù)字為狀態(tài)標號，橢圓形內(nèi)的字表示狀態(tài)的意義。帶箭頭的直線或弧線表示狀態(tài)的變遷，而直線或弧線旁邊的字代表自動機的輸入事件。例如，甲方自動機中的 “發(fā) 0 就是一個輸入事件。圖中在某些方面進行了一些簡化。例如，當乙方處于 “期望收 0 的狀態(tài)時，假設收到無過失的 1 幀，仍然應領先進入 “準備發(fā) ACK 狀態(tài)，然后才發(fā)出 ACK 。

7、但這里就將 “收 1 與 “發(fā) ACK 合并成為一個事件。其余局部不再詳述。2狀態(tài)遷移表方法除狀態(tài)轉移圖之外，還可用狀態(tài)遷移表又稱為判決表來表示自動機的工作。例如對甲方的自動機，可得出如下表所示的狀態(tài)變遷表。表中的工程代表 “新的狀態(tài)輸出 。例如在狀態(tài)為 x1 時，假設輸入為 “發(fā) 0 ，那么狀態(tài)從 x1 轉為 x2，同時輸出為 “ 0 幀 。當輸出為 “ 時表示無輸出。3混合描述方法比擬實用的方法是合并一些狀態(tài)，即考慮一些次要的細節(jié)。例如，甲方的狀態(tài) 1 和狀態(tài) 2，狀態(tài) 3和狀態(tài) 4 都可以合并，乙的狀態(tài) 1 和狀態(tài) 4，狀態(tài) 2 和狀態(tài) 3 也可進行合并。這樣可以用 3 個字符 XYZ

8、表示整個系統(tǒng)的狀態(tài)，其中 X0 或 1，對應于甲方準備發(fā) 0 或 1包括發(fā)完后等待 ACK 的狀態(tài)；Y0 或 1，對應于乙方期望收到 0 或 1；Z0、l、A或，對應于信道上傳送的是 0、1、ACK 或出現(xiàn)了過失包括喪失。這樣，就可得出 圖3-24 的有限狀態(tài)機。在弧線或直線旁邊注明的數(shù)字為狀態(tài)變遷的標號，其意義也注明在 圖3-24 的右方。假設系統(tǒng)一開始處在000狀態(tài)。這表示甲發(fā)完 0，乙期望收到 0，而信道上傳送的也是 0。在無過失的情況下，系統(tǒng)的狀態(tài)僅在 4 個狀態(tài)中循環(huán)：00001A11110A000 。從理論上講，應當共有 2 × 2 × 4 = 16 種不同的狀

9、態(tài)。去掉沒有意義的組合后，還剩下 10 種狀態(tài)，而導致狀態(tài)變遷的輸人事件共有 9 種 標號 0 8 。這種有限狀態(tài)機可幫助我們檢查協(xié)議是否正確。例如，檢查一下乙方會不會連續(xù)將兩個 0 號幀送交主機。這相當于檢查一下會不會出現(xiàn)這種情況，即在兩次出現(xiàn)狀態(tài)變遷 1 之間不出現(xiàn)狀態(tài)變遷 3 。仔細檢查 圖3-24 就可發(fā)現(xiàn)這種情況是不會發(fā)生的。同樣方法也可用來排除連續(xù)將兩個 1 號幀送交主機的可能。再檢查一下會不會發(fā)生甲方連續(xù)改變狀態(tài) 2 次 如從 0 到 1，再回到 0 而乙方的狀態(tài)未改變。這種情況相當于出現(xiàn)了未被發(fā)現(xiàn)的報文喪失?？梢钥闯?，這種情況也是不存在的。協(xié)議必須不出現(xiàn)死鎖。死鎖的出現(xiàn)是因為存

10、在著這樣的一種狀態(tài)子集，其特點是：從這一子集內(nèi)變遷到子集外是不可能的，而在這一子集內(nèi)狀態(tài)的變遷總是局限于子集內(nèi)的幾個狀態(tài)?？梢钥闯觯瑘D3-24 所示的自動機沒有死鎖現(xiàn)象。有限狀態(tài)機模型的缺點就是當描述比擬復雜的協(xié)議時，狀態(tài)的數(shù)目將急劇增加，以致很難用它來清晰地描述協(xié)議。五、協(xié)議驗證協(xié)議的 “驗證 一詞包括了“validation與“verification，包括了協(xié)議語法和語義的驗證。一般說來，協(xié)議的驗證包括以下幾個方面的內(nèi)容： l可達性reachability 驗證協(xié)議的各種可能狀態(tài)之間的可達關系。如果從狀態(tài) A 到狀態(tài) B 的變遷不可能發(fā)生直接或間接，那么從狀態(tài) A 到狀態(tài) B 是不可達的

11、。如果協(xié)議從初始狀態(tài)到某個狀態(tài)不可達，那么說明協(xié)議有錯誤。 2死鎖 最典型的死鎖是協(xié)議中各實體都處于這樣的一種等待狀態(tài)，即只有在“某一事件發(fā)生后才能做進一步的動作，但在該狀態(tài)下，這個“某一事件卻不可能發(fā)生。死鎖發(fā)生時，協(xié)議所處的狀態(tài)稱為死鎖狀態(tài)。 死鎖的另一種形式是協(xié)議處于無限的死循環(huán)中，而沒有別的事件可使協(xié)議從這一循環(huán)中解脫出來。例如，協(xié)議無限制地執(zhí)行超時重發(fā)操作，但總是收不到對方確實認信息。這種形式的死鎖稱為活鎖livelock，表示整個協(xié)議的狀態(tài)還是在變化的，不過不能脫離這種死循環(huán)狀態(tài)而已。3有界性檢驗協(xié)議的某些成分或參數(shù)例如通道容量、窗口大小是否有界。4完整性檢驗協(xié)議是否缺少應有的處理

12、，以及有無非期待的接收即錯收。5可恢復性或自同步性這是當出現(xiàn)過失后，協(xié)議能否在有限的步驟內(nèi)返回到正常狀態(tài)包括初始態(tài)下執(zhí)行。6狀態(tài)二義性一個進程在某一時刻只允許具有一個穩(wěn)定狀態(tài)。所謂穩(wěn)定狀態(tài)是指當通信雙方的通道為空時的進程狀態(tài)。假設在某一時刻進程可以有不只一個的穩(wěn)定狀態(tài)，那么稱該進程的狀態(tài)為二義狀態(tài)。7動作序列將協(xié)議的動作按執(zhí)行順序組合起來，即構成協(xié)議的動作序列。協(xié)議的動作序列集合又稱為協(xié)議的語言。檢查協(xié)議的動作序列，可以驗證協(xié)議有無錯誤動作或無用動作。8通道溢出檢查當通道中的數(shù)據(jù)已到達通道的最大容量后，是否有某個進程仍然試圖向通道中放入數(shù)據(jù)。六、參考代碼如下為Java參考代碼import ja

13、va.io.*;import .*;public class Sender extends Threadprivate String address = "127.0.0.1" private int port = 9878; public Sender() Socket client = null ; for(int i=0;i<10; i+) client = new Socket() ; Msg data = new Msg(i%2); InetSocketAddress isa = new InetSocketAddress(this.address,this

14、.port); try client.connect(isa,10000); ObjectOutputStream out = new ObjectOutputStream(client.getOutputStream(); out.writeObject(data); System.out.println("發(fā)送分組 "+data.getN_msg(); BufferedReader br = new BufferedReader(new InputStreamReader(client.getInputStream(); String str = br.readLine

15、(); if(str.equals("resend1") System.out.println("分組喪失，重發(fā)"); i-; out.flush(); out.close(); out = null ; data = null ; client.close();client = null ; continue; else if(str.equals("resend2") System.out.println("ACK喪失，重發(fā)"); i-; out.flush(); out.close(); out = null

16、 ; data = null ; client.close();client = null ; continue; else System.out.println("n"+"接收ACK"+data.getN_msg()+" 發(fā)送分組"+(data.getN_msg()+1)%2); out.flush(); out.close(); out = null ; data = null ; client.close();client = null ; catch(java.io.IOException e) System.out.prin

17、tln("Socket error!" ); System.out.println("IOException :" + e.toString(); try this.sleep(8000); catch (InterruptedException e) e.printStackTrace(); public static void main(String args) new Sender();import java.io.*;import .*;public class Recver extends Thread private boolean OutS

18、erver = false; private static ServerSocket server ; private static int ServerPort = 9878; public static void main(String args) (new Recver().start();public Recver() try server = new ServerSocket(ServerPort); catch(java.io.IOException e) System.out.println("Socket啟動有問題 !" ); System.out.prin

19、tln("IOException :" + e.toString(); public void run() Socket socket; ObjectInputStream in ; System.out.println("伺服器已啟動 !" ); while(!OutServer) socket = null; try synchronized(server) socket = server.accept(); socket.setSoTimeout(15000); in = new ObjectInputStream(socket.getInputS

20、tream(); Msg data = (Msg)in.readObject(); System.out.println("發(fā)送端正在發(fā)送的內(nèi)容"+data.getN_msg()+" 狀態(tài)："+data.getInfo(); if(data.getInfo().equals("losePackage") System.out.println("分組喪失"); DataOutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.write

21、Bytes("resend1"+'n'); dos.close(); else if(data.getInfo().equals("loseAck") System.out.println("ACK喪失"); DataOutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.writeBytes("resend2"+'n'); dos.close(); else System.out.println(&

22、quot;接收分組 "+data.getN_msg()+" 發(fā)送ACK "+data.getN_msg(); DataOutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.writeBytes("ok"+'n'); dos.close(); System.out.println(); in.close(); in = null ; socket.close(); catch(java.io.IOException e) System.out.println("Socket error !" ); System.out.println("IOException :" +