Reliability of Internal BGP Networks: Models and Optimizations

Xiao, Li; Nahrstedt, Klara; Wang, Jun

Permalink

https://hdl.handle.net/2142/11074 Copy

Description

Title

Reliability of Internal BGP Networks: Models and Optimizations

Author(s)

• Xiao, Li
• Nahrstedt, Klara
• Wang, Jun

Issue Date

2005-07

Keyword(s)

networking

Abstract

A reliable routing control plane in Internal Border Gateway Protocol (IBGP) is very important for achieving dependable Internet data communication. However, the reliability modeling of IBGP and the design of reliable IBGP route reflection networks, which are of great importance to increase the robustness of IBGP operations, have not been well investigated. The reliability analysis of IBGP networks, which are overlaid on top of IP networks, is challenging, because failures of IBGP sessions may be correlated through the shared IGP routes. In this paper, we first present a model for the reliability analysis in IBGP networks to characterize correlated failures, followed by two metrics to measure the reliability of IBGP. Then, we investigate the optimization problems of finding the most reliable IBGP route reflection topologies. We show that the problems in general are NP-hard and an optimization bound is thus provided. Moreover, we develop efficient algorithms for searching satisfactory nearoptimal topologies in general scenarios, as well as the optimal solutions in some special networks. Our study shows that route reflection topologies considerably influence the reliability of IBGP operations. By applying our models and optimization techniques, a route reflection topology can be appropriately configured and the IBGP robustness can be improved significantly.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11074

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections