Toward reliable, verifiable, and policy-compliant inter-domain routing

The stability, reliability, and security of Border Gateway Protocol (BGP) are vital to the success of the Internet. In this dissertation, we further an understanding of BGP dynamics by studying the structure and stability of origin advertisements, and explore techniques to guarantee that the advertised BGP route not only is associated with the valid origin but also comply with policies which are considered as the universal best practice. Analyzing real-world BGP updates for a period of one year from multiple vantage points, we visualize and quantitatively characterize the frequency, size, and effect of address assignment and origin changes. Broad classes of prefix behaviors are developed. We show that a significant portion of BGP traffic is due to prefix flapping and explore the contributing factors. A significant portion of prefixes have high origin stability. Most ASes are involved in few, if any, prefix movement events, while a small number of ASes are responsible for most of the origin churn. Additionally, we find that some abnormal prefix flapping is most likely due to misconfiguration and some culprit ASes characterize the places where multi-origin prefixes oscillate. Exploiting the characteristics that a significant number of prefixes have high origin stability and that historical information regarding prefix origins could be fairly reliable, we propose a non-cryptographic, incrementally deployable mechanism that probabilistically detects false BGP origin advertisements. Our technique is based on the observation that the highly connected nature of the Internet makes it difficult to block all the information from a valid source. We show how ASes can coordinate to inform the valid origin of a prefix about the potential prefix forgery attacks. We explore the design, operation, and efficacy of our detection mechanism and perform simulations based on real Internet topologies. Our results indicate that lightweight probing is highly effective; 98% of all invalid announcements are detected with only 10% of the ASes deploying the protocol. We further show that judicious AS selection strategies can further improve the detection capability while reducing the polling cost. Lastly, we quantitatively characterize BGP announcements that violate the valley-free property---an indicator that during route propagation, universal best practices regarding BGP policies are not preserved. Our analysis indicates that valley announcements are more pervasive than expected. Approximately ten thousand valley announcements appear every day and involve a substantial number of prefixes. We find that large surges of violating announcements can be attributed to transient configuration errors. We further propose a dynamic mechanism that extends BGP with additional information as transitive attributes and prevents construction and propagation of valley routes. Such information implicitly reflects the policies of the ASes along the path, without revealing the relationship of each AS pair.