Networking and Telecommunications Group

YoungsuChae

ShashidharMerugu

EllenW.Zegura

SamratBhattacharjee

NetworkingandTelecommunicationsGroupDepartmentofComputerScienceCollegeofComputing,GeorgiaTech,Atlanta,GAUniversityofMaryland,CollegePark,MDyschae,merugu,ewz@cc.gatech.edubobby@cs.umd.edu

Abstract—Oneofthetraditionalgoalsofnetworkinghasbeentohide

detailsofnetworktopologyfromendusers.Asnetworksbecomelargerandmoreheterogeneous,however,situationsariseinwhichtheabilitytoidentifyparticulartopologicalpropertiesenablescapabilitiesandperfor-mancethataredifficulttoachievewithapurely“blackbox”interfacetonetworktopology.Examplesofsuchsituationsincludedeploymentofac-tivenetworkingfunctionalitytostrategicpoints(e.g.,upstreamfromalossylink)ortheconstructionofasecureoverlaytopologyonanetworkwithselectivesupportforIPsecurity.Ontheotherhand,anapproachthat“opensup”thenetworkwithoutconstraintsseemsneithernecessarynorpractical.Wethereforeproposeamethodtoqueryandsynthesizenetworkinformationthatallowsconstrainedprogrammability.Wedemonstratethemethodonasetofexamples,andwediscussourimplementationwithinanactivenetworkingenvironment.

Keywords—activenetworks,programminginterfaces,activeservices

I.INTRODUCTION

Oneofthetraditionalgoalsofnetworkinghasbeentohidede-tailsofnetworktopologyfromendusers.Forexample,asendercanuseIPtotransmitpacketstoanydestination,withoutregardto(orinformationabout)thetopologybetweenthesourceanddestination,beyondconnectivity1.Asnetworksbecomelargerandmoreheterogeneous,however,situationsariseinwhichtheabilitytoidentifyparticulartopologicalpropertiesenablesca-pabilitiesandperformancethataredifficulttoachievewithapurely“blackbox”interfacetonetworktopology.Forexample,considerthefollowingproblems:

Determinethecapacityonthemost-constrainedlinkinthemulticasttreerootedataparticularsourcehost.Thisinfor-mationcouldbeusedtoaffectthesourceencodingofthedatasothatitissuitablefortheleastcapablereceiver.Placearepairserverattheupstreamendofanylinkinthemulticasttreefromsourcetomulticastreceivergroup,whoselossrateexceedspacketspersecond.Thepurposeoftherepairserveristocachepacketsfromthesourceandreplytonegativeacknowledgementsinamoretimelymannerandwithlessoverheadthanrelyinguponthesource[1].

Constructavirtualtopologywhoselinksandnodes(i.e.,routersandhosts)aresecurebasedonsupportforIPsec[2]andanadequatedistributionofsharedkeys.

Accesstointernalnetworktopologyinformationiscriticaltotheseproblems;hidingtopologymakesthemdifficultorim-possibletosolve.Ontheotherhand,anapproachthat“opens

WorksupportedbyDARPAundercontractnumberN66001-97-C-8512.

1Due

tothebest-effortnatureofIP,ofcourse,thesetransmittedpacketsmay

ormaynotactuallybereceived.

up”thenetworkwithoutconstraintsseemsneithernecessarynorpractical.Theexamplesabovedonotrequireafullypro-grammablenetworkinterface,withtheassociatedwell-knownconcernsregardingperformanceandsecurity.

Weproposeaprogrammablegather-compute-scatter(GCS)mechanismtoqueryandsynthesizenetworkinformation.Theusercontrolstheactivityduringeachphase(gather,compute,scatter)andcanprescribemultipleiterations.However,thecomputephaseisrestrictedinaccessandcomputation,balancingprogrammabilitywithperformanceandsecurity.TheprimaryadvantagesovertraditionalMIBqueriesare(1)dynamiccontroloverwherequeriesareperformed,(2)network-embeddedsyn-thesisofresults,and(3)dynamiccontroloverwhereresultsaresent.Theseadvantagestranslateintosavingsinbandwidthandtimeoveracentralizedandnon-programmablequerysystem.Thepaperisorganizedasfollows.ThenextsectionstatesourassumptionsaboutthenetworkanddescribestheGCSmecha-nisminsomedetail.InSectionIIIweillustratetheuseofthemechanismthroughasetofexamples.SectionIVdescribesourimplementationwithinanactivenetworkingenvironmentandreportsonaperformanceexperiment.RelatedworkisdescribedinSectionV,andweconcludeinSectionVI.

II.THEGATHER-COMPUTE-SCATTERMECHANISM

A.Networkmodel

Weassumeanetworkconsistingofnodes(i.e.,routersorhosts)andlinks(i.e.,channelsonwhichnodescansendmes-sages).Linksmaybephysicaltransmissionmedia,ortheymaybeahigherlayerentity.Bothnodesandlinkshaveattributespro-vidingstaticordynamicinformation.Forexample,anattributemightbetheaveragequeuelengthforalinkorthesupportforaparticularprotocolatanode.Weassumethateachnodehasalocalinterfacethatcanbeusedtoreadtheattributevaluesforthenodeandanyincidentlinks.Eachnodeandlinkhasanattributewhichisagloballyuniqueidentifier.Inadditiontotheattributestorage,weassumeeachnodehasastatestorethatcanbeusedbyapplicationstoholdtemporaryinformation.B.IGCSoverview

