This research is motivated by the network construction problem studied in [2], [5], [8]–[10]. It has applications in the areas of overlay network construction and wireless coverage of networks. Given a weighted undirected graph and a list of requests of connectivity constraints on some subsets of vertices, the objective is to form connected subgraphs such that all the connectivity constraints are satisfied and the total cost of the selected edges is minimized. This problem was proved APX-complete [8], [9]. In the past two decades, the network construction problem and its variants have been studied in both online and offline settings. The performance of these variants, algorithms relies on the sizes of the connectivity constraints. In this work, we generalize the problem by introducing Steiner vertices into connectivity constrains. We focus on designing algorithms for this Steiner network construction problem on various graph topologies. We present efficient optimal online and offline algorithms for this problem’s variants, particularly, on cycles and bipartite graphs. Our algorithmic approaches are new in dealing with this network construction problem and its variants.

Social Virtual Reality (VR) is regarded as one of the most popular VR applications since it transcends geographical barriers, allowing users to interact in simulated environments for various purposes. Despite its promising prospects, there is a growing concern about the harassment issue due to the immersive nature of social VR compared to other online social environments. Existing protections against harassment in social VR are highly limited in terms of practical effectiveness. The deficiency of studies toward understanding and preventing harassment in social VR further complicates the regulation and intervention efforts of social VR platforms in such situations. To address these challenges, we, in this paper, quantitatively investigate human interaction behaviors in social VR. More specifically, we first build a customized platform based on Mozilla Hubs, a popular social VR platform, to collect data about users’ social interaction behaviors involving harassment instances. A subsequent analysis of the collected dataset SAHARA (Social interAction beHAviors in vR with hArassment) reveals that the task of online harassment detection in social VR is complicated since it depends on not only users’ actions but also their spatial and temporal relationships. To accurately discern harassment, we propose a novel framework HardenVR (HA-Rassment DEtectioN framework for social VR). As a context-aware harassment detection framework, HardenVR employs a transformer-based model to capture relative poses and learn users’ hand actions in 6-DOF (Degree-of-Freedom). Meanwhile, multiple mechanisms, including the extra attention mechanism, distance-aware clustering method, and the sliding window, have been introduced into the model to handle challenges of data imbalance, over-fitting, and continuous detection. The design of HardenVR aims to achieve the balance between accuracy, efficiency, and cost-effectiveness for the task of harassment detection. As a starting point, HardenVR successfully learns pose information as the context to identify harassment and the experiment results show its detection accuracy as high as 98.26%.

In this paper, we design, analyze, and evaluate a hybrid quantum algorithm for the metric traveling salesman problem (TSP). TSP is a well-studied NP-complete problem that many algorithmic techniques have been developed for, on both classic computers and quantum computers. The existing literature of algorithms for TSP are neither adaptive to input data nor suitable for processing medium-size data on the modern classic and quantum machines. In this work, we leverage the classic computers’ power (large memory) and the quantum computers’ power (quantum parallelism), based on the input data, to fasten the hybrid algorithm’s overall running time. Our algorithmic ideas include trimming the input data efficiently using a classic algorithm, finding an optimal solution for the post-processed data using a quantum-only algorithm, and constructing an optimal solution for the untrimmed data input efficiently using a classic algorithm. We conduct experiments to compare our hybrid algorithm against the state-of-the-art classic and quantum algorithms on real data sets. The experimental results show that our solution truly outperforms the others and thus confirm our theoretical analysis. This work provides insightful quantitative tools for people and compilers to choose appropriate quantum or classical or hybrid algorithms, especially in the NISQ (noisy intermediate-scale quantum) era, for NP-complete problems such as TSP.

Multiuser Augmented Reality (MuAR) is essential to implementing the vision of Metaverse for its capability to provide immersive and interactive experiences. In such experiences, peer positions are critical to understand each other’s intentions and actions so as to guarantee the smooth cooperation among users. However, we find that the explicit peer positions provided by the current practice could be incomplete and/or inaccurate in some situations, which leads to the weakened spatial awareness. To achieve the accurate peer tracking in MuAR, we propose a novel multiple sensors information fusion method, CSA (Coordinate System Alignment), to detect and correct defective relative positions by the current practice. CSA firstly formulates problem of correcting erroneous positions into an overdetermined system, and then finds the solution by applying the simulated annealing algorithm to expedite the search process. The evaluation results show that CSA’s ability to reduce errors significantly (58.3% on average) under long-term error duration, especially its advantage in reducing the relative direction errors. The result confirms the potential of CSA to provide reliable peer tracking in MuAR. Meanwhile, it does not impose extra restrictions on users’ practice with current mobile devices in experiences.

