滑動(dòng)窗口的仿真協(xié)議

1、 計(jì)算機(jī)網(wǎng)絡(luò)課程設(shè)計(jì)書 學(xué) 院計(jì)算機(jī)與信息工程學(xué)院專 業(yè)網(wǎng)絡(luò)工程課程名稱計(jì)算機(jī)網(wǎng)絡(luò)題 目滑動(dòng)窗口協(xié)議仿真完成期限自2015年6月23日至2015年6月29日共1周內(nèi)容及任務(wù)1、 項(xiàng)目的目的 掌握滑動(dòng)窗口協(xié)議的工作原理，并能夠用所學(xué)計(jì)算機(jī)高級(jí)語言進(jìn)行編程模擬其運(yùn)行過程;培養(yǎng)學(xué)生的動(dòng)手實(shí)踐和思考能力。二，項(xiàng)目任務(wù)的主要內(nèi)容和要求 (1)本次設(shè)計(jì)任務(wù)是根據(jù)滑動(dòng)窗口協(xié)議的工作原理，在Visual C+ 6.0的平臺(tái)上用C+語言編寫一個(gè)基本TCP滑動(dòng)窗口協(xié)議的模擬程序。 (2)要求該程序能夠?qū)崿F(xiàn)滑動(dòng)窗口協(xié)議的發(fā)送和接收數(shù)據(jù)幀功能，在此功能上體現(xiàn)滑動(dòng)窗口協(xié)議的運(yùn)作。 (3) 程序按照滑動(dòng)窗口協(xié)議實(shí)現(xiàn)端對(duì)端

2、的數(shù)據(jù)傳送。包括協(xié)議的各種策略，如包丟失、停等應(yīng)答、超時(shí)等都應(yīng)有所仿真實(shí)現(xiàn)；(4) 顯示數(shù)據(jù)傳送過程中的各項(xiàng)具體數(shù)據(jù)。雙方幀的個(gè)數(shù)變化，幀序號(hào)，發(fā)送和接受速度，暫?；蛑貍魈崾镜?；3、 項(xiàng)目設(shè)計(jì)（研究）思路 (1) 查閱相關(guān)資料，理解滑動(dòng)窗口協(xié)議的工作原理； (2) 設(shè)計(jì)滑動(dòng)窗口協(xié)議實(shí)現(xiàn)端對(duì)端數(shù)據(jù)傳送的功能流程圖； (3) 編寫代碼實(shí)現(xiàn)滑動(dòng)窗口協(xié)議工作的模擬程序，包括包丟失、停等應(yīng)答、超時(shí)等； (4) 測(cè)試程序功能的實(shí)現(xiàn)情況。4、 具體成果形式和要求 (1)滑動(dòng)窗口協(xié)議實(shí)現(xiàn)端對(duì)端數(shù)據(jù)傳送的模擬程序。 (2)按照要求撰寫課程設(shè)計(jì)報(bào)告并準(zhǔn)備答辯。進(jìn)度安排起止日期工作內(nèi)容2015.6.23-2015.

3、6.24了解網(wǎng)絡(luò)協(xié)議編程的基本知識(shí)；2015.6.25-2015.6.26了解滑動(dòng)窗口協(xié)議的工作機(jī)制；2015.6.27-2015.6.28使用編程語言編寫一個(gè)滑動(dòng)窗口協(xié)議的模擬程序，按要求實(shí)現(xiàn)程序。2015.6.29最后匯總，調(diào)試，答辯主要參考資料1 謝希仁. 計(jì)算機(jī)網(wǎng)絡(luò)M. 4版. 北京:電子工業(yè)出版社, 2003.2 李仁發(fā).何彥. 基于虛擬實(shí)驗(yàn)方法的滑動(dòng)窗口協(xié)議分析J. 系統(tǒng)仿真學(xué)報(bào). 2002. 8 (14) ; 1026 - 1063.3 李建中,張冬冬. 滑動(dòng)窗口規(guī)模的動(dòng)態(tài)調(diào)整算法J. 軟件學(xué)報(bào). 2004. 12 (15) : 1800 - 1814.4 王栩,李建中,王偉平.

