The Internet is a huge and complex network in which Internet Service Providers (ISPs) compete for revenue. In order to support the establishment of commercial agreements, routing in the Internet must therefore allow each ISP to autonomously set up its own routing policies while ensuring global connectivity. The Border Gateway Protocol (BGP) allows to achieve both these goals, and is the currently adopted protocol for Internet routing. It can be shown that the interaction of not-so-unlikely BGP configurations adopted at different ISPs can cause permanent oscillations of routing. Several models and algorithms have been proposed in the literature to study routing oscillations. The goal of this paper is to provide a survey of state of the art contributions in this field with an emphasis on the algorithmic aspects. -
Cittadini, L., DI BATTISTA, G., Rimondini, M. (2008). (Un)-Stable Routing in the Internet: A Survey from the Algorithmic Perspective (Invited Lecture). In Graph-Theoretic Concepts in Computer Science 34th International Workshop, WG 2008, Durham, UK, June 30 – July 2, 2008. Revised Papers (pp.1-13). Berlin, Heidelberg : Springer-Verlag [10.1007/978-3-540-92248-3_1].
(Un)-Stable Routing in the Internet: A Survey from the Algorithmic Perspective (Invited Lecture)
CITTADINI, LUCA;DI BATTISTA, Giuseppe;RIMONDINI, Massimo
2008-01-01
Abstract
The Internet is a huge and complex network in which Internet Service Providers (ISPs) compete for revenue. In order to support the establishment of commercial agreements, routing in the Internet must therefore allow each ISP to autonomously set up its own routing policies while ensuring global connectivity. The Border Gateway Protocol (BGP) allows to achieve both these goals, and is the currently adopted protocol for Internet routing. It can be shown that the interaction of not-so-unlikely BGP configurations adopted at different ISPs can cause permanent oscillations of routing. Several models and algorithms have been proposed in the literature to study routing oscillations. The goal of this paper is to provide a survey of state of the art contributions in this field with an emphasis on the algorithmic aspects. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
