Erasure coding has been used in storage systems to enhance data durability at a lower storage overhead. However, these systems suffer from long access latency tails due to a lack of flexible load balancing mechanisms and passively launched degraded reads when the original storage node of the requested data becomes a hotspot. We provide a new perspective to load balancing in coded storage systems by proactively and intelligently launching degraded reads and propose a variety of schemes to make optimal decisions either per request or across requests statistically. Experiments on a 98-machine cluster based on the request traces of 12 million objects collected from Windows Azure Storage (WAS) show that our schemes can reduce the median latency by 44.7% and the 95th-percentile tail latency by 77.8% in coded storage systems.

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size.

We design flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two new classes of erasure-resilient codes are introduced -- Basic Pyramid Codes (BPC) and Generalized Pyramid Codes (GPC). Both schemes require slightly more storage space than conventional schemes, but significantly improve the critical performance of read during failures and unavailability. As a by-product, we establish a necessary matching condition to characterize the limit of failure recovery, that is, unless the matching condition is satisfied, a failure case is impossible to recover. In addition, we define a maximally recoverable (MR) property. For all ERC schemes holding the MR property, the matching condition becomes sufficient, that is, all failure cases satisfying the matching condition are indeed recoverable. We show that GPC is the first class of non-MDS schemes holding the MR property.

Network codes designed specifically for distributed storage systems have the potential to provide dramatically higher storage efficiency for the same availability. One main challenge in the design of such codes is the exact repair problem: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. One of the main open problems in this emerging area has been the design of simple coding schemes that allow exact and low cost repair of failed nodes and have high data rates. In particular, all prior known explicit constructions have data rates bounded by 1/2. In this paper we introduce the first family of distributed storage codes that have simple look-up repair and can achieve rates up to 2/3. Our constructions are very simple to implement and perform exact repair by simple XORing of packets. We experimentally evaluate the proposed codes in a realistic cloud storage simulator and show significant benefits in both performance and reliability compared to replication and standard Reed-Solomon codes.

Consider a linear [n,k,d]qcodeC. We say that theith coordinate ofChas localityr, if the value at this coordinate can be recovered from accessing some otherrcoordinates ofC. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancyn-kin terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance.

The convergence of games and online social platforms is an exploding phenomena. The continued success of social games hinges critically on the ability to deliver smooth and highly-interactive experiences to end-users. However, it is extremely challenging to satisfy the stringent performance requirements of online social games.

Cloud service providers operate data centers around the world, and they depend on Global Traffic Management systems to direct requests from clients to the most appropriate data center to serve the requests. While GTM systems have been in-use for years, they are attracting re-newed interests due to the rapid expansion of cloud service providers' networks, the introduction of public DNS systems, as well as new proposals to alter how they should work and what information local DNS servers (LDNS) should make available to drive the GTM systems. This paper uses large-scale measurements conducted from more than 5M clients to establish properties of the current Internet that affect the design of the GTM systems, such as the stretch between a client's actual position and its LDNS from GTM's perspective, the impact of public DNS systems, and the granularity at which GTM decisions should be made. The results can inform the debate over how GTM systems should be designed.

To optimize network performance, cloud service providers have a number of options available to them, including co-locating production servers in well-connected Internet eXchange (IX) points, deploying data centers in additional locations, or contracting with external Content Distribution Networks (CDNs). Some of these options can be very costly, and some may or may not improve performance significantly. Cloud service providers would clearly like to be able to estimate a priori performance gain of the various options before sinking significant capital expenditures into major infrastructure changes. In this paper we take a measurement-oriented approach and develop methodologies that accurately predict the performance improvement for making major infrastructure changes. Our methodologies leverage active web content, existing large-scale CDN infrastructures, and the SpeedTest network. We then apply our methodologies and a CloudBeacon tool to the problem of locating satellite data centers throughout the world. The results show that for North America, a deployment limited to 11 locations will be sufficient. However, in order to provide good latency and throughput performance on a global scale, somewhere between a total of 36 and 72 cloud-service locations with good peering connections is most likely needed.

