DS2
is an Internet
delay space synthesizer that can be used to synthesize Internet delay
data at a large scale compactly while preserving
important properties of the real Internet delay space.
Understanding the characteristics of
the Internet delay space (i.e., the all-pairs set of static round-trip
propagation delays among edge networks in the Internet) is important
for the design of global-scale distributed systems. For instance,
algorithms used in overlay networks are often sensitive to violations
of the triangle inequality and to the growth properties within the
Internet delay space. Since designers of distributed systems often rely
on simulation and emulation to study design alternatives, they need a
realistic model of the Internet delay space. Our analysis shows
that existing models do not adequately capture
important properties of the Internet delay space.
In this project, we
analyze measured delays among thousands of Internet edge networks and
identify key properties that are important for distributed system
design. Furthermore, we design and implement
DS2,
a synthesizer of the
Internet delay
space, based on our analytical findings.
DS2
preserves the
relevant metrics far better than existing models, allows for a compact
representation, and can be used to synthesize delay data for
simulations and emulations at a scale where direct measurement and
storage are impractical.
Some compelling features of
DS2
are:
DS2
adequately captures
and
preserves the relevant
characteristics of the
Internet delay space, including overall delay distribution, global
clustering,
local clustering, growth metrics, and triangle inequality
violations.
DS2
can interpolate
missing
measurements.
DS2
has a highly compact
representation. It only requires O(N)
memory space to
simulate a
network with N nodes (as
opposed to the O(N2)
matrix representation).
The computation overhead of
generating a
deterministic delay value for a given pair of nodes in DS2
is
negligible and only
requires a
little run-time computation, which makes the efficient simulation
possible.
DS2
can be used to
synthesize delay data
for simulations and emulations at a scale where direct measurement and
storage are impractical. The compact representation enables
accurate and memory efficient network simulations at large scale.
DS2
tool download: DS2
(beta version)
is now publicly available, any comments are appreciated! For your
convenience, HERE
is a synthetic 16kx16k
delay space based on Matrix1.
Bo Zhang
Department of Computer Science, 6100 Main Street MS132
Rice University
Houston, Texas, 77005
Telephone: 1-713-348-3817
Email:bozhang AT cs.rice.edu since
October
2006
