Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/631FE9B5-F20B-45E0-97DE-EDAEC2B79715 | ||
| Year | 2007 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | Y. Breitbart, M. Garofalakis, A. Gupta, A. Kumar and R. Rastogi, "On configuring BGP route reflectors", in 2nd Internationa Conference on Communication Systems Software and Middleware, 2007. doi: 10.1109/COMSWA.2007.382444 https://doi.org/10.1109/COMSWA.2007.382444 | ||
| Appears in Collections |
The Border Gateway Protocol (BGP) is the standard protocol for exchanging routing information between border routers of Autonomous Systems (ASes) in today’s Internet. Within an AS, border routers exchange externally-learned BGP route advertisements via Internal- BGP (I-BGP) peerings. Naive solutions for these I-BGP peering sessions (e.g., based on full-mesh topologies) simply cannot scale to the sizes of modern AS networks. Carefully designed route-reflector configurations can drastically reduce the total number and connection cost of the required I-BGP sessions. Nevertheless, no principled algorithmic approaches exist for designing such configurations, and current practice relies on manual reflector selection using simple, ad-hoc rules. In this paper, we address the novel and challenging optimization problems involved in designing effective BGP route-reflector configurations for AS networks. More specifically, we consider the problems of selecting route reflectors in an AS topology to minimize: (1) the total connection cost of all I-BGP peering sessions, and (2) the average distance traversed by route advertisements within the AS. We present NP-hardness results that establish the intractability of these problems, and propose several polynomial-time approximation algorithms (based on LP-rounding and combinatorial techniques) with guaranteed (constant-factor or logarithmic) bounds on the quality of the approximate solution. Our simulation results validate our approach, demonstrating the effectiveness of our configuration algorithms over a wide range of network topologies.
Copyright © DIAS 2013
