Overheadmkxk.com

AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworksBrunoBaynat1,GeorgesNogueira1,MasoodMaqbool2,andMarceauCoupechoux21UniversitePierreetMarieCurie-Paris,France{firstname.
lastname}@lip6.
fr2TelecomParisTech-Paris,France{firstname.
lastname}@telecom-paristech.
frAbstract.
Thispapertacklesthechallengingtaskofdevelopingasim-pleandaccurateanalyticalmodelforperformanceevaluationofWiMAXnetworks.
Theneedforaccurateandfast-computingtoolsisofprimaryimportancetofacecomplexandexhaustivedimensioningissuesforthispromisingaccesstechnology.
Inthispaper,wepresentagenericMarko-vianmodeldevelopedforthreeusualschedulingpolicies(slotsharingfairness,throughputfairnessandopportunisticscheduling)thatprovidesclosed-formexpressionsforalltherequiredperformanceparametersataclickspeed.
Thismodeliscomparedindepthwithrealisticsimulationsthatshowitsaccuracyandrobustnessregardingthedierentmodelingassumptions.
Finally,thespeedofouranalyticaltoolallowsustocarryondimensioningstudiesthatrequireseveralthousandsofevaluations,whichwouldnotbetractablewithanysimulationtool.
Keywords:WiMAX,performanceevaluation,dimensioning,analyticalmodels.
1IntroductionTheevolutionoflast-mileinfrastructureforwiredbroadbandnetworksfacesacuteimplicationssuchasdicultterrainandhighcost-to-serveratio.
Latestdevelopmentsinwirelessdomaincouldnotonlyaddresstheseissuesbutcouldalsocomplementtheexistingframework.
Oneofsuchhighlyanticipatedtech-nologiesisWiMAX(WorldwideInteroperabilityforMicrowaveAccess)basedonIEEEstandard802.
16.
TherstoperativeversionofIEEE802.
16is802.
16-2004(xed/nomadicWiMAX)[1].
ItwasfollowedbyaraticationofmobileWiMAXamendmentIEEE802.
16ein2005[2].
Ontheotherhand,thecon-sortiumWiMAXForumwasfoundtospecifyproles(technologyoptionsarechosenamongthoseproposedbytheIEEEstandard),deneanend-to-endar-chitecture(IEEEdoesnotgobeyondphysicalandMAClayer),andcertifyproducts(throughinter-operabilitytests).
SomeWiMAXnetworksarealreadydeployedbutmostoperatorsarestillundertrialphases.
Asdeploymentiscoming,theneedarisesformanufacturersL.
Frattaetal.
(Eds.
):NETWORKING2009,LNCS5550,pp.
521–534,2009.
cIFIPInternationalFederationforInformationProcessing2009522B.
Baynatetal.
andoperatorstohavefastandecienttoolsfornetworkdesignandperfor-manceevaluation.
In[3]authorsproposeananalyticalmodelforstudyingtherandomaccessschemeofIEEE802.
16d.
NiyatoandHossain[4]formulatethebandwidthallocationofmultipleserviceswithdierentQoSrequirementsbyusinglinearprogramming.
Theyalsoproposeperformanceanalysis,rstatcon-nectionlevel,andthen,atpacketlevel.
Intheformercase,variationsoftheradiochannelarehowevernottakenintoaccount.
Inthelattercase,thecom-putationofperformancemeasuresrelyonmulti-dimensionalMarkovianmodelthatrequiresnumericalresolutions.
NotspecictoWiMAXsystems,genericanalyticalmodelsforperformanceevaluationofcellularnetworkswithvaryingchannelconditionshavebeenproposedin[5,6,7].
Themodelspresentedinthesearticlesaremostlybasedonmulti-classprocessor-sharingqueueswitheachclasscorrespondingtousershavingsimilarradioconditionsandsubsequentlyequaldatarates.
Thevariabilityofradiochannelconditionsatowlevelistakenintoaccountbyintegratingpropagationmodels,mobilitymodelsorspatialdistribu-tionofusersinacell.
InordertouseclassicalPS-queuesresults,thesepapersconsiderimplicitlythatuserscanonlyswitchclassbetweentwosuccessivedatatransfers.
However,ashighlightedinthenextsection,inWiMAXsystems,radioconditionsandthusdataratesofaparticularusercanchangefrequentlyduringadatatransfer.
Inaddition,capacityofaWiMAXcellmayvaryasaresultofvaryingradioconditionsofusers.
Asaconsequence,anyPS,DPS(discrimina-toryPS)orevenGPS(generalizedPS)queueisnotappropriateformodelingthesechannelvariations.
Inthispaper,wedevelopanovelandgenericanalyticalmodelthattakesintoaccountframestructure,preciseslotsharing-basedschedulingandchannelqualityvariationofWiMAXsystems.
Unlikeexistingmodels[5,6,7],ourmodelisadaptedtoWiMAXsystems'assumptionsandisgenericenoughtointegrateanyappropriateschedulingpolicy.
Here,weconsiderthreeclassicalpolicies:slotsharingfairness,instantaneousthroughputfairness,andopportunistic.
Foreachofthem,wedevelopclosed-formexpressionsforallperformancemetrics.
More-over,ourapproachmakesitpossibletotakeintoaccounttheso-called"outage"situation.
Auserexperiencesanoutage,ifatagiventimeradioconditionsaresobadthatitcannottransferanydataandisthusnotscheduled.
Onceagain,classicalPS-likequeuesarenotappropriatetomodelthisfeature.
Thepaperisorganizedasfollows.
ModelingassumptionsarepresentedinSection2.
Section3presentsthegenericanalyticalmodelanditsadaptiontothethreeconsideredschedulingpolicies.
ValidationandrobustnessarediscussedinSection4.
Section5nallygivesanexampleofWiMAXdimensioningprocess.
2ModelingAssumptionsThedevelopmentofouranalyticalmodelisbasedonseveralassumptionsrelatedtothesystem,thechannel,thetracandtheschedulingalgorithm.
Wepresentheretheseassumptions.
AllofthemwillbediscussedinSection3.
4,and,aswillbedevelopedinthatsection,mostofthemcanberelaxed,ifnecessary,AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks523byslightlymodifyingthemodel.
Whereverrequired,relateddetailsofWiMAXsystemarespecied.
Variousnotationsarealsointroducedinthissection.
AWiMAXtimedivisionduplex(TDD)framecomprisesofslotsthatarethesmallestunitofresourceandwhichoccupiesspacebothintimeandfrequencydomain.
Apartoftheframeisusedforoverhead(e.
g.
,DLMAPandULMAP)andtherestforuserdata.
ThedurationTFofthisTDDframeisequalto5ms[2].
Systemassumptions.
WeconsiderasingleWiMAXcellandfocusonthedownlinkpartwhichisacriticalportionofasymmetricdatatrac.
1.
OverheadintheTDDframeisassumedtobeconstantandindependentofthenumberofconcurrentactivemobilestation(MS).
Asaconsequence,thetotalnumberofslotsavailablefordatatransmissioninthedownlinkpartisconstantandwillbedenotedbyNS.
2.
WeassumethatthenumberofMSthatcansimultaneouslybeinactivetransferisnotlimited.
Asaconsequence,anyconnectiondemandwillbeacceptedandnoblockingcanoccur.
OneoftheimportantfeaturesofIEEE802.
16eislinkadaptation:dier-entmodulationandcodingschemes(MCS)allowsadynamicadaptationofthetransmissiontotheradioconditions.
Asthenumberofdatasubcarriersperslotisthesameforallpermutationschemes,thenumberofbitscarriedbyaslotforagivenMCSisconstant.
TheselectionofappropriateMCSiscarriedoutaccordingtothevalueofsignaltointerferenceplusnoiseratio(SINR).
Incaseofoutage,i.
e.
,iftheSINRistoolow,nodatacanbetransmittedwithouterror.
Wedenotetheradiochannelstatesas:MCSk,1≤k≤K,whereKisthenumberofMCS.
Byextension,MCS0representstheoutagestate.
ThenumberofbitstransmittedperslotbyaMSusingMCSkisdenotedbymk.
Fortheparticularcaseofoutage,m0=0.
Channelassumption.
TheMCSusedbyagivenMScanchangeveryoftenbecauseofthehighvariabilityoftheradiolinkquality.
3.
WeassumethateachMSsendsafeedbackchannelestimationonaframebyframebasis,andthus,thebasestation(BS)canchangeitsMCSeveryframe.
SincewedonotmakeanydistinctionbetweenusersandconsiderallMSasstatisticallyidentical,weassociateaprobabilitypkwitheachcodingschemeMCSk,andassumethat,ateachtime-stepTF,anyMShasaprobabilitypktouseMCSk.
Tracassumptions.
Thetracmodelisbasedonthefollowingassumptions.
4.
Allusershavethesametraccharacteristics.
Inaddition,wedon'tconsideranyQoSdierentiationhere.
5.
WeassumethatthereisaxednumberNofMSthataresharingtheavailablebandwidthofthecell.
524B.
Baynatetal.
6.
EachoftheNMSisassumedtogenerateaninnitelengthON/OFFelastictrac.
AnONperiodcorrespondstothedownloadofanelement(e.
g.
,awebpageincludingallembeddedobjects).
Thedownloadingdurationde-pendsonthesystemloadandtheradiolinkquality,soONperiodsmustbecharacterizedbytheirsize.
AnOFFperiodcorrespondstothereadingtimeofthelastdownloadedelement,andisindependentofthesystemload.
AsopposedtoON,OFFperiodsmustthenbecharacterizedbytheirduration.
7.
WeassumethatbothONsizesandOFFdurationsareexponentiallydis-tributed.
WedenotebyxontheaveragesizeofONdatavolumes(inbits)andbytofftheaveragedurationofOFFperiods(inseconds).
Schedulingassumption.
Theschedulingalgorithmisresponsibleforallo-catingradioresourcestousers.
Inwirelessnetworks,schedulingmaytakeintoaccounttheirradiolinkquality.
Inthispaper,wehaveconsideredthreetradi-tionalschemes.
Theslotfairnessschedulingallocatesthesamenumberofslotstoallactiveusers.
Thethroughputfairnessschedulingensuresthatallactiveusershavethesameinstantaneousthroughput.
Theopportunisticschedulinggivesallresourcestoactiveuserswiththebestchannel.
8.
Atanytimeandforallschedulingpolicies,ifthereisonlyoneactiveuser,weassumethattheschedulercanallocatealltheavailableslotsforitstransfer.
3WiMAXAnalyticalModel3.
1MarkovianModelArstattemptformodelingthissystemwouldbetodevelopamulti-dimensionalContinuousTimeMarkovChain(CTMC).
Astate(n0,.
.
.
,nK)ofthischainwouldbeaprecisedescriptionofthecurrentnumbernkofMSusingcodingschemeMCSk,0≤k≤K(includingoutage).
Thederivationofthetransitionsofsuchamodelisaneasytask.
HoweverthecomplexityoftheresolutionofthismodelmakesitintractableforanyrealisticvalueofK.
Inordertoworkaroundthecomplexityproblem,weaggregatethestatedescriptionofthesystemintoasingledimensionn,representingthetotalnumberofconcurrentactiveMS,regardlessoftheMCStheyuse.
TheresultingCTMCisthusmadeofN+1statesasshowninFig1.
–Atransitionoutofagenericstatentoastaten+1occurswhenaMSinOFFperiodstartsitstransfer.
This"arrival"transitioncorrespondstooneMSamongthe(Nn)inOFFperiod,endingitsreading,andisperformedwitharate(Nn)λ,whereλisdenedastheinverseoftheaveragereadingtime:λ=1toff.
–Atransitionoutofagenericstatentoastaten1occurswhenaMSinONperiodcompletesitstransfer.
This"departure"transitionisperformedwithagenericrateμ(n)correspondingtothetotaldeparturerateoftheframewhennMSareactive.
AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks525Fig.
1.
GeneralCTMCwithstate-dependentdepartureratesObviously,themaindicultyofthemodelresidesinestimatingtheaggregatedepartureratesμ(n).
Inordertodoso,werstexpressμ(n)asfollows:μ(n)=m(n)NSxonTF,(1)wherem(n)istheaveragenumberofbitsperslotwhentherearenconcurrentactivetransfers.
Obviously,m(n)dependsonK,thenumberofMCS,andpk,0≤k≤K,theMCSvectorprobability.
Italsostronglydependsonn,becausethenumberofbitsperslotmustbeestimatedbyconsideringallpossibledistri-butionsofthenMSbetweentheK+1possibleMCS(includingoutage).
Itisworthwhilenotingthattheparametersm(n)nallydependontheschedulingpolicy,asitdenes,ateachtime-step,thequantityofslotsgiventoeachofthenMSwithrespecttotheMCStheyuse.
Inordertoprovideagenericexpressionofm(n),wedenexk(j0,.
.
.
,jK)theproportionoftheresource(i.
e.
,oftheNSslots)thatisassociatedtoaMSusingMCSk,whenthecurrentdistributionofthenMSamongtheK+1codingschemesis(j0,.
.
.
,jK).
Theaveragenumberofbitsperslot,m(n),whentherearenactiveusers,canthenbeexpressedasfollows:m(n)=(n,.
.
.
,n)(j0,.
.
.
,jK)=(0,.
.
.
,0)|j0+.
.
.
+jK=nj0=nKk=1mkjkxk(j0,.
.
.
,jK)nj1,.
.
.
,jKKk=0pjkk,(2)whereKk=0pjkkistheprobabilityofanydistributionofthenMSsuchthatthenumberofMSusingMSCkisjk,andnj0,.
.
.
,jKisthemultinomialcoecientthattakesintoaccountallsuchpossiblesdistributions.
3.
2SchedulingPolicyModelingWenowpresenttheadaptationofthemodel,forthethreespecicschedulingpoliciesweconsiderinthispaper.
Foreachofthemweprovideclosed-formexpressionsfortheaveragenumberofbitsperslots,m(n).
Slotsharingfairness.
Eachtime-step,theschedulerequallysharestheNSslotsamongtheactiveusersthatarenotinoutage.
If,atagiventime-step,therearenactiveMS,eachoftheMSthatarenotinoutagereceivesaportionNSnj0ofthewholeresource.
Asaconsequence,theproportionoftheresourcethat526B.
Baynatetal.
isassociatedtoaMSusingMCSk,isthusgivenby:xk(j0,.
.
.
,jK)=1nj0foranyk=0.
Byreplacingtheseproportionsingenericexpression(2)weobtain:m(n)=(n,.
.
.
,n)(j0,.
.
.
,jK)=(0,.
.
.
,0)|j0+.
.
.
+jK=nj0=nn!
nj0Kk=1mkjkKk=0pjkkjk!
.
(3)Instantaneousthroughputfairness.
Theresourceissharedinordertopro-videthesameinstantaneousthroughputtoallactiveusersthatarenotinoutage.
ThispolicyallowsMSusingMCSwithalowbitrateperslottoobtain,atagiventime-step,proportionallymoreslotscomparedtoMSusingaMCSwithahighbitrateperslot.
Inordertorespectinstantaneousthroughputfairnessbetweenallactiveusersthatarenotinoutage,thexk(j0,.
.
.
,jK)mustbesuchthat:mkxk(j0,.
.
.
,jK)=Cforanyk=0,whereCisaconstantsuchthatKk=1jkxk(j0,.
.
.
,jK)=1.
Byreplacingtheproportionsxk(j0,.
.
.
,jK)ingenericexpression(2),theaveragenumberofbitsperslotm(n)becomes:m(n)=(n,.
.
.
,n)(j0,.
.
.
,jK)=(0,.
.
.
,0)|j0+.
.
.
+jK=nj0=n(nj0)n!
Kk=0pjkkjk!
Kk=1jkmk.
(4)Opportunisticscheduling.
Alltheresourceisgiventousershavingthehigh-esttransmissionbitrate,i.
e.
,thebetterradioconditionsandthenthebetterMCS.
Withoutlossofgenerality,weassumeherethattheMCSareclassiedinincreasingorder:m0i).
Asamatteroffact,αi(n)correspondstotheprobabilitythattheschedulergivesatagiventime-stepalltheresourcetoMSthatuseMCSi.
Asaconsequence,wecanexpresstheaveragenumberofbitsperslotwhentherearenactiveusersas:m(n)=Ki=1αi(n)mi.
(5)Inordertocalculatetheαi(n),werstexpresstheprobabilitythattherearenoMSusingaMCShigherthanMCSias:p≤i(n)=1Kj=i+1pjn.
Then,wecalculatetheprobabilitythatthereisatleastoneMSusingMCSiconditionedbythefactthattherearenoMSusingabetterMCS:p=i(n)=11piij=0pjn.
αi(n)canthusbeexpressedas:αi(n)=p=i(n)p≤i(n).
AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks5273.
3PerformanceParametersThesteady-stateprobabilitiesπ(n)caneasilybederivedfromthebirth-and-deathstructureoftheMarkovchain(depictedinFig.
1):π(n)=N!
(Nn)!
TnFρnNnSni=1m(i)π(0),(6)whereρisgivenbyrelation(7)andplaysaroleequivalenttothe"tracinten-sity"ofErlanglaws[8],andπ(0)isobtainedbynormalization.
ρ=xontoff(7)Theperformanceparametersofthissystemcanbederivedfromthesteady-stateprobabilitiesasfollows.
TheaverageutilizationUoftheTDDframeis:U=Nn=1(1pn0)π(n).
(8)TheaveragenumberofactiveusersQisexpressedas:Q=Nn=1nπ(n).
(9)ThemeannumberofdeparturesD(MScompletingtheirtransfer)byunitoftime,isobtainedas:D=Nn=1π(n)μ(n).
FromLittle'slaw,wecanderivetheaveragedurationtonofanONperiod(durationofanactivetransfer):ton=QD.
WenallycomputetheaveragethroughputXobtainedbyeachMSinactivetransferas:X=xonton.
(10)3.
4DiscussionoftheModelingAssumptionsOurMarkovianmodelisbasedonseveralassumptionspresentedinSection2.
Wenowdiscusstheseassumptionsonebyone(itemnumbersarerelatedtothecorrespondingassumptions),evaluatetheiraccuracy,andprovide,ifnecessaryandpossible,extensionsandgeneralizationpropositions.
1.
DLMAPandULMAParelocatedinthedownlinkpartoftheTDDframe.
TheycontaintheinformationelementsthatallowMStoidentifytheslotstobeused.
ThesizeoftheseMAPs,andasaconsequencethenumberNSofavailableslotsfordownlinkdatatransmissions,dependsonthenumberofMSscheduledintheTDDframe.
Inordertorelaxassumption1,wecanexpressthenumberofdataslots,NS(n),asafunctionofn,thenumberofactiveusers.
ThisdependencycanbeeasilyintegratedinthemodelbyreplacingNSbyni=1NS(n)inrelation(6),andNSbyNS(n)inrelation(1).
528B.
Baynatetal.
2.
AlimitnmaxonthetotalnumberofMSthatcansimultaneouslybeinactivetransfer,canbeintroducedeasilyifrequired.
ThecorrespondingMarkovchain(Fig.
1)hasjusttobetruncatedtothislimitingstate(i.
e.
,thelaststatebecomesmin(nmax,N)).
Asaresult,ablockingcanoccurwhenanewtransferdemandarrivesandthelimitisreached.
TheblockingprobabilitycanbederivedeasilyfromtheMarkovchain[9].
3.
Radiochannelmaybehighlyvariableormayvarywithsomememory.
OuranalyticalmodelonlydependsuponstationaryprobabilitiesofdierentMCSwhateverbetheradiochanneldynamics.
ThisapproachisauthenticatedthroughsimulationsinSection4.
4.
Morecomplexsystemswithmultiple-tracordierentiationbetweenuserswouldnaturallyresultintomorecomplexmodels.
Thisisleftforfuturework.
5.
Poissonprocessesarecurrentlyusedinthecaseofalargepopulationofusers,assumingindependencebetweenthearrivalsandthecurrentpopulationofthesystem.
Aswefocusinthispaperontheperformanceofasinglecellsystem,thepotentialpopulationofusersisrelativelysmall.
Thehigherthenumberofon-goingdataconnections,thelesslikelythearrivalofnewones.
Poissonprocessesarethusanon-relevantchoiceforourmodels.
NotehoweverthatifPoissonassumptionshavetobemadeforconnectiondemandarrivals,onecandirectlymodifythearrivalratesoftheMarkovchain(i.
e.
,replacethestate-dependentrates(Nn)λbysomeconstantvalue,andlimitthenumberofstatesoftheMarkovchainasexplainedaboveinpoint2).
6.
EachMSissupposedtogenerateinnitelengthON/OFFsessiontrac.
In[10],anextensiontonitelengthsessionsisproposedinthecontextof(E)GPRSnetworks,whereeachMSgeneratesON/OFFtracduringasessionanddoesnotgenerateanytracduringaninter-session.
ThisworkshowsthataverysimpletransformationoftraccharacteristicsthatincreasesOFFperiodsbyaportionoftheinter-sessionperiod,enablestoderivetheaverageperformancefromtheinnitelengthsessionmodel.
Theaccuracyofthistransformationisrelatedtotheinsensibilityoftheaverageperformanceparameterswithregardstothetracdistributions(seenextpoint).
AsimilartransformationcanbeappliedtoourWiMAXtracmodel.
7.
MemorylesstracdistributionsarestrongassumptionsthatarevalidatedbyseveraltheoreticalresultsonPS-likequeues.
SeveralworksoninsensitivityhaveshownthattheaverageperformanceparametersareinsensitivetothedistributionofONandOFFperiods[11,12,13].
Initsgenericform,ourmodelisnolongerequivalenttoanyPS-likequeue,butweshowinSection4bycomparingourmodeltoextensivesimulations(usingParetodistributions),thatinsensibilitystillholdsorisatleastaverygoodapproximation.
8.
Insomecellularnetworks(e.
g.
(E)GPRS),MShavelimitedtransmissioncapabilitiesbecauseofhardwareconsiderations.
ThisconstraintdenesamaximumthroughputthenetworkinterfacecanreachoramaximumnumberofresourceunitsthatcanbeusedbytheMS.
Thischaracteristichasbeenintroducedinthecaseof(E)GPRSnetworks[9]andconsistsinreducingthedepartureratesoftherststatesoftheMarkovchain.
ThesameideacanbeappliedtoourWiMAXmodel.
AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks5294ValidationInthissectionwediscussthevalidationandrobustnessofouranalyticalmodelthroughextensivesimulations.
Forthispurpose,asimulatorhasbeendevelopedthatimplementsanON/OFFtracgeneratorandawirelesschannelforeachuser,andacentralizedschedulerthatallocatesradioresources,i.
e.
,slots,toactiveusersonaframebyframebasis.
4.
1SimulationModelsSystemParameters.
Systembandwidthisassumedtobe10MHz.
Thedown-link/uplinkratiooftheWiMAXTDDframeisconsideredtobe2/3.
Weassumeforthesakeofsimplicitythattheprotocoloverheadisofxedlength(2sym-bols).
ConsideringsubcarrierpermutationPUSC,thetotalnumberofdataslots(excludingoverhead)perTDDdownlinksub-frameisNS=450.
TracParameters.
Inouranalyticalmodel,weconsideranelasticON/OFFtrac.
MeanvaluesofONdatavolume(mainpageandembeddedobjects)andOFFperiod(readingtime),are3Mbitsand3srespectively.
Intherstphase(validationstudy),weassumethattheONdatavolumeisexponentiallydistributedasitisthecaseintheanalyticalmodelassumptions.
AlthoughwelladaptedtoMarkovtheorybasedanalysis,exponentiallawdoesnotalwaysttherealityfordatatrac.
ThisisthereasonwhyweconsidertruncatedParetodistributionsinthesecondphase(therobustnessstudy).
Re-callthatthemeanvalueofthetruncatedParetodistributionisgivenbyequationxon=αbα11(b/q)α1,whereαistheshapeparameter,bistheminimumvalueofParetovariableandqisthecutovaluefortruncatedParetodistribu-tion.
Twovaluesofqareconsidered:lowerandhigher.
Themeanvalueinbothcases(q=300Mbitsandb=611822bitsforthehighercutoandq=3000Mbitsandb=712926bitslowercuto)is3Mbitsforthesakeofcomparisonwiththeexponentialmodel.
Thevalueofα=1.
2hasbeenadoptedfrom[14].
ChannelModels.
AgenericmethodfordescribingthechannelbetweentheBSandaMSistomodelthetransitionsbetweenMCSbyanitestateMarkovchain(FSMC).
ThechainisdiscretetimeandtransitionsoccurseveryLframes,withLTFInourcase,andforthesakeofsimplicity,L=1.
SuchaFSMCisfullycharacterizedbyitstransitionmatrixPT=(pij)0≤i,j≤K,wherestate0representsoutage.
StationaryprobabilitiespkprovidethelongtermprobabilitiesforaMStoreceivedatawithMCSk.
Inouranalyticalstudy,channelmodelisassumedtobememoryless,i.
e.
,MCSareindependentlydrawnfromframetoframeforeachuser,andthediscretedistributionisgivenbythe(pi)0≤i,j≤K.
Thiscorrespondstothecasewherepij=pjforalli.
Thissimpleapproach,referredasthememorylesschannelmodel,istheoneconsideredinthevalidationstudy.
LetPT(0)bethetransitionmatrixassociatedtothememorylessmodel.
530B.
Baynatetal.
Table1.
StationaryprobabilitiesChannelmodelMemorylessAverageCombinedgoodbad50%MS50%MSa00.
50.
50.
5p00.
2250.
2250.
0200.
430p10.
1100.
1100.
0400.
180p20.
0700.
0700.
0500.
090p30.
1250.
1250.
1400.
110p40.
4700.
4700.
7500.
190Table2.
ChannelparametersChannelMCSBitsperstateandslot{0,.
.
.
,K}outagemk0Outagem0=01QPSK-1/2m1=482QPSK-3/4m2=72316QAM-1/2m3=96416QAM-3/4m4=144Intherobustnessstudy,weintroducetwoadditionalchannelmodelswithmemory.
Inthesemodels,theMCSobservedforagivenMSinaframedependsontheMCSobservedinthepreviousframeaccordingtotheFSMCpresentedabove.
ThetransitionmatrixisderivedfromequationPT(a)=aI+(1a)PT(0)giventhat0≤a≤1.
Inthisequation,Iistheidentitymatrixandparameteraisameasureofthechannelmemory.
AMSmaintainsitsMCSforacertaindurationwithmeantcoh=1/(1a).
Witha=0,thetransitionprocessbe-comesmemoryless.
Ontheotherextreme,witha=1,thetransitionprocesswillhaveinnitememoryandMSwillneverchangeitsMCS.
Forsimulationswehavetakenaequalto0.
5,sothatthechannelisconstantinaverage2frames.
Thisvalueisconsistentwiththecoherencetimegivenin[15]for45Km/hat2.
5GHz.
WecallthecasewhereallMShavethesamechannelmodelwithmemory(a=0.
5),theaveragechannelmodel.
Notethatthestationaryproba-bilitiesoftheaveragechannelmodelarethesameasthoseofthememorylessmodel.
AsthechanneldependsontheBS-MSlink,itispossibletorenethepreviousapproachbyconsideringpartoftheMStobeina"bad"state,andtherestina"good"state.
Badandgoodstatesarecharacterizedbydierentstationaryprobabilitiesbuthavethesamecoherencetime.
Inthesocalledcombinedchannelmodel,halfoftheMSareinagoodstate,therestinabadstate,andaiskeptto0.
5forbothpopulations.
Threemodelsarethusconsidered:thememoryless,theaverage,andthecom-binedchannelmodels.
WirelesschannelparametersaresummarizedinTab.
2.
ConsideredMCSaregivenincludingoutage,andforeachofthem,thenum-berofbitstransmittedperslot.
ChannelstationaryprobabilitiesaregiveninTab.
1.
Theprobabilitiesforthecombinedmodelareobtainedbyaveragingcorrespondingvaluesofgoodandbadmodelstationaryprobabilities.
4.
2SimulationResultsInthissection,werstpresentacomparisonbetweentheresultsobtainedthroughouranalyticalmodelandschedulingsimulator.
TheoutputparametersinconsiderationareU,X,andπ(n)(seeSection3.
3).
AnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks531Fig.
2.
Validationforthethreeschedulingpolicieswithxon=3Mbitsandtoff=3sFig.
3.
AveragethroughputperuserfordierentloadsFig.
4.
AveragethroughputperuserfordierenttracdistributionsFig.
5.
Averagethroughputperuserfordierentchan-nelmodelsValidationStudy.
Inthisstudy,simulationstakeintoaccountthesametracandchannelassumptionsasthoseoftheanalyticalmodel.
However,insimulatorMCSofusersaredeterminedonperframebasisandschedulingiscarriedoutinrealtime,basedonMCSatthatinstant.
Theanalyticalmodelontheotherhand,considersstationaryprobabilitiesofMCSonly.
Fig.
2(a,b)showrespectivelytheaveragechannelutilization(U)andtheaverageinstantaneousthroughputperuser(X)forthethreeschedulingschemes.
Itisclearthatsimulationandanalyticalresultsshowagoodagreement:forbothutilizationandthroughput,themaximumrelativeerrorstaysbelow6%andtheaveragerelativeerrorislessthan1%.
Fig.
2(c)furtherprovesthatouranalyticalmodelisaverygooddescriptionofthesystem:stationaryprobabilitiesπ(n)arecomparedwiththoseofsimulationsforagiventotalnumberN=50ofMS.
Againresultsshowaperfectmatchbetweentwomethodswithanaveragerelativeerrorbelow9%.
Attheend,Fig.
3showsthevalidationforthreedierentloads(1,3and5Mbps).
Ourmodelshowsacomparableaccuracyforallthreeloadconditionswithamaximumrelativeerrorofabout5%.
RobustnessStudy.
InordertochecktherobustnessofouranalyticalmodeltowardsdistributionofONdatavolumes,simulationsarecarriedoutforex-ponentialandtruncatedpareto(withlowerandhighercuto).
TheresultsforthisanalysisareshowninFig.
4.
Theaveragerelativeerrorbetweenanalytical532B.
Baynatetal.
resultsandsimulationsstaysbelow10%forallsets.
ItisclearthatconsideringatruncatedParetodistributionhaslittleinuenceonthedesignparameters.
Nextweevaluatetherobustnessofouranalyticalmodelwithrespecttothechannelmodel.
Wecomparetheanalyticalresultswithsimulationforthethreepre-citedchannelmodels:memoryless,averageandcombined(withstationaryprobabilitiesgiveninTab.
1).
IfwelookattheplotofFig.
5,wecansaythatevenforacomplexwirelesschannel,ouranalyticalmodelshowsconsiderablerobustnesswithanaveragerelativeerrorbelow7%.
WecanthusdeducethatfordesigningaWiMAXnetwork,channelinformationisalmostcompletelyincludedinthestationaryprobabilitiesoftheMCS.
5NetworkDesignInthissectionweprovidesomeexamplestodemonstrateapplicationofourmodelwhileconsideringthroughputfairnessscheduling.
However,resultscanbeobtainedinthesamemannerforotherschedulingschemesbyusingtheirrespectiveaveragebitsperslotm(n).
5.
1PerformanceGraphsWerstdraw3-dimensionalsurfaceswhereperformanceparametersarefunctionof,e.
g.
,N,thenumberofusersinthecellandρ,thecombinationoftracparameters.
Foreachperformanceparameter,thesurfaceiscutoutintolevellinesandtheresulting2-dimensionalprojectionsaredrawn.
Thestepbetweenlevellinescanbearbitrarilychosen.
TheaverageradioresourceutilizationoftheWiMAXcellU,andtheaver-agethroughputperuserXforanyMSinthesystemarepresentedinFig.
6and7(correspondingtotheradiolinkcharacteristicspresentedinSection4).
Thesegraphsallowtodirectlyderiveanyperformanceparameterknowingthetracloadprole,i.
e.
,thecouple(N,ρ).
Eachgraphistheresultofseveralthousandsofinputparametersets.
Obviously,anysimulationtoolorevenanymulti-dimensionalMarkovchainrequiringnumericalresolution,wouldhavepre-cludedthedrawingofsuchgraphs.
5.
2DimensioningStudyInthissection,weshowhowourmodelcanbeadvantageouslyusedfordimen-sioningissues.
Twoexamples,eachrespectingacertainQoScriterion,aregiven.
InFig.
8wendminimumnumberNofMSinthecelltoguaranteethattheaverageradioutilizationisover50%.
Thiskindofcriterionallowsoperatorstomaximizetheutilizationofnetworkresourceincomparisonwiththetracloadoftheircustomers.
Foragiventracloadproleandagivensetofsystemparameters,thepointofcoordinates(NS,ρ)inthegraphislocatedbetweentwolevellines,andthelevellinewiththehighervaluegivestheoptimalvalueofN.
TheQoScriterionchosenforsecondexampleistheuserthroughput.
Wehavetaken50Kbps,anarbitraryvalueofminimumuserthroughput.
NextweAnEcientAnalyticalModelfortheDimensioningofWiMAXNetworks533Fig.
6.
AverageutilizationUFig.
7.
AveragethroughputperuserXFig.
8.
DimensioningtheminimumvalueofNforhavingU≥50%Fig.
9.
DimensioningthemaximumvalueofNforhavingX≥50KbpsperuserndthemaximumnumberNmaxofusersinthecelltoguaranteetheminimumthroughputthreshold.
InFig.
9,agivenpoint(NS,ρ)islocatedbetweentwolevellines.
ThelinewiththelowervaluegivesNmax.
Asexplainedbefore,theaveragethroughputperuserisinverselyproportionaltoN.
ThegraphsofFig.
9and8canbejointlyusedtosatisfymultipleQoScriteria.
Forexample,ifwehaveaWiMAXcellconguredtohaveNS=450slotsandatracprolegivenbyρ=300(e.
g.
,xon=1.
2Mbitsandtoff=20s),Fig.
8givesNmin=55,andFig.
9givesNmax=200.
ThecombinationofthesetwographsrecommendtohaveanumberofusersN∈[55;200]toguaranteeareasonableresourceutilizationandaminimumthroughputtousers.
6ConclusionAsdeploymentofWiMAXnetworksisunderway,needarisesforoperatorsandmanufacturerstodevelopdimensioningtools.
Inthispaper,wehavepresentednovelanalyticalmodelsforWiMAXnetworksandelasticON/OFFtrac.
ThemodelsareabletoderiveErlang-likeperformanceparameterssuchasthroughputperuserorchannelutilization.
Basedonaone-dimensionalMarkovchainandthederivationofaveragebitrates,whoseexpressionsaregivenforthreemain534B.
Baynatetal.
schedulingpolicies(slotfairness,throughputfairnessandopportunisticschedul-ing),ourmodelisremarkablysimple.
Theresolutionofmodelprovidesclosed-formexpressionsforalltherequiredperformanceparametersataclick-speed.
Extensivesimulationshavevalidatedthemodel'sassumptions.
Theaccuracyofthemodelisillustratedbythefactthat,forallsimulationresults,maximumrelativeerrorsdonotexceed10%.
Evenifthetracandchannelassumptionsarerelaxed,analyticalresultsstillmatchverywellwithsimulationsthatshowstherobustnatureofourmodel.
References1.
Group,I.
S.
W.
:IEEEStandardforlocalandmetropolitanareanetworks-Part16:AirInterfaceforFixedBroadbandWirelessAccessSystems(2004)2.
Group,I.
S.
W.
:DraftIEEEstd802.
16e/D9.
IEEEStandardforlocalandmetropoli-tanareanetworks-Part16:AirInterfaceforFixedBroadbandWirelessAccessSystems(2005)3.
Vinel,A.
,Zhang,Y.
,Lott,M.
,Tiurlikov,A.
:PerformanceanalysisoftherandomaccessinIEEE802.
16.
In:Proc.
ofIEEEPIMRC,pp.
1596–1600(September2005)4.
Niyato,D.
,Hossain,E.
:Aqueuing-theoreticandoptimization-basedmodelforradioresourcemanagementinIEEE802.
16broadbandnetworks.
IEEEToC,vol.
55(2006)5.
Borst,S.
:User-levelperformanceofchannel-awareschedulingalgorithmsinwirelessdatanetworks.
In:IEEEInfocom.
(2003)6.
Bonald,T.
,Proutiere,A.
:Wirelessdownlinkchannels:Userperformanceandcelldimensioning.
In:ACMMobicom.
(2003)7.
Liu,S.
,Virtamo,J.
:PerformanceAnalysisofWirelessDataSystemswithaFinitePopulationofMobileUsers.
In:19thITC.
(2005)8.
Engset,T.
O.
:Onthecalculationofswitchesinanautomatictelephonesystem.
In:ToreOlausEngset:Themanbehindtheformula(1998)9.
Baynat,B.
,Eisenmann,P.
:TowardsanErlang-LikeformulaforGPRS/EDGEnetworkengineering.
In:IEEEInt.
Conf.
onCommunications(ICC)(June2004)10.
Baynat,B.
,Boussetta,K.
,Eisenmann,P.
,Rached,N.
B.
:TowardsanErlang-LikeformulafortheperformanceevaluationofGPRS/EDGEnetworkswithnite-lengthsessions.
In:Proc.
of3rdIFIP-TC6NetworkingConference(May2004)11.
Berger,A.
,Kogan,Y.
:Dimensioningbandwidthforelastictracinhigh-speeddatanetworks.
IEEE/ACMTransactionsonNetworking8,643–654(2000)12.
Fredj,S.
B.
,Bonald,T.
,Proutiere,A.
,Regnie,G.
,Roberts,J.
:Statisticalband-widthsharing:AStudyofcongestionatowlevel.
In:Proc.
ofACMSigcomm.
(August2001)13.
Heyman,D.
,Lakshman,T.
,Neidhardt,A.
:Newmethodforanalyzingfeedbackprotocolswithapplicationstoengineeringwebtracovertheinternet.
In:Proc.
oftheACMSigmetrics(June1997)14.
Feldmann,A.
,Gilbert,A.
C.
,Huang,P.
,Willinger,W.
:DynamicsofIPtrac:Astudyoftheroleofvariabilityandtheimpactofcontrol.
ComputerCommunicationReview(October1999)15.
Ramadas,K.
,Jain,R.
:WiMAXSystemEvaluationMethodology.
Technicalreport,WimaxForum(January2007)