We consider exact repair of failed nodes in maximum distance separable (MDS) code based distributed storage systems. It is well known that an (n, k) MDS code can tolerate failure (erasure) of up to n - k storage disks, when the code is used to store k information elements over n distributed storage disks. The focus of this paper is optimal recovery, in terms of repair bandwidth - the amount of data to be downloaded to repair a failed node - for a single failed node. When a single node fails, it has been previously shown by Dimakis et. al. that the amount of repair bandwidth is at least equation units, when each storage disk stores ℒ units of data. The achievability of this lower bound of equation units, for arbitrary values of (n, k); has been shown previously using asymptotic code constructions based on asymptotic interference alignment. However, the existence of finite codes satisfying this lower bound has been shown only for specific regimes of (n, k) and their existence for arbitrary values of (n, k) remained open. In this paper, we provide the first known construction of a finite code for arbitrary (n, k), which can repair a single failed systematic node by downloading exactly equation units of data. The code that we construct is based on permutation matrices and hence termed the Permutation Code.

As storage systems grow in size and complexity, various hardware and software component failures inevitably occur, resulting in disk malfunction in failures, as well as silent errors. Existing techniques and schemes overcome the failures and silent errors in a separate fashion. In this paper, we advocate using the STAR code as a unified and systematic mechanism to simultaneously tolerate failures on one disk and silent errors on another. By exploring the unique geometric structure of the STAR code, we propose a novel efficient decoding algorithm - EEL. Both theoretical and experimental performance evaluations show that EEL constantly outperforms a naive Try-and-Test approach by large factors in overall decoding throughput.

Voice over Internet (VoIP) has been experiencing enormous growth in recent years. While posed to replace traditional PSTN for both enterprise and residential customers, VoIP has yet to achieve the same level of quality and reliability as PSTN. One key challenge is that a growing segment of customers is increasingly relying on WiFi connections. VoIP over WiFi (VoWiFi) experiences significant degradation in quality because of packet losses, mostly due to WiFi's low capacity, varying signal strength, interference, etc. To understand this problem, we have developed and deployed a comprehensive measurement platform in a global enterprise network. From large-scale real-world traces, we quantitatively analyze the impact of WiFi connections and study measures to mitigate such impact. Our results confirm that WiFi connections incur significantly more packet losses than wirelines, but these losses can be effectively concealed by sending each packet up to five times (heavy replication). Due to WiFi's inherent overhead, heavy replication only marginally increases WiFi airtime. To avoid the overhead on wirelines, we further propose a relay-based solution, where heavy replication only occurs between endpoints and nearby relays, and is removed before packets are transmitted on inter-branch long haul links or the public Internet. The solution has been implemented and deployed in the global enterprise network, and measurement results confirm that it can indeed greatly improve the performance of VoIP for WiFi users. In particular, it reduces the percentage of poor calls from 35% to 10%; and increases the percentage of acceptable ones from 45% to 70%.

Global enterprises are increasingly adopting unified communication solutions over traditional telephone systems. Such solutions provide integrated audio/video conferencing and messaging services, and enable flexible working environments by allowing mobile and dispersed users to communicate and collaborate easily and efficiently. The ultimate goal of unified communications is to ensure a smooth and best possible user experience across all scenarios. To address this challenge and understand the impact of various network scenarios on unified audio/video conferencing, we have developed a distributed experimental platform - SureCall - and deployed it on over 80 machines across a global enterprise and many residential networks. SureCall has collected worth of more than 6 months of packet-level audio/video conferencing traces. Through in-depth analysis of these traces, we have quantitatively compared how key performance metrics, such as packet loss and jitter, as well as the correlation between them, are affected by the enterprise and residential networks, by WiFi connections and VPN links, etc. In addition, we show how SureCall can serve as an ideal platform to design, experiment and validate new schemes and algorithms. We have developed a new audio quality classifier using the SureCall platform, which is being experimented with the recent release of Office Communicator solution for large-scale validation.

