Microsoft Word 林松德-0813-Fair Link and Node Contention in Wireless Mesh Networking-11

Transcription

1 國立交通大學 網路工程研究所 碩士論文 無線網狀網路中公平的連結競爭及節點競爭 Fair Link and Node Contention in Wireless Mesh Networking 研究生 : 林松德 指導教授 : 林盈達教授 張立平教授 中華民國九十八年八月

2 無線網狀網路中公平的連結競爭及節點競爭 Fair Link and Node Contention in Wireless Mesh Networking 研究生 : 林松德 指導教授 : 林盈達 張立平 Student: Sung-De Lin Advisor: Ying-Dar Lin Li-Ping Chang 國立交通大學網路工程研究所碩士論文 A Thesis Submitted to Institute of Network Engineering College of Computer Science National Chiao Tung University in partial Fulfillment of the Requirements for the Degree of Master in Computer Science Aug Hsinchu, Taiwan, Republic of China 中華民國九十八年八月

3 無線網狀網路中公平的連結競爭及節點競爭 學生 : 林松德 指導教授 : 林盈達博士 張立平博士 國立交通大學網路工程研究所碩士班 摘 要 隨著 IEEE s 草案 (draft) 的提出, 使得無線網狀網路技術更適用於骨幹網路的架設 ; 然而在目前的草案中, 並沒有針對 公平性問題 提出任何相關的解決方式, 導致靠近骨幹出口的少數近端節點將獨佔頻寬 造成末端節點餓死, 無法提供任何頻寬給該節點所服務之工作站使用 本論文分析 無線網路中公平性問題的成因, 有節點競爭問題以及連接競爭問題, 提出 Fair Link and Node Contention(FLNC) 演算法, 動態地使用三種機制, 包括雙重佇列輪詢機制 (DRR) 分隔近端節點與遠端節點流量解決節點競爭問題, 以及 RTS/CTS 機制並搭配調整競爭視窗解決連結競爭問題 透過模擬的結果顯示, 在四個節點的串列網路拓樸與五個節點的樹狀網路拓樸飽和流量環境下, 可以消除不公平問題帶來的 9 Mbps 傳輸速度的差異 關鍵字 : 無線網狀網路, IEEE s, 公平性問題, 多點跳躍無線網路, RTS/CTS i

4 Fair Link and Node Contention in Wireless Mesh Networking Student: Sung-De Lin Advisor: Dr. Ying-Dar Lin Dr. Li-Pin Chang Department of Network Engineering National Chiao Tung University ABSTRACT The proposed IEEE s draft makes the wireless technique more suitable for backhaul network. However, there is no any solution addressing on the fairness problem in the latest version of s daft, which causes near-portal nodes occupying most channel resource and the further nodes starved. This thesis points out that the fairness problem results from the node contention and the link contention, and proposes the Fair Link and Node Contention (FLNC) algorithm that uses the round-robin mechanism among dual queues to solve the node contention, and adopts RTS/CTS mechanism and adjusts the size of contention window to relieve the link contention. By simulation result, we show that on a 4-node chain topology and a 5-node tree topology with saturated offered load, using FLNC can decrease the 9-Mbps throughput difference coming from fairness problem. Keywords: Wireless mesh, IEEE s, fairness problem, multi-hop wireless, RTS/CTS ii

5 誌 謝 終於在這第三年的最後一刻, 完成了研究所的學業, 這漫長的三年, 對自己的人生來說, 無疑是一個難忘的記錄 暫時停止了工作, 回到了校園, 攻讀碩士, 受到很多以前同學 朋友的質問, 總是對朋友這麼說, 我是在投資自己的人生, 為自己的人生加分, 在這畢業之際, 能否為自己的未來人生加分, 現在也還沒辦法回答自己, 但是至少可以確定, 在這漫長的三年研究所時間裡, 多花了其它同學一年的時間, 才達到畢業的水準, 真的是學習到, 也見識到了很多, 對自己的能力跟訓練, 都是加分的, 等待未來投入職場, 運用在這三年來所累積的能量, 證明自己的能力 感謝論文指導教授, 林盈達教授 張立平教授, 賴源正教授 葉瑞鴻博士 張舜理學長 古佳育學長, 因為有你們的費心指導, 讓本論文得以完整 感謝實驗室的眾多成員, 學長 同學 學弟妹, 總是熱鬧的實驗室, 讓苦悶的研究時間, 不至於難熬, 吃飯 娛樂 購物 出遊, 為生活帶來了休息的機會 特別感謝第一屆的學長俊達 仕宏 士豪 譽繽 光仁, 同學辰暉 千庭 家明 蕙茹, 學弟妹, 郡杰 宥全 明毅 士庭 秀芬 詩凱 晉廷 偉杰 義勛 莉君, 因為認識你 ( 妳 ) 們, 讓我的研究所生活更豐富 開心 多采多姿, 感謝我的父母認同我的決定, 我的朋友達叔 君豪 家蓉, 最後要感謝的, 是這三年來, 無怨無悔支持我的老婆家英, 因為有妳的支持, 這一本論文才得以產生, 我將畢業的榮耀, 全部都歸功於妳 iii

6 目 錄 摘要... i ABSTRACT... ii 誌謝... iii 目錄... iv 圖目錄... v 表目錄... vi 第一章簡介... 1 第二章背景知識 Overview of Mesh Networks 公平性問題 (Fairness Problem) 節點競爭 (Node Contention) 連結競爭 (Link Contention) Related Works... 9 第三章 Fair Link and Node Contention 演算法概觀 FLNC 演算法 演算法所使用之三種機制說明 DRR 機制 RTS/CTS 機制 Contention Windows Adjustment 機制 第四章 Simulation Studies 模擬環境 DRR 機制 控管 single Collision Domain 的公平性問題 RTS/CTS 機制 解決隱藏節點帶來的公平性問題 CWA 機制 無配合 RTS/CTS 機制時, 無法發生效果 CWA 機制 補償 RTS/CTS 機制所產生的副作用 Full Function Summary with a Decision Table 第五章結論 參考文獻 iv

7 圖目錄 圖 1.1: 串列及樹狀網路拓撲... 2 圖 1.2: 串列及樹狀網路拓撲發生公平性問題的實驗結果... 2 圖 2.1: IEEE s mesh architecture... 4 圖 2.2: 節點內部佇列結構示意圖... 6 圖 2.3: 四節點發生連結競爭... 7 圖 2.4: 使用 RTS/CTS 機制, 解決公平性問題... 8 圖 3.1: The flow chart of FLNC algorithm 圖 3.2: The architecture of FLNC algorithm 圖 3.3: DRR Ratio Control 機制實作示意圖 圖 3.4: CWA 機制實作示意圖 圖 4.1: 三節點串列網路拓撲, 採用 DRR 演算法實驗結果 圖 4.2: 三節點串列網路拓撲的 fairness index 圖 4.3: 四節點串列網路拓撲 圖 4.4: 串列網路拓撲模擬結果 圖 4.5: 串列網路拓撲 fairness index 圖 4.6: 串列網路拓撲, 啟用 RTS/CTS 機制 圖 4.7: 串列網路拓撲, 啟用 RTS/CTS 機制的 fairness index 圖 4.8: 串列網路拓撲 CWA 實驗 圖 4.9: 串列網路拓撲,CWA 實驗 fairness index 圖 4.10: 串列網路拓撲,DRR+RTS/CTS+CWA 實驗結果 圖 4.11: 串列網路拓撲,DRR+RTS/CTS+CWA fairness index 圖 4.12: 串列網路拓撲 no function V.S full function 圖 4.13: 串列網路拓撲 fairness index 圖 4.14: 五個節點的樹狀網路拓撲 圖 4.15: 樹狀網路拓撲模擬結果 圖 4.16: 樹狀網路拓撲 fairness index v