WeproposetheIterativeGather-Compute-Scatter(IGCS)dis-tributedcomputationmodeltoqueryandsynthesizenetworkstate.IGCSprogramsrepeatagather,compute,scattercycleuntilagivenconditionissatisfied.Formanyprograms,thenumberofiterationsispre-determinedandfixed,thoughthisis

notrequired.Duringaniteration,asetofmessagesarecollectedduringthegatherphase.Onceaspecificsetofmessageshavebeencollected,thecomputephasecommences.Theinputstothecomputationarethesetofcollectedmessages,thenodeandlinkattributes,andthestatestoreforthiscomputation.Thecomputephasecanproduceasinglemessage(ofafixedIGCSmessagetype)thatisthen“scattered”,i.e.transmittedtoasetofdestinations.IGCSprogramscanretainstateatanodewhiletheyareactive.AllstateislostafterthelastiterationoftheIGCScomputation.

SSSS :SourceR :IGCS RouterRD :DestinationRDDDDDDDDSource initiates a queryThe query is scattered on a Computation treeSSRRDDDDDDDDResults are gathered from...gathered results are synthesized and scattereddownstream neighbors ....to upstream nodes in the Computation TreeFig.1.Snapshotsofadistributedcomputationmodeltoquerynetworkstate

Figure1illustratesfoursnapshotsofthismechanisminsidethenetwork,comprisingtwoiterations.Theinitialscatterphaseisusedtodisseminateaquerydownapath(oratree),andthesecondgatherphaseisusedtoaccumulateresults.Thecomputephasesynthesizesinformationateachnode.Wecanseehownetworkinformation(e.g.,lossrate)canbegatheredupacomputationtree(e.g.,correspondingtoamulticastdistributiontree).Thegatheredinformationcanbeprocessedateachnode(e.g.,themaximumofallthegatheredlossratesiscomputed)andthenforwardedupthecomputationtreetosatisfyanetworkquery.

C.IGCSspecification

AnIGCSnode-levelcomputationisspecifiedbyasetofthree-tuples:

01wheredenotesthetotalnumberofiterations.Thesets

andandthefunctiondescriptiondefinetheprocessingduringthegather,scatter,andcomputephasesoftheiteration,respectively.

Thegatherphaseofthe

iterationisspecifiedbytheset,oftheform12,whereeachidentifiesaspecificlinkincidenttothenodewherethecomputationisrunning.AnyIGCSmessagethatarrivesononeoftheselinksandcontainstheidentifierforthisIGCSinstantiationwillbedeliveredandstoreduntilonemessagehasbeenreceivedoneachlink.

Thecomputephaseofthe

iterationisspecifiedbythefunction.Anyfunctionthatcanbeexecutedduringacompute

phasehasthefollowingsignature:

Σ

Σ

Π

whereisanIGCSmessage,Πisthestatestoreassociated

withthisnode-levelcomputation,

isthesetofmessagesgatheredduringthegatherphase,Σisthecurrentnodeat-tributes,andΣ

isthecurrentlinkattributes.maybenull,correspondingtoafunctionthatdoesnotproduceanoutputmessage.

Thus,functionsinthecomputephasetakeasinputthestateofthenodeandlinks,setofmessagesgatheredinthecurrentiteration,andacomputation-specificstatestore.Theymaypro-duceasinglemessagethatisthenforwardedinthescatterphase.Stateaccumulatedbyiterationsofacomputationisstoredinitsstatestore.Thestateisdiscardedafterthelastiteration.Aswillbeillustratedlater,onecommonpurposeofthecomputephase(inadditiontoproducinganoutputmessage)istogeneratethegatherandscattersetsforsubsequentiterations.Thescatterphaseintheiterationisdefinedbytheset.Eachisasetoflinkdescriptors12.Duringthe

iteration,themessageproducedbythecomputephaseisforwardedonalllinksspecifiedby.

D.IGCSmessageformat

TheformatofanIGCSmessageisshowninTableI.Each

KeyValue

compIdComputationIdentifiertopIdTopologyIdentifier

...

...

III.EXAMPLESOFIGCSCOMPUTATIONS

TodemonstratehowtheIGCScomputationmodelworks,wedescribeafewexamples.Webeginbyconsideringaqueryex-ample,wherethegoalistoidentifytheleastavailablebandwidthonthepathfromasourcetoadestination.WethenshowhowatrivialmodificationallowstheIGCScomputationtobeex-tendedtoidentifytheleastavailablebandwidthonthemulticasttreefromasource.Wethenturntotwoexamplesthatinvolveidentifyingtopologies.Thefirstidentifiesaspanningtreeonanunderlyingtopology;thesecondidentifiessecurelinks,makinguseoftheabilitytoidentifyaspanningtree.

