A NEW SUFFICIENT CONDITION FOR ROBUST INTERDOMAIN ROUTING

Border Gateway Protocol (BGP) is currently the only interdomain routing protocol employed on the in- ternet. It allows tens of thousands of Autonomous Systems (ASes) to exchange routing information while implementing economic and organizational policies. However, conflicting policies between ASes can cause rout- ing instability and/or unpredictable routing solutions. A system of routers is robust if routing tables always converge predictably, despite router and link failures. We pursue an approach to guarantee BGP robustness through operational guidelines. Existing guidelines for BGP robustness are essentially geared toward satisfying the same sufficient condition for BGP robustness developed by Griffin and Wilfong. In this thesis, we first show that there exists a weaker sufficient condition for BGP robustness. We then discuss how new guidelines for configuring BGP with a guarantee of robustness may be derived from this new condition. Additionally, we compare various models of BGP behavior and show that the models do not always have equivalent results and sometimes have completely different behavior.