Routing configurations of a network should constantly adapt to traffic variations to achieve good network performance. Adaptive routing faces two main challenges: 1) how to accurately measure/estimate time-varying traffic matrices? 2) how to control the network and application performance degradation caused by frequent route changes? In this paper, we develop a novel data-enabled predictive traffic engineering (DeeP-TE) algorithm that minimizes the network congestion by gracefully adapting routing configurations over time. Our control algorithm can generate routing updates directly from the historical routing data and the corresponding link rate data, without direct traffic matrix measurement or estimation. Numerical experiments on real network topologies with real traffic matrices demonstrate that the proposed DeeP-TE routing adaptation algorithm can achieve close-to-optimal control effectiveness with significantly lower routing variations than the baseline methods.

Federated Learning (FL) trains a shared model using data and computation power on distributed agents coordinated by a central server. Decentralized FL (DFL) utilizes local model exchange and aggregation between agents to reduce the communication and computation overheads on the central server. However, when agents are mobile, the communication opportunity between agents can be sporadic, largely hindering the convergence and accuracy of DFL. In this paper, we propose Cached Decentralized Federated Learning (Cached-DFL) to investigate delay-tolerant model spreading and aggregation enabled by model caching on mobile agents. Each agent stores not only its own model, but also models of agents encountered in the recent past. When two agents meet, they exchange their own models as well as the cached models. Local model aggregation utilizes all models stored in the cache. We theoretically analyze the convergence of Cached-DFL, explicitly taking into account the model staleness introduced by caching. We design and compare different model caching algorithms for different DFL and mobility scenarios. We conduct detailed case studies in a vehicular network to systematically investigate the interplay between agent mobility, cache staleness, and model convergence. In our experiments, Cached-DFL converges quickly, and significantly outperforms DFL without caching.

Field-of-View (FoV) adaptive streaming significantly reduces bandwidth requirement of immersive point cloud video (PCV) by only transmitting visible points inside a viewer's FoV. The traditional approaches often focus on trajectory-based 6 degree-of-freedom (6DoF) FoV predictions. The predicted FoV is then used to calculate point visibility. Such approaches do not explicitly consider video content's impact on viewer attention, and the conversion from FoV to point visibility is often error-prone and time-consuming. We reformulate the PCV FoV prediction problem from the cell visibility perspective, allowing for precise decision-making regarding the transmission of 3D data at the cell level based on the predicted visibility distribution. We develop a novel spatial visibility and object-aware graph model (CellSight) that leverages the historical 3D visibility data and incorporates spatial perception, occlusion between points, and neighboring cell correlation to predict the cell visibility in the future. We focus on multi-second ahead prediction to enable the use of long pre-fetching buffers in on-demand streaming, critical for enhancing the robustness to network bandwidth fluctuations. CellSight significantly improves the long-term cell visibility prediction, reducing the prediction Mean Squared Error (MSE) loss by up to 50% compared to the state-of-the-art models when predicting 2 to 5 seconds ahead, while maintaining real-time performance (more than 30fps) for point cloud videos with over 1 million points.

Low Earth Orbit (LEO) satellite networks are emerging as crucial components of space-air-ground integrated networks (SAGINs), extending beyond terrestrial capabilities to provide global data transmission services for the Internet of Things (IoT) and mobile devices. The proliferation of connected devices has led to increased data volumes and highly variable, bursty traffic patterns, thus posing significant challenges for network stability and necessitating effective routing control mechanisms. Traditional Lyapunov optimization methods have been fundamental in network optimization, offering stability guarantees under the assumption that traffic flows remain strictly within the network's capacity region. However, this assumption is often violated in LEO satellite networks due to their dynamic and bursty nature, thereby rendering conventional approaches inadequate for ensuring stability. To address this challenge, we propose a robust Lyapunov optimization framework tailored for LEO satellite networks. Our method relaxes the strict requirements of traditional Lyapunov optimization by allowing the network to tolerate finite violations of the capacity region while still ensuring overall system stability. This approach demonstrates that, for a stabilizable network system, it is not necessary for traffic to remain within the capacity region at every time slot. We validate the effectiveness of the proposed robust Lyapunov optimization through extensive simulations under various traffic conditions and LEO satellite network configurations. The results confirm that LEO satellite networks can maintain stability despite finite violations of the capacity region, ensuring reliable performance amid dynamic and bursty traffic demands.

Many XR applications require the delivery of volumetric video to users. Point Cloud has become a popular volumetric video format. A dense point cloud consumes much higher bandwidth than a 2D/360$^{\circ }$video frame. User Field of View (FoV) is more dynamic with 6-DoF movement than 3-DoF movement. To save bandwidth, FoV-adaptive streaming predicts a user's FoV and only downloads point cloud data falling in the predicted FoV. However, it is vulnerable to FoV prediction errors, which can be significant when a long buffer is utilized for smoothed streaming. In this work, we propose a multi-round progressive refinement framework for point cloud video streaming. Instead of sequentially downloading point cloud frames, our solution simultaneously downloads/patches multiple frames falling into a sliding time-window, leveraging the inherent scalability of octree-based point-cloud coding. The optimal rate allocation among all tiles of active frames are solved numerically using the heterogeneous tile rate-quality functions calibrated by the predicted user FoV. Multi-frame downloading/patching simultaneously takes advantage of the streaming smoothness resulting from long buffer and the FoV prediction accuracy at short buffer length. We evaluate our streaming solution using simulations driven by real point cloud videos, real bandwidth traces, and 6-DoF FoV traces of real users. Our solution is robust against the bandwidth/FoV prediction errors, and can deliver high and smooth view quality in the face of bandwidth variations and dynamic user and point cloud movements.

Modern communication networks are increasingly equipped with in-network computational capabilities and services. Routing in such networks is significantly more complicated than the traditional routing. A legitimate route for a flow not only needs to have enough communication and computation resources, but also has to conform to various application-specific routing constraints. This paper presents a comprehensive study on routing optimization problems in networks with embedded computational services. We develop a set of routing optimization models and derive low-complexity heuristic routing algorithms for diverse computation scenarios. For dynamic demands, we also develop an online routing algorithm with performance guarantees. Through evaluations over emerging applications on real topologies, we demonstrate that our models can be flexibly customized to meet the diverse routing requirements of different computation applications. Our proposed heuristic algorithms significantly outperform baseline algorithms and can achieve close-to-optimal performance in various scenarios.

The 31st IEEE International Conference on Network Protocols (ICNP 2023) will be held in Reykjavik, Iceland, between October 10 and 13, 2023. On behalf of the Organizing Committee and Program Committee of ICNP 2023, we are pleased to welcome you to an exciting Technical Program, which consists of papers on a wide range of networking research topics, including congestion control, smart NIC, LoRA, measurement, in-network computing, algorithms & analysis, learning & networking, security & blockchain, wireless, and multimedia networking.

The emerging edge networks are cloud-native. Flows with computation needs are processed in-flight by compute nodes inside the network. Routing with In-Network Processing (RINP) not only has to maintain network-wide load balance on communication and computation elements, but also has to quickly restore flows upon various types of failures. In this paper, we propose a novel path-based two-stage traffic engineering scheme to trade-off between routing model complexity, network performance in the normal stage, and restoration efficiency upon failures. For the normal stage, our model jointly optimizes computation demand allocation and traffic flow routing. We further speed-up RINP calculation by controlling the path budget and decoupling computation allocation and traffic routing. For the restoration stage, we develop a fast restoration scheme that only re-routes the flows traversing the failed elements to achieve close-to-optimal network delay performance while minimizing the fraction of unrestored flows. Evaluation results on real network instances demonstrate that in the normal stage, our scheme achieves near-optimal performance with up to 50--100x speedup compared to link-based routing models. In the restoration stage, our scheme can restore most of the affected traffic with up to 10x speedup compared to globally rerouting all the flows.

Streaming of live 360-degree video allows users to follow a live event from any view point and has already been deployed on some commercial platforms. However, the current systems can only stream the video at relatively low-quality because the entire 360-degree video is delivered to the users under limited bandwidth. Streaming video falling into user field of view (FoV) can improve bandwidth efficiency of 360-degree video delivery. In this paper, we propose to use the idea of “flocking” to simultaneously improve the accuracy of user FoV prediction and video delivery efficiency for live 360-degree video streaming. By assigning variable playback latencies to users in a streaming session based on their network conditions, a “streaming flock” is formed and led by “strong” users with low playback latencies in the front of the flock. We propose a long short-term memory (LSTM) based collaborative FoV prediction scheme where the FoV traces of users in the front of the flock are utilized to predict the FoV of users behind them. Given a predicted FoV, we develop an optimal rate allocation strategy to maximize the perceptual quality. By conducting experiments using real-world user FoV traces and LTE/5 G network bandwidth traces, we evaluate the gains of the proposed strategies over several benchmarks. Our experimental results demonstrate that the proposed streaming system can increase the overall quality dramatically by about 10 dB compared with heuristic FoV prediction strategy. In addition, the network-aware flocking formation can further reduce the video freeze without influencing video quality.

Edge caching will play a critical role in facilitating the emerging content-rich applications. However, it faces many new challenges, in particular, the highly dynamic content popularity and the heterogeneous caching configurations. In this paper, we propose Cocktail Edge Caching, that tackles the dynamic popularity and heterogeneity through ensemble learning. Instead of trying to find a single dominating caching policy for all the caching scenarios, we employ an ensemble of constituent caching policies and adaptively select the best-performing policy to control the cache. Towards this goal, we first show through formal analysis and experiments that different variations of the LFU and LRU policies have complementary performance in different caching scenarios. We further develop a novel caching algorithm that enhances LFU/LRU with deep recurrent neural network (LSTM) based time-series analysis. Finally, we develop a deep reinforcement learning agent that adaptively combines base caching policies according to their virtual hit ratios on parallel virtual caches. Through extensive experiments driven by real content requests from two large video streaming platforms, we demonstrate that CEC not only consistently outperforms all single policies, but also improves the robustness of them. CEC can be well generalized to different caching scenarios with low computation overheads for deployment.