TheexamplesassumetheexistenceofafunctionNextHop(topology,node)thatreturnstheappropriatelinkonagiventopologytoagivendestinationnode.Weas-sumethefunctionreturnsNullatthedestination.TheexamplesalsouseafunctionGetNodeIDthatreturnsthenodeidentifierattribute.

A.Pathinformationretrieval

1403625(a)Firstiteration

1403625(b)Seconditeration

Fig.2.Leastbandwidthfindingonpath0-1-4-6

Asafirstexample,considertheproblemoffindingtheleastavailablebandwidthalongthepathfromNode0toNode6inFigure2(a).TheproblemcanbesolvedwithanIGCScompu-tationwithtwoiterations.Duringthefirstiteration,theIGCScomputationisdispersedalongthepath0-1-4-6asshowninFig-ure2(a).Figure2(b)showsmessageflowintheseconditeration,inwhichtheleastavailablebandwidthinformationiscalculatedandreturnedtothesource.

TheIGCSmessageforthecomputationisshowninFig-ure3(a).Inadditiontotherequiredkeys,thismessagealsospecifiesthenumberofiterations,theinitialgatherset,thecom-putefunctionsforthetwoiterations,andthesourceanddestina-tionnodesforthepath.ThoughtheIGCScomputationexecutesfortwoiterations,themessagedoesnotspecify0,1,and1.

Instead,theyaredeterminedduringthecomputephaseofthefirstiteration.

Thefirstcomputephase,showninFigure3(b),accomplishestwotasks.First,itdistributestheIGCScomputationonthepathbyupdatingtheoriginalmessagetoreflecttheproper

andthenspecifyingascattertothenextnodeinthepathtodstNode.Second,thecomputephasedeterminesthegatherandscattersetsforthenextiteration.Theseconditerationwillproceedfromthedestinationbacktothesourcealongthereversepath,thusthegathersetfortheseconditerationisexactlythescattersetforthefirstiteration.Thescattersetfortheseconditerationisthelinkonwhichtheinitialmessagearrived.(WedeterminethisusingtheNexthopfunctionandassumingsym-metricpaths.)Notethatatthedestination,1willbeNull,thusthegatherphaseofiteration1atthedestinationwill(trivially)completeassoonasiteration0isdone.

Duringthesecondcomputephase,theinformationgath-eredfromdownstreamlinksissynthesizedinthefunctioncal-min-bw,showninFigure3(c).Thelocallinkattributesareusedinthisfunction,alongwiththegatheredresultsstoredin

,tofindtheleastavailablebandwidthsofaralongthepathfromthecurrentnodetothedestination.Thisresultisstoredasa

(bw,least-value)pairinmessage

andsenttotheprevioushoponthepathinthesecondscatterphase.

Key

UniqueID

T

Null

0

cal-min-bw

Node6

(a)IGCSMessage

fwd-sig:

GetNodeId()min

(c)Codefor1

Fig.3.IGCScomputationforretrievingpathproperty

Extensions

ThesameIGCScomputationcanbeusedtocalculatetheminimumavailablebandwidthalongamulticasttree.Consider

thatnodes0,3,5and6arecurrentlyparticipatinginamulticastgroupwithaddressgrAddr.AssumethatNode0isasourceinterestedinfindingtheminimumbandwidthalongthemulticasttree.WecaneasilysolvetheproblembyinstantiatingthesameIGCScomputationwithgrAddrasdstNode.

ThecurrentIGCScomputationcanbeeasilymodifiedtosolvethemulticastrepairserverproblemdiscussedintheintroduction.Thisisachievedbyprovidinganewfunctionfor1.Insteadofgatheringminimumbandwidthinformation,thenewfunctioncheckswhetheranyofthedown-streamlinksonthemulticasttreeexperiencepacketlosslargerthanacertainthresholdvalue.Ifthelossrateatanodeexceedsthethreshold,itisaddedtoalistofpossiblerepairlocationsintheIGCSmessage.Whenthecomputationisdone,themulticastsourcenodehasthelistofcandidatesandcandeterminethelocation(s)oftherepairserver(s)baseditspolicy.

Comparisonwithacentralizedalgorithm

WecomparetheaboveIGCScomputationwithacentralizedalgorithminSectionIV-C.Briefly,thecentralizedalgorithmrequiresmoretime,sinceitmustqueryeachnodeaboutthenexthop,andresultsingreatermessagetraffic.Wequantifytheseeffectswhenwecompareimplementationsofbothschemes.B.Buildingaspanningtree

First IGCS messageOther messages 1403625(a)Firstiteration

1403625(b)Seconditeration

Fig.4.Buildingaspanningtree

Asthesecondexample,weconsidertheproblemofbuildingaspanningtreetopologyoveranetwork.Aspanningtreeisusefulforavarietyofqueriesthatrequirenetwork-wideinformation.Wewillshowinthenextexamplehowthespanningtreeisusedwhilebuildingasecuresub-topologyoverabasetopology.Wesolvetheproblemwithatwo-iterationIGCScomputationthatisbasedonconstrainedflooding[3].Duringthefirstiter-

