DOC

An Overlay Multicast Routing Algorithm Based on Genetic Algorithms

By Jay Perry,2014-02-17 20:22
8 views 0
An Overlay Multicast Routing Algorithm Based on Genetic Algorithms

An Overlay Multicast Routing Algorithm

    Based on Genetic Algorithms ChineseJournalofElectronics

    Vo1.16,No.1,Jan.2007

    AnOverlayMulticastRoutingAlgorithm

    BasedonGeneticAlgorithms

    CHENGPeng.DAIQionghaiandWUQiufeng

    (DepartmentAutomation,TsinghuaUniversity,Beng100084,China) Abstract——Overlaymulticasttreessh0uldbebuilt

    accordingtothreeconstraints:cost,loadbalancingand stress.ThisPaPerformalizesafunctiontoevaluatethe performanceofmulticasttreesinacertainmeshonthe threeindexesrespectivelyandgeneratesanoverallfit

    nessfunction,thenProPoses0MR-GAsolution,anoverlay multicastroutingapproachbasedongeneticalgorithms. Numericalsimulationsshowthatcomparedtosimplegeo- graphicalroutingrules.oMRGAsolutionfindsmoreoi>- timizedtreessatisfyingtheloadbalancingandstresscon- straintswhichhavelesscostandaremoresuitablefordata distribution.CombinedwithAnalyticHierarchyProcess aIgorithm,OMR-GAcanobtainaquickconvergence.

    Overlaymulticast,Multicastrouting,Ge_ Keywords

    neticalgorithms,Analytichierarchyprocess. I.Introduction

    Multicastservicesallowonehosttosendinformationtoa largenumberofreceivers,withoutbeingconstrainedbyitsnet

    workinteffacebandwidth.Earlymulticastprotocolsarecalled

    IPmulticast(IPM)protocols.Thelimitednetworklayersup- portforIPMintheInternethasmadeitnecessarytodeploy multicastservicesatahigherleve1.0verlaymuIticast(0M, alsoknownasApplicationlayermulticast,ALM1wasthen proposed[.

    0MsystemsarebuiltontopofInternetunicastinfras

    tructure.InOMsystems,hostsself-organizeintoacontrol topologycalledmesh,thenonetreeoronesetoftrees,which areOMdatatopologies,willbebuiltembeddedinthemesh byaroutingalgorithm.Multicastdataistransferredalong the0Mtree.OneOMgroupanditscorresponding0Mtree areshowninFig.1.

    Thepurposeofmulticast(either0MorIPM)routing algorithms[Jistofindmulticasttreessatisfiedwithcost andloadbalancingconstraints.Inoneoftheearliestpapersto addresstheissueofroutingtomultipledestinations[16,asin-

    glecostisassociatedwitheachlinkinthenetwork.MSTH[7

    andADHJalgorithmsaremodifiedtointegratelinkcapaci

    tiesformulticastrouting.Thenodalloadbalancingproblem ofIPMtreesisdiscussedinR,ef.f191.

    Theperformanceof0Mtreesshouldalsobedescribed bycostandloadbalancingindexes.Thoughtheindexesare mostlysimilartothoseofIPMtrees,manyearly0Mproto- colsusesimplegeographicalrules,suchasCompassRouting (cR)[1,8,BidirectionalMinimalSpanningTree(BMST)[2and

    floodingrouting.tobuildanacceptabletreeinsteadoftry- ingtofindanoptimizedtree.Thesesimpleroutingrulescan notoptimizetheoverallperformance,sometimestheycaneven notoptimizeanysingleperformanceindex.

    ()(b)

    Fig.1.Overlaymulticasttopologies.)Overlaymulticast group;(b)Overlayrnulticasttree

    SomerecentOMroutingalgorithmstrytooptimizethe overallperformanceofOMtreest71.Butthesealgorithms onlypayattentiontocostandloadbalancingamongapplica- tionlayerhosts.andignorethenetworklayerIoadbalancing indexwhichiscalledstressl..OneOMtreemayuseonenet

    worklayerlinkmorethanonce,whichmeansonephyrsicallink maytransitthesamemulticastdataseveraltimes.Thelink usedmanytimesbythesameoMtreemaybecomethebot

    tieneckofthemulticastsession.Sothestressindexisalsoan importantfactorinfluencing0Mrouting.

    Inthispaper,anovelOMroutingalgorithmbasedonGe- neticAlgorithms,OMR-GA,isproposedtoachieveasource treeaccordingtocost,loadbalancingandstressconstraints. oMRGAalgorithmcanbeadaptedtodifferentroutingcon- straintsbymodifying,combiningandchangingfitnessfunc- tionsandweights.

    ManuscriptReceivedApr.2005;AcceptedJune2006.ThisworkissupportedbytheNational

    NaturalScienceFoundationofChina

    (No.60432030)andDistinguishedYoungScholarsofNSFC(No.60525111).

162ChineseJournalofElectronics2007

    Theothersectionsofthispaperareorganizedasfollow

    ing:SectionIIdescribesthe0Mroutingproblemandpro- posesthefitnessfunctionsforOMtrees;SectionIIIdiscussed 0MRGAindetails;thenumericalsimulationissummarized inSectionIV,performanceoftreesgeneratedbyOMRGA,

    CRandBMSTinonecertainmesharecompared.SectionV givesouttheconclusion.

II.ProblemDescription

    1.Networkmodel

    ThehostsinOMgroupself-organizeintoaconnectedmesh whichcanbesummarizedasadirectedgraphM(H,P'c).The meshMconsistsofanonemptysetHoflHlhostsanda setP,PCH×H,oflPlunicastpathsconnectingpairsof hosts.Eachunicastpathisassociatedwithacostfunction, c:P--+R.Thesepathsareelementpathswhicharecandi- datestobuildOMtree.H=sUD.sisthedatasourceofthe groupandotherhostsbelongingtoDarethereceivers.The 0Mmeshisacompletegraphifanytwohostsareconnected byelementpaths.

    Withaviewtothenetworklayertopology.the0Mmesh canbesummarizedintoadirectedgraph,G(H,N,L,E,c). ThesetNconsistsoffNfroutersandthesetEconsistsof edgesconnectingpairsofrouters,ENxN,E={eli?

    N,ilEl}.ThesetLconsistsofthelinksconnectinghosts androuters,lLl=lHI,L={lJ?N,JlLI}.Alledgesand

    linksareassociatedwiththecostfunctionc.Anelementpath inMcanbewrittenasalink-edges-linksequence,theelement path'scostisequaltothesumofthelinks'andtheedges'cost inthesequence.

    2.oMroutingconstraints

    GivenmeshM.theobjectiveof0Mroutingalgorithmis tofindaspanningtreeT(H,F),FP,M,subjectedto thefollowingconstraints.

    CostconstraintAtree'scostisthesumofcostofits allbranches.Theobjectiveofcostoptimizationistofinda spanningtreeT(H,F)ofgivenmeshM,whosecostshouldbe theminimumamongallofM'sspanningtrees.

    LoadBalanceconstraintForahost,thenumberofits childreninOMtreeshouldnotbemorethananupperbound. Forhosth,usedmax()anddT(h)todenotethedegreebound anditsactualdegreeintreeTrespectively.Observethevari- abe

    ratdT(h)=dT(h)/dm(^)

    The0Mroutingproblemunderloadbalanceconstraintis: FindaspanningtreeT(H,F)ofgivenmeshM,subjectto ?ratdT(h)1,Yh?日;

    ?thevalueofmaxhratdT(h)isthemaximumoneamong allofM'sspanningtrees.

    StressconstraintThestressconstrainttriestolimit themaximumtimesforoneedgetotransitthesamedata.Be analogoustoloadbalanceconstraint,8maxe)and8T(e)are definedasthestressupperboundandtheactualstressintree ofedgee.Theroutingproblemunderstressconstraintis: FindaspanningtreeT(H,F)ofgivenmeshM,subjectto ?ratsT(e)1,Ve?;

    ?thevalueofmaxeratsT(e1isthemaximumoneamong aUofM'sspanningtrees.where

    ratsT(e)=ST(e)/smaxe)

    III.ProposedAlgorithm

    HeuristicsbasedonGeneticalgorithms(GA)havebeenap- pliedtosolvetheroutingproblemincommunicationnetworks foralongperiod.InRef.[5GeneticAlgorithmsareusedto

    buildIPMtreebyoptimizingthetree'scost.Refs.914use

    GAtosolveIPMroutingproblemswithbandwidthandcost constrains.Ref.151combinesGAandNeuronnetworks(NN) forIPMrouting.InRef.[7aGAbased0Mroutingalgorithm

    isproposedtooptimizeOMtree'scostanddegreeperformance

inacompletegraphmesh.

    1.Algorithmsteps

    MeshsetupGivenH,?,E,c,s,chooseelement

    pathstoachieveaconnectedmesh,thencalculateeachele

    mentpath'scostandthestressforeachedgeintroducedby it.

    RoutingtablesForacertainreceiver,findallpossible overlayroutesfromthesourcetoitandsortthembycost. PickuptheRrouteswiththeleastcosttobuildtherouting tableforthisreceiver.Onepossibleroutemaybeanelement pathorasequenceofseveralelementpaths.Onlyoverlay routesinroutingtablesmaybeusedasdatapathfromsource toreceivers.

    InitializationofchromosomesFordestinationset D={hi,h2,,hlHI1),useastringofintegerswithlength (1l1)torepresentachromosome.Thevalueofthei-th gene,gl,representsthepositionoftheroutefromsourceto hiusedinthisOMtreeinthecorrespondingroutingtable. Theinitialproceduregeneratesseveraldifferentchromosomes randomlyasthefirstgeneration.

    FitnessevaluationUsethefollowingthreefunctions toevaluatecost,balanceandstressperformanceofachromo- some.

    ?

    fl=1——C(T)/C(M,

    whereC(M)isthetotalsumofallelementpaths'costinM andC(T)isthetotalsumofT'sallbranches'cost. 10,.theise

    .

rmaxeratsT(e),ifmaxeratsT(e)1,.10,.theise

    Defineoverallfitnessfunctionas

    f=lfl+2.2+A3.3,

    wherel,2,A3areweights.

    Chromosomesrepr0ducti0nThechromosomesre

    productionprocedureincludesthreephases:selection, crossoverandmutation,discardtheduplicatechromosomes. Thechromosomesaresortedaccordingtotheirfitness value.Halfofthemwithsmallerfitnessvaluedieolfandthe otherhalfsurvive.Thenewgenerationincludestwoparts. Thefirstpartisthecopyofthesurvivedchromosomesinthe father'sgenerationandthesecondpartisgeneratedbythe

    AnOverlayMulticastRoutingAlgorithmBasedonGeneticAlgorithms163 firstpartthroughsinglepointcrossoverandmutationopera-

    tion.Thebreakpointsofcrossoveroperationsarerandomly chosen.ThemutationprobabilityforacertaingeneisP,and thenewvalueofthegeneaftermutationischosenfrom1to Rrandomly.Aftercrossoverandmutationoperations,ifthere areduplicatedchromosomesinthenewgeneration,thenran- domlygeneratenewchromosomestoreplacetheredundant OlleS.

    EndconditionsThemaximumofgenerationsis

    achieved.

    2.Choosingproperweights

    Theweightsofthreefitnessfunctionsinoverallfitness functioncanbedescribedasaweightvector.Thevectorinfiu- encesthealgorithmoutputwhentheratiosofweightschanges. Insimplestapplications,theweightscanbepre-set.Forex- ample,setl:2:Aa=1:1:1.Buttheweightsmay

    needmoreexactnumericalanalyze.Analytichierarchypro- cess(AHP)method[20canbeusedtocalculatetheproper

    weightswhenoneortwofitnessvaluesaremoreemphasized thantheothers.

    Inmostsituations,costfitnessshouldbethemostimpor

    tantoneamongthreeindexesandtheloadbalancingfitness takesthesecondplace,anobjectivejudgementmatrixasfol- lowingcanbegeneratedbyAHP.

    135]

    A=I1/313I

    L1/51/31J

    Mutationprobability

    Fig.2.Theeffectsofthescaleofroutingtable

    andmutationprobabilityontheoutput

    oftheproposedalgorithm

    AccordingtoAHP,theproperweightsshouldbe

    l:2:Aa=0.6333:0.2605:0.1062

    IV.SimulationandAnalyze

    Thesimulationnetworktopologyissimilartotheoneused inRefs.11and41.GeneratedbyGTItmtJ,thesimulation

    topologyisdistributedona100×100plant.Thereare8transit

    routers32stubroutersand20hosts,Onehostisconnectedto astubrouterviaalink.Anedge'scostisthedistancebetween thepairofrouters,alllinks'costaresetas1.

    Anytwohostsareneighborswithaprobabilityof0.3.The simulationmeshincludes63pairsofneighbors,126element paths.Thesumofallelementpaths'costis11174.Thede_ greeupperboundissetas4forallhosts.Theupperboundof stressissetas10fortheedgesconnectingtwotransitrouters,

4forthoseconnectingtwostubrouters,8forthoseconnect

    ingonetransitrouterandonestubrouter.Thepopulationof geneticalgorithmis10,maxgenerationis500.

    ThereferencetreesaregeneratedbyCompassrouting (cR)usedinRef.[1]andtheBidirectionalminimalspanning tree(BMST1usedinR_ef.I21.CRbuildssourcetreesrootedon themulticastsourcehost.whileBMSTisasharetreedecided bythemesh.ThefitnessvaluesoftheBMSTofthesimulation meshisrespectively0.7940,0.6000and0.7500. 1.Parameterssetup

    Inthisstep,thefoCUSistheeffectsoftheparameters,.e. scaleofroutingtablesRandmutationprobabilityP.Pidone

    hosttoactasthemuIticastsource,setRas5,10,15,20re- spectively,PincreasesfromO.1to0.9,l=2=Aa=1,for each(R,P)pair,runOMR-GAalgorithm10timestoobtain 360OMR_GAtrees.

    TheloadbalancingfitnessandStressfitnessofall360trees areallequalto1.Thedifferenceofoutputfitnessvaluesmostly comesfromthedifferenceofthecostfitnessvalues,asshown inFig.2.WhsameP.theoutputfitnessvaluedecreaseswhen Rincreases.WithsameR,theoutputfitnessvaluetendsto decreasewhenPincreases.

    TooptimizetheproperOMtree,Rshouldbesetas5and Pshouldbesetintheinternal[0.1,0.5.whsameR,Pinflu

    GenerationsGenerations

    Fig.3.Theevolutionprocess

    encestheconvergencespeedofOMR-GAalgorithm.Asshown inFig.3andFig.4,theoutputfitnessvalueswhenP=0.3is largerthanthosewhenP=O.5.buttheevolutionprocesscon- vergesmoreslowlythanthelaterones,inwhichtheoutput

    fitnessdonotchangemuchafter300generations. 2.ComparisonwithCRandBMST

    Thethreefitnessfunctions'valueofthesourcetreerooted onthesamehostusedintheabovesimulationbyCompass routing(cR)isrespectivelyO.8337,1and0.All360oMR

    GAtrees'costfitnessvaluesobtainedintheabovesimulation arelargerthanthatoftheBMST,only13(3.61%)trees'cost fitnessvaluesarelessthanthatoftheCRtree.Especially whenR=5.all9O0MRGAtrees'costfitnessvaluesare

    largerthantheCRtreeasshowninFig.5.

    F~rthermore,takedifferenthostinthegroupasmulticast 1Il0I10uIIlJ??0II0_l,d

    110I10uII1??0II0_l0.

    l1110I10uIIlJ??0II_l

164ChineseJournalo/Electronics2007

    source.Foreachhost,setR=5,P0.2,A1=A2A3=1, runOMR.GAalgorithm10timestoobtain10OMR.GAtrees. whilegettheCRtreerootedonthesamehost.Forthesame source.each0MR.GAtrees'overallfitnessvalueisalways largerthanthatofthecorrespondingCRtreeandtheBMST. Tble1showsthecomparisonofthefitnessvaluesof0MR. GAtreesandcorrespondingCRtree.Table2showsthecom. parisonoftheaveragefitnessvaluesofall200OMR.GAtrees. 20CRtreesandtheonlyBMST.

    Fig.4.Thedeviationfrom500generationoutput 2.87

    2.86

    2.85

    2.84

Report this document

For any questions or suggestions please email
cust-service@docsford.com