Robot locomotion is a major challenge in robotics. Model-based approaches are vulnerable to model errors, and incur high computation overhead resulted from long control horizon. Model-free approaches are trained with a large number of training samples, which are expensive to obtain. In this paper, we develop a hybrid control and learning framework, called Reinforced iLQR (RiLQR), which combines the advantages of model-based iLQR control with model-free RL policy learning to simultaneously achieve high sample efficiency, low computation overhead, and high robustness against model errors in robot locomotion. Through extensive evaluation on the Mujoco platform, we demonstrate that RiLQR outperforms the state-of-the-art model-based and model-free baselines by big margins in a set of tasks with different complexities.

Edge caching will play a critical role in facilitating the emerging content-rich applications. However, it faces many new challenges, in particular, the highly dynamic content popularity and the heterogeneous caching configurations. In this paper, we propose Cocktail Edge Caching, that tackles the dynamic popularity and heterogeneity through ensemble learning. Instead of trying to find a single dominating caching policy for all the caching scenarios, we employ an ensemble of constituent caching policies and adaptively select the best-performing policy to control the cache. Towards this goal, we first show through formal analysis and experiments that different variations of the LFU and LRU polices have complementary performance in different caching scenarios. We further develop a novel caching algorithm that enhances LFU/LRU with deep recurrent neural network (LSTM) based time-series analysis. Finally, we develop a deep reinforcement learning agent that adaptively combines base caching policies according to their virtual hit ratios on parallel virtual caches. Through extensive experiments driven by real content requests from two large video streaming platforms, we demonstrate that CEC not only consistently outperforms all single policies, but also improves the robustness of them. CEC can be well generalized to different caching scenarios with low computation overheads for deployment.

It is highly challenging to simultaneously achieve high-rate and low-latency in live video streaming. Chunk-based streaming and playback speed adaptation are two promising new trends to achieve high user Quality-of-Experience (QoE). To thoroughly understand their potentials, we develop a detailed chunk-level dynamic model that characterizes how video rate and playback speed jointly control the evolution of a live streaming session. Leveraging on the model, we first study the optimal joint video rate-playback speed adaptation as a non-linear optimal control problem. We further develop model-free joint adaptation strategies using deep reinforcement learning. Through extensive experiments, we demonstrate that our proposed joint adaptation algorithms significantly outperform rate-only adaptation algorithms and the recently proposed low-latency video streaming algorithms that separately adapt video rate and playback speed without joint optimization. In a wide-range of network conditions, the model-based and model-free algorithms can achieve close-to-optimal trade-offs tailored for users with different QoE preferences.

User activities in cyberspace leave unique traces for user identification (UI). Individual users can be identified by their frequent activity items through statistical feature matching. However, such approaches face the data sparsity problem. In this paper, we propose to address this problem by multi-item-set fingerprinting that identifies users not only based on their frequent individual activity items, but also their frequent consecutive item sequences with different lengths. We also propose a new similarity metric between fingerprint vectors that combines the advantages of Jaccard distance and relative entropy distance. Furthermore, we develop a fusion decision scheme by consolidating matching candidates generated by different similarity metrics. It improves the precision at the price of extra rejection. Our proposed approaches can be used in both one-by-one matching and bipartite graph group matching. Through extensive experiments on three real user datasets, in particular a large-scale Internet Protocol Television (IPTV) viewer dataset, we demonstrate that the proposed approaches outperform the state-of-the-art methods. The average matching precision reaches 93.8% for a dataset of 1,000 users and 100% for a dataset of 100 users. This work is of significance for information forensics and raises a new challenge for human privacy protection in cyberspace.

Internet Protocol TV (IPTV) normally has the advantage of providing far more TV channels than the traditional TV services, while as the other side of the coin it has the problem of information overload. Users of IPTV usually have difficulties finding channels matching their interests. In this paper, using a large IPTV dataset, we analyze channel zapping behaviors of IPTV users and discover various patterns that can be used to generate more accurate channel zapping recommendations. Based on user behavior analysis, we develop several base and fusion recommender systems that generate in real-time a short list of channels for users to consider whenever they want to switch channels. A deep neural network model that consists of a “Recommender System Attention (RS Attention)” module and a “Channel Attention” module capturing the static and dynamic user switching behaviors is also developed to further improve the recommendation accuracy. Evaluation on the IPTV dataset demonstrates that our fusion recommender can achieve 41% hit ratio with only three candidate channels, and our attention neural network model further pushes it up to 45%. Our recommender systems only take as input user channel zapping sequences, and can be easily adopted by IPTV systems with low data and computation overheads.

Low-latency is a critical user Quality-of-Experience (QoE) metric for live video streaming. It poses significant challenges for streaming over the Internet. In this paper, we explore the design space of low-latency live streaming by developing dynamic models and optimal adaptation strategies to establish QoE upper bounds as a function of the allowable end-to-end latency. We further develop practical live streaming algorithms within the iterative Linear Quadratic Regulator (iLQR) based Model Predictive Control and Deep Reinforcement Learning frameworks, namely MPC-Live and DRL-Live, to maximize user live streaming QoE by adapting the video bitrate while maintaining low end-to-end video latency in dynamic network environment. Through extensive experiments driven by real network traces, we demonstrate that our live streaming algorithms can achieve close-to-optimal performance within the latency range of two to five seconds.

Virtual Reality (VR) and Augmented Reality (AR) technologies have become popular in recent years. Encoding and transmitting the omni-directional or $360^\circ $ video is critical and challenging for those applications. The $360^\circ $ video requires much higher bandwidth than the traditional planar video. A premium quality $360^\circ $ video with 120 frames per second (fps) and 24K resolution can easily consume bandwidth in the range of Gigabits-per-second~\cite1. On the other hand, at any given time, a user only watches a small portion of the $360^\circ$ scope within her Field-of-View (FoV). An effective way to reduce the bandwidth requirement of $360^\circ $ video is through FoV-adaptive streaming, which codes and delivers the predicted FoV region at higher quality, and discards or codes at lower quality the remaining regions. Such strategy has been quite extensively studied for video-on-demand \citefov_adapt_2,fov_adapt_3,1,tile_based_3,qian2016optimizing and live video streaming applications\citelive_1,live_2,live_3, sun2020flocking. Interactive applications, such as conferencing, gaming, and remote collaboration, can also benefit from $360^\circ $ video by creating an immersive environment for participants to interact with each other citeinteractive_gamming \citevr_conferencing \citelee2015outatime. However, realtime coding and streaming of $360^\circ $ video with extremely low latency, required for interactive applications, has not been sufficiently addressed. This work focuses on developing low-latency and FoV-adaptive coding and streaming strategies for interactive $360^\circ$ video streaming. We assume the sender and the receiver are connected by a network path with dynamically varying throughput without short-latency guarantee. The sender is either the video source, or a proxy server relaying the source video. The receiver is either the end user device that directly renders the video, or a local edge server that renders the video and transmit to the end user \citeHou2017.

Streaming of live 360-degree video allows users to follow a live event from any view point and has already been deployed on some commercial platforms. However, the current systems can only stream the video at relatively low-quality because the entire 360-degree video is delivered to the users under limited bandwidth. In this paper, we propose to use the idea of "flocking" to improve the performance of both prediction of field of view (FoV) and caching on the edge servers for live 360-degree video streaming. By assigning variable playback latencies to all the users in a streaming session, a "streaming flock" is formed and led by low latency users in the front of the flock. We propose a collaborative FoV prediction scheme where the actual FoV information of users in the front of the flock are utilized to predict of users behind them. We further propose a network condition aware flocking strategy to reduce the video freeze and increase the chance for collaborative FoV prediction on all users. Flocking also facilitates caching as video tiles downloaded by the front users can be cached by an edge server to serve the users at the back of the flock, thereby reducing the traffic in the core network. We propose a latency-FoV based caching strategy and investigate the potential gain of applying transcoding on the edge server. We conduct experiments using real-world user FoV traces and WiGig network bandwidth traces to evaluate the gains of the proposed strategies over benchmarks. Our experimental results demonstrate that the proposed streaming system can roughly double the effective video rate, which is the video rate inside a user's actual FoV, compared to the prediction only based on the user's own past FoV trajectory, while reducing video freeze. Furthermore, edge caching can reduce the traffic in the core network by about 80%, which can be increased to 90% with transcoding on edge server.

Low-latency is a critical user Quality-of-Experience (QoE) metric for live video streaming. It poses significant challenges for streaming over the Internet. In this paper, we explore the design space of low-latency live video streaming by developing dynamic models and optimal control strategies. We further develop practical live video streaming algorithms within the Model Predictive Control (MPC) framework, namely MPC-Live, to maximize user QoE by adapting the video bitrate while maintaining low end-to-end video latency in dynamic network environment. Through extensive experiments driven by real network traces, we demonstrate that our live video streaming algorithms can improve the performance dramatically within latency range of two to five seconds.

With the new emerging throughput-intensive ultralow latency applications, there is a need for a transport layer protocol that can achieve high throughput with low latency. One promising candidate is TCP BBR, a protocol developed by Google, with the aim of achieving high throughput and low latency by operating around the Bandwidth Delay Product (BDP) of the bottleneck link. Google reported significant throughput gains and much lower latency relative to TCP Cubic following the deployment of BBR in their high-speed wide area wired network. As most of these emerging applications will be supported by Millimeter Wave (mmWave) wireless networks, BBR should achieve both high throughput and ultra-low latency in these settings. However, in our preliminary experiments with BBR over a mmWave wireless link operating at 60 GHz, we observed a severe degradation in throughput that we were able to attribute to high delay variation on the link. In this paper, we show that “throughput collapse” occurs when BBR's estimate of minimum RTT is less than half of the average RTT of the uncongested link (as when delay jitter is large). We demonstrate this phenomenon and explain the underlying reasons for it using a series of controlled experiments on the CloudLab testbed. We also present a mathematical analysis of BBR, which matches our experimental results closely. Based on our analysis, we propose and experimentally evaluate potential solutions that can overcome the throughput collapse without addina sianificant latency.

360° video streaming is a key component of the emerging Virtual Reality (VR) and Augmented Reality (AR) applications. In 360° video streaming, a user may freely navigate through the captured 360° video scene by changing her desired Field-of-View. High-throughput and low-delay data transfers enabled by 5G wireless networks can potentially facilitate untethered 360° video streaming experience. Meanwhile, the high volatility of 5G wireless links present unprecedented challenges for smooth 360° video streaming. In this paper, novel multi-path multi-tier 360° video streaming solutions are developed to simultaneously address the dynamics in both network bandwidth and user viewing direction. We systematically investigate various design trade-offs on streaming quality and robustness. Through simulations driven by real 5G network bandwidth traces and user viewing direction traces, we demonstrate that the proposed 360° video streaming solutions can achieve a high-level of Quality-of-Experience (QoE) in the challenging 5G wireless network environment.