8 表目錄 表 2.1: 三種網路結構比較表... 5 表 2.2: 相關文獻的機制與比較... 9 表 3.1: Pseudo code of FLNC algorithm 表 4.1: 模擬參數設定 表 4.2: Decision Table vi

9 第一章簡介 s wireless mesh network 的草案 (draft)[1] 具有諸多特點, 如佈建快速 (fast deployment) 高擴展性(highly expandability) 節省佈線成本(wiring cost)[2-3], 由於這些特點, 彌補了傳統 無線網路不適用於有線網路不易佈建的環境的缺點, 使得無線網路更適用於網路基礎建設較不完善的環境 雖然本標準目前尚在草案階段, 仍未定案, 已經吸引許多國際大廠投入研發符合草案 (draft) 規格的產品 s 的標準相較於傳統 無線網路, 兩者主要的差別在於 : 傳統 無線網路由 access point(ap) 以及 stations(stas) 所組成 ; 而 s 無網網路, 是由 mesh portal(mpp) mesh point (MP) mesh access point(map) 以及 station(stas) 所組成, 其中 MAP MPP 以及 MP 之間, 透過封包轉送 (forward) 的機制, 達成封包在 mesh networks 中的傳遞, 而 STAs 透過對 MAP 的連結, 藉由 MAP 所提供的連結服務, 對 mesh networks 中的其它 STAs 傳遞封包 ; 或將封包送達至 MAP 之後, 再由 MAP 將封包轉送到 MPP, 利用 MPP 與 Internet 連結 傳統 無線網路的存取點 (AP), 只需負擔連結的該存取點之 station 的封包傳輸, 並將所有封包轉送至有線網路 ; 而 s 中的節點, 在傳送自己的封包工作之外, 還必須協助轉送其它節點所傳送過來的封包, 以達到將封包送達到 mesh networks 中的 STAs; 或送至 MPP, 以連結至 Internet 透過上述的封包轉送機制, 使 mesh networks 得以降低對有線網路的需求 然而如此的封包轉送的設計概念, 造成了額外的問題, 也就是 公平性問題 (unfairness problem) 圖 1.2 (a) (b) 分別為圖 1.1 中的串列及樹狀的無線網路拓撲, 發生了 公平性問題 的結果 從圖 1.2 (a) 可看出, 在此網路拓撲中, 所有的節點, 都發送大量的封包至目的地節點 N0 也就是 MPP, 透過 N0 節點, 將封包傳送至有線網路 然而, 隨著各個節點送出流量的提高, 觀察各節點所取得的頻寬, 將會發現, 隨著 N1 所送出的封包流量的提高,N1 所獲得的頻寬不斷提高, 而隨著 N1 所送出的封包流量的增加, 節點 N2 及 N3 所能取得的頻寬不斷下降, 到最後,N2 及 N3 會因為 N1 的獨占頻寬, 而無法成功取得傳送機會傳送封包, 此現象即為 公平性問題 同樣的現象也發生在圖 1

10 1.2 (b), 其中 N1 的流量, 導致 N2 N3 及 N4 無法取得傳送封包的機會, 最終餓死 (starvation) (a) 四個節點的串列網路拓撲 (b) 五個節點的樹狀網路拓撲 圖 1.1: 串列及樹狀網路拓撲 Throughput(Mbps) N1 N2 N3 Throughput(Mbps) N1 N2 N3 N Offered load(mbps) Offered load (Mbps) (a) 串列網路拓撲公平性問題 (b) 樹狀網路拓撲公平性問題 圖 1.2: 串列及樹狀網路拓撲發生公平性問題的實驗結果 造成公平性問題的主要原因來自於節點內封包處理時的競爭問題 ( 以下稱之為節點競爭 ) 以及節點與節點之間的連結競爭 首先, 節點競爭發生在網路的各節點內, 由於網路中的每個節點, 都必須處理兩種類別的封包, 第一種為本地封包 (local packets), 包括由該節點自行產生, 或是該節點所服務的 STAs 藉由獨立的無線頻道 (a separated wireless channel) 所傳送過來的封包 ; 第二種為使用共通頻道 (common channel) 轉送其它節點所傳送過來的轉送封包 (forward packets) 前者的封包產生速率通常快於後者, 以至於若僅使用單一佇列 (single queue) 先到先服務 (FCFS) 的實作方式, 此節點的封包傳送 (packet transmission) 比例, 本地封包會大於轉送封包, 亦即造成不公平現象 其次為連結競爭, 造成連結競爭現象的主因, 在於無線訊號僅具有有限度傳送距離的特性 由於遠端節點無法聽到接收方附近的頻道使用狀況, 而進行錯誤的傳輸嘗試, 增大自身的競爭視窗 (contention window) 區間, 降低競爭無線資源的機率, 造成不公平現象 2

11 針對 公平性問題, 在目前已被提出來的解決方法中, 主要區分為兩大類, 分別針對網路設備的封包管理機制 [4-5] 以及無線網路的 MAC layer[6-8] 作修改 其中封包管理機制的部份, 主要針對佇列的管理方式, 修改佇列機制, 使用一個或多個佇列的方式, 透過佇列的管理, 降低佇列分配不公平的問題, 以減緩公平性問題所造成的現象 針對於 MAC 層協定的修改方式,[6-8] 提出修改標準 back-off window 機制, 也有作者提出採用 e 的機制 [10] 或修改基本 DCF 機制 [11], 藉此調整各節點之間取得傳送機會的機率, 也有作者提出全面性的 rerouting 的機制 [12], 以達成負戴平衡及提高整體網路的公平性 如果只採用單一種解決方案, 會有其適用性的問題 在節點的佇列中實作多重的佇列機制, 若沒有配合 back-off window 的調整, 只能解決節點內的節點競爭問題, 而無法有效解決節點與節點之間的連結競爭問題 相對地, 若只使用 back-off window 的調整機制, 只能解決在小量的封包傳輸的情況, 並無法完全解決因佇列分配不公平所造成的不公平傳輸情況 此外, 上述所提出來的方法中, 都是討論無線隨意網路 (ad-hoc networks) 的環境, 並沒有針對 mesh networks 的特性, 亦即網路流量皆透過 MPP 轉送, 提出其適用的解決方案 綜合前述的觀察所得, 本論文提出演算法, 在各節點中, 利用本演算法的判斷機制, 分別動態啟用以下三個機制, 在網路節點中實作 DRR 機制, 解決節點競爭 (node contention) 問題, 使用 RTS/CTS 機制及 CWA (Contention Window Adjustment) 機制, 解決連結競爭 (link contention) 問題, 合併使用上述三種機制, 解決 mesh networks 中的 公平性問題, 並透過 NS2 網路模擬程式的模擬方式, 觀察在串列以及樹狀的網路拓撲之下, 各解決方式的成效 最後證明在三個解決方式同時使用的環境下, 可以有效的改善 mesh networks 中的 公平性問題, 提高整體無線網路的公平性 本篇論文其餘章節組織如下 : 第二章說明 mesh networks 的網路概念, 以及 mesh networks 中造成 公平性問題 的主要原因 第三章說明本論文所提出之 FLNC 演算法及 其細節, 第四章描述模擬的參數 環境 及模擬結果數據, 最後第五章為總結 3

12 第二章背景知識 本小節首先介紹網狀網路 (mesh networks) 的協定概觀, 並說明 mesh networks 依不同功能所定義之節點名稱, 並將 mesh networks ad-hoc networks 及 infrastructure mode 三種無線網路結構特性作比較 ; 其此說明何謂 mesh networks 上的公平性問題, 並詳細說明造成公平性問題的兩大主因 2.1 Overview of Mesh Networks IEEE s 為一尚在草案階段的標準, 其特點在於 : 採用傳統 a/b/g 的 PHY Layer[13], 透過新制定的 Layer-2 的路由協定 (routing protocol) 稱之為 HWMP[14](Hybrid Wireless Mesh Protocol), 並利用節點與節點之間的封包轉送 (forward) 機制, 以降低網路節點中需要直接連結有線網路之節點個數, 透過封包轉送機制, 可降低有線網路的佈線成本, 使 無線網路, 更適合用於骨幹網路的架設 s 中的對於網路節點的定義, 根據其功能的不同, 分成以下幾種, 圖 2.1 為一個 s 網路拓撲, 其中每一節點皆為基本節點, 稱為 MP(mesh point), 而具有能提供無線連結功能服務給 STAs 的 MP, 稱之為 MAP (mesh access point), 而負責將 mesh networks 中的封包 (packet) 橋接 (bridge) 到有線網路的 MP, 則稱之為 MPP(mesh portal) 圖 2.1: IEEE s mesh architecture 4

