Advisor : Dr. Frank Y. S. Lin Present by :Yi-Wei Li 暑期進度報告 Advisor : Dr. Frank Y. S. Lin Present by :Yi-Wei Li 問題描述 (WHY QOS) 自己解法 LITERAL REVIEW 問題與解法 缺點與改善 其他方法解決之 三到五篇 (一篇兩到三頁) 自己的想法 要用何種APPROACH 完整解決單一問題 Information Management Dept. National Taiwan University 2019/1/15

outline Introduction Literature review Our problem 2019/1/15

outline Introduction Literature review Our problem 2019/1/15

Introduction Wireless mesh network have received much attention in recent years due to its low up-front cost easy network maintenance robustness reliable service coverage 在 multihop wireless mesh network，節點藉由連上mesh router (TAP) 以multihop 方式由gateway向backhaul傳送資料至internet。 而MESH NETWORK必須由 backhaul，transient access point(另一種說法為MESH ROUTER)，mobile client上敘三種組成 至少須有一個Backhaul對外聯繫 在此我們考量infrastructure-based mesh network，也就是說 transient access point 僅有接收用戶上傳之traffic flow及幫其他AP作relay，並不會自行產生資料 2019/1/15

Fairness Temporal fairness: Spatial bias fairness: Within a collision area, the allocation of resources is controlled to ensure that the channel access time is fair for all nodes. Spatial bias fairness: The fairness scheme assigns channel access time uniformly to flows by allocating more resources to nodes located further away from the destination. MESH NETWORK雖然仍在開發中階段，在其中一個重要的議題為公平對待用戶也就是fairness。FAIRNESS最基本的定義就是將資源均等的分給所有客戶。另一種可能情況為有些具有較高度優先權的連線必須優先處理。 在同一個gateway服務的區域中，既然用戶使用同一個backhaul對外，那麼不論聯繫到任一AP都該被均等的對待並享有相同資源在使用者附相同費用情況下。然而現實情況則不然，用戶所分享到的資源(在這裡以頻寬為例)是隨著距離gateway HOP數上升而急速下降。 給定何種RESOURCE(切入 fairness) 。傳統的Fairness議題注重在資源分配，在此常見的網路資源可以被粗分為下列兩項 (1)占有頻寬的時間，(2)每次傳輸享有多少頻寬。FTP、MAIL server類的傳輸對頻寬相當計較，而multimedia、 視訊會議、 VOIP等 則是對延遲感到相當敏感。然而對end-to-end fair而言，許多處理該類的研究都以下兩項FAIRNESS為基礎取得目標值 T指的是……在服務的區間內妥善的分配資源，使得每一條FLOW使用相同長度的時間來傳送資料 S指的是……既然所有的TRAFFIC FLOW使用相同傳輸時間，更多的資源必須被投注在較遠的ROUTER才能達成不論距離GATEWAY遠近均享有同品質的服務 1…… 2.相對於較近者， 對較遠者投入更多資源使其無差距 2019/1/15

Quality of service Quality of service is the ability to provide different priority to user Delay Jitter Dropping probability Error In multihop wireless networks, defining the fairness objective must also address Contention neighborhoods Loss or Error rate Admission control  IEEE 802.11e Transmission Processing Propagation Queueing 基於以上的分析~我們已知QOS在WIRELESS MESH NETWORK已經是一個重要的議題，常見的QOS可分類為下面幾種，而在我未來研究想要著重於DELAY的部分，DELAY又可分(按動畫) (查書講詳細) 然而，IEEE 802.11 MAC 傳輸協定，並無法保證傳送即時性多媒體資料時，能和有線區域網路一樣擁有頻 寬大且穩定的傳輸品質，因此無線區域網路所提供的服務品質必須考量與周遭鄰近節點的干擾， 此外為維護一定品質的傳輸，不得讓超出規範的傳輸進入我們的網路。關於admission control : IEEE 802.11e QoS MAC 協定於2005 年 7 月正式通過，其傳送方式採用HCF (Hybrid Coordination Function)，其中提及到在HCCA (HCF Controlled Channel Access) 模式中有一簡單的允入 控制單元 (ACU，Admission Control Unit) 機制，此機制在CBR (Constant Bit Rate) 環境 中能夠有效的被運用 2019/1/15

