This paper presents an approach to alleviating the server-client communication bottleneck in collocated multi-user virtual reality (VR). Instead of transmitting unique packets to each client, the system multicasts the same packets to all users, combining packetization, visibility-aware prioritization, and lightweight acknowledgments to ensure efficiency and fairness. To enable rapid scene completion, the environment is partitioned into independent fixed-size packets that can be decoded immediately upon arrival, and transmission order is guided by precomputed visibility footprints. Scalability is achieved through repeated multicast until compact bitmap acknowledgments confirm reception, keeping communication cost mostly independent of the number of clients. A controlled study with 23 participants in groups of 7 and 16 showed that this method reconstructs environments several times faster and with fewer missing parts than a conventional unicast TCP-based approach. These findings demonstrate that multicast transmission over commodity Wi-Fi can support large collocated VR groups.

5G is much faster than 4G, offering faster data transfer and better user experience overall. Intuitively, 5G should be used as much as possible. However, in this study, we unveil a surprising finding in operational 5G networks: 5G radio access may be in a persistent ON-OFF loop which repeatedly turns 5G on and then off. We conduct extensive measurement experiments with three US operators (T-Mobile, AT&T, and Verizon) in two US cities to characterize and analyze 5G ON-OFF loop instances in the wild. Surprisingly, we find that such 5G ON-OFF loops are not rare. They are widely observed at many places, significantly hurting data performance (from several hundreds of Mbps to tens of or even zero Mbps). We further dive into their causes and uncover that inconsistent triggers to turn 5G on and off co-exist in real-world settings, repeatedly releasing 5G radio access after getting 5G back. We identify three loop types each with distinct triggering events/causes (sub-types). Inconsistent policies and mechanisms on both network and device sides, as well as ''improper'' use of certain frequency channels, are responsible for the loops observed in this study. Our datasets and artifacts have been released on Github and MI-LAB.

Video Conferencing Applications (VCAs) are widely used in education and remote work. Realistic modeling of VCAs, especially proprietary VCAs, enables simulation of VCA behaviors under network conditions that are different from those where the VCAs are deployed. Models of VCAs can be useful for both network operators and VCA developers who can assess how sensitive a VCA is to changes in the network. For instance, if VCA A begins to suffer video quality degradation when end-to-end delay exceeds 100 ms, while VCA B's corresponding threshold is 200 ms, operators can decide to give priority to A's traffic for better overall user experience. Additionally, modeling helps VCA designers select parameter values to navigate inherent performance trade-offs. If a model can quantify, for instance, how increasing a certain threshold to enhance video quality stability may increase frame latency, designers can make informed choices.

Internet service providers often fingerprint the type of application, e.g., video streaming or video conferencing, from a network traffic trace, for security and traffic engineering purposes. Several traffic classification methods have been proposed to apply machine learning techniques to packet timestamp and packet size information in traffic traces to perform such fingerprinting. However, classification accuracy drops when the machine learning methods are trained on traces that do not capture diverse end point and underlying network conditions. In this work, we compare a number of augmentation techniques that attempt to mitigate this problem, and evaluate their effectiveness when we systematically change specific end point and underlying network conditions. We find that the Rosetta traffic classification method that uses packet size sequences benefits much more from current augmentation methods than the mini-FlowPic method that uses both packet timestamps and sizes. We believe that there is a critical need for customized augmentations that enrich traffic traces, while being faithful to behaviors of real users and real protocols.1

Immersive virtual reality (VR) experiences require transmission and rendering of large-scale 3D content, often represented as point clouds or polygon meshes. Unfortunately, existing networked VR systems often fail to fully exploit the flexibility of VR data representations. To address this problem, we propose a cross-layer design that elevates a network data unit to a usable rendering unit for VR applications. Our aim is to bridge the gap between networks and applications in order to enhance visual quality, especially over constrained and variable networks. Our approach, Rendering Unit that is Network-aware (RUN), with two variants, RUN-Packet and RUN-Hybrid, includes mechanisms to effectively utilize network data units when encoding, transmitting, decoding, and rendering. Specifically, we develop additive detail refinement mechanisms and address streaming challenges such as head-of-line (HoL) blocking. We prototype our system in Unity 3D and evaluate it using synthetic network environments and real network traces. Our results with both static and dynamic point clouds demonstrate that RUN significantly reduces stalls and delivers smoother frame updates, enhancing visual quality.

The increasing popularity of video streaming and conferencing services have altered the nature of Internet traffic. In this paper, we take a first step toward quantifying the impact of this changing nature of traffic on the Quality of Experience (QoE) of popular video streaming and conferencing applications. We first analyze the traffic characteristics of these applications and of backbone links, and show how simple multipath routing may adversely impact application QoE. To mitigate this problem, we propose a new routing path selection approach, inspired by the TCP timeout computation algorithm, that uses both the average and variation of path load. Preliminary results show that this approach improves application QoE by on average 14% and packet latency by 11% for video streaming and conferencing applications, respectively.1

In this paper, we presentRoCC, a robust congestion control approach for datacenter networks based on RDMA.RoCCleverages switch queue size as an input to a PI controller, which computes the fair data rate of flows in the queue. The PI parameters are self-tuning to guarantee stability, rapid convergence, and fair and near-optimal throughput in a wide range of congestion scenarios. Our simulation and DPDK implementation results show thatRoCCcan achieve up to$7\times$reduction in PFC frames generated under high load levels, compared to DCQCN. At the same time,RoCCcan achieve$1.7 - 4.5\times$and$1.4 - 3.9\times$lower tail latency for long flows and$2.1-7\times$and$3.5-8.2\times$lower tail latency for short flows, compared to DCQCN and HPCC, respectively. We also find thatRoCCdoes not require PFC. The functional components ofRoCCcan be efficiently implemented in P4 and FPGA-based switch hardware.

This paper describes a method for reducing rendering load such that complex virtual environments (VEs) can be deployed on “thin” VR systems with limited rendering power. The method partitions the VE into four regions: a near region, an intermediate region, a stationary far region, and a dynamic far region. The stationary far region is replaced with an environment map, which brings a substantial rendering load reduction. The other three regions are rendered from geometry: the near region is rendered from the user viewpoint, the dynamic far geometry is rendered from the center of the environment map, and the intermediate region is rendered with a morph that switches viewpoint gradually from the user viewpoint to the center of the environment map. The intermediate region connects the near and far regions seamlessly. Furthermore, the environment map is enhanced with per pixel range which allows depth compositing the dynamic and stationary far geometry. An IRB approved user study (N = 22) found significant advantages for our method over conventional near-far partitioning.

We propose an optimization to reduce the latency incurred by a stateless 5G control plane. The key idea is to avoid redundant database read operations. We achieve this by reading the user’s state only once and sending it to successive network functions in a chain. Experimental results show that this optimization can reduce the total cost by 33% on average.

The adoption of a cloud-native architecture in 5G networks has facilitated rapid deployment and update of cellular services. An important part of this architecture is the implementation of 5G network functions statelessly. However, statelessness and its associated serialization and de-serialization of data and database interaction significantly increase latency. In this work, we take the first steps towards quantifying the cost of statelessness in a cloud-native 5G system. We compare the cost of different state management paradigms, and propose a number of optimizations to reduce this cost. Our preliminary results indicate that sharing user state among 5G functions reduces the overall cost by on an average of 10% in experiments with 100 to 1000 simultaneous requests. Optimizations such as non-blocking calls and custom database APIs also reduce cost, albeit to a lower extent. We believe that the paradigms proposed in this paper can aid operators and software vendors as they design cloud-native 5G networks.

