山東大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)網(wǎng)絡(luò)試驗(yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院班級：13計(jì)基地目錄一、實(shí)驗(yàn)簡述3二、實(shí)驗(yàn)內(nèi)容3實(shí)驗(yàn)一：雙隊(duì)列模型 3一、實(shí)驗(yàn)?zāi)Ｐ?二、具體實(shí)現(xiàn)4二、結(jié)果展示 6實(shí)驗(yàn)二：802.11無線競爭模型 7一、實(shí)驗(yàn)?zāi)Ｐ?二、具體實(shí)現(xiàn)8三、實(shí)驗(yàn)結(jié)果81圖表結(jié)果82數(shù)據(jù)結(jié)果1.0三、實(shí)驗(yàn)感想 10一、雙隊(duì)列單服務(wù)器1.0二、802.11無限競爭模型 1.1亠、實(shí)驗(yàn)簡述實(shí)驗(yàn)一要求采用盡量公平的調(diào)度算法，實(shí)現(xiàn)一個(gè)服務(wù)器服務(wù) 2個(gè)隊(duì)列的功 能。且滿足以下條件：到達(dá)包數(shù)是泊松過程(POiSSOn process);服務(wù)時(shí)間是指 數(shù)分布(expOnentially distributed )；只有一部服務(wù)器(SerVe

2、r)；隊(duì)列長度無限 制；可加入隊(duì)列的包數(shù)為無限。實(shí)驗(yàn)二基于802.11協(xié)議采用二進(jìn)制指數(shù)回退算法，沒有中央控制器的調(diào)度 算法實(shí)現(xiàn)對五個(gè)站的調(diào)度機(jī)制。要求盡可能達(dá)到公平。二、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一：雙隊(duì)列模型一、實(shí)驗(yàn)?zāi)Ｐ捅敬斡?jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)主要是關(guān)于服務(wù)器處理包的過程模擬，其中一個(gè)重要的基礎(chǔ)排隊(duì)模型是M/M/1排隊(duì)模型。M/M/1排隊(duì)模型是一種單一服務(wù)器(Sin gle-server)的排隊(duì)模型，有以下主要特點(diǎn)：1. 到達(dá)人數(shù)是泊松過程(POiSSOn PrOCeSS)2. 服務(wù)時(shí)間是指數(shù)分布(exponentially distributed)Word資料3只有一臺(tái)服務(wù)器（SerVer）4.隊(duì)列長度無限

3、制5可加入隊(duì)列的人數(shù)為無限M/M/1排隊(duì)模型在任何狀態(tài)下，只有兩種事情可能發(fā)生：1. 有人加入隊(duì)列。如果模型在狀態(tài) k,它會(huì)以速率進(jìn)入狀態(tài)k + 12. 有人離開隊(duì)列。如果模型在狀態(tài) k（ k不等于0）,它會(huì)以速率進(jìn)入狀態(tài) k -1二、具體實(shí)現(xiàn)1.赤字輪詢算法赤字輪詢算法引入赤字的概念，即在較長時(shí)間統(tǒng)計(jì)平均意義上平衡各條流所獲得的吞吐量。因?yàn)楦髁髦g不同業(yè)務(wù)造成的數(shù)據(jù)包大小的差異以及各流內(nèi)部數(shù) 據(jù)包大小的不同都可能造成在一個(gè)輪詢周期內(nèi)各虛擬隊(duì)列所發(fā)送的字節(jié)數(shù)具有 較大偏差。DRR算法為每個(gè)虛擬隊(duì)列維護(hù)一個(gè)赤字字節(jié)數(shù)，使得本次輪詢未能 發(fā)送的字節(jié)會(huì)在下一次甚至下幾次輪詢過程中得到補(bǔ)償。具體過程如

4、下：將有數(shù)據(jù)包等待發(fā)送的虛擬隊(duì)列存放于一個(gè)鏈表中，輪詢過程即訪問鏈表表頭上的隊(duì) 列，訪問時(shí)先將隊(duì)列的當(dāng)前赤字值（deficitcounter ）加上一個(gè)預(yù)先分配的值（表 示每次輪詢允許發(fā)送的字節(jié)數(shù)），將它作為本次輪詢所能發(fā)送的最大字節(jié)數(shù)Q,然后服務(wù)該隊(duì)列。服務(wù)隊(duì)列時(shí)先判斷隊(duì)頭上的數(shù)據(jù)包長度（Byte）是否小于Q,如果是,則服務(wù)后令Q減去Byte并繼續(xù)此循環(huán)過程直至Byte>Q,將最后得到的 Q值賦予deficitcounter,并將該隊(duì)列從數(shù)組中取出插入數(shù)組尾部，接著訪問數(shù) 組中的下一個(gè)隊(duì)列。若從虛擬隊(duì)列中取出數(shù)據(jù)包后隊(duì)列為空，則將該虛擬隊(duì)列從數(shù)組中刪除。為了使結(jié)果更加精確，可以在電腦承