ation,theIGCScomputationisfloodedovertheentirenetworkasinFigure4(a).Onlythefirstsignalingmessagereceivedatanodeinitiatesanewnode-levelcomputation.Ateachnode,thesignalingmessageisfloodedontoallthelinksexcepttheonewherethefirstmessagereceived.Thelinkwherethefirstmes-sagewasreceiveddefinesaparent-childrelationshipandformsaspanningtreeonthenetwork.Duringtheseconditeration,inFigure4(b),thelocalspanningtreeinformationiscombinedwiththeinformationreceivedfromchildnodesandthenforwardedalongthespanningtreetowardsthesource.

TheinitialIGCSmessageforthecomputationisshowninFigure5(a).Itincludesatreekeythatisusedtoreturnthespanningtreeduringtheseconditeration.ThecomputationforthefirstiterationisshowninFigure5(b).Duringthefirstiteration,wefloodtheIGCSmessagebysetting0tobeallthelinksexceptthelinkfromwhichtheIGCSmessagehasbeenreceived.Notethatbecauseeachnodeexecutesthefirstiterationexactlyonce,thefloodingwillautomaticallyterminatewithoutlooping.Asinthepreviousexample,1issettoallthelinksof0,and1istheprevioushopfortheinitialmessage.Theseconditerationgathersthesub-treeinformationfromthechildnodeandbuildsupanewsub-treethatincludesthelocalnode.Thecomputationfor1isshowninFigure5(c).

Key

UniqueID

TNull

0

build-sub-tree

GetNodeId()1NextHop(

)

0Σ

1

1

0

(b)Codefor

0

build-sub-tree:

thencombinesallthelocaltopologyinformationandbuildsaspanningtreeusingaspanningtreefindingalgorithmsuchasDijkstra’s.Assumethatthenetworkhasnodesandlinks.Thetotalnumberofmessagesexchangedinthecentralizedal-gorithmis21.FortheIGCScomputation,twomessagesareexchangedalongeachlinkinthespanningtree.Otherlinkscarryonemessage.Thosetwoapproachesresultinthesamenumberofmessagesiftheunderlyingnetworkisatreetopology.Asincreases,theIGCScomputationresultsinmoremessageexchanges.However,themaximumnumberofmessageex-changedperlinkistwo.Further,theinitiatingnodeexchangesonly2messagesforoutgoinglinks.Inthecentralizedal-gorithm,however,theinitiatingnodeexchangesall21messages,potentialleadingtomessageimplosion.

C.Identifyingasecuretopology

secure linkinsecure link130524(a)Basetopology

secure link13054(b)Inducedsecuretopology

Fig.6.Property-basedtopologyidentification

Thefinalexampleistoidentifyanewtopology,whichconsistsofonlysecurelinks,fromabasetopology.InFigure6(a),thetopologycontainsbothsecureandinsecurelinks.TheproblemistobuildanewtopologythatconsistsofonlysecurelinksasinFigure6(b).

Atwo-iterationIGCScomputationwillsolvethisproblem,ifweassumeaspanningtreeSThasalreadybeencomputed.Thepreviousexampleshowshowthiscanbedone.ThefirstiterationdispersestheIGCScomputationonthespanningtreeST.Theseconditerationretrieveslocalsecurelinkinformationandalsogathersthesecurelinkinformationfromthechildnodes.

Thesetofsecurelinksarescatteredtotheparentnodeinthespanningtree.Whenthecomputationisdone,therootnodehasthecompletesetofsecurelinksandcaninstantiatethesecuretopology.

Figure7showstheIGCSmessageandthecomputationsfor0and1.NotethatweassumethattheGetChildLinkandtheGetParentLinkfunctionsaregiven.TheGetChildLinkfunctionidentifiesthelinkstothechildrenofthelocalnodeonthegivenspanningtreeST.GetParentLinkidentifiesthelinktotheparent.

Forcomparisonwithacentralizedalgorithm,thetopologyidentificationproblemissimilartothespanningtreeproblem.TheIGCScomputationwouldhaveanadditionaladvantageifadistributedtopologyinstantiationschemewereinplace,sincethiswouldallowIGCStoavoidcollectingthetopologyinfor-mationinacentrallocation.Distributedtopologyinstantiationisanareaforfuturework.

Key

UniqueID

T

Null

0

build-sub-topo

ST

(a)IGCSMessage

fwd-sig-st:

GetNodeId()

.

=

,

1

,

(c)Codefor

1

Fig.7.IGCScomputationforbuildingsecuretopology

IV.IGCSSYSTEMIMPLEMENTATION

WehaveimplementedIGCSwithintheCANEsexecutionenvironmentontopoftheBowmanNodeOS[4].Thissectionprovidesanoverviewoftheimplementationandtheresultsofaperformanceexperiment.

A.CANEsandBowman