13 802.11s 其本質為 multi-hop wireless networks, 類似於 ad-hoc networks 然而, 由於其設計概念的不同, 兩者之間, 有其適用性的不同, 以及基本網路特徵的差異 首先, 兩者的適用環境有其顯著的不同,ad-hoc networks 適用於臨時性, 非永久架設的環境, 可能用於兩部或多部電腦之間, 短暫的架設, 互相傳遞資訊 例如軍事上的用途, 作戰非常時期的使用, 且對於各節點之間移動性, 有較高的需求 ;802.11s 則著重於長時間 永久性的基礎建設, 當各節點架設完成, 節點的移動情況, 通常並不會發生 而兩者網路之間的 traffic pattern 也有其顯著的不同,ad-hoc networks 中, 著重的是節點於節點之間的 end-to-end 的 traffic pattern, 相對地, 對外的流量, 並不多, 甚至並不需要對外的流量, 僅僅只有內部的組成節點之間的資料交換 而 mesh networks 的架設, 主要著重在於服務需要連結的 STAs, 提供 STAs 連結至 Internet 的需求, 故大部份的 traffic pattern 皆透過 MPP 對外傳送至 Internet, 或由 Internet 透過 MPP 轉送至 STAs; 而 mesh networks 內部 STAs 之間的相互連結需求較少 表 2.1: 三種網路結構比較表 s ad-hoc Infrastructure mode 適用環境 永久性架設 臨時性的使用 永久性架設 網路流量特性 大部份流量皆流向 MPP 或由外部利用 MPP 大部份的流量為網路內部的 end-to-end 流量 大部份皆為 AP 將外部流向內部的流量, 分配至各 STAs 流向內部節點 移動性 (Mobility) 網路內部各節點, 架設完成後, 極少發生節點移動現象 網路內部各節點, 發生移動的情況, 相當頻繁 除 STAs 外,AP 並不會有移動的情況發生, STAs 也鮮少發生離開 AP 的覆蓋範圍 2.2 公平性問題 (Fairness Problem) Mesh networks 其本質為 multi-hop wireless networks, 所以在發生在 ad-hoc networks 中的 公平性問題, 將會同樣發生在 mesh networks, 一旦發生此問題, 會造成距離 MPP 愈遠的節點, 所能達到的最高傳送速度愈低的現象 Mesh networks 中的 公平性問題 [15], 來自兩個原因, 一 節點競爭 (node contention), 5

14 二 連結競爭 (link contention) 圖 1.1(a)(b) 中, 皆在節點 N1 發生了節點競爭問題, 由於 mesh networks 中的節點, 通常以單一佇列方式存放接收到的封包, 並沒有針對 local traffic 及 forward traffic 作分類, 導致佇列中的封包, 都被到達速度較高的 local traffic 的封包所佔據, 發生佇列分配不公平的現象, 導致 N1 都只傳送本身的 local traffic, 而完全忽略 N2 的封包, 造成 mesh networks 中發生不公平的情況 圖 1.1(a)(b) 為四個節點的串列拓撲, 其中 N1 與 N3 互為隱藏節點, 兩者之間發生了連結競爭 (link contention) 現象, 一旦發生上述現象, 將會造成 N1 及 N3 兩者之間所能成功傳送封包的機會, 產生相當大的落差, 甚至造成 N3 完全無法成功將封包傳送至 N2 本小節茲就上述兩個問題, 分別詳細描述 節點競爭 (Node Contention) Mesh networks 的節點中, 接收封包的存放佇列上會有兩種類的封包 : local traffic 封包與 forward traffic 封包, 如圖 2.2 所示 local traffic 的封包來自於該節點本身所產生以及該節點所服務之 STAs 利用獨立的無線頻道所傳送過來之封包, 由於封包都來由於一個跳躍 (one hop) 以內的距離, 到達速度較快 ; 而 forward traffic 的封包, 來自於網路中其它節點所轉送, 此一類別的封包, 所經過之跳躍數 (hop count) 較大, 到達速度較慢 由於此兩種類之間的到達速度有所不同, 若節點使用單一佇列 FCFS 演算法處理封包, 將會造成各節點中的佇列, 都由較近端之節點所傳送過來之封包所佔據 佇列分布不平均的現象, 是造成 公平性問題 的一大主因 圖 2.2: 節點內部佇列結構示意圖 連結競爭 (Link Contention) MAC 中的 contention windows back-off 機制, 其基本特性使用於 mesh networks, 6

15 會造成公平性問題的主因有二 : 一 back-off window; 二 隱藏節點問題 圖 2.3(a) 中,N2 及 N3 處於同一 collision domain, 而 N2 及 N3 基於 back-off window 機制, 倒數至同一時間點, 於相同時間點發出了資料封包 (data packet) 至下一節點 (next hop); 其中,N2 的封包成功的傳送至下一節點 N1, 而 N3 的封包在傳送至 N2 時,N2 正處於傳送封包的階段, 並無法接收封包 兩個相鄰的節點, 於相同的時間發送相同的封包, 但是由於 N2 及 N3 距離目的地節點的距離不同, 在兩個節點之間, 發生了不公平的結果 隨著 N3 發送封包的失敗, 將導致 N3 將自身的 back-off windows 再次加倍, 並參與下一次的競爭, 由於此現象, 更提高了 N2 成功傳送封包的機率, 而相對的降低了 N3 的傳送機會 (a) 末端兩節點的競爭情況 (b) 隱藏節點問題下的競爭情況 圖 2.3: 四節點發生連結競爭 圖 2.3(b) 中, 其中 N1 及 N2 處於同一 collision domain, 而 N2 及 N3 處於 single collision domain N1 N2 及 N3 構成了 multiple collision domain, 其中 N1 及 N3 互為隱藏節點, 當 N1 及 N3 同時發送封包至下一節點時,N1 得以成功將封包送達至 N0, 而相對地, N3 在傳送封包至 N2 時,N2 同時也接收到 N1 傳送封包的訊號干擾, 導致 N3 所傳送的封包, 無法成功送達 ; 而此現象一旦發生, 亦會造成 N3 無法成功傳送封包, 並發生如前述現象, 不斷將自身 back-off window 加倍, 降低取得傳送機會的機率 當兩個節點處於 single collision domain 之下, 由於下一節點 (next hop) 的不同, 導致 其中一個節點受到較不公平的對待, 造成無法成功傳送封包 ; 然而, 當兩個同時競爭的 傳送機會的結點, 互相處於 multiple collision domain, 可以發現, 距離 MPP 越遠的節點, 7

