I detta dokument presenteras och utvärderas experimentellt en ny algoritm för effektiv en-hop länk-state routing i full-mesh nätverk. Tidigare tekniker för denna inställning skala dåligt, som varje nod ådrar sig quadratic (n 2 ) kommunikation overhead för att sända sin länk tillstånd till alla andra noder. Däremot, i vår algoritm utbyter varje nod routing tillstånd med endast en liten delmängd av overlay noder bestäms med hjälp av ett beslutförhetssystem. Med hjälp av två runda protokoll, kan varje nod hitta en optimal one-hop väg till någon annan nod med endast n 1.5 pernode kommunikation. Vår algoritm kan också användas för att hitta den optimala kortaste vägen av godtycklig längd med endast n 1.5 log n pernode kommunikation. Algoritmen är utformad för att vara motståndskraftig mot både nod- och länkfel. Vi tillämpar denna algoritm på ett Resilient Overlay Network (RON) system, och utvärdera resultaten med hjälp av en storskalig, globalt distribuerad uppsättning av Internet värdar. Den minskade kommunikation overhead från att använda vår förbättrade full-mesh algoritm gör det möjligt att skapa alla-par routing overlays som skala till hundratals noder, utan att minska systemets förmåga att snabbt hitta optimala rutter.
Sontag m.fl. REF föreslog ett protokoll som gör det möjligt för varje nod att hitta en optimal one-hop väg till någon annan nod med en kommunikation overhead O(n 1.5 ).
Scaling all-pairs overlay routing
{'venue': "CoNEXT '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}