4、 基于滑動(dòng)窗口的數(shù)據(jù)流壓縮技術(shù)及連續(xù)查詢處理方法 J . 計(jì)算機(jī)研究與發(fā)展. 2004. 10 (41) : 1639- 1644.5 特南鮑姆. 計(jì)算機(jī)網(wǎng)絡(luò)（第四版）. 清華出版社指導(dǎo)教師意見（簽字）： 年月日系（教研室）主任意見（簽字）： 年月日 計(jì)算機(jī)網(wǎng)絡(luò)課程設(shè)計(jì)說明書（封面） 學(xué)院名稱： 計(jì)算機(jī)與信息工程學(xué)院 班級(jí)名稱： 網(wǎng)絡(luò)工程一班 學(xué)生姓名： 學(xué) 號(hào)： 201321 題 目： 滑動(dòng)窗口協(xié)議仿真 指導(dǎo)教師姓 名： 邵雪梅 起止日期： 2015.6.232015.6.29 第一部分：正文部分一，選題背景 早期的網(wǎng)絡(luò)通信中，通信雙方不會(huì)考慮網(wǎng)絡(luò)的擁擠情況直接發(fā)送數(shù)據(jù)。由于大家不知道網(wǎng)絡(luò)擁

5、塞狀況，一起發(fā)送數(shù)據(jù)，導(dǎo)致中間結(jié)點(diǎn)阻塞掉包，誰也發(fā)不了數(shù)據(jù)。在數(shù)據(jù)傳輸過程中，我們總是希望數(shù)據(jù)傳輸?shù)母煲恍?，但如果發(fā)送方把數(shù)據(jù)發(fā)送的過快，接收方就可能來不及接收，這就造成數(shù)據(jù)的丟失。因此就有了滑動(dòng)窗口機(jī)制來解決這些問題。早期我們使用的是1bit滑動(dòng)窗口協(xié)議，一次只發(fā)送一個(gè)幀，等收到ack確認(rèn)才發(fā)下一個(gè)幀，這樣對(duì)信道的利用率太低了。因此提出了一種采用累積確認(rèn)的連續(xù)ARQ協(xié)議，接收方不必對(duì)收到的幀逐個(gè)發(fā)送ack確認(rèn)，而是收到幾個(gè)幀后，對(duì)按序到達(dá)的最后一個(gè)幀發(fā)送ack確認(rèn)。同1bit滑動(dòng)窗口協(xié)議相比，大大減少了ack數(shù)量，并消除了延遲ack對(duì)傳輸效率的影響。但是，這會(huì)產(chǎn)生一個(gè)新的問題，如果發(fā)送方發(fā)

6、送了5個(gè)幀，而中間的第3個(gè)幀丟失了。這時(shí)接收方只能對(duì)前2個(gè)幀發(fā)出確認(rèn)。發(fā)送方無法知道后面三個(gè)幀的下落，只好把后面的3個(gè)幀再重傳一次，這就是回退N協(xié)議。為了解決這個(gè)問題，又提出了選擇重傳協(xié)議。當(dāng)接收方發(fā)現(xiàn)某幀出錯(cuò)后，繼續(xù)接受后面送來的正確的幀，只是不交付它們，存放在自己的緩沖區(qū)中，并且要求發(fā)送方重傳出錯(cuò)的那一幀。一旦收到重傳來的幀后，就可以將存于緩沖區(qū)中的其余幀一并按正確的順序遞交給主機(jī)。本文主要介紹如何根據(jù)滑動(dòng)窗口協(xié)議的原理，在Visual C+的平臺(tái)上設(shè)計(jì)一個(gè)滑動(dòng)窗口協(xié)議模擬程序，并最終使該程序得以實(shí)現(xiàn)。本次程序設(shè)計(jì)分兩部分：第一部分是發(fā)送方，第二部分是接收方。通過發(fā)送方和接收方之間的數(shù)據(jù)幀

