In this paper we focus on the problem of optimizing email volume for maximizing sitewide engagement of an online social networking service. Email volume optimization approaches published in the past have proposed optimization of email volume for maximization of engagement metrics which are impacted exclusively by email; for example, the number of sessions that begin with clicks on links within emails. The impact of email on such downstream engagement metrics can be estimated easily because of the ease of attribution of such an engagement event to an email. However, this framework is limited in its view of the ecosystem of the networking service which comprises of several tools and utilities that contribute towards delivering value to members; with email being just one such utility. Thus, in this paper we depart from previous approaches by exploring and optimizing the contribution of email to this ecosystem. In particular, we present and contrast the differential impact of email on sitewide engagement metrics for various types of users. We propose a new email volume optimization approach which maximizes sitewide engagement metrics, such as the total number of active users. This is in sharp contrast to the previous approaches whose objective has been maximization of downstream engagement metrics. We present details of our prediction function for predicting the impact of emails on a user's activeness on the mobile or web application. We describe how certain approximations to this prediction function can be made for solving the volume optimization problem, and present results from online A/B tests.

Online social networking services distribute various types of messages to their members. Common types of messages include news, connection requests, membership notifications, promotions and event notifications. Such communication, if used judiciously, can provide an enormous value to members thereby keeping them engaged. However sending a message for every instance of news, connection request, or the like can result in an overwhelming number of messages in a member's mailbox. This may result in reduced effectiveness of communication if the messages are not sufficiently relevant to the member's interests. It may also result in a poor brand perception of the networking service. In this paper we discuss our strategy and experience with regard to the problem of email volume optimization at LinkedIn. In particular, we present a cost-benefit analysis of sending emails, the key factors to administer an effective volume optimization, our algorithm for volume optimization, the architecture of the supporting system and experimental results from online A/B tests.

We present a new set of solutions for topology verification and failure localization in Software Defined Networks (SDNs). Our solutions are targeted towards offloading the control plane as much as possible and bringing more resilience against congestion or partitioning in the control plane. The core idea is to define control flows for network diagnosis and utilize a fraction of the forwarding table rules on the switches to serve these control flows. For topology verification, we present provably optimal or order-optimal solutions in total number of static forwarding rules and control messages. For single link failure localization, we present a solution that requires at least 3 |E| but at most 6 |E| forwarding rules using at most 1+log2 |E| control messages, where |E| denotes the number of bidirectional links in the forwarding plane. We analyze the latency vs. rule and control message optimality trade-offs showing that sub-second failure localization is possible even in data center scale networks without significant additional overhead in the number of static rules and control messages. We further simulate the performance of failure localization in identifying multiple link failures.

Recent literature including our past work provides analysis and solutions for using: 1) erasure coding; 2) parallelism; or 3) variable slicing/chunking (i.e., dividing an object of a specific size into a variable number of smaller chunks) in speeding up the I/O performance of storage clouds. However, a comprehensive approach that considers all three dimensions together to achieve the best throughput-delay tradeoff curve had been lacking. This paper presents the first set of solutions that can pick the best combination of coding redundancy ratio and object chunking/slicing options as the load dynamically changes. Our specific contributions are as follows: 1) We establish via measurements that combining variable redundancy ratio and chunking is mostly feasible over a popular public cloud. 2) We relate the delay-optimal values for chunking level and code redundancy ratio to the queue backlogs via an approximate queuing analysis. 3) Based on this analysis, we propose TOFEC that adapts the chunking level and redundancy ratio against the queue backlogs. Our trace-driven simulation results show that TOFEC's adaptation mechanism converges to an appropriate code that provides the optimal throughput-delay tradeoff without reducing system capacity. Compared to a nonadaptive strategy optimized for throughput, TOFEC delivers 2.5× lower latency under light workloads; compared to a nonadaptive strategy optimized for latency, TOFEC can scale to support over 3× as many requests. 4) We propose a simpler greedy solution that performs on a par with TOFEC in average delay performance, but exhibits significantly more performance variations.

