General-purpose congestion control algorithms (CCAs) are designed to achieve general congestion control goals, but they may not meet the specific requirements of certain users. Customized CCAs can meet certain users' specific requirements; however, non-expert users often lack the expertise to implement them. In this paper, we present an exploratory non-expert customized CCA framework, named NECC, which enables non-expert users to easily model, implement, and deploy their customized CCAs by leveraging Large Language Models and the Berkeley Packet Filter (BPF) interface. To the best of our knowledge, we are the first to address the customized CCA implementation problem. Our evaluations using real-world CCAs show that the performance of NECC is very promising, and we discuss the insights that we find and possible future research directions.

Hardware TCP/IP stacks, which directly implement TCP/IP functionality in hardware, have gained increasing attention due to their ability to meet the performance requirements of rapidly growing network speeds while significantly reducing CPU overhead. However, comprehensively testing these hardware implementations remains challenging because of their prohibitively large test input spaces involving diverse packet contents and complex packet dynamics. Symbolic execution, a powerful program analysis technique, has successfully improved testing coverage in software TCP/IP stacks but has not yet been widely adopted for hardware TCP/IP stacks. This paper addresses this gap by enabling symbolic execution to systematically test hardware TCP/IP stacks based on AMD Vitis High-Level Synthesis (HLS). We identify key challenges in applying symbolic execution in this hardware context and propose methods to overcome them. Evaluations on a real-world open-source hardware TCP/IP stack demonstrate the effectiveness of our methods in achieving high test coverage and discovering previously undetected bugs.

Abstract Automatic Program Repair (APR) has garnered significant attention as a practical research domain focused on automatically fixing bugs in programs. While existing APR techniques primarily target imperative programming languages like C and Java, there is a growing need for effective solutions applicable to declarative software specification languages. This paper systematically investigates the capacity of Large Language Models (LLMs) to repair declarative specifications in Alloy, a declarative formal language used for software specification. We designed six different repair settings, encompassing single-agent and dual-agent paradigms, utilizing various LLMs. These configurations also incorporate different levels of feedback, including an auto-prompting mechanism for generating prompts autonomously using LLMs. Our study reveals that dual-agent with auto-prompting setup outperforms the other settings, albeit with a marginal increase in the number of iterations and token usage. This dual-agent setup demonstrated superior effectiveness compared to state-of-the-art Alloy APR techniques when evaluated on a comprehensive set of benchmarks. This work is the first to empirically evaluate LLM capabilities to repair declarative specifications, while taking into account recent trending LLM concepts such as LLM-based agents, feedback, auto-prompting, and tools, thus paving the way for future agent-based techniques in software engineering.

Congestion control algorithms, such as RENO and CUBIC, are vital for the Internet. However, numerous bugs have been discovered and reported in the Congestion Control Algorithm Implementations (CCAIs), even in those that have been extensively tested and used on the Internet for years, such as Linux RENO and Linux CUBIC. Some of these bugs have potentially severe impacts on the performance and stability of the Internet. Unfortunately, current CCAI testing and verification methods are inadequate for proving the absence of bugs, require substantial verification expertise, or are not scalable to a large number of acknowledgment packets (ACKs) that trigger CCAI actions. To address all these shortcomings, we propose an ACK Scalable Method, called ASM. Our experiments with two representative loss-based CCAIs, Linux RENO and CUBIC, demonstrate the promising performance of the proposed ASM even with tens of thousands of ACKs.

To achieve a line rate in the high-speed environment of modern networks, there is a continuing effort to offload network functions from software to programmable hardware (HW). Although the offloading effort has led to greater performance, it brings difficulty in the verification of timing-related network functions (Time-NFs) as well. Time-NFs use numerical timing values to perform various network tasks. For example, congestion control algorithm BBR uses round-trip time to improve throughput. Errors in Time-NFs could cause packet loss and poor throughput. However, verifying Time-NFs in HW often involves many clock cycles that can result in an exponentially increasing number of test cases. Current verification methods either do not scale or sacrifice soundness for scalability.In this paper, we propose an invariant-based method to improve the verification efficiency without losing soundness. Our method is motivated by an observation that most Time-NFs follow a few fixed patterns to use timing information. Based on these patterns, we develop a set of easy-to-validate invariants to constrain the examination space. According to experiments on real Time-NFs, our method can speed up verification by 7 times on average without losing the verification soundness.

To bypass network censorship, Shadowsocks is often deployed on long-distance transnational networks; however, such proxy networks are usually plagued by high latency, high packet loss rate, and unstable bandwidth. Most existing tuning solutions rely on hand-tuned heuristics, which cannot work well in the volatile Shadowsocks networks due to the labor intensive and time-consuming properties. In this paper, we propose Auter, which automatically tunes multi-layer buffer parameters with reinforcement learning (RL) to improve the performance of Shadowsocks in long-distance networks. The key insight behind Auter is that different network environments require different sizes of buffers to achieve sufficiently good performance. Hence, Auter continuously learns a tuning policy from volatile network states and dynamically alter sizes of multi-buffers for high network performance. We prototype Auter and evaluate its effectiveness under various real networks. Our experimental results show that Auter can effectively improve network performance, up to 40.5% throughput increase in real networks. Besides, we demonstrate that Auter outperforms all the existing tuning schemes.

This paper aims to address the significant power challenges in live virtual reality (VR) streaming (a.k.a., 360-degree video streaming), where the VR view rendering and the advanced deep learning operations (e.g., super-resolution) consume a considerable amount of power draining the battery-constrained VR headset. We develop EdgeVR, a power optimization technique for live VR streaming, which offloads the on-device VR rendering and deep learning operations to an edge server for power savings. To address the significantly increased motion-to-photon (MtoP) latency due to the edge offloading, we develop a live VR viewport prediction method to pre-render the VR views on the edge server and compensate for the round-trip delays. We evaluate the effectiveness of EdgeVR using an end-to-end live VR streaming system with an empirical VR head movement dataset involving 48 users watching 9 VR videos. The results reveal that EdgeVR achieves power-efficient live VR streaming with low MtoP latency.