Microservices enable rapid service deployment and scaling. Integrating poorly-understood microservice components into Service Function Chains (SFCs) or graphs limits a provider's control over service delivery latency, however. Orchestration frameworks currently instantiate and place myriads of microservice components without knowing the impact of placement decisions on latency.

We propose CoRE, a 360° video streaming approach that reduces bandwidth requirements compared to transferring the entire 360° video. CoRE uses non-linear sampling in both the spatial and temporal domains to achieve robustness to view direction prediction error and to transient wireless network bandwidth fluctuation. Each CoRE frame samples the environment in all directions, with full resolution over the predicted field of view and gradually decreasing resolution at the periphery, so that missing pixels are avoided, irrespective of the view prediction error magnitude. A CoRE video chunk has a main part at full frame rate, and an extension part at a gradually decreasing frame rate, which avoids stalls while waiting for a delayed transfer. We evaluate a prototype implementation of CoRE through trace-based experiments and a user study, and find that, compared to tiling with low-resolution padding, CoRE reduces data transfer amounts, stalls, and H.264 decoding overhead, increases frame rates, and eliminates missing pixels.

We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared with other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods.

In this paper, we present RoCC, a robust congestion control approach for datacenter networks based on RDMA. RoCC leverages switch queue size as an input to a PI controller, which computes the fair data rate of flows in the queue, signaling it to the flow sources. The PI parameters are self-tuning to guarantee stability, rapid convergence, and fair and near-optimal throughput in a wide range of congestion scenarios. Our simulation and DPDK implementation results show that RoCC can achieve up to 7× reduction in PFC frames generated under high average load levels, compared to DCQCN. At the same time, RoCC can achieve up to 8× lower tail latency, compared to DCQCN and HPCC. We also find that RoCC does not require PFC. The functional components of RoCC are implementable in P4-based and fixed-function switch ASICs.

Cellular service carriers often employ reactive strategies to assist customers who experience non-outage related individual service degradation issues (e.g., service performance degradations that do not impact customers at scale and are likely caused by network provisioning issues for individual devices). Customers need to contact customer care to request assistance before these issues are resolved. This paper presents our experience with PACE (ProActive customer CarE), a novel, proactive system that monitors, troubleshoots and resolves individual service issues, without having to rely on customers to first contact customer care for assistance. PACE seeks to improve customer experience and care operation efficiency by automatically detecting individual (non-outage related) service issues, prioritizing repair actions by predicting customers who are likely to contact care to report their issues, and proactively triggering actions to resolve these issues. We develop three machine learning-based prediction models, and implement a fully automated system that integrates these prediction models and takes resolution actions for individual customers. We conduct a large-scale trace-driven evaluation using real-world data collected from a major cellular carrier in the US, and demonstrate that PACE is able to predict customers who are likely to contact care due to non-outage related individual service issues with high accuracy. We further deploy PACE into this cellular carrier network. Our field trial results show that PACE is effective in proactively resolving non-outage related individual customer service issues, improving customer experience, and reducing the need for customers to report their service issues.

CoRE is an approach for streaming 360° videos based on a non-linear sampling of the equirectangular video cube. CoRE is robust to view prediction errors.

Caller-ID spoofing deceives the callee into believing a call is originating from another user. Spoofing has been strategically used in the now-pervasive telephone fraud, causing substantial monetary loss and sensitive data leakage. Unfortunately, caller-ID spoofing is feasible even when user authentication is in place. State-of-the-art solutions either exhibit high overhead or require extensive upgrades, and thus are unlikely to be deployed in the near future. In this paper, we seek an effective and efficient solution for 4G (and conceptually 5G) carrier networks to detect (and block) caller-ID spoofing. Specifically, we propose Nascent, Network-assisted caller ID authentication, to validate the caller-ID used during call setup which may not match the previously-authenticated ID. Nascent functionality is split between data-plane gateways and call control session functions. By leveraging existing communication interfaces between the two and authentication data already available at the gateways, Nascent only requires small, standard-compatible patches to the existing 4G infrastructure. We prototype and experimentally evaluate three variants of Nascent in traditional and Network Functions Virtualization (NFV) deployments. We demonstrate that Nascent significantly reduces overhead compared to the state-of-the-art, without sacrificing effectiveness.

Resource flexing is the notion of allocating resources on-demand as workload changes. This is a key advantage of Virtualized Network Functions (VNFs) over their non-virtualized counterparts. However, it is difficult to balance the timeliness and resource efficiency when making resource flexing decisions due to unpredictable workloads and complex VNF processing logic.

We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared to other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods.

The Ripple credit network has emerged as a payment backbone with key advantages for financial institutions and the remittance industry. Its path-based IOweYou (IOU) settlements across different (crypto)currencies conceptually distinguishes the Ripple blockchain from cryptocurrencies (such as Bitcoin and altcoins), and makes it highly suitable to an orthogonal yet vast set of applications in the remittance world for cross-border transactions and beyond. This work studies the structure and evolution of the Ripple network since its inception, and investigates its vulnerability to devilry attacks that affect the IOU credit of linnet users» wallets. We find that about 13M USD are at risk in the current Ripple network due to inappropriate configuration of the rippling flag on credit links, facilitating undesired redistribution of credit across those links. Although the Ripple network has grown around a few highly connected hub (gateway) wallets that constitute the core of the network and provide high liquidity to users, such a credit link distribution results in a user base of around 112,000 wallets that can be financially isolated by as few as 10 highly connected gateway wallets. Indeed, today about 4.9M USD cannot be withdrawn by their owners from the Ripple network due to PayRoutes, a gateway tagged as faulty by the Ripple community. Finally, we observe that stale exchange offers pose a real problem, and exchanges (market makers) have not always been vigilant about periodically updating their exchange offers according to current real-world exchange rates. For example, stale offers were used by 84 Ripple wallets to gain more than 4.5M USD from mid-July to mid-August 2017. Our findings should prompt the Ripple community to improve the health of the network by educating its users on increasing their connectivity, and by appropriately maintaining the credit limits, rippling flags, and exchange offers on their IOU credit links.

Instantiating a distributed application that involves extensive inter-node communication onto a network is a challenging task. In this work, we focus on the special case of mapping a network emulation experiment onto a cluster comprising several (possibly heterogeneous) physical machines. We automatically profile the available physical machine resources, and use this information, together with the characteristics of the experimental topology, to determine an efficient mapping that preserves performance fidelity. We design an algorithm, which we call the “Waterfall” algorithm, and integrate it into a complete framework for profiling and mapping. We demonstrate the effectiveness of our framework via simulations and two sets of Crossfire Distributed Denial of Service attack testbed experiments.

Sensor nodes are prone to failures due to their limited hardware capabilities, and software uncertainties stemming from erroneous logic or configuration. Such failures as well as wireless channel dynamics can degrade network performance, potentially creating network partitions. Existing troubleshooting tools either only diagnose a few problems or suffer from high overhead due to periodic transmission of control packets. In this paper, we propose Feluda, a system that exploits provenance, i.e., forwarding path of data packets, for automatic localization of problematic nodes and packets. Unlike existing methods, Feluda extracts necessary network performance metrics from packet headers and stores them into node flash storage, thereby reducing out-of-band packet transmissions. Once problematic nodes and corresponding packets are identified at the base station (BS), Feluda provides efficient querying mechanisms to retrieve packet headers of interest from specific nodes. Packet header analysis reveals the root cause of the problem. We implement Feluda using Java and ContikiOS on the BS and sensor nodes, respectively. Testbed experiments and COOJA simulations demonstrate the effectiveness of Feluda compared to the state-of the-art.

