Distributed Systems Group -- Research

Feedback Based Routing

Students: Dapeng Zhu, Mark Gritter

Inter-domain routing entails coordinating the routers of many administratively independent ISPs to agree on operational routes such that packets are delivered reliably ad efficiently. With the world-wide scale of the Internet, it is infeasible to assume that all such ISPs can be fully trusted or that all links and routers remain operational. Links and routers can fail or be compromised by attackers. At the same time, the increasing dependence on Internet-based applications calls for better robustness in the routing system. A corporate mission-critical VPN must remain operational regardless of individual router failures and compromises, and VoIP over such a VPN calls for low-latency fail-over. BGP is the current inter-domain routing protocol in the Internet; yet, it is susceptible to large-scale failures if a router is compromised, and long service interruptions when links or routers fail.

We explore what we call Feedback Based Routing as an approach to making inter-domain routing resistant to attacks and byzantine failures. Together with source-routing at the autonomous routing domain granularity, we show how the Internet can achieve much higher availability. Feedback-based routing is far more scalable than BGP and can be incrementally deployed on the Internet.

An initial description can be found in Feedback Based Routing with Mark Gritter and David R. Cheriton. In ACM HotNets, October 2002, Princeton, NJ
[ ps ] [ pdf ]

More detailed description and evaluation in Feedback Based Routing with Mark Gritter and David R. Cheriton, 2003 [ ps ] [ pdf ]

Last updated on Feb. 25, 2005