16 同時受到前述兩種情況的連結競爭, 並於兩種情況之下, 都發生較難取到傳送機會的狀 況, 無法成功傳送封包 為了解決隱藏節點問題, 無線網路中的標準 RTS/CTS 機制, 是一個最立即 也最簡易的解決方案 觀察圖 2.4(a) 中, 啟用 RTS/CTS 機制,N1 及 N3 競爭傳送機會, 而 N3 藉由 RTS/CTS 機制, 成功的在與 N1 的競爭之下, 取得了傳送機會, 得以成功傳送封包至下一節點 接下來觀察圖 2.4(b) 中, 同樣的競爭情況, 然而, 此時,N1 在與 N3 的競爭之中, 同樣藉由 RTS/CTS 機制, 成功取得傳送機會 ; 此時, 從圖中可以觀察到 N3 於 N1 的傳送期間, 作了一次到三次的 RTS 傳送, 由於此現象, 造成 N3 不斷放大自身的 back-off window, 亦會降低節點 N3 取得傳送機會的機率 (a) RTS/CTS 解決末端節點的競爭問題 (b) RTS/CTS 機制的副作用 圖 2.4: 使用 RTS/CTS 機制, 解決公平性問題 觀察上述現象, 可以發現,RTS/CTS 雖然對 multiple collision domain 之下的節點競爭, 發生效果, 降低不公平現象 ; 然而, 也同時造成了額外的副作用, 由於其協定特性, 造成了更不公平的現象發生 歸結 RTS/CTS 機制所造成的現象, 可以觀察到, 其主要問題在於 multiple collision domain 特性使然 圖 2.4(a) 中,N1 藉由 N2 所傳送之 CTS 封包, 取得了 NAV 值, 而得到所需的資訊, 不會於 N3 的傳送期間, 作不必要的封包傳送嘗試 相對地, 在 N1 成功利用 RTS/CTS 取得傳送機會時, 只有相鄰 N1 的 N0 及 N2 能接收到 N1 的 RTS 封包, 而 N2 於收到 N1 之 RTS 封包, 並取得 NAV 資料時, 並不會再將 NAV 資訊轉送至 N3, 導致 N3 無法得知 NAV 資料, 並會於 N1 傳送的過程中, 不斷的嘗試傳送, 造成自身 back-off window 不斷加大 總結上述之現象, 可以發現,RTS/CTS 機制只適用於 infrastructure 結構, 且只適用於 single collision domain, 而在 multiple 8

17 collision domain 之下, 即使發生了微幅的改善, 並也會因其特性, 造成額外的副作用 2.3 Related Works 為了解決 公平性問題, 在目前已有多篇相關的論文被提出來, 也分別從各個角 度切入, 試圖解決此問題, 茲整理如表 2.2 表 2.2: 相關文獻的機制與比較 RTS/CTS MAC DCF C/W Routing Dual Queue Multi Queue This work Yu et al. [4] Nandiraju et al. [5] Nandiraju [6] Jun and Sichitiu[7] Gambiroza [8] Yamada et al. [9] Kleinberg et al. [12] [4-5] 僅用佇列的方式解決 公平性問題, 針對佇列分配不平均的現象, 在 link layer 實作 dual-queue 或 multi-queue 的方式, 可以改善因為節點競爭的問題, 所造成的 starvation [4] 中提出雙重佇列的機制, 將封包分類為 VoIP 封包及一般封包, 分別存放於兩個佇列, 並以優先傳送 VoIP 佇列的封包的原則, 達成保障 VoIP 封包的優先權, 作者宣稱作法簡單, 而且不需要更動 MAC protocol, 然而作者的作法只針對 VoIP 的封包優先傳送, 並無法如本論文提供頻寬調整的機制, 無法達到完全的公平 [5] 的作者, 提出一個稱為 QMMN 的機制, 僅利用單一佇列的空間分配, 達成多重佇列形式的分配形式, 然而作者宣稱的演算法, 基於平均分配給不同來源節點的原則, 根據作者所得的實驗結果, 並無法達成完全的公平, 主要原因為作者並沒有處理 hidden terminal problem, 導致中間節點受到夾擠, 造成嚴重頻寬下降 ; 上述兩篇的作法, 單單解決 link layer 的佇列分配問題, 並無法完全解決 公平性問題, [6-9] 的作者, 都處理 MAC layer 的協定問題, 否則所有問題將會發生在 Mac Layer, 並無法到達 link layer, 所以必須同時處理,[6] 的作者延伸其原有的 QMMN 的演算法, 加上修改 MAC protocol, 利用 ACK 封包, 夾帶 C/W 資訊, 9

18 藉由 C/W 資訊的傳遞, 提供鄰近節點之間的溝通, 透過此機制, 以達成判斷節點本身的 C/W 的調整, 然而作者提出來的 QMMN 演算法, 及 C/W 的計算調整, 都需要較多的計算複雜度, 實作較為困難, 需要於節點設備上採用計算能力較好的處理器, 否則運算成本可能會造成該節點上之運算負擔, 甚至影響傳輸效能 此外,[12] 提出使用 re-routing 的方式解決 公平性問題, 然而此方法只適合於規模較大 具有多重路徑可供採用的網路結構, 如本論文中所討論之串列網路拓撲或是樹狀網路拓撲, 並無法使用 re-routing 的方法作改善 前述的所有相關的論文中, 都是針對 ad-hoc networks 所作的討論, 尚未有針對 mesh networks 的特性提出相關的解決方式 而本論文主要討論當在 mesh networks 中發生 公平性問題 時的解決方法, 並針對 mesh networks 的特性, 提出 FLNC 演算法, 於 mesh networks 中各個節點實作此演算法, 使各個節點具有動態判斷三種機制的開啟或關閉的功能 10

19 第三章 Fair Link and Node Contention 本章詳述本論文所提出 Fair Link and Node Contention (FLNC) 演算法 本演算法運作於 mesh networks 中網路節點 (MP) 上, 其主要概念為合併使用三種公平性問題的解決機制 (mechanisms) 本演算法判斷根據各節點所觀察的網路流量 雙佇列所存之封包總量比例 封包傳送目的地之總量統計, 動態決定開啟或關閉包括有 DRR RTS/CTS 與 Contention Window Adjustment 等三個機制 當 mesh networks 中的節點都採用本演算法, 可以達成頻寬控制 避免公平性問題 防止節點餓死 (starvation) 等問題 3.1 演算法概觀 公平性問題, 主要是由於節點之間的節點競爭以及連結競爭所造成, 為了要解決節點競爭問題, 必須採用第一種解決機制, 在每個節點中實作雙重佇列, 並採用 DRR 演算法, 調節 local traffic 與 forward traffic 的比率, 藉以調節兩種類封包的比率 解決了節點競爭問題之後, 只能解決在 single collision domain 之內的節點的競爭問題, 而在 multiple collision domain 的節點之間, 必須進一步透過 RTS/CTS 及 CWA 機制, 處理節點彼此之間的連結競爭問題, 否則距離 MPP 較遠之節點的封包, 將會因為遭遇到連結競爭, 導致無法取得封包傳送機會以傳送封包, 發生餓死現象 FLNC 演算法的主要目標, 是在避免 mesh networks 中發生公平性問題, 導致網路中某些節點餓死 如何在每個節點中, 動態的開關本論文所提出的三個機制, 為 FLNC 演算法最主要的功能 由於三種機制的開啟或關閉, 都直接影響到該網路之整體效能, 因此本演算法必須針對節點上的流量統計資訊, 判斷是否需要開啟何種機制 3.2 FLNC 演算法 圖 3.1 為 FLNC 演算法的判斷機制流程圖,FLNC 演算法透過監看節點內部對外送 出的封包, 並根據目前所傳送的封包的表頭, 記錄目前該節點對外傳送的頻寬 封包傳 送的目的地等資訊, 並透過監看到的封包資訊, 提供演算法開關三種機制的判斷依據 11

