Modern data centers host a plethora of interactive data-intensive applications. These are known to often generate large numbers of short-lived parallel flows that must complete their transfer quickly to meet the stringent performance requirements of interactive applications. Network resources (e.g., switch buffer space) in the data center are scarce and are easily congested, which unfortunately results in long latency. As a first solution, following a traditional design rationale, Data Center TCP (DCTCP) was proposed to speed up the completion time of short-lived flow by maintaining a low buffer occupancy in the switch. In general, DCTCP performs well in homogeneous environments, however, its performance degrades quickly in heterogeneous environments or when it uses a large initial congestion window. To resolve this problem, we propose a Hypervisor-based congestion watching mechanism (HWatch), which measures the network load in the data center via ECN and uses the resulting statistics to determine the appropriate initial congestion window size to avoid congestion. HWatch neither needs modification to the TCP stack in the VMs nor requires any specialized network hardware features to meet its targets. In our evaluation, we demonstrate the benefits of HWatch in improving the performance of TCP flows through large-scale ns2 simulation and via testbed experiments in a small data center.

In data center networks, flows with different objectives coexist and compete for limited resources. From the application-level perspective, it is hard to satisfy the demands of different flows without effective resource planning. To address the bandwidth allocation problem under multi-objective scenarios, we study a multi-objective network utility maximization (NUM) problem and propose our practical bandwidth allocation framework HOMMO, which consists of an upper layer algorithm (ULA) and a lower layer algorithm (LLA). This hierarchical design helps to strike a balance between accuracy and efficiency. Implemented in network switches, ULA is an online learning-based scheme that allocates bandwidth for aggregated flows with different performances objectives. Taking the outputs from ULA as capacity constraints, LLA acts as a fast scheduling method at packet-level. We extend NUMFabric by implementing the design of isolate queues and corresponding dequeue strategy in switches and make it a feasible solution of the LLA. Therefore, HOMMO achieves satisfactory isolation across flows with different objectives, which is equivalent to provide a network slicing solution. To evaluate the proposed framework, we implement it in ns-3 and verify the performance under various scenarios. The simulation results show that HOMMO not only quickly converges to a near-optimal solution of the multi-objective NUM problem but also guarantees a Pareto-optimal solution. Moreover, it outperforms the well-known transport protocol (i.e., DCTCP) with 2x increase on average bandwidth utilization and 1.96x improvement in global network utility at the aggregated flow level.

Datacenter networked applications, often require multiple data transfer flows that semantically constitute a coflow group. A coflow is thus considered completed when all the transfers in the coflow are completed. Hence, application performance is optimized whenever the completion time of a coflow is minimized, rather than that of the flows composing it. Currently, popular coflow scheduling algorithms are mostly centralized, and they incur high overheads. The decentralized approach in the “many-to-many” scenario also incurs high communication overheads due to the communication among the local controllers. In this paper, we present a coflow scheduling mechanism that aims to minimize the coflow completion time for coflows that show a many-to-many communication pattern, and as a byproduct communication overhead cost is also minimized. Our algorithm preserves compatibility with existing commodity switches and network protocols and improves the coflow completion times on average by 1.8 times compared to the baseline as demonstrated via testbed implementation and large-scale simulation.

In cloud environments, interactive applications deployed in data centers often generate swarms of short-lived data transfers (or flows) that face dramatic competition for the scarce switch buffer space from other short-lived as well as the long-lived flows. In the presence of bloated queues, such short-lived flows often experience multiple packet losses per round-trip time which often triggers the timeout-based loss recovery mechanism. A direct consequence of this is an inflated application response time that turns out to be orders of magnitude larger than what it should be. A data center aware TCP protocol (DCTCP) was designed as a new TCP specifically to address this issue, however, it does not consider its co-existence with other transport protocol (e.g., CuBIC and NewReno of Linux). In such situations, which are abundant in multi-tenant data centers, the legacy large initial congestion window sizes (e.g., 10 segments), induce multiple packet losses at the onset of a TCP flow, which forces timeout and even binary exponential backoff. In this paper, we propose a novel Hypervisor-based, application-transparent approach for active congestion probing to enable the hypervisor to infer on-path congestion before the TCP connection is fully established for new traffic to avoid such massive packet losses and timeout. The so-called ProBoSCIS mechanism does not require any changes to TCP, works with all versions of TCP and does not need any special network hardware features other than those that exist in today's data center commodity switches. We show its effectiveness via ns2 simulation and demonstrate its practical feasibility by implementing and deploying it in a small-scale data center test-bed. We show the significant reduction in application latency by adopting ProBoSCIS in a series of real experiments.

