State migration is a crucial aspect of managing stateful stream processing applications, enabling load balancing, fault tolerance, and dynamic scaling. Existing state migration solutions make performance trade-offs between completion time, latency spike, and system overhead; however, they lack the flexibility to adjust these trade-offs across different application scenarios. In this paper, we propose Spacker, a unified framework that enables configurable state migration for flexible performance trade-offs. Spacker decomposes state migration into fine-grained key-level operations and introduces an abstraction of planning strategy, featuring three tuning knobs, that allow for flexible planning of operations. To further improve the efficiency, we design a non-disruptive migration protocol that minimizes the blocking of data processing during state migration. We have integrated Spacker with Apache Flink and implemented an adaptive planning strategy as an example that realizes the abstraction. Our results show that Spacker, with the planning strategy, can make adaptive planning decisions, based on analyzing the decision trade-offs under varying workload characteristics. It can reduce latency spikes while maintaining appropriate completion time and system overhead compared to statically configured migration solutions.

Currently, deduplication techniques are utilized to minimize the space overhead by deleting redundant data blocks across large-scale servers in data centers. However, such a process exacerbates the fragmentation of data blocks, causing more cross-server file retrievals with plummeting retrieval throughput. Some attempts prefer better file retrieval performance by confining all blocks of a file to one single server, resulting in non-trivial space consumption for more replicated blocks across servers. An ideal network storage system, in effect, should take both the deduplication and retrieval performance into account by implementing reasonable assignment of the detected unique blocks. Such a fine-grained assignment requires an accurate and comprehensive abstraction of the files, blocks, and the file-block affiliation relationships. To achieve this, we innovatively design the weighted hypergraph to profile the multivariate data correlations. With this delicate abstraction in place, we propose HyperPart, which elegantly transforms this complex block allocation problem into a hypergraph partition problem. For more general scenarios with dynamic file updates, we further propose a two-phase incremental hypergraph repartition scheme, which mitigates the performance degradation with minimal migration volume. We implement a prototype system of HyperPart, and the experiment results validate that it saves around 50% of the storage space and improves the retrieval throughput by approximately 30% of state-of-the-art methods under the balance constraints.

Real-time streaming data is generated in high volumes and consumed for statistical and analytical purposes, requiring efficient and effective management by Message Queuing Systems (MQS) that ensure high throughput and low latency. ByteDance relies extensively on MQS to handle its massive streaming data across various applications. However, existing MQS solutions often fall short of meeting ByteDance's high-volume, diverse requirements. To address these challenges, we propose ByteMQ (BMQ), a cloud-native streaming data layer designed to manage ByteDance's extensive streaming data needs efficiently in the cloud. BMQ features three key designs: 1) separation of messaging and storage, utilizing ByteDance's Federated Distributed File System (DFS) for high-performance data storage; 2) adaptive resource scheduling to balance workloads and redistribute resources across multiple availability zones; and 3) historical data restructuring to support offline applications with efficient structured data management. ByteDance has migrated 99.76% of its Kafka clusters to BMQ infrastructure, achieving about a 70% reduction in resource costs. This paper shares our journey of designing and implementing BMQ, providing insights that may benefit other organizations facing similar challenges.

In stream processing applications, an operator is often instantiated into multiple parallel execution instances, referred to as executors, to facilitate large-scale data processing. Due to unpredictable changes in executor workloads, data tuples processed by different executors may exhibit varying latency. In particular, within the same operator, the executor with the maximum latency significantly impacts the end-to-end (E2E) latency of the application. Existing solutions, such as load balancing and horizontal scaling, which involve workload migration, often incur substantial time overhead induced by state migration and synchronization. In contrast, elastically scaling up/down resources of executors rather than moving workloads can not only effectively handle workload fluctuations but also offer rapid adjustments; however, prior works only considered CPU scaling with the assumption of sufficient memory.In this paper, we propose Emma, an elastic multi-resource manager. Emma leverages the resource elasticity of lightweight virtualization containers, e.g., Linux containers, to resize the resource of executors at runtime. The core of Emma is a multi-resource provisioning plan that conducts performance analysis and resource adjustment in real-time. We explore the relationship between resources and performance experimentally and theoretically, guiding the plan to adaptively allocate the appropriate combination of resources to each executor to 1) accommodate the dynamic workload; 2) efficiently utilize resources to enhance the performance of as many executors as possible. Additionally, we propose an online learning method that makes the manager seamlessly adapt to diverse stream applications. We integrate Emma with Apache Samza, and our experiments show that compared to existing solutions, Emma can significantly reduce latency by orders of magnitude in real-world applications.

The continuous growth of Internet traffic, especially video content, presents challenges for access providers (APs) who must upgrade their infrastructure to meet increasing demands. Ensuring a high-quality experience (QoE) for end-users and finding ways to monetize network resources are key concerns. Guaranteeing QoE is complex, as it depends not only on link capacity but also on competing traffic flows and shared network data plane buffers. To address these challenges, we proposeDiffPerf, an in-network, online, and dynamic allocation system.DiffPerfoperates at both macroscopic and microscopic levels. At the macroscopic level, it elastically allocates bandwidth to performance-centric service classes defined by APs to accommodate different performance requirements. At the microscopic level,DiffPerfemploys a lightweight data-driven algorithm to statistically differentiate and isolate traffic flows within each class, improving their performance. We implementedDiffPerfprototypes using SDN-based technology, one with OpenDaylight and OpenFlow hardware switches, and the other with programmable Intel Tofino switches. Our evaluation focused on on-demand video streaming. The results demonstrate thatDiffPerfoffers APs a range of allocation choices while ensuring strong performance isolation. Additionally,DiffPerfimproves fairness and enhances overall user-perceived QoE within each class. Notably,DiffPerfconserves bandwidth and delivers a QoE improvement approximately$4.6\times $higher than TCP BBR, the most popular congestion control mechanism on the Internet.

In a streaming application, an operator is usually instantiated into multiple tasks for parallel processing. Tasks across operators have various memory demands due to different processing logic (e.g., stateful vs. stateless tasks). The memory demands of tasks from the same operator could also vary and fluctuate due to workload variability. Improper memory provision will cause some tasks to have relatively high latency, or even unbound latency that can eventually lead to system instability. We found that the task with the maximum latency of an operator has a significant and even decisive impact on the end-to-end latency.In this paper, we present our task-level memory manager. Based on our quantitative modeling of memory and task-level latency, the manager can adaptively allocate optimal memory size to each task for minimizing the end-to-end latency. We integrate our memory management on Apache Flink. The experiments show that our memory management could significantly reduce end-to-end latency for various applications at different scales and configurations, compared to the Flink native setting.

Distributed stream systems provide low latency by processing data as it arrives. However, existing systems do not provide latency guarantee, a critical requirement of real-time analytics, especially for stateful operators under burst and skewed workload. We present StreamSwitch, a control plane for stream systems to bound operator latency while optimizing resource usage. Based on a novel stream switch abstraction that unifies dynamic scaling and load balancing into a holistic control framework, our design incorporates reactive and predictive metrics to deduce the healthiness of executors and prescribes practically optimal scaling and load balancing decisions in time. We implement a prototype of StreamSwitch and integrate it with Apache Flink and Samza. Experimental evaluations on real-world applications and benchmarks show that StreamSwitch provides cost-effective solutions for bounding latency and outperforms the state-of-the-art alternative solutions.