20 首先第一個要決定的為 DRR 機制, 透過監看節點內部 local traffic 所獲取的流量, 是否超過額定的 threshold, 作為啟用 DRR 的判斷依據 當流量並未超過額定的 threshold 時, 代表 local traffic 只有占用少部分的整體佇列, 因此並不需要啟用 DRR 機制, 即可達成公平的頻寬分配 ; 當超過額定 threshold 時, 由於規範於節點與節點之間的 CSMA/CA 機制, 並無法解決節點內部 local traffic 與 forward traffic 競爭所造成之公平性問題, 此時則需要啟動 DRR 機制, 避免 local traffic 的流量, 阻擋了其它節點轉送過來的流量 第二個機制, 為 RTS/CTS 機制, 本機制的主要目的在於使用於 multiple collision domain 的情況下, 減緩末端節點所遭遇的連結競爭 (link contention) 問題, 然而 RTS/CTS 機制的開啟或關閉, 對於整體網路的效能, 有著極大的影響, 所以在必要時, 才開啟, 否則會造成整體網路效能嚴重下降 判斷是否開啟 RTS/CTS 機制, 所監看的是節點對外送出的封包目的地, 如果目的節點, 並不是該節點的下一個節點, 表示該節點有將封包送至 single collision domain 之外的需求發生, 則必須採用 RTS/CTS 機制傳送該封包, 以避免因為隱藏節點問題, 導致該節點無法搶得傳送機會, 傳送該封包 第三個為 CWA 機制, 監看的為目前的 forward traffic 的流量是否超過額定的 threshold, 代表存在遠方節點須透過本地節點傳送封包, 此時啟動 CWA 機制, 可避免由於 local traffic 流量過大, 阻擋了遠端節點所傳送過來的封包傳送機會 圖 3.2 為 FLNC 演算法架構圖, 主要分成兩個部份 其中左側為 FLNC 決策機制, 根據所監測的節點上 local traffic 的流量, 以及設定的相關拓撲資訊, 決定其相關的參數, 如 DRR ratio CWA ratio, 並透過目前的流量值, 決定開啟何種機制 右側部份為封包處理機制, 根據每一個待傳送的封包, 依目前三個機制的開啟或關閉的情況, 決定是否依機制作傳送 12

21 圖 3.1: The flow chart of FLNC algorithm 圖 3.2: The architecture of FLNC algorithm 13

22 表 3.1 為 FLNC 演算法的虛擬程式碼 表 3.1: Pseudo code of FLNC algorithm Procedure FLNC INPUT CurrentStatics:CS Topology:T Packet:PKT OUTPUT DRR RTSCTS CWA 1 Update CS 2 threshold1 := DecisionTable[T] 3 IF DRR=OFF 3 IF CS > threshold1 4 DRR:=ON 5 ENDIF 6 ELSE 7 IF CS < threshold1 8 DRR:=OFF 9 ENDIF 10 ENDIF 11 threshold2 := DecisionTable[T] 12 IF PKT.NEIGHBOR!= NEXTHOP 13 Padding RTS/CTS 14 ENDIF 15 threshold3 := DecisionTable[T] 16 IF CS < threshold3 17 Transmit with CWA ratio 18 ENDIF End Procedure 3.3 演算法所使用之三種機制說明 本演算法基於改善 mesh networks 中公平性問題的目標, 提出三種機制的合併使用, 並利用演算法的判斷機制, 提供動態開啟或關閉機制, 後面三個小節, 分別詳細描述三 種機制的動機及採用原因 DRR 機制 首先第一個機制為 DRR 機制, 本機制的作法為在各節點中實作雙佇列結構, 將 local traffic 以及 forward traffic 分別使用不同佇列作存放, 並利用 DRR [16] 在兩個佇列之間作排程, 藉此達到兩佇列之間的封包傳送比率調節, 達成頻寬控制的目標 利用 DRR 機制對此兩類的封包作排程, 解決造成 mesh networks 的公平性問題的節點競爭問題, 而 DRR 機制所具備的頻寬調節能力, 並可提供佈建的頻寬調整需求, 提高整體網路的頻寬的調節能力 14

23 圖 3.3 為各節中 DRR 機制實作示意圖 將兩種類別的流量 local traffic 及 forward traffic, 以兩個獨立的佇列存放, 解決節點競爭問題, 並在挑選待傳送封包的機制, 加上 DRR 機制的實作, 利用 DRR 機制的特性, 提供流量控制的能力, 如此的設計, 不但解決了節點上的節點競爭問題, 並同時使各節點具備了流量控管的機制, 使得整體網路具備的頻寬控制能力 圖 3.3: DRR Ratio Control 機制實作示意圖 RTS/CTS 機制 其次為 RTS/CTS 機制, 前小節的 DRR 機制, 提供了解決節點競爭的能力, 然而, 其外一項造成公平性問題的原因, 連結競爭, 必須透過 RTS/CTS 機制協助, 單單使用 DRR 機制, 僅能對於到達該節點上之封包, 作控管以及排程, 然而, 一旦發生連結競爭問題, 位於 multiple collision domain 中之末端節點, 將面臨到無法取得傳送機會傳送封包的情況, 當封包無法成功傳遞到下一個節點, 各節點上之雙佇列機制, 會發生其中之 forward traffic 的佇例, 封包數量遠少於 local traffic 的佇例, 則此時, 即使在各節點上實作 DRR 機制, 也會發生沒有足夠的封包數量可排程的問題 圖 2.4(b) 中的 N1 及 N3 發生連結競爭 (link contention) 問題, 並同時存在著隱藏節點問題, 導致 N3 完全無法成功將封包送到至下一節點 N2 利用 RTS/CTS 機制提供解決連結競爭 (link contention) 的能力, 透過 RTS/CTS 機制, 末端節點 N3 得以利用傳送 RTS 封包, 得以與 N1 及 N2 同時競爭傳送機會, 藉此避免 N3 遭遇餓死問題 (starvation) 15

24 3.3.3 Contention Windows Adjustment 機制 圖 2.4(a) 中的 N1 及 N3 雖然藉由 RTS/CTS 機制, 得以於不用的 collision domain 之下, 得以公平的爭取傳送機會 ; 然而從圖 2.4(b) 中的節點互動, 可以觀察到, 對於 N1 及 N3 而言, 每一次的取得競爭機會下, 仍然存在其不公平的現象, 造成此現象, 主要的原因, 在於兩者之間距離目的節點的距離不同, 而 NAV 值的傳遞距離有限, 而此時距離目的節點較遠的節點 N3, 相對於節點 N1 來說, 競爭力仍然較弱 ; 所以必須透過 CWA 機制的彌補, 提高 N3 參與 N1 及 N2 的競爭傳送機會的能力 圖 3.5 為 CWA 機制實作示意圖, 由於末端節點會遭遇缺乏 NAV 值的資訊, 造成不 必要的傳送嘗試, 使得加大自身的 back-off window 的情況, 所以必須透過調整各節點之 間的 back-off window 的方式, 以補償此差異 圖 3.4: CWA 機制實作示意圖 在 CWA 機制的調整原則上, 以距離 MPP 的距離為參考值, 當該節點距離 MPP 較近時, 表示該節點在競爭成功取得傳送機會機率, 大於距離 MPP 較遠的節點, 會因為 RTS/CTS 機制所帶來的 NAV 值資訊傳遞問題, 造成影響到末端節點的傳送機會, 所以使用 CWA 機制, 根據 CWA 機制所設定的 ratio 值, 調整該節點的 back-off window, 例在節點 N1 在四個節點的網路拓撲中, 將其 CW-min 根據 CWA 的 ratio 值, 乘上 不等的倍數, 提高末端節點取得傳送機會的機率 在此需要注意的部份在於,CWA 機制, 主要用於協助 RTS/CTS 機制的改善, 可以將 CWA 機制視為依附於 RTS/CTS 機制而產生的機制, 也就是說, 單單使用 CWA 機制, 沒有搭配 RTS/CTS 機制, 並無法為末端節點, 爭取到更多的傳送機會 16

