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

1、精選文檔 計(jì)算機(jī)網(wǎng)絡(luò)課程設(shè)計(jì)書(shū) 學(xué) 院計(jì)算機(jī)與信息工程學(xué)院專(zhuān) 業(yè)網(wǎng)絡(luò)工程課程名稱(chēng)計(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í)語(yǔ)言進(jìn)行編程模擬其運(yùn)行過(guò)程;培育同學(xué)的動(dòng)手實(shí)踐和思考力量。 二，項(xiàng)目任務(wù)的主要內(nèi)容和要求    (1)本次設(shè)計(jì)任務(wù)是依據(jù)滑動(dòng)窗口協(xié)議的工作原理，在Visual C+ 6.0的平臺(tái)上用C+語(yǔ)言編寫(xiě)一個(gè)基本TCP滑動(dòng)窗口協(xié)議的模擬程序。 (2)要求該程序能夠?qū)崿F(xiàn)滑動(dòng)窗口協(xié)議的發(fā)送和接收數(shù)據(jù)幀功能，在此功能上體現(xiàn)滑

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

3、對(duì)端數(shù)據(jù)傳送的模擬程序。 (2)依據(jù)要求撰寫(xiě)課程設(shè)計(jì)報(bào)告并預(yù)備答辯。進(jìn)度安排起止日期工作內(nèi)容2015.6.23-2015.6.24了解網(wǎng)絡(luò)協(xié)議編程的基本學(xué)問(wèn)；2015.6.25-2015.6.26了解滑動(dòng)窗口協(xié)議的工作機(jī)制；2015.6.27-2015.6.28使用編程語(yǔ)言編寫(xiě)一個(gè)滑動(dòng)窗口協(xié)議的模擬程序，按要求實(shí)現(xiàn)程序。2015.6.29最終匯總，調(diào)試，答辯主要參考資料1 謝希仁. 計(jì)算機(jī)網(wǎng)絡(luò)M. 4版. 北京:電子工業(yè)出版社, 2003.2 李仁發(fā).何彥. 基于虛擬試驗(yàn)方法的滑動(dòng)窗口協(xié)議分析J. 系統(tǒng)仿真學(xué)報(bào). 2002. 8 (14) ; 1026 - 1063.3 李建中,張冬冬. 滑動(dòng)

4、窗口規(guī)模的動(dòng)態(tài)調(diào)整算法J. 軟件學(xué)報(bào). 2004. 12 (15) : 1800 - 1814.4 王栩,李建中,王偉平. 基于滑動(dòng)窗口的數(shù)據(jù)流壓縮技術(shù)及連續(xù)查詢(xún)處理方法 J . 計(jì)算機(jī)爭(zhēng)辯與進(jìn)展. 2004. 10 (41) : 1639- 1644.5 特南鮑姆. 計(jì)算機(jī)網(wǎng)絡(luò)（第四版）. 清華出版社指導(dǎo)老師意見(jiàn)（簽字）： ×年×月×日系（教研室）主任意見(jiàn)（簽字）： ×年×月×日 計(jì)算機(jī)網(wǎng)絡(luò)課程設(shè)計(jì)說(shuō)明書(shū)（封面） 學(xué)院名稱(chēng)： 計(jì)算機(jī)與信息工程學(xué)院 班級(jí)名稱(chēng)： 網(wǎng)絡(luò)工程一班 同學(xué)姓名： 學(xué) 號(hào)： 201321 題 目： 滑動(dòng)窗口協(xié)議仿

5、真 指導(dǎo)老師姓 名： 邵雪梅 起止日期： 2015.6.232015.6.29 第一部分：正文部分一，選題背景 早期的網(wǎng)絡(luò)通信中，通信雙方不會(huì)考慮網(wǎng)絡(luò)的擁擠狀況直接發(fā)送數(shù)據(jù)。由于大家不知道網(wǎng)絡(luò)擁塞狀況，一起發(fā)送數(shù)據(jù)，導(dǎo)致中間結(jié)點(diǎn)堵塞掉包，誰(shuí)也發(fā)不了數(shù)據(jù)。在數(shù)據(jù)傳輸過(guò)程中，我們總是期望數(shù)據(jù)傳輸?shù)母煲恍偃绨l(fā)送方把數(shù)據(jù)發(fā)送的過(guò)快，接收方就可能來(lái)不及接收，這就造成數(shù)據(jù)的丟失。因此就有了滑動(dòng)窗口機(jī)制來(lái)解決這些問(wèn)題。早期我們使用的是1bit滑動(dòng)窗口協(xié)議，一次只發(fā)送一個(gè)幀，等收到ack確認(rèn)才發(fā)下一個(gè)幀，這樣對(duì)信道的利用率太低了。因此提出了一種接受累積確認(rèn)的連續(xù)ARQ協(xié)議，接收方不必對(duì)收到的幀逐個(gè)發(fā)送

