Abstract-Dynamic routing protokoll såsom RIP och OSPF i huvudsak genomföra distribuerade algoritmer för att lösa de kortaste vägar problem. Gränsportprotokollet (BGP) är för närvarande det enda interdomain routingprotokollet som används på Internet. BGP löser inte ett kortaste problem eftersom det krävs ett interdomänprotokoll för att tillåta policybaserade mätvärden att överskrida avståndsbaserade mätvärden och göra det möjligt för autonoma system att självständigt definiera sin routingpolicy med liten eller ingen global samordning. Det är då naturligt att fråga om BGP kan ses som en distribuerad algoritm för att lösa några grundläggande problem. Vi introducerar problemet med stabila vägar och visar att BGP kan ses som en distribuerad algoritm för att lösa detta problem. Till skillnad från en kortaste stig träd, en sådan lösning representerar inte en global optimal, utan snarare en jämviktspunkt där varje nod tilldelas sin lokala optimal. Vi studerar problemet med stabila vägar med hjälp av en härledd struktur som kallas ett tvistehjul, som representerar motstridiga routingstrategier vid olika noder. Vi visar att om inget tvisthjul kan konstrueras så finns det en unik lösning på problemet med stabila vägar. Vi definierar det enkla vektorprotokollet (SPVP), en distribuerad algoritm för att lösa problemet med stabila vägar. SPVP är avsett att fånga det dynamiska beteendet hos BGP på en abstrakt nivå. Om SPVP konvergerar motsvarar det resulterande tillståndet en stabil väglösning. Om det inte finns någon lösning, då SPVP alltid skiljer sig. I själva verket kan SPVP även avvika när en lösning finns. Vi visar att SPVP kommer att konvergera till den unika lösningen av en instans av stabila vägar problem om ingen tvist hjul finns.
Griffin och Al.'s seminal arbete modellerade BGP som en distribuerad algoritm för att lösa problemet med stabila vägar, och härledde en teoretisk tillräcklig villkor (dvs "inget tvistehjul") för BGP stabilitet REF.
The stable paths problem and interdomain routing
{'venue': 'TNET', 'journal': None, 'mag_field_of_study': ['Computer Science']}