25 第四章 Simulation Studies 本章利用模擬的方式, 分別驗證本論文所提出的三個機制, 應用於串列網路拓撲以及樹狀網路拓撲的結果 並利用網路模擬程式 -NS2 的模擬, 觀察各機制的效果及成效 第 4.1 小節說明模擬環境與參數設定, 第 4.2 小節於串列網路拓撲的中間節點實作 DRR 機制, 利用 DRR 機制的特性, 改善節點競爭的現象, 並觀察 DRR 機制所能提供的調整能力為何 接下來第 4.3 小節討論 RTS/CTS 機制, 並透過模擬結果了解 RTS/CTS 機制對於公平性問題的改善能力, 並討論其不足的部份 第 4.4 小節觀察利用 DRR 機制搭配 CWA 機制, 但並不啟用 RTS/CTS 機制, 觀察僅採用此兩機制的配合, 其效果為何 第 4.5 小節同時採用 DRR 機制配合配合 RTS/CTS 機制, 並利用 CWA 機制彌補 RTS/CTS 機制的不足, 觀察在此三個機制同時使用於該網路拓撲上, 針對公平性問題, 所能達成的改善能力為何 第 4.6 小節觀察所有方法 (full function) 使用在串列網路拓撲及樹狀網路拓撲上的效果, 與未實作任何機制的環境比較 最後在第 4.7 小節, 將實驗所觀察之數據, 整理成 Decision table, 提供網路架設參數 4.1 模擬環境 表 4.1 為本章所使用的相關模擬參數 其中於 NS2 的版本選擇為目前官方所釋出之最新版本,NS2 v2.33[17], 作業系統的平台所選用的為 Linux Fedora Core 5, 頻寬的選擇採用目前市面上最普遍的 g 的 54 Mbps 的頻寬, 而在各節點之間的有效距離設定為 250 公尺, 為了避免路由協定的影響, 本論文採取靜態路由的協定, 以避免無效的路由, 影響實驗結果的觀察 而在介面佇列部份, 修改 NS2 v2.33 內部所釋出之 PriQueue, 使用內建之 DRR 演算法, 達成於各網路節點上實作 DRR 機制的目的 最後在 UDP 封包上限, 設定為 2500 Bytes, 而實際傳送之 CBR 封包大小, 設定為 2400 Bytes 並引用 Fairness Index[18] 的計算方式, 協助觀察各節點之間所分配到之頻寬比率, 利用 Fairness Index 可以針對各節點之間的觀察差異, 提供量化比較的數據, 藉以判斷公平性 17

26 表 4.1: 模擬參數設定 Parameter Settings Physical Layer Bandwidth 54 Mb Transmit Power Carrier Sense Power e 10 Receive Power Threshold e 10 MAC Layer Rate for Data Frames 54 Mb Rate for Control Frames 1 Mb RTS Threshold 100 or 5000 (Enable or Disable RTS/CTS) Interface Queue DRR over PriQueue UDP packet size 2500 CBR packet size DRR 機制 控管 single Collision Domain 的公平性問題 首先觀察 DRR 演算法, 使用在 Mesh Network 環境下, 針對節點競爭現象的改善以及頻寬調整的效果 觀察圖 4.1(a) 中之網路拓撲, 其中 N1 及 N2 上皆接收來自其服務的 STAs 所傳送的 CBR traffic, 藉由 UDP 封包傳送 本實驗節點 N1 中實作 DRR 機制, 利用 DRR 機制針對 N1 自身所服務的封包流量, 以及由 N2 所傳送過來之封包流量, 使用 DRR 的 ratio 調整, 觀察 DRR 演算法的效果, 對於調節各節點上之流量比例的控制能力 圖 4.1(b) 中為最原始之設定 ( 以下為 0:0 模式 ), 並無實作 DRR 機制於 N1 上, 從圖中可看出, 當網路流量在 10 Mbps 以下,N1 及 N2 都得以透過 的 CSMA/CA 機制, 得出相當公平的流量分配 ; 當流量超過 10 Mbps 之後, 兩節點各別所能取得之頻寬, 開始發生的變化, 隨著 N1 上所送出之流量的提高,N1 逐漸獨占所有的頻寬, 直到 27 Mbps 的點上, 兩者之間的所分配的頻寬達到飽和且穩定的狀態 最終 N1 獨占了所有可用的頻寬, 而 N2 發生了餓死現象, 完全無法取得機會傳送封包 圖 4.1(c) 中, 節點 N1 實作了 DRR 機制, 並將其 Ratio 調整為 1:1, 亦即 N1 自身的 比例為 1, 而為 N2 所轉送的比例, 也為 1 從圖中可看出, 採用了 DRR 機制於 N1 後, N1 及 N2 兩者之間的流量, 藉由 DRR 的機制, 得到預期的頻寬分配, 兩個節點的流量 18

27 從 0 到 30 Mbps 之間, 維持 1:1 的比例分配 圖 4.1(d) 中將 ratio 調整為 1:2, 其中 N1 比例為 1, 而為 N2 所轉送的比例, 調整為 2 從圖中可看出, N1 及 N2 兩者之間的流量, 在 10 Mbps 之後飽和, 並維持預期的 ratio (a) 三個節點串列網路拓撲 (b) 未實作 DRR 機制的實驗結果 (c) 實作 DRR 機制,Ratio 1:1 (d) 實作 DRR 機制,Ratio 1:2 圖 4.1: 三節點串列網路拓撲, 採用 DRR 演算法實驗結果 從實驗結果, 我們可觀察到, 在節點 N1 實作 DRR 機制, 調整節點 N1 及 N2 的頻 寬分配, 並從模擬結果可得出,DRR 機制在兩個存在於 single collision domain 的節點, 可以達到準確的頻寬分配 圖 4.2 為利用 fairness index 作為一比較參數, 其中,0:0 模式的曲線, 隨著頻寬的上升, 造成 fairness index 不斷的下降, 最終降至 0.5,0.5 為兩個節點之間最不公平的結果, 亦即其中有一節點發生了餓死情況 而採用了 1:1 及 2:2 的曲線, 隨著各節點流量的增加, 維持了預期的 Fairness Index, 並不會隨著各節點提供流量的增加, 而影響其 fairness 19

28 index 利用此圖的比較方式, 可以幫助觀察各 ratio 所能得到之 fairness index 較符合實 驗設定所預期的結果 圖 4.2: 三節點串列網路拓撲的 fairness index 圖 4.3 為一四個節點串列網路拓撲, 其中跟前一個實驗不同之處在於此拓撲中存在兩個 multiple collision domain, 其中 N1 N2 以及 N2 N3 各自形成一個獨立的 collision domain 從實驗結果圖 4.4(a) 中可以觀察到, 在未實作 DRR 機制時,N2 在 N1 送出 25Mbps 的流量時, 發生了餓死現象, 而由於 N3 位於距離 MPP 最遠, 節點 N3 更早在 N1 及 N2 送出 6Mbps 的流量時, 就發生了餓死現象 圖 4.3: 四節點串列網路拓撲 接著從分別調整 N1 上之 DRR ratio 從 1:1 到 1:2, 觀察三個節點所能分配到的頻寬, 圖 4.4(b), 圖 4.4(c), 圖 4.4(d) 中, 可以觀察到,DRR 機制對於 N1 及 N2 兩個節點之間的頻寬分配, 達到如同前一個實驗中,single collision domain 的效果, 而節點 N3 所能分配到的頻寬, 並沒有因為 DRR Ratio 的調整, 而能取得更高的頻寬 20

29 (a) 未實作 DRR 機制的實驗結果 (b) N1 N2 : Ratio 1:1 (c) N1 N2 : Ratio 1:2 (d) N1 Ratio 1:1,N2 Ratio 1:2 圖 4.4: 串列網路拓撲模擬結果 圖 4.5 為四個節點串列網路拓撲的 fairness index 數據,0:0 模式的曲線, 隨著頻寬的上升, 最後降至 0.33, 此值表示三個節點之間, 僅有一個節點得以傳送, 而其它兩個節點餓死 而其它三個曲線, 雖然 N1 及 N2 得以使用 DRR 機制, 維持頻寬的分配, 而整體的 fairness index 因為 N3 的餓死, 導致 fairness index 能分別維持在 0.7 及 0.62 圖 4.5: 串列網路拓撲 fairness index 21