Multipath TCP (MPTCP) has captured the networking community's attention in recent years since it simultaneously transfers data over multiple network interfaces, thus increases the performance and stability. Existing works on MPTCP study its performance only in traditional wired and wireless networks. Meanwhile, cloud computing has been growing rapidly with lots of applications deployed in private and public clouds, where virtual machine (VM) scheduling techniques are often adopted to share physical CPUs among VMs. This motivates us to study MPTCP's performance under VM scheduling impact. For the first time, we show that VM scheduling negatively impacts all MPTCP subflows' throughput. Specifically, VM scheduling causes the inaccuracy in computing the overall aggressiveness parameter of MPTCP congestion control, which leads to the slow increment of the congestion windows of all MPTCP subflows instead of just a single subflow. This finally results in a poor overall performance of MPTCP in cloud networks. We propose a modified version for MPTCP, which considers VM scheduling noises when MPTCP computes its overall aggressiveness parameter and its congestion windows. Experimental results show that our modified MPTCP performs considerably better (with up to 80% throughput improvement) than the original MPTCP in cloud networks.

Google introduced BBR representing a new model-based TCP class in 2016, which improves throughput and latency of Google's backbone and services and is now the second most popular TCP on the Internet. As BBR is designed as a general-purpose congestion control to replace current widely deployed congestion control such as Reno and CUBIC, this raises the importance of studying its performance in different types of networks. In this paper, we study BBR's performance in cloud networks, which have grown rapidly but have not been studied in the existing BBR works. For the first time, we show both analytically and experimentally that due to the virtual machine (VM) scheduling in cloud networks, BBR underestimates the pacing rate, delivery rate, and estimated bandwidth, which are three key elements of its control loop. This underestimation can exacerbate iteratively and exponentially over time, and can cause BBR's throughput to reduce to almost zero. We propose a BBR patch that captures the VM scheduling impact on BBR's model and improves its throughput in cloud networks. Our evaluation of the modified BBR on the testbed and EC2 shows a significant improvement in the throughput and bandwidth estimation accuracy over the original BBR in cloud networks with heavy VM scheduling.

Danmu (a.k.a., barrage videos or bullet comments) is a novel type of interactive video streaming, which displays instantaneous user comments flying across the screen during the video playback to better engage the users. However, such fancy experience brings a considerable burden to the battery of mobile user devices that have limited capacity. For example, WiFi testbed experiments show 15% to 35% increase in WiFi network energy consumption because of the large amount of additional network traffic for user comments. On the other hand, current network energy minimization methods adversely impact the Quality of Service (QoS) of Danmu users, because they put off the transmission and then delay the display of the user comments that should match with the timeline of the corresponding videos. In this paper, for the first time, a heuristic QoS-aware network energy optimization algorithm is proposed to reduce the WiFi network energy consumption while still maintaining the desired QoS of Danmu users. Comprehensive testbed experiments using an open-source Danmu streaming system and with real Danmu user traces indicate up to 28% WiFi network energy saving depending on different system, network, and user settings.

The significant impact of TCP congestion control on the Internet highlights the importance of testing congestion control algorithm implementations (CCAIs) in various network environments. Many CCAI testing problems can be solved by exploring the numerical state space of CCAIs, which is defined by a group of numerical (and nonnumerical) state variables of the CCAIs. However, the current practices for automated numerical state space exploration are either limited by the approximate abstract CCAI models or inefficient due to the large space of network environment parameters and the complicated relation between the CCAI states and network environment parameters. In this paper, we propose an automated numerical state space exploration method, called ACT, which leverages the model-agnostic feature of random testing and greatly improves its efficiency by guiding random testing under the feedback iteratively obtained in a test. Our experiments on five representative Linux TCP CCAIs show that ACT can more efficiently explore a large numerical state space than manual testing, undirected random testing, and symbolic execution based testing, while without requiring an abstract CCAI model. ACT detects multiple design and implementation bugs of these Linux TCP CCAIs, including some new bugs not reported before.

There is a rising effort to move the full TCP/IP stack from the software to the hardware to improve the network performance and programmability further. The hardware-based TCP/IP stack must be utterly correct since TCP is the foundation of many critical applications. However, it is impractical to apply the conventional model checking methods or decomposition techniques to verify the correctness because there are numerous stateless and stateful functions involved in TCP/IP stack. Therefore, we propose an automated field-based decomposition method to make feasible the model checking of the hardware-based TCP/IP. Our method can significantly mitigate the state space explosion issue while maintaining the verification completeness. We choose FPGA, a popular programmable hardware, as our study object in the paper. Our method effectiveness is demonstrated by the verification of both stateful and stateless functions of the FPGA-based TCP/IP.

Network protocols are challenging to test for correctness due to the huge number of packet dynamics possibilities. Network simulators are popular in evaluating the performance of network protocols but unable to test the correctness under different packet dynamics efficiently. Random testing and symbolic execution are two effective automated correctness testing techniques that can explore different program execution possibilities. Random testing is simple and scalable in checking typical cases but often misses corner ones with low probabilities. Symbolic execution is more efficient in exploring these corner cases but suffers from the scalability problem. In this paper, we propose a testing platform built upon a network simulator by implementing a combination of symbolic execution and random testing to mitigate their limitations. Then we evaluate the efficiency of different techniques in testing Linux network stack under multiple possibilities of packet dynamics.

