High-speed data transfer is vital to data-intensive computing that often requires moving large data volumes efficiently within a local data center and among geographically dispersed facilities. Effective utilization of the abundant resources in modern multicore environments for data transfer remains a persistent challenge, particularly, for Non-Uniform Memory Access (NUMA) systems wherein the locality of data accessing is an important factor. This requires rethinking how to exploit parallel access to data and to optimize the storage and network I/Os. We address this challenge and present a novel design of asynchronous processing and resource-aware task scheduling in the context of high-throughput data replication. Our software allocates multiple sets of threads to different stages of the processing pipeline, including storage I/O and network communication, based on their capacities. Threads belonging to each stage follow an asynchronous model, and attain high performance via multiple locality-aware and peer-aware mechanisms, such as task grouping, buffer sharing, affinity control and communication protocols. Our design also integrates high performance features to enhance the scalability of data transfer in several scenarios, e.g., file-level sorting, block-level asynchrony, and thread-level pipelining. Our experiments confirm the advantages of our software under different types of workloads and dynamic environments with contention for shared resources, including a 28-160 percent increase in bandwidth for transferring large files, 1.7-66 times speed-up for small files, and up to 108 percent larger throughput for mixed workloads compared with three state of the art alternatives, GridFTP , BBCP and Aspera.

One constant challenge in multicourse systems is to utilize fully the abundant resources, while assuring superior performance for individual tasks, particularly, in Non-uniform Memory Access (NUMA) systems where the locality of access is an important factor. To achieve this goal requires rethinking how to exploit parallel data access and I/O related optimizations. In the context of developing software for high-speed data transfer, we offer a novel design using asynchronous processing, and detail the advantages of resources-conscious task scheduling. In our design, multiple sets of threads are allocated to the different stages of the processing pipeline based on the capacity of resources, including storage I/O, and network communication operations. The threads in these stages are executed in an asynchronous mode, and they communicate efficiently via localized mechanisms in NUMA systems, e.g., task grouping, buffer memory, and locks. With this design, multiple effective optimizations are seamlessly integrated particularly for improving the performance and scalability of end-to-end data transfer. To validate the benefits of the design and optimizations therein, we conducted extensive experiments on the state-of-the-art multicourse systems. Our results highlighted the performance advantages of our software across different typical workloads, compared to the widely adopted data transfer tools, Graft and BBCP.

In an iSCSI based storage area network, target hosts serve concurrent I/O requests from initiators to achieve both high throughput and low latency. Existing iSCSI leverages the OS page cache to ensure data sharing and reuse. However, the non-uniform memory access (NUMA) architecture introduces another dimension of complexity, i.e., asymmetric memory access in multi-core and many-core platforms. Within a NUMA platform, an iSCSI target often dispatches an access request with a cache hit to an I/O thread remote to cached data, and thus cannot fully utilize multi-core systems. We encounter this problem in the context of ultra high-speed data transfer between two iSCSI storage systems, during which inferior NUMA remote memory access lags behind available high network bandwidth, and thereby becomes a bottleneck of the entire end-to-end data transfer path. We design a NUMA-aware cache mechanism to align cache memory with local NUMA nodes and threads, and then schedule I/O requests to those threads that are local to the data being accessed. This NUMA-aware solution results in lower access latency and higher system throughput. We implement a cache system within the Linux SCSI target framework, and evaluated it on our NUMA-based iSCSI testbed. Experimental results show the NUMA-aware cache can significantly improve the performance of iSCSI as measured by several benchmark tools and confirm its viability in data intensive applications and real-life workloads.

Data-intensive applications frequently rely on multicore computer systems, in which Non-Uniform Memory Access (NUMA) is a dominant architecture. To transfer data into and out from these high-performance computers becomes a bottleneck, and thus it is crucial to understand their I/O performance characteristics. However, the complexity in NUMA architecture presents a new challenge in modeling its I/O access cost, and thus lead to difficulties in configuring proper processor and memory affinity. In this paper, we show that existing NUMA experimental methods and metrics are inappropriate on contemporary high-end systems. We characterize a state-of-the-art NUMA host, and propose, to the best of our knowledge, the first methodology to simulate I/O operations using memory semantics, and model the I/O bandwidth performance. Our methodology is thoroughly tested and validated by mapping multiple parallel I/O streams to different sets of hardware components (CPU, memory, network cards, and SSDs) and by measuring the performance of each mapping. The experimental results and analysis reveal that our methodology can dramatically reduce characterization workload, accurately estimate the overall I/O performance, and effectively mitigate resource contention among I/O tasks.

