Active Queue Management (AQM) algorithms have seen a lot of attention in recent academic literature as well as in the popular press. The problem with traditional AQM is that it is designed to operate on queues at the IP layer. However, the problem popularly called bufferbloat can move about among many queues some of which are resistant to traditional AQM such as Layer 2MAC protocols used in cable/DSL links. We call this problem bufferbloat displacement. Our contribution is a new class of AQM algorithm called Active Sense Queue Management (ASQM). ASQM is an IP layer AQM protocol that has the added benefit of managing Layer 2 link delay, i.e. bufferbloat displacement. We provide testbed experiments comparing ASQM's bandwidth delay characteristics with traditional AQM algorithms demonstrating ASQM's ability to manage bufferbloat displacement where traditional AQM algorithms cannot.

The IEEE 802.11n standard defines channel bonding that allows wireless devices to operate on 40 MHz channels by doubling their bandwidth from standard 20 MHz channels. Increasing channel width increases capacity, but it comes at the cost of decreased transmission range and greater susceptibility to interference. However, with the incorporation of Multiple-Input Multiple-Output (MIMO) technology in 802.11n, devices can now exploit the increased transmission rates from wider channels with minimal sacrifice to signal quality and range. The goal of our work is to identify the network factors that influence the performance of channel bonding in 802.11n networks and make intelligent channel bonding decisions. We discover that channel width selection should consider not only a link's signal quality, but also the strength of neighboring links, their physical rates, and interferer load. We use our findings to design and implement a network detector that successfully identifies interference conditions that affect channel bonding decisions in 100% of our test cases. Our detector can form the foundation for more robust and accurate algorithms that can adapt bandwidth to variations in channel conditions. Our findings allows us to predict the impact of network conditions on performance and make channel bonding decisions that maximize throughput.