As data-parallel applications process more complex data, the dependencies between computation jobs in a multi-stage job also become more complicated. However, most of the existing scheduling solutions primarily rely on total bytes sent (job size) to differentiate jobs where jobs with fewer? bytes sent are prioritized over the larger ones. This approach overlooks the fact that jobs may consist of multiple computation stages, and that the completion of a computation job stage depends on the completion of other jobs' stage. In this paper, we present a coflow scheduler of multi-stage jobs that minimizes the average job completion time. Our solution prioritizes jobs based on the multi-faceted characteristics of multi-stage job structure per stage, instead of total bytes sent. Our experiments show that our approach provides twice the performance of existing solutions on average and by four times in bursty traffic scenario.

ECN is a powerful tool that can achieve low latency and high throughput simultaneously. Support ECN for multiqueue scenarios is an industry trend in datacenter networks. However, ECN schemes developed for per-port marking cannot be applied directly to the multi-queue scenarios. It hurts at least one metric among latency, throughput, and the scheduling policy. State-of-the-art multi-queue ECN marking schemes each has its own limitations. In this paper, we present per-Port Marking with Selective Blindness (PMSB). The intuition is that: if a flow is found to be a victim of per-port marking, we can either revoke the marking or cancel the flow back-off even if its packets qualify the per-port threshold (i.e., selective blindness). By breaking the fixed causal relationship between ECN marking and flow backoff, flows from un-congested queues can be protected. We evaluate PMSB with large-scale NS-3 simulations. Our results demonstrate that PMSB can preserve a given scheduling policy. Compared with the current practice, PMSB can reduce the average/99% completion time for small flows by 64.49%/72.89% respectively while delivering a slightly better performance for large flows.

In response to poor quality of experience (QoE), users self-regulating, i.e. they immediately release bandwidth and abandon network. However, there are studies that show users are willing to tolerate poor QoE for some time to evaluate if network performance will improve before abandoning the network. In this paper, we investigate how users willingness to wait for improved QoE may influence network activities, such as network pricing, bandwidth allocation, network revenue, and performance. We develop and employ a self-regulation model that includes user evaluation of QoE before deciding to abandon or stay in the network. This model considers these two factors: user tolerance of low QoE and the price per unit a user is willing to pay. Our investigation uncovers a double edged problem - network may be populated with lower paying users, who are also dissatisfied. These lower paying users drive the price higher than the price produced by conventional solution for network congestion. This leads to our proposal for a market informed congestion control scheme, where network resolves congestion based on user profile that is defined by their ability to pay and demand for bandwidth.

Advances in smartphone technologies enable mobile data subscribers to resell their data allowance to other users, creating a secondary data market. The trading environment of this secondary data market is dynamic and ad-hoc: buyers and sellers join and leave the market at all times, changing the trading landscape constantly. The amount of data demanded and offered at any point in time also vary. These conditions make determining a fair transaction price, and matching buyers to sellers difficult in practice. Prior schemes utilize global description of the network and market forces to achieve good performance, but the implementation requires a high overhead cost. In this paper, we present DataMart, a data pricing and user matching platform for trading in this dynamic, ad-hoc and heterogeneous market that works in distributed manner without needing global information. Using insights from real world traces, we demonstrate via simulation that our pricing scheme is converging and consistent with the law of demand and supply. Further, our user matching scheme achieves comparable performance to the optimal solution. We implement a prototype on Android platform, and the experiment results confirm the effectiveness of DataMart.