Data-intensive applications place stringent requirements on the performance of both back-end storage systems and front-end network interfaces. However, for ultra high-speed data transfer, for example, at 100 Gbps and higher, the effects of multiple bottlenecks along a full end-to-end path, have not been resolved efficiently. In this paper, we describe our implementation of an end-to-end data transfer software at such high-speeds. At the back-end, we construct a storage area network with the iSCSI protocols, and utilize efficient RDMA technology. At the front-end, we design network communication software to transfer data in parallel, and utilize NUMA techniques to maximize the performance of multiple network interfaces. We demonstrate that our system can deliver the full 100 Gbps end-to-end data transfer throughput. The software product is tested rigorously and demonstrated applicable to supporting various data-intensive applications that constantly move bulk data within and across data centers.

Providing high-speed data transfer is vital to various data-intensive applications.While there have been remarkable technology advances to provide ultra-high-speed network bandwidth, existing protocols and applications may not be able to fully utilize the bare-metal bandwidth due to their inefficient design.We identify the same problem remains in the field of Remote Direct Memory Access (RDMA) networks.RDMA offloads TCP/IP protocols to hardware devices.However, its benefits have not been fully exploited due to the lack of efficient software and application protocols, in particular in wide-area networks.In this paper, we address the design choices to develop such protocols.We describe a protocol implemented as part of a communication middleware.The protocol has its flow control, connection management, and task synchronization.It maximizes the parallelism of RDMA operations.We demonstrate its performance benefit on various local and wide-area testbeds, including the DOE ANI testbed with RoCE links and InfiniBand links.

Network coding techniques have been proved effective in increasing the capacity of wireless ad hoc and mesh networks. Despite this, little is known about its potentials and limitations of improving application perceivable performance. One of the mysteries lies in the complicated interaction between the low-layer network coding function and the upper-layer protocols/applications. In this paper, targeting multimedia applications, we attempt to inspect the interaction between network coding and end-host coding techniques, in particular forward error correction (FEC), and study how network coding can benefit multimedia applications by interacting with FEC. We show network coding has two positive impacts on the efficacy of FEC. First, when network capacity is critically low for competing multimedia flows, even a marginal capacity increase leads to much higher packet recovery ratio for applications. Second, we show that network coding technique can lead to less bursty packet loss patterns. Even at a fair loss rate, such less bursty loss patterns lead to dramatically higher packet recovery ratio at the receivers. Our results and analysis validate that network coding can be beneficial to end-host coding techniques.

For many applications in wireless sensor networks (WSNs), users may want to continuously extract data from the networks for analysis later. However, accurate data extraction is difficult-it is often too costly to obtain all sensor readings, as well as not necessary in the sense that the readings themselves only represent samples of the true state of the world. Clustering and prediction techniques, which exploit spatial and temporal correlation among the sensor data provide opportunities for reducing the energy consumption of continuous sensor data collection. Integrating clustering and prediction techniques makes it essential to design a new data collection scheme, so as to achieve network energy efficiency and stability. We propose an energy-efficient framework for clustering-based data collection in wireless sensor networks by integrating adaptively enabling/disabling prediction scheme. Our framework is clustering based. A cluster head represents all sensor nodes in the cluster and collects data values from them. To realize prediction techniques efficiently in WSNs, we present adaptive scheme to control prediction used in our framework, analyze the performance tradeoff between reducing communication cost and limiting prediction cost, and design algorithms to exploit the benefit of adaptive scheme to enable/disable prediction operations. Our framework is general enough to incorporate many advanced features and we show how sleep/awake scheduling can be applied, which takes our framework approach to designing a practical algorithm for data aggregation: it avoids the need for rampant node-to-node propagation of aggregates, but rather it uses faster and more efficient cluster-to-cluster propagation. To the best of our knowledge, this is the first work adaptively enabling/disabling prediction scheme for clustering-based continuous data collection in sensor networks. Our proposed models, analysis, and framework are validated via simulation and comparison with competing techniques.

