ICS Theory Group

ICS 269, Winter 2004: Theory Seminar


13 Feb 2004:
Routing in highly dynamic network communities
Amitabha Bagchi

The advent of large freely-evolving networks has led to a new notion of computing in communities. These communities share resources to achieve shared or individual goals. Unlike the rigidly organized parallel systems of the past, these networks have relatively looser interconnection regimes and allow, in fact expect, nodes and edges to come and go as they please. We study the ability of networks to deal with this highly dynamic situation by looking at the basic problem of routing. We use the edge expansion of the network (roughly the number of edges per node going out of a given set of nodes) as our measure of the ability to route packets efficiently. We study the effect if nodes leaving the system on the expansion of the network. We also propose a system of routing flows through disjoint paths to provide robustness against edges going down and analyze it in terms of the expansion.