搜索
Real-timeOn-lineNetworkSimulationBoleslawSzymanski,YuLiu,AnandSastry,KiranMadnaniDepartmentofComputerScience,RPI,Troy,NY12180,USAemail:{szymansk,liuyu6,sastra,madnak}cs.rpi.eduAbstractThecomplexityanddynamicsoftheInternetisdrivingthedemandforscalableandeffi-cientnetworksimulation.Thispaperdescribesacollaborativeon-linesimulationschemethatsupportsreal-timeon-linecollaborativesimulators.Themajordifficultyinsimulatinglargenetworksatthepacketlevelistheenormouscom-putationalpowerneededtoexecutealleventsthatcommunicationpacketsundergointhenet-work.Theneededcomputationalresourcescanonlybeprovidedbytheparallelcomputationinvolvingalargenumberofprocessors.However,parallelizingsimulationatpacketleveldoesnotworkefficientlyandthereforedonotscaletolargenumberofprocessorsbecauseoftightsynchronizationbetweennetworkcomponents.Toovercomethisproblemwedesignedamethodinwhichalargenetworkisdecomposedintopartsandeachpartissimulatedindepen-dentlyandconcurrentlywiththeothers.Thesepartsexchangeinformationperiodicallyaboutthepacketdelaysandlossesalongthepathswithineachpart.Eachpartiteratesoverthese-lectedsimulatedtimeintervaluntiltheexchangedinformationchangeslessthantheprescribedtolerance.Eachdecomposedpartmayrepresentasubnetorasubdomainoftheentirenetwork,therebymirroringthenetworkstructureinthesimulationdesign.Theproposedmethodisindependentofthespecificsimulatortechniqueemployedtorunsimulatorsofthepartsofthedecomposednetwork.Hence,itisageneralmethodforefficientparallelizationofnetworksimulationbasedonconvergencetothefixedpointsolutionofinter-parttraffic.Themethodcanbeusedinallapplicationsinwhichthespeedofthesimulationisofessence,suchas:on-linenetworksimulation,networkmanagement,ad-hocnetworkdesign,emergencynetworkplanning,largenetworksimulationornetworkprotocolverificationunderextremeconditions(largeflows).Thedescribedmethodcanalsobeusedtosimulatenetworksotherthancomputerandcommunicationnetworks,likedistributionnetworkofgoodsandproducts,roadtraffic,etc.Inthepaper,weprovidethedescriptionoftheproposedmethodanditsimplementationbasedonnssimulator,andwepresentthesimulationandtestresultsofexperimentsonthesamplecommunicationnetworks.11IntroductionThemajordifficultyinsimulatinglargenetworksatthepacketlevelistheenormouscomputationalpowerneededtoexecutealleventsthatpacketsundergothenetwork[6].Theusualapproachtoprovidingsuchvastcomputationalresourcesreliesonparallelizationofanapplicationtotakeadvantageofalargenumberofprocessorsconcurrently.Suchparallelizationdoesnotworkeffi-cientlyfornetworksimulationsatpacketlevelbecauseoftightsynchronizationbetweennetworkcomponents[3].Toovercomethisdifficulty,wedesignedamethoddescribedinthispaper,inwhichalargenetworkisdecomposedintopartsandeachpartissimulatedindependentlyandsi-multaneouslywiththeothers.Eachpartrepresentsasubnetorasubdomainoftheentirenetwork.Thesepartsareconnectedtoeachotherthroughedgesthatrepresentcommunicationlinksexistinginthesimulatednetwork.Intheinitial(zero)iterationofthesimulationprocess,eachpartassumesonitsexternalin-linkseithernotrafficortrafficequivalenttotheonethatismeasuredinthemonitorednetworkwhenon-linesimulationisused.Then,eachpartsimulatesitsinternaltraffic,andcomputestheresultingoutflowofpacketsthroughitsout-links.Inthesubsequentk0iteration,theinflowintoeachpartfromtheotherpartswillbegener-atedbasedontheoutflowmeasuredbyeachpartintheiterationk−1.Oncetheinflowstoeachpartiniterationkarecloseenoughtotheircounterpartsintheiterationk−1,theiterationstopsandthesimulationeitherprogressestothenextsimulationtimeintervalorcompletesexecutionandproducesthefinalresults.Moreformally,consideranetworkΓ=(N,L),whereNisasetofnodesandL(asubsetofCartesianproductN×N),asetofunidirectionallinksconnectingthem(bidirectionallinksaresimplyrepresentedasapairofunidirectionallinks).Let(N1,...,Nq)beadisjointpartitioningofthenodes,eachpartitionmodeledbyasimulator.ForeachsubsetNi,wecandefineasetofexternalout-linksandin-linksaswellaslocallinksasfollows:Oi=L&Ni×(N−Ni),Ii=L&(N−Ni)×Ni,andLi=L&Ni×Ni.ThepurposeofasimulatorSi,thatmodelspartitionNiofthenetwork,istocharacterizetrafficonthelinksinitspartitionintermsofafewparameterschangingslowlycomparedtothecollaborativesimulationtimestep.Intheimplementationpresentedinthispaper,wecharacterizeeachtrafficasanaggregationoftheflows,andeachflowisrepresentedbytheactivityofitssourceandthepacketdelaysandlossesonthepathfromitssourcetotheboundaryofthatpart.Sincethedynamicsofthesourcecanbefaithfullyrepresentedbythecopyofthesourcereplicatedtotheboundary,thetrafficischaracterizedbythepacketdelaysandlossesontherelevantpaths.Thankstoqueuingattheroutersandtheaggregatedeffectofmanyflowsonthesizeofthequeues,thepathdelaysandpacketdroppingrateschangemoreslowlythanthetrafficitself.Itshouldbenotedthatwearealsoexperimentingwiththedirectmethodofrepresentingthetrafficontheexternallinksasaself-similartrafficdefinedbyafewparameters.Theseparameterscanbeusedtogeneratetheequivalenttrafficusingon-linetrafficgeneratordescribedin[12].Nomatterwhichcharacterizationischosen,basedonsuchcharacterization,thesimulatorcanfindtheoverallcharact