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

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

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

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

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

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

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

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

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

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

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

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

12、，以及有無非期待的接收即錯(cuò)收。5可恢復(fù)性或自同步性這是當(dāng)出現(xiàn)過失后，協(xié)議能否在有限的步驟內(nèi)返回到正常狀態(tài)包括初始態(tài)下執(zhí)行。6狀態(tài)二義性一個(gè)進(jìn)程在某一時(shí)刻只允許具有一個(gè)穩(wěn)定狀態(tài)。所謂穩(wěn)定狀態(tài)是指當(dāng)通信雙方的通道為空時(shí)的進(jìn)程狀態(tài)。假設(shè)在某一時(shí)刻進(jìn)程可以有不只一個(gè)的穩(wěn)定狀態(tài)，那么稱該進(jìn)程的狀態(tài)為二義狀態(tài)。7動(dòng)作序列將協(xié)議的動(dòng)作按執(zhí)行順序組合起來，即構(gòu)成協(xié)議的動(dòng)作序列。協(xié)議的動(dòng)作序列集合又稱為協(xié)議的語(yǔ)言。檢查協(xié)議的動(dòng)作序列，可以驗(yàn)證協(xié)議有無錯(cuò)誤動(dòng)作或無用動(dòng)作。8通道溢出檢查當(dāng)通道中的數(shù)據(jù)已到達(dá)通道的最大容量后，是否有某個(gè)進(jìn)程仍然試圖向通道中放入數(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啟動(dòng)有問題 !" ); System.out.prin

19、tln("IOException :" + e.toString(); public void run() Socket socket; ObjectInputStream in ; System.out.println("伺服器已啟動(dòng) !" ); 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 :" +