The bandwidth required for TV content distribution is rapidly increasing due to the evolution of high definition TV (HDTV) and ultra HDTV. Service providers are constantly trying to differentiate themselves by innovating new ways of distributing content more efficiently with lower cost and higher penetration. We propose a cost-efficient wireless architecture [wireless live TV (WiLiTV)], consisting of a mix of wireless access technologies [satellite, Wi-Fi, and LTE/5G millimeter wave (mmWave) overlay links], for delivering live TV services. In the proposed architecture, live TV content is injected into the network at selected locations, consisting of some homes and/or cellular base stations, using satellite antennas. The content is then further distributed to other homes using a house-to-house Wi-Fi network or an LTE/5G mmWave overlay. We construct an optimal content distribution network with the minimum number of satellite injection points, while preserving the highest quality of experience, for different neighborhood densities. We evaluate the framework using time-varying demand patterns and a diverse set of home location data provided from an operational content distribution network. Our study demonstrates that this architecture reduces the overall cost by 60% compared with the traditional architecture. We have also shown that the WiLiTV is robust in its support for several TV formats.

We consider video calls affected by bursty packet losses, where frame-level forward error correction (FEC) is employed due to delay constraints, and damaged frames and others predicted from them are discarded. Here, a high frame rate (FR) at low bitrates leads to large quantization step sizes (QS), small frames, and suboptimal FEC, whereas a low FR at high bitrates reduces the perceptual quality. To mitigate frame losses and freezing, hierarchical-P (hierP) temporal layering can be used with lower coding efficiency than IPPP coding. We study the received quality maximization for hierP and IPPP, by jointly optimizing the encoding FR, QS, and the FEC redundancy, under sending bitrate constraints. Building upon Q-STAR perceptual quality and R-STAR bitrate models, which depend on QS, and the decoded and encoding FR, respectively, we cast the problem as a combinatorial optimization problem. We solve for the encoding FR and the bitrate using exhaustive search, hill-climbing, and a greedy FEC distribution algorithm to determine the FEC redundancies. We show that, for random losses, the FEC bitrate ratio is an affine function of the packet-loss rate; low encoding FR is preferred at wider sending bitrate ranges with higher packet loss; layer protection is more even at higher bitrates; and IPPP, while achieving higher Q-STAR scores, is prone to freezing. For bursty losses, we show that layer redundancies are higher, rising with the mean burst length, reaching 80%; and hierP achieves higher Q-STAR scores than IPPP for longer bursts, and a smaller mean and variance of decoded frame distances.

Users’ preferences, and consequently their ratings and reviews to items, change over time. Likewise, characteristics of items are also time-varying. By dividing data into time periods, temporal Recommender Systems (RSs) improve recommendation accuracy by exploring the temporal dynamics in user rating data. However, temporal RSs have to cope with rating sparsity in each time period. Meanwhile, reviews generated by users contain rich information about their preferences, which can be exploited to address rating sparsity and further improve the performance of temporal RSs. In this article, we develop a temporal rating model with topics that jointly mines the temporal dynamics of both user-item ratings and reviews. Studying temporal drifts in reviews helps us understand item rating evolutions and user interest changes over time. Our model also automatically splits the review text in each time period into interim words and intrinsic words. By linking interim words and intrinsic words to short-term and long-term item features, respectively, we jointly mine the temporal changes in user and item latent features together with the associated review text in a single learning stage. Through experiments on 28 real-world datasets collected from Amazon , we show that the rating prediction accuracy of our model significantly outperforms the existing state-of-art RS models. And our model can automatically identify representative interim words in each time period as well as intrinsic words across all time periods. This can be very useful in understanding the time evolution of users’ preferences and items’ characteristics.

360 degree video compression and delivery is one of the key components of virtual reality (VR) applications. In such applications, the users may freely control and navigate the captured 3D environment from any viewing direction. Given that only a small portion of the entire video is watched at any time, fetching the entire 360 degree raw video is therefore unnecessary and bandwidth-consuming. In this work, a novel two-tier 360 degree video streaming scheme is proposed to accommodate the dynamics in both network bandwidth and viewing direction. Based on the real-trace driven simulations, we demonstrate that the proposed framework can significantly outperform conventional 360 video streaming schemes.

Emerging commercial live content broadcasting platforms are facing great challenges to accommodate large scale dynamic viewer populations. Existing solutions constantly suffer from balancing the cost of deploying at the edge close to the viewers and the quality of content delivery. We propose LiveJack, a novel network service to allow CDN servers to seamlessly leverage ISP edge cloud resources. LiveJack can elastically scale the serving capacity of CDN servers by integrating Virtual Media Functions (VMF) in the edge cloud to accommodate flash crowds for very popular contents. LiveJack introduces minor application layer changes for streaming service providers and is completely transparent to end users. We have prototyped LiveJack in both LAN and WAN environments. Evaluations demonstrate that LiveJack can increase CDN server capacity by more than six times, and can effectively accommodate highly dynamic workloads with an improved service quality.

Compared with the traditional television services, Internet Protocol TV (IPTV) can provide far more TV channels to end users. However, it may also make users feel confused even painful to find channels of their interests from a large number of them. In this paper, using a large IPTV trace, we analyze user channel-switching behaviors to understand when, why and how they switch channels. Based on user behavior analysis, we develop several base and fusion recommender systems that generate in real-time a short list of channels for users to consider whenever they want to switch channels. Evaluation on the IPTV trace demonstrates that our recommender systems can achieve up to 45 percent hit ratio with only three candidate channels. Our recommender systems only need access to user channel watching sequences, and can be easily adopted by IPTV systems with low data and computation overheads.

Social voting is an emerging new feature in online social networks. It poses unique challenges and opportunities for recommendation. In this paper, we develop a set of matrix-factorization (MF) and nearest-neighbor (NN)-based recommender systems (RSs) that explore user social network and group affiliation information for social voting recommendation. Through experiments with real social voting traces, we demonstrate that social network and group affiliation information can significantly improve the accuracy of popularity-based voting recommendation, and social network information dominates group affiliation information in NN-based approaches. We also observe that social and group information is much more valuable to cold users than to heavy users. In our experiments, simple metapath-based NN models outperform computation-intensive MF models in hot-voting recommendation, while users' interests for nonhot votings can be better mined by MF models. We further propose a hybrid RS, bagging different single approaches to achieve the best top-k hit rate.

With the prevailing of mobile phones and online video contents, the demand for mobile online video is increasing. The desire, however, is held down by the high mobile traffic cost. To solve this problem, an off-the-shelf solution is WiFi-Direct (WFD), which is widely available on a majority of mobile devices. There is, however, no systematic study of WFD-based group data transfer and cooperative video streaming on real phones. Thus, we designed and implemented a WFD-based LTE cooperative video streaming system, in which the WFD GO (Group Owner) device takes the responsibility of peer information exchange, data relay, and LTE cooperative downloading scheduling. Based on the system, we evaluated the performance of WFD-based group data sharing, including Ping response delay, throughput, and power efficiency. Valuable findings were obtained. For instance, we discovered that when a WFD device connects to a traditional AP (Access Point), even if there is \emph{no} data transmission to/from the AP, the Device-to-Device (D2D) throughput would decrease by at least 72\%. Based on these findings, we provided recommendations for the design and deployment of WFD based D2D systems. We finally demonstrated the feasibility of WFD based LTE cooperative video streaming using our system. We showed that, using multiple realistic LTE networks, a 3-device cooperative system can provide smooth video streaming with bitrate more than 10Mbps.

Software Defined Networking (SDN) has recently emerged as a new network management platform. The centralized control architecture presents many new opportunities. Among the network management tasks, measurement is one of the most important and challenging one. Researchers have proposed many solutions to better utilize SDN for network measurement. Among them, how to detect Distributed Denial-of-Services (DDoS) quickly and precisely is a very challenging problem. In this paper, we propose methods to detect DDoS attacks leveraging on SDN's flow monitoring capability. Our methods utilize measurement resources available in the whole SDN network to adaptively balance the coverage and granularity of attack detection. Through simulations we demonstrate that our methods can quickly locate potential DDoS victims and attackers by using a constrained number of flow monitoring rules.

Collaborative filtering (CF) is the state-of-the-art approach to item recommendation. However, it can neither recommend new items with no user feedbacks, nor could it recommend "long-tail" items easily. Content-based filtering can solve both problems through content analysis. However, content-based filtering alone has a much worse performance than CF. In this paper, we fuse user feedbacks and content analysis into the probabilistic matrix factorization framework. In particular, we propose a recursive dynamic programming approach to computing item similarity matrix from item content. Item latent factors are predicted from the item similarity matrix when no usage data is available. We investigate how performances of recommendation algorithms vary on items with different popularities. Results show that our approach has better performance than the same hybrid model with naive item similarity measures and Matrix Factorization.

We study interactive video calls between two users, where at least one of the users is connected over a cellular network. It is known that cellular links present highly-varying network bandwidth and packet delays. If the sending rate of the video call exceeds the available bandwidth, the video frames may be excessively delayed, destroying the interactivity of the video call. In this paper, we present Rebera, a cross-layer design of proactive congestion control, video encoding and rate adaptation, to maximize the video transmission rate while keeping the one-way frame delays sufficiently low. Rebera actively measures the available bandwidth in real-time by employing the video frames as packet trains. Using an online linear adaptive filter, Rebera makes a history-based prediction of the future capacity, and determines a bit budget for the video rate adaptation. Rebera uses the hierarchical-P video encoding structure to provide error resilience and to ease rate adaptation, while maintaining low encoding complexity and delay. Furthermore, Rebera decides in real time whether to send or discard an encoded frame, according to the budget, thereby preventing self-congestion and minimizing the packet delays. Our experiments with real cellular link traces demonstrate Rebera can, on average, deliver higher bandwidth utilization and shorter packet delays than Apple's FaceTime.

