Overlay Mesh Construction
In recent years, overlay networks have been used to deploy
bandwidth-intensive applications like A/V broadcast, video conferencing,
data collection, multi-path routing, and file mirroring/transfer. The
performance of these applications is highly dependent on the ability to
operate over good quality overlay paths. A richly connected overlay
network comprised of high quality virtual paths provides the ideal
setting for these applications; applications can then react quickly to
fluctuating performance, use application-specific path selection
criteria, and coordinate concurrent communication channels over multiple
We have developed a mesh-first approach, where the dense graph of
all possible overlay links is reduced to a minimal topology composed of k trees. In particular, we focus on
a distributed algorithm to compute k
Minimum Spanning Trees (k-MST),
where edge weights correspond to any one of the standard performance
metrics, such as latency, bandwidth, and loss rate. The mesh is
constructed using initial estimates of network properties and refined
over time. The primary motivation to construct an overlay mesh of k trees is to ensure the existence
of k edge disjoint overlay
paths between any two nodes, to promote fault- and
performance-tolerance, and to enable path diversity. We have developed
a prototype overlay routing infrastructure that utilizes a k-tree methodology for mesh
construction that can be used in infrastructure-type settings like
PlanetLab as well as in large corporations. In our PlanetLab
implementation deployed over a 150-node overlay network, our prototype
demonstrated reasonable bandwidth utilization during construction, low
loss-rates for data streams, and high performance in a realistic
multicast file transfer scenario.
- A. Young, J. Chen, Z. Ma, A. Krishnamurthy, L. Peterson, and R.
available. Appeared in Infocom 2004.
Multipath Overlay TCP
Recent work on Internet measurement and overlay networks has shown that
redundant paths are common between pairs of hosts. We have developed a
multipath TCP protocol, which can utilize the available bandwidth of
those redundant paths in parallel. Multipath flows are more robust than
single-path flows as they do not stall even if some paths fail. Our
system also includes a mechanism for detecting shared congestions to
prevent multipath flows from obtaining an unfair share of bandwidth
during congestion. Multipath flows can also passively monitor the
performance of several paths in parallel and discover better overlay
paths than the routing path provided by the underlying routing
infrastructure. Our implementation has been evaluated and deployed on
the PlanetLab system.
A Transport Layer Approach for
Improving End-to-End Performance and Robustness Using Redundant Paths
M. Zhang, J. Lai, A.
Krishnamurthy, L. Peterson, and R. Wang.
To appear in Usenix Annual
Technical Conference, 2004. PDF
Range-Queriable Data Structures
Distributed hash tables use hashing schemes to map processors and keys
to a single ID space resulting in a load-balanced system where the
entities are (probabilistically) uniformly distributed over the ID
space. The main problem with DHT's, however, is that while we can locate
a single key in logarithmic time, finding a series of keys logically
related in the key space cannot be done efficiently. Concurrent data
structures, such as skip graphs
and skip nets, have been
proposed as alternatives. These systems can support range queries, but
the initial proposals do not specify a method by which keys are assigned
to processors in the system. Naive attempts to map keys to processors
either suffer from load-imbalance or fail to store similar keys
together. We have developed a load-balancing mechanism for assigning
keys to processors that ensures load balance and assigns similar keys
to the same processor. Initial experimental results show that the
resulting system uses significantly less state, displays long runs of
related keys, and provides a customizable degree of load-balance.
- Load Balancing and
Locality in Range-Queriable Data Structures
- J. Aspnes, J. Kirsch, and A. Krishnamurthy.
To appear in PODC, 2004. PS
Distributed Indexing of High-dimensional Data
Indexing of high-dimensional data is essential for building
applications such as multimedia retrieval, data mining, and spatial
databases. Traditional index structures rely on centralized processing.
This approach does not scale with the rapidly increasing amount of
application data available on massively distributed systems like the
Internet. We have developed a distributed high-dimensional index
structure based on peer-to-peer overlay routing. A new routing scheme
is used to lookup data keys in the distributed index, which guarantees
logarithmic lookup and maintenance cost, even in the face of skewed
datasets. We propose a novel nearest neighbor (NN) query scheme that can
substantially reduce search cost by sacrificing a small amount of
precision. We propose a load-balancing mechanism that partitions the
high dimensional search space in a balanced manner. We then analyze the
performance of our proposed using a variety of metrics with simulation
as well as a functional PlanetLab implementation.
Towards a Scalable Peer-to-Peer Index Service for High-Dimensional Data
- C. Zhang, A. Krishnamurthy, and R. Wang.
Submitted for publication.
Managing a Portfolio of Overlay Paths
In recent years, several architectures have been proposed and developed
for supporting streaming applications that take advantage of multiple
paths through the network simultaneously. We consider the problem of
computing a set of paths and the relative amounts of data conveyed
through them in order to support these high-performance data streams.
Given the expectation, variance, and covariance of an appropriate metric
of interest for overlay links, we attempt to solve the underlying
resource allocation problem by applying methods used in managing a
finance portfolio. We observe that the flow allocation problem
requires constrained application of these methods, and we discuss the
tractability of enforcing the constraints. We finally present some
simulation results to evaluate the effectiveness of our proposed
- Managing a
Portfolio of Overlay Paths
- D. Antonova, A. Krishnamurthy, Z. Ma, and R. Sundaram.
To appear in NOSSDAV, 2004.
Topology-sensitive Object Location
The ability to track the locations of distributed objects and maintain
cache coherence is crucial for many applications. Distributed hash
tables (DHTs) is the only pragmatic solution for this problem on
large-scale systems. However, proponents of the DHT-based approach
recognize that there are classes of applications on medium-scale systems
for which it is not appropriate. These include applications that
require strict consistency among many writers or fine-grained control
over the physical location of data. We have developed two different
object tracking systems that support strong coherence semantics and can
exploit the awareness of network topology. The first system maintains
explicit meta-data information to provide a consistent view of objects
in infrastructure-type settings. The network-awareness is especially
beneficial in a wide area network where the system's ability of
confining routing messages to a smallest possible locality is important.
Experiments with a deployment of the system on a real-world Internet
overlay show substantial benefits of the system compared to existing
approaches. The second system uses a multicast-like solution that
minimizes global meta-data state, allows autonomous data movement
decisions, and can effectively exploit locality in systems with
irregular and ad-hoc connectivity. Although we describe our second
approach as a "multicast-like" solution, it is actually quite different
from overlay multicast systems. Typically, the goal of existing
multicast systems is to deliver data to all machines in the target set.
In contrast, our goal is to retrieve a single copy from several possible
locations: the request need not always reach all possible locations,
and one or more data replies may return. To accomplish this
efficiently, we must carefully manage the order, type, and parallelism
of the requests to optimize performance.
Coherent and Network-Aware Tracking of
C. Zhang, J. Lai, S. Sobti, A.
Krishnamurthy, and R. Wang.
Submitted for publication.
Segank: A Distributed Mobile
S. Sobti, N. Garg, F. Zheng, J. Lai, A.
Krishnamurthy, and R. Wang.
Appeared in Usenix Conference on File and
Storage Technologies, 2004. PS