Stream processing is widely used for real-time data processing and decision-making, leading to tens of thousands of streaming jobs deployed in ByteDance cloud. Since those streaming jobs usually run for several days or longer and the input workloads vary over time, they usually face diverse runtime issues such as processing lag and varying failures. This requires runtime management to resolve such runtime issues automatically. However, designing a runtime management service on the ByteDance scale is challenging. In particular, the service has to concurrently manage cluster-wide streaming jobs in a scalable and extensible manner. Furthermore, it should also be able to manage diverse streaming jobs effectively. To this end, we propose StreamOps to enable cloud-native runtime management for streaming jobs in ByteDance. StreamOps has three main designs to address the challenges. 1) To allow for scalability, StreamOps is running as a standalone lightweight control plane to manage cluster-wide streaming jobs. 2) To enable extensible runtime management, StreamOps abstracts control policies to identify and resolve runtime issues. New control policies can be implemented with a detect-diagnose-resolve programming paradigm. Each control policy is also configurable for different streaming jobs according to the performance requirements. 3) To mitigate processing lag and handling failures effectively, StreamOps features three control policies, i.e., auto-scaler, straggler detector, and job doctor, that are inspired by state-of-the-art research and production experiences at ByteDance. In this paper, we introduce the design decisions we made and the experiences we learned from building StreamOps. We evaluate StreamOps in our production environment, and the experiment results have further validated our system design.

As video streaming services become more popular, users desire high perceived video quality, which has placed more stringent requirements on the quality of connection. Existing issues of cellular networks encourage users to seek alternative connections such as public Wi-Fi networks; however, expectations of both users and owners of Wi-Fi networks are not sufficiently satisfied and various concerns are yet to be addressed by a better Wi-Fi access system. Based on a go-as-you-pay scheme, we design and implement DiFi, a per-user-based system with dynamic resource allocation and pricing. DiFi offers data burst that accommodates user requirements on the burstiness of traffic, in addition to bandwidth. It better caters to the various individual requirements of users, and better utilizes the limited network resources for the owners. We leverage the blockchain-based smart contract to address realistic concerns on decentralized control, privacy and trustiness and our implementation is compatible with existing Wi-Fi infrastructures.

Due to the long-run and unpredictable nature of stream processing, any statically configuredexecution of stream jobs fails to process data in a timely and efficient manner. To achieve performance requirements, stream jobs need to be reconfigured dynamically. In this paper, we present Trisk, a control plane that support versatile reconfigurations while keeping high efficiency with easy-to-use programming APIs. Trisk enables versatile reconfigurations with usability based on a task-centric abstraction, and encapsulates primitive operations such that reconfigurations can be described by compositing the primitive operations on the abstraction. Trisk adopts a partial pause-and-resume design for efficiency, through which synchronization mechanisms in the native stream systems can further be leveraged. We implement Trisk on Apache Flink and demonstrate its usage and performance under realistic application scenarios. We show that Trisk executes reconfigurations with shorter completion time and comparable latency compared to a state-of-the-art fluid mechanism for state management.

Continuing the current trend, Internet traffic is expected to grow significantly over the coming years, with video traffic consuming the biggest share. Despite numerous optimizations of the transport congestion control, and the switch butter sizing and management algorithms; however, the complex interaction among all of them still leads to uncertain user performance and thus degrades user-perceived quality, under various network and traffic conditions. The culprit is the difficulty to dynamically control the amount of bandwidth allocated to each of the competing flows under bottleneck due to the algorithms lack of visibility of butter content where the flows reside. We address this bandwidth allocation problem by proposing DiffPerf, an in-network system that relies on a lightweight learning algorithm to statistically differentiate and isolate user flows to help them achieve better performance in an online and dynamic manner. We built two SDN-based prototypes of DiffPerf; one on OpenDaylight with OpenFlow Brocade switch and the other with programmable data plane Barefoot Tofino switch. We evaluate it from an application perspective for ABR video streaming as it accounts for a majority of the Internet traffic. Our evaluations demonstrate the practicality and flexibility that DiffPerf assists users in achieving better fairness and improving overall user-perceived quality. On average DiffPerf yields a quality improvement of about $4.6\times$ and $1.2\times$ higher than TCP BBR and TCP CUBIC, respectively.

The intra-window join (IaWJ), i.e., joining two input streams over a single window, is a core operation in modern stream processing applications. This paper presents the first comprehensive study on parallelizing the IaWJ on modern multicore architectures. In particular, we classify IaWJ algorithms into lazy and eager execution approaches. For each approach, there are further design aspects to consider, including different join methods and partitioning schemes, leading to a large design space. Our results show that none of the algorithms always performs the best, and the choice of the most performant algorithm depends on: (i) workload characteristics, (ii) application requirements, and (iii) hardware architectures. Based on the evaluation results, we propose a decision tree that can guide the selection of an appropriate algorithm.

The emergence of large-scale dynamic sets in networked and distributed applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional${k}$candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

With the rise of video streaming and cloud services, the Internet has evolved into a content-centric service platform. Due to the best-effort service model of the Internet, the quality of service (QoS) of Internet services however cannot be guaranteed. Furthermore, characterizing QoS is challenging since it depends on the autonomous business decisions such as capacity planning, routing strategies and peering agreements of network providers. To quantify the QoS for Internet-based services, we regard the Internet infrastructure as a transport system for data packets and study the Internet ecosystem and the economics of transport services collectively provided by the autonomous network providers. In contrast to the traditional transport economics that studies the movement of people and goods over space and time, our focus in theInternet transport economicsis the movement of streams of data packets that create information services. In particular, we model the supply of network capacities and demands of throughput driven by network protocols and establish a macroscopic network equilibrium under which both the end-to-end delays and drop rates of Internet routes can be derived. We show that this equilibrium solution always exists and its uniqueness can be guaranteed under various realistic scenarios. We analyze the impacts of user demands and resource capacities on the network equilibrium and provide implications of Netflix-Comcast type of peering on the QoS of users. We demonstrate that our framework can be used as a building block to understand the routing strategies under a Wardrop equilibrium and to enable further studies such as Internet peering and in-network caching.

With the rapid growth of congestion-sensitive and data-intensive applications, traditional settlement-free peering agreements with best-effort delivery often do not meet the QoS requirements of content providers (CPs). Meanwhile, Internet access providers (IAPs) feel that revenues from end-users are not sufficient to recoup the upgrade costs of network infrastructures. Consequently, some IAPs have begun to offer CPs a new type of peering agreement, called paid peering, under which they provide CPs with better data delivery quality for a fee. In this article, we model a network platform where an IAP makes decisions on the peering types offered to CPs and the prices charged to CPs and end-users. We study the optimal peering schemes for the IAP, i.e., to offer CPs both the paid and settlement-free peering to choose from or only one of them, as the objective is profit or welfare maximization. Our results show that 1) the IAP should always offer the paid and settlement-free peering under the profit-optimal and welfare-optimal schemes, respectively, 2) whether to simultaneously offer the other peering type is largely driven by the type of data traffic, e.g., text or video, and 3) regulators might want to encourage the IAP to allocate more network capacity to the settlement-free peering for increasing user welfare.