CANEsisanexecutionenvironmentthatprovidesacompos-ableactivenetworkingenvironment.CompositioninCANEsisachievedintwosteps.First,theuserselectsanunderlyingpro-gram.Theunderlyingprogramexportsoneormoreprocessingslotsthatidentifythespecificpointswhereinjectedprogramsareboundandexecuted.Userscanselectorprovideasetofinjectedprogramsthatcanbeusedtocustomizetheunderlyingprogram.AllIGCScomputationssharethesameunderlyingprogram(describedbelow)thatcontainsonlyoneslotforthecomputephase.

BowmanisaNodeOSforactivenetworks.Bowmanpro-videsthreekeyresourceabstractions:channelsthatarecom-municationend-points,a-flowsthataretheprimaryabstractionsforcomputation,andstate-storethatprovidesamechanismfora-flowstostoreandretrievestate.Thea-flowsareusedtoim-plementtheIGCSnode-levelcomputations;channelsprovideacommunicationmechanismthroughwhichtheIGCSnode-levelcomputationscanexchangemessages.TheBowmanalsopro-videsanefficientpacketclassificationmechanismusedtospecifythegatherandscattersets.

Bowman a−flownewnode-levelcomputationusingaBowmana-flow.Figure8showsatypicalsnapshotoftheIGCSsystem.TheIGCSdaemononNodeAreceivesasignalingmessagefromtheuserandiniti-atesanewnode-levelcomputation.Duringthefirstiteration,thenode-levelcomputationcomputesasetofnodesonwhichthecurrentcomputationshouldbeinitiated(NodesBandCinthisexample)andsendsthesignalingmessagetothenodes.Uponreceivingthesignalingmessage,thedaemonsonnodesBandCperformthesameoperationsandspreadoutthecomputation.Duringtheprocessing,theunderlyingandcomputeslotpro-gramsareloadedontothelocalnodeviaBowmancodeloadingmechanism.Thecomputeslotprogramsareboundtothepropercomputephases.Thedatapartofthesignalingmessageisstoredintothelocalstate-storesothattheinformationcanberetrievedbytheIGCScomputation.

IGCSunderlyingprogram:TheunderlyingprogramprovidesthecomputationframeworkforoneormoreiterationsoftheGather-Compute-Scattercycle.Theunderlyingprogramgathersasetofmessagesthroughthechannelsspecifiedinthecurrentgatherphase.Thenitexecutesthecomputeslotprogramofthecurrentiteration.Inthescatterphase,itsendsoutthemessagesthroughthechannelsspecifiedinthecurrentscatterphase.Figure11intheAppendixshowsthemainbodyoftheIGCSunderlyingprogram.Ateachiteration,theunderlyingprogramgathersmessagesbysubscribingtothedatapacketswithitsowncomputationidonthegatherchannels.Aftergatheringallthemessages,itstoresthemintothelocalstate-storeforfurtherprocessingduringthecomputephase.Next,theunderlyingprogramraisesthecomputeslotprogramwhichisboundtothecurrentiterationofthecomputephase.The“raised”injectedprogramdoesthecomputation-specificprocessingofthecurrentiterationusingthegatheredmessagesandlocalinformation.Italsogeneratesoutgoingmessagesandspecifiesasetofchannelsforthescatterphase.Themessagesaresentoutoverthescatterchannelsduringthescatterphase.

IGCSComputeslotprogram:TheIGCScomputeslotpro-gramdefineseachIGCScomputation.Thecomputeslotpro-gramsareboundtothepropercomputephasesandexecutedduringthespecifiediteration.Theslotprogramscanbespeci-fiedstaticallyinthesignalingmessageordynamicallymodifiedatrun-time.

SincealltheIGCScomputationssharethesameunderlyingprogram,eachIGCScomputationisspecializedthroughthein-jectedprogramsthatareboundtothecomputeslots.TheIGCSsystemprovidesanAPIthroughwhichtheslotprogramscancommunicatewiththeIGCSunderlyingprogramandotherslotprogramsboundtothedifferentiterations.

Figure12intheAppendixshowsaslotprogramfortheIGCSin-bandsignaling.Asintheexample,theIGCSAPIprovidesasetoffunctionstoretrieve/configuregather/scatterphasesandothersharedobjects.ThenumberofiterationsfortheIGCScom-putationandslotprogramsboundtothecomputephasescanalsobemodified“on-the-fly”withincomputeslotprograms.Theca-pabilityofrun-timemodificationallowsdynamicconfigurationoftheIGCScomputations.

Node B IGCSDaemonsignaling message NodeComputation iNode A NodeComputation isignaling message IGCSDaemon NodeComputation jsignaling messageNode C IGCSDaemon NodeComputation iFig.8.IGCSsystemarchitecture

B.IGCSsystemarchitecture

TheIGCSsystemhasthreemajorcomponents:theIGCSdaemon,theIGCSunderlyingprogramandtheIGCScomputeslotprogram.Wedescribeeachinturn.

IGCSdaemon:TheIGCSdaemonisanode-residentprogram,whichisresponsibleforprocessingIGCSsignalingmessages.Uponreceivingasignalingmessage,itparsesthemessageandinitiatesanode-levelcomputationwithapropersetofcodemodulesfortheIGCSunderlyingprogramandcomputeslotprograms.