We consider a heterogeneous network scenario where macro cells provide continuous coverage and many small cells with short transmission ranges within the coverage area of each macro cell provide high capacity access. We focus on scenarios where most small cells can be put on the sleep mode and macro cell capacity is sufficient for serving a large fraction of user population. Few users generate high demand and thus a small fraction of small cell base stations (SC-BS) that can serve these users should be ideally powered on to offload the macro cell base station (MC-BS). As different sets of users create demand surge over time, a network controller should keep track of peak demand locations and power on a minimal number of SC-BSs. We propose a new solution to this end. Our solution iteratively determines which SC-BSs should be turned on and performs power control to dictate the coverage area of each SC-BS. We use the flow byte counters on the MC-BS and active SC-BSs to form a system of linear equations and use linear optimization using L1norm of the demand vector as the objective function to localize the demand. Our evaluations indicate that the solution is quite effective in tracking the peak demand locations. For instance in one particularly challenging scenario with heavy-tailed i.i.d. spatial distribution for peak demand, 80% of the peak demand locations were identified correctly more than 90% of the time using less than 7% of the SC-BSs.

With the rapid proliferation of smartphones, hundreds of millions of mobile users are attracted to Instant Messaging (IM) apps. While such apps have brought convenience to our life, it comes with the price of great energy consumption, as these apps keep sending heartbeat messages to the server periodically in order to maintain an always-online connection. These frequent and fragmented transmissions result in a considerable amount of energy waste. In this paper, we investigate the "cost and potential of heartbeats". We quantify power consumption of heartbeats of real-world IM apps through extensive measurements. The measurement results confirm that huge power consumption is induced by heartbeats. The goal of this paper is to save energy by turning the energy wastage of heartbeats into transmitting useful data. Thus, we develop eTrain, a transmission management system running on Android phones, which takes advantage of IM heartbeats (as trains) to piggyback aggregated delay-tolerant apps' data such as e-mail and Weibo (as cargoes) via an online transmission strategy, so as to minimize the cumulative tail energy without sacrificing user-specified deadlines. Compared to other existing works, eTrain can reduce more energy consumption under the same settings. Experiments conducted on smartphones show that eTrain can achieve 12%-33% energy saving in various application scenarios.

We investigate near-optimal load balancing and auto-scaling solutions that can get the best delay performance while attaining high utilization in two-tier cloud storage systems. The first tier consists of a distributed cache composed of leased resources from a computing cloud (e.g., Amazon EC2) and the second tier consists of a persistent distributed storage (e.g., Amazon S3). At any point in time our solutions dynamically determine how many cache servers should be active as the incoming load, object popularities, and service rate of persistent storage are subject to change. We first present a load balancing solution for a given set of cache servers that can evenly distribute the load against workloads with an unknown Zipf distribution while keeping the overall cache hit ratios close to the maximum. Building on this load balancer, we then present our auto-scaling solution that uses the request backlogs in the caching tier to determine the number of active cache servers to be used in the next epoch. Via simulations, we show that the end-to-end design is quite effective in converging to the right amount of service capacity against the system dynamics.

Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.

Software Defined Networks (SDN) decouple the forwarding and control planes from each other. The control plane is assumed to have a global knowledge of the underlying physical and/or logical network topology so that it can monitor, abstract and control the forwarding plane. When parts of the control plane become unavailable or unreliable, individual controllers should still be able to monitor the forwarding plane and run diagnostics to take the correct routing actions. In our paper, we present solutions that install an optimal or near-optimal number of static forwarding rules on switches/routers for any controller to be able to verify the topology connectivity and detect/locate link failures at data plane speeds without relying on state updates from forwarding plane nodes and other controllers while requiring reachability to only one (arbitrary) forwarding node. Our upper bounds on performance indicate that sub-second link failure localization is possible even at data-center scale networks. For networks with hundreds or few thousand links, tens of milliseconds of latency is achievable.

Our paper presents solutions using erasure coding, parallel connections to storage cloud and limited chunking (i.e., dividing the object into a few smaller segments) together to significantly improve the delay performance of uploading and downloading data in and out of cloud storage. TOFEC is a strategy that helps front-end proxy adapt to level of workload by treating scalable cloud storage (e.g. Amazon S3) as a shared resource requiring admission control. Under light workloads, TOFEC creates more smaller chunks and uses more parallel connections per file, minimizing service delay. Under heavy workloads, TOFEC automatically reduces the level of chunking (fewer chunks with increased size) and uses fewer parallel connections to reduce overhead, resulting in higher throughput and preventing queueing delay. Our trace-driven simulation results show that TOFEC's adaptation mechanism converges to an appropriate code that provides the optimal delay-throughput trade-off without reducing system capacity. Compared to a non-adaptive strategy optimized for throughput, TOFEC delivers 2.5× lower latency under light workloads; compared to a non-adaptive strategy optimized for latency, TOFEC can scale to support over 3× as many requests.

