I.J.ComputerNetworkandInformationSecurity,2014,1,19-25PublishedOnlineNovember2013inMECS()DOI:10.5815/ijcnis.2014.01.03Copyright©2014MECSI.J.ComputerNetworkandInformationSecurity,2014,1,19-25DistributedTrafficBalancingRoutingforLEOSatelliteNetworksYongLu,FuchunSun,YoujianZhao,HongboLi,HeyuLiuTsinghuauniversity,Beijin,China{lysky007@gmail.com,fcsun@tsinghua.edu.cn,zhaoyoujian@tsinghua.edu.cn,hbli@mail.tsinghua.edu.cn,hy-liu10@mails.tsinghua.edu.cn}Abstract—Satellitenetworkshavebeenwidelyinvestigatedbothinthebusinessandacademiaformanyyears,withmanyimportantroutingalgorithmsreportedintheliteratures.However,fewerexistingroutingalgorithmsfocusonthetrade-offbetweentheroutingsurvivabilityandtheroutingcomputationandstorageoverheads.Duetotopologicaldynamics,itisdifficulttoeffectivelyapplytheconventionalroutingprotocolssuchasRIPorOSPFtoLowEarthOrbit(LEO)satellitenetworks.Accordingtothevirtualtopologymodelbasedonvirtualnode,thispaperproposeanewfullydistributedroutingprotocolforLEOsatellitenetworks,calledDistributedTrafficBalancingRouting(DTBR).Theproposedprotocolnotonlyguaranteestheroutingsurvivabilityandprovidestheabilityoftrafficbalancing,butalsoresultinfewadditionalcomputationandstorageoverheadsonlyderivingfromtheinformationfloodingoffailedsatellites.Simulationresultsdemonstratepositiveconclusionsofourmethods.IndexTerms—LowEarthOrbit(LEO),satellitenetworks,snapshot,survivabilityI.INTRODUCTIONSatellitenetworkshavebeenanimportantinfrastructureofbothNext-GenerationInternet(NGI)andInterplanetaryInternet(IPN).Comparedwiththegroundnetworks,satellitenetworkscanprovidetheextraordinaryadvantagesinglobalcommunication,broadcast,spaceinformationdevelopment,etc.Mostsatellitenetworksmakeuseofinter-satellitelinks(ISLs)toconstructadynamicnetwork,whosecharacteristicssuchasthetopologicaldynamics,limitedprocessingfacilityandstoragespace,etc.,obstructtheeffectiveimplementationofconventionalroutingprotocolssuchasRIPorOSPF.Withtherapiddevelopmentofspacetechnologies,futurespacecommunicationwillbeconfrontedwithcomplexsituation.Notonlythenaturalfactorssuchaselectromagneticinterference,physicalfailureandenergylimited,butalsothefactitiousbehaviorsuchasspatialcompetition,militarystrike,etc.,mightresultinthesatellitefailure,whichcanbringthesignificantimpactonthecommunicationofsatellitenetworks.Firstofall,theeffectsofthefailedsatellitesoncommunicationareglobal.Oncethefailedsatellitesmovetoanewgeographicalareawhereprevioussatellitesaresafe,thecommunicationofthisareaisinfluenceduntilthefailedsatellitesmoveaway.Secondly,duetothelongrenewingcycleandexpensivemaintenance,therecoveryofthefailedsatellitesneedsalongtimeorcannotevenbecompleted.Thereforeitisachallengeissuetodeveloptheefficientandsurvivableroutingprotocolsforsatellitenetworks.Sofar,manyroutingschemeshavebeendevelopedforsatellitenetworks.Fortheroutingalgorithmsbasedonvirtualtopology(VP)[1],[2],[3],thetimevaryingtopologyistackledbyadiscretetimenetworkmodel.Ineachtimeinterval,thesatellitenetworkisassumedtohaveafixedtopology.Thetimeintervalisdeterminedbythechangeofthephysicaltopologyorothermetricssuchaspropagationdelay[1].Forexample,theconceptofsnapshots[2]wasintroducedtodescribethedynamicsofLSNs.WhenanewISLisaddedoranalreadyexistingISLisbroken,anewsnapshotdifferentfromthepreviousonewillbeformed.However,thenumberofsnapshotsinitscyclecanbeverylargeastheISLschangeprettyfastwhentheypassthesouthandnorthPolarRegionsorswitchovertheseam,whichresultsintheverylargeoverheadsofroutingcomputationandstorage.In[4],basedonthepredictablechangesofspacecraftnetworks,theauthorsformalizethesnapshotconcept.Everysatelliteonlystoresthedifferencesbetweenadjacentsnapshotsandthetransitionrules,sothesnapshottransitioncanbecompletedautomaticallybythesatelliteswithlowstorageoverhead.Nonetheless,thesnapshotnumberisessentiallyunchanged,whichmeansthatthefrequentroutingcomputationisstillunavoidable.WiththerapidgrowthofInternet-basedapplications,manydistributedroutingalgorithms[5],[6],[7]arepresentedtoforwardthepacketswiththenominaloverhead.Sincethedistributedroutingschemesdecidestheroutebythelocalinformation,theyarejustsuitableforthecasethatonlyaneighboringsatellitefails,insteadofthecasethatanysatellitemayfailatanytime.Toimprovetheroutingperformance,routingprotocolsbasedonmulti-layeredsatellitenetworkareproposed[8],[9],[10].However,theseroutingprotocolsonlyconsideredthecaseofrandomnodefailuresinLEOsatellitelayer.Infact,iftheMEOsatellitefails,theseroutingprotocolswillcollapse.Anagent-basedloadbalancingrouting(ALBR)[11],[12]ispresentedforLEOsatellitenetworks,inwhichmobileagentsandstationaryagentscooperatetoachievetheloadbalancingrouting.However,thecaseofrandomnode20DistributedTrafficBalancingRoutingforLEOSatelliteNetworksCopyright©2014MECSI.J.ComputerNetworkandInformationSecurity,2014,1,19-25failureisnotconsidered.Inthiscase,themobileagentdoesnotknowthenetworktopology,soitispossiblethatthemobileagentremoveitselfbeforeitreachesthedestinationbecauseofthefaultysatellites.Fromtheabovestatement,itcanbeseenth