Smartphones have recently become a popular platform for deploying the computation-intensive virtual reality (VR) applications, such as immersive video streaming (a.k.a., 360-degree video streaming). One specific challenge involving the smartphone-based head mounted display (HMD) is to reduce the potentially huge power consumption caused by the immersive video. To address this challenge, we first conduct an empirical power measurement study on a typical smartphone immersive streaming system, which identifies the major power consumption sources. Then, we develop QuRate, a quality-aware and user-centric frame rate adaptation mechanism to tackle the power consumption issue in immersive video streaming. QuRate optimizes the immersive video power consumption by modeling the correlation between the perceivable video quality and the user behavior. Specifically, QuRate builds on top of the user's reduced level of concentration on the video frames during view switching and dynamically adjusts the frame rate without impacting the perceivable video quality. We evaluate QuRate with a comprehensive set of experiments involving 5 smartphones, 21 users, and 6 immersive videos using empirical user head movement traces. Our experimental results demonstrate that QuRate is capable of extending the smartphone battery life by up to 1.24X while maintaining the perceivable video quality during immersive video streaming. Also, we conduct an Institutional Review Board (IRB)-approved subjective user study to further validate the minimum video quality impact caused by QuRate.

The packet time information at their receivers carries useful network information and is used by various networking applications and protocols. However it is challenging to accurately measure the packet time information in a cloud network due to various software and hardware factors at their receivers, such as virtual machine (VM) scheduling. In order to mitigate the impact of those receiver factors, we propose a novel packet timestamping mechanism to measure the inter-packet gaps just before they arrive at their receiver using an external clock server, which periodically sends packets to the receiver. We demonstrate the application of the proposed timestamping mechanism using an improved available bandwidth estimation method, which leverages two types of packet time information: the original packet time information measured using the local receiver clock, and the additional inter-packet gap information measured using the external clock server. Both our experiment results and analysis show that the additional information can greatly improve the available bandwidth estimation accuracy in a cloud network even with heavy VM scheduling at the cost of little additional traffic overhead.

The correctness of network protocol implementations is difficult to test mainly because of the temporal uncertain nature of network events. In order to test the correctness of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of temporal uncertain events, which is very time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch, and thus is more efficient than brute force testing. In this paper, we argue that the efficiency of SEIB could be further exponentially improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes.

Realistic network environments are commonly emulated by Internet application developers to test both the performance and the correctness of their applications. In this paper, we argue that emulating just realistic network environments may be inadequate for detecting hard-to-detect faults that have very low occurrence probabilities but potentially high impact if exposed in the real world. Specifically, we conduct extensive experiments to study the correctness testing capabilities of realistic and unlikely network environments. Our results show that small investments in emulating unlikely network environments may help in quickly detecting otherwise hard-to-detect faults.

New TCP congestion control algorithms are being developed and deployed in the Internet. However, it is challenging to test their correctness mainly due to the scalability problem caused by the extremely large number of test inputs. In this paper, we propose a scalable testing method, called SCCT, which tackles the scalability problem using two techniques. 1) SCCT tests only the congestion control algorithms of TCP at the interface level instead of the whole TCP at the packet level. 2) SCCT exercises an equivalence class of test inputs simultaneously using symbolic execution, instead of a single test input at a time. Both techniques can improve the scalability by many orders of magnitude. Our Linux TCP experiments on seven congestion control algorithms show that SCCT is scalable and quickly detects multiple Linux bugs that have not been reported before.

The majority of Internet traffic is transferred by transport protocols. The correctness of these transport protocol implementations is hard to validate as their behaviors depend not only on their protocols but also on their network environments that can introduce dynamic packet delay and loss. Random testing, widely used in industry due to its simplicity and low cost, struggles to detect packet delay related faults which occur with low probability. Symbolic execution based testing is promising at detecting such low probability faults, but it requires large testing budgets as it attempts to cover a prohibitively large input space of packet dynamics. To improve its cost-effectiveness, we propose two domain-specific heuristic techniques, called packet retransmission based priority and network state based priority, which are motivated by two common transport protocol properties. In our experiments using the Linux TFTP programs, our techniques improve the cost-effectiveness of symbolic execution based testing for transport protocols, detecting three times as many faults when the budget is in the range of minutes and hours.

Network programs are difficult to test, especially under the large space of network program behavior defined by packet dynamics such as packet delay and packet loss. It is unlikely for common approaches using testbeds with random packet dynamics to cover the prohibitively large number of packet dynamics possibilities in a limited time. In this paper, we leverage symbolic execution to find the equivalence classes of packet dynamics which lead to exactly the same network program behavior, in order to efficiently check the large space of network program behavior. Specifically, we propose and develop a network program test platform, called Symbolic Packet Dynamics (SPD), to automatically and transparently test unmodified network programs for low- probability bugs and extreme-case performance under packet dynamics. SPD uses symbolic representation of packet dynamics, instead of random packet dynamics. Our experiments show that SPD can achieve significantly much higher packet dynamics coverage than random packet dynamics within the same amount of time, and thus it is much easier and takes much shorter time for SPD to detect low-probability bugs and extreme-case performance.

A fundamental problem of current bandwidth estimation methods is that they require accurate packet time information. However, it is hard to accurately measure packet time information in an increasing number of network environments, such as widely deployed high speed networks, and emerging cloud computing networks. Motivated by the observation that many applications only need the relative bandwidth information of different paths instead of the actual bandwidth information of a single path, we propose sequence-based bandwidth comparison. Specifically, this paper proposes a capacity comparison method, called Path Comp, which can relatively compare the capacities of the paths from two senders to the same receiver. Path Comp mainly uses the arrival sequence information of packets, and does not require any accurate packet time information. Our test bed, campus network, and EC2 experiments show that Path Comp can not only determine which path is faster but also accurately determine how much faster in a variety of network environments.

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional RENO, whereas it is now controlled by multiple different TCP algorithms, such as RENO, CUBIC, and Compound TCP (CTCP). However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of a remote Web server. CAAI can identify all default TCP algorithms (e.g., RENO, CUBIC, and CTCP) and most non-default TCP algorithms of major operating system families. We then present the CAAI measurement result of about 30 000 Web servers. We found that only 3.31 % ~ 14.47 % of the Web servers still use RENO, 46.92% of the Web servers use BIC or CUBIC, and 14.5 % ~ 25.66 % of the Web servers use CTCP. Our measurement results show a strong sign that the majority of TCP flows are not controlled by RENO anymore, and a strong sign that the Internet congestion control has changed from homogeneous to heterogeneous.