6、ack確認(rèn)，而是收到幾個(gè)幀后，對(duì)按序到達(dá)的最終一個(gè)幀發(fā)送ack確認(rèn)。同1bit滑動(dòng)窗口協(xié)議相比，大大削減了ack數(shù)量，并消退了延遲ack對(duì)傳輸效率的影響。但是，這會(huì)產(chǎn)生一個(gè)新的問(wèn)題，假如發(fā)送方發(fā)送了5個(gè)幀，而中間的第3個(gè)幀丟失了。這時(shí)接收方只能對(duì)前2個(gè)幀發(fā)出確認(rèn)。發(fā)送方無(wú)法知道后面三個(gè)幀的下落，只好把后面的3個(gè)幀再重傳一次，這就是回退N協(xié)議。為了解決這個(gè)問(wèn)題，又提出了選擇重傳協(xié)議。當(dāng)接收方發(fā)覺(jué)某幀出錯(cuò)后，連續(xù)接受后面送來(lái)的正確的幀，只是不交付它們，存放在自己的緩沖區(qū)中，并且要求發(fā)送方重傳出錯(cuò)的那一幀。一旦收到重傳來(lái)的幀后，就可以將存于緩沖區(qū)中的其余幀一并按正確的挨次遞交給主機(jī)。本文主要介紹如何

7、依據(jù)滑動(dòng)窗口協(xié)議的原理，在Visual C+的平臺(tái)上設(shè)計(jì)一個(gè)滑動(dòng)窗口協(xié)議模擬程序，并最終使該程序得以實(shí)現(xiàn)。本次程序設(shè)計(jì)分兩部分：第一部分是發(fā)送方，其次部分是接收方。通過(guò)發(fā)送方和接收方之間的數(shù)據(jù)幀傳輸模擬，學(xué)習(xí)滑動(dòng)窗口協(xié)議把握流量的原理和方法，以及滑動(dòng)窗口協(xié)議的工作機(jī)制。二、設(shè)計(jì)理念2.1 滑動(dòng)窗口協(xié)議工作原理TCP滑動(dòng)窗口用來(lái)暫存兩臺(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)收到的

8、分組。隨著新的確認(rèn)到來(lái)，窗口不斷向右滑動(dòng)?；瑒?dòng)窗口算法工作過(guò)程如下：首先，發(fā)送方為每1幀賦一個(gè)序號(hào)（sequence number），記作SeqNum?，F(xiàn)在，我們忽視SeqNum是由有限大小的頭部字段實(shí)現(xiàn)的事實(shí)，而假設(shè)它能無(wú)限增大。發(fā)送方維護(hù)3個(gè)變量：發(fā)送窗口大小（send window size），記作SWS，給動(dòng)身送方能夠發(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)窗

