Tel-Aviv University - Computer Science Colloquium

Sunday, Nov 6, 2005, 11:15-12:15

Room 309
Schreiber Building


Scott Kirkpatrick

Hebrew University


Medusa -- a generic structure for long-tailed random networks


DIMES (see ) is a distributed agent-based mapping

effort which at present has attracted 3500 volunteers running more than 6000

DIMES clients in 87 countries.  And it is centered here at TAU.  We find

that significant amounts of new information can be found in the long tails

of this measurement process.  A novel picture of the intermediate scale

structure of the Internet is emerging which should generalize to many

situations described as random graphs or networks.


The data suggests a new picture of the AS-graph structure, which

distinguishes a relatively large, redundantly connected core of nearly 100

ASes and two components that flow data in and out from this core.  One

component is fractally interconnected through peer links;  the second makes

direct connections to the core only.  We plan to use this picture as a

framework for measuring and extrapolating changes in the Internet's physical

structure.  It also suggests ways in which changing today's rigidly

hierarchical routing conventions could give enormous increases in the

Internet's carrying capacity.


This work has been done in collaboration with Eran Shir and Yuval Shavitt of

TAU, and Shai Carmi of Bar-Ilan University.