We describe an emerging application of data mining in the context of computer networks. This application concerns the problem of predicting the size of a flow and detecting elephant flows (very large flows). Flow size is a very important statistic that can be used to improve routing, load balancing and scheduling in computer networks. Flow size prediction is particularly challenging since flow patterns continuously change and predictions must be done in real time (milliseconds) to avoid delays. We describe how to formulate the problem as an online machine learning task to continuously adjust to changes in flow traffic. We evaluate the predictive nature of a set of features and the accuracy of three online predictors based on neural networks, Gaussian process regression and online Bayesian Moment Matching on three datasets of real traffic. We also demonstrate how to use such online predictors to improve routing (i.e., reduced flow completion time) in a network simulation.

Coflow scheduling can improve application-level communication performance for data-parallel clusters. However, most prior coflow scheduling schemes are based on the centralized approach, which achieve good performance but suffers from high control overhead and scalability issue. On the other hand, state of the art decentralized solution requires switch modification, which makes it hard to implement. In this paper, we present Stream, the decentralized and readilyimplementable solution for coflow scheduling. The key idea of Stream is to opportunistically take advantage of many-to-one and many-to-many coflow patterns to coordinate coflows without resorting to the centralized controller, and then emulate shortest coflow first scheduling to minimize the average coflow completion time (CCT). We implement Stream with existing commodity switches and show its performance using both testbed experiments and large-scale simulations. Our evaluation results show that Stream's performance is comparable to the centralized solution, and outperforms the state of the art decentralized scheme by 1.77x on average.

We investigate emerging proximity-based Mobile Crowd Service or pMCS systems, in which services are provided and consumed by users carrying smart mobile devices (e.g., smartphones) and in proximity of each other (e.g., within Bluetooth range). Due to limited resources on smartphones, it is crucial to provide a mechanism to incentivize users' participation and ensure fair trading in a pMCS system. In this paper, we design a multi-market dynamic double auction mechanism for a pMCS system, referred to as MobiAuc, and we show that it is truthful, feasible, individual-rational, no-deficit, and computationally efficient. The novelty and significance of MobiAuc is that it addresses and solves the fair trading problem in a multi-market dynamic double auction setting which naturally occurs in a mobile wireless environment. We demonstrate its efficiency via simulations based on generated user patterns (stochastic arrivals and random market clustering of users) and real-world traces. Our preliminary implementation of MobiAuc and experiments on Android platform have demonstrated the feasibility of MobiAuc mechanism in practice.

When natural disasters strike, network infrastructure is often completely destroyed, disabling communication; this significantly hampers rescue and relief efforts. Therefore, emergency communication network infrastructure must be deployed to provide communication at ground zero to rescue and relief agencies. The deployment strategy has to consider these humanitarian agencies' varying degrees of responsibilities which correspond to their levels of communication needs. In this paper, we propose a more precise deployment of emergency communication network based on our field study of how relief organizations collaborated at ground zero in Aceh, Indonesia, post Tsunami 2004. Building on our field findings, the emergency communication deployment is formulated to a k-Weighted Deployment problem, achieving a more customized delivery of communication network services to organizations according to their varying level of responsibilities and communication needs, including resource provisioning strategy. Finally, we devise a two-stage implementation protocol to achieve the objective of a more effective and targeted deployment to areas affected by natural disasters.

The growing popularity for video based applications has put an enormous strain on the network and causes the network to be more prone to congestion. The study of congestion control and bandwidth allocation problems is often formulated into Network Utility Maximization (NUM) framework, and the existing solutions for NUM generally focus on single-layered applications. However, today's quality of video is divided into several layers, where each layer provides different level of enhancement of quality. In this paper, we study how multi-layered video based applications impact network performance and pricing through NUM formulation, in particularly traffic from video streaming. In our investigation, we design and implement a new multi-layered user utility model that leverages on studies of human visual perception. Then, using this new utility model to examine network activities, we demonstrate that solving NUM with multi-layered utility is intractable, and that rate allocation and network pricing may oscillate due to user behavior specific to multi-layered applications. To address this, we propose a new approach for admission control to ensure quality of service and experience.