Abstract Location‐based social discovery (LBSD) services enable users to discover their geographic neighborhoods to make new friends. Original LBSD services were designed to provide the exact distances to nearby users. It has been shown that it is easy to pinpoint any target user's location by using trilateration based on the exact distances from three fake Global Positioning System locations to the target user. To defend against the trilateration attack, contemporary LBSD services then began to report distances of nearby users in concentric bands, for example, bands of 100 meters, rather than exact distances. In this paper, we investigate the user location privacy leakage problem in LBSD services reporting distances in discrete bands. Using number theory, we analytically show that by strategically placing multiple virtual probes with fake Global Positioning System locations, one can nevertheless localize user locations in band‐based LBSD. Our methodology is guaranteed to localize any reported user within a circle of radius no greater than one meter, even for LBSD services using large bands (such as 100 m as used by WeChat). Eventually, countermeasures are proposed to reduce location privacy leakage to the very minimum. To the best of our knowledge, this is the first work that explicitly exploits and quantifies user location privacy leakage in band‐based LBSD services. We expect our study to draw more public attention to this serious privacy issue and expectantly motivate better privacy preserving LBSD designs. Copyright © 2016 John Wiley & Sons, Ltd.

We consider peer-to-peer multi-party video conferencing (P2P-MPVC), where users with different uplink -downlink capacities send their videos using multicast trees. One way to deal with user bandwidth heterogeneity is employing layered video coding, generating multiple layers with different rates, whereas an alternative is partitioning the receivers of each source and disseminating a different non-layered video version within each group. In this paper, we aim to maximize the received video quality for both systems under uplink-downlink capacity constraints, while constraining the number of hops the packets traverse to two. We first show any multicast tree is equivalent to a collection of 1-hop and 2-hop trees, under user uplink-downlink capacity constraints. This reveals that the packet overlay hop count can be limited to two without sacrificing the achievable rate performance. Assuming a fine granularity scalable stream that can be truncated at any rate, we propose an algorithm that solves for the number of video layers, layer rates, and distribution trees for the layered system. For the partitioned simulcast system, we develop an algorithm to determine the receiver partitions along with the video rate and the distribution trees for each group. Through numerical comparison, we show that the partitioned simulcast system achieves the same average receiving quality as the ideal layered system without any coding overhead for the four-user systems simulated, and better quality than the layered system when the layered coding overhead is only 20%. The two systems perform similarly for the six-user case if the layered coding overhead is 10%.

HTTP Adaptive Streaming (HAS) is widely deployed on the Internet for live and on-demand video streaming services. Video adaptation algorithms in the existing HAS systems are either too sluggish to respond to congestion level shifts or too sensitive to short-term network bandwidth variations. Both degrade user video experience. In this paper, we formally study the tradeoff between responsiveness and smoothness in HAS through analysis and experiments. We show that client-side buffered video time is a good feedback signal to guide video adaptation. We then propose novel video rate control algorithms that balance the needs for video rate smoothness and high bandwidth utilization. We show that a small video rate margin can lead to much improved smoothness in video rate and buffer size. We also propose HAS designs that can work with multiple servers and wireless connections. We develop a fully functional HAS system and evaluate its performance through extensive experiments on a network testbed and the Internet. We demonstrate that our HAS designs are highly efficient and robust in realistic network environment.

Private Information Retrieval (PIR) allows users to retrieve information from a database without revealing the content of these queries to anyone. The traditional information-theoretic PIR schemes utilize multiple servers to download single data block, thus incur high communication overhead and high computation burden. In this paper, we develop an Information- theoretic multi-block PIR scheme that significantly reduce the client communication and computation overheads by downloading multiple data blocks at a time. The design of k-safe binary matrices insures the information will not be revealed even if up to k servers collude. Our scheme has much lower overhead than the classic PIR schemes. The implementation of fast XOR operations benefits both servers and clients in reducing coding and decoding time. Our work demonstrates that multi-block PIR scheme can be optimized to simultaneously achieve low communication and computation overhead, comparable to even non-PIR systems, while maintaining a high level of privacy.

The robustness of inter‐session network coding is still an open issue in lossy wireless networks. The traditional XOR based network coding cannot work well if the overhearing is unperfect. Especially, the coding node cannot know the overheard information in time. In this paper, we consider a robust network coding method, namely R 2 NC which uses random linear network coding to encode packets together in the inter‐session level, to resist the unperfect overhearing problem. With this method, coding node can always know the solvability of coded packets without the knowledge of overheard information. We analyse the performance of R 2 NC method with both lossy links of output and overhearing in the classic X ‐topology model, and give a necessary condition for the existence of coding gain. Finally, we design an optimal coding algorithm and a relay selection algorithm for R 2 NC to achieve its maximal transmission efficiency. Through ns‐2 simulations, we demonstrate that R 2 NC plays a good performance in terms of throughput, delay and overhead, and is robust against losses on output and overhearing links.

Cloud gaming has emerged as a promising approach to more affordable and accessible games. By rendering high-end video games in the cloud and streaming encoded game scenes to players via the broadband networks, users are relieved from downloading or installing game software. With cloud gaming, users can easily play high-end 3-D video games on any devices anytime and anywhere. In this paper, we conducted a comprehensive measurement study of a leading cloud gaming system in China, namely, CloudUnion. Unlike the previous work, our measurement study was based on an in-depth understanding of the internal mechanisms of CloudUnion, and thus we were able to reveal problems that cannot be observed in a black-box approach. We built a dedicated measurement platform, which enables us to study CloudUnion from different views, including the global view, local view, and user view. We also conducted a comparison study with another cloud gaming system, namely, GamingAnywhere. Our measurement results unveil the pros and cons of the current cloud gaming system design, and bring forth important insights about the cloud infrastructure, user behaviors, traffic patterns, user-perceived quality, and so on. Our work will be valuable for the design of future cloud gaming systems.

IP-based TV systems are widely used to stream video content on the Internet. Compared with the traditional broadcast TV systems, IP-based TV systems suffer from much longer channel switching delays. In this paper, we propose a new IP-based streaming framework, called fast IP-based TV (FIPTV), to achieve close-to-zero channel switching delay at the price of extra download bandwidth and increased playback lags. In FIPTV, other than the channel being watched, a client also downloads an extra combination virtual channel, called backing united stream (BUS), which consists of video segments sequentially sampled from a set of target channels that a client might switch to in the near future. Video segments downloaded from the combination channel will be cached in a local buffer. When the client issues a channel switch request to a target channel, the client will immediately playback the most recently downloaded video of the target channel, leading to close-to-zero channel switching time, but a positive playback lag. Through analysis and simulations , we show that short average playback lag can be achieved across all channels through carefully designed channel scheduling algorithms on the BUS channel by considering channel popularity. We implement the proposed streaming framework in real systems. Through experiments on the Internet, we show that the actual channel switching delay can be reduced to less than 0.25 seconds, which is much shorter than that of the popular Internet video streaming services.

Video watching time is a crucial measure for studying user watching behavior in online Internet video-on-demand (VoD) systems. It is important for system planning, user engagement study, and service quality evaluation. However, due to limited access to large-scale VoD systems, there is still a lack of accurate model for characterizing the distribution of user watching time on a per video basis. In this paper, we measure PPLive, one of the most popular commercial Internet VoD systems in China, over a three week period, and characterize user watching time distributions of 1,000 most popular movies. We find that a video's watching time can be modeled by a concatenation of exponential distribution (in the first several minutes of the video) and truncated power law distribution (in the remaining time of the video), when users watch the video without interruptions. For comparison, user watching time with user interactions such as seeking and/or pause operations does not follow such a distribution. We further reveal interesting characteristics regarding the relation between video's watching time distribution and various watching/video-related features (including time-of-day, user ratings, and movie genres). Our measurement and modeling results bring forth important insights for design, deployment, and evaluation of Internet VoD systems.

Video telephony is increasingly being adopted by end consumers. It is extremely challenging to deliver video calls over wireless networks. In this paper, we conduct a measurement study on three popular mobile video call applications: Face-Time, Google Plus Hangout, and Skype, over both WiFi and Cellular links. We study the following questions: 1) how they encode/decode video in realtime under tight resource constraints on mobile devices? 2) how they transmit video smoothly in the face of various wireless network impairments? 3) what is their delivered video conferencing quality under different mobile network conditions? 4) how different system architectures and design choices contribute to their delivered quality? Through detailed analysis of measurement results, we obtain valuable insights regarding the unique challenges, advantages and disadvantages of existing design solutions, and possible directions to deliver high-quality video calls in wireless networks.

Video telephony requires high-bandwidth and low-delay voice and video transmissions between geographically distributed users. It is challenging to deliver high-quality video telephony to end-consumers through the best-effort Internet. In this paper, we present our measurement study on three popular video telephony systems on the Internet: Google+, iChat, and Skype. Through a series of carefully designed active and passive measurements, we uncover important information about their key design choices and performance, including application architecture, video generation and adaptation schemes, loss recovery strategies, end-to-end voice and video delays, resilience against random and bursty losses, etc. The obtained insights can be used to guide the design of applications that call for high-bandwidth and low-delay data transmissions under a wide range of “best-effort” network conditions.

Multiparty video conferencing (MPVC) facilitates real-time group interaction between users. While P2P is a natural delivery solution for MPVC, a peer often does not have enough bandwidth to deliver her video to all other peers in the conference. Recently, we have witnessed the popularity of one-view MPVC, where each user only watches full video of another user. One-view MPVC opens up the design space for P2P delivery. In this paper, we explore the feasibility of a pure P2P solution for one-view MPVC. We characterize the video source rate region achievable through video relays between peers. For both homogeneous and heterogeneous MPVC systems, we establish tight universal video rate lower bounds that are independent of the number of peers, the number of video sources, and the specific viewing relations between peers. We further propose, P2P video relay designs to approach the maximal video rate region. Through numerical simulations, we verified that the derived lower bounds are indeed tight bounds, and the proposed bandwidth allocation algorithm can achieve a close-to-optimal peer upload bandwidth utilization. Our results demonstrate that P2P is a promising solution for one-view MPVC. Insights obtained from our study can be used to guide the design of P2P MPVC systems.