For many applications in wireless sensor networks, accurate data collection is a crucial problem. Users may want to continuously extract data from the networks for analysis after. Clustering and prediction techniques, which exploit spatial and temporal correlation among sensor data, provide opportunities for reducing the energy consumption of sensor data collection. We propose the LEAP (Localized Energy-Aware Prediction) approach. LEAP is clustering based. A cluster head represents all sensor nodes in the cluster, and collects data values from them. LEAP implements local prediction algorithms, and only data values not within a specified error bound are collected by a cluster head. By doing so, the cluster head maintains an accurate view of the sensor data, while the communication cost is reduced. In this paper, we present energy-aware prediction models used in LEAP, analyze the performance tradeoff between reducing communication cost and limiting prediction cost, and design algorithms to exploit the benefit of energy-aware prediction. We believe LEAP has broad applications. Our proposed models, analysis, and algorithms are validated via simulation.

Wireless sensor networks have stringent constraints on system resources and data aggregation techniques are critically important. However, accurate data aggregation is difficult due to the variation of sensor readings and due to the frequent communication failures. To address these difficulties, we propose a scalable and robust data aggregation algorithm. The novelty of our work includes two aspects. First, our algorithm exploits the mixture model and the Expectation Maximization (EM) algorithm for parameter estimation. Hence, it captures the effects of aggregation over different scales while keeping the communication cost low. Second, our algorithm exploits loss-tolerant multi-path routing schemes. Hence, it obtains accurate statistical information even in the presence of high link and node failure rates. We demonstrate that our techniques reduce communication cost while retaining the precious statistical information otherwise neglected by other aggregation techniques. Our evaluation shows the proposed techniques are robust against link and node failures, and perform consistently well.

In peer-to-peer streaming applications such as IP television and live shows, a key problem is how to construct an overlay network to provide high-quality, almost real-time media relay in an efficient and scalable manner. Much work has focused on the construction of tree and graph network topology, often based on the inference of network characteristics such as delay and bandwidth. Less attention has been paid to improving the liveness of media delivery, and to exploiting the flexibility of applications to construct better overlay networks. We propose the NSYNC, an ongoing work on constructing low-latency overlay networks for live streaming. It aims at solving the following problems. In typical applications, peers must buffer a portion of a real-time event, e.g., for at least a few seconds, to limit the impact of adversary network conditions. Thus, it introduces both (1) delay, especially long delay for peers that are many hops away from the origin servers, and (2) partial ordering between the peers. With NSYNC, the application media players can slightly increase or decrease the speed of playing media. Thus, the peers in a network can be synchronized to achieve two effects. First, late peers can catch early peers and the origin server such that the entire peer networks improve liveness. Second, the client/server roles between a pair of neighboring peers can be reversed, allowing opportunities for constructing more efficient overlay networks. NSYNC can be used in various peer-to-peer streaming systems.

In unstructured peer-to-peer networks, controlled flooding aims at locating an item at the minimum message cost. Dynamic querying is a new controlled flooding technique. While it is implemented in some peer-to-peer networks, little is known about its undesirable behavior and little is known about its general usefulness in unstructured peer-to-peer networks. This paper describes the first evaluation and analysis of such techniques, and proposes novel techniques to improve them. We make three contributions. First, we find the current dynamic querying design is flawed. Although it is advantageous over the expanding ring algorithm in terms of search cost, it is much less attractive in terms of peer perceived latency, and its strict constraints on network connectivity prevent it from being widely adopted. Second, we propose an enhanced flooding technique which requires the search cost close to the minimum, reduces the search latency by more than four times, and loosens the constraints on the network connectivity. Thus, we make such techniques useful for the general unstructured peer-to-peer networks. Third, we show that our proposal requires only minor modifications to the existing search mechanisms and can be incrementally deployed in peer-to-peer networks.

