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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.