In dynamic streaming, a user can dynamically choose from different versions of the same video. In P2P dynamic streaming, there is one P2P swarm for each version, and within a swarm, peers can share video chunks with each other, thereby reducing the server's bandwidth cost. Due to economy of scale, cooperation among peers can also reduce the per-peer content price. In this paper, we use cooperative game theory to dynamically assign each peer to a version. To maximally incentivize peer cooperation, we use mechanism design to develop pricing schemes that reflect content and bandwidth cost savings derived from peer cooperation. With this approach, each peer is assigned to a swarm that is commensurate with its upload contribution and the price it is willing to pay. We also develop and simulate a distributed dynamic P2P streaming algorithm, consisting of chunk scheduling, token-based accounting, and video version switching, to dynamically adjust each peer's video version based on the collaborative behaviors of all peers.

Adaptive streaming, such as Dynamic Adaptive Streaming over HTTP (DASH), has been widely deployed to provide uninterrupted video streaming service to users with dynamic network conditions. In this paper, we analytically study the potential of using P2P in conjunction with adaptive streaming. We first study the capacity of P2P adaptive streaming by developing utility maximization models that take into account peer heterogeneity, taxation-based incentives, multi-version videos at discrete rates. We further develop stochastic models to study the performance of P2P adaptive streaming in face of bandwidth variations and peer churn. Through analysis and simulations, we demonstrate that incentive-compatible video sharing between peers can be easily achieved with simple video coding and distribution designs. P2P adaptive streaming not only significantly reduces the load on the servers, but also improves the stability of user-perceived video quality in the face of dynamic bandwidth changes.

Video watching time is a crucial measure for studying user watching behavior in online Internet video-on-demand (VoD) systems. It is important for system planning, user engagement understanding, and system quality evaluation. However, due to the limited access of user data in large-scale streaming systems, a systematic measurement, analysis, and modeling of video watching time is still missing. In this paper, we measure PPLive, one of the most popular commercial Internet VoD systems in China, over a three week period. We collect accurate user watching data of more than 100 million streaming sessions of more than 100 thousand distinct videos. Based on the measurement data, we characterize the distribution of watching time of different types of videos and reveal a number of interesting characteristics regarding the relation between video watching time and various video-related features (including video type, duration, and popularity). We further build a suite of mathematical models for characterizing these relationships. Extensive performance evaluation shows the high accuracy of these models as compared with commonly used data-mining based models. Our measurement and modeling results bring forth important insights for simulation, design, deployment, and evaluation of Internet VoD systems.

Video-conferencing has recently gained its momentum and is widely adopted by end-consumers. But there have been very few studies on the network impacts of video calls and the user Quality-of-Experience (QoE) under different network conditions. In this paper, we study the rate control and video quality of Skype video call, and analyze the network impacts in large-scale networks. We first measure the behaviors of Skype video call on a controlled network testbed. By varying packet loss rate, propagation delay and available network bandwidth, we observe how Skype adjusts its sending rate, FEC redundancy, video rate and frame rate. It is found that Skype is robust against mild packet losses and propagation delays, and can efficiently utilize the available network bandwidth. We also find that it employs an overly aggressive FEC protection strategy. Based on the measurement results, we develop rate control model, FEC model, and video quality model for Skype video calls. Extrapolating from the models, we conduct numerical analysis to study the network impacts. We demonstrate that user back-offs upon quality degradation serve as an effective user-level rate control scheme. We also show that Skype video calls are indeed TCP-friendly and respond to congestion quickly when the network is overloaded. Through a case study of a 4G wireless network, we demonstrate that the proposed models can be used in user-QoE-aware network provisioning.

We perform a large-scale topology mapping and geolocation study for China's Internet. To overcome the limited number of Chinese PlanetLab nodes and looking glass servers, we leverage unique features in China's Internet, including the hierarchical structure of the major ISPs and the abundance of IDC data centers. Using only 15 vantage points, we design a traceroute scheme that finds significantly more interfaces and links than iPlane with significantly fewer traceroute probes. We then consider the problem of geolocating router interfaces and end hosts in China. When examining three well-known Chinese geoIP databases, we observe frequent occurrences of null replies and erroneous entries, suggesting that there is significant room for improvement. We develop a heuristic for clustering the interface topology of a hierarchical ISP, and then apply the heuristic to the major Chinese ISPs. We show that the clustering heuristic can geolocate router interfaces with significantly more detail and consistency than can the existing geoIP databases in isolation. We show that the resulting clusters expose several characteristics of the Chinese Internet, including the major ISPs' provincial structure and the centralized interconnections among the ISPs. Finally, using the clustering heuristic, we propose a methodology for improving commercial geoIP databases and evaluate using IDC data center landmarks.

In this paper, we propose a Bayesian-inference-based recommendation system for online social networks. In our system, users share their content ratings with friends. The rating similarity between a pair of friends is measured by a set of conditional probabilities derived from their mutual rating history. A user propagates a content rating query along the social network to his direct and indirect friends. Based on the query responses, a Bayesian network is constructed to infer the rating of the querying user. We develop distributed protocols that can be easily implemented in online social networks. We further propose to use Prior distribution to cope with cold start and rating sparseness. The proposed algorithm is evaluated using two different online rating data sets of real users. We show that the proposed Bayesian-inference-based recommendation is better than the existing trust-based recommendations and is comparable to Collaborative Filtering (CF) recommendation. It allows the flexible tradeoffs between recommendation quality and recommendation quantity. We further show that informative Prior distribution is indeed helpful to overcome cold start and rating sparseness.

Dynamic Adaptive Streaming over HTTP (DASH) is widely deployed on the Internet for live and on-demand video streaming services. Video adaptation algorithms in existing DASH systems are either too sluggish to respond to congestion level shifts or too sensitive to short-term network bandwidth variations. Both degrade user video experience. In this paper, we formally study the responsiveness and smoothness trade-off in DASH through analysis and experiments. We show that client-side buffered video time is a good feedback signal to guide video adaptation. We then propose novel video rate control algorithms that balance the needs for video rate smoothness and high bandwidth utilization. We show that a small video rate margin can lead to much improved smoothness in video rate and buffer size. The proposed DASH designs are also extended to work with multiple CDN servers. We develop a fully-functional DASH system and evaluate its performance through extensive experiments on a network testbed and the Internet. We demonstrate that our DASH designs are highly efficient and robust in realistic network environment.

Video telephony requires high-bandwidth and low-delay voice and video transmissions between geographically distributed users. It is challenging to deliver high-quality video telephony to end-consumers through the best-effort Internet. In this paper, we present our measurement study on three popular video telephony systems on the Internet: Google+, iChat, and Skype. Through a series of carefully designed active and passive measurements, we are able to unveil important information about their key design choices and performance, including application architecture, video generation and adaptation schemes, loss recovery strategies, end-to-end voice and video delays, resilience against random and bursty losses, etc. Obtained insights can be used to guide the design of applications that call for high-bandwidth and low-delay data transmissions under a wide range of "best-effort" network conditions.

We perform a large-scale topology mapping and geolocation study for China's Internet. To overcome the limited number of Chinese PlanetLab nodes and looking glass servers, we leverage several unique features in China's Internet, including the hierarchical structure of the major ISPs and the abundance of IDCs. Using only 15 vantage points, we design a traceroute scheme that finds significantly more interfaces and links than iPlane with significantly fewer traceroute probes. We then consider the problem of geolocating router interfaces and end hosts in China. We develop a heuristic for clustering the interface topology of a hierarchical ISP, and then apply the heuristic to the major Chinese ISPs. We show that the clustering heuristic can geolocate router interfaces with significantly more detail and accuracy than can the existing geoIP databases in isolation, and the resulting clusters expose the major ISPs' provincial structure. Finally, using the clustering heuristic, we propose a methodology for improving commercial geoIP databases.

Video telephony has recently gained its momentum and is widely adopted by end-consumers. But there have been very few studies on the network impacts of video calls and the user Quality-of-Experience (QoE) under different network conditions. In this paper, we study the rate control and video quality of Skype video calls. We first measure the behaviors of Skype video calls on a controlled network testbed. By varying packet loss rate, propagation delay and bandwidth, we observe how Skype adjusts its rates, FEC redundancy and video quality. We find that Skype is robust against mild packet losses and propagation delays, and can efficiently utilize the available network bandwidth. We also find that Skype employs an overly aggressive FEC protection strategy. Based on the measurement results, we develop rate control model, FEC model, and video quality model for Skype. Extrapolating from the models, we conduct numerical analysis to study the network impacts of Skype. We demonstrate that user back-offs upon quality degradation serve as an effective user-level rate control scheme. We also show that Skype video calls are indeed TCP-friendly and respond to congestion quickly when the network is overloaded.

Online social network information promises to increase recommendation accuracy beyond the capabilities of purely rating/feedback-driven recommender systems (RS). As to better serve users' activities across different domains, many online social networks now support a new feature of "Friends Circles", which refines the domain-oblivious "Friends" concept. RS should also benefit from domain-specific "Trust Circles". Intuitively, a user may trust different subsets of friends regarding different domains. Unfortunately, in most existing multi-category rating datasets, a user's social connections from all categories are mixed together. This paper presents an effort to develop circle-based RS. We focus on inferring category-specific social trust circles from available rating data combined with social network data. We outline several variants of weighting friends within circles based on their inferred expertise levels. Through experiments on publicly available data, we demonstrate that the proposed circle-based recommendation models can better utilize user's social trust information, resulting in increased recommendation accuracy.

User Generated Content (UGC) video applications, such as YouTube, are enormously popular. UGC systems can potentially reduce their distribution costs by allowing peers to store and redistribute the videos that they have seen in the past. We study peer-assisted UGC from three perspectives. First, we undertake a measurement study of the peer-assisted distribution system of Tudou (a popular UGC network in China), revealing several fundamental characteristics that models need to take into account. Second, we develop analytical models for peer-assisted distribution of UGC. Our models capture essential aspects of peer-assisted UGC systems, including system size, peer bandwidth heterogeneity, limited peer storage, and video characteristics. We apply these models to numerically study YouTube-like UGC services. And third, we develop analytical models to understand the rate at which users would install P2P client applications to make peer-assisted UGC a success. Our results provide a comprehensive study of peer-assisted UGC distribution, exposing its fundamental characteristics and limitations.