Providing Internet access to Mobile Ad hoc Networks (MANETs) can greatly extend their applications, increase their scalability, and improve the quality of service. However, a critical problem is how the mobile hosts can locate Internet-based servers efficiently in a dynamic, unstructured network. Neither reactive strategies, where the hosts initiate on-demand server discovery, nor proactive strategies, where the servers periodically advertise their availability information, are optimal. To that end, this paper studies adaptive strategies that (1) combine both proactive advertising by the servers and on-demand discovery by the mobile hosts, and (2) determine the relative rate of proactive advertising and on-demand discovery adaptively according to the network characteristics including the host mobility level and the offered load. We propose and evaluate two novel, integrated algorithms. First, to determine the rate of proactive advertising, we propose an exponential backoff algorithm to probe the optimal operating point. Second, to reduce the network traffic due to reactive (on-demand) discovery, we propose a novel controlled flooding algorithm. Our simulation study reveals that, compared to the previous proactive strategies and reactive strategies, our adaptive strategies reduce network traffic for locating the servers by several times when the network has a moderate offered load and a low or high level of host mobility.

Emerging multi-hop wireless mesh networks have much different characteristics than the Internet. They have low dimensionality and large diameters. Content and service replication can greatly improve their scalability. However, replication strategies in such networks have not been well studied. This paper studies the optimality of replication strategies and explores it in multi-hop wireless mesh networks for the first time. We start with the problem of determining the optimal numbers of replicas for a set of objects which have distinct probabilities of being requested in large 2-D mesh networks. We reveal the structure of the optimal replication strategy to minimize object access cost. To minimize average cost to access an object in 2-D mesh networks, the optimal strategy replicates an object such that the number of its replicas is proportional to p0.667, where p is the access probability of the object. This result indicates the inefficiency of demand-driven content and service replication in 2-D mesh networks, where an object is replicated such that the number of its replicas is proportional to p. We further study practical, online algorithms to approximate the optimal strategy. Interestingly, the optimal replication can be approximated well by a localized replacement algorithm. The algorithm utilizes only handy information and incurs no communication overhead. The paper demonstrates a significant performance gain by the optimal strategy, and the effectiveness of the online replacement algorithm.

Media streaming in wireless ad hoc networks is challenging due to the stringent resource restrictions and the decentralized architecture. To support long and high-quality streams, one viable approach is divide-and-conquer. A media stream is partitioned into segments, and then the segments are replicated in a network and served in a peer-to-peer fashion. It alleviates resource requirements on light-weight devices, improves load balancing, and provides an opportunity for fine-grain replication, among others. This paper describes a peer-to-peer service model using this approach, and in particular, studies replication strategies for the segments. We exploit topological properties of the underlying networks, and exploit correlation of streaming access. Several strategies are described and evaluated. A novel strategy uses adaptive and selective replication. It infers end-host clustering from hop-distance, and selectively replicates media segments to avoid starving any of them. Preliminary simulation study demonstrates its effectiveness in minimizing the cost to discover and retrieve media data.

The increasing diversity of Internet application requirements has spurred recent interest in transport protocols with flexible transmission controls. In window-based congestion control schemes, increase rules determine how to probe available bandwidth, whereas decrease rules determine how to back off when losses due to congestion are detected. The control rules are parameterized so as to ensure that the resulting protocol is TCP-friendly in terms of the relationship between throughput and loss rate. This paper presents a comprehensive study of a new spectrum of window-based congestion controls, which are TCP-friendly as well as TCP-compatible under RED. Our controls utilize history information in their control rules, and by doing so, they improve the transient behavior. We demonstrate analytically, and through extensive ns simulations, the steady-state and transient behavior of several instances of this new spectrum.

Internet streaming applications are affected by adverse network conditions such as high packet loss rates and long delays. This paper aims at mitigating such effects by leveraging the availability of client-side caching proxies. We present a novel caching architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. A salient feature of our caching algorithms is that they allow partial caching of streaming media objects and joint delivery of content from caches and origin servers. The caching algorithms we propose are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit-rate requirements, and the available bandwidth between clients and servers. Using realistic models of Internet bandwidth derived from proxy cache logs and measured over real Internet paths, we have conducted simulations to evaluate the performance of various cache management alternatives. Our experiments demonstrate that network-aware caching algorithms can significantly reduce service delay and improve overall stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.

