Abstract-Det är viktigt i kommunikationsnät att använda rutter som är så korta som möjligt (dvs. har låg stretch) medan routing tabeller små. Nya framsteg inom kompakt routing visar att en sträcka på 3 kan uppnås samtidigt som en sublineär (i storleken på nätverket) utrymme vid varje nod [14]. Det är också känt att ingen routing system kan uppnå sträcka mindre än 3 med sub-linjärt utrymme för godtyckliga nätverk. Däremot har simuleringar på verkliga nätverk visat att stretch mindre än 3 faktiskt kan erhållas med hjälp av sublinjära stora routingtabeller [6]. I det här dokumentet undersöker vi ytterligare avräkningar mellan mellanslag för kompakt routing genom att analysera en specifik klass av grafer och genom att presentera en effektiv algoritm som (ungefär) finner den optimala avskrivningen mellan mellanslag för varje givet nätverk. Vi studerar först en populär modell av slumpmässiga grafer, kända som Bernoulli slumpmässiga grafer eller Erdős-Renyi grafer, och visar att stretch mindre än 3 kan erhållas i samband med sublinjära routing tabeller. I synnerhet kan stretch 2 erhållas med hjälp av routing tabeller som växer ungefär som n 3/4 där n är antalet noder i nätverket. Kompakta routingsystem inbegriper ofta val av landmärken. Vi presenterar en enkel girig plan för landmärke val som tar en önskad stretch s och en budget L på antalet landmärken som indata, och producerar en uppsättning av som mest O (L log n) landmärken som uppnår stretch s. Vårt program producerar routing tabeller som inte använder mer än O (log n) mer utrymme än det optimala systemet för att uppnå stretchs med L landmärken. Detta kan vara ett värdefullt verktyg för att uppnå nära optimal stretch-space kompromisser för specifika grafer. Vi simulerar detta giriga schema (och andra heuristiker) på flera klasser av slumpmässiga grafer samt på Internet som grafer.
Enachescu m.fl. REF presenterade ett kompakt routingsystem som uppnår stretch 2 genom att använda mellanslag O(n 1,75 ) på Erdős-Renyi grafer.
Reducing Maximum Stretch in Compact Routing
{'venue': 'IEEE INFOCOM 2008 - The 27th Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2008 - The 27th Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}