5、受能力范圍內(nèi)適當(dāng)增加發(fā)送 包的個(gè)數(shù)2仿真與計(jì)算為了模擬隊(duì)列長度分布，采用每個(gè)隊(duì)列長度所占時(shí)間除以總時(shí)間來表示。隊(duì) 列長度發(fā)生變化的原因是有包到達(dá)隊(duì)列或離開隊(duì)列，因此我們可定義一個(gè)變量 COunt并初始化為0，在每次包到達(dá)時(shí)COunt+1，每個(gè)包離開時(shí)COunt-1 ，在兩個(gè) 離開或到達(dá)事件之間隊(duì)列中包的個(gè)數(shù)是不變的，這時(shí)就為包的個(gè)數(shù)為COUnt的隊(duì) 列長度數(shù)組的時(shí)間加上這個(gè)時(shí)間間隔，依此繼續(xù)得到所有的隊(duì)列中包的個(gè)數(shù)為某 個(gè)值的所占有的所有時(shí)間，再用該時(shí)間除以總時(shí)間得到隊(duì)列長度為 X時(shí)概率，最 后可得到隊(duì)列長度>=x時(shí)的概率分布。為了模擬等待時(shí)間分布，可以根據(jù)每個(gè)包的到達(dá)隊(duì)列時(shí)間和離開隊(duì)列

6、時(shí)間來 獲得等待時(shí)間，為了使畫出的圖更加精確，增大間距，每0.1s為一個(gè)單位。統(tǒng)計(jì)等待時(shí)間在0-01s之間、0.1-0.2s之間的包的個(gè)數(shù)，用每0.1s包的個(gè)數(shù)除以 總個(gè)數(shù)得到在某個(gè)0.1s時(shí)間間隔的概率，最后得到時(shí)間 >=某時(shí)間的概率。總之，采用數(shù)組來存儲(chǔ)包的到達(dá)時(shí)間、離開隊(duì)列時(shí)間、服務(wù)完成時(shí)間、每個(gè) 包的大小等。到達(dá)時(shí)間通過包發(fā)送的時(shí)間間隔來產(chǎn)生，時(shí)間間隔通過泊松函數(shù)產(chǎn)生。根據(jù)調(diào)度算法來獲得包的離開隊(duì)列時(shí)間，服務(wù)完成時(shí)間可根據(jù)離開隊(duì)列的時(shí)間加上服務(wù)器處理包所用的時(shí)間，而服務(wù)器處理包所用時(shí)間則由包的大小除以服 務(wù)器的服務(wù)速率獲得。當(dāng)我們獲得了每個(gè)包的狀態(tài)后，便可計(jì)算出隊(duì)列長度分布 和等

7、待時(shí)間分布了。三、結(jié)果展示1圖表結(jié)果：分別將兩個(gè)隊(duì)列的隊(duì)列長度分布和等待時(shí)間分布畫在一幅圖中進(jìn)行比較，看是否是調(diào)度公平。測試包個(gè)數(shù)為108 ,結(jié)果如下：(1)隊(duì)列分布：下方紅線為隊(duì)列1等待隊(duì)列分布，上方藍(lán)線為隊(duì)列2等待隊(duì)列分布。圖表40,50分別代表隊(duì)列每秒發(fā)送包數(shù)。O等待隊(duì)列長度概率分布10隊(duì)列1(40)隊(duì)列2(50)-210率概度長列隊(duì)此于等于大-410-610-8100102030405060708090100等待隊(duì)列長度(2)時(shí)間分布F方紅線為隊(duì)列1等待時(shí)間分布，上方藍(lán)線為隊(duì)列1等待時(shí)間分布。010等待時(shí)間長度概率分布I-IlLLULS隊(duì)列 1(40)；隊(duì)列 2(50)'率概度

