En förbindelse mellan två anslutna system kan vara en typkundleverantör när det ena anslutna systemet är en leverantör av det andra anslutna systemet, eller av typen peer-peer, om de är peering AS. Detta kommersiella förhållande framkallar en global hierarkisk struktur som är en nyckelingrediens i förmågan att förstå den topologiska strukturen i AS-anslutningskurvan. Tyvärr är det mycket svårt att samla in uppgifter om den faktiska typen av samband mellan anslutna system, och i allmänhet är denna information inte en del av de insamlade AS-anslutningsdata. Typen av relation (TOR) problem försöker ta itu med denna brist, genom att dra slutsatsen vilken typ av relation mellan anslutna AS baserat på deras routing politik. De strategier som presenterats hittills är emellertid lokala till sin natur och fångar inte upp den globala hierarkiska strukturen. I detta arbete definierar vi ett nytt sätt att härleda denna typ av relation från insamlade data, med beaktande av både lokal politik och globala hierarkiska begränsningar. Vi definierar det acykliska typ av relation AToR-problemet som fångar upp denna globala hierarki och presenterar en effektiv algoritm som gör det möjligt att avgöra om det finns ett hierarkiskt uppdrag utan ogiltiga vägar. Vi visar sedan att den relaterade allmänna optimeringsproblem är NP-komplett och presentera en 2 3 approximation algoritm där den objektiva funktionen är att minimera det totala antalet lokala policy missmatchningar. Vi stöder vår strategi genom omfattande experiment och simuleringsresultat som visar att våra algoritmer klassificerar typen av relation mellan ASes mycket bättre än alla tidigare algoritmer.
I REF definieras det acykliska type of Relation (ATor) problemet.
Acyclic Type of Relationships Between Autonomous Systems
{'venue': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}