Multi-party set reconciliation is a key component in distributed and networking systems. It naturally contains two dimensions, i.e., set representation and reconciliation protocol. However, existing sketch data structures are insufficient to satisfy the new needs brought by the multi-party scenario simultaneously, including space-efficiency, mergeability, and completeness. The current reconciliation protocols, on the other hand, fail to achieve the global optimization of communication cost. To this end, in this article, we propose the marked cuckoo filter (MCF), a data structure for representing set members. Grounded on MCF, we implement the MCFsyn protocol to reconcile multiple sets. MCFsyn aggregates and distributes sets information represented by MCFs along with an underlying minimum spanning tree among the participants. The participants then identify the different elements by traversing the overall MCF which contains the information of all elements in the union set. For the identified missing elements, MCFsyn helps the participants to choose the optimal senders to fetch with the minimum communication cost. Comprehensive evaluations indicate that MCFsyn significantly outperforms existing alternatives in terms of both reconciliation accuracy and communication cost.

With the rise of video streaming and cloud services, the Internet has evolved into a content-centric service network; however, quality of service (QoS) is still a major concern for the content providers. Because quality degradation is influenced by 1) the capacities of links along the routes used for content delivery and 2) the amount of competing traffic across these links, it is very difficult to diagnose.

Over-the-top (OTT) services reach users via the open Internet without dedicated infrastructures and have experienced enormous growth in recent years. Netflix, an OTT streaming provider, now accounts for more than one-third of peak U.S. downstream traffic and causes cord-cutting of traditional cable pay-TV services from incumbent Internet service providers (ISPs). However, the service quality of video streaming is still influenced by the last-mile Internet access providers, who do not have incentives to deploy enough capacity and want to charge OTT service providers (OSPs) for direct connection. Although Netflix has reached deals with ISPs such as Comcast and Verizon to improve service quality, their undisclosed agreements have raised concerns about net neutrality. In this article, we study the economics of the Netflix-Comcast type of deals and derive the conditions under which an OSP and an ISP would reach such a deal. We analyze the impact of a deal transaction on the revenue of providers, the utility of users and the social welfare. Based on these results, we further classify different policy regimes and draw regulatory implications that depend on the intensity of ex-post deal competition and the cost of the deal. Our results can help understand how existing deals were made, how future deals might emerge, and how regulators should respond to various market conditions and scenarios.

Set reconciliation is a common and fundamental task in distributed systems. In many cases, given set A on $Host_A$ and set B on $Host_B$, applications need to identify those elements that appear in set A but not in set B, and vice versa. However, existing methods incur unsatisfactory space utilization and non-trivial false positives and false negatives. In this paper, we present a novel reconciliation method based on Cuckoo filter (CF). After exchanging the CFs each of which represents a set of elements, we query the local elements against the received CF to determine the elements that only belong to the local host and should be transmitted to the other host. The evaluation results indicate that the CF-based reconciliation method outperforms existing methods significantly.

The emergence of large-scale dynamic sets in networking applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional k candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

Increasing popularity of delay-sensitive and data-intensive online services such as video streaming has placed stronger requirements on the quality of content delivery. By negotiating premium peering agreement with an Internet service provider (ISP), a content provider (CP) is able to improve its service quality, which is beneficial for attracting end-users and increasing profits. Meanwhile, by deploying cache on its content delivery route with a proper caching mechanism, transit traffic is effectively reduced and bandwidth is saved, hence the CP can also achieve better service quality. In this paper, we study how a CP determines an optimal strategy that maximizes its utility, if both premium peering and caching are available from an ISP. We present the conditions that the CP's optimal strategy should comply with, and observe that the optimal quantity of purchasing one capacity is positively correlated to that of the other. We also find that the CP's optimal strategy indicates that the CP would purchase a moderate amount of capacity, or the maximum amount available in some case, to maximize its utility.

Elasticity is highly desirable for stream systems to guarantee low latency against workload dynamics, such as surges in arrival rate and fluctuations in data distribution. Existing systems achieve elasticity using a resource-centric approach that repartitions keys across the parallel instances, i.e., executors, to balance the workload and scale operators. However, such operator-level repartitioning requires global synchronization and prohibits rapid elasticity. We propose an executor-centric approach that avoids operator-level key repartitioning and implements executors as the building blocks of elasticity. By this new approach, we design the Elasticutor framework with two level of optimizations: i) a novel implementation of executors, i.e., elastic executors, that perform elastic multi-core execution via efficient intra-executor load balancing and executor scaling and ii) a global model-based scheduler that dynamically allocates CPU cores to executors based on the instantaneous workloads. We implemented a prototype of Elasticutor and conducted extensive experiments. We show that Elasticutor doubles the throughput and achieves up to two orders of magnitude lower latency than previous methods for dynamic workloads of real-world applications.

Data communication in cloud-based distributed stream data analytics often involves a collection of parallel and pipelined TCP flows. As the standard TCP congestion control mechanism and its variants are designed for achieving “fairness” among competing flows and are agnostic to the application layer contexts, the bandwidth allocation among a set of TCP flows traversing bottleneck links often leads to sub-optimal application-layer performance measures, e.g., stream processing throughput or average tuple complete latency. Motivated by this and enabled by the rapid development of the software-defined networking (SDN) techniques, in this paper, we re-investigate the design space of the bandwidth allocation problem and propose a cross-layer framework which utilizes the instantaneous information obtained from the application layer and provides on-the-fly and dynamic bandwidth adjustment algorithms for assisting the stream analytics applications achieving better performance during the runtime. We implement a prototype cross-layer bandwidth allocation framework based on a popular open-source distributed stream processing platform, Apache Storm, together with the OpenDaylight controller, and carry out extensive experiments with real-world analytical workloads on top of a local cluster consisting of ten workstations interconnected by a SDN-enabled fat-tree like testbed. The experiment results clearly validate the effectiveness and efficiency of our proposed framework and algorithms. Finally, we leverage the proposed cross-layer SDN framework and introduce an exemplary mechanism for bandwidth sharing and performance reasoning among multiple active applications and show a case of a point solution on how to approximate application-level fairness.

Net neutrality has recently been heavily debated as a potential regulation of the Internet. This debate is centered around the argument whether the Internet Service Providers (ISPs) should be allowed to provide differentiated services over the Internet. Advocates of net neutrality have expressed concerns about the ISPs' pricing power, which might be used to discriminate Content Providers (CPs), and consequently destroy innovations at the edge of the Internet and hurt users' utilities. However, without service differentiation, ISPs do not have incentives to expand infrastructure capacities and provide quality of services, which will eventually impair the development of the future Internet. Although market competition among the ISPs would alleviate the problem and reduce the need for net neutrality regulations, the problem is more severe in monopolistic markets, e.g., rural access markets where natural monopolies exist due to high deployment costs and appropriate regulations are most in need. We study the service differentiation offered by a monopolistic ISP and find that the ISP's profit-optimal strategy makes a free ordinary service damaged good, which hurts the welfare of CPs and their users. Instead of imposing net neutrality regulations, we propose a more flexible and lenient policy framework that generalizes net neutrality regulations. We believe that by allowing ISPs to differentiate services under a well-designed policy constraint, the utility of the entire Internet ecosystem could be greatly improved.