8、長間時(shí)此于等于大-110-210-310-410-510-610-710020406080100120140160180等待時(shí)間長度實(shí)驗(yàn)二：802.11無線競爭模型一、實(shí)驗(yàn)?zāi)Ｐ陀梦鍌€(gè)站來模擬802.11MAC子層協(xié)議。首先，看一下什么是 802.11。802.11協(xié)議組是國際電工電子工程學(xué)會(huì)(IEEE為無線局域網(wǎng)絡(luò)制定的標(biāo)準(zhǔn)。 為了避免沖突碰撞，采用的協(xié)議為 CSMA/CA協(xié)議，即采用二進(jìn)制指數(shù)后退的方 法來解決沖突問題。該方法是在第i次沖突后，從02i-1之間隨機(jī)選擇一 個(gè)數(shù)，然后等待這么多個(gè)時(shí)間槽。然而，達(dá)到10次沖突之后，隨機(jī)數(shù)的選擇區(qū)間被固定在最大值1023 ,以后不再增加，在16次沖

9、突之后，控制器放棄努力， 并給計(jì)算機(jī)返回一個(gè)失敗報(bào)告。比如：第一次沖突后，從01之間隨機(jī)選擇一個(gè)數(shù)然后作為該站等待的時(shí)間槽數(shù)。雖然，CSMA/CA和回歸都能解決碰撞的問題，不過，在功能上，它們是有差別的CSMA/CA 是一種“競爭'(contention)通信協(xié)議，它傾聽WLAN網(wǎng)絡(luò)，避免碰撞發(fā)生。它和傳統(tǒng)的CSMACD（被以太網(wǎng)絡(luò) 使用）不同，CSMA/CD是在碰撞發(fā)生之后，才起來處理后續(xù)的傳送作業(yè)。CSMA/CA 則是防患未然，所以比較有助于網(wǎng)絡(luò)通信。因?yàn)樗谌魏握嬲臄?shù)據(jù)被傳送之前， 會(huì)先在網(wǎng)絡(luò)上廣（broadcast）一個(gè)信號，偵聽是否有碰撞發(fā)生，同時(shí)告訴其它裝置 不要廣播。二

10、、具體實(shí)現(xiàn)首先創(chuàng)建了新的結(jié)構(gòu)-站，然后創(chuàng)建 5個(gè)站。然后令總包數(shù)為10000000（107），設(shè)置固定的參數(shù)timeslot為一個(gè)時(shí)間單位。當(dāng)一個(gè)站需要發(fā)包時(shí)，采用P堅(jiān)持的方法，在0N-1之間隨機(jī)選擇個(gè)數(shù)作為該包開始發(fā)包時(shí)timeslot值，等到對應(yīng)的timeslot值時(shí)試圖發(fā)送包，若同時(shí)有其他包在同一時(shí)間發(fā)送，產(chǎn)生碰 撞，該包返回到站中同時(shí)該包要進(jìn)行二進(jìn)制回退選擇自己再次發(fā)包的時(shí)間；如不產(chǎn)生碰撞，則成功發(fā)送，根據(jù)包的大小決定包發(fā)送完成的時(shí)間并返回ack給站，在包處理的過程中其他包不能發(fā)送。最后，若產(chǎn)生16次沖突時(shí)，拋棄此包。三、實(shí)驗(yàn)結(jié)果1圖表結(jié)果（1）等待隊(duì)列概率分布，如下圖所示。010率概

11、量數(shù)包務(wù)服此于等于大-6100204060等待隊(duì)列概率分布PaCketO2-O80100120140160180已服務(wù)包數(shù)量(2)等待時(shí)間長度分布，如下圖所示率概間時(shí)待等此于等于大等待時(shí)間長度概率分布50O-2-O-3-O-4-5-O - O£100150200等待時(shí)間長度2503002數(shù)據(jù)結(jié)果（1）服務(wù)器服務(wù)數(shù)據(jù)初始數(shù)據(jù)運(yùn)行結(jié)果競爭信道站數(shù)（個(gè)）5總包數(shù)（個(gè)）810平均間隔時(shí)間（秒）15.5總時(shí)間（秒）30993668.7200平均服務(wù)器響應(yīng)時(shí)間（秒）1.8吞吐率（個(gè)/單位時(shí)間）3.226465時(shí)間槽0.07碰撞浪費(fèi)時(shí)間概率0.00888（2）五個(gè)站服務(wù)數(shù)據(jù)發(fā)送總包數(shù)（個(gè)）平均等待

12、時(shí)間 （秒）平均等待包個(gè)數(shù) （個(gè)）信道利用率站1200043730.80476319.9004300.580357站2200007330.62091819.7787390.580357站3200050730.87260519.9449050.580357站4200098730.88730619.9593600.580357站5199799630.78283919.8622560.580357二、實(shí)驗(yàn)感想一、雙隊(duì)列單服務(wù)器首先選擇數(shù)組作為模擬結(jié)構(gòu)，將隊(duì)列中每個(gè)包的到達(dá)隊(duì)列時(shí)間、離開隊(duì)列時(shí) 間、服務(wù)完成時(shí)間放入相應(yīng)的數(shù)組中。然后就是選擇調(diào)度機(jī)制來調(diào)度包的發(fā)送。 算法對結(jié)果的影響是至關(guān)重要的，決定了隊(duì)列調(diào)度的公平程度。這里采用了帶赤 字的輪轉(zhuǎn)制度來進(jìn)行模擬，在編碼過程中，為了優(yōu)化方法，如果一個(gè)隊(duì)列中還有 赤字但是隊(duì)