Fairness and Load Balancing

1FairnessandLoadBalancinginWirelessLANsUsingAssociationControlYigalBejerano,Seung-JaeHanandLi(Erran)LiBellLaboratories,LucentTechnologies600MountainAvenue,MurrayHill,NJ07974Abstract:RecentstudiesonoperationalwirelessLANs(WLANs)haveshownthatthetrafficloadisoftenunevenlydis-tributedamongtheaccesspoints(APs).Suchloadimbalanceresultsinunfairbandwidthallocationamongusers.Wearguethattheloadimbalanceandconsequentunfairbandwidthallo-cationcanbegreatlyalleviatedbyintelligentlyassociatinguserstoAPs,termedassociationcontrol,ratherthanhavingusersas-sociatewiththeAPsofstrongestsignalstrength.Inthispaper,wepresentanefficientalgorithmicsolutiontodeterminetheuser-APassociationsformax-minfairbandwidthallocation.Weprovidearigorousformulationoftheassocia-tioncontrolproblem,consideringbandwidthconstraintsofboththewirelessandbackhaullinks.Weshowthestrongcorrelationbetweenfairnessandloadbalancing,whichenablesustouseloadbalancingtechniquesforobtainingoptimalmax-minfairbandwidthallocation.AsthisproblemisNP-hard,wedevisealgorithmsthatachieveconstant-factorapproximation.Inpar-ticular,wepresenta2-approximationalgorithmforunweightedusersanda3-approximationalgorithmforweightedusers.Inouralgorithms,wefirstcomputeafractionalassociationsolu-tion,inwhichuserscanbeassociatedwithmultipleAPssimul-taneously.Thissolutionguaranteesthefairestbandwidthalloca-tionintermsofmax-minfairness.Then,byutilizingaroundingmethod,weobtaintheintegralsolutionfromthefractionalsolu-tion.Wealsoconsidertimefairnessandpresentapolynomial-timealgorithmforoptimalintegralsolution.Wefurtherextendourschemesfortheon-linecasewhereusersmayjoinandleavedynamically.Oursimulationsdemonstratethattheproposedalgorithmsachieveclosetooptimalloadbalancing(i.e.,max-minfairness)andtheyoutperformcommonly-usedheuristicap-proaches.Keywords:WirelessLocalAreaNetworks(WLAN),IEEE802.11,Max-MinFairness,LoadBalancing,ApproximationAl-gorithms.I.INTRODUCTIONInrecentyears,IEEE802.11wirelessLANs(WLANs)havebeenrapidlydeployedinenterprises,publicareasandhomes.Recentstudies[2],[3],[4]onoperationalWLANshaveshownthatthetrafficloadisoftendistributedunevenlyamongtheac-cesspoints(APs).InWLANs,bydefault,eachuserscansallavailablechannelstodetectitsnearbyAPsandassociateitselfwiththeAPthathasthestrongestreceivedsignalstrengthindi-cator(RSSI),whileignoringitsloadcondition.Asusersare,Partofthispaperwaspublishedin.typically,notuniformlydistributed,someAPstendtosufferfromheavyloadwhileadjacentAPsmaycarryonlylightloadorbeidle.SuchloadimbalanceamongAPsisundesirableasithampersthenetworkfromprovidingfairservicestoitsusers.Assuggestedininitialstudies[5],[6],[7]theloadimbalanceproblemcanbealleviatedbybalancingtheloadamongtheAPsviaintelligentlyselectingtheuser-APassociation,termedasso-ciationcontrol.Obviously,associationcontrolcanbeusedtoachievedifferentobjectives.Forinstance,itcanbeusedtomax-imizetheoverallsystemthroughputbyshiftinguserstoidleorlightlyloadedAPsandallowingeachAPtoserveonlytheuserswithmaximaldatarate.Clearly,thisobjectiveisnotadesiredsystembehaviorfromthefairnessviewpoint.Amoredesirablegoalistoprovidenetwork-widefairbandwidthallocation,whilemaximizingtheminimalfairshareofeachuser.Thistypeoffairnessisknownasmax-minfairness.Informally,abandwidthallocationismax-minfairifthereisnowaytogivemoreband-widthtoanyuserwithoutdecreasingtheallocationofauserwithlessorequalbandwidth.Inthispaper,wepresentefficientuser-APassociationcontrolalgorithmsthatensuremax-minfairbandwidthallocationandweshowthatthisgoalcanbeobtainedbybalancingtheloadontheAPs.A.RelatedWorkLoadbalancinginWLANshasbeenintenselystudiedbyboththeresearchcommunityandtheindustry.VariousWLANvendorshaveincorporatedproprietaryload-balancingfeaturesintheirnetworkdevicedrivers,APfirmwaresandWLANcards[8],[9].Intheseproprietarysolutions,theAPsbroad-casttheirloadconditionstotheusersviatheBeaconmessagesandeachuserchoosestheleastloadedAP.In[5],[6],[7],differ-entassociationcriteriathanRSSIareproposed.ThesemetricstypicallytakeintoaccountfactorssuchasthenumberofuserscurrentlyassociatedwithanAP,themeanRSSIofuserscur-rentlyassociatedwithanAP,theRSSIofthenewuserandthebandwidthanewusercangetifitisassociatedwithanAP.Forexample,Balachandranetal.[6]proposetoassociatenewuserswiththeAPthatcanprovideaminimalbandwidthrequiredbytheuser.IftherearemorethanonesuchAP,theonewiththestrongestsignalisselected.Mostoftheseheuristicsonlyde-terminetheassociationofnewlyarrivedusers,excepttheonein[7].TsaiandLien[7]proposetoreassociateuserswhensomeconditionsareviolated.Loadbalancinghasalsobeenstudiedincellularnetworks,bothTDMAandCDMAnetworks.Usually,itisachievedviadynamicchannelallocation(DCA)[10].Thesemethodsarenot2applicableinWLANsettingwhereeachAPnormallyusesonechannelandchannelallocationisfixed.Anotherapproachistousecelloverlappingtoreducethecallblockingprobabilityandmaximizethenetworkutilization.In[12],[13],anewlyar-riveduserisassociatedwiththecellwiththegreatestnumberofavailablechannels.In[14],LagrangeandJabbariaddressfair-nessissuesinthisapproachbyrestrictingthenumberofavail-ablechannelsforne