A smartphone application that displays a live view of road traffic can provide drivers with real-time information on traffic jams, flash floods or accidents along their planned routes. This information aids them in avoiding delays and uncertainties on the road, enhancing their navigation experience. Several US departments of transportation provide information from street cameras in the form of a snapshot of a particular location on a Google map. However, it is difficult for drivers to manually select cameras on the map to obtain consolidated information about road conditions along a particular route. In this paper, we design an energy-efficient mobile service that provides drivers with a convenient interface to observe live camera coverage along a route. Our proposed solution comprises an Android application and a cloud-based proxy service between smartphones and traffic cameras. The proxy provides an abstraction layer over different communication protocols adopted by traffic cameras, and transfers camera images for a specified route to the smartphone as a batch, thereby reducing communication overhead and improving user response time. By employing an in-memory cache, the proxy server maintains the most recently accessed camera images and reduces camera polling. We integrate our solution with traffic cameras from cities in Massachusetts, New York, and Washington DC, and demonstrate its reduced energy consumption and reduced response time.

Sensor nodes are inherently unreliable and prone to hardware or software faults. Thus, they may report untrustwor- thy or inconsistent data. Assessing the trustworthiness of sensor data items can allow reliable sensing or monitoring of physical phenomena. A provenance-based trust framework can evaluate the trustworthiness of data items and sensor nodes based on the intuition that two data items with similar data values but with different provenance (i.e., forwarding path) can be considered more trustworthy. Forwarding paths of data items generated from redundantly deployed sensors should consist of trustworthy nodes and remain dissimilar. Unfortunately, operating many sensors with dissimilar paths consumes significant energy. In this paper, we formulate an optimization problem to identify a set of sensor nodes and their corresponding paths toward the base station that achieve a certain trustworthiness threshold, while keeping the energy consumption of the network minimal. We prove the NP-hardness of this problem and propose ERUPT, a simulated annealing solution. Testbed and simulation results show that ERUPT achieves high trustworthiness, while reducing total energy consumption by 32-50% with respect to current approaches.

Accurate online network monitoring is crucial for detecting attacks, faults, and anomalies, and determining traffic properties across the network. With high bandwidth links and consequently increasing traffic volumes, it is difficult to collect and analyze detailed flow records in an online manner. Traditional solutions that decouple data collection from analysis resort to sampling and sketching to handle large monitoring traffic volumes. We propose a new system, Pegasus, to leverage commercially available co-located compute and storage devices near routers and switches. Pegasus adaptively manages data transfers between monitors and aggregators based on traffic patterns and user queries. We use Pegasus to detect global icebergs or global heavy-hitters. Icebergs are flows with a common property that contribute a significant fraction of network traffic. For example, DDoS attack detection is an iceberg detection problem with a common destination IP. Other applications include identification of “top talkers,” top destinations, and detection of worms and port scans. Experiments with Abilene traces, sFlow traces from an enterprise network, and deployment of Pegasus as a live monitoring service on PlanetLab show that our system is accurate and scales well with increasing traffic and number of monitors.

In this work, we propose techniques to attain visibility into an arbitrary Internet subnetwork that is responsive to indirect probes but not to direct probes. By probing the network from a small number of selected vantage points, we are able to collect information about network-layer topology which would otherwise be hidden from measurement due to rate limiting practices, security mechanisms, and routing dynamics. We investigate the reasons for differing visibility, and the required number and placement strategies of vantage points needed to collect topology information at a low cost. We demonstrate substantial improvement in global visibility as probed by the TraceNET path measurement tool when leveraging only five vantage points selected according to route similarity.

Rapid flooding is necessary for code updates and routing tree formation in wireless sensor networks. Link correlation-aware collective flooding (CF) is a recently proposed technique that provides a substrate for efficiently disseminating a single packet. Applying CF to multiple packet dissemination poses several challenges, such as reliability degradation, redundant transmissions, and increased contention among node transmissions. The varying link correlation observed in real networks makes the problem harder. In this paper, we propose a multi-packet flooding protocol, SYREN, that exploits the synergy among link correlation and network coding. In particular, SYREN exploits link correlation to eliminate the overhead of explicit control packets in networks with high correlation, and uses network coding to pipeline transmission of multiple packets via a novel, single yet scalable timer per node. SYREN reduces the number of redundant transmissions while achieving near-perfect reliability, especially in networks with low link correlation. Test bed experiments and simulations show that SYREN reduces the average number of transmissions by 30% and dissemination delay by more than 60% while achieving the same reliability as state-of-the-art protocols.

Internet Service Providers (ISPs) need to balance multiple opposing objectives. On one hand, they strive to offer innovative services to obtain competitive advantages; on the other, they have to interconnect with potentially competing ISPs to achieve reachability, and coordinate with them for certain services. The complexity of balancing these objectives is reflected in the diversity of policies of the Border Gateway Protocol (BGP), the standard inter-domain routing protocol. Unforeseen interactions among the BGP policies of different ISPs can cause routing anomalies. In this work, we propose a methodology to allow ISPs to check their BGP policy configurations for guaranteed convergence to a single stable state. This requires that a set of ISPs share their configurations with each other, or with a trusted third party. Compared to previous approaches to BGP safety, we (1) allow ISPs to use a richer set of policies, (2) do not modify the BGP protocol itself, and (3) detect not only instability, but also multiple stable states. Our methodology is based on the extension of current theoretical frameworks to relax their constraints and use incomplete data. We believe that this provides a rigorous foundation for the design and implementation of safety checking tools.

Internet Service Providers (ISPs) use routing policies to implement the requirements of business contracts, manage traffic, address security concerns and increase scalability of their network. These routing policies are often a high-level expression of strategies or intentions of the ISP. They have meaning when viewed from a network-wide perspective (e.g., mark on ingress, filter on egress). However, configuring these policies for the Border Gateway Protocol (BGP) is undertaken at a low-level, on a per router basis. Unintended routing outcomes have been observed. In this work, we define a language that allows analysis of network-wide configurations at the high-level. This language aims at bridging the gap between router configurations and abstract mathematical models capable of capturing complex policies. The language can be used to verify desired properties of routing protocols and hence detect potential unintended states of BGP. The language is accompanied by a tool suite that parses router configuration languages (which by their nature are vendor-dependent) and translates them into vendor-independent representations of policies.

Routing stability and correctness in the Internet have long been a concern. Despite this, few theoretical frameworks have been proposed to check BGP configurations for convergence and safety. The most popular approach is based on the Stable Paths Problem (SPP) model. Unfortunately, SPP requires enumeration of all possible control-plane paths, which is infeasible in large networks. In this work, we study how to apply algebraic frameworks to the BGP configuration checking problem. We propose an extension of the Stratified Shortest Path Problem (SSPP) model that has a similar expressive power to SPP, but enables more efficient checking of configuration correctness. Our approach remains valid when BGP policies are applied to iBGP sessions - a case which is often overlooked by previous work, although common in today's Internet. While this paper focuses mainly on iBGP problems, our methodology can be extended to eBGP if operators are willing to share their local-preference configurations.

Assessing the trustworthiness of sensor data and transmitters of this data is critical for quality assurance. Trust evaluation frameworks utilize data provenance along with the sensed data values to compute the trustworthiness of each data item. However, in a sizeable multi-hop sensor network, provenance information requires a large and variable number of bits in each packet, resulting in high energy dissipation due to the extended period of radio communication, and making trust systems unusable. We propose energy-efficient provenance encoding and construction schemes, which we refer to as Probabilistic Provenance Flow (PPF). To the best of our knowledge, ours is the first work to make the Probabilistic Packet Marking (PPM) approach for IP traceback feasible for sensor networks. We design two bit-efficient provenance encoding schemes along with a complementary vanilla scheme. Depending on the network size and bit budget, we select the best method using mathematical approximations and numerical analysis. Our TOSSIM simulations demonstrate that the encoding schemes of PPF have identical performance with a low bit budget (~ 32-bit), requiring 33% fewer packets and 30% less energy than PPM variants to construct provenance. With a two-fold increase in bit budget, PPF with the selected encoding scheme reduces the energy consumption by 60%1.