The router buffer sizing problem is a vital problem to the performance of the Internet. The traditional rule-of-thumb is that the router buffer size should be equal to the bandwidth-delay product (BDP) of a link. Recent studies show that the router buffer size can be significantly smaller than the BDP without causing negative impact on the TCP performance in the Internet. But a fundamental assumption of all those studies is that all the TCP traffic in the Internet is generated by the traditional RENO protocol, which, however, is no longer true as the current Internet is dominated by multiple different TCP protocols, such as RENO, CUBIC and Compound TCP (CTCP). Thus, it is imperative that we revisit the router buffer sizing problem for the Internet with heterogeneous TCP. In this paper, we propose methods to determine the router buffer size requirements under various constraints for the Internet with heterogeneous TCP and discuss the tradeoff among the constraints. The constraints considered include the link utilization constraint, the packet drop rate constraint, and the queuing delay constraint. Our study shows that the required router buffer size can be significantly smaller than the BDP but also demonstrates that it is dependent on the protocol mix of the heterogeneous TCP flows.

Most of the commercial peer-to-peer (P2P) video streaming deployments support hundreds of channels and are referred to as multichannel systems. Recent research studies have proposed specific protocols to improve the streaming quality for all channels by enabling cross-channel cooperation among multiple channels. In this paper, we focus on the following fundamental problems in designing cooperating multichannel systems: 1) what are the general characteristics of existing and potential designs? and 2) under what circumstances should a particular design be used to achieve the desired streaming quality with the lowest implementation complexity? To answer the first question, we propose simple models based on linear programming and network-flow graphs for three general designs, namely Naive Bandwidth allocation Approach (NBA), Passive Channel-aware bandwidth allocation Approach (PCA), and Active Channel-aware bandwidth allocation Approach (ACA), which provide insight into understanding the key characteristics of cross-channel resource sharing. For the second question, we first develop closed-form results for two-channel systems. Then, we use extensive numerical simulations to compare the three designs for various peer population distributions, upload bandwidth distributions, and channel structures. Our analytical and simulation results show that: 1) the NBA design can rarely achieve the desired streaming quality in general cases; 2) the PCA design can achieve the same performance as the ACA design in general cases; and 3) the ACA design should be used for special applications.

It is challenging to provide delay-bounded service in a large-scale P2P live streaming system since a P2P streaming system is not scalable from the perspective of playback delay. However, certain peers called subscribers are more sensitive to playback delay than other peers, and the violation of the delay bound dramatically affects their satisfaction. In this paper, we study subscriber bounded delay (SBD) problem, which aims to provide bounded delay service to subscribers and best-effort delay service to ordinary peers in a large-scale single channel P2P live streaming system. We formulate the SBD as a decision problem and prove that it is NP-Complete. Then we propose a decentralized heuristic called the high fanout promotion (HFP) algorithm, which helps the system to serve the maximum number of subscribers with delay-bounded service, and to provide best-effort delay service to remaining subscribers and ordinary peers. We evaluate its performance using simulation experiments and compare our approach with the naive greedy algorithm and the general delay minimization approaches in the literature. Our extensive packet-level simulations show that our distributed solution can serve more subscribers with bounded delay video service compared to the other two methods (17%-50% in our simulations). Our distributed algorithm works well in both homogeneous and heterogeneous environments, and it converges very fast.

Energy consumption is becoming a serious issue for data centers. Minimizing the energy consumption of a data center is a complex problem. It consists of developing energy models for servers and network elements and investigating energy-aware (green) routing strategies using these models. In this paper, we adapt energy models for servers and network elements in a data center. The server energy model incorporates the impact of temperature and voltage of a server on its leakage energy. Using the server and network energy models, we propose a green routing scheme that minimizes the total combined energy consumption of servers and network elements in a data center under dynamic traffic. The proposed green routing scheme uses dynamic voltage scaling, rate adaptation, and anycast transmission for minimizing the total energy consumption. Extensive simulation results validate the effectiveness of the proposed green routing in minimizing the total energy consumption of a data center as compared to well-known existing approaches.

Data Center Network architectures (DCN) are evolving for increased scalability, performance, and low network complexity. In this paper, we propose HyScale, a switch-centric DCN architecture using hybrid optical networks. HyScale employs Optical Burst Switching and Optical Circuit Switching technologies for transmitting low and high volumes of data respectively in a data center. The proposed architecture is highly scalable, recursively defined, fault-tolerant, and has low network complexity. It also has a multitude of desirable graph-theoretic properties like high bisection width, and low diameter. By exploiting the structural properties of HyScale, we propose a highly efficient and simple routing scheme. In our experiments, the proposed routing scheme gives a lower packet loss ratio by an average of 23% as compared to the Shortest Path Routing with almost negligible increase in the length of the routes.

