advertisement

2006-05-15-Lin-Infocom2006

75 %
25 %
advertisement
Information about 2006-05-15-Lin-Infocom2006
Travel-Nature

Published on December 23, 2008

Author: aSGuest7855

Source: authorstream.com

advertisement

Throughput Optimization and Fair Bandwidth Allocation in Multi-Hop Wireless Local Area Networks : Throughput Optimization and Fair Bandwidth Allocation in Multi-Hop Wireless Local Area Networks Qunfeng Dong (University of Wisconsin-Madison) Suman Banerjee (University of Wisconsin-Madison) Benyuan Liu (University of Massachusetts-Lowell) INFOCOM 2006 Slides by Ting-Yu Lin Slide 2: Outline Introduction The “Performance anomaly” of 802.11 WLANs (one-hop) Previously proposed one-hop/multi-hop solutions and limitations Our multi-hop solution Fairness in multi-hop WLANs Max-Min Throughput Fairness Max-Min Time Fairness Fair bandwidth allocation in multi-hop WLAN Construction and maintenance of an efficient tree Backward compatibility Evaluation Summary Slide 3: Background The “Performance anomaly” of 802.11 WLANs Channel rate diversity is prevalent in 802.11 WLANs [KNE03, TG04] 802.11 DCF implements Throughput-based Fairness Assigns approximately equal bandwidth to each client A low bit rate client brings down throughput of everyone [HRBD03] Rate of 8,9: 11 Mbps Rate of 5,6,7: 5.5 Mbps Rate of 1,2,3,4: 2 Mbps Total Throughput: 3.3 Mbps Slide 4: Background Solution 1: Time-based Fairness [TG04] Each client receives equal time share High bit rate clients are protected Aggregate throughput is increased However, throughput of low bit rate clients is decreased! Rate of 8,9: 11 Mbps Rate of 5,6,7: 5.5 Mbps Rate of 1,2,3,4: 2 Mbps Total Throughput: 5.2 Mbps Slide 5: Background Solution 2: Multi-AP Association Control [BHL04] In 802.11, clients are assigned to the AP with the strongest RSSI Often leads to unbalanced load distribution and idle channel Throughput and fairness can be improved by careful association Slide 6: Background Solution 2: Multi-AP Association Control [BHL04] In 802.11, clients are assigned to the AP with the strongest RSSI Often leads to unbalanced load distribution and idle channel Throughput and fairness can be improved by careful association Bandwidth of client 1: 1 Mbps Bandwidth of client 2: 1 Mbps Bandwidth of client 3: 1 Mbps Bandwidth of client 4: 1 Mbps Bandwidth of client 5: 1 Mbps A fair default association Slide 7: Background Solution 2: Multi-AP Association Control [BHL04] In 802.11, clients are assigned to the AP with the strongest RSSI Often leads to unbalanced load distribution and idle channel Throughput and fairness can be improved by careful association Bandwidth of client 1: 1 Mbps Bandwidth of client 2: 2 Mbps Bandwidth of client 3: 2 Mbps Bandwidth of client 4: 1 Mbps Bandwidth of client 5: 1 Mbps A max-min fair association Slide 8: Motivation & Challenges A common limitation of these previous techniques Only use AP-client links, which often have low bit rates. High rate P2P links between clients exist, but not utilized. Solution 3: Multi-Hop WLAN [LBB04] Forward traffic via high bit rate P2P links between clients Less channel access time is needed ? increased throughput Challenges: How to build an efficient multi-hop tree rooted at the AP? How to conduct fair bandwidth allocation in a multi-hop topology? Objective: Improve throughput without sacrificing fairness in multi-hop WLAN Our Results : Our Results Max-min throughput fair allocation in multi-hop WLANs No client can get more bandwidth without decreasing the bandwidth of clients with the same or less bandwidth Max-min time fair allocation in multi-hop WLANs No client can get more time share without decreasing the time share of clients with the same or less time share Multi-hop tree construction Iteratively search for a better tree topology such that fair bandwidth within the new tree leads to better client throughput Fairness : Fairness Max-min throughput fairness A feasible bandwidth allocation B is max-min throughput fair if No client can be allocated more bandwidth without decreasing the bandwidth of clients with the same or less bandwidth Max-min time fairness A feasible bandwidth allocation B is max-min time fair if For each node i in the multi-hop tree, assume the same amount of total bandwidth allocated to nodes in the sub-tree rooted at node i Neither node i nor any child of it can be assigned more time share of node i without decreasing the time share of some of them with equal or less time share of node i Gives more bandwidth to forwarding nodes and hence Encourages clients to serve as forwarding nodes Leads to more skewed bandwidth allocation but higher throughput Slide 11: Methodology Focus on the up-link direction, and solve the bandwidth allocation within a single-AP tree first Aggregate throughput= 44/5 More aggregate throughput= 55/6 Slide 12: Max-min throughput fairness (MMFA) A bandwidth allocation B is feasible if and only if it is feasible at every node i with i Pi Qi={j1, j2, j3} j1 j2 j3 Slide 13: Max-min throughput fairness (MMFA) General idea Fair bandwidth allocation within a multi-hop tree structure is recursively done in a bottom-up order During the bottom-up recursive process, at each node i, MMFA performs the “pump-and-drain” operation First “pump” the node, i.e., allocate to the node a bandwidth such that it is fully loaded or even overloaded Then “drain” the nodes in the sub-tree rooted at that node, i.e., decrease their allocated bandwidth such that the resulting bandwidth allocation is feasible and throughput fair within the sub-tree Slide 14: Detailed design Max-min throughput fairness (MMFA) Each node i maintains and reports to its parent the following info. Slide 15: Max-min throughput fairness (MMFA) Pump: Slide 16: Max-min throughput fairness (MMFA) Drain: Slide 17: Original case of max-min throughput fair allocation in a single-hop WLAN r8, r9: 11 Mbps r5, r6, r7: 5.5 Mbps r1, r2, r3, r4: 2 Mbps 2bi/11 + 3bi/5.5 + 4bi/2 = 1 4bi + 12bi + 44bi = 22 bi = 11/30 aggregate throughput = 99/30 = 3.3 Mbps Slide 18: Example of max-min throughput fair allocation using MMFA in a multi-hop WLAN (all links have a 11 Mbps data rate) At node 7: Pump b7=11 W7=11/11+2*(11/11)=3 > 1 Drain n4=|T4nN7[L7]|=1 d=(3-1)/(1/11+n4/11+n4/11)=22/3 b7=b4=11-22/3=11/3 At node 5: Pump b5=11 W5=11/11+4*(11/11)=5 > 1 Drain n1=|T1nN5[L5]|=1=n2 d=(5-1)/(1/11+2*(n1/11+n1/11))=44/5 b5=b1=b2=11-44/5=11/5 Slide 19: At node 9: Pump b9=11/3, B7=22/3 W9=1/3+B7/11+B7/11=5/3 > 1 Drain n7=|T7nN9[L9]|=2 d=(5/3-1)/(1/11+n7/11+n7/11)=22/15 b9=b7=b4=11/3-22/15=11/5 At node 8: Pump b8=11/3, B5=33/5, B6=22/3 W8=1/3+2*3/5+2*2/3=43/15 > 1 Drain n6=|T6nN8[L8]|=2 d=(43/15-1)/(1/11+n6/11+n6/11) =42*11/75 > L8[|L8|]- L8[|L8|-1] => b8=b6=b3=b5=b1=b2=11/5 Drain again W8=1/5+2(3/5+2/5)=11/5 > 1 d=(11/5-1)/(1/11+5/11+5/11)=6/5, so 11/5-6/5=1 Slide 20: Finally Drain at the AP: B8=6, B9=33/5 WAP=6/11+3/5=63/55 > 1, n9=3 d=(63/55-1)/(n9/11)=8/15 Thus b9=b7=b4=11/5-8/15=5/3 Aggregate throughput is maximized: 11Mbps Slide 21: Max-min time fairness t i Pi |Tj| = 3 j Slide 22: Max-min time-based fairness allocation (TBFA) General idea Fair bandwidth allocation within a multi-hop tree structure is recursively done in a bottom-up order During the bottom-up recursive process, at each node i, TBFA performs the “pump-and-drain” operation First “pump” the node, i.e., allocate to the node a bandwidth such that it is fully loaded or even overloaded Then “drain” the nodes in the sub-tree rooted at that node, i.e., decrease their allocated bandwidth such that the resulting bandwidth allocation is feasible and time fair within the sub-tree Slide 23: Pump: Max-min time-based fairness allocation (TBFA) Slide 24: Drain: Max-min time-based fairness allocation (TBFA) Slide 25: Original case of max-min time fair allocation in a single-hop WLAN r8, r9: 11 Mbps r5, r6, r7: 5.5 Mbps r1, r2, r3, r4: 2 Mbps time share at each node = 1/9 b8=b9=11*(1/9)=11/9 b5=b6=b7=5.5*(1/9)=11/18 b1=b2=b3=b4=2*(1/9)=2/9 aggregate throughput = 5.2 Mbps Slide 26: Example of max-min time fair allocation using TBFA in a multi-hop WLAN (all links have a 11 Mbps data rate) At node 7: subtree size |G7|=2 Time share T77=T74=1/2 Bp4=T74/(1/11+1/11)=11/4=b4 b7=11*1/2=11/2 At node 5: subtree size |G5|=3 Time share T55=T51=T52=1/3 Bp1=T51/(1/11+1/11)=11/6=b1 Bp2=Bp1=11/6=b2 b5=11*1/3=11/3 Slide 27: At node 9: Time share T99=1/3, T97=2/3 Bp7=T97/(1/11+1/11)=11/3 b9=11*1/3=11/3 B7=11/4+2/11=33/4 > Bp7 Drain node 7 subtree size |G4|=1 d=(33/4-11/3)/(11+|G4|/(1/11+1/11)) =5/18 Time share T77= T74=1/2-5/18=2/9 b7=11*2/9=22/9, b4=(11/2)*(2/9)=11/9 Slide 28: At node 8: Time share T88=1/6, T86=1/3, T85=1/2 Bp6=T86/(1/11+1/11)=11/6 < B6=33/4 Bp5=T85/(1/11+1/11)=11/4 < B5=22/3 b8=11*1/6=11/6 Drain node 6 |G3|=1 Time share T66=1/2, T63=1/2 d=(33/4-11/6)/(11+|G3|/(1/11+1/11)) =7/18 Time share T66= T63=1/2-7/18=1/9 b6=11*1/9=11/9, b3=(11/2)*(1/9)=11/18 Drain node 5 |G1|=|G2|=1 Time share T55=T51=T52=1/3 d=(22/3-11/4)/(11+2/(1/11+1/11)) =5/24 Time share T55=T51=T52=1/3-5/24=1/8 b5=11*1/8=11/8 b1=b2=(11/2)*(1/8)=11/16 Slide 29: Finally Drain at the AP: Time share TAP9=1/3, TAP8=2/3 Bp9=TAP9/(1/11)=11/3 < B9=22/3 Bp8=TAP8/(1/11)=22/3 > B8=77/12 TAP8=(77/12)/11=7/12 No Drain needed at node 8! TAP9=1-7/12=5/12 Bp9=11*(5/12)=55/12 < B9=22/3 Drain node 9 Time share T99=1/3, T97=2/3 with |G7|=2 d=(22/3-55/12)/(11+|G7|/(1/11+1/11))=1/8 Time share T99=1/3-1/8=5/24 b9=11*(5/24)=55/24 Time share T97=2/3-2*(1/8)=5/12 Bp7=T97/(1/11+1/11)=55/24 < B7=11/3 Drain node 7 (continued in next slide..) Slide 30: Aggregate throughput is maximized: 11Mbps Drain node 7 Time share T77=T74=2/9 with |G4|=1 d=(11/3-55/24)/(11+|G4|/(1/11+1/11))=1/12 Time share T77=T74=2/9-1/12=5/36 b7=11*5/36=55/36 b4=(11/2)*(5/36)=55/72 Tree Construction : Start with a default WLAN topology For example, a one-hop association based on RSSI Iteratively search for a better tree topology Such that fair bandwidth allocation within the new tree leads to a better client bandwidth vector Until no better tree can be found This iterative search can also be used to handle client arrival and client leave If a client arrives, quickly associate it with some AP For example, the AP with the strongest RSSI If a client leaves, quickly associate its children with some AP Then iteratively search for a better tree topology Tree Construction Slide 32: A good multi-hop tree structure Equal bandwidth share at each node: 11/9 And the aggregate throughput is also maximized: 11Mbps By migrating node 3 from node 6 to node 7! Original tree structure Backward Compatibility : Legacy client devices can work as usual Upon arrival, simply associate with the AP with the strongest RSSI Not necessary to participate in tree construction Allocated bandwidth changes as the tree topology evolves Upon leave, simply disconnect from the AP No children, no additional processing needed Incremental deployment is enabled and encouraged Investing to upgrade client device will lead to perceivable boost in performance, in spite of the existence of other legacy client devices Backward Compatibility Evaluation : Network settings 30 clients Scenario I: 150m×150m One AP at each corner Scenario II: 300m×300m One AP at each corner Scenario III: 150m×150m One AP at the center Scenario IV: 300m×300m One AP at the center Link rates 0m-50m 11 Mbps 50m-80m 5.5 Mbps 80m-120m 2 Mbps 120m-150m 1 Mbps 150m+ N/A Evaluation Evaluation : Evaluation Evaluation : Evaluation Evaluation : Evaluation Evaluation : Evaluation Evaluation : Evaluation Summary : Unpractical interference model assumed (Truth: even though nodes are not associated with each other, they still interfere!). The extension part to the case of multiple APs is weak (Trees need to be node-disjoint). This work fails to address how to construct a good multi-hop tree structure (only simple iterative heuristic is suggested), which should play a critical component in throughput optimization and fairness provisioning. Summary

Add a comment

Related presentations