Correlated packet reception can be advantageous for sensor network broadcast protocols. By exploiting link correlation information, researchers have devised efficient single packet flooding protocols. In this work, we use testbed experiments to gain insight into the behavior of link correlation-aware broadcast protocols. We observe that, in the presence of varying link correlation, traditional link correlation-aware flooding mechanisms do not perform well in disseminating multiple packets due to reliability requirements and redundant transmissions. We conduct simulations to compare existing link correlation-aware flooding protocols with two versions of a multi-packet dissemination protocol, where one uses network coding and the other exploits both link correlation and network coding. Simulation results indicate the potential of the latter approach to be used as a reliable multi-packet dissemination protocol in practical scenarios. We also compare this protocol with existing multi-packet dissemination protocols, and reveal cases when certain protocols perform better than others.

Understanding the behavior of large-scale systems is challenging, but essential when designing new Internet protocols and applications. It is often infeasible or undesirable to conduct experiments directly on the Internet. Thus, simulation, emulation, and testbed experiments are important techniques for researchers to investigate large-scale systems. In this paper, we propose a platform-independent mechanism to partition a large network experiment into a set of small experiments that are sequentially executed. Each of the small experiments can be conducted on a given number of experimental nodes, e.g., the available machines on a testbed. Results from the small experiments approximate the results that would have been obtained from the original large experiment. We model the original experiment using a flow dependency graph. We partition this graph, after pruning uncongested links, to obtain a set of small experiments. We execute the small experiments in two iterations. In the second iteration, we model dependent partitions using information gathered about both the traffic and the network conditions during the first iteration. Experimental results from several simulation and testbed experiments demonstrate that our techniques approximate performance characteristics, even with closed-loop traffic and congested links. We expose the fundamental trade off between the simplicity of the partitioning and experimentation process, and the loss of experimental fidelity.

The Border Gateway Protocol (BGP), the de-facto Internet interdomain routing protocol, disseminates information about Internet prefixes to Autonomous Systems (ASes). Prefixes are announced and withdrawn as routes and policies change, making them unreachable from portions of the Internet for certain time periods. This paper aims to predict routing failures of prefixes in the Internet.We investigate the similarity of prefixes in the Internet with respect to their propensity to fail, i.e., become unreachable. Given a prefix of interest, we define a “BGP molecule” - the prefixes in the Internet that are likely to fail together with this prefix. We show that the AS paths to prefixes, coupled with knowledge of the prefix geographical location, contribute to its failure tendency. The BGP molecules constructed are used in four failure prediction schemes among which a hybrid scheme achieves 91% predictability of failures with 99.3% coverage of prefixes in the Internet.

Shared measurement services offer key advantages over conventional ad-hoc techniques for network monitoring. A measurement service may receive measurement requests concurrently from different applications and network administrators. These measurement requests are often served by injecting active network measurement traffic between two hosts. Two active measurements are said to interfere when the probe packets of one measurement tool are viewed as network traffic by the other. This may lead to faulty measurement readings. In this paper, we model the measurement interference problem, and show how to schedule measurement tasks to reduce interference and hence increase measurement accuracy. We propose twelve computationally tractable algorithms that decrease the total completion time (makespan) of measurement tasks, while avoiding interference. Our evaluation shows that the algorithm we refer to as Largest Area First, Busiest Node First - Earliest Interval Schedule (LAFBNF-EIS) has a mean makespan of about 5% more than the theoretical lower bound over our set of measurement workloads.

Large-scale sensor-based decision support systems are being widely deployed. Assessing the trustworthiness of sensor data and the owners of this data is critical for quality assurance of decision making in these systems. Trust evaluation frameworks use data provenance along with the sensed data values to compute the trustworthiness of each data item. However, in a sizeable multi-hop sensor network, provenance information requires a large and variable number of bits in each packet, which, in turn, results in high energy dissipation with extended period of radio communication, making trust systems unusable. We propose an energy-efficient provenance transmission and construction scheme, which we refer to as Probabilistic Provenance Flow (PPF). To the best of our knowledge, ours is the first approach to make the Probabilistic Packet Marking (PPM) approach of IP traceback feasible for sensor networks. We propose two bit-efficient complementary provenance encoding and construction methods, and combine them to handle topological changes in the network. Our TOSSIM simulations demonstrate that PPF requires at least 33% fewer packets and consumes 30% less energy than PPM-based approaches to construct provenance, yet still provides high accuracy in trust score calculation.1

A number of network path delay, loss, or bandwidth inference mechanisms have been proposed over the past decade. Concurrently, several network measurement services have been deployed over the Internet and intranets. We consider inference mechanisms that use O(n) end-to-end measurements to predict the O(n2) end-to-end pairwise measurements among n nodes, and investigate when it is beneficial to use them in measurement services. In particular, we address the following questions : 1) For which measurement request patterns would using an inference mechanism be advantageous? 2) How does a measurement service determine the set of hosts that should utilize inference mechanisms, as opposed to those that are better served using direct end-to-end measurements? We explore three solutions that identify groups of hosts which are likely to benefit from inference. We compare these solutions in terms of effectiveness and algorithmic complexity. Results with synthetic data sets and data sets from a popular peer-to-peer system demonstrate that our techniques accurately identify host subsets that benefit from inference, in significantly less time than an algorithm that identifies optimal subsets. The measurement savings are large when measurement request patterns exhibit small-world characteristics, which is often the case. (Part of this work (focusing on one of three solutions presented in this paper) appeared in).

Welcome to IEEE ICNP 2010, the Eighteenth International Conference on Network Protocols in Kyoto, Japan! Continuing the tradition of being the premier conferences on network protocols, we have an exciting program with papers, posters and a panel, representing the best of today's research. We are delighted to have two keynote speakers this year: Professor P. R. Kumar (University of Illinois at Urbana-Champaign, USA) and Dr. Shigeyuki Akiba (President and Chief Executive Officer, KDDI R&D Laboratories Inc., Japan).

The Border Gateway Protocol (BGP) maintains inter-domain routing information by announcing and withdrawing IP prefixes, possibly resulting in temporary prefix unreachability. Prefix availability observed from different vantage points in the Internet can be lower than standards promised by Service Level Agreements (SLAs). In this paper, we develop a framework for predicting long-term prefix availability, given short-duration prefix information from publicly available BGP routing databases. We compare three prediction models, and find that bagged decision trees perform the best when predicting for long future durations, whereas a simple model works well for short prediction durations. We show that mean time to failure and to recovery outperform past availability in terms of their importance for predicting availability for long durations. We also find that predictability is higher in the year 2009, compared to four years earlier. Our models allow ISPs to adjust BGP routing policies if predicted availability is low, and the models are useful for cloud computing systems, P2P, and VoIP applications.

Energy efficiency is critical for wireless sensor networks. The data-gathering process must be carefully designed to conserve energy and extend network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we first study the construction of a data-gathering tree when there is a single base station in the network. The objective is to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm that starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We then extend our work to the case when there are multiple base stations and study the construction of a maximum-lifetime data-gathering forest. We show that both the tree and forest construction algorithms terminate in polynomial time and are provably near optimal. We then verify the efficacy of our algorithms via numerical comparisons.