TheIGCSdaemonisimplementedasanextensionoftheBowmanNodeOS.Uponreceivingthesignalingmessages,thedaemonconfiguresanewIGCScomputationandinitiatesthe

C.Performanceanalysis

QueryReply01234(a)Centralizedalgorithm

Computation flowResult−synthesis flow01234(b)IGCSalgorithm

Fig.9.Findingtheminimumavailablebandwidth

Inthissection,wepresentalimitedsetofIGCSperformanceresults.Wehaveimplementedtwosolutionsforfindingtheminimumavailablebandwidth:acentralizedalgorithmandtheIGCSalgorithmdescribedinSectionIII.Inshort,theIGCSalgorithmspreadsthecomputationalongthepathandeachnode-levelcomputationcomputestheresultandreturnsittowardsthesourcenodeasshowninFigure9(b).Forthecentralizedalgorithm,weassumethatthesenderdoesnotknowallthenodesalongthepath,butonlyknowsitsnext-hopnodetowardsthedestination.Thesendersendsaquerymessagetothisnode.Thenodereplieswithitslocalbandwidthinformationandnext-hopnodetowardsthedestination.Thesenderthensendsaquerymessagetothenext-hopnode,andthenodereplieswithitslocalinformation.Thequery-replyactioncontinuesuntilthesendersendsthelastquerymessagetothedestination,asinFigure9(a).Itisstraightforwardtoshowthattherunningtimeofthecentralizedalgorithmgrowsasthesquareofthelengthofthepath,whiletherunningtimeoftheIGCSalgorithmislinearinthelengthofthepath.Therunningtimeofbothalgorithmsislinearwiththepathdelay,thoughthecoefficientislargerforthecentralizedalgorithm.

TheIGCScomputationperformsin-bandsignalinginthefirstiterationtoinitiateanode-levelcomputationateachnode.Theinitiationofanode-levelcomputationincludescreationofathreadandcodeloadingforunderlyingandinjectedcodes.Thecodesareloadedfromacodeserverthathasalsobeenimple-mentedinBowman.Thefirstcold-startcomputationexperiencesadelayincurredbythecodeloading.However,oncethecodemodulesareloadedandstoredinthecodecacheateachnode,thesubsequentcomputationsthatutilizethecodemodulesdoonlycachelookup,reducingthetimeforthecomputationinitiationsignificantly.Thecold-startoverheadforthemodulesisabout35msec,whilethewarm-startoverheadisonlyabout5msec.Figure10(a)showstherunningtimeofeachalgorithmwithdifferentpathlengthsforalinkdelayof5msec.FortheIGCSalgorithm,weshowbothcold-startandwarm-startresults.TherunningtimeofthecentralizedalgorithmiscomparabletotheIGCSresultsforapathlengthoftwo.Therunningtimeofthecentralizedalgorithm,however,growsmuchfasterthanIGCSas

55005000IGCS warm-start

IGCS cold-startCentralized