Various differentiated pricing schemes have been proposed for the Internet market. Aiming at replacing the traditional single-class pricing for better welfare, yet, researchers have shown that existing schemes can bring only marginal profit gain for the ISPs. In this article, we point out that a proper form of differentiated pricing for the Internet should not only consider congestion, but more importantly, it should provide application specific treatment to data delivery. Formally, we propose an “application-driven pricing” approach, where an ISP offers a number of service classes in terms of a guaranteed quality of service and announces a unit usage price for each class, and content providers are free to choose which class to use depending on the requirement of their applications. Unlike previous studies, we point out that the revenue gain of multi-class pricing under our scheme can be significant. This is because we capture important aspects of application heterogeneity and take the quality of service and price as control knobs. We identify key factors that impact the revenue gain and reveal fundamental understandings on when and why an application-driven multi-class pricing can significantly increase the revenue of ISPs.

In recent years, we have witnessed a growing trend for online service companies to offer “bundling sales” to increase revenue. Bundling sale means that a company groups a set of products/services and charges this bundle at a fixed price, which is usually less than the total price of individual items in the bundle. In this work, our aim is to understand the underlying dynamics of bundling, particularly what is the optimal bundling sale strategy and under what situations it will be more attractive than the separate sales. We focus on online service markets that exhibit network effects . We formulate mathematical models to capture the interactions between buyers and sellers, analyze the market equilibrium and its stability, and provide an optimization framework to determine the optimal sale strategy for a service provider. We analyze the impact of various factors on the profitability of bundling, including the network effects, operating costs, and variance and correlation of customers’ valuations toward these services. We show that bundling is more profitable when the variance of customers’ valuations and the operational cost of the services are small. In addition, a positive network effect and a negative correlation among customers’ valuation on services increase the profitability of bundling, whereas the heterogeneity of services and the asymmetry of operating costs reduce its advantage.

Data communication in cloud-based distributed stream data analytics often involves a collection of parallel and pipelined TCP flows. As the standard TCP congestion control mechanism is designed for achieving "fairness" among competing flows and is agnostic to the application layer contexts, the bandwidth allocation among a set of TCP flows traversing bottleneck links often leads to sub-optimal application-layer performance measures, e.g., stream processing throughput or average tuple complete latency. Motivated by this and enabled by the rapid development of the Software-Defined Networking (SDN) techniques, in this paper, we re-investigate the design space of the bandwidth allocation problem and propose a cross-layer framework which utilizes the additional information obtained from the application layer and provides on-the-fly and dynamic bandwidth adjustment algorithms for helping the stream analytics applications achieving better performance during the runtime. We implement a prototype cross-layer bandwidth allocation framework based on a popular open-source distributed stream processing platform, Apache Storm, together with the OpenDaylight controller, and carry out extensive experiments with real-world analytical workloads on top of a local cluster consisting of 10 workstations interconnected by a SDN-enabled switch. The experiment results clearly validate the effectiveness and efficiency of our proposed framework and algorithms.

With the rapid growth of congestion-sensitive and data-intensive applications, traditional settlement-free peering agreements with best-effort delivery often do not meet the QoS requirements of content providers (CPs). Meanwhile, Internet access providers (IAPs) feel that revenues from end-users are not sufficient to recoup the upgrade costs of network infrastructures. Consequently, some IAPs have begun to offer CPs a new type of peering agreement, called paid peering, under which they provide CPs with better data delivery quality for a fee. In this paper, we model a network platform where an IAP makes decisions on the peering types offered to CPs and the prices charged to CPs and end-users. We study the optimal peering schemes for the IAP, i.e., to offer CPs both the paid and settlement-free peering to choose from or only one of them, as the objective is profit or welfare maximization. Our results show that 1) the IAP should always offer the paid and settlement-free peering under the profit-optimal and welfare-optimal schemes, respectively, 2) whether to simultaneously offer the other peering type is largely driven by the type of data traffic, e.g., text or video, and 3) regulators might want to encourage the IAP to allocate more network capacity to the settlement-free peering for increasing user welfare.

Reputation systems have become an indispensable component of modern E-commerce systems, as they help buyers make informed decisions in choosing trustworthy sellers. To attract buyers and increase the transaction volume, sellers need to earn reasonably high reputation scores. This process usually takes a substantial amount of time. To accelerate this process, sellers can provide price discounts to attract users, but the underlying difficulty is that sellers have no prior knowledge on buyers’ preferences over price discounts. In this article, we develop an online algorithm to infer the optimal discount rate from data. We first formulate an optimization framework to select the optimal discount rate given buyers’ discount preferences, which is a tradeoff between the short-term profit and the ramp-up time (for reputation). We then derive the closed-form optimal discount rate, which gives us key insights in applying a stochastic bandits framework to infer the optimal discount rate from the transaction data with regret upper bounds. We show that the computational complexity of evaluating the performance metrics is infeasibly high, and therefore, we develop efficient randomized algorithms with guaranteed performance to approximate them. Finally, we conduct experiments on a dataset crawled from eBay. Experimental results show that our framework can trade 60% of the short-term profit for reducing the ramp-up time by 40%. This reduction in the ramp-up time can increase the long-term profit of a seller by at least 20%.

As Internet applications have become more diverse in recent years, users having heavy demand for online video services are more willing to pay higher prices for better services than light users that mainly use e-mails and instant messages. This encourages the Internet service providers (ISPs) to explore service differentiation so as to optimize their profits and allocation of network resources. Much prior work has focused on the viability of network service differentiation by comparing with the case of a single-class service. However, the optimal service differentiation for an ISP subject to resource constraints has remained unsolved. In this paper, we establish an optimal control framework to derive the analytical solution to an ISP's optimal service differentiation, i.e., the optimal service qualities and associated prices. By analyzing the structures of the solution, we reveal how an ISP should adjust the service qualities and prices in order to meet varying capacity constraints and users' characteristics. We also obtain the conditions under which ISPs have strong incentives to implement service differentiation and whether regulators should encourage such practices.

We consider data intensive cloud-based stream analytics where data transmission through the underlying communication network is the cause of the performance bottleneck. Two key inter-related problems are investigated: task placement and bandwidth allocation. We seek to answer the following questions. How does task placement make impact on the application-level throughput? Does a careful bandwidth allocation among data flows traversing a bottleneck link results in better performance? In this paper, we address these questions by conducting measurement-driven analysis in a SDN-enabled computer cluster running stream processing applications on top of Apache Storm. The results reveal (i) how tasks are assigned to computing nodes make large difference in application level performance; (ii) under certain task placement, a proper bandwidth allocation helps further improve the performance as compared to the default TCP mechanism; and (iii) task placement and bandwidth allocation are collaboratively making effects in overall performance.

As Internet applications have become more diverse in recent years, users having heavy demand for online video services are more willing to pay higher prices for better services than light users that mainly use e-mails and instant messages. This encourages the Internet Service Providers (ISPs) to explore service differentiations so as to optimize their profits and allocation of network resources. Much prior work has focused on the viability of network service differentiation by comparing with the case of a single-class service. However, the optimal service differentiation for an ISP subject to resource constraints has remained unsolved. In this work, we establish an optimal control framework to derive the analytical solution to an ISP's optimal service differentiation, i.e., the optimal service qualities and associated prices. By analyzing the structures of the solution, we reveal how an ISP should adjust the service qualities and prices in order to meet varying capacity constraints and users' characteristics. We also obtain the conditions under which ISPs have strong incentives to implement service differentiation and whether regulators should encourage such practices.

