The first generation of geographic face routing algorithms use planarization techniques that rely on the unit-disk assumption. They can exhibit persistent routing failure when used with real radios, whose connectivity violates that assumption. In this talk, I will start by describing the Cross-Link Detection Protocol (CLDP), which enables provably correct geographic routing on arbitrary graphs. This protocol proactively probes links to determine link-crossings, and can incur moderate overhead. In the second half of my talk, I will describe a lazy cross-link removal technique that addresses this problem incurs two orders of magnitude lower overhead than the best known geographic routing protocol. I will conclude my talk with some observations about the applicability of geographic routing to the Internet. This is joint work with Young-Jin Kim (USC), Brad Karp (Univ. College, London) and Scott Shenker (UC Berkeley).
Speaker Biography
Ramesh Govindan received his B. Tech. degree from the Indian Institute of Technology at Madras, and his M.S. and Ph.D. degrees from the University of California at Berkeley. He is an Associate Professor in the Computer Science Department at the University of Southern California, and a senior researcher at the NSF Center for Embedded Networked Systems. His research interests include scalable routing in internetworks, Internet topology discovery and modeling, and wireless sensor networks.