9、口協(xié)議工作圖窗口協(xié)議算法有三個(gè)功能：l 在不行靠鏈路上牢靠地傳輸幀l 保持幀的傳輸挨次l 支持流量把握2.2 選擇重傳協(xié)議在選擇重傳協(xié)議中，當(dāng)接收方發(fā)覺(jué)某幀出錯(cuò)后，其后連續(xù)送來(lái)的正確的幀雖然不能馬上遞交給接收方的高層，但接收方仍可收下來(lái)，存放在一個(gè)緩沖區(qū)中，同時(shí)要求發(fā)送方重新傳送出錯(cuò)的那一幀。一旦收到重新傳來(lái)的幀后，就可以原已存于緩沖區(qū)中的其余幀一并按正確的挨次遞交高層。這種方法稱(chēng)為選擇重發(fā)(SELECTICE REPEAT)，其工作過(guò)程如圖所示。明顯，選擇重發(fā)削減了鋪張，但要求接收方有足夠大的緩沖區(qū)空間。 2-2 選擇重傳協(xié)議原理圖三、過(guò)程論述(1）發(fā)送方程序流程圖：3-1發(fā)送方程序流程圖

10、（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)，或者進(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(stru

11、ctsendq_slot);if(!swpstate1.sendq) exit(1);sendq_rear->next=NULL;printf("請(qǐng)輸入窗口大?。?quot;);scanf("%ld",&swpstate1.sws); /輸入窗口大小swpstate1.rws=swpstate1.sws; /把窗口大小的值賦給變量if (swpstate1.sws>0) printf("請(qǐng)輸入第一幀的序列號(hào)："); scanf("%ld",&swpstate1.hdr.seqnum); /輸入第一

12、幀序列號(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->timeout=1;sendp->next=NULL;sendq_rear->next=sendp;sendq_rear=sendp;-swpstate1.sws;swpstate1.lfs=swpstate1.hdr.seqn

13、um; /最近發(fā)送的幀取值swpstate1.lar=swpstate1.hdr.seqnum; /最近收到的確認(rèn)幀取值dowhile(swpstate1.sws>0) /當(dāng)窗口大小大于0時(shí)，執(zhí)行以下的循環(huán)sendp=(struct sendq_slot*)malloc(sizeof(struct sendq_slot); if(!sendp) exit(1); sendp->msg=swpstate1.lfs+1; /假如輸入的幀序號(hào)大于之前幀序號(hào)，那么窗口向前滑動(dòng) sendp->timeout=1; /時(shí)延為1 sendp->next=NULL; sendq_rea

14、r->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ā)送新幀后）：%ldn",swpstate1.lfs);/輸出最近發(fā)送幀序號(hào)（2）接收方的接收原則從總體上看是先推斷輸入的數(shù)據(jù)幀是否在接收范圍之內(nèi)，若是，則

15、連續(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)："); scanf("%ld",&a); if(a>=swpstate1.nfe&

16、&a<=swpstate1.lfs) /推斷數(shù)據(jù)幀應(yīng)被接收或緩存 if(swpstate1.head=NULL) recvp=recvq_rear=(structrecvq_slot*)malloc(sizeof(structrecvq_slot); recvp->next=NULL; swpstate1.head=recvp; else if(swpstate1.head!=NULL) recvp=(struct recvq_slot*)malloc(sizeof(struct recvq_slot); recvp->next=NULL; recvq_rear-&g

17、t;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(recvp->msg=swpstate1.nfe) /是否放入緩存推斷 recvp->received=1; else recvp->received=0; -swpstate1.rws; if(recvp->received=1) /數(shù)據(jù)幀被接收，則進(jìn)行下面語(yǔ)句 a=a-1; do a=a+1; if(s

18、wpstate1.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) swpstate1.head=swpstate1.head->next; else p2->next=p1->next; swpstate1.nfe=a+1; swpstate1.hdr.acknum=a+1; swpstate1.hd

19、r.flags=1; while(flag=1); printf("ACK號(hào)（期盼的下一幀的序號(hào)）：%ldn",swpstate1.nfe); printf("沒(méi)按序接受的序號(hào):n"); p1=swpstate1.head; while(p1!=NULL) printf("%ldt",p1->msg); p1=p1->next; （4）當(dāng)接收完一個(gè)數(shù)據(jù)幀時(shí)，我們可以選擇終止下面的連續(xù)接收，也可以選擇連續(xù)接收。假如連續(xù)接收，那么程序跳到推斷循環(huán)，連續(xù)推斷是否接收下一個(gè)數(shù)據(jù)幀，原理與上面相當(dāng)。while(swpstate1.r

20、ws>0)&&(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->next=p3; e

21、lse 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ù)）：%ld

22、n",swpstate1.lfs); 四、結(jié)果分析滑動(dòng)窗口協(xié)議的基本原理就是在任意時(shí)刻，發(fā)送方都維持了一個(gè)連續(xù)的允許發(fā)送的幀的序號(hào)，稱(chēng)為發(fā)送窗口；同時(shí)，接收方也維持了一個(gè)連續(xù)的允許接收的幀的序號(hào)，稱(chēng)為接收窗口。發(fā)送窗口和接收窗口的序號(hào)的上下界不肯定要一樣，甚至大小也可以不同。不同的滑動(dòng)窗口協(xié)議窗口大小一般不同。發(fā)送方窗口內(nèi)的序號(hào)代表了那些已經(jīng)被發(fā)送，但是還沒(méi)有被確認(rèn)的幀，或者是那些可以被發(fā)送的幀。接受方為其窗口內(nèi)的每一個(gè)序號(hào)保留了一個(gè)緩沖區(qū)。與每個(gè)緩沖區(qū)相關(guān)聯(lián)的還有一位，用來(lái)指明該緩沖區(qū)是滿(mǎn)的還是空的。 若從滑動(dòng)窗口的觀點(diǎn)來(lái)統(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）整體窗口呈現(xiàn)，命令行界面 5-1圖（2）輸入窗口大小及第一幀序列號(hào) 5-2圖（3）當(dāng)輸入的接收幀并不是ACK期盼的幀，那么依據(jù)滑動(dòng)窗口協(xié)議該幀不被接收