Recommendation accuracy can be improved by incorporating trust relationships derived from social networks. Most recent work on social network based recommendation is focused on minimizing the root mean square error (RMSE). Social network based top-k recommendation, which recommends to a user a small number of items at a time, is not well studied. In this paper, we conduct a comprehensive study on improving the accuracy of top-k recommendation using social networks. We first show that the existing social-trust enhanced Matrix Factorization (MF) models can be tailored for top-k recommendation by including observed and missing ratings in their training objective functions. We also propose a Nearest Neighbor (NN) based top-k recommendation method that combines users' neighborhoods in the trust network with their neighborhoods in the latent feature space. Experimental results on two publicly available datasets show that social networks can significantly improve the top-k hit ratio, especially for cold start users. Surprisingly, we also found that the technical approach for combining feedback data (e.g. ratings) with social network information that works best for minimizing RMSE works poorly for maximizing the hit ratio, and vice versa.

In this paper, we propose a Bayesian-inference based recommendation system for online social networks. In our system, users share their movie ratings with friends. The rating similarity between a pair of friends is measured by a set of conditional probabilities derived from their mutual rating history. A user propagates a movie rating query along the social network to his direct and indirect friends. Based on the query responses, a Bayesian network is constructed to infer the rating of the querying user. We develop distributed protocols that can be easily implemented in online social networks. The proposed algorithm is evaluated in a synthesized social network derived from a movie rating data set of real users. We show that the Bayesian-inference based recommendation provides personalized recommendations as accurate as the traditional CF approaches, and allows the flexible trade-offs between recommendation quality and recommendation quantity.

Recent advances in scalable video coding (SVC) make it possible for users to receive the same video with different qualities. To adopt SVC in P2P streaming, two key design questions need to be answered: 1) layer subscription: how many layers each peer should receive, and 2) layer scheduling: how to deliver to peers the layers they subscribed. From the system point of view, the most efficient solution is to maximize the aggregate video quality on all peers, i.e., the social welfare. From individual peer point of view, the solution should be fair. Fairness in P2P streaming should additionally take into account peer contributions to make the solution incentive-compatible. In this paper, we first develop utility maximization models to understand the interplay between efficiency, fairness and incentive in layered P2P streaming. We show that taxation mechanisms can be devised to strike the right balance between social welfare and individual peer welfare. We then develop practical taxation-based P2P layered streaming designs, including layer subscription strategy, chunk scheduling policy, and mesh topology adaptation. Extensive trace-driven simulations show that the proposed designs can effectively drive layered P2P streaming systems to converge to the desired operating points in a distributed fashion.

Mobile video broadcasting service, or mobile TV, is expected to become a popular application for 3G wireless network operators. Most existing solutions for video Broadcast Multicast Services (BCMCS) in 3G networks employ a single transmission rate to cover all viewers. The system-wide video quality of the cell is therefore throttled by a few viewers close to the boundary, and is far from reaching the social-optimum allowed by the radio resources available at the base station. In this paper, we propose a novel scalable video broadcast/multicast solution, SV-BCMCS, that efficiently integrates scalable video coding, 3G broadcast, and ad-hoc forwarding to balance the system-wide and worst-case video quality of all viewers at 3G cell. We solve the optimal resource allocation problem in SV-BCMCS and develop practical helper discovery and relay routing algorithms. Moreover, we analytically study the gain of using ad-hoc relay, in terms of users' effective distance to the base station. Through extensive real video sequence driven simulations, we show that SV-BCMCS significantly improves the system-wide perceived video quality. The users' average PSNR increases by as much as 1.70 dB with slight quality degradation for the few users close to the 3G cell boundary.

In a multiparty video conference, multiple users simultaneously distribute video streams to their receivers. As the traditional server-based solutions incur high infrastructure and bandwidth cost, conventional peer-to-peer (P2P) solutions only leveraging end-users' upload bandwidth are normally not self-sustainable: The video streaming workload increases quadratically with the number of users as each user could generate and distribute video streams, while the user upload bandwidth only increases linearly. Recently, hybrid solutions have been proposed that employ helpers to address the bandwidth deficiency in P2P video-conferencing swarms. It is also noticed that a system hosting multiple parallel conferencing swarms can benefit from cross-swarm bandwidth sharing. However, how to optimally share bandwidth in such systems has not been explored so far. In this paper, we study the optimal bandwidth sharing in multiswarm multiparty P2P video-conferencing systems with helpers and investigate two cross-swarm bandwidth-sharing scenarios: (1) swarms are independent and peers from different swarms share a common pool of helpers; (2) swarms are cooperative and peers in a bandwidth-rich swarm can further share their bandwidth with peers in a bandwidth-poor swarm. For each scenario, we develop distributed algorithms for intraswarm and interswarm bandwidth allocation under a utility-maximization framework. Through analysis and simulation, we show that the proposed algorithms are robust to peer dynamics and can adaptively allocate peer and helper bandwidth across swarms so as to achieve the system-wide optimum.

Opportunistic Routing (OR) has recently been proposed to improve the efficiency of unicast in multi-hop wireless networks. OR exploits the broadcast nature of wireless transmission medium and opportunistically selects a relay path to deliver a packet to its receiver. To adopt OR in wireless multicast, the main challenge is to efficiently share opportunistic relay paths between multiple receivers. In this paper, we propose an opportunistic overlay multicast design for wireless networks, named Minimum Steiner Tree with Opportunistic Routing (MSTOR). In MSTOR, the source and receivers are connected by an overlay Sterner tree. The source multicasts packets along the overlay links of the Steiner tree to reach all receivers. The transmission of packets on each overlay link is controlled by unicast OR. We first propose an overlay construction algorithm based on the optimal "OR distance" between nodes. We then design the MSTOR protocol and implement it in OPNET by customizing the IEEE 802.15.4 modules. Through OPNET simulations, we study the performance improvement of MSTOR over several existing unicast and multicast routing schemes. Our results demonstrate that MSTOR can achieve a much higher multicast efficiency than the original unicast OR and the traditional minimum multicast-tree based schemes. MSTOR can be easily deployed for multicast in multi-hop wireless networks.

Despite the success to deliver increasingly large number of channels to millions of users, the current multi-channel P2P video streaming systems still suffer several fundamental performance problems, such as large start-up delays and poor performance for unpopular channels. To alleviate the impact of channel churn and resource imbalance, the View-Upload Decoupling (VUD) P2P streaming design decouples peer downloading and uploading, and enables cross-channel resource sharing. However, VUD incurs upload bandwidth overhead and distribution swarm management cost. It is also challenging to adapt VUD distribution swarms in extreme peer churn scenarios, such as flash-crowd. In this paper, we propose ViVUD, a Virtual Server Cluster based VUD design. In ViVUD, a virtual server cluster consisting of bandwidth-rich peers is provisioned to improve the streaming quality of each channel. A virtual server cluster provides stable video feeds to boost peers newly joining a channel to reduce their start-up delays. To enable cross-channel bandwidth sharing, following the VUD design, virtual server clusters for unpopular channels are formed by bandwidth-rich peers watching popular channels. Through analysis and simulations, we show that, compared with the original VUD design, ViVUD incurs less upload bandwidth overhead, has lighter management requirement, achieves lower channel start-up delays, and adapts faster to flash crowds.

The success of future P2P applications ultimately depends on whether users will contribute their bandwidth, CPU and storage resources to a larger community. In this paper, we propose a new incentive paradigm, Networked Asynchronous Bilateral Trading (NABT), which can be applied to a broad range of P2P applications. In NABT, peers belong to an underlying social network, and each pair of friends keeps track of a credit balance between them. When user Alice provides a service (a file, storage space, computation and so on) to her friend Bob, she charges Bob credits. Thus, in NABT, there is no global currency; instead, there are only credit balances maintained between pairs of friends. NABT allows peers to supply each other asynchronously and further allows peers to trade with remote peers through intermediaries. We theoretically show that NABT is perfectly efficient with balanced demands and supports "networked tit-for-tat". The efficiency of NABT with unbalanced demands is determined by the min-cut of credit limits of the underlying social network. Using simulations driven by MySpace traces, we demonstrate that a simple two-hop NABT design can have high trading efficiency, provide service differentiation, exploit trading intermediaries, and discourage free-riders.

Recent advance in scalable video coding (SVC) makes it possible for users to receive the same video with different qualities. To adopt SVC in P2P streaming, two key design questions need to be answered: 1) layer subscription: how many layers each peer should receive? 2) layer scheduling: how to deliver to peers the layers they subscribed? From the system point of view, the most efficient solution is to maximize the aggregate video quality on all peers, i.e., the social welfare. From individual peer point of view, the solution should be fair. Fairness in P2P streaming should additionally take into account peer contributions to make the solution incentive-compatible. In this paper, we show that taxation mechanisms can be devised to strike the right balance between social welfare and individual peers' welfare. We develop practical taxation-based P2P layered streaming designs, including layer subscription strategy, chunk scheduling policy, and mesh topology adaptation. Extensive trace-driven simulations show that the proposed designs can effectively drive layered P2P streaming systems to converge to the desired operating points in a distributed fashion.

Peer-to-peer (P2P) systems exploit the uploading bandwidth of individual peers to distribute content at low server cost. While the P2P bandwidth sharing design is very efficient for bandwidth-sensitive applications, it imposes a fundamental performance constraint for delay-sensitive applications: The uploading bandwidth of a peer cannot be utilized to upload a piece of content until it completes the download of that content. This constraint sets up a limit on how fast a piece of content can be disseminated to all peers in a P2P system. In this paper, we theoretically study the impact of this inherent delay constraint and derive the minimum delay bounds for P2P live streaming systems. We show that the bandwidth heterogeneity among peers can be exploited to significantly improve the delay performance of all peers. We further propose a conceptual snowball streaming algorithm to approach the minimum delay bound in a dynamic P2P networking environment. Our analysis and simulation suggest that the proposed algorithm has better delay performance and more robust than static balanced multi-tree-based streaming solutions. Insights brought forth by our study can be used to guide the design of new P2P systems with shorter streaming delays.

In recent years, there have been several large-scale deployments of P2P live video systems. Existing and future P2P live video systems will offer a large number of channels, with users switching frequently among the channels. In this paper, we develop infinite-server queueing network models to analytically study the performance of multichannel P2P live video systems. Our models capture essential aspects of multichannel video systems, including peer channel switching, peer churn, peer bandwidth heterogeneity, and Zipf-like channel popularity. We apply the queueing network models to two P2P streaming designs: the isolated channel design (ISO) and the View-Upload Decoupling (VUD) design. For both of these designs, we develop efficient algorithms to calculate critical performance measures, develop an asymptotic theory to provide closed-form results when the number of peers approaches infinity, and derive near-optimal provisioning rules for assigning peers to groups in VUD. We use the analytical results to compare VUD with ISO. We show that VUD design generally performs significantly better, particularly for systems with heterogeneous channel popularities and streaming rates.