As the Internet continues to evolve, traditional peering agreements cannot accommodate the changing market conditions. Premium peering has emerged where access providers (APs) charge content providers (CPs) for premium services beyond best-effort connectivity. Although prioritized peering raises concerns about net neutrality, the U.S. FCC exempted peering agreements from its recent ruling, as it falls short of background in the Internet peering context. In this paper, we consider the premium peering options provided by APs and study whether CPs will choose to peer. Based on a novel choice model of complementary services, we characterize the market shares and utilities of the providers under various peering decisions and identify the value of premium peering for the CPs that fundamentally determine CPs' peering decisions. We find that high-value CPs have peer pressure when low-value CPs peer; however, low-value CPs behave oppositely. The peering decisions of the high-value and low-value CPs are substantially influenced by their baseline market shares and user stickiness, respectively, but not vice versa.

The net neutrality debate has been centered on the question: should Internet service providers (ISPs) be allowed to differentiate services for Internet content traffic? The concern is that the differentiation imposed by selfish ISPs might discriminate content providers (CPs) and harm social welfare. Although market competition among ISPs would alleviate the problem and moderate the necessity for net neutrality regulations, the problem remains in monopolistic access markets. We focus on such a market and study paid prioritization where CPs voluntarily pay for prioritizing their traffic under shared capacity. We study an ISP's pricing strategy, CPs' choices of priority, and the resulting system equilibrium, based on which we derive the utility of the ISP and CPs as well as social welfare. This paper shows that: 1) an ISP's optimal pricing leads to an efficient differentiation among CPs, such that social welfare is close to its maximum; 2) although ISPs might inhibit capacity deployment in the short run, price regulation could solve this issue; and 3) under medium system scale and capacity cost, ISPs would have strong incentives to expand capacity under paid prioritization. From a welfare perspective, our results suggest that paid prioritization could be superior to the imposition of net neutrality regulations.

Android, the most popular mobile OS, has around 78% of the mobile market share. Due to its popularity, it attracts many malware attacks. In fact, people have discovered around 1 million new malware samples per quarter, and it was reported that over 98% of these new malware samples are in fact “derivatives” (or variants) from existing malware families. In this paper, we first show that runtime behaviors of malware's core functionalities are in fact similar within a malware family. Hence, we propose a framework to combine “runtime behavior” with “static structures” to detect malware variants. We present the design and implementation of Monet, which has a client and a backend server module. The client module is a lightweight, in-device app for behavior monitoring and signature generation, and we realize this using two novel interception techniques. The backend server is responsible for large scale malware detection. We collect 3723 malware samples and top 500 benign apps to carry out extensive experiments of detecting malware variants and defending against malware transformation. Our experiments show that Monet can achieve around 99% accuracy in detecting malware variants. Furthermore, it can defend against ten different obfuscation and transformation techniques, while only incurs around 7% performance overhead and about 3% battery overhead. More importantly, Monet will automatically alert users with intrusion details so to prevent further malicious behaviors.

In a stream data analytics system, input data arrive continuously and trigger the processing and updating of analytics results. We focus on applications with real-time constraints, in which, any data unit must be completely processed within a given time duration. To handle fast data, it is common to place the stream data analytics system on top of a cloud infrastructure. Because stream properties, such as arrival rates can fluctuate unpredictably, cloud resources must be dynamically provisioned and scheduled accordingly to ensure real-time responses. It is essential, for existing systems or future developments, to possess the ability of scaling resources dynamically according to the instantaneous workload, in order to avoid wasting resources or failing in delivering the correct analytics results on time. Motivated by this, we propose DRS, a dynamic resource scaling framework for cloud-based stream data analytics systems. DRS overcomes three fundamental challenges: 1) how to model the relationship between the provisioned resources and the application performance, 2) where to best place resources, and 3) how to measure the system load with minimal overhead. In particular, DRS includes an accurate performance model based on the theory of Jackson open queueing networks and is capable of handling arbitrary operator topologies, possibly with loops, splits, and joins. Extensive experiments with real data show that DRS is capable of detecting sub-optimal resource allocation and making quick and effective resource adjustment.

Internet services are traditionally priced at flat rates; however, many Internet service providers (ISPs) have recently shifted towards two-part tariffs where a data cap is imposed to restrain data demand from heavy users.Although the two-part tariff could generally increase the revenue for ISPs and has been supported by the US FCC, the role of data cap and its optimal pricing structures are not well understood.In this article, we study the impact of data cap on the optimal two-part pricing schemes for congestion-prone service markets.We model users' demand and preferences over pricing and congestion alternatives and derive the market share and congestion of service providers under a market equilibrium.Based on the equilibrium model, we characterize the two-part structures of the revenue-and welfare-optimal pricing schemes.Our results reveal that 1) the data cap provides a mechanism for ISPs to transition from the flat-rate to pay-as-you-go type of schemes, 2) both the revenue and welfare objectives of the ISP will drive the optimal pricing towards usage-based schemes with diminishing data caps, and 3) the welfare-optimal tariff comprises lower fees than the revenue-optimal counterpart, suggesting that regulators might want to promote usage-based pricing but regulate the lump-sum and per-unit fees.

Through virtualization technologies, modern enterprises can build private clouds to support the daily operations of their subsidiaries and consolidate resources from them. In making these resource allocation and consolidation decisions, they want to maximize the achieved utilities and minimize the incurred costs by their subsidiaries, respectively. However, these subsidiaries very often operate autonomously and have private information about job characteristics and energy costs. Due to this information asymmetry, they might be motivated to behave in their own best interests rather than that of the enterprise. To solve these principal-agent problems, we design a tunable auction under which subsidiaries submit bids and resources are allocated in proportion to their bids. We show that the induced competition game obtains a unique Nash equilibrium, under which hidden characteristics of subsidiaries can be revealed. By using variational inequality techniques, we derive the dynamics of the Nash equilibrium as a function of the auction parameters. We design a feedback control mechanism to dynamically adjust the tunable auction parameters based on observable information such as the bids and the resulting allocations. We prove that our adaptive auction converges to the optimal Nash equilibrium under which the aggregate utility of an enterprise is maximized.

Telecommunication companies possess mobility information of their phone users, containing accurate locations and velocities of commuters travelling in public transportation system. Although the value of telecommunication data is well believed under the smart city vision, there is no existing solution to transform the data into actionable items for better transportation, mainly due to the lack of appropriate data utilization scheme and the limited processing capability on massive data. This paper presents the first ever system implementation of real-time public transportation crowd prediction based on telecommunication data, relying on the analytical power of advanced neural network models and the computation power of parallel streaming analytic engines. By analyzing the feeds of caller detail record (CDR) from mobile users in interested regions, our system is able to predict the number of metro passengers entering stations, the number of waiting passengers on the platforms and other important metrics on the crowd density. New techniques, including geographical-spatial data processing, weight-sharing recurrent neural network, and parallel streaming analytical programming, are employed in the system. These new techniques enable accurate and efficient prediction outputs, to meet the real-world business requirements from public transportation system.

We develop an optimization framework to trade short-term profits for reputation (i.e., reducing ramp-up time). We apply the stochastic bandits framework to design an online discounting mechanism which infers the optimal discount from a seller's historical transaction data. We conduct experiments on an eBay's dataset and show that our online discounting mechanism can trade 60% of the shortterm profits for reducing the ramp-up time by 40%.

