INFORMATION DYNAMICS APPLIED TO LINK-STATE ROUTING

InfoDynRouting,November1,20011INFORMATIONDYNAMICSAPPLIEDTOLINK-STATEROUTING1HyeonsangEom,AshokK.Agrawala,SamH.Noh2,A.UdayaShankar({hseom,agrawala,noh,shankar}@cs.umd.edu)InstituteforAdvancedComputerStudiesComputerScienceDepartmentUniversityofMarylandCollegePark,20742CS-TR-4297UMIACS-TR-2001-75November1,2001AbstractInformationDynamics[Agrawala,2000]isaninformation-centricframeworkthatprovidesasufficientunderstandingofthecharacteristicsofinformationusedinsystemsforbettersystemdesignandimplementation.Inthispaper,wedescribehowtoimprovelink-stateroutingbasedonthisframework.Link-stateroutingprotocolssuchasOSPF(OpenShortestPathFirst)[Moy,1991]arecurrentlyusedinmanynetworks.Inlink-staterouting,routesaredeterminedbasedonlink-delayestimates,whichareperiodicallyfloodedthroughoutthenetwork.Thisfloodingoflink-delayestimatesisdonewithoutconsideringtherelevanceoftheseestimatestoroutingquality,i.e.withouttakingintoaccounttheusefulnessofthelink-delayinformation.Wehavedevelopedanewapproachthatimproveslink-stateroutingbyestimatingfuturelinkdelaysandfloodingtheseestimatesonlytotheextentthattheyarerelevant.Thismeansthatweconsiderthedynamicsofthelink-delayinformationanditsusefulness.Simulationstudiessuggestthatourapproachcanleadtosignificantreductionsinroutingtrafficwithnoticeableimprovementsofroutingqualityinhigh-loadconditions,demonstratingtheeffectivenessoftheframework.Weplantofurtherinvestigatetheconditionswhereourinformation-dynamicsapproachisbetterthanthestandardapproach.1ThisworkissupportedpartlybyDARPA/RomeLabs,DepartmentoftheAirForce,undercontractF306020020578totheDepartmentofComputerScienceattheUniversityofMaryland.Theviews,opinions,and/orfindingscontainedinthisreportarethoseoftheauthor(s)andshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressedorimplied,oftheDepartmentofAirForce,DARPA,DOD,ortheU.S.Government.2Dr.SamH.NohiscurrentlywiththeUniversityofMarylandInstituteforAdvancedComputerStudies(UMIACS)andtheSchoolofInformationandComputerEngineering,Hong-IkUniversity,Seoul,Korea.InfoDynRouting,November1,200121.IntroductionInformationplaysamajorroleintheoperationofsystems.Ingeneral,suchinformationusedinorgeneratedbysystemsisalsodynamicinnature.TheInformation-Dynamicsframework[Agrawala,2000]providesanewperspectiveforsystemswithafocusoninformation,informationusefulness(or“value”),andthechangesofinformationanditsusefulnessovertime.Hence,withtheframework,wecanbetterunderstandtheinteractionsbetweendifferentcomponentsofasystemthatusesinformation.Suchbetterunderstandingprovidesabasisforbettersystemdesignandimplementation.Inthispaper,weapplytheinformation-dynamicsframeworktonetworksystems.Inparticular,wefocusonlink-stateroutingwhereweshowthatthedynamicnatureoflink-delayinformationplaysakeyroleindeterminingthedisseminationofthisinformation,andthattheunderstandingofthisroleeventuallyleadstomoreefficientrouting.Inlink-staterouting,eachnodeinthenetworkmaintainsaviewofthecurrentstateofthenetwork.Theviewisessentiallyagraphwithverticescorrespondingtothenetworknodes,edgescorrespondingtonetworklinks,andforeachlink,acostrepresentinganestimateofthecurrentdelayonthelink.Eachnodemakes(periodicand/orevent-driven)measurementsofthestateofeachofitsoutgoinglinks.Itperiodicallyconstructsanestimateforthecurrentdelayonthelinkfromthesestatemeasurements,andfloodstheselink-delayestimatestoallothernodesinthenetwork[Peterson,1996;Rosen,1980]sothatothernodescanupdatetheirviews.Eachnodeperiodicallyusesitsviewtocomputeleast-costpathstoallothernodes,wherethecostofapathisthesumofthecostsofallthelinksinthepath.Whenanodereceivesaworkloadpacket,itforwardsthepackettotheneighborthatisthenextnodeintheleast-costpathtothedestinationnodeofthepacket.Theinformation-dynamicsframeworkdefinestheinteractionsofentities(thebasicbuildingblocksofasystem)intermsofinformation,therebyprovidingguidanceonhowalink-stateroutingsystemcanbeimproved.Intheframework,agentsaredefinedasactiveentitiesthathavecapabilitiestoautonomouslyperformoperationsoractions,andthatcanalsoinitiateactions.Thenodesinanetworkareagentsbecausetheyinitiateroutingactivities(seriesofactions),i.e.periodicviewandrouteupdates.InfoDynRouting,November1,20013Eachagenthasitsperceivedreality,i.e.itsviewoftheworld.Eachnodeasanagentmaintainsitsperceivedrealitythatincludesitsnetwork-stateview,routes,androutecosts.Acontextofanagentisarelevantpart(togiveninformation)oftheagent’sperceivedrealitythatincludesagoalandthecostinvolvedinachievingthegoal.Inlink-staterouting,givenlink-delayinformation,eachnodehasacontext.Thegoalofeachnodeinalink-stateroutingsystemistorouteworkloadpacketstowardminimizingtheend-to-enddelays.Eachnodetakesactionswiththeinformation,suchasusingandbroadcastinginformation,inordertoaccomplishitsgoal.Themaincostinvolvedistheoverheadofbroadcastinglink-delayestimates.Theinformation-dynamicsframeworkallowsustoconsiderthiscontextofeachnodeinimprovinglink-staterouting.Thekeyconceptinthiswholeframeworkisthenotionofinformationdynamics,thatis,thefactthattheusefulnessofinformationaswellasinformationitselfm