The state of the resources at a destination in Grid computing over OBS architecture (GoOBS) may change between a task's selection of a destination and its arrival at the destination. These changes in the availability of the resources requested at the destination may lead to blocking of tasks, and thus increase the resource blocking rate. In this paper, we investigate the resource scheduling problem in GoOBS. Our objective is to minimize the resource blocking rate by containing the impact of the changes in the availability of the resources at a destination. We propose a non-selfish destination selection paradigm to minimize the resource blocking rate. The selection of a destination by a request is called non-selfish, if the selected destination has sufficient resources available to simultaneously process one or more additional requests. Extensive simulations were performed to validate the effectiveness of the heuristics based on the non-selfish destination selection paradigm. Among the proposed heuristics, the NFFD heuristic is most effective in minimizing the resource blocking rate. Compared to the best existing approach, the NFFD heuristic reduces the resource blocking rate by 21% to 73% in our experiments.

Nowadays, millions of Internet users watch and upload a large number of videos on User Generated Content (UGC) sites (e.g., Youtube) everyday. Moreover, online videos about hot events, such as breaking news and Olympic games, attract lots of users. In this paper, we study the characteristics of hot-event videos by collecting video traces of the largest UGC site in China for 28 days. We first empirically study statistical properties of such videos and find that hot-event videos contribute a large number of views, even though the total number of hot-event videos is relatively small. In addition, there exist extremely active uploaders and top 10% active uploaders upload over 60% videos. The video popularity demonstrates high skewness, where top 5% the most popular videos contribute over 80% views. Finally, we analyze the popularity evolution of hot-event videos using the consecutive 28-day video traces. The popularity of the studied videos decays very fast and most of these videos remain popular for only a week. Our findings reflect the most recent developments of UGC sites, which provide technical and commercial insights for engineers and UGC site owners.

Digital video recorder (DVR) style and non-prerecording (NPR) style are two possible implementations for P2P-based time-shifted streaming, but existing P2P streaming solutions are not suitable to implement the NPR method. Since peers can view any arbitrary video segments which have been broadcasted, they might encounter severe video quality problems and the server bandwidth consumption can become high. In this paper, we focus on minimizing the server bandwidth consumption to maintain smooth streaming service in NPR-style P2P-based time-shifted streaming. To reduce the server cost, peers prefetch segments which are not required for their current viewing. Hence even if they are viewing different parts of the video, they can exchange segments with one another. However, segment prefetching competes for bandwidth with ordinary segment fetching, and it might bring negative impact. A good prefetching solution should not affect peers' viewing experience. We formulate the problem of finding a prefetching solution as an optimization problem, with the objective to minimize the server bandwidth consumption. Then we propose a heuristic algorithm by decomposing the global optimization problem into a set of smaller problems. Each peer runs this algorithm to determine which segments to prefetch and how to serve other peers. Simulation experiments demonstrate that our design provides P2P-based time-shifted streaming at low server bandwidth consumption.

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of a remote web server. CAAI can identify all default TCP algorithms (i.e., AIMD, BIC, CUBIC, and CTCP) and most non-default TCP algorithms of major operating system families. We then present, for the first time, the CAAI measurement result of the 5000 most popular web servers. Among the web servers with valid traces, we found that only 16.85~25.58\% of web servers still use the traditional AIMD, 44.51\% of web servers use BIC or CUBIC, and 10.27$\sim$19\% of web servers use CTCP. In addition, we found that, for the first time, some web servers use non-default TCP algorithms, some web servers use some unknown TCP algorithms which are not available in any major operating system family, and some web servers use abnormal slow start algorithms. Our CAAI measurement results show a strong sign that the majority of TCP flows are not controlled by AIMD anymore, and a strong sign that the Internet congestion control has already changed from homogeneous to highly heterogeneous.

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Five years ago, Internet traffic was mainly controlled by the standard TCP AIMD algorithm, whereas Internet traffic is now controlled by many different TCP congestion control algorithms, such as AIMD, CUBIC, CTCP, and FAST. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP congestion control algorithms. In this paper, we present our initial work towards measuring such important information in the Internet. Specifically, considering that web traffic comprises a significant portion of the total Internet traffic, we propose a method that can actively infer the TCP multiplicative decrease parameter of a remote web server. The multiplicative decrease parameter, together with other TCP characteristics (such as the window growth function to be measured in our future work), can be used to uniquely identify the TCP congestion control algorithm of a web server. Our extensive lab test-bed experiments show that our method can infer the TCP multiplicative decrease parameter with reasonably good accuracy.

Peer-to-peer (P2P) technology greatly scales up traditional Internet streaming service. However, the philosophy that peers help one another distribute video content produces a large amount of cross-ISP P2P traffic. Newly proposed ISP-friendly P2P mechanisms reduce the cross-ISP P2P traffic by using locality-based peer selection methods with which peers tend to connect to other peers in the same ISP domain. However, one unanswered question is that how we can achieve the tradeoffs between the cross-ISP P2P traffic and the P2P streaming performance if there are conflicts between them. In this paper, we propose a rate allocation mechanism for achieving the tradeoffs between the cross-ISP P2P traffic and the P2P streaming performance. We model the tradeoffs as a multiobjective optimization problem and solve it using the Goal Attainment method. The evaluation result shows that our mechanism is able to achieve the tradeoffs between the conflicts and maintain good fairness among peers and streaming overlays.

Peer-to-peer (P2P) technology has become an attractive approach for enabling large-scale video streaming applications, but the factor of users' subjective preferences is usually ignored in such networks. As users have different demands on video quality, we have proposed several schemes, to address the design challenge of providing all users uninterrupted video with their desired qualities in case their demands change dynamically. However, there is still a lack of theoretical analysis of how good we can achieve, and what guidelines we should follow when designing schemes in case of demand heterogeneity. To shed more light on demand heterogeneity problem, we model the problem as a resource demand and supply problem. We propose an optimization method to improve bandwidth efficiency through efficient bandwidth allocation. We develop a tiered overlay and a price-rated mechanism to implement cooperation among peers, and present a framework to address the challenge via efficient bandwidth allocation and group cooperation. Through complementary simulations, we evaluate the effectiveness of the proposed framework, and show that it effectively helps existing solutions, such as the Partial Participation Scheme (PPS), achieve better performance.

