On constructing correct and scalable iBGP configurations
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38324 |
| _version_ | 1826208072872230912 |
|---|---|
| author | Vutukuru, Mythili |
| author2 | Hari Balakrishnan. |
| author_facet | Hari Balakrishnan. Vutukuru, Mythili |
| author_sort | Vutukuru, Mythili |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T13:59:46Z |
| format | Thesis |
| id | mit-1721.1/38324 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:59:46Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/383242019-04-10T23:45:36Z On constructing correct and scalable iBGP configurations Vutukuru, Mythili Hari Balakrishnan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 51-53). BGP (Border Gateway Protocol), the Internet's current inter-domain routing protocol, has two modes of operation: eBGP (external BGP, used to exchange routing information between autonomous systems (ASes)), and iBGP (internal BGP, used to propagate that information about external destinations to other BGP routers within an AS). Full-mesh iBGP and iBGP with route reflection are the two most common methods of configuring iBGP. Although a full-mesh iBGP guarantees correct and predictable routing, it requires a large number of iBGP sessions-approximately quadratic in the number of BGP routers. Such configurations do not scale well in the number of BGP routers in the AS because of the memory, bandwidth and CPU overhead involved in exchanging routes over a large number of iBGP sessions at each router. Hence configurations based on route reflectors are commonly used for intra-AS route dissemination in large ASes. However, researchers have found that configuring route reflectors in an unprincipled fashion can result in routing anomalies like forwarding loops and sub-optimal paths. Although previous work on iBGP configuration correctness gives sufficient conditions to check if a given iBGP configuration is correct, the problem of constructing correct and scalable iBGP configurations using route reflection has not received much attention. (cont.) This thesis proposes and analyzes the first (to our knowledge) algorithm to construct iBGP session configurations that are both correct and more scalable than a full-mesh iBGP. Our algorithm, BGPSep, uses the notion of a graph separator--a small set of nodes whose removal partitions a graph into connected components of roughly equal sizes--to choose route reflectors and iBGP sessions in a way that guarantees correctness. We evaluate an implementation of the BGPSep algorithm on several real-world network topologies and find that iBGP configurations generated by BGPSep have between 2.5 to 5 times fewer iBGP sessions than a full-mesh. by Mythili Vutukuru. S.M. 2007-08-03T18:30:05Z 2007-08-03T18:30:05Z 2006 2006 Thesis http://hdl.handle.net/1721.1/38324 154317795 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 53 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Vutukuru, Mythili On constructing correct and scalable iBGP configurations |
| title | On constructing correct and scalable iBGP configurations |
| title_full | On constructing correct and scalable iBGP configurations |
| title_fullStr | On constructing correct and scalable iBGP configurations |
| title_full_unstemmed | On constructing correct and scalable iBGP configurations |
| title_short | On constructing correct and scalable iBGP configurations |
| title_sort | on constructing correct and scalable ibgp configurations |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/38324 |
| work_keys_str_mv | AT vutukurumythili onconstructingcorrectandscalableibgpconfigurations |