INTEL RESEARCH SEMINAR

DATE: Monday, July 8, 2002
TIME: Noon - 1:30 pm
PLACE: Intel Seminar (417 S. Craig Street - 3rd Floor)
INTEL EVENTS PAGE: http://www.intel-research.net/pittsburgh/events.htm

SPEAKER:
Brad Karp
 ICSI, Berkeley

TITLE:
Geographic Routing for Scalable Wireless Network Systems

ABSTRACT:
The fundamental scaling challenge for a network routing system is to find correct routes on networks with many nodes, even when the topology changes, without generating an excessive load of network routing protocol messages. As the number of network nodes and rate of topological change increase, traditional distance-vector and link-state routing protocols do not scale: they either fail to find routes, generate too much routing protocol traffic, or both. Large-scale, mobile, wireless networks exhibit exactly these properties: the nodes are numerous, and the topology changes constantly. They represent an extreme point in the scaling challenge for routing. Real, truly scalable sensor networks, rooftop networks, and ad hoc networks cannot be built without a routing protocol that addresses this challenge.

In this talk, I'll present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that solves this scaling problem. GPSR uses the positions of routers and a packet's destination to make packet forwarding decisions. The algorithm makes greedy forwarding decisions using only information about a router's immediate neighbors in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. By keeping state only about the local topology, GPSR scales better in per-router state than shortest-path and ad hoc routing protocols as the number of network destinations increases. Under mobility's frequent topology changes, GPSR can use local topology information to find correct new routes quickly. I'll describe the GPSR protocol, and show results from extensive simulations of mobile wireless networks to compare its performance with that of Dynamic Source Routing. These simulations demonstrate GPSR's scalability on densely deployed wireless networks. I'll conclude by describing one of my ongoing projects in geographically informed distributed systems: GHT, a geographic hash table for istributed storage on sensor networks.

BIO:
 Brad Karp earned a B.S. at Yale University in 1992, an S.M. at Harvard University in 1995, and a Ph.D. at Harvard University in 2000, all in computer science. Since October 2000, he has been a research scientist at ICSI's ICIR group (formerly known as ACIRI) at Berkeley. Brad's research interests lie in scalable wireless and wired network systems. In his thesis, he designed geographic algorithms and protocols, including GPSR (Greedy Perimeter Stateless Routing), for routing robustly and scalably on networks with great numbers of nodes and rapid topological change. His recent work has included the design of a TCP robust to reordered packets (useful for multi-path routing); a scalable distributed storage system for sensor networks, GHT (Geographic Hash Table), that leverages GPSR to store data scalably across the population of sensors in a network; and the design of geographic traffic engineering algorithms for wireless networks, that distribute traffic to enhance spatial reuse. When outside of lab, he clings to the liberal arts by listening to and playing music (piano, classical and jazz; voice, classical), and devouring theatre, fiction, and The Economist.

For Further Seminar Info:
Contact Kim Kaan, 412-605-1203, or visit http://www.intel-research.net.

SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/