Unlike telephone operators, which pay termination fees to reach the users of another network, Internet content providers (CPs) do not pay the Internet service providers (ISPs) of users they reach. While the consequent cross subsidization to CPs has nurtured content innovations at the edge of the Internet, it reduces the investment incentives for the access ISPs to expand capacity. As potential charges for terminating CPs' traffic are criticized under the net neutrality debate, we propose to allow CPs to voluntarily subsidize the usage-based fees induced by their content traffic for end-users. We model the regulated subsidization competition among the CPs under a neutral network and show how deregulation of subsidization could increase an access ISP's utilization and revenue, strengthening its investment incentives. Our results suggest that subsidization competition will increase the competitiveness and welfare of the Internet content market. However, regulators might need to: 1) regulate access prices if the access ISP market is not competitive enough; and 2) regulate subsidies if network is highly congested. We envision that subsidization competition could become a viable net-neutral model for the future Internet.

As Internet traffic grows exponentially due to the pervasive Internet accesses via mobile devices and increasing adoptions of cloud-based applications, broadband providers start to shift from flat-rate to usage-based pricing, which has gained support from regulators such as the FCC. We consider generic congestion-prone network services and study usage-based pricing of service providers under market competition. Based on a novel model that captures users' preferences over price and congestion alternatives, we derive the induced congestion and market share of the service providers under a market equilibrium and design algorithms to calculate them. By analyzing different market structures, we reveal how users' value on usage and sensitivity to congestion influence the optimal price, revenue, and competition of service providers, as well as the social welfare. We also obtain the conditions under which monopolistic providers have strong incentives to implement service differentiation via Paris Metro Pricing and whether regulators should encourage such practices.

There has been increasing interest in designing and developing highly scalable infrastructures to support the efficient distribution of content. This has led to the recent development of content-oriented network architectures that rely on on-demand caching. This paper addresses the question of how a cache provider can monetize its service. Standard cache management policies such as least recently used (LRU) treat different content in a strongly coupled manner that makes it difficult for a cache provider to design individualized contracts. We propose the use of timer-based caching for the purpose of designing contracts, which allow providers to monetize caching. We focus on on-demand request-based contracts that allow content providers (CPs) to negotiate contracts at the time that requests are made. We propose and analyze three variations, one where a contract is negotiated only at the time of a miss, and two where contracts are negotiated at the times of both misses and hits. The latter two differ from one another according to whether pricing is based on cache occupancy (time content spends in the cache) or on request rate. We conclude that the first one is least preferable and that the last one provides the provider greater opportunity for profit and greater flexibility to CPs.

In a data stream management system (DSMS), users register continuous queries, and receive result updates as data arrive and expire. We focus on applications with real-time constraints, in which the user must receive each result update within a given period after the update occurs. To handle fast data, the DSMS is commonly placed on top of a cloud infrastructure. Because stream properties such as arrival rates can fluctuate unpredictably, cloud resources must be dynamically provisioned and scheduled accordingly to ensure real-time response. It is essential, for the existing systems or future developments, to possess the ability of scheduling resources dynamically according to the current workload, in order to avoid wasting resources, or failing in delivering correct results on time. Motivated by this, we propose DRS, a novel dynamic resource scheduler for cloud-based DSMSs. DRS overcomes three fundamental challenges: (a) how to model the relationship between the provisioned resources and query response time (b) where to best place resources, and (c) how to measure system load with minimal overhead. In particular, DRS includes an accurate performance model based on the theory of Jackson open queueing networks and is capable of handling arbitrary operator topologies, possibly with loops, splits and joins. Extensive experiments with real data confirm that DRS achieves real-time response with close to optimal resource consumption.

Most sampling techniques for online social networks (OSNs) are based on a particular sampling method on a single graph, which is referred to as a statistic. However, various realizing methods on different graphs could possibly be used in the same OSN, and they may lead to different sampling efficiencies, i.e., asymptotic variances. To utilize multiple statistics for accurate measurements, we formulate a mixture sampling problem, through which we construct a mixture unbiased estimator which minimizes the asymptotic variance. Given fixed sampling budgets for different statistics, we derive the optimal weights to combine the individual estimators; given a fixed total budget, we show that a greedy allocation towards the most efficient statistic is optimal. In practice, the sampling efficiencies of statistics can be quite different for various targets and are unknown before sampling. To solve this problem, we design a two-stage framework which adaptively spends a partial budget to test different statistics and allocates the remaining budget to the inferred best statistic. We show that our two-stage framework is a generalization of 1) randomly choosing a statistic and 2) evenly allocating the total budget among all available statistics, and our adaptive algorithm achieves higher efficiency than these benchmark strategies in theory and experiment.

Least Recently Used (LRU) is the most commonly used cache replacement policy; however, it suffers from two problems: i) cache thrashing, i.e., repeated references cause continuous page evictions due to a larger size of the working set than that of the cache, and ii) cache pollution, i.e., high reuse content gets evicted by items with low or no reuse from a cache. To solve these problems, prior works divide the cache into multiple segments and keeping the history of evicted pages, which impose high overhead in terms of memory. In this paper, we propose an adaptive cache replacement policy which divides the cache into two variable-sized segments: protected and unprotected. The division of cache segments is elastic in nature and can adaptively react to the workload changes without any history of evicted pages. We conduct extensive simulations using both synthetic and real workloads. Our evaluation shows that our policy can obtain the hit ratio close to the state of the art policies which keep history information of evicted pages up to multiple times of cache size.

We present LiveTraj, a novel system for tracking trajectories in a live video stream in real time, backed by a cloud platform. Although trajectory tracking is a well-studied topic in computer vision, so far most attention has been devoted to improving the accuracy of trajectory tracking, rather than the efficiency. To our knowledge, LiveTraj is the first that achieves real-time efficiency in trajectory tracking, which can be a key enabler in many important applications such as video surveillance, action recognition and robotics. LiveTraj is based on a state-of-the-art approach to (offline) trajectory tracking; its main innovation is to adapt this base solution to run on an elastic cloud platform to achieve real-time tracking speed at an affordable cost. The video demo shows the offline base solution and LiveTraj side by side, both running on a video stream containing human actions. Besides demonstrating the real-time efficiency of LiveTraj, our video demo also exhibits important system parameters to the audience such as latency and cloud resource usage for different components of the system. Further, if the conference venue provides sufficiently fast Internet connection to our cloud platform, we also plan to demonstrate LiveTraj on-site, during which we will show LiveTraj identifying and tracking trajectories from a live video stream captured by a camera.

Content distribution, especially the distribution of video content, unavoidably consumes bandwidth resource heavily. Internet content providers (ICP) spend lots of money to buy content distribution network (CDN) service. By deploying thousands of edge servers close to end users, CDN companies are able to distribute content efficiently. In lieu of traditional CDN systems, we implement a crowdsourcing-based content distribution system, Thunder Crystal, which utilizes agents' upload bandwidth to amplify the content distribution capacity. Agents are well motivated to contribute storage and upload bandwidth to the system by rebated cash. As far as we know, this is a novel system that has not been studied before. In this work, we will present its design principles first. Then, we study agent behavior and methods to evaluate system efficiency and user efficiency. We evaluate the system by simulations, and observe that agents are well motivated to keep online most of the time and amplify the content distribution capacity by 10~20 times.

