Vi anser att kompakta routingsystem i nät med låg dubbleringsdimension, där dubbleringsdimensionen är det minsta värdet α så att varje boll i nätet kan täckas med högst 2 α bollar med halvradie. Det finns två varianter av routing-system design: i) märkt (namnberoende) routing, där designern får byta namn på noderna så att namnen (märkena) kan innehålla ytterligare routing information, t.ex. topologisk information, och ii) namn-oberoende routing, som fungerar ovanpå de godtyckliga ursprungliga nodnamnen i nätverket, dvs. nodnamnen är oberoende av routing systemet. I den här artikeln presenterar vi -a (1+ ) stretchade kompakta routingschema med log n -bit routing etiketter, O(log 2 n/ loglog n)-pakethuvuden, och ( (1 ) O(α) log 3 n)-bit routing information vid varje nod; -a (9 + )- stretch namn-oberoende kompakt routing schema med O(log 2 n/ loglog n)-bit pakethuvuden, och ( 1 ) O(α) log 3 n)-bit routing information vid varje nod. Dessutom visar vi en lägre gräns: alla namn-oberoende routing schema med o(n ( /60) 2 ) bitar av lagring vid varje nod har stretch inte mindre än 9− för någon  till (0, 8). Därför uppnår vårt namnoberoende routingsystem asymptotiskt optimal stretch med polylogaritmisk lagring vid varje nod och pakethuvud. Observera att båda systemen är skalfria i den meningen att deras rymdbehov inte beror på nätets normaliserade diameter. Vi presenterar också en enklare nonscale-free (9 + )- stretch namnoberoende kompakt routing system med förbättrade utrymmeskrav om är polynomial i n.
Konjevod, Richa och Xia REF presenterar ett kompakt routingsystem för nätverk med låg dubbleringsdimension som också använder Thorup- och Zwick-systemet för träd, där etiketterna har log n-bitar.
Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}