motivation 在距離gateway不同hop數下，提供滿足所有客 戶方案 該方案付相同費用且享有相同品質的網路方案 聯繫到任一AP，享有相同頻寬 聯繫到任一AP，其end-to-end dropping probability相 等 聯繫到任一AP，傳送相同長度封包，其end-to-end delay相等 …. Throughput V.S. Delay 2019/1/15

outline Introduction Literature review Our problem 2019/1/15

literature review [1] “End-to-end performance and fairness in multihop wireless backhaul networks” MobiCom ’04 Throughput fairness Our objective is to study fairness and end-to-end performance in multihop wireless backhaul networks via the following methodology. First, we develop a formal reference model that characterizes objectives such as removing spatial bias and maximizing spatial reuse Second, we perform an extensive set of simulation experiments to quantify the impact of the key performance factors towards achieving these goals. Next, we develop and study a distributed layer 2 fairness algorithm which targets to achieve the fairness of the reference model Finally, we study the critical relationship between fairness and aggregate throughput and in particular study the fairness-constrained system capacity of multihop wireless backhaul networks. 2019/1/15

Multirate transmission UDP TCP Multirate transmission 2019/1/15

literature review [1] (cont.) Their algorithm: Measurement of offered load and capacity Message distribution Aggregate fair share computation Ingress rate limiting Inter-TAP Fairness Algorithm 2019/1/15

literature review [2] “Location-Dependent Throughput and Delay in Wireless Mesh Networks” The research** proposed an analytical model and two network design strategies for fair throughput and delay minimization. Network layer MAC layer GW **T. Liu and W. Liao, ”Location-Dependent Throughput and Delay in Wireless Mesh Networks,” Vehicular Technology 2019/1/15

literature review [2] (cont.) Successful channel access probability p(x) forwarding probability q(x) 外圈為內圈的若干倍 2019/1/15

literature review [2] (cont.) 2 strategy Per-user fair resource sharing Minimize end-to-end delay 2019/1/15

outline Introduction literature review Our problem 2019/1/15

Our objective Min-max fairness Subject to 嘗試在throughput 與delay間取得平衡 達到相同per OD pair throughput fairness下，最小化 最大end-to-end delay 差距 Subject to Max-min fair flow constrain Bandwidth constrain End-to-end delay constrain …… (Service Level Agreement) 2019/1/15

Transmission time (max-min fair) We would like to treat all sessions fairly when it is necessary to turn traffic away from the network. Session 2 Session 3 Session 1 傳統作法 resource allocation 我們想要最大化網路使用率(utilization)藉由對min session進行resource allocation 由上圖session 0穿越兩段link而session 1 2 3僅使用一段link 於是session 012共同分享前段LINK的頻寬，分別為1/3 。Session3則使用link2之剩餘頻寬 如果我們強制限制session3的頻寬為1/3那麼將會浪費link2 頻寬且對左半邊之其他session無帶來益處 反之，若將session3限制條的低一點，那麼session3將會對session 0作更嚴格的限制。 Session 0 2019/1/15

bottleneck 1 3 2 5 4 Session 4 (rate 1) Session 1 (rate 2/3) 以上圖為例 於是我們便可以延伸出bottleneck觀念: session在調整傳送速率時，最快遇到因受限於LINK頻寬而無法再向上調整的link時，便稱該LINK為這組SESSION之bottleneck。 以session 1為例，為何在link (1,3)不能以rate 1傳送，其因於該session在 link (3,5)僅能使用2/3 rate 然而link (3,5)並非session 5之bottleneck，其因於在link(2,3) 即有三個session共享頻寬 Session 1 2 3 4 5之bottleneck分別為(3,5) (2,3) (2,3) (4,5) (2,3) Session 5 (rate 1/3) Session 3 (rate 1/3) Session 2 (rate 1/3) The bottleneck of session 1 : ( 3,5 ) session 2 : ( 2,3 ) session 3 : ( 2,3 ) session 4 : ( 4,5 ) session 5 : ( 2,3 ) 2019/1/15

