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 paths.

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. Wang.
PDF 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 available.

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 available.

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.
          SkipIndex: 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 techniques.
           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 Objects
        C. Zhang, J. Lai, S. Sobti, A. Krishnamurthy, and R. Wang.  
        Submitted for publication.

        Segank: A Distributed Mobile Storage System        
        S. Sobti, N. Garg, F. Zheng, J. Lai, A. Krishnamurthy, and R. Wang.
        Appeared in Usenix Conference on File and Storage Technologies, 2004.  PS available.