Task migration happens when distributed data processing systems scale in real-time. To handle the task migration process more gracefully, we propose three task migration methods: (i) worker level migration, (ii) executor level migration, and (iii) executor level migration with reliable messaging. We implement our migration methods on Apache Storm. Our experiments show that, compared with Storm's original migration implementation, our methods significantly reduce the performance degradation and the number of task failures during each migration.

Internet services are traditionally priced at flat rates; however, many Internet service providers (ISPs) have recently shifted towards two-part tariffs where a data cap is imposed to restrain data demand from heavy users and usage over the data cap is charged based on a per-unit fee. Although the two-part tariff could generally increase the revenue for ISPs and has been supported by the FCC chairman, the role of data cap and its revenue-optimal and welfare-optimal pricing structures are not well understood. In this paper, we study the impact of data cap on the optimal two-part pricing schemes for congestion-prone service markets, e.g., broadband or cloud services. We model users' demand and preferences over pricing and congestion alternatives and derive the market share and congestion of service providers under a market equilibrium. Based on the equilibrium model, we characterize the two-part structures of the revenue-optimal and welfare-optimal pricing schemes. Our results reveal that 1) the data cap provides a mechanism for ISPs to transition from flat-rate to pay-as-you-go type of schemes, 2) with growing data demand and network capacity, the revenue-optimal pricing moves towards usage-based schemes with diminishing data caps, and 3) the structure of the welfare-optimal tariff comprises lower fees and data cap than those of the revenue-optimal counterpart, suggesting that regulators might want to promote usage-based pricing but regulate the per-unit fees. Our results could help providers design revenue-optimal pricing schemes and guide regulatory authorities to legislate desirable regulations.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies, and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network-aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

Unlike telephone operators, which pay {\em termination fees} to reach the users of another network, Internet Content Providers (CPs) do not pay the Internet Service Providers (ISPs) of users they reach. While the consequent cross subsidization to CPs has nurtured content innovations at the edge of the Internet, it reduces the investment incentives for the access ISPs to expand capacity. As potential charges for terminating CPs' traffic are criticized under the net neutrality debate, we propose to allow CPs to voluntarily subsidize the usage-based fees induced by their content traffic for end-users. We model the regulated subsidization competition among CPs under a neutral network and show how deregulation of subsidization could increase an access ISP's utilization and revenue, strengthening its investment incentives. Although the competition might reduce the throughput of certain CPs, we find that the main cause comes from high access prices rather than the existence of subsidization. Our results suggest that subsidization competition will increase the competitiveness and welfare of the Internet content market; however, regulators might need to regulate access prices if the access ISP market is not competitive enough. We envision that subsidization competition could become a viable model for the future Internet.

As Internet traffic grows exponentially due to the pervasive Internet accesses via mobile devices and increasing adoptions of cloud-based applications, broadband providers start to shift from flat-rate to usage-based pricing, which has gained support from regulators such as the FCC. We consider generic congestion-prone network services, including cloud services, and study the pay-as-you-go type of usage-based pricing of service providers under market competition. Based on a novel model that captures users' preferences over usage price and congestion alternatives, we derive the induced congestion and market share of the service providers under a market equilibrium and design algorithms to calculate them. By analyzing different market structures, we reveal how users' value on usage and sensitivity to congestion influence the optimal price, revenue, and competition of service providers, as well as the social welfare. We also obtain the conditions under which monopolistic providers have strong incentives to implement service differentiation via Paris Metro Pricing and whether regulators should encourage such practices.

Net neutrality has been heavily debated as a potential Internet regulation. Advocates have expressed concerns about the pricing power of ISPs, which might be used to discriminate Content Providers (CPs), and consequently destroy innovations at the edge of the Internet and hurt the user welfare. However, without service differentiation, ISPs do not have incentives to expand infrastructure capacities and provide quality of services, which will eventually impair the future Internet. Although competition among ISPs would alleviate the problem and reduce the need for regulations, the problem is more severe in monopolistic markets. We study the service differentiation offered by a monopolistic ISP and find that its profit-optimal strategy makes an ordinary service "damaged good", which hurts the welfare of CPs. Instead of imposing net neutrality regulations, we propose a flexible and lenient policy framework that generalizes net neutrality regulations. We find that a stringent regulation is needed when 1) the ISP's capacity is abundant, 2) the profit distribution of CPs is concentrated, or 3) the utility of CPs and their users are not positively correlated. We believe that by allowing the ISPs to differentiate services under a well designed policy constraint, the utility of the Internet ecosystem could be greatly improved.

In recent years, we have witnessed a growing trend for online service companies to offer “bundling sales” to increase revenue. Bundling sale means that a company groups a set of its products/services and charges this bundle at a fixed price, which is usually less than the total price of individual items. In this paper, our goal is to understand the underlying dynamics of bundling, in particular, what is the optimal bundling sale strategy and under what situations it will be more attractive than the separate sales. We focus on online service markets that exhibit network effect. We provide mathematical models to capture the interactions between buyers and sellers, analyze the market equilibrium and its stability, and formulate an optimization framework to determine the optimal sale strategy for the service provider. We analyze the impact of the key factors, including the network effects and operating costs, on the profitability of bundling. We show that bundling is more profitable than separate sale in most cases; however, the heterogeneity of services and the asymmetry of operating costs reduce the advantage of bundling. These findings provide important insights in designing proper sale strategies for online services.

The net neutrality debate has been centered at the question: whether price and service differentiation should be allowed for the Internet? We focus on a monopoly market, where regulation is often required, and study the type of service differentiation where an option of paid prioritization is provided for the Content Providers (CPs) by an Internet Service Provider (ISP). We study the ISP's pricing strategy and the corresponding CPs' responses. Based on the higher level CPs' choices of service classes and the lower level traffic equilibrium, we analyze the utility of the ISP and the CPs as well as the social welfare. By comparing the induced social welfare under different settings, we find that ISP's optimal pricing leads to an efficient differentiation among the CPs such that the social welfare is highly optimized. We also identify the conditions under which the ISP would have a strong incentive to expand its capacity when the market grows. In conclusion, our results support the use of priority-based pricing and service differentiation rather than imposing net neutrality regulations.

Peer-to-peer (P2P) systems rely on peers' cooperation to provide a more robust and scalable service as compared to the traditional client-server architecture. However, the peers might be selfish in nature-they would like to receive services from others, but would not like to contribute their own resources by default. To conquer this problem, proper incentive schemes are needed so as to stimulate the peers' contributions. In particular, in P2P video-on-demand (VoD) systems, peers need to distributively cache the proper videos so as to mutually upload and help each other to acquire the required data. Content providers of P2P-VoD services want to incentivize peers to do so and alleviate the workload of the content server. In this paper, we design a practical mechanism to incentivize distributed caching in such systems, under which the peers are rewarded based on the popularity of the video they cache. We characterize the impact of this incentive scheme on peers' caching behaviors. In particular, we formulate an optimization framework to decide the optimal reward price for each video so as to keep enough replicas and minimize the content provider's operational cost. We first derive close form solutions in an asymptotic system, and then extend our results to be adaptive to various practical issues. Via extensive simulations, we validate the effectiveness and efficiency of our incentive scheme.

