UCLA

In this dissertation, we describe avoidance routing. Avoidance routing is a mechanism that provides users control over how their data transits the Internet. Currently, a user may use cryptography to provide confidentially for their data, but has no control over who can observe or access their data. Avoidance routing provides this control by having users specify properties of routers they do not trust, such as geopolitical location. A path to the destination that does not transit routers with the given properties is found, on-demand, with reasonable assurances that the path found does not contain untrusted routers.

Avoidance routing accomplishes this by augmenting BGP with a security vector. This vector contains the properties of each router along the given AS path. Given this vector and a users criteria, avoidance routing conducts a depth-first search to find a valid path the destination. We leverage the information contained within BGP to try and find this path quickly and optimally. Our results show that avoidance routing tends to find short paths, on average 7 hops longer than the standard path in the worst case. Further, less than 1\% of nodes on the Internet are visited, and only 5\% in the worst case. The storage space required to store the augmented advertisements or conduct the search is both reasonable and small. Finally, their is no performance impact in terms of packet forwarding by using avoidance routing.

We will discuss our use of a consensus mechanism to provide protection of routing information. This mechanism treats each neighbor of a node as a consensus speaker or ``voter''. These speakers will each make claims about their neighbor, and the consensus approach will attempt to determine the validity of these claims as well as the quality of each speaker. When routing, only nodes with high agreement on their claims will be used, as well as only speakers with high quality. Our results show that our consensus mechanism, while simple, also provides reasonable security guarantees.