CSAIL Event Calendar: Previous Series

Balanced Network Decompositions for Internet Routing

Speaker: Richard M. Karp , University of California at Berkeley
Date: November 7 2006
Time: 4:15PM to 5:30PM
Location: 32-G449
Host: Silvio Micali, MIT

Let G be an undirected n-node graph whose edges represent communication links between nodes. A balanced decomposition of G consists of a set of connected subgraphs called components such that

1. Every node lies in at least one component.
2. Every component has O(sqrt(n)) nodes.
3. Any two components contain a common node.
4. The diameter of each component is O(log n).
5. With the exception of at most one exceptional node per component, every node lies in at most two components.

A balanced decomposition provides an efficient scheme for point-to-point communication. For each component, there is a routing table of size O(sqrt(n)) shared by all its non-exceptional nodes, supporting point-to-point communication within the component. For any two nodes u and v, there is a linking node w, such that a message from u to v can follow a path of length O(log n) in a component containing u and w, concatenated with a path of length O(log n) in a component containing w and v.

The preferential attachment model has been proposed as a plausible model for the growth of the Internet graph, in which nodes are the hosts and routers within the Internet. In this model nodes are added one by one. Each new node makes d simultaneous independent choices of neighbors, where the probability of choosing a given existing node is proportional to its degree. Our main result is that a graph generated according to the preferential attachment model (even with d = 2) has a balanced decomposition (with high probability).

At the core of our proof is a stochastic process that combines the classical Polya urn model with the power of two choices. There are n urns, each with initial occupancy 1. At each step two urns are chosen independently, where, in each choice, the probability of drawing an urn is proportional to its occupency. A ball is then added to the chosen urn of lower occupency. We show that, after a polynomial-bounded number of steps, all urns will have nearly equal occupancies (with high probability). Ths is in contrast with the classical Polya model, in which the occupencies are typically diverse.

This is joint work with Christos Papadimitriou, Henry Lin, Marth Sideri, and Christos Amanatidis.

See other events that are part of Theory Colloquium Fall 2006

See other events happening in November 2006