30 4.3 RTS/CTS 機制 - 解決隱藏節點帶來的公平性問題 本小節的實驗為在圖 4.3 的網路拓撲下, 使用 DRR 機制配合 RTS/CTS 機制, 觀察 使用此兩個機制, 對發生於節點 N3 上連結競爭問題, 所能達到的改善效果 從圖 4.6(a) 未啟用 RTS/CTS 機制的圖中, 可以看出, 節點 N3 發生了嚴重的餓死現象, 而圖 4.6(b) 中, 啟用了 RTS/CTS 機制後,N3 所分配到的頻寬, 藉由 RTS/CTS 機制的啟用, 微幅增加了所能分配到的頻寬, 但是僅僅 RTS/CTS 機制所能達成的效果, 仍然有限 從圖 4.7 可以更清楚觀察到, 雖然 RTS/CTS 機制並無法完全解決節點 N3 所遭遇到的餓死現象, 但是從 fairness index 的觀察中, 可以看出,RTS/CTS 機制, 對於節點 N3, 還是達到了改善的效果 (a) 未啟用 RTS/CTS 機制 (b) 啟用 RTS/CTS 機制 圖 4.6: 串列網路拓撲, 啟用 RTS/CTS 機制 圖 4.7: 串列網路拓撲, 啟用 RTS/CTS 機制的 fairness index 22

31 4.4 CWA 機制 - 無配合 RTS/CTS 機制時, 無法發生效果 本小節的實驗為在圖 4.3 的網路拓撲下, 使用 DRR 機制配合 CWA 機制, 但並沒有 開啟 RTS/CTS 機制, 觀察單單使用此兩機制, 能否改善節點 N3 的所遭受的連結競爭問 題 根據前小節的結果得知,RTS/CTS 機制, 對於末端節點 N3 所面臨的連結競爭, 造成了相當有限的改善效果 本小節接著實驗單獨使用 CWA 機制, 沒有搭配 RTS/CTS 機制時, 能否單獨靠 CWA 機制, 配合 DRR 的調節, 達成本論文所要求的公平性 所以本小節分別開啟 CWA 機制, 觀察 Ratio 從 2~5 時作用, 了解 CWA 機制對於末端節點所發生的連結競爭問題, 改善效果為何 依序由圖 4.8(a)~(d), 觀察 ratio 分別為 2~5 的實驗結果 觀察實驗結果圖 4.8(a)~(d),CWA ratio 分別為 2~5 的情況, 可以發現, 無論怎麼調整 CWA ratio, 對實驗結果, 並沒有造成影響, 所以四組實驗的結果, 完全一致 造成此現象的原因, 是由於沒有 RTS/CTS 機制的配合所造成, 觀察節點 N3 上所發生的競爭情形, 可以了解到, 雖然 N1 及 N2 透過 CWA 所設定的 ratio, 加大自身的 contention widows size, 將機會讓給 N3, 然而, 由於 N3 同時面臨了與 N1 及 N2 的連結競爭, 並面對與 N1 的不公平的連結競爭 為了要完全解決 N3 所面臨的不公平對待, 必須再搭配 RTS/CTS 機制, 利用其機制的特性, 協助 N3 得以與 N1 作較公平的連結競爭, 以彌補 N3 所遭受的不公平對待 觀察到圖 4.9 的 fairness index, 可以更明確的比較此四種 ratio 的情況下, 四種 CWA ratio 實驗曲線, 完全一致, 也就是表示, 無論 CWA ratio 如何調整, 對於各節點之間的 連結競爭情況, 並沒有造成任何的影響, 無法解決此網路拓撲上所發生的不公平現象 23

32 (a) CWA Ratio 2 (b) CWA Ratio 3 (c) CWA Ratio 4 (d) CWA Ratio 5 圖 4.8: 串列網路拓撲 CWA 實驗 圖 4.9: 串列網路拓撲,CWA 實驗 fairness index 4.5 CWA 機制 - 補償 RTS/CTS 機制所產生的副作用 本小節實驗 Contention Window Adjustment(CWA) 機制, 由於前小節的結果觀察得出, 雖然 RTS/CTS 機制, 對於末端節點 N3 的餓死現象, 造成了微幅的改善效果, 但是效果 24

33 有限, 不符合本論文所要求的公平性 ; 而使用 DRR 機制搭配 CWA 機制, 完全無法改善 所以本小節同時採 DRR 機制, 搭配 RTS/CTS 機制加上 CWA 機制, 觀察 RTS/CTS 搭配上 CWA 機制的作用, 對於末端節點的餓死現象的改善效果 根據 CWA 的 ratio 設定, 本小節實驗在各節點上調整 CWA 的 ratio, 依序由圖 4.10(a)~(d), 觀察 ratio 分別為 及 5 的情況 首先觀察到圖 4.10(a) 中,CWA ratio 為 2 的情況, 對比於前小節圖 4.6(b) 的結果, 可以觀察到利用 RTS/CTS 搭配 CWA 機制, 有效地改善了 N3 所面臨的餓死情況, 但此 ratio 的調整情況, 並無法達成完全的公平, 接著觀察圖 4.10(b) ratio 為 3 的情況, 可以發現三個節點之間所分配之頻寬, 得以達到更為公平的分配, 但仍有其落差, 隨著 CWA ratio 的加大, 到 ratio 為 5 的情況下, 可以發現利用 CWA 機制, 可以達成完全公平之頻寬分配的效果, 符合本論文所要求之公平性的調整 (a) CWA Ratio 2 (b) CWA Ratio 3 (c) CWA Ratio 4 (d) CWA Ratio 5 圖 4.10: 串列網路拓撲,DRR+RTS/CTS+CWA 實驗結果 25

34 觀察到圖 4.11 的 fairness index, 可以清楚觀察在四種不同 ratio 的情況下, 所能達成 的公平性的差異, 可以觀察出在 ratio 為 5 的情況下, 無論在各節點的各種 offered load 的變化, 都能夠提供該網路拓撲的各節點之間的公平性 圖 4.11: 串列網路拓撲,DRR+RTS/CTS+CWA fairness index 4.6 Full Function 從前面三個小節分別模擬所得的結果, 可觀察到同時採用三種機制時, 對公平性問題能得到較佳的解決 本小節同時採用三種機制, 在此稱之為 full function; 在串列網路網路拓撲及樹狀網路拓撲上採用 full function 作模擬, 以無實作任何機制 (no function) 的模擬作為對照組, 了解同時採用三種機制的 FLNC 演算法, 對公平性問題的改善效果 首先我們觀察串列網路拓撲, 對圖 4.3 的四個節點的串列網路拓撲, 分別模擬無實作機制 (no function) 及實作三種機制 (full function) 作比較, 觀察 full function 所能達到的改善效果 其中 full function 所採用的參數為 :DRR ratio 在 N1 及 N2 分別設定為 1:2 及 1:1, RTS/CTS 機制開啟, 並將 CWA ratio 設定為 5 觀察圖 4.12(a) 及圖 4.12(b) 兩組實驗數據,no funtion 的實驗中, 當 offered load 到達 25 Mbps 時, 在此串列網路拓撲中, 最大及最小的節點頻寬, 有 9.5 Mbps 的差異發生 ; 而在採用 FLNC 演算法的實驗, 可以完全消除因公平性問題所造成的頻寬差異 26

35 (a) 未實作機制 no function (b) 實作 full function 圖 4.12: 串列網路拓撲 no function V.S full function 觀察圖 4.13 為四個節點的串列網路拓撲, 比較 no functino 及 full function 的 fairness index 在無實作任何機制(no function) 時,fairness index 會隨著 offered load 的增加, 到 30 Mbps 時, 降至 0.33, 而實作 FLNC 的 full function, 在 offered load 從 0 Mbps 到 30 Mbps 都能維持 fairness index 為 1, 亦即最公平的情況, 每個節點所能獲得的頻寬都相同 圖 4.13: 串列網路拓撲 fairness index 圖 4.14 為五個節點的樹狀網路拓撲, 為 mesh networks 架設中常見之基本架構, 對 此樹狀網路拓撲, 模擬參數為 :DRR ratio 在 N1 及 N2 分別設定為 1:3 及 1:2,RTS/CTS 機制開啟,CWA ratio 設定為 5 27