Multiuser Augmented Reality (MuAR) is essential to implementing the vision of Metaverse. With the pervasive mobile devices, MuAR enables multiple devices to share a common AR experience. In such experiences, the peer positions are critical to understand peers' intentions and actions so as to achieve the smooth interaction in AR. Such a spacial awareness requirement poses new challenges to MuAR. Traditionally, in AR experiences designed for the single user, the SLAM algorithm is adopted to compute self positions. However, the computed positions cannot be directly used to compute the relative positions of peer devices in MuAR, because they are computed with respect to independent coordinate systems associated with participating devices. To fill in the gap, the industry has recently proposed to implement peer tracking with the help of built-in Ultra Wideband (UWB) chip. In this work, we aim to perform a reality check on the proposed support, with the Nearby Interaction (NI) framework developed for iOS mobile devices as an example. The goal of our study is to gain an in-depth understanding about the reliability of the proposed support and identify potential issues. Through extensive measurements, we discover the peer tracking solution is not reliable sometimes, in terms of availability and accuracy. Furthermore, with regard to erroneous position reports, we present a quantitative analysis, summarizing the error types (e.g., transient errors and permanent errors) and revealing their underlying reasons. We believe the preliminary findings could help to improve the spacial awareness and enhance user experiences in MuAR.

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of ϕ≈1.618 [11], [2], [6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of ϕ applies even to the special case of 2-bounded instances, and a ϕ-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a ϕ-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 12(13−1)≈1.303 and we prove a nearly tight lower bound of 14(1+17)≈1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer ℓ≥0 we prove a lower bound of 12(ℓ+1)(1+5+8ℓ+4ℓ2) for online algorithms with ℓ-lookahead, i.e., algorithms that at time t can see all packets arriving by time t+ℓ. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with ℓ-lookahead, for any ℓ≥0.

We introduce a cloud-enabled defense mechanism for Internet services against network and computational Distributed Denial-of-Service (DDoS) attacks. Our approach performs selective server replication and intelligent client re-assignment, turning victim servers into moving targets for attack isolation. We introduce a novel system architecture that leverages a "shuffling" mechanism to compute the optimal re-assignment strategy for clients on attacked servers, effectively separating benign clients from even sophisticated adversaries that persistently follow the moving targets. We introduce a family of algorithms to optimize the runtime client-to-server re-assignment plans and minimize the number of shuffles to achieve attack mitigation. The proposed shuffling-based moving target mechanism enables effective attack containment using fewer resources than attack dilution strategies using pure server expansion. Our simulations and proof-of-concept prototype using Amazon EC2 [1] demonstrate that we can successfully mitigate large-scale DDoS attacks in a small number of shuffles, each of which incurs a few seconds of user-perceived latency.

The Internet has witnessed rapidly increasing streaming traffic to various mobile devices. In this paper, we find that for the popular iOS based mobile devices, accessing popular Internet streaming services typically involves about 10% - 70% unnecessary redundant traffic. Such a practice not only overutilizes and wastes resources on the server side and the network (cellular or Internet), but also consumes additional battery power on users' mobile devices and leads to possible monetary cost. To alleviate such a situation without changing the server side or the iOS, we design and implement a CStreamer prototype that can transparently work between existing iOS devices and media servers. We also build a CStreamer iOS App to enable end users to access Internet streaming services via CStreamer. Experiments conducted based on this prototype running on Amazon EC2 show that CStreamer can completely eliminate the redundant traffic without degrading user's QoS.

Receiving Internet streaming services on various mobile devices is getting increasingly popular, and cloud platforms have also been gradually employed for delivering streaming services to mobile devices. While a number of studies have been conducted at the client side to understand and characterize Internet mobile streaming delivery, little is known about the server side, particularly for the recent cloud-based Internet mobile streaming delivery. In this work, we aim to investigate the Internet mobile streaming service at the server side. For this purpose, we have collected a 4-month server-side log on the cloud (with 1,002 TB delivered video traffic) from a top Internet mobile streaming service provider serving worldwide mobile users. Through trace analysis, we find that 1) a major challenge for providing Internet mobile streaming services is rooted from the mobile device hardware and software heterogeneity. In this workload, we find over 3,400 different hardware models with more than 100 different screen resolutions running 14 different mobile OS and three audio codecs and four video codecs. 2) To deal with the device heterogeneity, CPU-intensive transcoding is used on the cloud to customize the video to the appropriate versions at runtime for different devices. A video clip could be transcoded into more than 40 different versions to serve requests from different devices. 3) Compared to videos in traditional Internet streaming, mobile streaming videos are typically of much smaller size (a median of 1.68 MBytes) and shorter duration (a median of 2.7 minutes). Furthermore, the daily mobile user accesses are more skewed following a Zipf-like distribution but users' interests also quickly shift. Considering the huge demand of CPU cycles for online transcoding, we further examine server-side caching to reduce the total CPU cycle demand from the cloud. We show that a policy considering different versions of a video altogether outperforms other intuitive ones when the cache size is limited.