Recommending news articles entails additional requirements to recommender systems. Such requirements include special consumption patterns, fluctuating itemcollections, and highly sparse user profiles. This workshop (NRS'[email protected]) brought together researchers and practitioners around the topics of designing and evaluating novel news recommender systems. Additionally, we offered a challenge allowing participants to evaluate their recommendation algorithms with actual user feedback.

The emergence of MIMO antennas and channel bonding in 802.11n wireless networks has resulted in a huge leap in capacity compared with legacy 802.11 systems. This leap, however, adds complexity to selecting the right transmission rate. Not only does the appropriate data rate need to be selected, but also the MIMO transmission technique (e.g., Spatial Diversity or Spatial Multiplexing), the number of streams, and the channel width. Incorporating these features into a rate adaptation (RA) solution requires a new set of rules to accurately evaluate channel conditions and select the appropriate transmission setting with minimal overhead. To address these challenges, we propose ARAMIS (Agile Rate Adaptation for MIMO Systems), a standard-compliant, closed-loop RA solution that jointly adapts rate and bandwidth. ARAMIS adapts transmission rates on a per-packet basis; we believe it is the first 802.11n RA algorithm that simultaneously adapts rate and channel width. We have implemented ARAMIS on Atheros-based devices and deployed it on our 15-node testbed. Our experiments show that ARAMIS accurately adapts to a wide variety of channel conditions with negligible overhead. Furthermore, ARAMIS outperforms existing RA algorithms in 802.11n environments with up to a 10 fold increase in throughput.

Streaming video over the Internet to wireless mobile devices has seen a tremendous increase in popularity amongst users. Recent improvements in infrastructure have made the delivery of video over wireless a reality. However, user demand for high definition video streams promises to quickly devour the bandwidth provided by these improvements. There has been extensive work to solve these problems. However, recent advancements at the application and transport layers have made possible the development of new methods that can improve throughput in existing HTTP/TCP infrastructure. In this paper we present a novel client driven application layer rate adaptation mechanism. Our solution can achieve significant throughput increases as compared to a standard rate adaptive HTTP/TCP video stream operating over a wireless link. In addition it operates with standard HTTP/TCP video servers and requires no in-network modifications or kernel changes at the client. We demonstrate the performance improvements of our proposed system through both emulation and deployment on a wireless mesh network in South Africa.

The IEEE 802.11n standard allows wireless devices to operate on 40MHz-width channels by doubling their channel width from standard 20MHz channels, a concept called channel bonding. Increasing channel width should increase bandwidth, but it comes at the cost of decreased transmission range and greater susceptibility to interference. However, with the incorporation of MIMO (Multiple-Input Multiple-Output) technology in 802.11n, devices can now exploit the increased transmission rates from wider channels at a reduced sacrifice to signal quality and range. The goal of our work is to understand the characteristics of channel bonding in 802.11n networks and the factors that influence that behavior to ultimately be able to predict behavior so that network performance is maximized. We discuss the impact of channel bonding choices as well as the effects of both co-channel and adjacent channel interference on network performance. We discover that intelligent channel bonding decisions rely not only on a link's signal quality, but also on the strength of neighboring links and their physical rates.

Online spectrum auctions offer ample flexibility for bidders to request and obtain spectrum on-the-fly. Such flexibility, however, opens up new vulnerabilities to bidder manipulation. Aside from rigging their bids, selfish bidders can falsely report their arrival time to game the system and obtain unfair advantage over others. Such time-based cheating is easy to perform yet produces severe damage to auction performance. We propose Topaz, a truthful online spectrum auction design that distributes spectrum efficiently while discouraging bidders from misreporting their bids or time report. Topaz makes three key contributions. First, Topaz applies a 3D bin packing mechanism to distribute spectrum across time, space and frequency, exploiting spatial and time reuse to improve allocation efficiency. Second, Topaz enforces truthfulness using a novel temporal-smoothed critical value based pricing. Capturing the temporal and spatial dependency among bidders who arrive subsequently, this pricing effectively diminishes gain from bid and/or time-cheating. Finally, Topaz offers a “scalable” winner preemption to address the uncertainty of future arrivals at each decision time, which significantly boosts auction revenue. We analytically prove Topaz's truthfulness, which does not require any knowledge of bidder behavior, or an optimal spectrum allocation to enforce truthfulness. Using empirical arrival and bidding models, we perform simulations to demonstrate the efficiency of Topaz. We show that proper winner preemption improves auction revenue by 45-65% at a minimum cost of spectrum utilization.

Abstract Monitoring and troubleshooting a large wireless mesh network (WMN) presents several challenges. Diagnosis of problems related to wireless access in these networks requires a comprehensive set of metrics and network monitoring data. Collection and offloading of a large amount of data are infeasible in a bandwidth constrained mesh network. Additionally, the processing required to analyze data from the entire network restricts the scalability of the system and impacts the ability to perform real‐time fault diagnosis. To this end, we propose MeshMon, a network monitoring framework that includes a multi‐tiered method of data collection. MeshMon, dynamically controls the granularity of data collection based on observed events in the network, thereby achieving significant bandwidth savings and enabling real‐time automated management. Our evaluation of MeshMon on a real testbed shows that we can diagnose a majority (87%) of network faults with a 66% savings in bandwidth required for network monitoring. Copyright © 2010 John Wiley & Sons, Ltd.

Online Social Networks (OSN) are fun, popular, and socially significant. An integral part of their success is the immense size of their global user base. To provide a consistent service to all users, Facebook, the world’s largest OSN, is heavily dependent on centralized U.S. data centers, which renders service outside of the U.S. sluggish and wasteful of Internet bandwidth. In this paper, we investigate the detailed causes of these two problems and identify mitigation opportunities. Because details of Facebook’s service remain proprietary, we treat the OSN as a black box and reverse engineer its operation from publicly available traces. We find that contrary to current wisdom, OSN state is amenable to partitioning and that its fine grained distribution and processing can significantly improve performance without loss in service consistency. Through simulations of reconstructed Facebook traffic over measured Internet paths, we show that user requests can be processed 79% faster and use 91% less bandwidth. We conclude that the partitioning of OSN state is an attractive scaling strategy for Facebook and other OSN services.

Satellite systems are ideal for distributing the same content to a large number of users, as well as providing broadband connectivity in remote areas or backup in case of terrestrial network failures. Unlike terrestrial networks, satellite networks face a unique set of challenges, such as signal fading and interference from multiple transmitters combined with long propagation delays. A well known challenge is that these unique characteristics can have an adverse impact on various protocols, making it necessary to study protocol behavior in satellite networks. The challenge of our research, and the focus of this paper, is to develop an architecture for a high-fidelity and scalable emulation testbed tailored for mobile satellite communications research. The testbed is designed to provide multi-beam, multi-satellite, TDMA, and mobility functionality. Our validation studies demonstrate that the testbed is capable of achieving delay, loss, and jitter that can be associated with a mobile satellite link.

Once, satellites were considered an important option for creating global Internet access. However, for a period of time, satellites were supplanted by other ground-based technologies. More recently, satellites have been proposed as an integral component in highly dynamic challenged environments where large numbers of mobile devices connect through satellite-based terminals. Routing within groups of mobile devices is performed by one of the myriad of wireless routing protocols, but over the space/ground link, BGP is the protocol of choice. In this work, we conduct a high fidelity experimental study of link intermittency on the space/ground link and its effect on BGP peering sessions between ground and satellite routers. Our results show that a routing architecture that does not correctly adapt to the particular characteristics of satellite links performs very poorly. By contrast, a correctly tuned routing architecture can survive prolonged outages intermixed with short periods of link connectivity.

Rate adaptation is a critical component that impacts the performance of IEEE 802.11 wireless networks. In congested networks, traditional rate adaptation algorithms have been shown to choose lower data-rates for packet transmissions, leading to reduced total network throughput and capacity. A primary reason for this behavior is the lack of real-time congestion measurement techniques that can assist in the identification of congestion-related packet losses in a wireless network. In this work, we first propose two real-time congestion measurement techniques, namely an active probe-based method called Channel Access Delay, and a passive method called Channel Busy Time. We evaluate the two techniques in a testbed network and a large WLAN connected to the Internet. We then present the design and evaluation of Wireless cOngestion Optimized Fallback (WOOF), a rate adaptation scheme that uses congestion measurement to identify congestion-related packet losses. Through simulation and testbed implementation we show that, compared to other well-known rate adaptation algorithms, WOOF achieves up to 300 percent throughput improvement in congested networks.

Wireless networks have evolved into an important technology for connecting users to the Internet. As the utility of wireless technology grows, wireless networks are being deployed in more widely varying conditions. The monitoring of wireless networks continues to reveal key implementation deficiencies that need to be corrected in order to improve protocol operation and end-to-end network performance. In wireless networks, where the medium is shared, unwanted traffic can pose significant overhead and lead to suboptimal network performance. Much of the previous analyses of unwanted traffic in wireless networks focus on malicious traffic. However, another major contributor of unwanted traffic is incorrect link layer behavior. Using data we collected from the 67th Internet Engineering Task Force (IETF) meeting held in November 2006, we show that a significant portion of link layer traffic stems from mechanisms that initiate, maintain, and change client-AP associations. We further show that under conditions of high medium utilization and packet loss rate, handoffs are initiated incorrectly. We analyze the traffic to understand when handoffs occur and whether the handoffs were beneficial or should have been avoided.

For many years, online criminals have been able to conduct their illicit activities by masquerading behind disreputable Internet service providers (ISPs). For example, organizations such as the Russian business network (RBN), Atrivo (a.k.a., Intercage), McColo, and most recently, the triple fiber network (3FN) operated with impunity, providing a safe haven for Internet criminals for their own financial gain. What primarily sets these ISPs apart from others is the significant longevity of the malicious activities on their networks and the apparent lack of action taken in response to abuse reports. Interestingly, even though the Internet provides a certain degree of anonymity, such ISPs fear public attention. Once exposed, rogue networks often cease their malicious activities quickly, or are de-peered (disconnected) by their upstream providers. As a result, the Internet criminals are forced to relocate their operations. In this paper, we present FIRE, a novel system to identify and expose organizations and ISPs that demonstrate persistent, malicious behavior. The goal is to isolate the networks that are consistently implicated in malicious activity from those that are victims of compromise. To this end, FIRE actively monitors Botnet communication channels, drive-by-download servers, and phishing Web sites. This data is refined and correlated to quantify the degree of malicious activity for individual organizations. We present our results in real-time via the Web site maliciousnetworks.org. These results can be used to pinpoint and to track the activity of rogue organizations, preventing criminals from establishing strongholds on the Internet. Also, the information can be compiled into a null-routing blacklist to immediately halt traffic from malicious networks.

The availability of Internet services brings many benefits to developing regions, yet Internet deployment levels in these regions remain staggeringly low. In this work we investigate how existing cellular deployments, which have enjoyed more rapid and wider deployment than client Internet infrastructure, could be used to provide very low cost Internet services in underdeveloped rural areas. We propose a new service model in which traffic is delivered over multihop client-to-client connections that are coordinated by end-to-end control traffic exchanged over cellular infrastructure. To enable this scheme in low client density rural settings, we propose a novel data forwarding mechanism for opportunistic space-time paths. To explore multiple opportunistic paths, but without the high forwarding cost of replicating data on these paths, we use network coding and send only a fraction of the data on each path. Through extensive OPNET simulations we show that globally coordinated opportunistic forwarding enables service acceptable to most applications at only a fraction of cellular infrastructure load. We argue that the reduced load on the cellular infrastructure allows additional users to share services and cost of the network and has the potential to lower the per user price of data services in developing regions.

A wired testbed's usefulness for wireless research hinges on its ability to faithfully reproduce the wireless medium. One of the key properties of a wireless medium is its broadcast nature. Wireless broadcast behavior is used in applications such as cell phone and satellite networks to disseminate the same data to multiple users as well as perform time synchronization. In this paper, we investigate two methods that can be used to ascertain if a given wireless emulator is modeling the broadcast property correctly. Our results indicate that the better of the two proposed methods offers micro-second precision.

Abstract The incredible growth in the capabilities and functionality of mobile devices has enabled new applications and network architectures to emerge. Due to the potential for node mobility, along with significant node heterogeneity, characteristics such as very large delays, intermittent links, and high link error rates pose a new set of network challenges. Along with these challenges, end‐to‐end paths are assumed not to exist and message relay approaches are often adopted. While message flooding is a simple and robust solution for such cases, its cost in terms of network resource consumption is unaffordable. In this paper, we focus on the evaluation of different controlled message flooding schemes over disconnected sparse mobile networks. We study the effect of these schemes on message delay, network resource consumption, and neighbor discovery overhead. Our simulations show that our schemes can save substantial network resources while incurring a negligible increase in the message delivery delay. Copyright © 2008 John Wiley & Sons, Ltd.

Traditional rate adaptation solutions for IEEE 802.11 wireless networks perform poorly in congested networks. Measurement studies show that congestion in a wireless network leads to the use of lower transmission data rates and thus reduces overall network throughput and capacity. The lack of techniques to reliably identify and characterize congestion in wireless networks has prevented development of rate adaptation solutions that incorporate congestion information in their decision framework. To this end, our main contributions in this paper are two-fold. First, we present a technique that identifies and measures congestion in an 802.11 network in real time. Second, we design Wireless congestion Optimized Fallback (WOOF), a measurement-driven rate adaptation scheme for 802.11 devices that uses the congestion measurement to identify congestion related packet losses. Through experimental evaluation, we show that WOOF achieves up to 300% higher throughput in congested networks, compared to other well-known adaptation algorithms.

A new generation of distributed systems and applications rely on the cooperation of diverse user populations motivated by self-interest. While they can utilize "reputation systems" to reduce selfish behaviors that disrupt or manipulate the network for personal gain, current reputations face a key challenge in large dynamic networks: vulnerability to peer collusion. In this paper, we propose to dramatically improve the accuracy of reputation systems with the use of a statistical metric that measures the "reliability" of a peer's reputation taking into account collusion-like behavior. Trace-driven simulations on P2P network traffic show that our reliability metric drastically improves system performance. We also apply our metric to 18,000 randomly selected eBay user reputation profiles, and surprisingly discover numerous users with collusion-like behaviors worthy of additional investigation.

Abstract Reputation mechanisms help peers in a peer‐to‐peer system avoid unreliable or malicious peers. In application‐level networks, however, short peer lifetimes mean reputations are often generated from a small number of past transactions. These reputation values are less ‘reliable’, and more vulnerable to bad‐mouthing or collusion attacks. We address this issue by introducing proactive reputations, a first‐hand history of transactions initiated to augment incomplete or short‐term reputation values. We present several mechanisms to generate proactive reputations, along with a statistical similarity metric to measure their effectiveness. Copyright © 2007 John Wiley & Sons, Ltd.

The eight papers in this special issue focus on delay and disruption tolerant wireless communication. The papers cover routing and network coding for spare mobile ad hoc networks, cross-layer design for sensor networks, satellite communication, and DTN architectural issues.

Integrating mobile computing and localized user interaction into the Internet requires more than simply overcoming pure routing challenges. Apart from issues such as intermittent connectivity and unreliable nodes, the human factor is becoming increasingly important. To date, user behavior has only been considered in terms of mobility patterns and incentives for encouraging cooperation. Moreover, the focus has always been on systems that aim to enforce fairness by either bringing an indirect equilibrium or by punishing "misbehaving" users. The goal of this paper is therefore to present Coupons. Coupons is an idea to define, evaluate, and implement algorithms for the emerging class of social network and information sharing applications. Coupons is a system designed to allow users to opportunistically interact and share data through a wireless medium, to overcome highly variable Internet access through adaptive localized interaction, and to incorporate an incentive scheme to make the system usable and encourage participation.

When new wireless technologies are deployed and subjected to real usage patterns, unforeseen performance problems inevitably seem to arise, to be fixed only in later generations. Why do these performance issues fail to appear in experimental settings before the technology is deployed? We believe that one of the major reasons behind the discrepancies found between experimental performance evaluations and real-world experience lies in the unrealistic workload patterns typically used in experiments. One of the significant contributions of this work is to rigorously demonstrate that common synthetic traffic models for wireless local-area networks induce drastically distorted performance metrics at every layer of the protocol stack. In order to show this, we present a testable definition of “sufficient realism” for traffic models, and develop the theoretical methodology necessary to interpret experimental results using this definition. Finally, we show by example that this distortion can completely invert the relative performance of protocols. The greater overall contribution of this paper, however, is the complete collection of ideas, techniques and analytical tools that will allow the development of more realistic synthetic traffic models in the future.

The rapid growth in the popularity of cellular networks has led to aggressive deployment and a rapid expansion of mobile services. Services based on the integration of cellular networks into the Internet have only recently become available, but are expected to become very popular. One current limitation to the deployment of many of these services is poor or unknown network performance, particularly in the cellular portion of the network. Our goal in this paper is to motivate and present the Mobile Internet Services Test (MIST) platform, a new distributed architecture to measure and characterize cellular network performance as experienced by mobile devices. We have used MIST to conduct preliminary measurements; evaluate MIST’s effectiveness; and motivate further measurement research.

As the utility of wireless technology grows, wireless networks are being deployed in more widely varying conditions. The monitoring of these networks continues to reveal key implementation deficiencies that need to be corrected in order to improve protocol operation and end-to-end performance. Using data we collected from the 67th Internet Engineering Task Force (IETF) meeting held in November 2006, we show that under conditions of high medium utilization and packet loss, handoffs can be incorrectly initiated. Using the notion of persistence and prevalence for the association of a client to an Access Point (AP), we show that although the clients were predominantly static, the handoff rate is surprisingly high. Through the analysis of the data set, we show that unnecessary handoff events not only increase the amount of management traffic in the network, but also severely impact client performance.

Over the last decade, several value-added services have been proposed for deployment in the Internet. IP multicast is an example of such a service. IP multicast is a stateful service in that it requires routers to maintain state for forwarding multicast data toward receivers. This characteristic makes the service and its users vulnerable to denial-of-service (DoS) attacks. One type of attack aims to saturate the available buffer space for storing state information at the routers. A successful attack can prevent end systems from properly joining multicast groups. In this paper, we present a solution to state overload attacks; evaluate the overhead of the solution through a combination of simulation and implementation; and outline an incremental deployment strategy for its partial deployment. The evaluation results indicate that our solution improves the resistance of IP multicast to state overload attacks.

The capacity problem in wireless mesh networks can be alleviated by equipping the mesh routers with multiple radios tuned to non-overlapping channels. However, channel assignment presents a challenge because co-located wireless networks are likely to be tuned to the same channels. The resulting increase in interference can adversely affect performance. This paper presents an interference-aware channel assignment algorithm and protocol for multi-radio wireless mesh networks that address this interference problem. The proposed solution intelligently assigns channels to radios to minimize interference within the mesh network and between the mesh network and co-located wireless networks. It utilizes a novel interference estimation technique implemented at each mesh router. An extension to the conflict graph model, the multi-radio conflict graph, is used to model the interference between the routers. We demonstrate our solution’s practicality through the evaluation of a prototype implementation in a IEEE 802.11 testbed. We also report on an extensive evaluation via simulations. In a sample multi-radio scenario, our solution yields performance gains in excess of 40% compared to a static assignment of channels.

Flash crowds and high concentrations of users in wireless LANs (WLANs) cause significant interference problems and unsustainable load at access points. This leads to poor connectivity for users, severe performance degradation, and possible WLAN collapse. To validate this claim, we present two case studies of large, heavily loaded operational WLANs. These studies provide significant insight into the degraded performance and collapse of a WLAN during heavy use. To address these problems, we propose IQU, a practical queue-based user association management system for heavily loaded WLANs. IQU grants users fair opportunities to access the WLAN while maintaining high overall throughput, even when the WLAN is heavily loaded. The basic premise of IQU is to control user associations with the WLAN through request queues and work period allocations. We implement a prototype of IQU and evaluate it on a wireless testbed. Our evaluation demonstrates that IQU significantly improves network throughput under heavy load; the tradeoff is that users have to wait for network access. We explore the impact of IQU parameters on system performance, and validate the robustness of IQU under heavy load conditions. Through IQU, WLANs can be utilized efficiently and network collapse prevented.

As mobile and wireless technologies become more pervasive in our society, people begin to depend on network connectivity regardless of their location. Their mobility, however, implies a dynamic topology where routes to a destination cannot always be guaranteed. The intermittent connectivity, which results from this lack of end-to-end connection, is a dominant problem that leads to user frustration. Existing research to provide the mobile user with a mirage of constant connectivity generally presents mechanisms to handle disconnections when they occur. In contrast, the system we propose in this paper provides ways to handle disconnections before they occur. We present a data bundling system for intermittent connections (DBS-IC) comprised of a stationary agent (SA) and a mobile agent (MA). The SA proactively gathers data the user has previously specified, and opportunistically sends this data to the MA. The SA groups the user-requested data into one or more data bundles, which are then incrementally delivered to the MA during short periods of connectivity. We fully implement DBS-IC and evaluate its performance via live tests under varying network conditions. Results show that our system decreases data retrieval time by a factor of two in the average case and by a factor of 20 in the best case

The evolution of wireless devices along with the increase in user mobility have created new challenges such as network partitioning and intermittent connectivity. These new challenges have become apparent in many situations where the transmission of critical data is of high priority. Disaster rescue groups, for example, are equipped with numerous devices which constantly gather and transmit various forms of data. The challenge of establishing communication between groups of this type has led to an evolutionary form of networks which we consider in this paper, namely, delay tolerant mobile networks (DTMNs). Nodes in DTMNs usually form clusters that we define as regions. Nodes within each region have end-to-end paths between them. Both regions, as well as nodes within a region, can be either stationary or mobile. For such environments, we propose using a dedicated set of messengers that relay message bundles between these regions. Our goal is to understand how messenger scheduling can be used to improve network performance and connectedness. We develop several classes of messenger scheduling algorithms which can be used to achieve inter-regional communication in such environments. We use simulation to better understand the performance and tradeoffs between these algorithms

Multicast is a key service for many audio and video applications, yet it continues to be a challenging Internet service to deploy. While much attention has been given to a number of problems associated with multicast, two closely related problems in particular have received almost no attention. First, there is essentially no host support for dealing with the variety of ways to join a multicast group, and second, there is a complete absence of group join success or failure feedback from the network. The lack of a straightforward way to robustly join a multicast group and then to know whether the join has been successful is possibly the biggest limitation for multicast application developers today. In this study we develop a robust solution to determine the existence and nature of multicast service in the network. We consider two options: (1) the use of existing protocol features to extract the required information, and (2) the introduction of new protocol extensions to directly query the network. Our results indicate that while a truly robust group join is possible only when there is network support, these additional changes are difficult to deploy. Our evaluation implements a proof-of-concept prototype to determine the existence and nature of the multicast service in the network.

Constructing indoor radio maps plays an important role in many services and applications, such as wireless base station planning. We propose a hybrid approach to constructing indoor radio maps by developing a novel indoor signal propagation model, called the hidden environment model (HEM). The model is hybrid because it combines on-site measurements with a number of different types of calculations. As part of this model, we introduce the idea of an environment factor matrix (EFM). The EFM represents a model of the environmental features that affect radio attenuation. We also develop a lazy sampling algorithm to help generate the EFM. The goal of the lazy sampling algorithm is to balance the number of measurements that need to be taken with our model's accuracy. The goal is to minimize the measurement workload while maintaining satisfactory accuracy. We evaluate our model by comparing the radio maps calculated from the model to a radio map obtained by exhaustive measurements. The results show that our hidden environment model achieves good accuracy.

The Internet has evolved from a wired infrastructure to a hybrid of wired and wireless domains. As network access is now provided with much of the last mile being a wireless mobile environment, delivering rich multimedia to users is now a necessity. However, despite the advent of new technology and standards such as Mobile Internet protocol version 6 (MIPv6), there is still an important dilemma over the choice of systems that either achieve high levels of performance or offer easier deployment. The very deployment of IPv6 is delayed for this reason; network providers continue to use legacy systems. The goal of this paper then is to offer insight into this issue by examining the case of data streaming to MIPv6 users through the use of multicast. By specifically considering the debate over network and application layer multicast, we examine a spectrum of possible alternatives and evaluate the potential of enhancing the functionality of access routers. The result is an overlay architecture that can bring the desired balance between deployment complexity and performance.

Simulation environments are an important tool for the evaluation of new concepts in networking. The study of mobile ad hoc networks depends on understanding protocols from simulations, before these protocols are implemented in a real-world setting. To produce a real-world environment within which an ad hoc network can be formed among a set of nodes, there is a need for the development of realistic, generic and comprehensive mobility, and signal propagation models. In this paper, we propose the design of a mobility and signal propagation model that can be used in simulations to produce realistic network scenarios. Our model allows the placement of obstacles that restrict movement and signal propagation. Movement paths are constructed as Voronoi tessellations with the corner points of these obstacles as Voronoi sites. Our mobility model also introduces a signal propagation model that emulates properties of fading in the presence of obstacles. As a result, we have developed a complete environment in which network protocols can be studied on the basis of numerous performance metrics. Through simulation, we show that the proposed mobility model has a significant impact on network performance, especially when compared with other mobility models. In addition, we also observe that the performance of ad hoc network protocols is effected when different mobility scenarios are utilized.

Integrating ad hoc networks into the Internet requires a number of difficult technical challenges to be overcome. In particular, ad hoc networks must not only overcome intermittent connectivity, but they also need a strong incentive mechanism to encourage users to participate in the cooperative relay of data traffic. We believe that inherent in solving these problems is the development of new applications that might, in fact, be more easily deployed in an ad hoc environment than in a traditional fixed network infrastructure. To this end, we develop and evaluate the idea of "coupons" for wide-scale information distribution in ad hoc networks. "Coupons" provide a simple incentive to nodes for relaying a piece of information. By using mechanisms on top of basic flooding to control distribution efficiently, the concept provides an elegant solution for scalable data dissemination with reduced network costs.

Networks of small devices, such as environmental sensors, introduce a number of new challenges for traditional protocols and approaches. In particular, the extreme resource constraints characteristics of these devices force the engineering of device and application-specific optimizations in order to reduce complexity. By offloading some, if not most, of the complexity out of the small device and into the network, we simplify the design of individual devices, and may make otherwise infeasible applications possible. We look specifically at the problem of global mobility, and its associated protocol Mobile IP (MIP). We introduce the mobility gateway which performs MIP processing on behalf of registered devices. The mobility gateway provides an interface between the optimized world of small devices and the larger Internet. Through simulation, we investigate the potential savings offered by this technique in terms of bandwidth and power. In a sample scenario, we find the total number of bytes transmitted over the wireless channel reduced by as much as 70%, and the battery life of the device extended by more than 100 hours.

With the advent of small form-factor devices, protocol standardization, and robust protocol implementations, multi-hop mobile networks are witnessing widespread deployment. The monitoring of such networks is crucial for their robust operation. To this end, this paper presents DAMON, a distributed system for monitoring multi-hop mobile networks. DAMON uses agents within the network to monitor network behavior and send collected measurements to data repositories. DAMON's generic architecture supports the monitoring of a wide range of protocol, device, and network parameters. Other key features of DAMON include seamless support for multiple repositories, auto-discovery of sinks by the agents, and resiliency of agents to repository failures. We have implemented DAMON agents that collect statistics on data traffic and the ad hoc on-demand distance vector (AODV) routing protocol. We have used our implementation to monitor an ad hoc network at the 58th Internet Engineering Task Force (IETF) meeting held November 2003 in Minneapolis, MN. In this paper, we describe the architecture of DAMON and report on the performance of the IETF network using monitoring information collected by DAMON. Our network monitoring system is available online for use by other researchers.

The successful deployment of multicast in the Internet requires the availability of good network management solutions. Discovering multicast tree topologies is an important component of this task. Network managers can use topology information to monitor and debug potential multicast forwarding problems. In addition, the collected topology has several other uses, for example, in reliable multicast transport protocols, in multicast congestion control protocols, and in discovering network characteristics. We present a mechanism for discovering multicast tree topologies using the forwarding state in the network. We call our approach tracetree. First, we present the basic operation of tracetree. Then, we explore various issues related to its functionality (e.g., scalability, security, etc.). Next, we provide a detailed evaluation by comparing it to the currently available alternatives. Finally, we discuss a number of deployment issues. We believe that tracetree provides an efficient and scalable mechanism for discovering multicast tree topologies and therefore fills an important void in the area of multicast network management.

Source specific multicast (SSM) provides native support for single sender multicast applications. Current proposals for supporting multiple sender applications on top of SSM includes using multiple SSM channels or using an application layer relay mechanism on top of SSM. These approaches have potential scalability or single point of failure problems, respectively. In this paper, we propose network layer extensions to SSM. Our extensions provide a convenient mechanism for SSM group owners to include additional senders in their multicast applications. We present our SSM extensions model and provide a detailed discussion on the protocol operation under various scenarios. We also examine the protocol performance by comparing it to alternative approaches on several performance metrics. With SSM Extensions, we introduce a small number of changes into the existing infrastructure and in return, provide an effective and efficient mechanism to support multiple-sender applications on top of SSM.

As the multicast-capable part of the Internet continues to evolve, important questions to ask are whether the protocols are operating correctly, the topology is well connected, and the routes are stable. A critical step in being able to answer these questions is to monitor the traffic and network operation. In this paper, we analyze characteristics of the multicast infrastructure over the last three years using monitoring data collected from several key routers. Specifically, we focus on analyzing two characteristics of the infrastructure: size and stability. The size analysis focuses on counting the number of connected hosts and networks, and analyzing how the size of the infrastructure has changed over past three years. Second, the stability analysis focuses on examining persistence, prevalence, and visibility of routes across the topology. From our analyses, we identify a number of problems with multicast routing and their effect on the connectivity of certain multicast networks. Moreover, we offer insight into the evolution and future of multicast in the Internet.

One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with a number of significant benefits, including repeatable scenarios, isolation of parameters, and exploration of a variety of metrics. The topology and movement of the nodes in the simulation are key factors in the performance of the network protocol under study. Once the nodes have been initially distributed, the mobility model dictates the movement of the nodes within the network. Because the mobility of the nodes directly impacts the performance of the protocols, simulation results obtained with unrealistic movement models may not correctly reflect the true performance of the protocols. The majority of existing mobility models for ad hoc networks do not provide realistic movement scenarios; they are limited to random walk models without any obstacles. In this paper, we propose to create more realistic movement models through the incorporation of obstacles. These obstacles are utilized to both restrict node movement as well as wireless transmissions. In addition to the inclusion of obstacles, we construct movement paths using the Voronoi diagram of obstacle vertices. Nodes can then be randomly distributed across the paths, and can use shortest path route computations to destinations at randomly chosen obstacles. Simulation results show that the use of obstacles and pathways has a significant impact on the performance of ad hoc network protocols.

In this paper we compare Network (IP multicast) and Application Layer Multicast (ALM) under a specific assumption: end hosts are wireless devices using the Mobile IPv6 (MIPv6) protocol. This comparison has three main goals. First, we analyze the implications of running multicast in a mobile, wireless network using Mobile IPv6 (MIPv6). Second, we run a number of simulations to verify whether the network performance issues are different than in wired networks. Finally, using these results, we try to identify the factors that have the most significant impact on performance. Our results indicate that although ALM can be designed to work on top of a wireless network running MIPv6, there are a number of additional performance penalties beyond what occurs in wired networks. Essentially, the advantage of using IP multicast grows even stronger in mobile networks. Nevertheless, we recognize that there are significant barriers to ubiquitous network layer multicast and therefore believe that a more hybrid approach combining both IP multicast and ALM would offer the best performance.

The benefit derived from using multicast is seemingly dependent upon the shape of the distribution tree. We attempt to model interdomain multicast trees accurately. We measure a number of key parameters, such as depth, degree frequency, and average degree, for a number of real and synthetic data sets. We find that interdomain multicast trees actually do share a common shape at both the router and autonomous system levels. Furthermore, we develop a characterization of multicast efficiency which reveals that group sizes as small as 20 to 40 receivers offer a 55%-70% reduction in the total number of links traversed when compared to separately delivered unicast streams. A final contribution of our work consists in a number of data sets, compiled from multicast group membership and path data, that can be used to generate large sample trees, representative of the current multicast infrastructure.

There exists a huge demand for multimedia goods and services in the Internet. Currently available bandwidth speeds can support sale of downloadable content like CDs, e-books, etc. as well as services like video-on-demand. In the future, such services will be prevalent in the Internet. Since costs are typically fixed, maximizing revenue can maximize profits. A primary determinant of revenue in such econtent markets is how much value the customers associate with the content. Though marketing surveys are useful, they cannot adapt to the dynamic nature of the Internet market. In this work, we examine how to learn customer valuations in close to real-time. Our contributions in this paper are threefold: (1) we develop a probabilistic model to describe customer behavior, (2) we develop a framework for pricing e-content based on basic economic principles, and (3) we propose a price discovering algorithm that learns customer behavior parameters and suggests prices to an e-content provider. We validate our algorithm using simulations. Our simulations indicate that our algorithm generates revenue close to the maximum expectation. Further, they also indicate that the algorithm is robust to transient customer behavior. 1.

Peer-to-peer (P2P) content exchange has recently gained attention from both the research and industrial communities. The dynamic nature of peer networks and the resource constraints of peer hosts have introduced a number of unique technical challenges that must be addressed to make large-scale P2P content exchange applications viable. In this work, we present and evaluate Pixie, an architecture that integrates one-to-many distribution of content and peer networks. Pixie provides a valuable data location service as well as a number of scalability properties both in terms of data location and content distribution. Our results indicate that, using a one-to-many scheme, we can significantly reduce the resources consumed in searching for and distributing content across peer networks. These scalability properties will become increasingly important as peer content exchange is extended to support more advanced applications.

Content delivery has become an important enterprise on the Internet. There exists a huge demand for bandwidth-intensive, rich multimedia content like news, entertainment services and software. Two key issues associated with any content-delivery system are: revenue and user satisfaction. We explore the domain of pricing for content delivery, and how it relates to revenue, and system utilization. A fundamental contribution of this paper is to consider a probabilistic user behavior model where users can refuse the offered service based on their capacity to pay and the price quoted. As a first step, we consider a system which delivers multimedia content on a first-come-first-served basis, and analyze pricing mechanisms which maximize the expectation of revenue. We argue that charging a constant price based on the customers' capacities to pay maximizes the expected revenue. Since the customers' capacities are highly varying and not known beforehand, we develop an adaptive pricing model and validate it using simulation. Our simulation results indicate that the adaptive pricing scheme generates nearly the same revenue as the theoretical expectation.

Multicast is a promising technique for mass distribution of streaming media. However, the inherent heterogeneity of the Internet poses several challenges. A major challenge is to develop a congestion control mechanism that is efficient, flexible (to administrative heterogeneity) and deployable. Many approaches using a layered encoding scheme have been proposed to address this problem. In parallel, many tools are being developed which provide a snapshot of network internals. Of particular interest are multicast topology discovery tools. The existence of such tools motivates the possibility of using tree topology information for multicast congestion control. In this paper we seek to understand the benefits of such a mechanism and the challenges in its practical implementation. We develop an algorithm, called TopoSense, which uses topology information and layered streams to control congestion within an administrative domain. Our algorithm presents a new model for multicast congestion control as it does not involve on-router computation as opposed to other approaches which require router support. We evaluate our algorithm using ns, the network simulator. Our results indicate that topology information is very useful in understanding the dynamics of multicast congestion and can be used for efficient traffic management.

Most of the tools available for monitoring multicast have only marginal utility in today's multicast infrastructure. These tools lack the ability to handle the latest routing protocols because they rely on application layer data like the Realtime Transport Protocol (RTP). Our goal is to develop a system that monitors multicast at the network layer; that can provide functionality for all of the network management tasks; and that can be easily extended to monitor the evolving set of multicast protocols. To this end, we have developed Mantra, a tool for collecting data from multicast routers, analyzing the collected data and presenting realtime results. Using collected data, Mantra creates interactive graphs depicting the state of the multicast infrastructure. Results from Mantra are being used to monitor multicast usage and deployment, as well as routing protocol deployment and performance. In addition, the results are being used to detect common anomalies and to troubleshoot frequent routing problems. In this paper, we discuss the issues related to multicast monitoring, describe the existing efforts in the field and present the design of Mantra. In addition, we present results based on data collected over a 6 months period by monitoring the multicast traffic at two points: (1) at the Federal IntereXchange-West (FIXW) router, and (2) an on-campus router.

We investigate two issues. First, what level of efficiency gain does multicast offer over unicast? Second, how does the shape of multicast trees impact multicast efficiency? We address the first issue by developing a metric to measure multicast efficiency for a number of real and synthetic datasets. We find that group sizes as small as 20 to 40 receivers offer a 60-70% reduction in the number of links traversed compared to separately delivered unicast streams. Addressing the second issue, we have found that almost all multicast trees have similar characteristics in terms of key parameters such as depth, degree frequency and average degree. A final contribution of our work is that we have taken multicast group membership data and multicast path data and compiled datasets which can be used to generate large, realistic multicast trees.

No abstract available.

The IP multicast infrastructure has transitioned to a topology that now supports hierarchical routing. Multicast network monitoring and management have become key requirements necessary for providing robust multicast operation. Monitoring services help to identify potential problems such as protocol shortcomings, implementation bugs or configuration errors. This type of monnitoring often requires knowing the multicast tree topology. In this paper, we present a new approach, called tracetree, to discover tree topology in the source-to-receiver(s) direction using network forwarding state. We start with an overview of the problem. Then, we describe tracetree functionality including its request forwarding and response collection mechanisms. Next, we discuss a number of functional issues related to tracetree. Finally, we evaluate our technique by comparing it to a number of alternative approaches. We believe that our technique provides a scalable way of discovering a multicast tree's topology in realtime while requiring only marginal additional router functionality.

Abstract One of the new applications evolving in the Internet is streaming audio/video. A major reason for its growing popularity is interest in the compelling new services that become possible. Prototype services are being developed which are new to the Internet but offer the same look, feel, and functionality that have traditionally only been found in services delivered via other communication medium, e.g. broadcast television. In addition, the Internet is evolving to offer ‘value‐added’ services, like streaming audio/video with VCR‐style interactivity and embedded hyperlinks. We are poised both on seeing the development of new paradigms for interacting with audio/video, and on seeing the merging of broadcast television and Internet‐based broadcasts. Before this process can be considered successful, a number of technical challenges, derived from the various ways in which content is physically delivered, must be solved. In this paper, we focus on the value‐added service of VCR interactivity. VCR interactivity has long been a challenge for both broadcast television and streamed Internet audio/video. The challenge is how to provide individualized playout for content being streamed to a large group of users using one‐to‐many delivery. While some new companies are starting to offer devices which provide this kind of service for broadcast television, there are still numerous technical challenges for the Internet‐based version of a similar service. This paper has a three‐fold objective. First, we describe the types of services available in the traditional broadcast infrastructure and compare these to the types of services that are deployed or possible in Internet‐based services. Second, we describe our attempts to implement some of the more challenging and novel service types. In particular, we examine client‐based control of programs streamed over the Internet to tens, thousands, or even millions of users. Finally, we discuss the impact of these services on the protocols and applications used to support Internet‐based, multi‐party conferencing. Copyright © 2001 John Wiley & Sons, Ltd.

Content delivery has become an important application in the Internet. "Content" in this context can be a range of objects from movies to Web pages to software distribution. A streaming content delivery server should provide nearly immediate and continuous service by provisioning sufficient server and local network resources for the duration of playout. Because of the resource implications of delivering many large files simultaneously, scalability is an important requirement. Good scalability can be achieved by using a single channel to serve multiple users waiting for the same object (referred to as batching). Batching is especially useful during high load periods. Typical strategies in use today for allocating channels use a greedy allocate-as-needed policy with little consideration for anything other than satisfying the current request or maximizing the number of batched requests. Macroscopic system characteristics, like request arrival patterns, have stable long-term averages, but can vary unpredictably across shorter intervals. This variability can cause scheduling algorithms to suffer poor and unpredictable short-term performance. We propose a set of rate-based allocation algorithms to solve these limitations. We present our work in developing a set of workloads with variable request rates, quantify the drawbacks of traditional greedy channel-allocation algorithms, and quantify the advantages of the rate-based algorithms. We also generalize the content delivery model and discuss when rate-based algorithms might be effective other kinds of systems.

To further advance the deployment of multicast, many consider it necessary to provide a quantitative measure of the potential benefit of employing multicast rather than unicast. We approach this problem in three ways. First, we propose a rudimentary metric that can provide a reasonable measure of the benefit achieved by an active group using multicast instead of unicast. Second, we discuss many of the issues inherent in developing multicast metrics and how these issues may be addressed to improve the accuracy of our model. Third, we consider how characteristics of network topology and group distribution might offer a predictive estimate for the proposed metric. In general, we identify two rules for evaluating the efficiency of multicast: (1) multicast efficiency increases as the average path length increases, and (2) fan-out close to the source decreases multicast's efficiency.

The multicast infrastructure has transitioned to a topology that now supports hierarchical routing. Instead of a flat virtual topology originally called the Multicast Backbone (MBone) there now exists a hierarchy where routing information is exchanged between autonomous systems (ASes). In today's multicast infrastructure reachability problems are common. Unlike in the MBone, the possibility of limited connectivity between domains is now possible. We present a system called sdr-monitor. This tool collects session directory information from numerous places around the world and presents an application layer view of reachability. Using data collected over the last year, we present an analysis of long term reachability characteristics for the global multicast infrastructure. Our findings are that overall reachability is generally quite poor. However, having identified some of the reasons, we believe there is not a fundamental infrastructure problem, but rather protocol bugs and a lack of management tools.

The Multicast Backbone (MBone), the Internet's multicast research infrastructure, has existed since the early 1990s. Since its inception, there have been few formal studies investigating the "state of multicast", i.e., the success of multicast deployment. Our work attempts to understand: (1) how the MBone is used, (2) how multicast deployment has progressed, and (3) what barriers exist for the continued deployment of multicast. Future research and deployment efforts would benefit significantly with answers to these macro-scale questions. Our work is based on data sets collected over a 4.5 year period. These data sets include join/leave statistics for many of the MBone sessions advertised through the MBone's session directory tool. Using this data, we examine characteristics about the number and frequency of multicast groups and about the users participating in these groups. In addition, we attempt to qualify the accuracy of our results by examining other sources of multicast traffic statistics. Among our conclusions, we find that the use and deployment of multicast has continued to grow, but at a relatively slow rate. Furthermore, most of the activity in the MBone occurs among a relatively small group of core users. Finally, in an attempt to understand why these conditions exist, we offer several possible reasons why multicast deployment has not been more rapid.

The exponential growth of the Internet combined with the increasing popularity of streaming audio and video are pushing Internet bandwidth constraints to their limits. Methods of managing and more efficiently utilizing existing bandwidth are becoming increasingly vital. Using IP multicast to deliver content, especially streaming audio and video, can provide enormous bandwidth savings. A decade of effort at deploying multicast, combined with the rising need for better traffic management for bandwidth-hungry applications has led to significant momentum for multicast use and deployment. One of the remaining barriers to widespread adoption is the lack of multicast monitoring and debugging tools. To address this need we introduce MHealth, a graphical, near real-time multicast monitoring tool. MHealth utilizes existing tools to collect comprehensive data about Realtime Transport Protocol (RTP) based streaming audio/video sessions. By using a combination of application-level protocol data for participant information and a multicast route tracing tool for topology information, MHealth is able to present a multicast tree's topology and information about the quality of received data. In this paper we describe the design and implementation of MHealth and include an example analysis of multicast tree statistics. Copyright © 2000 John Wiley & Sons, Ltd.

Straightforward, one-way delivery of audio/video through television sets has existed for many decades. In the 1980s, new services like pay-per-view and video-on-demand were touted as the "killer applications" for interactive TV. However, the hype quickly died away, leaving only hard technical problems and costly systems. As an alternative, we propose a new jukebox paradigm offering flexibility in how programs are requested and scheduled for playout. The jukebox scheduling paradigm offers flexibility ranging from complete viewer control (true video-on-demand), to complete service provider control (traditional broadcast TV). We first describe our proposed jukebox paradigm and relate it to other on-demand paradigms. We also describe several critical research issues, including the one-to-many delivery of content, program scheduling policies, server location, and the provision of advanced services like VCR-style interactivity and advanced reservations. In addition, we present our implementation of a jukebox-based service called the Interactive Multimedia Jukebox (IMJ). The IMJ provides scheduling via the World Wide Web (WWW) and content delivery via the Multicast Backbone (MBone). For the IMJ, we present usage statistics collected during the past couple of years. Furthermore, using this data and a simulation environment, we show that jukebox systems have the potential to scale to very large numbers of viewers.

The World Wide Web (WWW) has gained tremendously in popularity. In this work we explore the use of UDP, best-effort multicast as a delivery option. Reliability is achieved through repetitive, cyclic transmission of a requested page. This solution is expected to be most efficient when used for highly requested pages. We view this cyclic multicast technique as a delivery option that can be integrated with the traditional reliable unicast and reliable multicast options. We first describe the architecture of an integrated Web server employing all three delivery options. We then describe the cyclic multicast technique and consider the various procedures needed for its successful operation. We characterize the gains in performance achieved by our proposal through an extensive performance analysis and simulation of our technique by itself, and when integrated with the other delivery options. We also describe our experience with an implementation of a prototype cyclic multicast server and its performance over the multicast backbone (MBone).

In typical video delivery systems offering programs on-demand, service should be be nearly immediate and continuous. A video server can provide this type of service by reserving sufficient network and server resources for the duration of playout. Scalability and reduced cost can be achieved using a single channel to serve multiple customers waiting for the same program (referred to as batching). Batching is especially useful during high load periods typically occuring during evening prime time hours. Typical channel allocation algorithms use a greedy, allocate-as-needed policy. Variations in system load can cause these algorithms to suffer poor and unpredictable short-term performance, and non-optimal long term performance. In this paper, we develop a set of realistic workloads, identify the limitations of greedy allocation algorithms, and propose a set of rate-based allocation schemes to solve these limitations. The performance of various video delivery systems are simulated and compared. The rate-based policies are shown to be robust for the workloads examined, and are easy to implement.

One purpose of the MBone is to study the performance of multicast and real time protocol in global conferencing applications. Part of this evaluation is dependent on understanding how the MBone is used and developing realistic workloads and usage models to assist in protocol evaluation. We have developed a tool, called Mlisten, to accurately collect the join/leave times for multicast group members in MBone audio sessions. Using data collected with Mlisten and a set of analysis tools, we report statistics about several MBone audio sessions including member inter arrival times and durations, multicast tree routing information, and group spatial characteristics. Data was also collected and analyzed for all active sessions to produce information about movement among multicast groups.

In typical proposals for video-on-demand (VoD) systems, customers are serviced individually by allocating and dedicating a transmission channel and a set of server resources to each customer. This approach leads to an expensive to operate, nonscalable system. We consider a VoD system that uses multicast delivery to service multiple customers with a single set of resources. The use of multicast communication requires that part of the on-demand nature of the system be sacrificed to achieve scalability and cost-effectiveness. One drawback to using multicast communication is that it complicates the provision or interactive VCR-style functions. Interactivity can be provided by either increasing the complexity of the customer set-top box (STB) or by modifying the semantics of the interactive functions to make them easier to provide. We describe a framework and mechanisms by which such interactive functions can be incorporated into a multicast delivery VoD system. Through the use of simulation, we evaluate and compare the performance of a unicast VoD system and multicast VoD systems offering various levels of interactivity.