45004000)c3500esm( e3000miT gn2500innuR200015001000500

0

2345

Path Length (hops)

67

8910

(a)Effectofpathlength

12000

IGCS warm-start

IGCS cold-startCentralized

10000

8000

)cesm( emiT6000

gninnuR4000

2000

0

1234

Link Delay (msec)

5678910

(b)Effectoflinkdelay

Fig.10.Runningtimewithvaryinglinkdelayandpathlength

thepathlengthincreases.Atapathlengthoffour,thecentralizedalgorithmrequiresnearlytwiceasmuchtimeasIGCS;thegapincreasesquicklywithmorehops.TheIGCScold-startgrowsslightlyfasterthanIGCSwarm-startsince,forthecold-start,thecodeloadingtimeateachnodeisaccumulatedasthelengthofthepathgrows.

Figure10(b)showstherunningtimeofeachalgorithmwithdifferentlinkdelays.Thelengthofthepathisfixedat10hops.Asdiscussed,therunningtimeisalinearfunctionofthelinkdelayforbothalgorithms.Thecentralizedalgorithm,however,

hasahigherconstantmultiplierof

1,comparedto2fortheIGCSalgorithm,whereisthenumberofhops.AlthoughtheIGCScold-startandtheIGCSwarm-startshowthesamerateofgrowth,thecold-starthasslightlymoreoverheadduetoitscodeloadingtime.Figure10(b)confirmsthemeasureddifferenceinoverheadforwarm-startandcold-start.

TheIGCScomputationshowsbetterscalabilityintermsoflinkdelayandpathlength,comparedtothecentralizedalgorithm.Itsrunningtimeisalinearfunctionoflinkdelayandpathlengthwithasmallcoefficientvalue.AlthoughthereisanoverheadofcodeloadingintheIGCScomputation,itisnegligibleforanypathoflengthlargerthanthreehops.

V.RELATEDWORK

Priorworkrelatedtothispapercanbeseparatedintotwobroadcategories:workinthevirtualnetworkcommunityandworkindistributedcomputing.

IGCSisalight-weightdynamic-configurabledistributedsys-tem.However,theIGCSsystemismoresuitabletoacertaintypeofdistributedalgorithmduetoitsiterativegather-compute-scatterstructure.Thereareatleasttwodifferentstylesofdis-tributedalgorithmsthatarenaturallyfitintotheIGCScompu-tationmodel:heartbeatalgorithmsandprobe/echoalgorithms.TheIGCSsystemprovidesadistributedcomputingenvironmentforthosetypesofproblems.

Theheartbeatalgorithmissuitablefortheproblemsintheareaofparalleliterativecomputationssuchasgridcomputation.Asanexample,considertheproblemofcomputingthetopologyofanetwork.Adistributedalgorithmwithheartbeatparadigm[5]worksasfollows:Eachprocessexecutesasequenceofiterations.Oneachiteration,processesexchangetheirlocalknowledgeofthetopologywiththeirneighborsandbuildtheirownlocaltopologyinformationusingtheexchangedinformation.Astheiterationscomplete,eachprocessgraduallyconvergesonthecompletetopology.Thecomputationterminateswhenalltheprocesseshavelearnedthecompletetopology.Thistypeofalgorithmiscalledaheartbeatalgorithmsincetheactionsofeachprocessarelikethebeatingofaheat:firstexpand,sendinginformationout;thencontract,gatheringnewinformationin.Theprobe/echoalgorithmissuitablefordistributedcomputa-tionsthatexploreovergraphs.Aprobeisaquerysentbyonenodetoitssuccessor;anechoisasubsequentreplytothequery.Forthesameproblemoftopologydiscoveryexplainedabove,theprobe/echoalgorithmworksasfollows[5]:Theinitiatorsendsouttheprobemessagetoitsallneighbors.Afterreceivingaprobe,anodesendsittoallitsneighborsexceptthenodefromwhichitreceivestheprobe,andwaitsforanechofromeach.Tobreakthepossibledeadlocksituation,ifanodereceivesthemul-tiplesameprobes,itimmediatelysendsanechocontaininganulltopology.Eventually,anodewillreceiveanechoinresponsetoeveryprobeitsends.Atthispoint,itechoestheunionofitsneighborsetandtheechoesitreceives.Intheprobe/echoalgo-rithm,onlytheinitiatorgetsthecompletetopologyinformationunliketheheartbeatalgorithm.Forcomputationsthatdissem-inateorgatherinformationongraphs,probe/echoalgorithmsaremoreefficientthatheartbeatalgorithms[5].Incontrast,theheartbeatalgorithmsareappropriateandnecessaryformanyparalleliterativealgorithmsinwhichnodesneedtoexchangeinformationuntiltheyconvergeonananswer.

Inthevirtualnetworkcommunity,theNetScriptactivenet-workingprojectatColumbiaUniversityaddressesthedeploy-mentofvirtualnetworks:inparticular,asNetScriptVirtualNetworks(VANs)[6].TheNetScripteffortfocusesonacom-monrouterprogramminglanguage,andtheirworkdescribesthegeneralnotionofcoordinateddeploymentandmanagement.TheVANarchitectureabstractsunderlyingnetworkedresourcesandconnectivityintoasingleend-to-endprogrammablenetworktosupportuniformdeployment,configurationmanagement,se-curity,andend-to-endresourcemanagement.ThemajorgoalofVANs,therefore,istoprovideanabstractionofnetworkre-sourcesthatcanbeprogrammedandmanagedasasingleobject.

TheVANsarchitecturelackstheabilityofprovidingcustomizedvirtualconnectivityandinterestingtopology.

TheX-Bone[7]isageneralizedoverlaymanagementsystem.Itsarchitectureconsistsofoverlaymanager,resourcedaemons,andamulticastcontrolprotocol.TheX-Bonedirectorytool,xd,incorporatesaninterfaceandaresourcediscoveryprotocol,adaptedfromthesdandsdrM-Bonetools.TheX-Bonealsoservesasaframeworktocoordinateandmanageothernewmechanisms(e.g.multi-protocollabelswitching)withinoverlaynetworks.AvisionfortheX-boneisthatitcouldbeusedtoautomaticallycreatevirtualtopologiesthathavecertain(graph-theoretic)properties,e.g.mapaeightnodecycletoacertainphysicaltopologysuchthattheoveralllatencyisminimized.Inthispaper,wehavedevelopedtheIGCScomputationmodelthatgeneralizesthecreationofsuchmappings.

Supranet[8]providesatoolkitthatcanbeusedatdifferentlevels,thusaccommodatingtheneedsofbeginner,intermediate,andexpertcreators.Thetoolkitincorporatescreatingatopology,generatingaroutingtableanddefiningsecurityrequirementoverthetopology.Itfocusesonoptimizingthetopologyandresourcesofthevirtualnetworktothephysicalnetwork.Itsoptimization,however,isstaticinasensethatitoccursonlyatthecreationtimeofthesupranetsandusesafixedsetofalgorithms.Forexample,thetoolkitautomaticallycreatesappropriateroutingtablesthatreflectthecreator’sdecisionaboutthetopologyandtheroutingtablesneverchangeduringthewholesupranetlifetime.Ourdesignismoregeneralanddynamic.AnIGCScomputationisgeneralenoughtoidentifyawidevarietyofcustomizedtopolo-giesandtheindentifiedtopologiescanbedynamicallymanagedbysubsequentIGCScomputations.

VI.CONCLUSIONS

Increasingly,situationsariseinwhichitisdesirabletoquerynetworkstate,identifynetworklocationsandinstantiatevirtualtopologies.TheblackboxinterfacetonetworktopologythatiscurrentlyprovidedbyIPmakesthisdifficultorimpossible.Activenetworking,ontheotherhand,providesaprogrammableinterfacetonetworkingresources,andthusthepossibilityofexposingsomeoftheinternalsoftheblackbox.Wehaveusedactivenetworkingtoprovideaprogrammablemechanismtoidentifytopologicalentitiesandprotocolstoinstantiatethoseentitiesintoavirtualtopology.

Wehavenotaddressedseveralkeyissuesrelatedtothequery-ingofnetworkstateandtheinstantiationofmultiplevirtualtopologies.Specifically,thispaperdoesnotconsiderresourcemanagementacrossvirtualtopologies(norwithinavirtualtopol-ogy).Someformofadmissioncontrolforvirtualtopologiesmaybenecessary,dependingupontheresourceguaranteesthataredesired.Wehavealsoneglectedthevariousissuesofsecurity,includingaccesscontrolfornodeandlinkstateandauthorizationtocreatevirtualtopologies.Resourcemanagementandsecurityarebothissuesofimportanceforactivenetworks(withorwith-outvirtualtopologies),andweexpectthatsolutionsdevelopedbytheactivenetworkscommunitywillbeapplicabletovirtualnetworks.

REFERENCES

[1]“ActiveErrorRecovery(AER):Areliablemulticastimplementationutiliz-ingActiveNetworkservices,”http://www.tascnets.com/panama/AER/.

[2]IETFIPSecurityWorkingGroup,“IPSecurityProtocol,”WorkinProgress.[3]A.Segall,“DistributedNetworkProtocols,”Trans.onInformationTheory,

vol.29,no.1,pp.23–35,Jan1983.

[4]S.Merugu,S.Bhattacharjee,E.Zegura,andK.Calvert,“Bowman:ANode

OSforActiveNetworks,”ToappearinInfocom2000.

[5]GregoryR.Andrews,“ParadigmforProcessInteractioninDistributed

Programs,”ACMComputingSurveys,vol.23,no.1,pp.49–90,March1991.

[6]Y.YeminiandS.daSilva,“TowardsProgrammableNetworks,”in

IFIP/IEEEInternationalWorkshoponDistributedSystems:OperationsandManagement,L’Aquila,Italy,Oct.1996.

[7]JoeTouchandSteveHotz,“TheX-BONE,”inThirdGlobalInternetMini-ConferenceinconjunctionwithGlobecom’98,Sydney,Australia,Nov.8-121998.

[8]L.DelgrossiandD.Ferrari,“AVirtualNetworkServiceforIntegrated-ServicesInternetworks,”in7thInternationalWorkshoponNetworkandOperatingSystemSupportforDigitalAudioandVideo,St.Louis(Missouri),May1997.

APPENDIX:IGCSUNDERLYINGANDINJECTEDPROGRAMS

u_inti;

igcs_io_t*tmp_io;

igcs_msg_table_t*cur_in;

for(i=0;i/*GatherPhase*/

igcs_get_gather(i,tmp_io);/*getchannelsforgatherphase*/if(tmp_io->num_ch!=0){

igcs_install_gather_filter(tmp_io);/*Installgatherfilter*/cur_in=igcs_gather_msg(tmp_io);/*getincomingmessages*/c_Ep(inMsg)=cur_in;/*assigninputmessages*/igcs_uninstall_gather_filter(tmp_io);/*Uninstallgatherfilter*/}

/*ComputePhase*/

igcs_raise_slot(Compute);

/*executethecomputeslot*/

/*ScatterPhase*/

igcs_get_scatter(i,tmp_io);/*getchannelsforscatterphase*/igcs_scatter_msg(c_Ep(outMsg),tmp_io);/*scattermessages*/}

Fig.11.IGCSUnderlyingProgram

igcs_msg_t*tmp_msg;igcs_io_ttmp_io;inti;

memcpy(tmp_msg,/*getsignalingmessage*/

(igcs_msg_t*)igcs_get_sigmsg(),tmp_sig->len);i=igcs_next_hop(tmp_msg->src_id);/*setscatterphaseof*/tmp_io.num_ch=1;/*theseconditeration*/tmp_io.ch[0]=i;

igcs_set_scatter(1,&tmp_io);

igcs_get_all_vn_channel(&tmp_io);/*setscatterphaseof*/_igcs_get_diff_channel(&tmp_io,i);/*thefirstiteration*/igcs_set_scatter(0,&tmp_io);igcs_set_gather(1,&tmp_io);/*setgatherphaseof1stiter*/tmp_msg->src_id=net_utils_local_ip_number();tmp_msg->type=IGCS_SIG;c_Ip(outMsg)=tmp_msg;/*setoutputmessage*/

Fig.12.IGCSInjectedProgramExample