The reachability of IP address prefixes exhibits significant fluctuations due to changes in both physical connectivity and ISP routing policies. In the late 1990s, Labovitz et al. performed an extensive study of inter-domain path stability by analyzing BGP routing data. To reduce the noise in the BGP data, e.g., transient updates during route convergence, they applied several filters to preprocess the raw BGP data. In this work, we investigate prefix reachability as advertised by BGP, while revisiting the preprocessing filter design problem. We show that the reachability analysis results are highly sensitive to the specific filters applied and the parameters that control the strength of the filters. In particular, we compute the mean time to failure and recovery (MTTF and MTTR) as well as the up- to-downtime ratios of prefixes, and find that these can fluctuate by a factor of 10 by varying the filter parameters. We analyze the impact of recent fiber cuts in the Mediterranean sea and the Middle East, and study prefix reachability during a nine-month period in 2007 to evaluate the general health of the Internet.

A number of network path delay, loss, or bandwidth inference mechanisms have been proposed over the past decade. Concurrently, several network measurement services have been deployed over the Internet and intranets. We consider inference mechanisms that use O(n) end-to-end measurements to predict the O(n2) end-to-end pairwise measurements among n nodes, and investigate when it is beneficial to use them in measurement services. In particular, we address the following questions: (1) For which measurement request patterns would using an inference mechanism be advantageous? (2) How does a measurement service determine the set of hosts that should utilize inference mechanisms, as opposed to those that are better served using direct end-to-end measurements? (3) How can the answer to question 2 be efficiently computed as measurement requests arrive and terminate? Our solution is able to identify groups of hosts which are likely to benefit from inference, by utilizing a probabilistically generated spanning forest on the measurement request graph. We compare our solution to a simple heuristic that uses the number of measurements a host participates in. Results with synthetic datasets as well as datasets from a popular peer-to-peer system demonstrate that our technique identifies host subsets that benefit from inference quite accurately, and in significantly less time than an algorithm that identifies optimal subsets. The measurement savings are large when measurement request patterns exhibit small-world characteristics, which is often the case for peer-to-peer and other popular distributed systems.

Researchers in the denial-of-service (DoS) field lack accurate, quantitative, and versatile metrics to measure service denial in simulation and testbed experiments. Without such metrics, it is impossible to measure severity of various attacks, quantify success of proposed defenses, and compare their performance. Existing DoS metrics equate service denial with slow communication, low throughput, high resource utilization, and high loss rate. These metrics are not versatile because they fail to monitor all traffic parameters that signal service degradation. They are not quantitative because they fail to specify exact ranges of parameter values that correspond to good or poor service quality. Finally, they are not accurate since they were not proven to correspond to human perception of service denial. We propose several DoS impact metrics that measure the quality of service experienced by users during an attack. Our metrics are quantitative: they map QoS requirements for several applications into measurable traffic parameters with acceptable, scientifically determined thresholds. They are versatile: they apply to a wide range of attack scenarios, which we demonstrate via testbed experiments and simulations. We also prove metrics' accuracy through testing with human users.

Several popular simulation and emulation environments fail to account for realistic packet forwarding behaviors of commercial switches and routers. Such simulation or emulation inaccuracies can lead to dramatic and qualitative impacts on the results. In this paper, we present a measurement-based model for routers and other forwarding devices, which we use to simulate two different Cisco routers under varying traffic conditions. The structure of our model is device-independent, but requires device-specific parameters. We construct a profiling tool and use it to derive router parameter tables within a few hours. Our preliminary results indicate that our model can approximate the Cisco routers. The compactness of the parameter tables and simplicity of the model makes it possible to use it for high-fidelity simulations while preserving simulation scalability.

Energy efficiency is critical for wireless sensor networks. The data gathering process must be carefully designed to conserve energy and extend the network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we study the construction of a data gathering tree to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm which starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We show that the algorithm terminates in polynomial time and is provably near optimal.

We compare two representative streaming systems using mesh-based and multiple tree-based overlay routing through deployments on the PlanetLab wide-area experimentation platform. To the best of our knowledge, this is the first study to compare streaming overlay architectures in real Internet settings, considering not only intuitive aspects such as scalability and performance under churn, but also less studied factors such as bandwidth and latency heterogeneity of overlay participants. Overall, our study indicates that mesh-based systems are superior for nodes with high bandwidth capabilities and low round trip times, while multi-tree based systems currently cope better with stringent real time deadlines under heterogeneous conditions.

Serving multimedia content over the Internet with negligible delay remains a challenge. With the advent of Web 2.0, numerous video sharing sites using different storage and content delivery models have become popular. Yet, little is known about these models from a global perspective. Such an understanding is important for designing systems which can efficiently serve video content to users all over the world. In this paper, we analyze and compare the underlying distribution frameworks of three video sharing services - YouTube, Dailymotion and Metacafe - based on traces collected from measurements over a period of 23 days. We investigate the variation in service delay with the user's geographical location and with video characteristics such as age and popularity. We leverage multiple vantage points distributed around the globe to validate our observations. Our results represent some of the first measurements directed towards analyzing these recently popular services.