Our paper presents solutions that can significantly improve the delay performance of putting and retrieving data in and out of cloud storage. We first focus on measuring the delay performance of a very popular cloud storage service Amazon S3. We establish that there is significant randomness in service times for reading and writing small and medium size objects when assigned distinct keys. We further demonstrate that using erasure coding, parallel connections to storage cloud and limited chunking (i.e., dividing the object into a few smaller objects) together pushes the envelope on service time distributions significantly (e.g., 76%, 80%, and 85% reductions in mean, 90th, and 99th percentiles for 2-MB files) at the expense of additional storage (e.g., 1.75$\times$). However, chunking and erasure coding increase the load and hence the queuing delays while reducing the supportable rate region in number of requests per second per node. Thus, in the second part of our paper, we focus on analyzing the delay performance when chunking, forward error correction (FEC), and parallel connections are used together. Based on this analysis, we develop load-adaptive algorithms that can pick the best code rate on a per-request basis by using offline computed queue backlog thresholds. The solutions work with homogeneous services with fixed object sizes, chunk sizes, operation type (e.g., read or write) as well as heterogeneous services with mixture of object sizes, chunk sizes, and operation types. We also present a simple greedy solution that opportunistically uses idle connections and picks the erasure coding rate accordingly on the fly. Both backlog-based and greedy solutions support the full rate region and provide best mean delay performance when compared to the best fixed coding rate policy. Our evaluations show that backlog-based solutions achieve better delay performance at higher percentile values than the greedy solution.

In this paper, we compare performance of several Byzantine agreement algorithms, including NCBA, a network coding based algorithm. Unlike existing practical BFT protocols such as PBFT by Castro and Liskov [1], which utilize collision-resistant hash functions to reduce traffic load for BFT, NCBA uses a computationally efficient error-detection network coding scheme. Since NCBA does not rely on any hash function, it is always correct rather than correct only with high probability as PBFT. Through extensive experiments, we verified that NCBA performs at least as well as Digest, without relying on any cryptographic assumption on the hardness of breaking the hash function. To the best of our knowledge, this is the first implementation of BFT with network coding.

The goal of Byzantine Broadcast (BB) is to allow a set of fault-free nodes to agree on information that a source node wants to broadcast to them, in the presence of Byzantine faulty nodes. We consider design of efficient algorithms for BB in synchronous point-to-point networks, where the rate of transmission over each communication link is limited by its "link capacity". The throughput of a particular BB algorithm is defined as the average number of bits that can be reliably broadcast to all fault-free nodes per unit time using the algorithm without violating the link capacity constraints. The capacity of BB in a given network is then defined as the supremum of all achievable BB throughputs in the given network, over all possible BB algorithms.

This paper proves a necessary and sufficient condition for the existence of iterative, algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed edge represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. The following convergence requirement is imposed: for any ε > 0, after a sufficiently large number of iterations, the states of the fault-free nodes are guaranteed to be within ε of each other.

We consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. We propose an algorithm structure for achieving agreement capacity in general networks. We also introduce capacity achieving algorithms for two classes of networks: (i) arbitrary four-node networks with at most 1 failure; and (ii) symmetric networks of arbitrary size.

In this paper, we present an efficient deterministic algorithm for consensus in presence of Byzantine failures. Our algorithm achieves consensus on an L-bit value with communication complexity O(nL + n4L0.5 + n6) bits, in a network consisting of n processors with up to t Byzantine failures, such that t

We consider the problem of misbehavior detection in wireless networks. A commonly adopted approach is to exploit the broadcast nature of the wireless medium, where nodes monitor their downstream neighbors locally using overheard messages. We call such nodes the Watchdogs. We propose a lightweight misbehavior detection scheme which integrates the idea of watchdogs and error detection coding. We show that even if the watchdog can only observe a fraction of packets, by choosing the error detection code properly, an attacker can be detected with high probability while achieving throughput arbitrarily close to optimal. Such properties reduce the incentive for the attacker to attack. We then consider the problem of locating the misbehaving node and propose a simple protocol, which locates the misbehaving node with high probability. The protocol requires exactly two watchdogs per unreliable relay node.