Abstract—We present a thorough characterization of what we believe to be the first significant live Internet streaming media workload in the scientific literature. Our characterization of over 3.5 million requests spanning a 28-day period is done at three increasingly granular levels, corresponding to clients, sessions, and transfers. Our findings support two important conclusions. First, we show that the nature of interactions between users and objects is fundamentally different for live versus stored objects. Access to stored objects is user driven, whereas access to live objects is object driven. This reversal of active/passive roles of users and objects leads to interesting dualities. For instance, our analysis underscores a Zipf-like profile for user interest in a given object, which is in contrast to the classic Zipf-like popularity of objects for a given user. Also, our analysis reveals that transfer lengths are highly variable and that this variability is due to client stickiness to a particular live object, as opposed to structural (size) properties of objects. Second, by contrasting two live streaming workloads from two radically different applications, we conjecture that some characteristics of live media access workloads are likely to be highly dependent on the nature of the live content being accessed. This dependence is clear from the strong temporal correlation observed in the traces, which we attribute to the impact of synchronous access to live content. Based on our analysis, we present a model for live media workload generation that incorporates many of our findings, and which we implement in GISMO. Index Terms—Internet, live streaming, measurement, multimedia, workload characterization. I.

To serve asynchronous requests using multicast, two categories of techniques---stream merging and periodic broadcasting---have been proposed. For sequential streaming access, where requests are uninterrupted from the beginning to the end of an object, these techniques are highly scalable: the required server bandwidth for stream merging grows logarithmically as request arrival rate, and the required server bandwidth for periodic broadcasting varies logarithmically as the inverse of start-up delay. A sequential access model, however, is inappropriate to model partial requests and client interactivity observed in various streaming access workloads. This paper analytically and experimentally studies the scalability of multicast delivery under a non-sequential access model where requests start at random points in the object. We show that the required server bandwidth for any protocol providing immediate service grows at least as the square root of request arrival rate, and the required server bandwidth for any protocol providing delayed service grows linearly with the inverse of start-up delay. We also investigate the impact of limited client receiving bandwidth on scalability. We optimize practical protocols which provide immediate service to non-sequential requests. The protocols utilize limited client receiving bandwidth, and they are near-optimal in that the required server bandwidth is very close to its lower bound.

The increased diversity of Internet application requirements has spurred interest in flexible congestion control mechanisms. Window-based congestion control schemes use increase rules to probe available bandwidth, and decrease rules to back off when congestion is detected. The control rules are parameterized so as to ensure that the resulting protocol is TCP-friendly in terms of the relationship between throughput and packet loss rate. We propose a novel window-based congestion control algorithm called SIMD (Square-Increase/Multiplicative-Decrease). Contrary to previous memoryless controls, SIMD utilizes history information in its control rules. It uses multiplicative decrease but the increase in window size is in proportion to the square of the time elapsed since the detection of the last loss event. Thus, SIMD can efficiently probe available bandwidth. Nevertheless, SIMD is TCP-friendly as well as TCP-compatible through RED routers. Furthermore, SIMD has much better convergence behavior than TCP-friendly AIMD and binomial algorithms proposed previously.

Web caching aims at reducing network traffic, server load and user-perceived retrieval delays by replicating popular content on proxy caches that are strategically placed within the network. While key to effective cache utilization, popularity information (e.g. relative access frequencies of objects requested through a proxy) is seldom incorporated directly in cache replacement algorithms. Rather other properties of the request stream (e.g. temporal locality and content size), which are easier to capture in an online fashion, are used to indirectly infer popularity information, and hence drive cache replacement policies. Recent studies suggest that the correlation between these secondary properties and popularity is weakening due in part to the prevalence of efficient client and proxy caches. This trend points to the need for proxy cache replacement algorithms that directly capture popularity information. We present an on-line algorithm that effectively captures and maintains an accurate popularity profile of Web objects requested through a caching proxy. We propose a novel cache replacement policy that uses such information to generalize the well-known greedy dual-size algorithm, and show the superiority of our proposed algorithm by comparing it to a host of recently-proposed and widely-used algorithms using extensive trace-driven simulations and a variety of performance metrics.

Temporal locality of reference in Web request streams emerges from two distinct phenomena: the long-term popularity of Web documents and the short-term temporal correlations of references. We show that the commonly-used distribution of inter-request times is predominantly determined by the power law governing the long-term popularity of documents. This inherent relationship tends to disguise the existence of short-term temporal correlations. We propose a new and robust metric that enables accurate characterization of that aspect of temporal locality. Using this metric, we characterize the locality of reference in a number of representative proxy cache traces. Our findings show that there are measurable differences between the degrees (and sources) of temporal locality across these traces.

No abstract available.