Reliability-aware IBGP route reflection topology design

Li Xiao, Jun Wang, K. Nahrstedt

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


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
Number of pages10
ISBN (Electronic)0769520243
StatePublished - 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
ISSN (Print)1092-1648


Other11th IEEE International Conference on Network Protocols, ICNP 2003
CountryUnited States


  • 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