In this paper, we propose Opportunistic Carrier Prediction (OCP) that jointly addresses exposed terminal and hidden terminal problems in wireless networks. OCP is based on the rationale that past interference information can be a good indicator for the outcome of future packet delivery. Each OCP sender maintains a summary of past interference information and opportunistically accesses the channel when it is confident that the packet transmission will be successful and cause no collision to other flows. To realize OCP, we propose (1) a novel data structure for each sender to summarize the interference information and (2) physical layer preemptive decoding scheme for each sender to collect the identities of the interferers. We show that OCP improves the system throughput by up to 170%, packet delivery success ratio by up to 400% in random topologies, while almost eliminating starvation.

In this paper, we consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. The notion of throughput here is similar to that used in the networking/communications literature on unicast or multicast traffic. We identify necessary conditions for an agreement throughput of R to be achievable. We also provide tight sufficient conditions by construction for agreement throughput R in four-node networks.

In wireless sensor networks (WSN), energy efficiency is crucial to achieving satisfactory network lifetime. The most commonly used and may be the only efficient method to reduce the energy consumption significantly is to turn off the radios most of the time, except when it has to participate in data communication. The key challenge is to operate the radio at a low duty cycle but still ensure the delay is relatively low. Various power-saving medium-access control (MAC) protocols have been proposed along this thread. However, most of such protocols focus on a point-to-point communication setting, in which a node will drop an overheard packet if it is not the destination. On the other hand, cooperative wireless communication has been drawing extensive attention in the past few years. Node cooperation has been exploited to reduce end-to-end delay, improve transmission reliability, etc. However, not much has been done in utilizing node cooperation to save energy. This idea may sound absurd since cooperation requires more nodes involved in a communication and would result in more energy being consumed. But is this true? In this paper, we will exploit the possibility of cooperative power saving in wireless ad-hoc networks. The trade-off between energy consumption and delay will be studied. Interestingly, our analytical and simulation results show that cooperation can indeed help achieve a better delay-power consumption trade-off. Our results also show that cooperation together with asymmetric power allocation can achieve the optimal delay-power trade-off.

We study the optimal streaming of variable bit-rate (VBR) video over a random VBR channel. The goal of a streaming application is to enable the successful decoding of each video object before its displaying deadline is violated. Hence, we define the main performance metric of a streaming system as the probability of un-interrupted video presentation, or jitter-free probability. Previous literature has described solutions to estimate the jitter-free probability by assuming either independence in the encoded data process or simplistic channel models. In this work, we present a novel analytical framework, which requires only some basic statistical information of an arbitrary VBR channel, to bound the probability of jitter-free playout under the constraint of initial playout delay and receiver buffer size. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modeled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded video demonstrates that the proposed analysis derives close bounds to the actual system performance. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoffs between the initial playout delay, the receiver buffer size, and the jitter-free probability for a general class of VBR streaming over random VBR channels.

The main goal of a streaming application is to enable the successful decoding of each video object before its displaying deadline is violated, and to recover from a deadline violation properly. Hence, we define the main performance metric of a streaming system as the number of interruptions during a video presentation, or the number of jitters. Previous literature has described solutions to estimate the jitter-free probability for an entire video segment. In this work, we present a novel analytical framework, which requires only a Markov Variable Bit Rate (VBR) channel model, to study the frequency of jitters under the constraint of initial playback delay, receiver buffer size, and different jitter recovering schemes. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modeled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded video validate our analysis. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoffs between the jitter frequency, jitter recovering delay, initial delay, and the receiver buffer size for a general class of VBR streaming over random VBR channels with different jitter recovering schemes.

In this paper, we study the optimal streaming of variable bit-rate (VBR) videos over random VBR channels. We define the main performance metric of a streaming system as the probability of un-interrupted video presentation, or jitter-free probability. Previous literature has described solutions to estimate the jitter-free probability by assuming either independence in the encoded data process or simplistic channel models. In this work, we present an novel analytical framework, which requires only the maximum channel bit rate and some statistical information of an arbitrary VBR channel, to bound the probability of jitter-free playback under the constraint of initial playback delay and receiver buffer size. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modelled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded videos show that the proposed analysis provides close bounds to the actual system performance. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoff between initial playback delay, receiver buffer size, and the jitter free probability for a general class of VBR video streaming over random VBR channels.