7、傳輸模擬，學(xué)習(xí)滑動(dòng)窗口協(xié)議控制流量的原理和方法，以及滑動(dòng)窗口協(xié)議的工作機(jī)制。二、設(shè)計(jì)理念2.1 滑動(dòng)窗口協(xié)議工作原理TCP滑動(dòng)窗口用來暫存兩臺(tái)計(jì)算機(jī)間要傳送的數(shù)據(jù)分組。每臺(tái)運(yùn)行TCP協(xié)議的計(jì)算機(jī)有兩個(gè)滑動(dòng)窗口：一個(gè)用于數(shù)據(jù)發(fā)送，另一個(gè)用于數(shù)據(jù)接收。發(fā)送端待發(fā)數(shù)據(jù)分組在緩沖區(qū)排隊(duì)等待送出。被滑動(dòng)窗口框入的分組，是可以在未收到接收確認(rèn)的情況下最多送出的部分?；瑒?dòng)窗口左端標(biāo)志X的分組，是已經(jīng)被接收端確認(rèn)收到的分組。隨著新的確認(rèn)到來，窗口不斷向右滑動(dòng)?；瑒?dòng)窗口算法工作過程如下：首先，發(fā)送方為每1幀賦一個(gè)序號(hào)（sequence number），記作SeqNum?，F(xiàn)在，我們忽略SeqNum是由有限大小的頭

8、部字段實(shí)現(xiàn)的事實(shí)，而假設(shè)它能無限增大。發(fā)送方維護(hù)3個(gè)變量：發(fā)送窗口大?。╯end window size），記作SWS，給出發(fā)送方能夠發(fā)送但未確認(rèn)的幀數(shù)的上界；LAR表示最近收到的確認(rèn)幀（last acknowledgement received）的序號(hào)；LFS表示最近發(fā)送的幀（last frame sent）的序號(hào)，發(fā)送方還維持如下的不變式：LAR-LFSSWS。 2-1滑動(dòng)窗口協(xié)議工作圖窗口協(xié)議算法有三個(gè)功能：l 在不可靠鏈路上可靠地傳輸幀l 保持幀的傳輸順序l 支持流量控制2.2 選擇重傳協(xié)議在選擇重傳協(xié)議中，當(dāng)接收方發(fā)現(xiàn)某幀出錯(cuò)后，其后繼續(xù)送來的正確的幀雖然不能立即遞交給接收方的高層，

