Research Abstracts - 2007

Scale-free Routing Schemes

Frans Kaashoek & Petar Maymounkov

The Problem

After almost a decade of research the P2P community has not yet achieved its primary goal of building a P2P system that implements a "useful" application (e.g. WWW) or data structure (e.g. hash table) and, at the same time, guarantees system and user "safety". Usefulness or safety are currently achievable in isolation, but not together.

P2P systems are, by definition, large-scale distributed systems comprised of mostly-independent participants which are allowed to join or leave at will. This freedom of user behavior makes P2P systems very susceptible to impersonation attacks, known as Sybil Attacks.

To resist impersonation attacks, a P2P system must abide by a simple rule: All communication in the system should occur only between pairs of nodes that are "friends" in the physical world. This rule imposes severe combinatorial constraints on distributed algorithms that can run on P2P systems while maintaining system "safety".

We have established that a variety of useful data structures can be implemented on a P2P system, contingent on the existence of a "scale-free routing scheme". A routing scheme assigns a routing table and a label to each vertex of the network connetivity graph, such that local forwarding decisions can be made based on the current vertex's routing table and the destination vertex's label. A scale-free routing scheme additionally requires that:

1. The routing scheme be computable efficiently and *incrementally* in the local message-passing model of distributed computation. Incremental computation is a powerful concept (in this setting) which ensures that vertex labels and routing tables are fairly stable with respect to changes in the connectivity graph
2. The size of the routing table at each vertex is proportional to the vertex degree. This requirement is crucial in ensuring that "big players" (like Google) can co-exist in the same network with the "little guy"

Our reseach is concerned with the theoretical aspects (existence, lower bounds, and algorithms) of scale-free routing schemes, as well as the implementational aspects of the corresponding P2P systems.

Research Agenda

Scale-free routing schemes are "harder" than classiscal ones since they have more stringent requirements. Existing lower-bound techniqes (like the ones of Thorup and Zwick "Approximate Distance Oracles" STOC'01) based on Erdös' girth conjecture of 1963 are not applicable. We are thus investigating new combinatorial methods for derving such bounds.

The design of incremental algorithms also calls for techniques that deviate from the classical ones. Existing literature, e.g. Thorup and Zwick "Compact Routing Schemes" SPAA'01, uses heavily-combinatorial methods and data structures which do not seem amenable to incremental computation. To tackle this problem we have explored a few fruitful directions in the emerging field of Geometric Routing and Greedy Metric Embeddings.