山東大學計算機網絡實驗報告

1、計算機網絡實驗第八組計算機網絡試驗報告學院：計算機科學與技術學院班級：13計基地目錄一、實驗簡述3二、實驗內容3實驗一：雙隊列模型3一、實驗模型3二、具體實現3三、結果展示4實驗二：802.11 無線競爭模型6一、實驗模型6二、具體實現6三、實驗結果61.圖表結果62.數據結果8三、實驗感想8一、雙隊列單服務器8二、802.11無限競爭模型8一、實驗簡述實驗一要求采用盡量公平的調度算法，實現一個服務器服務2個隊列的功能。且滿足以下條件：到達包數是泊松過程（Poisson process）；服務時間是指數分布（exponentially distributed）；只有一部服務器（server）；

2、隊列長度無限制；可加入隊列的包數為無限。實驗二基于802.11協(xié)議采用二進制指數回退算法，沒有中央控制器的調度算法實現對五個站的調度機制。要求盡可能達到公平。二、實驗內容實驗一：雙隊列模型一、實驗模型本次計算機網絡實驗主要是關于服務器處理包的過程模擬，其中一個重要的基礎排隊模型是 M/M/1 排隊模型。M/M/1排隊模型是一種單一服務器（single-server）的排隊模型，有以下主要特點：1.到達人數是泊松過程(Poisson process)2.服務時間是指數分布(exponentially distributed)3.只有一臺服務器(server)4.隊列長度無限制5.可加入隊列的人數

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

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

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

6、了使畫出的圖更加精確，增大間距，每0.1s為一個單位。統(tǒng)計等待時間在0-0.1s之間、0.1-0.2s之間的包的個數，用每0.1s包的個數除以總個數得到在某個0.1s時間間隔的概率，最后得到時間>=某時間的概率?？傊捎脭到M來存儲包的到達時間、離開隊列時間、服務完成時間、每個包的大小等。到達時間通過包發(fā)送的時間間隔來產生，時間間隔通過泊松函數產生。根據調度算法來獲得包的離開隊列時間，服務完成時間可根據離開隊列的時間加上服務器處理包所用的時間，而服務器處理包所用時間則由包的大小除以服務器的服務速率獲得。當我們獲得了每個包的狀態(tài)后，便可計算出隊列長度分布和等待時間分布了。三、結果展示1.圖

7、表結果：分別將兩個隊列的隊列長度分布和等待時間分布畫在一幅圖中進行比較，看是否是調度公平。測試包個數為108，結果如下:（1）隊列分布：下方紅線為隊列1等待隊列分布，上方藍線為隊列2等待隊列分布。圖表40，50分別代表隊列每秒發(fā)送包數。（2）時間分布下方紅線為隊列1等待時間分布，上方藍線為隊列1等待時間分布。實驗二：802.11 無線競爭模型一、實驗模型用五個站來模擬802.11MAC子層協(xié)議。首先，看一下什么是802.11。802.11協(xié)議組是國際電工電子工程學會(IEEE)為無線局域網絡制定的標準。為了避免沖突碰撞，采用的協(xié)議為CSMA/CA協(xié)議，即采用二進制指數后退的方法來解決沖突問題。

8、該方法是在第i次沖突后，從02i-1之間隨機選擇一個數，然后等待這么多個時間槽。然而，達到10次沖突之后，隨機數的選擇區(qū)間被固定在最大值1023，以后不再增加，在16次沖突之后，控制器放棄努力，并給計算機返回一個失敗報告。比如：第一次沖突后，從01之間隨機選擇一個數然后作為該站等待的時間槽數。雖然，CSMA/CA和回歸都能解決碰撞的問題，不過，在功能上，它們是有差別的。CSMA/CA是一種“競爭”(contention)通信協(xié)議，它傾聽WLAN網絡，避免碰撞發(fā)生。它和傳統(tǒng)的CSMA/CD(被以太網絡使用)不同，CSMA/CD是在碰撞發(fā)生之后，才起來處理后續(xù)的傳送作業(yè)。CSMA/CA則是防患未然

9、，所以比較有助于網絡通信。因為它在任何真正的數據被傳送之前，會先在網絡上廣(broadcast)一個信號，偵聽是否有碰撞發(fā)生，同時告訴其它裝置不要廣播。 二、具體實現首先創(chuàng)建了新的結構-站，然后創(chuàng)建5個站。然后令總包數為10000000（107），設置固定的參數timeslot為一個時間單位。當一個站需要發(fā)包時，采用p堅持的方法，在0N-1之間隨機選擇個數作為該包開始發(fā)包時timeslot值，等到對應的timeslot值時試圖發(fā)送包，若同時有其他包在同一時間發(fā)送，產生碰撞，該包返回到站中同時該包要進行二進制回退選擇自己再次發(fā)包的時間；如不產生碰撞，則成功發(fā)送，根據包的大小決定包發(fā)送完成的時間并

10、返回ack給站，在包處理的過程中其他包不能發(fā)送。最后，若產生16次沖突時，拋棄此包。三、實驗結果1.圖表結果（1）等待隊列概率分布，如下圖所示。（2）等待時間長度分布，如下圖所示2.數據結果（1）服務器服務數據初始數據運行結果競爭信道站數（個）5總包數（個）108平均間隔時間（秒）15.5總時間（秒）30993668.7200平均服務器響應時間（秒）1.8吞吐率（個/單位時間）3.226465時間槽0.07碰撞浪費時間概率0.00888（2）五個站服務數據發(fā)送總包數（個）平均等待時間（秒）平均等待包個數（個）信道利用率站1200043730.80476319.9004300.580357站22

11、00007330.62091819.7787390.580357站3200050730.87260519.9449050.580357站4200098730.88730619.9593600.580357站5199799630.78283919.8622560.580357三、實驗感想一、雙隊列單服務器首先選擇數組作為模擬結構，將隊列中每個包的到達隊列時間、離開隊列時間、服務完成時間放入相應的數組中。然后就是選擇調度機制來調度包的發(fā)送。算法對結果的影響是至關重要的，決定了隊列調度的公平程度。這里采用了帶赤字的輪轉制度來進行模擬，在編碼過程中，為了優(yōu)化方法，如果一個隊列中還有赤字但是隊列中沒有包，這時將赤字清零并轉