Mathematical Model of the Relationship between BGP Convergence Delay and Network Topologies

Abstract

BGP is a distant vector inters Autonomous System (AS) routing protocol that comes up after EGP to eliminate the inefficiency of EGP with respect to flexibility and scalability and to give support of an actual routing protocol. BGP handles the scalability problem using Classless Inter-Domain Routing (CIDR) and solves the inefficiency of EGP by accumulating all the possible route information to a destination and running a decision process to select a route to be used and to advertise to the peers. Recently BGP protocol starts to encounter several problems such as routing table growth, load balancing problems, BGP hijacking and transit-AS problems and increasing time of Convergence delay. Convergence delay is the time between the selection process for the best path and when the routers settled. Convergence delay started recently to be an issue for internet and larger network as it started to be increased which causes instability in the network. Instability lead to lost packets, delayed delivery, loss of connectivity and long end-to-end delay in the Internet as well as added overhead to BGP routers. The goal of this research is to study the behavior of different network topology in terms of BGP convergence delay besides defining a mathematical model to represent the relationship between convergence delay and number of nodes. Simulation results show that Mesh topology has the highest convergence delay. The study of the relation between convergence delay and number of nodes leads to mathematical equations which some of them represent linear relationship while others represent compound relationship.