Recently, there has been a dramatic increase in interactive cloud based software applications (e.g. working on remote machines, online games, interactive websites such as financial, web search) and other soft real-time applications (traffic within data center). Compared to classical real-time media applications (VoIP/conferencing) and non real-time file delivery, these interactive software applications have unique characteristics as they are delay sensitive yet demand in order and reliable data delivery. Therefore existing protocols for delivery of lossless data (such as TCP) and other delivery protocols using UDP do not work well. In this demo, we show substantially improved performance for such traffic by using a transport protocol built on top of UDP which uses intelligent adaptive forward error correction (FEC) and improved congestion control (rate control). The transport protocol is made lossless by using a hybrid FEC/ARQ strategy. The congestion control technique improves the delay performance by preventing congestion induced loss and minimizing queuing delay while still fully utilizing network capacity and maintaining fairness across flows. In this demo, we present RAPID (a ReliAble transport Protocol for Improving end-to-end Delay) and show its effectiveness in improving the performance of interactive client-server applications.

Peer-to-peer (P2P) content distribution is able to greatly reduce dependence on infrastructure servers and scale up to the demand of the Internet video era. However, the rapid growth of P2P applications has also created immense burden on service providers by generating significant ISP-unfriendly traffic, such as cross-ISP and inter-POP traffic. In this work, we consider the unique properties of peer-assisted Video-on-Demand (VoD) and design a distributed rate allocation algorithm, which can significantly cut down on ISP-unfriendly traffic without much impact on server load. Through extensive packet-level simulation with both synthetic and real-world traces, we show that the rate allocation algorithm can achieve substantial additional gain, on top of previously proposed schemes advocating ISP-friendly topologies.

In this paper, we quantify the potential gains of hybrid CDN-P2P for two of the leading CDN companies, Akamai and Limelight. We first develop novel measurement methodology for mapping the topologies of CDN networks. We then consider ISP-friendly P2P distribution schemes which work in conjunction with the CDNs to localize traffic within regions of ISPs. To evaluate these schemes, we use two recent, real-world traces: a video-on-demand trace and a large-scale software update trace. We find that hybrid CDN-P2P can significantly reduce the cost of content distribution, even when peer sharing is localized within ISPs and further localized within regions of ISPs. We conclude that hybrid CDN-P2P distribution can economically satisfy the exponential growth of Internet video content without placing an unacceptable burden on regional ISPs.

In this paper, we study the maximally recoverable (MR) property for multi-protection group (MPG) codes. MPG codes with MR property achieve the best erasure recoverability given configurations, where a configuration represents the structural relationship between data and parity symbols. We present construction and decoding algorithms for MPG codes with MR property. We show that both recoverability and minimum decoding overhead of any MPG code with MR property depend only on the configuration, where decoding overhead is defined as the additional number of symbols to access, in order to decode the lost data symbols.

To flexibly explore the trade-offs between storage space and access efficiency in reliable data storage systems, we describe two classes of erasure resilient coding schemes: basic and generalized pyramid codes. The basic pyramid codes can be simply derived from any existing codes, and thus all known efficient encoding/decoding techniques directly apply. The generalized pyramid codes are radically advanced new codes, which can further improve access efficiency and/or reliability upon the basic pyramid codes. We also establish a necessary condition for any failure pattern to be ever recoverable, and show that the generalized pyramid codes are optimal in failure recovery (i.e., the necessary condition is also sufficient, and any failure pattern that is ever recoverable can indeed be recovered).

Video-on-demand in the Internet has become an immensely popular service in recent years. But due to its high bandwidth requirements and popularity, it is also a costly service to provide. We consider the design and potential benefits of peer-assisted video-on-demand, in which participating peers assist the server in delivering VoD content. The assistance is done in such a way that it provides the same user quality experience as pure client-server distribution. We focus on the single-video approach, whereby a peer only redistributes a video that it is currently watching.

The paper describes DISCOVR, a distributed collaborative video recorder. DISCOVR is a P2P application that combines asynchronous file sharing with synchronous on-demand media streaming. DISCOVR uses a flat entity ID space, with the entity being any of the media file, header, mega packets, index and metadata. All DISCOVR entities may be asynchronously or synchronously distributed. DISCOVR adopts a sender-driven priority based sharing protocol. If the user is on-demand viewing a media file, those packets that are to be viewed in the near future will be put on the synchronous access list, which prompts its connected peers and the peers that are indirectly connected to fulfill the distribution of the on-demand packets in high priority. By letting the peers engage in both asynchronous sharing and synchronous on-demand streaming, DISCOVR promotes the peers to remain online longer, thus improve the availability of the P2P system and the overall performance