Most of the commercial P2P video streaming deployments support hundreds of channels and are referred to as multichannel systems. Measurement studies show that bandwidth resources of different channels are highly unbalanced and thus recent research studies have proposed various protocols to improve the streaming qualities for all channels by enabling cross-channel cooperation among multiple channels. However, there is no general framework for comparing existing and potential designs for multi-channel P2P systems. The goal of this paper is to establish tractable models for answering the fundamental question in multi-channel system designs: Under what circumstances, should a particular design be used to achieve the desired streaming quality with the lowest implementation complexity? To achieve this goal, we first classify existing and potential designs into three categories, namely Naive Bandwidth allocation Approach (NBA), Passive Channel-aware bandwidth allocation Approach (PCA) and Active Channel-aware bandwidth allocation Approach (ACA). Then, we define the bandwidth satisfaction ratio as a performance metric to develop linear programming models for the three designs. The proposed models are independent of implementations and can be efficiently solved due to the linear property, which provides a way of numerically exploring the design space of multi-channel systems and developing closed-form solutions for special systems.

The success of commercial Peer-to-Peer (P2P) video streaming systems has triggered interest in exploiting end users' bandwidth to reduce the operating costs of IPTV and Content Distribution Networks (CDN) and to improve the user-perceived service quality. Traditionally, users watching different channels are organized into separate overlays, where there is no cooperation among different channels. However, based on measurement studies, cross-channel cooperation is found to be desirable due to the bandwidth imbalance among different channels. In this paper, we focus on studying the characteristics of existing and potential designs to help system designers choose proper cross-channel cooperation strategies considering efficiency and implementation complexity. Specifically, we propose simple models based on network flow graphs for three general designs, namely Naive Bandwidth allocation Approach (NBA), Passive Channel-aware bandwidth allocation Approach (PCA) and Active Channel-aware bandwidth allocation Approach (ACA) respectively, which capture the key characteristics of different designs. We develop closed-form results for two-channel systems. Then, we use extensive numerical simulations to compare the three designs for various peer population distributions, upload bandwidth distributions and channel structures. Our analytical and simulation results show that: 1) Though the NBA design can be implemented with low complexity, it cannot efficiently use user's bandwidth in general cases; 2) the PCA design can achieve the same bandwidth utilization efficiency as the ACA design in general cases; and 3) the ACA design should be used for special applications and systems in which a user is restricted to watch only one channel at a time.

Due to their widespread popularity, peer-to-peer (P2P) live streaming systems have become a great challenge for Internet service providers (ISPs) as they consume huge amount of Internet bandwidth. By observing that different users may watch a channel with different window sizes, we propose a cooperative scheme called partial participation scheme (PPS) in which different peers request a video stream at different rates based on their window sizes, and a subset of peers viewing the video stream using a small window work as helpers to forward extra data to help other peers using a large window. By reducing streaming rate received by small-window peers, the total amount of consumed bandwidth decreases without sacrificing users' satisfaction. PPS includes peer cooperative bandwidth allocation algorithms and neighbor maintenance mechanisms to achieve short resizing delay when a peer changes its window between different sizes. We evaluate the performance of PPS via a comprehensive set of metrics generated from extensive simulations. Our simulation results show that PPS greatly reduces the bandwidth consumption, achieves short resizing delay, and maintains high and stable streaming quality.

In this paper, we systematically study a fundamental tradeoff for TCP friendliness: in order for a congestion control protocol to maintain a certain degree of TCP friendliness, the longer its smoothness timescale is, the lower its average sending rate should be. This throughput-smoothness tradeoff exists not only for the traditional definition of TCP friendliness but also for any congestion control protocols that are designed to prevent competing TCP flows from complete starvation (which we believe is a basic requirement for a traffic control protocol) and then maintain a certain degree of TCP friendliness. Specifically, we derive the TCP-friendly sending rate requirements for three different smoothness timescales (i.e., milliseconds, seconds, and minutes) with a flow-level queueing model, and verify the analytical results with extensive packet-level simulation results. Finally, we propose a new TCP-friendly congestion control protocol for applications that prefer a smooth predictable sending rate on a multi-minute timescale, called Long-Time-Scale TCP-Friendly CBR-Like Rate Control (L-TFCBR).

Most of the literature on peer-to-peer (P2P) live streaming focuses on how to provide best-effort streaming quality by efficiently using the system bandwidth; however, there is no guarantee about the provided streaming quality. This paper considers how to provide statistically guaranteed streaming quality to a P2P live streaming system. We study a class of admission control algorithms which statistically guarantee that a P2P live streaming system has sufficient overall bandwidth. Our results show that there is a tradeoff between the user blocking rate and user-behavior insensitivity (i.e., whether the system performance is insensitive to the fine statistics of user behaviors). We also find that the system performance is more sensitive to the distribution change of user inter-arrival times than to that of user lifetimes.

Multi-view peer-to-peer (P2P) live streaming systems have recently emerged, where a user can simultaneously watch multiple channels. Previous work on multi-view P2P streaming solves the fundamental inter-channel bandwidth competition problem at the individual peer level, and thus can be used with very limited types of streaming protocols. In this paper, we propose a new protocol for multi-view P2P streaming, called divide-and-conquer (DAC), which efficiently solves the inter-channel bandwidth competition problem using a divide-and conquer strategy at the channel level, and thus is flexible to work with various streaming protocols. This makes DAC more suitable for upgrading current single-view P2P live streaming systems to multi-view P2P live streaming systems. Our extensive packetlevel simulations show that DAC is efficient in allocating the overall system bandwidth among competing channels, is flexible in working with various streaming protocols, and is scalable in supporting a large number of users and channels.

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(\delta ) time and message complexity where \delta is the maximum size of a two-hop neighborhood in a wireless network while message complexity remains O(\delta ), assuming that message delays can be bounded by an unknown constant. DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move, such as wireless mesh networks and wireless sensor networks. We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling. Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced. We further evaluate the effect of the time-varying nature of wireless links on the conflict-free property of DRAND-assigned time slots. This experiment is conducted on a 55-node testbed consisting of the more recent MicaZ sensor nodes.