Abstract Time synchronization is essential for several ad‐hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a time synchronization framework for clustered, multi‐hop sensor networks. We assume that relative node synchronization is sufficient, that is, consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within two‐hops) and perform inter‐regional synchronization in O(LLSync) × Niter time, where O(LLSync) denotes the complexity of the underlying low‐level synchronization technique (used for single‐hop synchronization), and Niter denotes the number of iterations where the low‐level synchronization protocol is invoked. Thus, our main objective is rapid convergence. We propose novel fully distributed protocols, SYNC‐IN and SYNC‐NET, for regional and network synchronization, respectively, and prove that Niter is O(1) for all protocols. Our framework does not require any special node capabilities (e.g., being global positioning systems (GPS)‐enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter‐cluster routing, and low‐level synchronization protocols. We formulate a density model for analyzing inter‐regional synchronization, and evaluate our protocols via extensive simulations. Copyright © 2007 John Wiley & Sons, Ltd.

We study sleep/wake scheduling for low duty cycle sensor networks. Our work is different from prior work in that we explicitly consider the effect of synchronization error in the design of the sleep/wake scheduling algorithm. In our previous work, we have studied sleep/wake scheduling for single hop communications, e.g., intra-cluster communications between a cluster head and cluster members. We showed that the there is an inherent trade-off between energy consumption and message delivery performance (defined as the message capture probability). We proposed an optimal sleep/wake scheduling algorithm, which satisfies a message capture probability threshold (assumed to be given) with minimum energy consumption. In this work, we consider multi-hop communications. We remove the previous assumption that the capture probability threshold is already given, and study how to decide the per-hop capture probability thresholds to meet the quality of services (QoS) requirements of the application. In many sensor network applications, the QoS is decided by the amount of data delivered to the base station(s), i.e., the multi-hop delivery performance. We formulate an optimization problem, which aims to set the capture probability threshold at each hop such that the network lifetime is maximized, while the multi-hop delivery performance is guaranteed. The problem turns out to be non-convex and hard to solve exactly. By investigating the unique structure of the problem and using approximation techniques, we obtain a solution that achieves at least 0.73 of the optimal performance.

Denial-of-service (DoS) research community lacks accurate metrics to evaluate an attack's impact on network services, its severity and the effectiveness of a potential defense. We propose several DoS impact metrics that measure the quality of service experienced by end users during an attack, and compare these measurements to application-specific thresholds. Our metrics are ideal for testbed experimentation, since necessary traffic parameters are extracted from packet traces gathered during an experiment.

The central paradigm of today's successful Internet is to keep the network core simple and move complexity towards the network end points. Unfortunately, this very paradigm limits network management and control capabilities, and creates opportunities for attacks such as worms, viruses, and spam that often seriously disrupt and degrade Internet and user performance. The thrust of this paper is that such problems cannot be effectively solved unless a paradigm shift is adopted. Towards a more secure and manageable Internet, we propose "virtualization" of the Internet, by carefully balancing its scalability and programmability properties. Our objective is to provide a programmable virtual Internet to users and to let them manage, control, and optimize it based on their individual needs.

Internet distance prediction gives pair-wise latency information with limited measurements. Recent studies have revealed that the quality of existing prediction mechanisms from the application perspective is short of satisfactory. In this paper, we explore the root causes and remedies for this problem. Our experience with different landmark selection schemes shows that although selecting nearby landmarks can increase the prediction accuracy for short distances, it can cause the prediction accuracy for longer distances to degrade. Such uneven prediction quality significantly impacts application performance. Instead of trying to select the landmark nodes in some "intelligent" fashion, we propose a hierarchical prediction approach with straightforward landmark selection. Hierarchical prediction utilizes multiple coordinate sets at multiple distance scales, with the "right" scale being chosen for prediction each time. Experiments with Internet measurement datasets show that this hierarchical approach is extremely promising for increasing the accuracy of network distance prediction.

Distance prediction algorithms use O(N) round trip time (RTT) measurements to predict the N2RTTs among N nodes. Distance prediction can be applied to improve the performance of a wide variety of Internet applications: for instance, to guide the selection of a download server from multiple replicas, or to guide the construction of overlay networks or multicast trees. Although the accuracy of existing prediction algorithms has been extensively compared using the relative prediction error metric, their impact on applications has not been systematically studied. In this paper, we consider distance prediction algorithms from an application's perspective to answer the following questions: (1) Are existing prediction algorithms adequate for the applications? (2) Is there a significant performance difference between the different prediction algorithms, and which is the best from the application perspective? (3) How does the prediction error propagate to affect the user perceived application performance? (4) How can we address the fundamental limitation (i.e., inaccuracy) of distance prediction algorithms? We systematically experiment with three types of representative applications (overlay multicast, server selection, and overlay construction), three distance prediction algorithms (GNP, IDES, and the triangulated heuristic), and three real-world distance datasets (King, PlanetLab, and AMP). We find that, although using prediction can improve the performance of these applications, the achieved performance can be dramatically worse than the optimal case where the real distances are known. We formulate statistical models to explain this performance gap. In addition, we explore various techniques to improve the prediction accuracy and the performance of prediction-based applications. We find that selectively conducting a small number of measurements based on prediction-based screening is most effective.

We study sleep/wake scheduling for low-duty cycle sensor networks. Our work is different from previous work in that we explicitly consider the effect of the synchronization error. We study a widely used synchronization scheme and show that the synchronization error is non-negligible, and using a conservative guard time is energy wasteful. Hence, we formulate an optimization problem to minimize the expected energy consumption, with the constraint that the message capture probability should be no less than a threshold. We find that the problem is non-convex, hence cannot be solved by conventional convex optimization techniques. By investigating the unique structure of the problem, we transform the problem into a convex equivalent, and solve it using an efficient search method. Simulations show that our scheme significantly outperforms schemes that do not intelligently consider the synchronization error. We also remove the assumption that the capture probability threshold is given, and study how to decide it to meet the quality of services (QoS) requirements of the application

Distributed virtual environments such as massive multi-player games require multiple servers to balance computational load. This paper investigates the architecture of a unified environment where the virtual online world is not partitioned according to rigid boundaries, but according to an adaptive paradigm. Since it is difficult to develop an optimal load balancing algorithm for a unified environment, we propose an optimistic scheme that quickly converges. The cost of frequent migrations is reduced by following a push/push data exchange model. We analyze the computational time costs of such a system and give simulation results to gauge its performance. The simulation results confirm that our load balancing scheme is efficient and can support large numbers of clients.

A multitude of overlay network designs for resilient routing, multicasting, quality of service, content distribution, storage, and object location have been recently proposed. Overlay networks offer several attractive features, including ease of deployment, flexibility, adaptivity, and an infrastructure for collaboration among hosts. In this paper, we explore cooperation among co-existing, possibly heterogeneous, overlay networks. We design Synergy, a utility-based overlay internetworking architecture that fosters overlay cooperation. Our architecture promotes fair peering relationships to achieve synergism. Results from Internet experiments with cooperative forwarding overlays indicate that our Synergy prototype improves delay, throughput, and loss performance, while maintaining the autonomy and heterogeneity of individual overlay networks.

Several sensor network applications, such as environmental monitoring, require data aggregation to an observer. For this purpose, a data aggregation tree, rooted at the observer, is constructed in the network. Node clustering can be employed to further balance load among sensor nodes and prolong the network lifetime. In this paper, we design and implement a system, iHEED, in which node clustering is integrated with multi-hop routing for TinyOS. We consider simple data aggregation operators, such as AVG or MAX. We use a simple energy consumption model to keep track of the battery consumption of cluster heads and regular nodes. We perform experiments on a sensor network testbed to quantify the advantages of integrating hierarchical routing with data aggregation. Our results indicate that the network lifetime is prolonged by a factor of 2 to 4, and successful transmissions are almost doubled. Clustering plays a dominant role in delaying the first node death, while aggregation plays a dominant role in delaying the last node death

Abstract — Time synchronization is essential for several ad-hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a clusteringbased time synchronization framework for multi-hop sensor networks. We assume that relative node synchronization is sufficient, i.e., consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within 2-hops) and perform inter-regional synchronization in O(LLSync) × Niter time, where O(LLSync) denotes the complexity of the underlying low-level synchronization technique (used for single hop synchronization), and Niter denotes the number of iterations where the low-level synchronization protocol is invoked. We propose two novel fully-distributed protocols, SYNC-IN and SYNC-NET, for regional and network synchronization, respectively, and prove that Niter is O(1) for both protocols. We exploit the tradeoff between rapid convergence (and consequently energy-efficiency) and perceived accuracy. Our framework does not require any special node capabilities (e.g., being GPS-enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter-cluster routing, and low-level synchronization protocols. We formulate a density model for analyzing interregional synchronization, and evaluate our protocols via extensive simulations. Index Terms — Sensor networks, time synchronization, node clustering I.

Fair bandwidth allocation is critical in wireless communication networks, since the wireless channel is often shared by a number of stations in the same neighborhood. With fair scheduling, bandwidth can be shared by competing flows in proportion to their assigned weights. In this paper, we propose a credit-based distributed protocol for fair allocation of bandwidth in IEEE 802.11 wireless LANs. Our protocol is derived from the distributed coordination function in the IEEE 802.11 medium access control (MAC) protocol. Analytical and simulation results demonstrate that the protocol achieves the desired bandwidth allocations. An important feature of our protocol is its backward compatibility, which allows legacy IEEE 802.11 stations to coexist with stations adopting the new MAC protocol.

We design and implement an efficient on-line approach, FlowMate, for clustering flows (connections) emanating from a busy server, according to shared bottlenecks. Clusters can be periodically input to load balancing, congestion coordination, aggregation, admission control, or pricing modules. FlowMate uses in-band (passive) end-to-end delay measurements to infer shared bottlenecks. Delay information is piggybacked on feedback from the receivers, or, if impossible, TCP or application round-trip time estimates are used. We simulate FlowMate and examine the effects of network load, traffic burstiness, network buffer sizes, and packet drop policies on clustering correctness, evaluated via a novel accuracy metric. We find that coordinated congestion management techniques are more fair when integrated with FlowMate. We also implement FlowMate in the Linux kernel v2.4.17 and evaluate its performance on the Emulab testbed, using both synthetic and tcplib-generated traffic. Our results demonstrate that clustering of medium to long-lived flows is accurate, even with bursty background traffic. Finally, we validate our results on the Internet Planetlab testbed.

Prolonged network lifetime, scalability, and load balancing are important requirements for many ad-hoc sensor network applications. Clustering sensor nodes is an effective technique for achieving these goals. In this work, we propose a new energy-efficient approach for clustering nodes in ad-hoc sensor networks. Based on this approach, we present a protocol, HEED (hybrid energy-efficient distributed clustering), that periodically selects cluster heads according to a hybrid of their residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED does not make any assumptions about the distribution or density of nodes, or about node capabilities, e.g., location-awareness. The clustering process terminates in O(1) iterations, and does not depend on the network topology or size. The protocol incurs low overhead in terms of processing cycles and messages exchanged. It also achieves fairly uniform cluster head distribution across the network. A careful selection of the secondary clustering parameter can balance load among cluster heads. Our simulation results demonstrate that HEED outperforms weight-based clustering protocols in terms of several cluster characteristics. We also apply our approach to a simple application to demonstrate its effectiveness in prolonging the network lifetime and supporting data aggregation.

Clustering sensor nodes increases the scalability and energy efficiency of communications among them. In hostile environments, unexpected failures or attacks on cluster heads (through which communication takes place) may partition the network or degrade application performance. In this work, we propose a new approach, REED (Robust Energy Efficient Distributed clustering), for clustering sensors deployed in hostile environments. Our primary objective is to construct a k (i.e., k-connected) network, where k is a constant determined by the application. Fault tolerance can be achieved by selecting k independent sets of cluster heads (i.e., cluster head overlays) on top of the physical network, so that each node can quickly switch to other cluster heads in case of failures or attacks on its current cluster head. The independent cluster head overlays also provide multiple vertex-disjoint routing paths for load balancing and security. Network lifetime is prolonged by selecting cluster heads with high residual energy and low communication cost, and periodically reclustering the network in order to distribute energy consumption among sensor nodes. We prove that REED can asymptotically achieve k tolerance if certain constraints on node density are satisfied. We also investigate via simulations the clustering properties of REED, and show that building multiple cluster head overlays does not consume significant energy.

Topology control in a sensor network balances load on sensor nodes and increases network scalability and lifetime. Clustering sensor nodes is an effective topology control approach. We propose a novel distributed clustering approach for long-lived ad hoc sensor networks. Our proposed approach does not make any assumptions about the presence of infrastructure or about node capabilities, other than the availability of multiple power levels in sensor nodes. We present a protocol, HEED (Hybrid Energy-Efficient Distributed clustering), that periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED terminates in O(1) iterations, incurs low message overhead, and achieves fairly uniform cluster head distribution across the network. We prove that, with appropriate bounds on node density and intracluster and intercluster transmission ranges, HEED can asymptotically almost surely guarantee connectivity of clustered networks. Simulation results demonstrate that our proposed approach is effective in prolonging the network lifetime and supporting scalable data aggregation.

Overlay networks among cooperating hosts have recently emerged as a viable solution to several challenging problems, including multicasting, routing, content distribution, and peer-to-peer services. Application-level overlays, however, incur a performance penalty over router level solutions. This paper characterizes this performance penalty for overlay multicast trees via experimental data, simulations, and theoretical models. Experimental data and simulations illustrate that (i) the average delay and the number of hops between parent and child hosts in overlay trees generally decrease, and (ii) the degree of hosts generally decreases, as the level of the host in the overlay tree increases. Overlay multicast routing strategies, together with power-law and small-world Internet topology characteristics, are causes of the observed phenomena. We compare three overlay multicast protocols with respect to latency, bandwidth, router degrees, and host degrees. We also quantify the overlay tree cost. Results reveal that L(n)/U(n) /spl prop/ n/sub 0.9/ for small n, where L(n) is the total number of hops in all overlay links, U(n) is the average number of hops on the source to receiver unicast paths, and n is the number of members in the overlay multicast session.

TCP connection throughput is inversely proportional to the connection round trip time (RTT). To mitigate TCP bias to short RTT connections, a differentiated services traffic conditioner can ensure connections with long RTTs do not starve when connections with short RTTs get all extra resources after achieving the target rates. Current proposals for RTT-aware conditioners work well for a small number of connections when most TCP connections are in the congestion avoidance phase. If there is a large number of TCP connections, however, connections time-out and go to slow start. We show that current RTT-aware conditioners over-protect long RTT flows and starve short RTT flows in this case. We design and evaluate a conditioner based on RTT as well as the retransmission time-out (RTO). The proposed RTT-RTO aware traffic conditioner works well for realistic situations with a large number of connections. Simulation results in a variety of situations confirm that the conditioner mitigates RTT bias.

We investigate the effect of TCP explicit congestion notification (ECN) with a new response strategy that is more aggressive in the short term, but preserves TCP long term behavior, without modifying the router marking rate. A less aggressive ECN decrease gives more incentives for end systems to become ECN-compliant, as ECN serves as an early warning sign in this case. Our analysis and simulation results demonstrate the effectiveness of the new algorithm in improving throughput and reducing fluctuations. We model a multiple bottleneck scenario with various types of traffic, and evaluate the effect of a number of parameters, including TCP flavor, increase/decrease parameters, buffer size, and random early detection (RED) parameters.

We design an efficient on-line approach, FlowMate, for partitioning flows at a busy server into flow groups that share bottlenecks. These groups are periodically input to congestion coordination, aggregation, load balancing, admission control, or pricing modules. FlowMate uses in-band packet delay measurements to the receivers to determine shared bottlenecks among flows. Packet delay information is piggybacked on returning feedback, or, if impossible, flow (e.g., TCP) round trip time estimates are used. We simulate FlowMate to examine the effect of network load, traffic burstiness, network buffer sizes, and packet drop policies on partitioning correctness. Our results demonstrate accurate partitioning of medium to long-lived flows even under heavy load and self-similar background traffic. Experiments with HTTP/1.1 flows demonstrate difficulties in partitioning bursty foreground traffic. We also study fairness of coordinated congestion management when integrated with FlowMate.

We propose an application level multicast approach, Topology Aware Grouping (TAG), which exploits underlying network topology in-formation to build efficient overlay networks among multicast group members. TAG uses information about path overlap among mem-bers to construct a tree that reduces the overlay relative delay penalty, and reduces the number of duplicate copies of a packet on the same link. We study the properties of TAG, and model and experiment with its economies of scale factor to quantify its benefits compared to unicast and IP multicast. We also compare the TAG approach with the ESM approach in a variety of simulation configurations in-cluding a number of real Internet topologies and generated topolo-gies. Our results indicate the effectiveness of the algorithm in reducing delays and duplicate packets, with reasonable algorithm time and space complexities.

We design and evaluate an adaptive traffic conditioner to improve application performance over the differentiated services assured forwarding behavior. The conditioner is adaptive because the marking algorithm changes based upon the current number of flows traversing through an edge router. If there are a small number of flows, the conditioner maintains and uses state information to intelligently protect critical TCP packets. On the other hand, if there are many flows going through the edge router, the conditioner only uses flow characteristics as indicated in the TCP packet headers to mark without requiring per flow state. Simulation results indicate that this adaptive conditioner improves throughput of data extensive applications like large FTP transfers, and achieves low packet delays and response times for Telnet and WWW traffic.

This paper proposes an algorithm for aggregating virtual channel connections (VCCs) onto virtual path connections (VPSs) in asynchronous transfer mode (ATM) networks. We focus on the interesting problem of multiplexing onto an available bit rate (ABR) VPC. ABR VPCs are particularly useful for connecting enterprise sites over the Internet, providing a virtual private network (VPN). The VPC/VCC hierarchy is also important for supporting Internet differentiated services over ATM. The coupling between the flow control mechanisms for VCCs and VPCs is not standardized. We propose fairness definitions for VPC bandwidth allocation, and describe an algorithm for allocating the VPC capacity to the multiplexed VCCs. Preliminary simulation results indicate that the algorithm achieves the required fair allocations, while controlling queue sizes.

This paper describes the "explicit rate indication for congestion avoidance" (ERICA) scheme for rate-based feedback from asynchronous transfer mode (ATM) switches. In ERICA, the switches monitor their load on each link and determine a load factor, the available capacity, and the number of currently active virtual channels. This information is used to advise the sources about the rates at which they should transmit. The algorithm is designed to achieve high link utilization with low delays and fast transient response. It is also fair and robust to measurement errors caused by the variations in ABR demand and capacity. We present performance analysis of the scheme using both analytical arguments and simulation results. The scheme is being considered for implementation by several ATM switch manufacturers.

An explicit rate switch scheme monitors the load at each link and gives feedback to the sources. We define the overload factor as the ratio of the input rate to the available capacity. In this paper, we present three overload-based switch schemes which provide MCR (minimum cell rate) guarantees for the ATM (asynchronous transfer mode) ABR (available bit rate) service. The switch schemes proposed use the overload factor and other terms including current source rate and target utilization to calculate feedback rates. A dynamic queue control mechanism is used to achieve efficient usage of the link, control queues and, achieve constant queuing delay at steady state. The proposed algorithms are studied and compared using several configurations. The configurations were chosen to test the performance of the algorithms in the presence of link bottlenecks, source bottlenecks and transient sources. Finally, a comparison of the proposed algorithms based on the simulation results is given.

In a wireless environment, due to topology changes and characteristics of media (interference in radio signals) the bandwidth of a link is unpredictable and possibly very low, the error rates are variable and extremely high. Provisioning and guaranteeing quality of service (QoS) in such an environment is a very challenging problem. In this paper we propose an adaptive and QoS framework to support multimedia applications in a wireless networking environment. The proposed framework is hierarchical in nature with cluster of mobile end hosts connected to a base station, base stations are connected to a supervisory node, which in turn is connected to the wired infrastructure. The changing conditions in wireless due to interference and possibly mobility, entitle that the real-time applications needing stringent QoS should be adaptable. The framework uses a generic feedback mechanism to support adaptability at all layers of the wireless network. An overview of existing wireless architectures which support QoS is given. The architectures discussed are WAMIS (wireless adaptive multimedia information system), SWAN (seamless wireless ATM network), MMWN (multimedia support for mobile wireless networks), and QGMC (QoS guarantees in mobile computing). The proposed approach is compared with these existing methods.

The available bit rate (ABR) service is designed to fairly allocate the bandwidth unused by higher priority services. The network indicates to the ABR sources the rates at which they should transmit to minimize their cell loss. Switches must constantly measure the demand and available capacity, and divide the capacity fairly among the contending connections. In order to compute the fair and efficient allocation for each connection, a switch needs to determine the effective number of active connections. We propose a method for determining the number of active connections and the fair bandwidth share for each. We prove the efficiency and fairness of the proposed method analytically, and simulate it for a number of configurations.

The ABR rate allocation schemes can achieve high link utilizations by maintaining non-zero (small) queues in the steady state, and draining queues when the sources do not have data to send. The queue length (and queuing delays) can be controlled if part of the available bandwidth is used for draining queues in the event of queue build up. A simple threshold function can allocate such bandwidth to drain queues. Better control of the queues, and hence delay, can be achieved using more sophisticated queue control functions. We study the design and analysis of several such queue control functions: the step, linear, hyperbolic and inverse hyperbolic functions. Analytical explanation and simulation results consistent with analysis are presented. From the study, we conclude that the inverse hyperbolic is the best queue control function. To reduce complexity, the linear function can be used since it performs satisfactorily in most cases.

We give a general definition of weighted fairness and discuss how a pricing policy can be mapped to general weighted (GW) fairness. The GW fairness can be achieved by calculating the excess fairshare (weighted fairshare of the left over bandwidth) for each VC. We show how a switch algorithm can be modified to support the GW fairness by using the excess fairshare term. We use ERICA+ as an example switch algorithm and show how it can be modified to achieve the general fairness. Simulations results are presented to demonstrate that, the modified switch algorithm achieves GW fairness. An analytical proof for convergence of the modified ERICA+ algorithm is given in the appendix.

ABR traffic management for point-to-multipoint connections controls the source rate to be the minimum rate supported by all the branches of the multicast tree. A number of algorithms have been developed for extending ABR congestion avoidance algorithms to perform feedback consolidation at the branch points. This paper discusses various design options and implementation alternatives for the consolidation algorithms, and proposes a number of new algorithms. The performance of the proposed algorithms and the previous algorithms is compared under a variety of conditions. Results indicate that the algorithms we propose eliminate the consolidation noise (caused if the feedback is returned before all branches respond), while exhibiting a fast transient response.

The ATM guaranteed frame rate (GFR) service is intended for best effort traffic that can benefit from minimum throughput guarantees. Edge devices connecting LANs to an ATM network can use GFR to transport multiple TCP/IP connections over a single GFR VC. These devices would typically multiplex VCs into a single FIFO queue. It has been shown that in general, FIFO queuing is not sufficient to provide rate guarantees, and per-VC queuing with scheduling is needed. We show that under conditions of low buffer allocation, it is possible to control TCP rates with FIFO queuing and buffer management. We present analysis and simulation results on controlling TCP rates by buffer management. We present a buffer management policy that provides loose rate guarantees to SACK TCP sources when the total buffer allocation is low. We study the performance of this buffer management scheme by simulation.

Compressed video is well known to be self-similar in nature. We model VBR carrying long-range dependent, multiplexed MPEG-2 video sources traffic. The actual traffic for the model is generated using fast-Fourier transform of the fractional Gaussian noise sequence. Our model of compressed video sources bears similarity to an MPEG-2 transport stream carrying video, i.e., it is long-range dependent and generates traffic in a piecewise constant bit rate manner. We study, the effect of such VBR traffic on ABR carrying TCP traffic. The effect of such VBR traffic is that the ABR capacity is highly variant. We find that a switch algorithm like ERICA+ can tolerate this variance in ABR capacity while maintaining high throughput and low delay. We present simulation results for terrestrial and satellite configurations.

ATM-UBR service responds to congestion by dropping cells when switch buffers become full. TCP connections running over UBR experience low throughput and high unfairness. For 100% TCP throughput, each switch needs buffers equal to the sum of the window sizes of all the TCP connections. Intelligent drop policies can improve the performance of TCP over UBR with limited buffers. The UBR+ service proposes enhancements to UBR for intelligent drop. The early packet discard scheme improves throughput but does not attempt to improve fairness. The selective packet drop scheme based on per-connection buffer occupancy improves fairness. The fair buffer allocation scheme further improves both throughput and fairness.

We extend our earlier studies of buffer requirements of TCP over ABR in two directions. First, we study the performance of TCP over ABR in an ATM backbone. We find that the TCP queues are at the edge router and not inside the ATM network. The edge router requires buffering equal to the sum of the receiver window sizes of the participating TCP connections. Second, we study the performance when ABR capacity is variable due to the effect of various patterns of VBR background traffic. The key factors in this study are the VBR traffic pattern, ABR feedback delays and the sensitivity of the ABR switch scheme to variance. We present our experiences in refining the ERICA+ switch scheme to handle these conditions.

We study the performance of selective acknowledgements (SACK) with TCP over the ATM-UBR service category. We examine various unspecified bit rate (UBR) drop policies, TCP mechanisms and network configurations to recommend optimal parameters for TCP over UBR. We discuss various TCP congestion control mechanisms compare their performance for LANs and WANs. We describe the effect of satellite delays on TCP performance over UBR and present simulation results for LANs, WANs and satellite networks. SACK TCP improves the performance of TCP over UBR, especially for large delay networks. Intelligent drop policies at the switches are an important factor for good performance in local area networks.