The emergence of the cloud computing paradigm has greatly enabled innovative service models, such as Platform as a Service (PaaS), and distributed computing frameworks, such as Map Reduce. However, most existing cloud systems fail to distinguish users with different preferences, or jobs of different natures. Consequently, they are unable to provide service differentiation, leading to inefficient allocations of cloud resources. Moreover, contentions on the resources exacerbate this inefficiency, when prioritizing crucial jobs is necessary, but impossible. Motivated by this, we propose Abacus, a generic resource management framework addressing this problem. Abacus interacts with users through an auction mechanism, which allows users to specify their priorities using budgets, and job characteristics via utility functions. Based on this information, Abacus computes the optimal allocation and scheduling of resources. Meanwhile, the auction mechanism in Abacus possesses important properties including incentive compatibility (i.e., the users' best strategy is to simply bid their true budgets and job utilities) and monotonicity (i.e., users are motivated to increase their budgets in order to receive better services). In addition, when the user is unclear about her utility function, Abacus automatically learns this function based on statistics of her previous jobs. An extensive set of experiments, running on Hadoop, demonstrate the high performance and other desirable properties of Abacus.

Frequency control is essential to maintain the stability and reliability of power grids. For decades, generation side controllers, e.g., isochoronous governors and automatic generation controllers, have been used to stabilize the frequency of power systems, which, however, incur high operational costs. In smart grids, demand response can be used to control frequency and thus reduce the grids' dependency on expensive controllers. Despite of its economic advantages, the synchronization problem, which is due to the simultaneous responses of smart appliances, becomes the main barrier to implementing frequency responsive demand control in reality. In this paper, we propose a distributed control algorithm for smart appliances, based on the randomized frequency monitoring and a baseline hysteresis algorithm, to solve the synchronization problem. We provide analytical results to characterize the influence of distributed demand response on the system frequency dynamics. Finally, we validate our analysis and demonstrate the effectiveness of our proposed algorithm via simulations on the Ireland power system.

We propose Resa, a novel framework for robust, elastic and realtime stream processing in the cloud. In addition to traditional functionalities of streaming and cloud systems, Resa provides (i) a novel mechanism that handles dynamic additions and removals nodes in an operator, and (ii) a node re-assignment scheme that minimizes output latency using a queuing model. We have implemented Resa on top of Twitter Storm. Experiments using real data demonstrate the effectiveness and efficiency of Resa.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

Network neutrality and the role of regulation on the Internet have been heavily debated in recent times. Among the various definitions of network neutrality, we focus on the one that prohibits paid prioritization of content. We develop a model of the Internet ecosystem in terms of three primary players: consumers, ISPs, and content providers. We analyze this issue from the point of view of the consumer and target the desired system state that maximizes consumer utility. By analyzing various structures of an ISP market, we obtain different conclusions on the desirability of regulation. We also introduce the notion of a Public Option ISP, an ISP that carries traffic in a network-neutral manner. We find: in a monopolistic scenario, network-neutral regulations might benefit consumers, however the introduction of a Public Option ISP is even better as it aligns the interests of the monopolistic ISP with the consumer utility; and in an oligopolistic scenario, the presence of a Public Option ISP is again preferable to network-neutral regulations, although the presence of competing nonneutral ISPs provides the most desirable situation for the consumers.

In this paper, we develop the notion of congestion equilibrium in large scale networks, with the specific goal of understanding the modern multiparty Internet ecosystem comprising of content providers, ISPs and users. We show that the concept of "congestion-taking" is analogous to the concept of "price-taking" in classical market economics. With a wide variety of congestion metrics and under very mild assumptions on the congestion dynamics, we characterize various properties of congestion equilibria and develop algorithms to compute them for large scale networks. Our work provides a new way to model and analyze modern large scale network-economic systems that have a complex interaction of engineering and economics.

Network neutrality and the role of regulation on the Internet have been heavily debated in recent times. Amongst the various definitions of network neutrality, we focus on the one which prohibits paid prioritization of content. We develop a model of the Internet ecosystem in terms of three primary players: consumers, ISPs and content providers. We analyze this issue from the point of view of the consumer, and target the desired system state that maximizes consumer surplus.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the “network neutrality” debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the profit model, selfish ISPs would yield globally optimal routing and interconnecting decisions. In this paper, we use a more detailed and realistic network model with three classes of ISPs: content, transit, and eyeball. This additional detail enables us to delve much deeper into the implications of a Shapley settlement mechanism. We derive closed-form Shapley values for more structured ISP topologies and develop a dynamic programming procedure to compute the Shapley values under more diverse Internet topologies. We also identify the implications on the bilateral compensation between ISPs and the pricing structures for differentiated services. In practice, these results provide guidelines for solving disputes between ISPs and for establishing regulatory protocols for differentiated services and the industry.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept ofShapley valueand its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit-sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits and encourage ISP connectivity so as to limit balkanization.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the "network neutrality" debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the revenue model, selfish ISPs would yield globally optimal routing and interconnecting decisions.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits, encourage ISP connectivity so as to limit balkanization.

Aloha [1] and its slotted variant [2] are commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other’s presence. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted- Aloha protocols. We evaluate the channel utilization and fairness of these types of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node greedily maximizing its own throughput, and attacker nodes that attempt to jam the channel. If all nodes are selfish and greedily attempt to maximize their own throughputs, a situation similar to the traditional Prisoner’s Dilemma[3] arises. Our results reveal that under heavy loads, greedy strategies reduce the utilization, and that attackers cannot do much better than attacking during randomly selected slots.

The current peer-to-peer (P2P) information sharing paradigm does not provide incentive and service differentiation for users. Since there is no motivation to share information or resources, this leads to the "free-riding" and the "tragedy of the commons" problems. We address how one can incorporate incentive into the P2P information sharing paradigm so as to encourage users to share information and resources. Our mechanism (or protocol) provides service differentiation to users with different contribution values and connection types. The mechanism also has some desirable properties: (1) conservation of cumulative contribution and social utility in the P2P community, (2) maximization of social utility if all requesting clients have the same contribution value, and (3) incentive-based resource distribution. The resource distribution algorithm and the contribution update algorithm are computationally efficient and can be easily implemented. Experimental results illustrate the efficiency and fairness of our algorithms.

Traditional peer-to-peer (P2P) networks do not provide service differentiation and incentive for users. Consequently, users can obtain services without themselves contributing any information or service to a P2P community. This leads to the "free-riding" and "tragedy of the commons" problems, in which the majority of information requests are directed towards a small number of P2P nodes willing to share their resources. The objective of this work is to enable service differentiation in a P2P network based on the amount of services each node has provided to its community, thereby encouraging all network nodes to share resources. We first introduce a resource distribution mechanism between all information sharing nodes. The mechanism is driven by a distributed algorithm which has linear time complexity and guarantees Pareto-optimal resource allocation. Besides giving incentive, the mechanism distributes resources in a way that increases the aggregate utility of the whole network. Second, we model the whole resource request and distribution process as a competition game between the competing nodes. We show that this game has a Nash equilibrium and is collusion-proof. To realize the game, we propose a protocol in which all competing nodes interact with the information providing node to reach Nash equilibrium in a dynamic and efficient manner. Experimental results are reported to illustrate that the protocol achieves its service differentiation objective and can induce productive information sharing by rational network nodes. Finally, we show that our protocol can properly adapt to different node arrival and departure events, and to different forms of network congestion.