Data-driven (or swarming based) streaming is one of the popular ways to distribute live multimedia streaming traffic over peer-to-peer (P2P) networks. The efficiency and user satisfaction highly depend on the constructed overlays. The common neighbor selection algorithms in existing overlay construction schemes usually randomly select a fixed number of neighbors which satisfy the selection requirements, such as end-to-end delay or a peerpsilas sojourn time. However, this fixed random neighbor-selection algorithm (FRNS) neglects the peerspsila upload bandwidth heterogeneity and therefore, the upload bandwidth cannot be efficiently used. In this paper, we propose a variable random neighbor-selection (VRNS) scheme to alleviate the problems due to bandwidth heterogeneity, and in which the number of neighbors with different upload bandwidths is dynamically determined by the statistical bandwidth information of the system. Our proposed scheme is shown to outperform FRNS based upon a large volume of carefully designed simulations.

The network coding paradigm has become an effective method for achieving efficient multicast in communication networks. The optical community has just started to venture into the application of network coding in optical networks. However, a number of challenges need to be overcome before network coding can be used in optical networks. These include limited buffering and processing capabilities as well as extremely coarse bandwidth granularity. In this paper, we address some of these problems. Finding multicast codes can be broken into two subproblems: finding a subgraph of the topology to code over and then finding an actual code for that subgraph. We show that the former problem is NP-Complete and provide heuristics which allow for coded multicast in optical wavelength division multiplexing networks which offer a modest improvement in bandwidth efficiency over traditional methods for finding routes for optical-layer multicast traffic.

Peer-to-peer (P2P) streaming systems, in which individual nodes or peers operated by ordinary Internet users collaborate to serve video streams, have recently aroused considerable interest in both academia and industry. An important problem in P2P streaming systems is how to reduce their consumed bandwidth, which is a major concern of Internet service providers. Our work is motivated by the fact that a user may dynamically change the size of a window displaying a video stream according to his/her personal choice, a scenario we refer to as dynamic window resizing. In this paper, we propose a scheme called the partial forwarding scheme (PFS) based on layered coding, in which users with small windows help in forwarding a part of the enhancement layer. PFS significantly reduces the total consumed bandwidth while still maintaining the desired streaming quality. Our extensive simulation results show that PFS can reduce the total consumed bandwidth by up to 40% while still maintaining satisfactory streaming quality.

The definition of TCP friendliness has been evolved over time from the traditional one for congestion control protocols to the recent ones for admission control protocols. All of them can effectively prevent the Internet from congestion collapse and TCP starvation, while enabling a wide variety of traffic control protocols other than TCP. However, the current TCP-friendly admission control protocols are designed to be TCP friendly only on fairly long time scales. That is, it is likely that a group of TCP users all experience persistent poor performance during their transmission, which then leads to dissatisfaction of TCP users. In this paper, we first present a new definition of TCP friendliness, called Stochastic TCP Friendliness, with which we study the time scale of TCP-friendly admission control protocols. Second, we develop a new traffic control protocol, called Stochastically TCP- Friendly Admission Control (STFAC), which is stochastically TCP friendly not only on a long time scale but also on a short time scale. Finally, we present very encouraging simulation results showing that STFAC can considerably improve the performance of UDP users and TCP users on both a long time scale and a short time scale, when compared with the traditional TCP- friendly congestion control protocols.

Motivated by the success of the Picture in Picture feature of the traditional TV, several commercial Peer-to-Peer MultiMedia Streaming (P2PMMS) applications now support the multi-view feature, with which a user can simultaneously watch multiple channels on its screen. This paper considers the peer selection problem in multi-view P2PMMS. This problem has been well studied in the traditional single-view P2PMMS; however, it becomes more complicated in multi-view P2PMMS, mainly due to the fact that a peer watching multiple channels joins multiple corresponding overlays. In this paper, we propose a novel peer selection algorithm, called Channel-Aware Peer Selection (CAPS), where a peer selects its neighboring peers based on the channel subscription of the system, in order to efficiently utilize the bandwidth of all peers in the system, especially those peers watching multiple channels. The results of a large-scale simulation with 10,000 peers and 4 channels shows that CAPS can significantly improve the system performance over the straightforward Random Peer Selection (RPS), which is widely used in single-view P2PMMS networks.

While the current definition of TCP friendliness has enabled a wide variety of traffic control protocols other than TCP, it still considerably restricts the design space of TCP-friendly traffic control protocols. For example, some multimedia streaming applications prefer a smooth sending rate on a time scale of minutes, however, a UDP flow maintaining a smooth sending rate on such a long time scale is naturally not TCP friendly by the current definition. In this paper, we first give a new class of TCP friendliness definitions, called stochastic TCP friendliness, which greatly expands the design space of TCP-friendly traffic control protocols, while still effectively maintaining the desired stability and fairness of the Internet. In particular, we propose stochastic TCP friendliness in usual stochastic order as a more appropriate design guideline for traffic control protocols, which intuitively ensures that a UDP flow is friendly to all competing TCP flows with any increasing utility function. Second, we develop a congestion control protocol, called TCP-friendly CBR-like rate control, which achieves a smooth sending rate on a time scale of minutes, and at the same time is stochastically TCP friendly in usual stochastic order in most network environments.