As an efficient distribution mechanism, Peer-to-Peer (P2P) technology has become a tremendously attractive solution to offload servers in large-scale video streaming applications. However, in providing on-demand asynchronous streaming services, P2P streaming design faces two major challenges: how to schedule efficient video sharing between peers with asynchronous playback progresses? how to provide incentives for peers to contribute their resources to achieve a high level of system-wide Quality-of-Experience (QoE)? In this paper, we present iPASS, a novel mesh-based P2P VoD system, to address these challenges. Specifically, iPASS adopts a dynamic buffering-progress-based peering strategy to achieve high peer bandwidth utilization with low system maintenance cost. To provide incentives for peer uploading, iPASS employs a differentiated prefetching design that enables peers with higher contribution prefetch content at higher speed. A distributed adaptive taxation algorithm is developed to balance the system-wide QoE and service differentiations among heterogeneous peers. To assess the performance of iPASS, we built a detailed packet-level P2P VoD simulator and conducted extensive simulations. It was demonstrated that iPASS can completely offload server when the average peer upload bandwidth is more than 1.2 times the streaming rate. Furthermore, we showed that the distributed incentive algorithm motivates peers to contribute and collaboratively achieve a high level of system wide QoE.

Mobile video broadcasting service, or mobile TV, is a promising application for 3G wireless network operators. Most existing solutions for video broadcast/multicast services in 3G networks employ a single transmission rate to cover all viewers. The system-wide video quality of the cell is therefore throttled by a few viewers close to the boundary, and is far from reaching the social-optimum allowed by the radio resources available at the base station. In this paper, we propose a novel scalable video broadcast/multicast solution, SV-BCMCS, that efficiently integrates scalable video coding, 3G broadcast and adhoc forwarding to balance the system-wide and worst-case video quality of all viewers in a 3G cell. We study the optimal resource allocation problem in SV-BCMCS and develop practical helper discovery and relay routing algorithms. Through analysis and extensive OPNET simulations, we demonstrate that SV-BCMCS can significantly improve the system-wide video quality at the price of slight quality degradation of a few viewers close to the boundary.

In recent years, peer-to-peer (P2P) technology has been demonstrated tremendously effective in delivering large-scale video streaming services. Although P2P streaming is scalable and robust, the network-oblivious peering and scheduling in the current designs impede the further improvement in streaming quality and the efficient usage of network resources. New P2P streaming systems exploit network information provided by Internet service providers (ISPs) to achieve a higher level of application performance and generate lower traffic stress. In this paper, utilizing information from ISPs, we investigate the strategies on the topology construction and maintenance of multi-tree based P2P streaming systems. We study topology optimization to minimize the average height of sub-stream trees and the average propagation latency in each tree. We first present the optimization formulations, and then propose a set of heuristic algorithms for the construction and dynamic management of the multiple sub-stream trees for practical implementation. Through numerical comparison study, we show that our algorithms can significantly improve the delay performance of existing P2P streaming systems.

As an efficient distribution mechanism, peer-to-peer technology has become a tremendously attractive solution to offload servers in large scale video streaming applications. However, in providing on-demand asynchronous streaming services, P2P streaming design faces two major challenges: how to schedule efficient video sharing between peers with asynchronous playback progresses? how to provide incentives for peers to contribute their resources to achieve a high level of system-wide quality-of-experience (QoE)? In this paper, we present iPASS, a novel mesh-based P2P VoD system, to address these challenges. Specifically, iPASS adopts a dynamic buffering-progress-based peering strategy to achieve high peer bandwidth utilization with low system maintenance cost. To provide incentives for peer uploading, iPASS employs a differentiated pre-fetching design that enables peers with higher contribution pre-fetch content at higher speed. Through packet-level simulations, it was demonstrated that iPASS can effectively offload server and the proposed distributed incentive algorithm motivates peers to contribute and collectively achieve a high level of of QoE.

In current multi-channel live P2P video systems, there are several fundamental performance problems including exceedingly-large channel switching delays, long playback lags, and poor performance for less popular channels. These performance problems primarily stem from two intrinsic characteristics of multi-channel P2P video systems: channel churn and channel- resource imbalance. In this paper, we propose a radically different cross-channel P2P streaming framework, called view-upload decoupling (VUD). VUD strictly decouples peer downloading from uploading, bringing stability to multichannel systems and enabling cross-channel resource sharing. We propose a set of peer assignment and bandwidth allocation algorithms to properly provision bandwidth among channels, and introduce substream swarming to reduce the bandwidth overhead. We evaluate the performance of VUD via extensive simulations as well with a PlanetLab implementation. Our simulation and PlanetLab results show that VUD is resilient to channel churn, and achieves lower switching delay and better streaming quality. In particular, the streaming quality of small channels is greatly improved.

In recent years there have been several large-scale deployments of P2P live video systems. Existing and future P2P live video systems will offer a large number of channels, with users switching frequently among the channels. In this paper, we develop infinite-server queueing network models to analytically study the performance of multi-channel P2P streaming systems. Our models capture essential aspects of multi-channel video systems, including peer channel switching, peer churn, peer bandwidth heterogeneity, and Zipf-like channel popularity. We apply the queueing network models to two P2P streaming designs: the isolated channel design (ISO) and the View-Upload Decoupling (VUD) design. For both of these designs, we develop efficient algorithms to calculate critical performance measures, develop an asymptotic theory to provide closed-form results when the number of peers approaches infinity, and derive near- optimal provisioning rules for assigning peers to groups in VUD. We use the analytical results to compare VUD with ISO. We show that VUD design generally performs significantly better, particularly for systems with heterogeneous channel popularities and streaming rates.

Peer-to-peer (P2P) technology has recently been employed to deliver large scale video multicast services on the Internet. Considerable efforts have been made by both academia and industry on P2P streaming design. While academia mostly focus on exploring design space to approach the theoretical performance bounds, our recent measurement study on several commercial P2P streaming systems indicates that they are able to deliver good user quality of experience with seemingly simple designs. One intriguing question remains:how elaborate should a good P2P video streaming design be?Towards answering this question, we developed and implemented several representative P2P streaming designs, ranging from theoretically proved optimal designs to straightforward “naive” designs. Through an extensive comparison study on PlanetLab, we unveil several key factors contributing to the successes of simple P2P streaming designs, including system resource index, server capacity and chunk scheduling rule, peer download buffering and peering degree. We also identify regions where naive designs are inadequate and more elaborate designs can improve things considerably. Our study not only brings us better understandings and more insights into the operation of existing systems, it also sheds lights on the design of future systems that can achieve a good balance between the performance and the complexity.

Peer-to-Peer (P2P) technology has recently been employed to deliver large scale video multicast services on the Internet. Considerable efforts have been made by both academia and industry on P2P streaming design. While academia mostly focus on exploring design space to approach the theoretical performance bounds, our recent measurement study on several commercial P2P streaming systems indicates that they are able to deliver good user Quality of Experience with seemingly simple designs. One intriguing question remains: how elaborate should a good P2P video streaming design be? Towards answering this question, we developed and implemented several representative P2P streaming designs, ranging from theoretically proved optimal designs to straight forward "naive" designs. Through an extensive comparison study on PlanetLab, we unveil several key factors contributing to the successes of simple P2P streaming designs, including system resource index, sever capacity and chunk scheduling rule, peer download buffering and peering degree. We also identify regions where naive designs are inadequate and more elaborate designs can improve things considerably. Our study not only brings us better understandings and more insights into the operation of existing systems, it also sheds lights on the design of future systems that can achieve a good balance between the performance and the complexity.

Peer-to-peer overlays can be used for service discovery over a global network fabric. We describe and evaluate a new service indexing mechanism for in-band streaming services such as application relays, mixers, and media transcoders. For this type of service, the location of the service in the network and service admission status are key attributes. We describe and analyze a service indexing mechanism which uses network position-based advertisement. We show that this mechanism gives good service selection, provides a close to uniform advertisement distribution in the overlay, reduces message overhead, and exhibits acceptable stability and setup delay.

Peer-to-peer video streaming has been gaining popularity. However, it is still challenging to manage a P2P system efficiently to support high video playback rate. In this paper, we propose HCPS - Hierarchically Clustered P2P Streaming system that can support a streaming rate approaching the optimum upper bound with short delay, yet is simple enough to be implemented in practice. In HCPS, the peers are grouped into clusters and a hierarchy is formed among clusters to retrieve video data from the source server. By actively balancing the uploading capacities among clusters, and executing the perfect scheduling algorithm [1] within each cluster, the system resource can be fully utilized. The simulation experiments driven by the traces collected from a real P2P streaming system demonstrate the effectiveness of HCPS.

Under device failures and maintenance activities, network resources reduce and congestion may arise inside networks. In this paper, we study a dual approach that combines traffic blocking (rate-limiting) at the edge of a network and traffic rerouting inside the network. We formulate a joint ingress blocking and routing optimization problem and develop mechanisms to introduce blocking differentiations among users with different service priorities and with different level of impact to network congestions. Our evaluation result shows that by blocking only a small fraction of traffic, one can greatly reduce network congestion under severe failures and maintenance activities. Our solution efficiently identifies the optimal blocking among heterogeneous users and achieves much better performance in comparison with proportional traffic blocking. The proposed algorithms can be easily adopted by network service providers in their traffic engineering practices.

We develop a simple stochastic fluid model that seeks to expose the fundamental characteristics and limitations of P2P streaming systems. This model accounts for many of the essential features of a P2P streaming system, including the peers' realtime demand for content, peer churn (peers joining and leaving), peers with heterogeneous upload capacity, limited infrastructure capacity, and peer buffering and playback delay. The model is tractable, providing closed-form expressions which can be used to shed insight on the fundamental behavior of P2P streaming systems. The model shows that performance is largely determined by a critical value. When the system is of moderate-to-large size, if a certain ratio of traffic loads exceeds the critical value, the system performs well; otherwise, the system performs poorly. Furthermore, large systems have better performance than small systems since they are more resilient to bandwidth fluctuations caused by peer churn. Finally, buffering can dramatically improve performance in the critical region, for both small and large systems. In particular, buffering can bring more improvement than can additional infrastructure bandwidth.