Max-min rate vectors algorithm Start with an all-zero rate vector and to increase the rates on all paths together until Fa = Ca for one or more links a. All sessions not using the saturated links are incremented equally in rate until one or more new links become saturated. Repeat 1. 2. until all sessions pass through at least one saturated link. 2019/1/15

2019/1/15

2019/1/15

2019/1/15

upstream Assumption Router 可控管其下所屬頻寬且可任意切割為 最小單位之集合 Contention-free environment 網路中拓樸及設備已固定(router，gateway， channel assignment) 使用single path routing processing delay、transmission delay、 propagation delay皆為定值 系統內節點以 M/M/1 queue表示 2019/1/15

Little’s result λ = average arrival rate = average sojourn time (time spent) in the system (service time + queueing time) = average number of customers in the system Little’s result or Little’s theorem is a very simple (but fundamental) relation between the arrival rate of customers, average number of customers in the system and the mean sojourn time of customers in the system. 2019/1/15

upstream Internet Gateway 1 2 3 a 4 c 5 b 6 第一層推throughput至個節點 得一初步基準值 ，各點得1/N = 1/10 粗體表示目前運算的LINK 6 Transient access point (TAP) Mobile client 2019/1/15

Internet Gateway 1 2 3 4 5 6 a b c 1. Throughput = 1/10 2. 目前的flow: γ , bandwidth C  delay = 1/(C-γ) = di C61+C62+C63=1 ; d6a = d6b = d6c 解C 6 a b c 2019/1/15

Internet Gateway 1 2 3 4 5 向上推一層 DELAY 6 a b c 2019/1/15

Internet Gateway 1 2 3 4 5 向上推一層 DELAY 6 a b c 2019/1/15

Internet Gateway 1 2 3 4 5 推最上層 DELAY 6 a b c 2019/1/15

downstream Assumption Gateway 擁有global information Router 可控管其下所屬頻寬且可任意切割為 最小單位之集合 Contention-free environment 網路中拓樸及設備已固定(router，gateway， channel assignment) 使用single path routing processing delay、transmission delay、 propagation delay皆為定值 系統內節點以 M/M/1 queue表示 2019/1/15

2019/1/15

2019/1/15

解C8,C9 2019/1/15

由上解得知 解C6,C7 2019/1/15

由上解得知 解C3,C4,C5 2019/1/15

由上解得知 解C1,C2 2019/1/15

Combined optimal routing and flow control Average number of packets in the system Penalty function Minimize Subject to for all w  W for all p  Pw , w W for all w W : the given value represent the desired input by OD pair w 2019/1/15

Penalty function aw: the optimal magnitude of input γw bw: the priority of OD pair w Input Rate γw 2019/1/15

Thanks for your listening !! 2019/1/15

2019/1/15

Gateway 1 2 3 4 5 6 a b c 2019/1/15

Our method Fairness index Bandwidth reallocation Admission control EX: Jain’s fairness index Bandwidth reallocation Admission control Leaky bucket Leaky bucket and token bucket 2019/1/15

Little’s result Average number of customers in the M/M/1 system Average system time 2019/1/15

3 2 1 Gateway 2019/1/15

M/M/1/B…. Dropping probability 2019/1/15

Probably solution Topology and Transmission power More bandwidth Carrier sense range Mac protocol Routing Scheduling schemes Bandwidth allocation Queueing model 2019/1/15

Processing + Propagation delay End-to-end delay n n-1 n-2 1 Gateway …… Transmission delay Processing + Propagation delay Queueing delay 2019/1/15

Queueing time Locally generated traffic Network layer MAC layer Traffic from other APS 2019/1/15

Our problem (N queue) Locally generated traffic Network layer MAC layer Traffic from other APS 2019/1/15

Our problem (N weighted queue) Locally generated traffic Network layer MAC layer Traffic from other APS 2019/1/15

internet Wired backhaul TAP1 TAP2 TAP3 TAP4 2019/1/15

literature review [2] (cont.) Conflict between locally generated traffic and forwarded traffic Network layer MAC layer GW 當我們得到傳輸的機會時 必須決定該傳送多少的local data 及relay data 調整其比例 才能達到fairness 2019/1/15

Introduction Our target is to achieve the end-to-end fairness of all clients with appropriate approach. Our problem…. QOS 使用者付費 2019/1/15