Brief announcement A space lower bound for name-independent compact routing in trees

Given a rooted n-node tree with arbitrary positive edge weights, and arbitrary node names, what is the minimum space that a single-source fixed-port name-independent compact routing algorithm needs in its largest routing table while achieving stretch 3? We

BriefAnnouncement:ASpaceLowerBoundforName-IndependentCompactRoutinginTrees

ComputerScienceKo Department,ing

TuftsUniversity,

Medford,MA02155.

laing@cs.tufts.edu

CategoriesandSubjectDescriptors:G.2.2[DiscreteMathematics]:GraphTheory—PathandCircuitProb-lems,NetworkProblems,Trees,Graphlabeling.

GeneralTerms:Algorithms,Performance,Theory.

Keywords:CompactRouting,Trees,SpaceComplexity.Givenarootedn-nodetreewitharbitrarypositiveedgeweights,andarbitrarynodenames,whatistheminimumspacethatasingle-source xed-portname-independentcom-pactroutingalgorithmneedsinitslargestroutingtablewhileachievingstretch3?Weshowthatthespacerequire-mentis (

√n)bits.

Let[n]={1,...,n}.Foreachn,wede neafamilyofweightedtreeswhicharestarsonn+1nodesparametrizedbyapermutationp:[n]→[n]mappingdestinationstoportnumbers.LetTn={TpeachTp=(V,E),withV|p=is{0a}permutationS

[n]andEon={[(0n],}i)where|i∈[n]}andletpmapeverydestinationdtoitsportnumberp(d).Clearly|Tnportnumberibe|=w(ni)!.=Now1+leti (wheretheweight0<of <the1

edgewithnlognbitsinanyleafnode(c∈Ncon-stant),forsu cientlylargen.Weshowthatscheme,therootnodeisconstrainedtouse (

√foranysuchCollegeofRajmohanComputerandRajaramanInformationScience,NortheasternUniversity,Boston,MA02115.

rraj@ccs.neu.edu

n(otherwiseitissoft).Wethencountthe

numberLofdistinctp requiredoverTnforhandlingjustthehardpermutations.L isclearlyalowerboundforL.InordertodetermineL ,we ndanupperboundMforthemaximumnumberofdi erenthardpermutationsthatasinglechoiceofp couldpossiblyhandle.WealsodeterminealowerboundNforthenumberofhardpermutationsand nallyconcludethatN/M≤L <L.

First,givenA,wederiveacompressionalgorithmpermutationsby (

√CAforsigni cantlycompressingsoftn)

).Finallya

combinatorialargumentleadstothefollowinglemma:Lemma0.2.AnupperboundonthemaximumnumberofhardpermutationsthatasinglepremappingfunctioncanhandleisgivenM=(n √bythefollowingexpressionn/c¯ 2

i=0(n √(c¯=8c):

n).Withtheselemmaswecomplete√theproofofTheorem0.1byprovingthatlog2(N/M)is (

n)

insomenode,intheworstcase.

Weremarkthatourresultdoesnotmakeanyassump-tionsontheheadersizesofthepackets,exceptthatthe rstheaderofeachpacketasitentersthenetworkisonlylognbitstouniquelyindicateadestinationnodein[n].Thus,ourlowerboundonspaceispurelyduetotheroutingcon-straintsandappliesforarbitraryheadersizes.

1.REFERENCES

[1]I.improvedAbraham,C.Int’munication-spaceGavoille,putingtrade-o .Malkhi.Routing(DISC)In,Proc.with

Oct2004.18th[2]P.FraigniaudandC.Gavoille.Aspacelowerboundfor

routingintrees.In19thSTACS.LNCS-Springer,2002.[3]C.schemesGavoilleandM.Gengler.Space-e ciencypages162–175,ofstretchJulyfactor1997.

three.In4th(SIROCCO)ofrouting

,[4]plexityLiandP.andVitanyi.itsApplicationsAnIntroduction.Springer-Verlag,toKolmogorov

1997.[5]M.oracles.ThorupIn33rdandU.ACMZwick.STOCApproximate,pages183–192,distance

2001.

本文来源：https://www.bwwdw.com/article/w4y4.html