P2P systems exploit the uploading bandwidth of individual peers to distribute content at low server cost. While the P2P bandwidth sharing design is very efficient for bandwidth sensitive applications, it imposes a fundamental performance constraint for delay sensitive applications: the uploading bandwidth of a peer cannot be utilized to upload a piece of content until it completes the download of that content. This constraint sets up a limit on how fast a piece of content can be disseminated to all peers in a P2P system. In this paper, we theoretically study the impact of this inherent delay constraint and derive the minimum delay bounds for realtime P2P streaming systems. We show that the bandwidth heterogeneity among peers can be exploited to significantly improve the delay performance of all peers. We further propose a simple snow-ball streaming algorithm to approach the minimum delay bound in realtime P2P video streaming. Our analysis suggests that the proposed algorithm has better delay performance and more robust than existing tree-based streaming solutions. Insights brought forth by our study can be used to guide the design of new P2P systems with shorter startup delays.

This paper explores how to remotely monitor network-wide quality in mesh-pull P2P live streaming systems. Peers in such systems advertise to each other buffer maps which summarize the chunks of the video stream that they currently have cached and make available for sharing. We demonstrate how buffer maps can be exploited to monitor network-wide quality. We show that the information provided in a peer's advertised buffer map correlates with that peer's viewing-continuity and startup latency. Given this correlation, we remotely harvest buffer maps from many peers and then process these buffer maps to estimate the video playback quality. We apply this methodology to a popular P2P live streaming system, namely, PPLive. To harvest buffer maps, we build a buffer-map crawler and also deploy passive sniffing nodes. We process the harvested buffer maps and present results for network-wide playback continuity, startup latency, playback lags among peers, and chunk propagation patterns. The results show that this methodology can provide reasonably accurate estimates of ongoing video playback quality throughout the network.

An emerging Internet application, IPTV, has the potential to flood Internet access and backbone ISPs with massive amounts of new traffic. Although many architectures are possible for IPTV video distribution, several mesh-pull P2P architectures have been successfully deployed on the Internet. In order to gain insights into mesh-pull P2P IPTV systems and the traffic loads they place on ISPs, we have undertaken an in-depth measurement study of one of the most popular IPTV systems, namely, PPLive. We have developed a dedicated PPLive crawler, which enables us to study the global characteristics of the mesh-pull PPLive system. We have also collected extensive packet traces for various different measurement scenarios, including both campus access networks and residential access networks. The measurement results obtained through these platforms bring important insights into P2P IPTV systems. Specifically, our results show the following. 1) P2P IPTV users have the similar viewing behaviors as regular TV users. 2) During its session, a peer exchanges video data dynamically with a large number of peers. 3) A small set of super peers act as video proxy and contribute significantly to video data uploading. 4) Users in the measured P2P IPTV system still suffer from long start-up delays and playback lags, ranging from several seconds to a couple of minutes. Insights obtained in this study will be valuable for the development and deployment of future P2P IPTV systems.

In many energy-rechargeable wireless sensor networks, sensor nodes must both sense data from the environment, and cooperatively forward sensed data to data sinks. Both data sensing and data forwarding (including data transmission and reception) consume energy at sensor nodes. We present a distributed algorithm for optimal joint allocation of energy between sensing and communication at each node to maximize overall system utility (i.e., the aggregate amount of information received at the data sinks). We consider this problem in the context of wireless sensor networks with directional, non-steerable antennas. We first formulate a joint data-sensing and data-routing optimization problem with both per-node energy-expenditure constraints, and traditional flow routing/conservation constraints. We then simplify this problem by converting it to an equivalent routing problem, and present a distributed gradient-based algorithm that iteratively adjusts the per-node amount of energy allocated between sensing and communication to reach the system-wide optimum. We prove that our algorithm converges to the maximum system utility. We quantitatively demonstrate the energy balance achieved by this algorithm in a network of small, energy-constrained X-band radars, connected via point- to-point 802.11 links with non-steerable directional antennas.

In this paper, we consider the problem of finding an "efficient" and "robust" set of routes in the face of changing/uncertain traffic. The changes/uncertainty in exogenous traffic is characterized by multiple traffic matrices. Our goal is to find a set of routes that result in good average case performance over the set of traffic matrices, while avoiding bad worst case performance for any single traffic matrix. With multiple traffic matrices, previous work aims solely to optimize the average case performance Chun Zhang, et al., (2005), or the worst case performance David Applegate, et al., (2003). For a given set of traffic matrices, different sets of routes offer a different tradeoff between the average case and the worst case performance. In this paper, we quantify the performance of a routing configuration at both network level and link level. We propose a simple metric-a weighted sum of the average case and the worst case performance-to control the tradeoff between these two considerations. Despite of its simple form, this metric is very effective. We prove that optimizing routing using this metric has desirable properties, such as the average case performance being a decreasing, convex and differentiable function to the worst case performance. By extending previous work Chun Zhang, et al., (2005) Bernard Fortz, et al., (2002), we derive methods to find the optimal routes with respect to the proposed metric for two classes of intra-domain routing protocols: MPLS and OSPF/IS-IS. We evaluate our approach with data collected from an operational tier-I ISP. For MPLS, we find that there exists significant tradeoff (e.g., 15%-23% difference) between optimizing solely on the average case performance and solely on the worst case performance. Our approach can identify solutions that can dramatically improve the worst case performance (13%-15%) while only slightly sacrificing the average case performance (2.2%-3%), in comparison to that by optimizing solely on the average case performance. For OSPF/IS-IS, we still find a significant difference between the two optimization objectives, however, a fine-grained tradeoff is difficult to achieve due to the limited control that OSPF/IS-IS provide.

In this paper, we study the interaction between overlay routing and traffic engineering (TE) in a single autonomous system (AS). We formulate this interaction as a two-player non-cooperative non-zero sum game, where the overlay tries to minimize the delay of its traffic and the TE's objective is to minimize network cost. We study a Nash routing game with best-reply dynamics, in which the overlay and TE have equal status, and take turns to compute their optimal strategies based on the response of the other player in the previous round. We prove the existence, uniqueness and global stability of Nash equilibrium point (NEP) for a simple network. For general networks, we show that the selfish behavior of an overlay can cause huge cost increases and oscillations to the whole network. Even worse, we have identified cases, both analytically and experimentally, where the overlay's cost increases as the Nash routing game proceeds even though the overlay plays optimally based on TE's routing at each round. Experiments are performed to verify our analysis.

Routing optimization is used to find a set of routes that minimizes cost (delay, utilization). Previous work has addressed this problem for the case of a known, static end-to-end traffic matrix. In the Internet, it is difficult to accurately estimate a traffic matrix, and the constantly changing nature of Internet traffic makes it costly to maintain optimal routing by responding to traffic changes. Thus, it is of interest to maintain a set of routes that are "good" for a number of different possible traffic scenarios. In this paper, we explore ways to find an optimal set of routes with multiple traffic matrices to minimize expected cost. We focus on two general approaches, source-destination routing and destination routing. In the case of source-destination routing, we extend existing methods with a single traffic matrix to solve the optimization problem with multiple traffic matrices: we extend the convex optimization solution methods for a single traffic matrix to the multiple traffic matrix case; we also extend the gradient-based solution methods for a single traffic matrix to the multiple traffic matrix case. However, the multiple traffic matrix case requires many more control variables. In the case of destination routing, we encounter many more differences from the single traffic matrix case. The loop-free property, which is valid for the single traffic matrix case, is no longer valid for the multiple traffic matrix case, and it is difficult to extend existing methods for a single traffic matrix to solve the optimization problem with multiple traffic matrices. We show that it is NP-complete even to determine the feasibility of multiple traffic matrices. We thus propose and evaluate a heuristic algorithm for this case.

Fluid models have been shown to he efficient and accurate in modelling large IP networks. However, unlike packet models, it is difficult to extract packet-level information from them. In this paper, we present a hybrid simulation method that maintains the performance advantage of fluid models while providing detailed packet level information for selected packet traffic flows. We propose two models to account for the interaction between background TCP traffic in a fluid network and foreground packet traffic of interest. The first assumes that the packet traffic poses a negligible load on the fluid network whereas the second accounts for the added load by transforming the packet traffic into fluid flows and solving the resulting enhanced fluid model. The first of these yields an efficient one pass solution algorithm whereas the second requires an additional pass to account for the packet traffic load. We establish the correctness of both approaches and present their implementation within ns-2. Comparisons between the hybrid models and a classical packet simulation show the two pass approach to be quite accurate and computationally efficient.

This paper compares Reno, new-Reno and selective acknowledgements (SACK), the three most common TCP implementations today in (future) optical burst switched (OBS) networks. In general, SACK, which considers multiple triple duplicated ACKed (TD) losses in one round, is found to perform best in OBS networks, while new-Reno, which improves Reno in packet switched networks by fast retransmission in responding to partial ACKs, may however perform worse than Reno. All three TCP implementations react to a time out (TO) loss in the same way (i.e., using slow start). In OBS networks, where a burst may contain all packets from one round, and a burst loss occurs mainly due to contention instead of buffer overflow, such a TO event may no longer imply heavy congestion, or in other words, it may he a false TO or FTO. Such FTOs, which may he common in OBS networks especially for fast TCP flows, can significantly degrade the performance of all existing TCP implementations. Accordingly, we also propose a new TCP implementation called burst TCP (BTCP) which can detect FTOs and react properly, and as a result, improve over the existing TCP implementations significantly.

Routers handle data packets from sources unresponsive to TCP's congestion avoidance feedback. We are interested in the impact these sources have on active queue management (AQM) control of long-lived TCP traffic. In this paper, we combine models of TCP/AQM dynamics with models of unresponsive traffic to analyze the effects on AQM performance.

In this paper we present a scalable model of a network of Active Queue Management (AQM) routers serving a large population of TCP flows. We present efficient solution techniques that allow one to obtain the transient behavior of the average queue lengths, packet loss probabilities, and average end-to-end latencies. We model different versions of TCP as well as different versions of RED, the most popular AQM scheme currently in use. Comparisons between our models andns simulation show our models to be quite accurate while at the same time requiring substantially less time to solve, especially when workloads and bandwidths are high. Categories and Subject Descriptors