36 圖 4.14: 五個節點的樹狀網路拓撲 觀察圖 4.15(a) 及圖 4.15(b) 中,no funtion 的實驗中, 當 offered load 到達 25 Mbps 時,, 最大及最小的節點頻寬, 發生 9.5 Mbps 的差異 ; 而在採用 full function 時,offered load 從 0 Mbps 到 30 Mbps 時, 各節點所獲得的頻寬皆維持在 1 Mbps, 達到完全的公平 (a) 未實作任何機制 (b) 實作 full function 圖 4.15: 樹狀網路拓撲模擬結果觀察圖 4.16 中的結果, 採用 full function 的網路拓撲, 可以維持準確的公平性, 各節點之間所送出之流量, 從 0 Mbps 到 30 Mbps, 皆可維持該網路拓撲中的 fairness index 為 1, 亦即完全的公平 圖 4.16: 樹狀網路拓撲 fairness index 28

37 4.7 Summary with a Decision Table 表 4.2 利用前面四小節實驗所得出之數據, 作整理所建構出之參考表格, 本論文稱 之為 Decision Table 在此表中, 主要根據不同的網路拓撲以及觀察各節點之 offered load 為參考值, 判斷三種機制開啟及關閉的考量, 及其參數值, 茲整理如下 : 當在 single collision domain 之下, 只需使用單一的 DRR 機制,ratio 的調整則視該節點所連結之鄰居節點 (neighbor) 的個數作調節即可, 無需使用其它機制 而當網路拓撲超過 single collision domain, 處於 multiple collision domain 之下, 則需要視各節點上之 offered load 來決定是否開啟 RTS/CTS 機制以及 CWA 機制, 以三個節點的串列拓撲的例子, 在各節點上 offered load 大於 2 Mbps 時, 則必須開啟 RTS/CTS 機制及 CWA 機制 ; 而在三個節點數之樹狀拓撲, 則在各節點上之 offered load 大於 2 Mbps 時, 須開啟 RTS/CTS 及 CWA 機制, 並視各節點所連結之鄰居節點 (neighbor) 個數, 調整該節點上之 DRR Ratio 表 4.2: Decision Table Case DRR RTS/CTS CWA(ratio) 2 hop Chain 1:2 No No 2 hop Tree 1:2 No No 3 hop Chain Offered load < 2 Mbps 1:2, 1:1 No No Offered load > 2 Mbps 1:2, 1:1 Yes Yes 3 hop Binary Tree Offered load < 2 Mbps 1:3, 1:2 No No Offered load > 2 Mbps 1:3, 1:2 Yes Yes 29

38 第五章結論 本論文探討無線網狀網路中的公平性問題以及解決方式 我們首先詳細說明公平性問題的成因, 包括有單一佇列造成的節點競爭問題 (node contention), 隱藏節點問題 (hidden terminal problem) 以及使用 RTS/CTS 機制造成的連結競爭問題 (link contention) 為了解決節點競爭, 我們使用 DRR 演算法, 調整本地封包與遠端封包兩者之間的比率分配 ; 為了解決連結競爭問題, 我們併用 RTS/CTS 機制與 CWA 機制, 增加遠方節點的成功傳送機率 與 [4][7] 的簡單雙重佇列機制及 QMMN 相比, 本論文顯示使用常見且複雜度較低的 DRR 演算法, 亦可解決 single collision domain 下的 公平性問題, 透過本論文所提出來的演算法及三個機制, 可以在 Mesh networks 的環境中, 達到完全公平頻寬分配, 而不會發生隨著距離 MPP 的距離的增加, 傳輸速度下增的現象 根據實驗的結果發現, 作出以下的觀察 : 1. DRR 機制在 single collision domain 的環境下, 不需要搭配 RTS/CTS 機制或是 CWA 機制, 即可根據 DRR 所設定的 ratio, 達到完全的公平 2. RTS/CTS 機制, 雖然解決了末端節點所面臨的連結競爭問題, 但是卻也因為其協定的設定, 造成了額外的連結競爭問題 3. 在 multiple collision domain 的環境下, 使用本論文所提出來的三個機制, 可以同時解決節點競爭問題 (node contention) 及連結競爭問題 (link contention), 達成完全的公平 並藉由模擬, 我們驗證上述三種方法同時使用的情況下, 能有效地解決四個節點串 列網路拓撲以及五個節點樹狀網路拓撲的公平性問題 並以此實驗數據, 整理出一個 Decision Table, 此表格所提供之參考數據, 可供佈建 mesh networks 的參考依據 由於本論文探討的網路規模較小, 在未來, 我們將研究大型無線網狀網路上的公平 性問題, 包括有 : 如何佈建多個 portals 以切割大型無線網狀網路, 並將本研究應用於此 分群後的網路 ; 以及多個 portals 所造成的公平性問題 30

39 參考文獻 [1] IEEE P802.11s/D2.03, Wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment: mesh networking, Nov [2] I.F. Akyildiz, X. Wang and W. Wang, Wireless mesh networks: a survey, Computer Networks, vol. 47, no. 4, pp , [3] M.L. Sichitiu, Wireless mesh networks: opportunities and challenges, in Proc. of World Wireless Congress, May [4] J. Yu, S. Choi and J. Lee, Enhancement of VoIP over IEEE WLAN via dual queue strategy, in Proc. of IEEE ICC 04, pp , Jun [5] N. Nandiraju et al., A Novel Queue Management Mechanism for Improving Performance of Multihop Flows in IEEE s based Mesh Networks, in Proc. of 25th IEEE International Performance Computing and Communications Conference (IPCCC), [6] Nagesh S. P. Nandiraju, A Cross-layered approach for Achieving Fairness in Multihop Wireless Mesh Networks, Ph.D. dissertation, Dept. of Elect. and Comp. Eng. and Comp. Sci. of the College of Eng., Univ. of Cincinnati, May [7] J. Jun and M. L. Sichitiu, Fairness and QoS in multi-hop wireless networks, in Proc. of IEEE Vehicular Technology Conference (VTC), pp , [8] V. Gambiroza, B. Sadeghi and E. Knightly, End-to-End Performance and Fairness in Multi-hop Wireless Backhaul Networks, in Proc. of MobiCom, [9] A. Yamada, A. Fujiwara and Y. Matsumoto, Enhancement of mesh network oriented IEEE MAC protocol, in Proc. of 10th Asia-Pacific Conference on Communications, vol. 1, pp , Sept [10] K. Duffy, et al., Improving fairness in multi-hop mesh networks using e, in Proc. of IEEE International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt '06), pp. 1-8, Apr [11] Y Chetoui, N Bouabdallah and J.B. Othman, Resolving the Unfairness Limitations of the IEEE DCF, International Journal of Computer Science and Network Security (IJCSNS), vol. 7, no. 1, Jan [12] J Kleinberg, Y Rabani and E Tardos, Fairness in routing and load balancing, 40th Annual Symposium on Foundations of Computer Science, [13] IEEE Computer Society, : Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, [14] A. Joshi, et al., HWMP Specification, IEEE P Wireless LANs, document IEEE /1778r1, Nov [15] L. Li and P.A.S Ward, Structural unfairness in based wireless mesh networks, in Proc. of the 5th Annual Communications Networks and Services Research Conference (CNSR 2007), vol. 1 pp , May [16] M. Shreedhar and George Varghese, Efficient fair queuing using deficit round-robin, IEEE/ACM Transactions on Networking, vol. 4, issue 3, pp ,

40 [17] NS-2 project, [18] R. Jain, A. Durresi and G. Babic, Throughput Fairness Index: An Explanation, ATM Forum Contribution, Feb