9、但接收方仍可收下來，存放在一個(gè)緩沖區(qū)中，同時(shí)要求發(fā)送方重新傳送出錯(cuò)的那一幀。一旦收到重新傳來的幀后，就可以原已存于緩沖區(qū)中的其余幀一并按正確的順序遞交高層。這種方法稱為選擇重發(fā)(SELECTICE REPEAT)，其工作過程如圖所示。顯然，選擇重發(fā)減少了浪費(fèi)，但要求接收方有足夠大的緩沖區(qū)空間。 2-2 選擇重傳協(xié)議原理圖三、過程論述(1）發(fā)送方程序流程圖：3-1發(fā)送方程序流程圖 （2）接收方程序流程圖：收到的包是否含有Push標(biāo)志？收到包的序號(hào)與等待接收的序號(hào)是否一致？收到包的序號(hào)在接收窗口范圍內(nèi)？NY直接提取數(shù)據(jù)，提前應(yīng)用進(jìn)程Y入接收隊(duì)列YN處理在接收隊(duì)列中的包（如果是普通包要判斷序號(hào)，或者

10、進(jìn)行拆包，組包操作）結(jié)束N3-2接受方程序流程圖3.2 功能實(shí)現(xiàn)（1）發(fā)送方程序：本程序設(shè)有四個(gè)變量：一是窗口大小變量，二是第一幀序列號(hào)變量，三是最近發(fā)送的幀變量，最后一個(gè)是最近收到的確認(rèn)幀變量。swpstate1.head=NULL; /變量初始值為空swpstate1.sendq=sendq_rear=(structsendq_slot*)malloc(sizeof(structsendq_slot);if(!swpstate1.sendq) exit(1);sendq_rear-next=NULL;printf(請(qǐng)輸入窗口大小：);scanf(%ld,&swpstate1.sws); /

11、輸入窗口大小swpstate1.rws=swpstate1.sws; /把窗口大小的值賦給變量if (swpstate1.sws0) printf(請(qǐng)輸入第一幀的序列號(hào)：); scanf(%ld,&swpstate1.hdr.seqnum); /輸入第一幀序列號(hào)swpstate1.nfe=swpstate1.hdr.seqnum; /把第一幀的值放進(jìn)緩沖池內(nèi)sendp=(struct sendq_slot*) malloc (size of(struct sendq_slot); if(!sendp) exit(1);sendp-msg=swpstate1.hdr.seqnum;sendp-t

12、imeout=1;sendp-next=NULL;sendq_rear-next=sendp;sendq_rear=sendp;-swpstate1.sws;swpstate1.lfs=swpstate1.hdr.seqnum; /最近發(fā)送的幀取值swpstate1.lar=swpstate1.hdr.seqnum; /最近收到的確認(rèn)幀取值dowhile(swpstate1.sws0) /當(dāng)窗口大小大于0時(shí)，執(zhí)行以下的循環(huán)sendp=(struct sendq_slot*)malloc(sizeof(struct sendq_slot); if(!sendp) exit(1); sendp-m

13、sg=swpstate1.lfs+1; /如果輸入的幀序號(hào)大于之前幀序號(hào)，那么窗口向前滑動(dòng) sendp-timeout=1; /時(shí)延為1 sendp-next=NULL; sendq_rear-next=sendp; sendq_rear=sendp; -swpstate1.sws; +swpstate1.lfs;swpstate1.hdr.acknum=0; /ACK清空swpstate1.hdr.flags=0; /存儲(chǔ)緩沖池清空printf(最近收到的ACK的幀序號(hào)：%ldn,swpstate1.lar); /輸出最近收到的ACK幀序號(hào)printf(最近發(fā)送的幀序號(hào)（發(fā)送新幀后）：%ld

14、n,swpstate1.lfs);/輸出最近發(fā)送幀序號(hào)（2）接收方的接收原則從總體上看是先判斷輸入的數(shù)據(jù)幀是否在接收范圍之內(nèi)，若是，則繼續(xù)判斷是否符合其他接收條件；若不是，則馬上丟棄該數(shù)據(jù)幀，不再進(jìn)行其他條件的判斷。struct sendq_slot *sendq_rear,*sendp,*p3,*p4; /設(shè)定變量struct recvq_slot *recvp,*recvq_rear,*p1,*p2; if(swpstate1.hdr.flags=0) /上次輸入的數(shù)據(jù)幀被放置在緩存區(qū)，輸入?yún)^(qū)被清空 do /如果繼續(xù)接收數(shù)據(jù)幀則實(shí)施下面循環(huán) printf(請(qǐng)輸入收到的數(shù)據(jù)幀號(hào)：); sca

15、nf(%ld,&a); if(a=swpstate1.nfe&anext=NULL; swpstate1.head=recvp; else if(swpstate1.head!=NULL) recvp=(struct recvq_slot*)malloc(sizeof(struct recvq_slot); recvp-next=NULL; recvq_rear-next=recvp; recvq_rear=recvp; else printf(所輸數(shù)據(jù)不在接收窗口內(nèi)！); break; /跳出該循環(huán) （3）若輸入數(shù)據(jù)幀在接收范圍內(nèi)則繼續(xù)判斷并進(jìn)行以下循環(huán)。 recvp-msg=a; if(r

16、ecvp-msg=swpstate1.nfe) /是否放入緩存判斷 recvp-received=1; else recvp-received=0; -swpstate1.rws; if(recvp-received=1) /數(shù)據(jù)幀被接收，則進(jìn)行下面語句 a=a-1; do a=a+1; if(swpstate1.head=NULL) break; p1=swpstate1.head; flag=0; while(a!=p1-msg)&(p1-next!=NULL) p2=p1;p1=p1-next; if(a=p1-msg) flag=1; if(p1=swpstate1.head) swp

17、state1.head=swpstate1.head-next; else p2-next=p1-next; swpstate1.nfe=a+1; swpstate1.hdr.acknum=a+1; swpstate1.hdr.flags=1; while(flag=1); printf(ACK號(hào)（期待的下一幀的序號(hào)）：%ldn,swpstate1.nfe); printf(沒按序接受的序號(hào):n); p1=swpstate1.head; while(p1!=NULL) printf(%ldt,p1-msg); p1=p1-next; （4）當(dāng)接收完一個(gè)數(shù)據(jù)幀時(shí)，我們可以選擇終止下面的繼續(xù)接收，

18、也可以選擇繼續(xù)接收。如果繼續(xù)接收，那么程序跳到判斷循環(huán)，繼續(xù)判斷是否接收下一個(gè)數(shù)據(jù)幀，原理與上面相當(dāng)。while(swpstate1.rws0)&(b=1); if(swpstate1.hdr.flags=1) p3=swpstate1.sendq-next; flag=0; while(swpstate1.hdr.acknum)!=p3-msg&p3-next!=NULL) p4=p3;p3=p3-next; if(swpstate1.hdr.acknum=p3-msg) flag=1; if(p3-msg=swpstate1.sendq-next-msg) swpstate1.sendq-

19、next=p3; else swpstate1.sendq-next=p3; swpstate1.sws=swpstate1.sws+(swpstate1.sendq-next-msg-swpstate1.lar); swpstate1.lar=swpstate1.sendq-next-msg; swpstate1.hdr.seqnum=swpstate1.hdr.acknum; printf(最近收到的ACK的幀序號(hào)（收到ACK后）：%ldn,swpstate1.lar); printf(最近發(fā)送的幀序號(hào)（此時(shí)還未發(fā)送新的數(shù)據(jù)）：%ldn,swpstate1.lfs); 四、結(jié)果分析滑動(dòng)窗口

20、協(xié)議的基本原理就是在任意時(shí)刻，發(fā)送方都維持了一個(gè)連續(xù)的允許發(fā)送的幀的序號(hào)，稱為發(fā)送窗口；同時(shí)，接收方也維持了一個(gè)連續(xù)的允許接收的幀的序號(hào)，稱為接收窗口。發(fā)送窗口和接收窗口的序號(hào)的上下界不一定要一樣，甚至大小也可以不同。不同的滑動(dòng)窗口協(xié)議窗口大小一般不同。發(fā)送方窗口內(nèi)的序號(hào)代表了那些已經(jīng)被發(fā)送，但是還沒有被確認(rèn)的幀，或者是那些可以被發(fā)送的幀。接受方為其窗口內(nèi)的每一個(gè)序號(hào)保留了一個(gè)緩沖區(qū)。與每個(gè)緩沖區(qū)相關(guān)聯(lián)的還有一位，用來指明該緩沖區(qū)是滿的還是空的。 若從滑動(dòng)窗口的觀點(diǎn)來統(tǒng)一看待1比特滑動(dòng)窗口、后退n及選擇重傳三種協(xié)議，它們的差別僅在于各自窗口尺寸的大小不同而已。1比特滑動(dòng)窗口協(xié)議：發(fā)送窗口=1，接收窗口=1；后退N協(xié)議：發(fā)送窗口1，接收窗口=1；選擇重傳協(xié)議：發(fā)送窗口1,接收窗口五、結(jié)論（或總結(jié)）下面我以窗口大小為11，第一幀序列號(hào)為3，做程序的測(cè)試 圖5 測(cè)試結(jié)果（1）整體窗口展示，命令行界面 5-1圖（2）輸入窗口大小及第一幀序列號(hào) 5-2圖（3）當(dāng)輸入的接收幀并不是ACK期待的幀，那么根據(jù)滑動(dòng)窗口協(xié)議該幀不被接收，且把該幀存放在緩沖區(qū)。 5-3圖（4）若輸入的幀超過了窗口大小，那么系統(tǒng)會(huì)顯示該幀不在接收范圍內(nèi)，并拒絕接收。 5-4圖 5-