Reliability-aware IBGP route reflection topology design

Li Xiao, Jun Wang, K. Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the internal border gateway protocol (IBGP), route reflection is widely used as an alternative to full mesh IBGP sessions inside an AS for scalability reason. However, some important issues, such as the impact of route reflection on the reliability of IBGP and the construction of reliable reflection topology with unreliable routers or links, have not been well investigated. This paper addresses the problem of finding reliable route reflection topologies for IBGP networks, which is of great importance to increase the robustness of IBGP operations. We first present a novel reliability model and two new metrics (IBGP expected lifetime and expected session loss) to evaluate the reliability of reflection topologies, and further to investigate the design problem. After studying the solvability conditions under the router capacity constraints, we prove the NP-hardness of the problem, and then design and implement three heuristic solutions using randomization techniques: heuristic selection, greedy search and simulated annealing. Our extensive computational experiments show that the reliability of IBGP reflection network can be significantly improved by our solutions.

Original languageEnglish (US)
Title of host publicationProceedings - 11th IEEE International Conference on Network Protocols, ICNP 2003
PublisherIEEE Computer Society
Pages180-189
Number of pages10
ISBN (Electronic)0769520243
DOIs
StatePublished - Jan 1 2003
Event11th IEEE International Conference on Network Protocols, ICNP 2003 - Atlanta, United States
Duration: Nov 4 2003Nov 7 2003

Publication series

NameProceedings - International Conference on Network Protocols, ICNP
Volume2003-January
ISSN (Print)1092-1648

Other

Other11th IEEE International Conference on Network Protocols, ICNP 2003
CountryUnited States
CityAtlanta
Period11/4/0311/7/03

Keywords

  • Computational modeling
  • Computer network reliability
  • Computer science
  • Guidelines
  • Network topology
  • Peer to peer computing
  • Reflection
  • Robustness
  • Routing protocols
  • Scalability

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Reliability-aware IBGP route reflection topology design'. Together they form a unique fingerprint.

  • Cite this

    Xiao, L., Wang, J., & Nahrstedt, K. (2003). Reliability-aware IBGP route reflection topology design. In Proceedings - 11th IEEE International Conference on Network Protocols, ICNP 2003 (pp. 180-189). [1249769] (Proceedings - International Conference on Network Protocols, ICNP; Vol. 2003-January). IEEE Computer Society. https://doi.org/10.1109/ICNP.2003.1249769