Study on the AS relationship based inter-domain routing

The border gateway protocol (BGP) is the de facto inter-domain routing protocol in the global Internet. L. Gao et al. (2000) proposes a set of guidelines in setting routing policies for autonomous systems (AS) to guarantee route convergence. However, BGP-4 lacks the ability to describe relationships between ASes, which makes it difficult to implement these guidelines. We introduce two new attributes into the inter-domain routing protocol. One is used locally to identify relationships in each eBGP session. The other is a transitive attribute, which is used to identify backup links. We also propose a hierarchical structure violation detection algorithm. An implementation was presented based on the zebra routing software. This design makes it possible that local routing policies can be checked independently and systematically. Comparing with the Internet routing registry R. Govindan et al. (1999) and the simple routing registry L. Gao et al. (2000), we argue that our approach requires a minimal degree of global coordination.