Window growth function for congestion control is a strong determinant of protocol behaviors, especially its second and higher-order behaviors associated with the distribution of transmission rates, its variances, and protocol stability. This paper presents a new stochastic tool, called convex ordering, that provides an ordering of any convex function of transmission rates of two protocols and valuable insights into high order behaviors of protocols. As the ordering determined by this tool is consistent with any convex function of rates, it can be applied to any unknown metric for protocol performance that consists of some high-order moments of transmission rates, as well as those already known such as rate variance. Using the tool, it is analyzed that a protocol with a growth function that starts off with a concave function and then switches to a convex function (e.g., an odd order function such as x3and x5) around the maximum window size in the previous loss epoch, gives the smallest rate variation under a variety of network conditions. Among existing protocols, BIC and CUBIC have this window growth function. Experimental and simulation results confirm the analytical findings.

TCP-Friendly Rate Control (TFRC) is being adopted in Internet standards for congestion control of various streaming media applications. In this paper, we consider the transmission of pre-recorded media from a server to a client by using TFRC, and analytically study the impact of TFRC on user-perceived media quality, which is roughly measured by calculating the rebuffering probability. A rebuffering probability is defined to be the probability that the total duration of all rebuffering events experienced by a user is longer than a certain threshold. Two approaches are presented to help an application determine an appropriate initial buffering delay and media playback rate in order to achieve a certain rebuffering probability under a given network condition. First, we derive a closed- form expression to approximate the average TFRC sending rate, which could be used as the maximum allowed playback rate of a media stream. Second, we develop a queueing model for a TFRC client buffer with the traffic described by a Markov-Renewal- Modulated Deterministic Process (MRMDP), and present an iterative method to calculate the rebuffering probability.

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(δ) time and message complexity where δ is the maximum size of a two-hop neighborhood in a wire-less network while message complexity remains O(δ), assuming that message delays can be bounded by an unknown constant.DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move,such as wireless mesh networks and wireless sensor networks.We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling.Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced.

TCP-friendly rate control (TFRC), an equation-based congestion control protocol, has been a promising alternative to TCP for streaming multimedia applications. However, TFRC using the TCP response function has the same bandwidth scalability problem as TCP in high-speed long-distance networks. In this paper, we propose high-speed equation-based rate control (HERC) for streaming multimedia transfer over high-speed long-distance networks, as an extension of TFRC by replacing the TCP response function with a high-speed response function. Our result indicates that while HERC achieves better bandwidth scalability than TFRC, it has worse smoothness than TFRC with the same loss history size. We prove that the smoothness index measured by the coefficient of variation of sending rates is approximately equal to 1.09d//spl radic/LCoV[/spl theta/] where d is the exponent parameter of the response function, L is the loss history size, and CoV[/spl theta/] is the coefficient of variation of loss intervals. Furthermore, we show that by setting L to 32d/sup 2/, HERC with any value of d can achieve the same smoothness as TFRC under the same loss interval distribution.

We study limitations of an equation-based congestion control protocol, called TFRC (TCP Friendly Rate Control). It examines how the three main factors that determine TFRC throughput, namely, the TCP friendly equation, loss event rate estimation and delay estimation, can influence the long-term throughput imbalance between TFRC and TCP. Especially, we show that different sending rates of competing flows cause these flows to experience different loss event rates. There are several fundamental reasons why TFRC and TCP flows have different average sending rates, from the first place. Earlier work shows that the convexity of the TCP friendly equation used in TFRC causes the sending rate difference. We report two additional reasons in this paper: (1) the convexity of 1/x where x is a loss event period and (2) different RTO (retransmission timeout period) estimations of TCP and TFRC. These factors can be the reasons for TCP and TFRC to experience initially different sending rates. But we find that the loss event rate difference due to the differing sending rates greatly amplifies the initial throughput difference; in some extreme cases, TFRC uses around 20 times more, or sometimes 10 times less, bandwidth than TCP.

High-speed networks with large delays present a unique environment where TCP may have a problem utilizing the full bandwidth. Several congestion control proposals have been suggested to remedy this problem. The existing protocols consider mainly two properties: TCP friendliness and bandwidth scalability. That is, a protocol should not take away too much bandwidth from standard TCP flows while utilizing the full bandwidth of high-speed networks. This work presents another important constraint, namely, RTT (round trip time) unfairness where competing flows with different RTTs may consume vastly unfair bandwidth shares. Existing schemes have a severe RTT unfairness problem because the congestion window increase rate gets larger as the window grows ironically the very reason that makes them more scalable. RTT unfairness for high-speed networks occurs distinctly with drop tail routers for flows with large congestion windows where packet loss can be highly synchronized. After identifying the RTT unfairness problem of existing protocols, This work presents a new congestion control scheme that alleviates RTT unfairness while supporting TCP friendliness and bandwidth scalability. The proposed congestion control algorithm uses two window size control policies called additive increase and binary search increase. When the congestion window is large, additive increase with a large increment ensures square RTT unfairness as well as good scalability. Under small congestion windows, binary search increase supports TCP friendliness. The simulation results confirm these properties of the protocol.

We consider an edge optical burst switching (OBS) node with or without converters, and with no buffering. The OBS node serves a number of users, each connected to the switch over a fiber link that supports multiple wavelengths. Each wavelength is associated with a 3-state Markovian burst arrival process. The arrival process permits short and long bursts to be modeled. We model the edge OBS node as a closed nonproduct-form queueing network, with multiple heterogeneous classes, and we develop a suite of approximate decomposition algorithms to analyze it. Our approximate algorithms have a good accuracy, and they provide insight into the effect of various system parameters on the performance of the edge OBS node.