Files in this item



application/pdfReliability of ... dels and Optimizations.pdf (372kB)
(no description provided)PDF


Title:Reliability of Internal BGP Networks: Models and Optimizations
Author(s):Xiao, Li; Nahrstedt, Klara; Wang, Jun
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.
Issue Date:2005-07
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2608
Rights 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).
Date Available in IDEALS:2009-04-20

This item appears in the following Collection(s)

Item Statistics