There is a fast growing number of public spaces offering Wi-Fi access to meet the rising demands for Internet access. It is common for such service to be offered to users at no charge or for a flat fee. Both situations provide very little incentive for Wi-Fi providers to offer better service to the users. Similarly, Wi-Fi providers pay a monthly flat rate to ISP for Internet access and, this too does not incentivize ISP to offer better service to Wi-Fi users. As a result, Wi-Fi users may experience poor connection when network becomes congested during peak hours. In this paper we propose a dynamic pricing scheme for Internet access and a revenue sharing mechanism that provides incentives for both ISP and Wi-Fi providers to offer better service to their users. We build our revenue sharing model based on Shapley value mechanism. Importantly, our proposed revenue sharing mechanism captures the power negotiation between ISP and Wi-Fi providers, and how shifts in power influences revenue division. Specifically, the model assures that the party who contributes more receives a higher portion of the revenue. In addition, our simulation demonstrates that our model captures the bargaining power shifts between Wi-Fi providers and ISP, and shows that the division of revenue asymptotically converges to a percentage value.

There is a fast growing number of public spaces offering Wi-Fi access to meet the rising demands for the Internet. It is common for such service to be offered to users at no charge or for a flat fee. Both situations provide very little incentive for Wi-Fi providers to offer better service to the users. Similarly, Wi-Fi providers pay a monthly flat-rate to ISP for Internet access, which does not incentivize ISP to offer better service to Wi-Fi users. As a result, Wi-Fi users may experience poor Internet connection when network becomes congested during peak hours. In this paper, we propose a dynamic pricing mechanism for both ISP and Wi-Fi providers in order to give mobile Wi-Fi users better service, while providing economic incentive for both ISP and Wi-Fi provider.

Network Utility Maximization (NUM) has been studied extensively to improve network quality of service (QoS) and to overcome network congestion. However, even with congestion resolved, network is not always able to meet user's minimum demand for QoS. To address this issue, this paper proposes a new "self-regulate" model that considers user tolerance for poor QoS and the price user is willing to pay. In addition, we demonstrate that user "self- regulate" model may not lead to convergence as today's Internet user landscape changes constantly and quickly. This leads to our proposal for an admission control algorithm which considers network revenue, user tolerance, and user utility.

Cellular Network Providers (CNP) provide users with wireless data access to meet the growing ubiquitous demand for the Internet. As users subscribe to a fixed data plan for a monthly flat fee, some users may exhaust their data allowance before the end of the billing cycle, while others underutilize their monthly quota. To take advantage of such underutilization, Khausik et. al. propose a mechanism for ad hoc bandwidth redistribution that allows subscribers to sell their unused bandwidth to users needing Internet access in exchange for some financial compensation as and when opportunities arise. There exists a popular belief that allowing such on-demand ad hoc service is not beneficial to CNP. This paper seeks to address and counter this opinion by proposing a pricing scheme and a revenue sharing mechanism that makes the provision of ad hoc connection advantageous to CNP. Our revenue sharing mechanism provides economic incentives to CNP. The simulation results show that our revenue sharing model ensures that CNP receives the majority portion of the revenue gained, regardless of the amount. Secondly, our pricing model ensures traffic from ad hoc users has minimal impact on the connection quality of current subscribers. In this model, we use Shapley value as the basis for deriving the revenue sharing.

Feedback mechanism based algorithms are frequently used to solve network optimization problems. These schemes involve users and network exchanging information to achieve convergence towards an optimal solution. However, in implementation, these algorithms do not guarantee messages will be delivered to the destination, especially when network congestion occurs, which in turn often results in packet drops. This condition may lead to algorithm failing to converge. To prevent this, we propose least square (LS) estimation algorithm to recover the missing information when packets are dropped from the network. Our results from several scenarios demonstrate that LS estimation can provide the convergence for feedback mechanism based algorithm.

This paper primarily addresses how available bandwidth should be optimally distributed among competing streams of elastic traffic like TCP traffic while taking Quality-of-Service (QoS) and delay into consideration. Network Utility Maximization (NUM) in [1], a congestion control algorithm, allows users to set for an optimum network-wide rate allocation through their utility. By incorporating delay into utility function, users can accommodate for QoS requirements.