Fast Scoped Rerouting for BGP

The currently deployed inter-domain routing protocol in the Internet is the Border Gateway Protocol (BGP) . It provides inter-domain connectivity and considers complex rules (policies) to influence the paths that are propagated to peers. At the time BGP was developed, policy-aware connectivity was the main objective. Today, however, the Internet user community requires not only a stable connectivity but also fast recovery from failures. Those requirements can not be fulfilled by BGP  entirely. The scalability of the current
Internet depends on several parameters, like the number of Autonomous Systems (ASes) or distinct routing table entries.Those parameters affect scalability as they determine the amount of exchanged information and the required resources, i.e., CPU time and memory usage, to fulfill the routing task. Every new AS adds at least one entry to the routing table. But because multi-homing is increasingly used, it is usually much more than only one entry. Another, not negligible, criterion for scalability is the dynamic of the network – especially the number of BGP updates, i.e., withdrawals and announcements of routes.



The frequency of BGP updates is one of the most serious problems of the current Border Gateway Protocol. In many different reasons for the occurrence of BGP updates are given. Among of them are: Router configuration errors (so called human errors), transient short-time physical and data link problems, software bugs, problems with leased lines (electrical timing issues that cause false alarms of disconnect) or short-time router failures. All those reasons have one thing in common: The generated BGP update is, strictly speaking, unnecessary, because it couldhave been avoided due to the temporary and short-time nature of the failure. Nevertheless, each time such a failure occurs, a BGP update has to be issued. Due to the fact that BGP
propagates every update message globally, the whole Internet is stressed even by a single mis-configuration. According to the main reason for routing instability are mis-configurations. Looking at an enormous mass of BGP updates populating the Internet  a mechanism is needed to reduce the total amount of BGP updates. Not only the load of router CPUs and the network is affected by those updates, but also the Internet has almost no chance to reach a consistent view at a single point in time.



Several recently proposed approaches try to alleviate BGP update storms. Most of them fix only a single BGP problem and extend BGP in a patchwork manner. The most related approaches to our novel concept are described in section II. The approach presented in this paper limits updates—in first instance—to those BGP peers that are directly affected by the current network change (e.g., link failure). Furthermore
this novel approach provides an alternative path to substitute a broken AS path. During the first reaction to the failure only peers that are inevitably affected by the failure are stressed with update messages. This approach is called Fast Scoped Rerouting (FaSRo), because it routes around the failure involving only a few peers to establish an alternative AS path. This reduces the total number of routing messages and accelerates convergence time . In contrast to that, BGP propagates a link failure in inter-domain connectivity
globally.



This paper is structured as follows: Section II contains a closer look at approaches that try to alleviate the problems of too many BGP update messages. Section III presents our novel FaSRo approach to improve the stability of inter-domain connectivity. Section IV provides first simulation results. Finally, section V gives a conclusion and an outlook on future work.