July 8, 2002
Noon - 1:30 pm
Intel Seminar (417 S. Craig Street - 3rd Floor)
EVENTS PAGE: http://www.intel-research.net/pittsburgh/events.htm
Geographic Routing for Scalable Wireless Network Systems
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.
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.
Contact Kim Kaan, 412-605-1203,
or visit http://www.intel-research.net.
SDI Home: http://www.pdl.cmu.edu/SDI/