Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/631FE9B5-F20B-45E0-97DE-EDAEC2B79715 | - |
| Identifier | http://ieeexplore.ieee.org/abstract/document/4268087/ | - |
| Identifier | https://doi.org/10.1109/COMSWA.2007.382444 | - |
| Language | en | - |
| Extent | 12 pages | en |
| Title | On configuring BGP route reflectors | en |
| Creator | Breitbart, Y | en |
| Creator | Gupta Anupam | en |
| Creator | Kumar Amit | en |
| Creator | Rastogi Rajeev | en |
| Creator | Garofalakis Minos | en |
| Creator | Γαροφαλακης Μινως | el |
| Publisher | Institute of Electrical and Electronics Engineers | en |
| Content Summary | 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. | en |
| Type of Item | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Type of Item | Conference Full Paper | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2015-11-30 | - |
| Date of Publication | 2007 | - |
| Subject | Autonomous systems | en |
| Subject | Algorithms | en |
| 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 | en |
Copyright © DIAS 2013
