Protocols for convergence and load-balancing in inter-domain routing

Over the last decade, the Internet has became the most popular communication tool. More and more people are using the Internet, not only for non-critical services such as Voice over IP (VoIP) and Internet TV, but also for critical services such as VoIP 911 and remote health monitoring.; This requires a stable Internet, which also provides end-to-end service guarantees. The Internet consists of many self-administered and inter-connected Autonomous Systems (ASms) or domains. Inter-domain routing in the Internet is performed by the Border Gateway Protocol (BGP). In BGP, each router chooses the best path according to some routing policy. Routing policies are chosen based on business agreements between domains. However, since routing policies are chosen locally, conflicts may occur between ASms, resulting in unstable behavior. In particular, routers may fail to achieve a stable route to the destination, i.e., routes may oscillate periodically.; To provide service guarantees, load balancing is required in both intra-domain and inter-domain routing protocols. Several methods provide load balancing at the intra-domain level, but load balancing in inter-domain routing is in its primitive stages. By providing load balancing across inter-domain links, each inter-domain link has a greater probability of maintaining spare bandwidth to support QoS reservations for critical applications.; We worked on two critical issues related to inter-domain routing: persistent oscillations and load balancing. We proposed convergence solutions for external BGP, internal BGP, and combined external & internal BGP. We also proposed an inter-domain load balancing algorithm, in which, incoming traffic is assigned to outgoing inter-domain links such that outgoing traffic load on inter-domain links is balanced.