PDF《Instability Free Routing: Beyond》

s guard against inter-AS loops ineffective. IP pre?x hijacks: Pre?x hijacks, such as the notorious AS

7007 incident [30], periodically happen in the Internet. This type of anomaly can have a large impact, disrupting the connectivity of thousands of networks. Miscon?gurations are frequently cited as the source of the problem. McPherson [29] took a closer look at the root cause of a recent IP pre?x hijack and hypothesized that the interactions between BGP and static routes may have been at the origin of the routing anomaly. Our discussions with operators suggest that a se- quence of route injections between BGP and IGPs, which resets the AS PATH, may also cause a network to advertise a pre?x it does not own. Traf?c for the affected pre?x is subse- quently black-holed when the offending network has insuf- ?cient resources to handle the increased amount of traf?c. Nondeterministic forwarding paths: Messages posted on bulletin boards used by network operators indicate that a network con?guration consisting of multiple routing do- mains may result in unexpected forwarding paths. Chen and Yuan [7] described a case involving the interactions between iBGP and static routes. Our experiments show that the scope of the problem is signi?cantly larger: e.g., interactions be- tween BGP and OSPF, or between OSPF and RIP, have the same problem. None of the existing analytical frameworks can explain the observed outcomes. The operational community has long suspected that the culprit of these anomalies may lie in the interactions be- tween routing protocols. However, despite the severity of the problems, there is a surprisingly small number of studies on such interactions from the research community. Two of them [20], [32] introduced several frameworks to analyze the impact of the underlying IGP on BGP, and formulated con- ditions that may lead to forwarding loops, route oscillations, and delayed convergence. In our previous work [27], we de- veloped a formal model to reason about the consequences of injecting routes across routing domains. In particular, that model can be used to explain the permanent inter-AS for- warding loops and IP pre?x hijacks mentioned above. Yet, these studies cannot make sense of all the anomalies described above. For example, none of them can provide a good explanation of the reported nondeterministic routing behaviors. In addition, the results in [20] and [32] are spe- ci?c to the interactions between BGP and an IGP. However, recent empirical studies [28], [25] show that operational net- works frequently deploy multiple instances of IGP and join them through route redistributions rather than with BGP to achieve important design objectives such as ef?cient routing. The interactions between these IGP instances require further research. The interactions between different instances of routing pro- tocols con?gured on one network, which we will simply re- fer to as routing instances, are currently governed by two procedures executed at border routers: route selection and route redistribution. The route selection procedure ranks routes received from different routing protocol instances and selects a best route among them for forwarding purposes, and the route redistribution procedure facilitates the exchange of routing information between routing instances. They a........