Compact inter-domain routing under real-world constraints

Due to the “natural” growth of the Internet, the scaling properties of today’s inter-domain routing system worsen at a steep rate. Certain operational practices and a number of limitations of the routing protocol itself further exacerbate the scalability problem. In order to address this threat, this paper introduces 2SIDR, a two-step inter-domain routing approach. 2SIDR aims at significantly reducing the state requirements of routers while minimizing the incurred path inflation due to the lack of full routing state. 2SIDR leverages insights from theoretical approaches termed compact routing. But instead of adhering to mathematical constraints 2SIDR takes practical constraints from Internet operations into consideration, i.e., data that is available in practice and business relationships. We call this practical compactness as it deliberately gives up mathematical bounds in order to satisfy real-world requirements. Two variants of 2SIDR were analyzed extensively based on multiple sources of data gathered from the Internet to construct an Internet-scale AS-level topology. Various aspects were analyzed such as the state/stretch trade-off and the effect of observed routing policies.