Receiving Internet streaming services on various mobile devices is getting more and more popular. To understand and better support Internet streaming delivery to mobile devices, a number of studies have been conducted. However, existing studies have mainly focused on the client side resource consumption and streaming quality. So far, little is known about the server side, which is the key for providing successful mobile streaming services. In this work, we set to investigate the Internet mobile streaming service at the server side. For this purpose, we have collected a one-month server log (with 212 TB delivered video traffic) from a top Internet mobile streaming service provider serving worldwide mobile users. Through trace analysis, we find that (1) a major challenge for providing Internet mobile streaming services is rooted from the mobile device hardware and software heterogeneity. In this workload, we find over 2800 different hardware models with about 100 different screen resolutions running 14 different mobile OS and 3 audio codecs and 4 video codecs. (2) To deal with the device heterogeneity, transcoding is used to customize the video to the appropriate versions at runtime for different devices. A video clip could be transcoded into more than 40 different versions in order to serve requests from different devices. (3) Compared to videos in traditional Internet streaming, mobile streaming videos are typically of much smaller size (a median of 1.68 MBytes) and shorter duration (a median of 2.7 minutes). Furthermore, the daily mobile user accesses are more skewed following a Zipf-like distribution but users' interests also quickly shift. Considering the huge demand of CPU cycles for online transcoding, we further examine server-side caching in order to reduce CPU cycle demand. We show that a policy considering different versions of a video altogether outperforms other intuitive ones when the cache size is limited.

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (ϕ := (1 + √ 5)/2 ≈ 1.618)-competitive deterministic online algorithm, a (4/3 ≈ 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2-speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.

With the increasing deployment of Internet P2P/overlay streaming systems, more and more clients use mobile devices, such as smart phones and PDAs, to access these Internet streaming services. Compared to wired desktops, mobile devices normally have a smaller screen size, a less color depth, and lower bandwidth and thus cannot correctly and effectively render and display the data streamed to desktops. To address this problem, in this paper, we propose PAT (Peer-Assisted Transcoding) to enable effective online transcoding in P2P/overlay streaming. PAT has the following unique features. First, it leverages active peer cooperation without demanding infrastructure support such as transcoding servers. Second, as online transcoding is computationally intensive while the various devices used by participating clients may have limited computing power and related resources (e.g., battery, bandwidth), an additional overlay, called metadata overlay, is constructed to instantly share the intermediate transcoding result of a transcoding procedure with other transcoding nodes to minimize the total computing overhead in the system. The experimental results collected within a realistically simulated testbed show that by consuming 6% extra bandwidth, PAT could save up to 58% CPU cycles for online transcoding.

In this paper, we investigate energy-aware real-time scheduling algorithms with speed change constraints. A processor is equipped with variable clock frequency (speedy) feature and is used to schedule a set of given jobs with deadlines. Each speed change involves time/energy overhead and recent studies show that it also impacts negatively the processor's lifetime reliability. Motivated by this, we study theoretical energy-aware scheduling problems with consideration of number and cost of speed changes. We associate a cost with each speed change to reflect its negative impact on the processor's lifetime reliability. We design speed schedules to satisfy all jobs' deadlines and optimize the energy consumption and the total cost incurred due to speed changes. Four related problems based on this framework are considered. We develop algorithms that perform arbitrarily close to the optimal and we also analyze their time complexities.

In embedded systems and data-center systems (systems, for short), it is widely accepted that energy consumption has become the bottleneck of system's performance improvement and it is one of the most significant factors to optimize. Unfortunately, an effective energy-aware strategy usually has an adverse impact on a job's flow time or stretch - two important user-perspective system performance metrics. In some cases, the more energy is saved by an energy-aware policy, the more flow time and the larger stretch occur to jobs. In this paper, we investigate the impact on job processing delay introduced by power-down energy-saving mechanisms. Specifically, we study bicriteria algorithms that minimize maximum flow time or largest stretch under a fixed energy budget and minimize total energy consumption under an upper bound of flow time or stretch. We develop optimal offline algorithms to quantitatively balance the system-perspective performance metric (energy consumption) and the user-perspective performance metric (flow time and stretch). We also develop two simple min-energy online algorithms against weakened adversaries. We prove that (1.) with appropriate extra flow time, an online algorithm can beat any non-idling algorithm, in terms of energy consumption; (2.) a deterministic online algorithm which has a bounded times of optimal stretch, is optimal in terms of competitive ratio with respect to energy consumption.

Internet streaming applications are becoming increasingly popular on mobile devices. However, receiving streaming services on mobile devices is often constrained by their limited battery power supply. Various techniques have been proposed to save battery power consumption on mobile devices, mainly focusing on how much data to transmit and how to transmit.

P2P streaming applications are very popular on the Internet today. However, a mobile device in P2P streaming not only needs to continuously receive streaming data from other peers for its playback, but also needs to continuously exchange control information (e.g., buffermaps and file chunk requests) with neighboring peers and upload the downloaded streaming data to them. These lead to excessive battery power consumption on the mobile device.

The pervasive usage of mobile devices and wireless networking support have enabled more and more Internet stream- ing services to all kinds of heterogeneous mobile devices. However, Internet mobile streaming services are challenged by the inherently limited on-device resources, device heterogeneity, and the bulk amount of streaming data.

Motivated by providing quality-of-service for next generation IP-based networks, we design algorithms to schedule packets with values and deadlines. Packets arrive over time; each packet has a non-negative value and an integer deadline. In each time step, at most one packet can be sent. Packets can be dropped at any time before they are sent. The objective is to maximize the total value gained by delivering packets no later than their respective deadlines. This model is the well-studied bounded-delay model (Hajek. CISS 2001. Kesselman et al. SICOMP 2004) which extensive competitive online algorithms have been developed for. In a generalization of this model, the success of delivering a packets in each time step depends on the reliability of the communication channel. In this paper, we apply online learning approaches on this model as well as a few of its variants. We design online learning algorithms and analyze their performance theoretically in terms of external regret. We also measure these algorithms' performance experimentally. We conclude that no online learning algorithms have a constant regret. Our online learning algorithms outperform the competitive algorithms for algorithmic simplicity and running complexity. However, in general, this online learning algorithms work no worse than the best known competitive online algorithm for maximizing weighted throughput in practice.

In P2P assisted multi-channel live streaming systems, it is commonly believed that in unpopular channels, quality degradation is due to the small number of participating peers with almost-the-same set of available data; this phenomena prevents effective data exchanges among peers themselves and automatically leads to data request contentions once a new data chunk becomes available. In popular programs, our measurement on PPLive for a continuous three-month period at various locations also shows numerous occurrences of quality degradation because of the even higher ratio (up to 190%) of repetitive data requests for the same data chunks.

In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings, we prove that no online algorithm can achieve a competitive factor greater than 1 - emax/E, where emaxis the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm EC-EDF* which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these settings. We also extend our analysis to other settings, including those with non-uniform value densities and dynamic voltage scaling capability.

With the ever-increasing P2P Internet traffic, recently much attention has been paid to the topology mismatch between the P2P overlay and the underlying network due to the large amount of cross-ISP traffic. Mainly focusing on BitTorrent-like file sharing systems, several recent studies have demonstrated how to efficiently bridge the overlay and the underlying network by leveraging the existing infrastructure, such as CDN services or developing new application-ISP interfaces, such as P4P. However, so far the traffic locality in existing P2P live streaming systems has not been well studied. In this work, taking PPLive as an example, we examine traffic locality in Internet P2P streaming systems. Our measurement results on both popular and unpopular channels from various locations show that current PPLive traffic is highly localized at the ISP level. In particular, we find: (1) a PPLive peer mainly obtains peer lists referred by its connected neighbors (rather than tracker servers) and up to 90% of listed peers are from the same ISP as the requesting peer; (2) the major portion of the streaming traffic received by a requesting peer (up to 88% in popular channels) is served by peers in the same ISP as the requestor; (3) the top 10\% of the connected peers provide most (about 70%) of the requested streaming data and these top peers have smaller RTT to the requesting peer. Our study reveals that without using any topology information or demanding any infrastructure support, PPLive achieves such high ISP level traffic locality spontaneously with its decentralized, latency based, neighbor referral peer selection strategy. These findings provide some new insights for better understanding and optimizing the network- and user-level performance in practical P2P live streaming systems.

Though plenty of research has been conducted to improve Internet P2P streaming quality perceived by end-users, little has been known about the upper bounds of achievable performance with available resources so that different designs could compare against. On the other hand, the current practice has shown increasing demand of server capacities in P2P-assisted streaming systems in order to maintain high-quality streaming to end-users. Both research and practice call for a design that can optimally utilize available peer resources. In the paper, we first present a new design, aiming to reveal the best achievable throughput for heterogeneous P2P streaming systems. We measure the performance gaps between various designs and this optimal resource allocation. Through extensive simulations, we find out that several typical existing designs have not fully exploited the potential of system resources. However, the control overhead prohibits the adoption of this optimal approach. Then, we design a hybrid system in trading off the cost of assignment and utilization of resources. This hybrid approach has a proved theoretical bound on efficiency of utilization. Simulation results show that compared with the optimal resource allocation, our proposed hybrid design can achieve near-optimal (up to 90%) utilization while only use much less (below 4%) control overhead. Our results provide a basis for both server capacity planning in current P2P-assisted streaming practice and future protocol designs.

Motivated by the quality-of-service (QoS) buffer management problem, we consider online scheduling of packets with hard deadlines in a finite capacity queue. At any time, a queue can store at mostbisin Z+packets. Packets arrive over time. Each packet is associated with a non-negative value and an integer deadline. In each time step, only one packet is allowed to be sent. Our objective is to maximize the total value gained by the packets sent by their deadlines in an online manner. Due to the Internet traffic's chaotic characteristics, no stochastic assumptions are made on the packet input sequences. This model is called a finite-queue model. We use competitive analysis to measure an online algorithm's performance versus an unrealizable optimal offline algorithm who constructs the worst possible input based on the knowledge of the online algorithm. For the finite-queue model, we first present a deterministic 3-competitive memoryless online algorithm. Then, we give a randomized (Phi2= (1+radic(5)/2)2ap 2.618)-competitive memoryless online algorithm. The algorithmic framework and its theoretical analysis include several interesting features. First, our algorithms use (possibly) modified characteristics of packets; these characteristics may not be same as those specified in the input sequence. Second, our analysis method is different from the classical potential function approach. We use a simple charging scheme, which depends on a clever modification (during the course of the algorithm) on the packets in the queue of the optimal offline algorithm. We then prove that a set of invariants holds at the end of each time step. Finally, we analyze the two proposed algorithm in a relaxed model, in which packets have no hard deadlines but an order. We conclude that both algorithms have the same competitive ratios in the relaxed model.

We consider online scheduling weighted packets with time constraints over a fading channel. Packets arrive at the transmitter in an online manner. Each packet has a value and a deadline by which it should be sent. The fade state of the channel determines the throughput obtained per unit of time and the channel's quality may change over time. In this paper, we design online algorithms to maximize weighted throughput, defined as the total value of the packets sent by their respective deadlines. Competitive ratio is employed to measure an online algorithm's performance. For this problem and one of its variants, we present two online algorithms with competitive ratios 2:618 and 2 respectively.

Motivated by providing differentiated services on the Internet, we consider efficient algorithms for buffer management in quality-of-service (QoS) routers. We study a FIFO buffering model with fairness constraint, in which packets have values to represent their priorities. The order of packets being sent complies with the order of their arriving time. Fairness is enforced such that the dropping rate of a higher- priority traffic class should not be much higher than that of a lower-priority traffic class by a factor of their values' ratio. Our objective is to maximize the total value of the packets sent. In this paper, we design both offline and online fair FIFO buffering algorithms. We first give a polynomial- time optimal offline algorithm. Then we discuss the fairness of a family of online algorithms and prove that all previously developed FIFO buffering algorithms do not guarantee fairness. For online algorithms, we use competitiveness to measure their performance against the worst-case scenarios. At last, we provide a fair online algorithm with a constant competitive ratio for the two traffic classes model. Our online algorithm is the first attempt to address the fairness concern in a competitive FIFO queue. It safeguards QoS guarantees and makes no stochastic assumptions on the input packet sequences.