Video conferencing applications (VCAs) are a vital tool for business, education, and other important purposes. However, VCAs are vulnerable to network latency, which can cause issues in client interactivity, such as increased overlaps, longer silence durations, and a degradation of the turn-taking structure. In this paper, we propose two systems for improving VCA interactivity in the presence of high network latency: one based on adjustment of the latency between pairs of clients, and the other based on notifying clients of their high latency. Both systems are suitable for deployment within the VCA selective forwarding unit, the central server for the conference. We evaluate the systems using a client behavioral model with accompanying interactivity metrics, and show, among other results, improvements of up to $50 \%$ in the overlap rate and $40 \%$ in useful conversation time, as well as restoration of the turn taking structure to the state with no network latency.

Video conferencing applications (VCAs) have become an indispensable tool for business, educational, and personal communications. There is, therefore, considerable interest in understanding and measuring the Quality of Experience (QoE) delivered by VCAs to their users. Video quality, one QoE measure, has received considerable attention in the literature. In this paper, we are concerned with another important aspect of VCA QoE, namely interactivity. We define this informally as the ability of a VCA to facilitate satisfying interaction among its users. Interactivity is primarily impacted by the media transmission latency among users which is, in turn, a function of network and application processing delays. Our goal in this work is to address two challenges in investigating interactivity-related QoE in VCAs. First, we propose a suite of meaningful quantifiable interactivity metrics, such as the proportion of silence time and rate of overlapping speech, that correlate well with conversational impairments and, hence, QoE perceptions. Second, we investigate scalable approaches for measuring these metrics. We develop a validated model for user behavior that enables realistic simulation of interactivity in VCA sessions. We also briefly consider an approach to measure interactivity metrics from packet traces. Through a set of experimental results, we demonstrate how our evaluation methodology provides a way for researchers, VCA service providers and network operators to perform large-scale investigations of how latency can interfere with user interactivity and impact VCA QoE.

Recording 3D movements of a user's hand, robotic arms, or an object, even in a small confined space, has several applications in AR/VR, robotics, movement science, and 3D modeling and rendering. Existing camera-based tracking systems, though extremely accurate, are quite expensive and suffer from issues of occlusion and face difficulties when operating in extremely dark or extremely bright environments. We contend that trading-off a bit of accuracy while reducing costs and enabling more flexible operating environment might be worth exploring. This paper presents UTrack3D, a table-top setup that tracks the movements of an object in 3D space using embedded low-cost ultra-wideband (UWB) radios. The core idea is to continuously track the changes in phase as captured from UWB signal's channel impulse response (CIR) derived from the UWB messages received at a set of dual-antenna UWB receivers. Each of our custom dual-antenna receivers captures the UWB signal from two corners of a cuboid allowing us to perform relative phase measurements. The main challenges in the solution are caused by a location-dependant large variation in the signal amplitudes and corruption of the CIR due to multipath. UTrack3D tackles these challenges via a signal processing pipeline fusing a forward localization process which tracks the object's location using UWB CIR phase, and a posterior location check process, which validates the estimated location. UTrack3D is implemented on commercial-off-the-shelf (COTS) UWB chips, and provides a 90th percentile accuracy of 9 mm in a table-top 3D region (1.5m × 0.8m × 0.8m). We evaluate the effects of additional UWB receivers, effect of different movement speeds, and effect of small-scale signal blocking using different materials. We expect UTrack3D to allow researchers a rich new environment for further advancing UWB-based 3D tracking.

This paper presents an ultra-wideband (UWB) based two-factor authentication (2FA) platform, called UWB-Auth, designed as carriable or wearable devices. UWB-Auth eliminates various social engineering attacks, including phishing attack, 2FA-fatigue attack, co-located attack etc., on existing 2FA solutions like Duo and reveals simple and fast user interaction. The key innovation of UWB-Auth is a novel combination of location authentication via UWB, checking whether a legitimate token is in the vicinity of the login device with centimeter-level accuracy, followed by an abstraction layer allowing different knowledge-based or biometric-based authentication, ensuring the user's identity and intent to login. Moreover, UWB-Auth reverses the sequence in which the two factors are verified, providing robust defences against data breach. We develop 3 UWB-Auth prototypes: a key-chain token, a smartwatch with commercial knowledge/biometric factor, and a smartring with customized knowledge/biometric authentication algorithm to demonstrate the effectiveness of UWB-Auth. Overall, UWB-Auth completes the whole authentication process in 4 seconds, and completely rejects malicious requests when the token is 20cm or 10^\circ outside a small valid physical area near the login device. Even when a malicious entity gains physical access to the token, UWB-Auth stops attack attempts via knowledge and biometric authentication.

We study user's valuations of smartphone sensing resources and the factors mediating them through a systematic auction study with 108 bids from$N=18$participants, two resource use conditions [fixed battery (FB) and variable battery (VB)] and three sensors (camera, microphone, and GPS) with differing energy and privacy costs. We use a second-price sealed-bid reverse auction as this allows us to elicit the participants’ truthful perceived value for sharing resources. We show that most users would be willing to share even highly-privacy intrusive sensors if they are sufficiently compensated. At the FB level, participants placed much lower value for sharing GPS (€13) than camera (€30) or microphone (€32.5). The values people place on sharing access to resources generally reflect four considerations: 1) the perceived value of the sensor type; 2) the value of the data captured by the sensor; 3) the impact of sharing on the device; and 4) personal variations related to sharing motives, personal tendencies, and the broader sharing context. We address the practical impact of our results by presenting two case studies (collaborative sensing and collaborative AI). Finally, we derive design implications for sharing sensing resources on personal devices.

The Internet has been experiencing immense growth in multimedia traffic from mobile devices. The increase in traffic presents many challenges to user-centric networks, network operators, and service providers. Foremost among these challenges is the inability of networks to determine the types of encrypted traffic and thus the level of network service the traffic needs to maintain an acceptable quality of experience. Therefore, end devices are a natural fit for performing traffic classification since end devices have more contextual information about device usage and traffic. This paper proposes a novel approach that classifies multimedia traffic types produced and consumed on mobile devices. The technique relies on a mobile device’s detection of its multimedia context characterized by its utilization of different media input/output (I/O) components, e.g., camera, microphone, and speaker. We develop an algorithm, MediaSense, which senses the states of multiple I/O components and identifies the specific multimedia context of a mobile device in real-time. We demonstrate that MediaSense classifies encrypted multimedia traffic in real-time as accurately as deep learning approaches and with even better generalizability.

The Internet has been experiencing immense growth in multimedia traffic from mobile devices. The increase in traffic presents many challenges to user-centric networks, network operators, and service providers. Foremost among these challenges is the inability of networks to determine the types of encrypted traffic and thus the level of network service the traffic needs for maintaining an acceptable quality of experience. Therefore, end devices are a natural fit for performing traffic classification since end devices have more contextual information about the device usage and traffic. This paper proposes a novel approach that classifies multimedia traffic types produced and consumed on mobile devices. The technique relies on a mobile device’s detection of its multimedia context characterized by its utilization of different media input/output components, e.g., camera, microphone, and speaker. We develop an algorithm, MediaSense, which senses the states of multiple I/O components and identifies the specific multimedia context of a mobile device in real-time. We demonstrate that MediaSense classifies encrypted multimedia traffic in real-time as accurately as deep learning approaches and with even better generalizability.

High-precision tracking of a pen-like instrument's movements is desirable in a wide range of fields spanning education, robotics, and art, to name a few. The key challenge in doing so stems from the impracticality of embedding electronics in the tip of such instruments (a pen, marker, scalpel, etc.) as well as the difficulties in instrumenting the surface that it works on. In this paper, we present ITrackU, a movement digitization system that does not require modifications to the surface or the tracked instrument's tip. ITrackU fuses locations obtained using ultra-wideband radios (UWB), with an inertial and magnetic unit (IMU) and a pressure sensor, yielding multidimensional improvements in accuracy, range, cost, and robustness, over existing works. ITrackU embeds a micro-transmitter at the base of a pen which creates a trackable beacon, that is localized from the corners of a writing surface. Fused with inertial motion sensor and a pressure sensor, ITrackU enables accurate tracking. Our prototype of ITrackU covers a large 2.5m × 2m area, while obtaining around 2.9mm median error. We demonstrate the accuracy of our system by drawing numerous shapes and characters on a whiteboard, and compare them against a touchscreen and a camera-based ground-truthing system. Finally, the produced stream of digitized data is minuscule in volume, when compared with a video of the whiteboard, which saves both network bandwidth and storage space.

Mobile Augmented Reality (MAR) mixes physical environments with user-interactive virtual annotations. Immersive MAR experiences are supported by computation-intensive tasks, which are typically offloaded to cloud or edge servers. Such offloading introduces additional network traffic and influences the motion-to-photon latency (a determinant of user-perceived quality of experience). Therefore, proper multimedia protocols are crucial to minimise transmission latency and ensure sufficient throughput to support MAR performance. Relatedly, 5G is a potential MAR supporting technology and is widely believed to be faster and more efficient than its predecessors. However, the suitability and performance of existing multimedia protocols for MAR in the 5G edge context have not been explored. In this work, we present a detailed evaluation of several popular multimedia protocols (HLS, MPEG-DASH, RTP, RTMP, RTMFP, and RTSP) and transport protocols (QUIC, UDP, and TCP) with a MAR system on a real-world 5G edge testbed. The evaluation results indicate that RTMP has the lowest median client-to-server packet latency on 5G and LTE for all image resolutions. In terms of individual image resolutions, from 144p to 480p over 5G and LTE, RTMP has the lowest median packet latency of $14.03\pm 1.05 {\mathrm ms}$. Whereas for jitter, HLS has the smallest median jitter across all image resolutions over LTE and 5G with medians of 2.62 ms and 1.41 ms, respectively. Our experimental results indicate that RTMP and HLS are the most suitable protocols for MAR.

Understanding end-user video Quality of Experience (QoE) is important for Internet Service Providers (ISPs). Existing work presents mechanisms that use network measurement data to estimate video QoE. Most of these mechanisms assume access to packet-level traces, the most-detailed data available from the network. However, collecting packet-level traces can be challenging at a network-wide scale. Therefore, we ask:"Is it feasible to estimate video QoE with lightweight, readily-available, but coarse-grained network data?" We specifically consider data in the form of Transport Layer Security (TLS) transactions that can be collected using a standard proxy and present a machine learning-based methodology to estimate QoE. Our evaluation with three popular streaming services shows that the estimation accuracy using TLS transactions is high (up to 72%) with up to 85% recall in detecting low QoE (low video quality or high re-buffering) instances. Compared to packet traces, the estimation accuracy (recall) is 7% (9%) lower but has up to 60 times lower computation overhead.

The coronavirus pandemic is altering our way of life. As more establishments open, there is an expectation that people will follow physical distancing guidelines. The implementation, however, is poor; just putting up warning signs appealing the general public to keep a distance of 6 feet from others is hardly enough. In this paper we consider the design of a wearable device that raises an alarm if another similar device is detected within a set distance. It uses off-the-shelf ultra-wideband radio technology for real-time, accurate distance estimation from others in the vicinity. We design an one-to-all ranging protocol that is able to accurately estimate distance to neighboring devices and warn the user if the distance falls below a certain established threshold within a short time. The device must compensate for human occlusions and avoid unnecessary warnings when physical barriers exist between devices. We implement and evaluate our protocol in a small testbed with custom prototype hardware as well as in simulation. Our ranging protocol is capable of performing up to 10 distance measurements per second, while avoiding packet collisions. The overall percentage of rangings completed is around 65% in a 10-node network, and the distance accuracy is around 20cm even with frequent human occlusions. We believe this prototype will provide the first steps to ensure physical distancing in various real-world settings.

We use various multimedia applications on smart devices to consume multimedia content, to communicate with our peers, and to broadcast our events live. This paper investigates the utilization of different media input/output devices, e.g., camera, microphone, and speaker, by different types of multimedia applications, and introduces the notion of multimedia context. Our measurements lead to a sensing algorithm called MediaSense, which senses the states of multiple I/O devices and identifies eleven multimedia contexts of a mobile device in real time. The algorithm distinguishes stored content playback from streaming, live broadcasting from local recording, and conversational multimedia sessions from GSM/VoLTE calls on mobile devices.

Cloud services are deployed in datacenters connected though high-bandwidth Wide Area Networks (WANs). We find that WAN traffic negatively impacts the performance of datacenter traffic, increasing tail latency by 2.5x, despite its small bandwidth demand. This behavior is caused by the long round-trip time (RTT) for WAN traffic, combined with limited buffering in datacenter switches. The long WAN RTT forces datacenter traffic to take the full burden of reacting to congestion. Furthermore, datacenter traffic changes on a faster time-scale than the WAN RTT, making it difficult for WAN congestion control to estimate available bandwidth accurately.

Modern end-host network stacks have to handle traffic from tens of thousands of flows and hundreds of virtual machines per single host, to keep up with the scale of modern clouds. This can cause congestion for traffic egressing from the end host. The effects of this congestion have received little attention. Currently, an overflowing queue, like a kernel queuing discipline, will drop incoming packets. Packet drops lead to worse network and CPU performance by inflating the time to transmit the packet as well as spending extra effort on retansmissions. In this paper, we show that current end-host mechanisms can lead to high CPU utilization, high tail latency, and low throughput in cases of congestion of egress traffic within the end host. We present zD, a framework for applying backpressure from a congested queue to traffic sources at end hosts that can scale to thousands of flows. We implement zD to apply backpressure in two settings: i) between TCP sources and kernel queuing discipline, and ii) between VMs as traffic sources and kernel queuing discipline in the hypervisor. zD improves throughput by up to 60%, and improves tail RTT by at least 10x at high loads, compared to standard kernel implementation.

BGP was initially created assuming by default that all ASes are equal. Its policies and protocols, namely BGP, evolved to accommodate a hierarchical Internet, allowing an autonomous system more control over outgoing traffic than incoming traffic. However, the modern Internet is flat, making BGP asymmetrical. In particular, routing decisions are mostly in the hands of traffic sources (i.e., content providers). This leads to suboptimal routing decisions as traffic sources can only estimate route capacity at the destination (i.e., ISP). In this paper, we present the design of Unison, a system that allows an ISP to jointly optimize its intra-domain routes and inter-domain routes, in collaboration with content providers. Unison provides the ISP operator and the neighbors of the ISP with an abstraction ISP network in the form of a virtual switch. This abstraction allows the content providers to program the virtual switch with their requirements. It also allows the ISP to use that information to optimize the overall performance of its network. We show through extensive simulations that Unison can improve ISP throughput by up to 30% through cooperation with content providers. We also show that cooperation of content providers only improves performance, even for non-cooperating content providers (e.g., a single cooperating neighbour can improve ISP throughput by up to 6%).

Understanding the user-perceived quality of experience (QoE) of HTTP-based video has become critical for content providers, distributors, and network operators. For network operators, monitoring QoE is challenging due to lack of access to video streaming applications, user devices, or servers. Thus, network operators need to rely on the network traffic to infer key metrics that influence video QoE. Furthermore, with content providers increasingly encrypting the network traffic, the task of QoE inference from passive measurements has become even more challenging. In this paper, we present a methodology called eMIMIC that uses passive network measurements to estimate key video QoE metrics for encrypted HTTP-based adaptive streaming (HAS) sessions. eMIMIC uses packet headers from network traffic to model an HAS session and estimate video QoE metrics, such as average bitrate and re-buffering ratio. We evaluate our methodology using network traces from a variety of realistic conditions and ground truth collected using a lab testbed for video sessions from three popular services, two video on demand (VoD) and one Live. eMIMIC estimates re-buffering ratio within 1% point of ground truth for up to 75% sessions in VoD (80% in Live) and average bitrate with error under 100 Kb/s for up to 80% sessions in VoD (70% in Live). We also compare eMIMIC with recently proposed machine learning-based QoE estimation methodology. We show that eMIMIC can predict average bitrate with 2.8%-3.2% higher accuracy and re-buffering ratio with 9.8%-24.8% higher accuracy without requiring any training on ground truth QoE metrics. Finally, we show that eMIMIC can estimate real-time QoE metrics with at least 89.6% accuracy in identifying buffer occupancy state and at least 85.7% accuracy in identifying average bitrate class of recently downloaded chunks.

The basic MAC mechanisms in IEEE 802.11 (WiFi) have remained largely unchanged for over 20 years. In this paper, we argue that the prevalence of WiFi makes it almost impossible to improve its performance through changes that require modifying hardware, firmware, or drivers. New applications, however, continue to exert novel performance demands. We suggest that changes should be developed as augmentation-only solutions through above-driver, kernel-level software modifications. An augmentation-only solution needs to maintain inter-operability and afford transparency in performance to existing WiFi devices, as well as enable minimum overhead upgradability. Our goal is to demonstrate the feasibility of MAC augmentation according to these principles. To this end, we leverage soft scheduling, where nodes are asked for a best-effort attempt to adhere to a given schedule. We allow the soft scheduler to coexist with and work at a different time scale from WiFi's Distributed Coordination Function (DCF); allowing it to reduce the time nodes spend contending for the medium while allowing DCF to handle only missed schedule slots and schedule divergence. We present a new Soft Token Passing Protocol (STPP) as an instance of this family of Soft Scheduling Protocols. We then show how STPP can be made part of a MAC protocol with specific performance improvement goals by developing the Wireless Low-Latency Local Links (WL4) system. We evaluate WL4 on a five node microbenchmark and quantify the system's overhead on network throughput and latency. We show that soft scheduling, via STPP, enables WL4 to adhere to our augmentation principles while improving the latency within the system.

Video streaming traffic is rapidly growing in mobile networks. Mobile Network Operators (MNOs) are expected to keep up with this growing demand, while maintaining a high video Quality of Experience (QoE). This makes it critical for MNOs to have a solid understanding of users' video QoE with a goal to help with network planning, provisioning and traffic management. However, designing a system to measure video QoE has several challenges: i) large scale of video traffic data and diversity of video streaming services, ii) cross-layer constraints due to complex cellular network architecture, and iii) extracting QoE metrics from network traffic. In this paper, we present VideoNOC, a prototype of a flexible and scalable platform to infer objective video QoE metrics (e.g., bitrate, rebuffering) for MNOs. We describe the design and architecture of VideoNOC, and outline the methodology to generate a novel data source for fine-grained video QoE monitoring. We then demonstrate some of the use cases of such a monitoring system. VideoNOC reveals video demand across the entire network, provides valuable insights on a number of design choices by content providers (e.g., OS-dependent performance, video player parameters like buffer size, range of encoding bitrates, etc.) and helps analyze the impact of network conditions on video QoE (e.g., mobility and high demand).

White spaces are portions of the TV spectrum that are allocated but not used locally. Ifaccurately detected, white spaces offer a valuable new opportunity for highspeed wireless communications. We propose a new method for white space detection that allows a node to actlocally, based on a centrally constructed model, and at low cost, whiledetecting more spectrum opportunities than best known approaches. Weleverage two ideas. First, we demonstrate that low-cost spectrum monitoringhardware can offer "good enough" detection capabilities. Second, we develop amodel that combines locally-measured signal features and location to more efficiently detect white space availability. We incorporate these ideas into the design,implementation, and evaluation of a complete system we call Waldo. We deployWaldo on a laptop in the Atlanta metropolitan area in the US covering 700 km2. Our results show that usingsignal features, in addition to location, can improve detection accuracy by up to10x for some channels. We also deploy Waldo on an Android smartphone,demonstrating the feasibility of real-time white space detection with efficientuse of smartphone resources.

It has become increasingly important for content providers (CPs) to reach consumers with low latency. Peering links that connect CPs directly to access Internet service providers (access ISPs) have been used for this purpose thus providing one-hop AS paths from CPs to users. While providing improved latency, these peering links still do not give CPs control over the entire end-to-end path to their users. This has made it difficult for CPs to completely manage user experience. Motivated by this, we propose the deployment of Zero-Hop Networks (ZeN), where a CP's entire end-to-end path to users is under its control. We believe it is important to respond to the compelling demand for ZeN and enable its provision over the shared Internet infrastructure so that all may continue to reap its benefits. In this paper we lay out the vision for ZeN, describing its goals and challenges. We propose to deploy ZeN by allowing CPs to extend their network's control over the access ISP substrate in a way that allows the CP to control the entire end-to-end path. We develop two strawman architectures based on Software-Defined Networking ideas: one based on resource reservation and the other based on network virtualization. We also discuss some elements of a research agenda that is needed to bring ZeN deployments to realization.

Dynamic Adaptive Streaming over HTTP (DASH) was introduced to enable high video quality streaming over HTTP. DASH depends on the adaptation logic at the client to choose which video bitrate to stream from the content server for each chunk. For clients receiving video over a cellular network, the cellular first hop tends to be the bandwidth bottleneck and can exhibit significant swings in available bandwidth. In this paper we develop and evaluate a Dynamic Adaptation for mobile Video Streaming (DAVS), a technique that can be used within DASH adaptation to handle the significant bandwidth variability experienced by cellular mobile clients. In our scheme the main innovation is that the client chooses a bitrate based on whether the playout buffer occupancy (BO) falls below or above a dynamic threshold. In addition, the scheme attempts to minimize bitrate switching by again delaying a change of video bitrate selection by a window of time - that is also dynamically determined. We evaluate the performance of DAVS over real traces collected from a mobile network operator. DAVS shows better performance over different video streaming metrics. Furthermore, It increases the QoE by a range 15% - 55% compared to benchmark algorithms.

With over 300 billion vehicle trips made in the United States and 64 billion in France per year, network operators have the opportunity to utilize the existing road and highway network as an alternative data network to offload large amounts of delay-tolerant traffic. To enable the road network as a large-capacity transmission system, we exploit the existing mobility of vehicles equipped with wireless and storage capacities together with a collection of offloading spots. An offloading spot is a data storage equipment located where vehicles usually park. Data is transloaded from a conventional data network to the closest offloading spot and then shipped by vehicles along their line of travel. The subsequent offloading spots act as data relay boxes where vehicles can drop off data for later pick-up by other vehicles, depending on their direction of travel. The main challenges of this offloading system are how to compute the road path matching the performance requirements of a data transfer and how to configure the sequence of offloading spots involved in the transfer. We propose a scalable and adaptive centralized architecture built on software-defined networking that maximizes the utilization of the flow of vehicles connecting consecutive offloading spots. We simulate the performance of our system using real roads traffic counts for France. Results show that the centralized controlled offloading architecture can achieve an efficient and fair allocation of concurrent data transfers between major cities in France.

Network function virtualization foresees the virtualization of service functions and their execution on virtual machines. Any service is represented by a service function chain (SFC) that is a set of VNFs to be executed according to a given order. The running of VNFs needs the instantiation of VNF Instances (VNFIs) that in general are software modules executed on virtual machines. The virtualization challenges include: 1) where to instantiate VNFIs; ii) how many resources to allocate to each VNFI; iii) how to route SFC requests to the appropriate VNFIs in the right sequence; and iv) when and how to migrate VNFIs in response to changes to SFC request intensity and location. We develop an approach that uses three algorithms that are used back-to-back resulting in VNFI placement, SFC routing, and VNFI migration in response to changing workload. The objective is to first minimize the rejection of SFC bandwidth and second to consolidate VNFIs in as few servers as possible so as to reduce the energy consumed. The proposed consolidation algorithm is based on a migration policy of VNFIs that considers the revenue loss due to QoS degradation that a user suffers due to information loss occurring during the migrations. The objective is to minimize the total cost given by the energy consumption and the revenue loss due to QoS degradation. We evaluate our suite of algorithms on a test network and show performance gains that can be achieved over using other alternative naive algorithms.

Multimedia streaming is a major mobile application, accounting for more than half of total mobile traffic. Streaming applications usually have a static buffering strategy. For example, buffer size is limited to x minutes of the stream, where x is optimized to provide the best trade-off between minimizing stalls and limiting waste of user's bandwidth and energy resulting from user abandonment. We show that such strategies based on information available on the mobile device alone do not work well when network conditions change dynamically, e.g., connectivity degrades due to congestion. We propose an alternative strategy using the framework called TANGO, based on a novel idea of cooperation between cellular network and mobile devices. By monitoring real-time network conditions and continuously predicting user location, our system is able to predict connectivity degradation in the near term. In such events, a notification is sent to the mobile device so that the streaming application can initiate a mitigation action, such as to pre-cache more content. In simulations based on real user traces, we found that TANGO reduces pause time by 13-72%, significantly outperforming DASH, which is the current state of the art.

Network virtualization techniques allow for the coexistence of many virtual networks hosted in the same substrate network. Virtual router migration allows for resource consolidation with the consequence to reduce the power consumption in low traffic periods. Unfortunately, virtual router migration has the effect of degrading the quality of service during the downtime in which the router is not able to carry on its forwarding function. For this reason, despite the advantages in power consumption saving, the migration technique should be applied with parsimony to avoid an excessive QoS degradation. The objective of this paper is to study virtual network embedding (VNE) problems aware of both operation and reconfiguration costs that are characterized by the energy consumption and the revenue loss due to QoS degradation. Both embedding optimization problem formulation and feasible solutions to the problem in cycle-stationary traffic scenario and when the possible embeddings are determined a priori will be given. Two migration policies will be introduced and compared. The first one, referred to as “global,” is based on the knowledge of the entire daily traffic profile and it is determined by solving a Markov decision process. The second one, referred to as “local,” is only based on the knowledge of the current traffic. The results achieved show how the application of the global policy allows better performance than the local one and its application can lead to a cost reduction in the order of 35% with respect to traditional migration policies.

Mobile devices are becoming increasingly capable computing platforms with significant processor power and memory. However, mobile compute capabilities are often underutilized. In this paper we consider how a collection of co-located devices can be orchestrated to provide a cloud service at the edge. Scenarios with co-located devices include, but are not limited to, passengers with mobile devices using public transit services, students in classrooms and groups of people sitting in a coffee shop. To this end, we propose the femtocloud system which provides a dynamic, self-configuring and multi-device mobile cloud out of a cluster of mobile devices. We present the femtocloud system architecture designed to enable multiple mobile devices to be configured into a coordinated cloud computing service despite churn in mobile device participation. We develop a prototype of our femtocloud system and use it in addition to simulations to evaluate the performance of the system showing its efficiency and ability to leverage the available devices' compute capacity. We contribute to a line of research on small, local and possibly private clouds.

With the advent of wearable computing and the resulting growth in mobile application market, we investigate mobile opportunistic cloud computing where mobile devices leverage nearby computational resources in order to save execution time and consumed energy. Our goal is to enable generic computation offloading to heterogeneous devices that include Cloud, mobile devices, and cloudlets. We propose a generic and flexible architecture that maximizes the computation gain with respect to various objective functions such as, minimizing the response time, reducing the overall energy consumption, and increasing the network lifetime. This novel architecture is designed to automate computation offloading to numerous compute resources over disrupted network connections.

DDoS attacks have been a persistent threat to network availability for many years. Most of the existing mitigation techniques attempt to protect against DDoS by filtering out attack traffic. However, as critical network resources are usually static, adversaries are able to bypass filtering by sending stealthy low traffic from large number of bots that mimic benign traffic behavior. Sophisticated stealthy attacks on critical links can cause a devastating effect such as partitioning domains and networks. In this paper, we propose to defend against DDoS attacks by proactively changing the footprint of critical resources in an unpredictable fashion to invalidate an adversary's knowledge and plan of attack against critical network resources. Our present approach employs virtual networks (VNs) to dynamically reallocate network resources using VN placement and offers constant VN migration to new resources. Our approach has two components: (1) a correct-by-construction VN migration planning that significantly increases the uncertainty about critical links of multiple VNs while preserving the VN placement properties, and (2) an efficient VN migration mechanism that identifies the appropriate configuration sequence to enable node migration while maintaining the network integrity (e.g., avoiding session disconnection). We formulate and implement this framework using SMT logic. We also demonstrate the effectiveness of our implemented framework on both PlanetLab and Mininet-based experimentations.

Recent studies observe that competing adaptive video streaming applications generate flows that lead to instability, under-utilization, and unfairness in bottleneck link sharing within the network. Additional measurements suggest there may also be a negative impact on users' perceived quality of service as a consequence. While it may be intuitive to resolve application-generated issues at the application layer, in this paper we explore the merits of a network layer solution. We are motivated by the observation that traditional network-layer metrics associated with throughput, loss, and delay are inadequate to the task. To bridge this gap we present a network-layer QoS framework for adaptive streaming video fairness that reflect the video user's quality of experience (QoE). We begin first by deriving a new measure to describe user-level fairness among competing flows, one that reflects the dynamics between the video encoding and its mapping to a screen with a given size and resolution. We then design and implement our framework in VHS (Video-Home-Shaper) to evaluate performance in the home's last access hop where this problem is known to exist. Experiments using a variety of devices, O/S platforms, and viewing screens demonstrate the merits of using video QoE as a basis for fair bandwidth sharing.

Mobile devices are often expected to perform computational tasks that may be beyond their processing or battery capability. Cloud computing techniques have been proposed as a means to offload a mobile device's computation to more powerful resources. In this paper, we consider the case where powerful computing resources are employed on a vehicle, thus they can be re-positioned in real time. User-carried devices with no Internet connectivity wish to initiate computing tasks to be run on a remote computer. This scenario finds application in challenged environments and may be used in a military or disaster relief setting. It is further enabled by increasing feasibility of constructing a Mobile High Performance Computer (MHPC) using rugged computer hardware with form factors that can be deployed in vehicles. By analogy to prior work on message ferries and data mules, one can refer to the use of MHPCs as computational ferrying. After illustrating and motivating the computational ferrying concept, we turn our attention into the challenges facing such a deployment. These include the well-known challenges of operating an opportunistic and intermittently connected network using message ferries - such as devising an efficient mobility plan for MHPCs and developing techniques for proximity awareness. In addition such a system must include computation offloading decision making mechanisms to be deployed by mobile users, techniques for scheduling computation on MHPCs, and for handling possible mobility of the users. In this paper, first we propose an architecture for the system components to be deployed on the mobile users and the MHPCs. We then provide solutions to the MHPC movement scheduling problem with sufficient generality to describe a number of plausible deployment scenarios. Finally, we report and discuss some preliminary results.

There is great potential for boosting the performance of mobile devices by offloading computation-intensive parts of mobile applications to the cloud. The full realization of this potential is hindered by a mismatch between how individual mobile devices demand computing resources and how cloud providers offer them: offloading requests from a mobile device usually require quick response, may be infrequent, and are subject to variable network connectivity, whereas cloud resources incur relatively long setup times, are leased for long time quanta, and are indifferent to network connectivity. In this paper, we present the design and implementation of the COSMOS system, which bridges this gap by providing computation offloading as a service to mobile devices. COSMOS efficiently manages cloud resources for offloading requests to both improve offloading performance seen by mobile devices and reduce the monetary cost per request to the provider. COSMOS also effectively allocates and schedules offloading requests to resolve the contention for cloud resources. Moreover, COSMOS makes offloading decisions in a risk-controlled manner to overcome the uncertainties caused by variable network connectivity and program execution. We have implemented COSMOS for Android and explored its design space through computation offloading experiments to Amazon EC2 across different applications and in various settings. We find that COSMOS, configured with the right design choices, has significant potential in reducing the cost of providing cloud resources to mobile devices while at the same time enabling mobile computation speedup.

The explosive growth of mobile data traffic poses severe pressure on cellular providers to better manage their finite spectrum. Proposed solutions such as congestion-pricing exist, but they degrade users' ability to use the network when they want. In this paper, we propose a fundamentally different approach - rather than reducing the aggregate busy hour traffic, we seek to smooth the peaks that cause congestion. Our approach is based on two key insights obtained from traffic traces of a large cellular provider. First, mobile traffic demonstrates high short-term variation so that delaying traffic for very short periods of time can significantly reduce peaks. Second, by making collaborative decisions on which traffic gets delayed and by how much across all users of a cell, the delays need not result in any degradation of user experience. We design a system, CoAST, to implement this approach using three key mechanisms: a protocol to allow mobile applications and providers to exchange traffic information, an incentive mechanism to incentivize mobile applications to collaboratively delay traffic at the right time, and mechanisms to delay application traffic. We provide extensive evaluations that show that CoAST reduces traffic peaks by up to 50% even for applications that are not thought to be delay-tolerant, e.g., streaming and web browsing, but which together account for 70% of all cellular traffic.

Network virtualization enables the deployment of novel network architectures and services on existing Internet infrastructure. In addition, virtual networks (VNs) can share the resources in the physical substrate. To enable efficient resource reallocation and network agility, VNs must sometimes migrate, i.e., change their placements on a substrate network. While VN placement, and to a lesser extent migration, has been studied in the past, little attention has been devoted to deploying and evaluating these functions over a real infrastructure. In this paper, we study the VN migration problem based on network virtualization in PlanetLab. We create a tool, PL-VNM, that orchestrates the VN migration on PlanetLab for a given new VN placement. The design and deployment of the tool reveal challenges and constraints. Some are particular to PlanetLab while others apply more generally to any virtualized infrastructure. Most significantly, we find that while in principle one can specify a migration schedule (sequence of migration steps) as an input to our tool, certain PlanetLab features make VN migration scheduling very difficult if not infeasible. Our work leads to recommendations about the features of a general virtualization environment and specific recommendations for PlanetLab that enable VN migration and migration scheduling. We believe that the recommended features make long-term experiments and application deployments on PlanetLab and other realistic virtualized infrastructures possible.

Overlay (virtual) networks are mainly used to improve Internet reliability and facilitate a rapid deployment of new services. However, in order for overlay services to adapt to dynamic network conditions in a timely manner, efficient diagnosis of performance problems is required. Existing overlay diagnosis approaches assume extensive knowledge about the network and require invasive monitoring sensors or active measurements. In this paper, we propose a novel diagnosis technique to localize performance anomalies and determine the packet loss in each network component. Our approach is purely based on packet loss observations at the end-points to reason about the loss location and severity in the network without any active probing or sensor deployment. We formulate the problem as a constraint-satisfaction problem using network loss properties and end-user observations. Our diagnosis is robust against insufficient observations or malicious end-user participation. We evaluate our approach extensively using simulation and experimentation and demonstrate the accuracy, effectiveness, and scalability of our approach under various network sizes, participation ratio, and malicious observation ratio.

Overlay networks have become an effective method to help overcome the limitations of the Internet in the last decade. Overlays must be monitored for various kinds of problems so that efficient performance can be sustained. An overlay's topology and placement on the substrate have a considerable effect on the level of difficulty in monitoring it. In this paper, we study the problem of placing overlay networks onto the substrate in a way that makes it easier to detect and localize faults, in other words, improves their diagnosability. Overlay network fault diagnosis is especially challenging because of their construction as virtual networks on top of a network substrate. We give a practical definition of diagnosability, and develop an overlay assignment algorithm that aims to optimize overlay placement for the ease and quickness of fault diagnosis. We evaluate the efficiency of this algorithm using an existing passive fault diagnosis scheme, and show that we are able to improve diagnosability without placing a significant strain on the network. We also analyze diagnosability in situations where traffic is sufficient for passive measurements on a percentage of paths rather than the whole network, and study how to augment passive diagnosis with selective active probing in order to raise diagnosability to a desired level.

Many environmental, commercial, military, and structural monitoring applications of wireless sensor networks (WSNs) involve lining up the sensors in a linear form, and making a special class of these networks; we defined these in a previous paper as Linear Sensor Networks (LSNs), and provided a classification of the different types of LSNs. A multihop approach to routing the data from the individual sensor nodes to the sink can be used in an LSN. However, this can result in a rapid depletion of the sensor energy, due to the frequent transmissions performed by the sensors to transmit their own, as well as other sensor data. In addition, in many applications, the distance between the sensors deployed to monitor the linear structure might be much greater than the communication range leading to a disconnected network where the multihop approach cannot be used. This paper presents a framework for monitoring linear infrastructures using ferry-based LSNs (FLSNs). The data that is collected by the sensors is assumed to be delay-tolerant. In such a system, a moving robot, vehicle, or any other mobile node (named a ferry), can move back and forth along the linear network, and collect data from the individual sensors when it comes within their communication range; The ferry can deliver the collected sensor data when it reaches the sink. It can also perform other functions, such as data processing, and aggregation, and can also transport messages from the sink to the sensor nodes (SNs). Four different ferry movement approaches are presented, simulated, and analyzed.

HTTP adaptive video streaming is an emerging technology that aims to deliver video quality to clients in a manner that accommodates available bandwidth and its fluctuations. In this scheme, a video stream is split at the server into small video files encoded at multiple bitrates. The video is composed at the client by downloading these files over HTTP and TCP. Although there are some efforts to standardize media representation for this technology, adaptation techniques remain an open area for development. Recently, an alarm was raised by a study about the interaction between TCP congestion control algorithms and large buffers on the Internet. Queuing delays when these buffers are full can reach several hundreds of milliseconds in a phenomenon that was dubbed buffer bloat. In this paper we use measurements on a testbed to demonstrate and quantify the buffer bloat effect of HTTP adaptive streaming. We show that in a typical residential setting a single video stream can easily cause queuing delays up to one second and even more hence seriously degrading the performance of other applications sharing the home network. We develop SABRE (Smooth Adaptive Bit RatE), a scheme that can be implemented by the client to mitigate this problem. We implemented SABRE in the VLC player. Using our testbed, we show that our technique can reduce buffer occupancy and significantly diminish the buffer bloat effect without affecting the experience of the video viewer.

Designers of content distribution networks (CDNs) often need to determine how changes to infrastructure deployment and configuration affect service response times when they deploy a new data center, change ISP peering, or change the mapping of clients to servers. Today, the designers use coarse, back-of-the-envelope calculations or costly field deployments; they need better ways to evaluate the effects of such hypothetical “what-if” questions before the actual deployments. This paper presents What-If Scenario Evaluator (WISE), a tool that predicts the effects of possible configuration and deployment changes in content distribution networks. WISE makes three contributions: 1) an algorithm that uses traces from existing deployments to learn causality among factors that affect service response time distributions; 2) an algorithm that uses the learned causal structure to estimate a dataset that is representative of the hypothetical scenario that a designer may wish to evaluate, and uses these datasets to predict hypothetical response-time distributions; 3) a scenario specification language that allows a network designer to easily express hypothetical deployment scenarios without being cognizant of the dependencies between variables that affect service response times. Our evaluation, both in a controlled setting and in a real-world field deployment on a large, global CDN, shows that WISE can quickly and accurately predict service response-time distributions for many practical what-if scenarios.

Mobile devices are increasingly being relied on for services that go beyond simple connectivity and require more complex processing. Fortunately, a mobile device encounters, possibly intermittently, many entities capable of lending it computational resources. At one extreme is the traditional cloud-computing context where a mobile device is connected to remote cloud resources maintained by a service provider with which it has an established relationship. In this paper we consider the other extreme, where a mobile device's contacts are only with other mobile devices, where both the computation initiator and the remote computational resources are mobile, and where intermittent connectivity among these entities is the norm. We present the design and implementation of a system, Serendipity, that enables a mobile computation initiator to use remote computational resources available in other mobile systems in its environment to speedup computing and conserve energy. We propose a simple but powerful job structure that is suitable for such a system. Serendipity relies on the collaboration among mobile devices for task allocation and task progress monitoring functions. We develop algorithms that are designed to disseminate tasks among mobile devices by accounting for the specific properties of the available connectivity. We also undertake an extensive evaluation of our system, including experience with a prototype, that demonstrates Serendipity's performance.

Message Ferrying is a mobility assisted scheme in which a special node, called a message ferry, is tasked with delivering data among a set of disconnected wireless nodes. One key challenge for such scheme is to design the ferry route in a way that improves certain network characteristics such as average data delivery delay or data loss ratio. Previous work has optimized ferry travel time, rather than directly optimizing message delivery performance metrics. In this paper, we revisit the basic ferry route design problem for stationary nodes with the goal of providing a framework for optimizing delay performance. We start with a Markovian Decision Problem (MDP) formulation which produces the optimal ferry route that minimizes the average data delivery delay. While this formulation, in principle, enables optimal ferry route design, it is numerically intractable for moderate to large size problems. Solutions to small problems, however, yield insight into the properties of optimal ferry routes. These insights, in turn, lead us to propose a ferry route design algorithm that takes advantage of the similarity between our problem and the link scheduling problem in traditional networks. Our algorithm is inspired by the Deficit Round Robin (DRR) algorithm which has provable properties for delay optimization when applied to link scheduling. Using simulations we show that our DRR-based algorithm produces ferry routes that are close to optimal when compared to the MDP-derived solutions for small problems. Our results also show that our algorithm produces ferry routes for moderate to large problems that significantly outperform existing solutions.

As the dominant Internet application, peer-to-peer (P2P) file sharing systems account for the major portion of Internet traffic, posing significant burden on ISPs. Many ISPs have attempted to discriminate against P2P traffic, making it important to alleviate such severe conflict. In this paper, we propose a novel architecture called iDTT that aims to use the underutilized off-peak time network capacity to transfer data for P2P file sharing systems. The rationale is that file sharing, especially for large files, is not real-time and able to tolerate some delay. iDTT is able to reduce network usage at peak time by storing data at overlay nodes and transferring it at off-peak times. This reduces ISP cost for transit traffic and the pressure on their infrastructure. Two representative P2P systems, eMule and BitTorrent, are adapted to use iDTT as their data plane. Our experiments on Emulab show that iDTT significantly reduces the network traffic at peak times while only slightly increasing the downloading time for these applications.

Most commercial video streaming systems rely on Content Distribution Networks (CDNs) to distribute video content. HTTP adaptive streaming has been recently adopted by major video streaming providers and is now considered the standard technique used with CDN-based streaming systems. Despite the success of these systems, cost-effective scalability continues to be of concern in their design and deployment. To address this, recent work has proposed the use of hybrid CDN and Peer-to-peer (P2P) live streaming systems. The design of these systems aims to combine the scalability of P2P systems and the desirable performance properties of CDN-based systems. However, the use of adaptive streaming, has not been explored extensively in such hybrid systems. Designing and operating an adaptive hybrid streaming system is very challenging. Two design decisions are very critical in the operation of any such system. The first one is the bitrate adaptation strategy which specifies how different bitrates are assigned to different users while maximizing user satisfaction. The second is defining the operational guidelines for switching the system between the CDN and the P2P modes while efficiently utilizing the available resources. In this paper we present a model and analysis of a hybrid CDN-P2P adaptive live streaming system with the objective of answering these two design questions. We first present a stochastic fluid model to the hybrid streaming system with a single video bitrate and we obtain theoretical results to guide the system operation as described above. We then extend the analysis to the adaptive streaming case with multiple video bitrates. We model adaptive streaming as a linear optimization problem to obtain the best bitrate adaptation strategy. We validate our analysis using simulations. Our conclusion is that adaptive hybrid streaming can significantly improve the ability of the system to satisfy more users with higher video bitrates over CDN-based systems.

Cellular data links are an effective outdoor Internet access solution in urban environments. In this paper, we evaluate cellular data service as a potential data communication solution for oil field crews operating at remote areas in the United States. In our study, we first record the performance of cellular data service at twelve oil field locations. Measurement results show extensive availability of cellular service at those locations making it potentially a data communication solution at field locations. Spatial diversity from multiple antennas is shown to improve the cellular data link's speed but quality of the link varies significantly due to attenuated/faded cellular signal. We then design a measurement framework and deploy measurement units to five oil field crews and carry out a side-by-side comparison of two different satellite links and cellular links from two service providers. Analysis of data sets consisting of more than 300 days' measurement shows that the cellular link has comparable or even higher availability than conventional satellite link at many field operations. However, the quality of its coverage is location dependent. This indicates that both cellular and satellite links should be used to provide highly available and cost-effective data communication for such operations.

Until recently, the vast majority of research in wireless and mobile networks focused on so-called Mobile Ad Hoc Networks (MANETs), where relatively stable end-to-end paths are the norm. More recently, research has focused on a different, Intermittently Connected Network (ICN) paradigm, where stable end-to-end paths are the exception and intermediate nodes may store data while waiting for transfer opportunities towards the destination. Protocols developed for MANETs generally do not work in ICNs since the connectivity assumptions are so different. In this talk I will first give an overview of ICNs and the types of challenges involved in their design and operation. I will then discuss our work in the WAM (wireless and mobile) Continuum project which is based on the simple but powerful observation that MANETs and ICNs fit into a continuum that generalizes these two previously distinct categories. Building on this observation, our work develops a framework that goes further to scope the entire space of wireless and mobile networks. I will summarize two efforts: The first gives clues of the fundamental relationship between ICNs and MANETs by unifying the use of message ferrying in ICNs with the well-known use of connected dominating set-based routing in MANETs. The second effort aims at developing a formal WAM Continuum framework where a network can be characterized by its position in this continuum. Certain network equivalence classes can be defined over subsets of this WAM continuum and this classification can be used to inform network design and operation. I will demonstrate how the unified view enabled by our framework can be used as a systematic, formal descriptive and evaluative tool.

In opportunistic networks, end-to-end paths between two communicating nodes are rarely available. In such situations, the nodes might still copy and forward messages to nodes that are more likely to meet the destination. The question is which forwarding algorithm offers the best trade off between cost (number of message replicas) and rate of successful message delivery. We address this challenge by developing the PeopleRank approach in which nodes are ranked using a tunable weighted social information. Similar to the PageRank idea, PeopleRank gives higher weight to nodes if they are socially connected to important other nodes of the network. We develop centralized and distributed variants for the computation of PeopleRank. We present an evaluation using real mobility traces of nodes and their social interactions to show that PeopleRank manages to deliver messages with near optimal success rate (close to Epidemic Routing) while reducing the number of message retransmissions by 50% compared to Epidemic Routing.

Overlay networks are becoming prevalent in today's networking environment. We consider scenarios where substrate resources are primarily consumed by many overlay networks placed on top of the substrate. We focus on the fair and efficient allocation of substrate link bandwidth among competing overlays. We adapt various existing fairness definitions to this scenario and define a metric to evaluate the fairness of an allocation in a multi-overlay setting. We also examine the effect of routing decisions on resource allocation, and discuss methods to deviate from shortest-path routing in the substrate in order to achieve higher rates and increased fairness for the overlays. We demonstrate that substrate networks can better meet overlay demands when a combination of fair allocation algorithms and intelligent routing decisions is employed.

In opportunistic ad-hoc networks, multi-hop data transfer over contemporaneous paths is unlikely since the devices are often disconnected from each other. However, data can still be stored and forwarded over time in an opportunistic hop-by-hop manner. Previous work has considered how the availability of various types of information such as social relationships can be used to guide forwarding algorithm to make better decisions and bring messages closer to the destination. This implicitly assumes that opportunistic contacts relate with the social property of node. However, the impact of such correlation between social and contact properties on social forwarding performances remains largely unexplored. In this paper we argue that the relevance of such social information (social inputs) is as important as designing a new social forwarding algorithms. We examine multiple datasets to determine the impact of correlation, if any, between social information of individuals and their mobility patterns on the forwarding performances. We propose methods which process the social inputs to improve the relevance of such social information to forwarding. We show that our processing methods could improve the success rate performances of many social forwarding algorithms by more than 30%.

We present NANO, a system that detects when ISPs apply policies that discriminate against specific classes of applications, users, or destinations. Existing systems for detecting discrimination are typically specific to an application or to a particular discrimination mechanism and rely on active measurement tests. Unfortunately, ISPs can change discrimination policies and mechanisms, and they can evade these tests by giving probe traffic higher priority. NANO detects ISP discrimination by passively collecting performance data from clients. To distinguish discrimination from other causes of degradation (e.g., overload, misconfiguration, failure), NANO establishes a causal relationship between an ISP and observed performance by adjusting for confounding factors. NANO agents deployed at participating clients across the Internet collect performance data for selected services and report this information to centralized servers, which analyze the measurements to establish causal relationship between an ISP and performance degradations. We have implemented NANO and deployed clients in a controlled environment on Emulab. We run a combination of controlled experiments on Emulab and wide-area experiments on PlanetLab that show that NANO can determine the extent and criteria for discrimination for a variety of discrimination policies and applications.

Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc Min-Max Buffer Problem} for the case when the nodes are onhierarchically separated metric spaces.

Many enterprise, campus, and data-center networks have complex layer-2 virtual LANs ("VLANs") below the IP layer. The interaction between layer-2 and IP topologies in these VLANs introduces hidden dependencies between IP level network and the physical infrastructure that has implications for network management tasks such as planning for capacity or reliability, and for fault diagnosis. This paper characterizes the extent and effect of these dependencies in a large campus network. We first present the design and implementation of EtherTrace, a tool that we make publicly available, which infers the layer-2 topology using data passively collected from Ethernet switches. Using this tool, we infer the layer-2 topology for a large campus network and compare it with the IP topology. We find that almost 70% of layer-2 edges are shared by 10 or more IP edges, and a single layer-2 edge may be shared by as many as 34 different IP edges. This sharing of layer-2 edges and switches among IP paths commonly results from trunking multiple VLANs to the same access router, or from colocation of academic departments that share layer-2 infrastructure, but have logically separate IP subnet and routers. We examine how this sharing affects the accuracy and specificity of fault diagnosis. For example, applying network tomography to the IP topology to diagnose failures caused by layer-2 devices results in only 54% accuracy, compared to 100% accuracy when our tomography algorithm takes input across layers.

We present an end-to-end active probing methodology that creates frequency-domain signals in IP network paths. The signals are generated by periodic packet trains that cause short-lived queueing delay spikes. Different probers can be multiplexed in the frequency-domain on the same path. Further, a signal that is introduced by a "prober" in one path can cause a crosstalk effect, inducing a signal of the same frequency into another path (the "sampler") as long as the two paths share one or more bottleneck queues. Applications of the proposed methodology include the detection of shared store-and-forward devices among two or more paths, the creation of covert channels, and the modulation of voice or video periodic packet streams in less noisy frequencies. In this paper we focus on the first application. Our goal is to detect shared bottleneck(s) between a "sampler" and one or more "prober" paths. We present a spectral probing methodology as well as the corresponding signal processing/detection process. The accuracy of the method has been evaluated with controlled and repeatable simulation experiments, and it has also been tested on some Internet paths.

Designers of content distribution networks often need to determine how changes to infrastructure deployment and configuration affect service response times when they deploy a new data center, change ISP peering, or change the mapping of clients to servers. Today, the designers use coarse, back-of-the-envelope calculations, or costly field deployments; they need better ways to evaluate the effects of such hypothetical "what-if" questions before the actual deployments. This paper presents What-If Scenario Evaluator (WISE), a tool that predicts the effects of possible configuration and deployment changes in content distribution networks. WISE makes three contributions: (1) an algorithm that uses traces from existing deployments to learn causality among factors that affect service response-time distributions; (2) an algorithm that uses the learned causal structure to estimate a dataset that is representative of the hypothetical scenario that a designer may wish to evaluate, and uses these datasets to predict future response-time distributions; (3) a scenario specification language that allows a network designer to easily express hypothetical deployment scenarios without being cognizant of the dependencies between variables that affect service response times. Our evaluation, both in a controlled setting and in a real-world field deployment at a large, global CDN, shows that WISE can quickly and accurately predict service response-time distributions for many practical What-If scenarios.

Overlay routing operating in a selfish manner is known to cause undesired instability when it interacts with native layer routing. We observe similar selfish behavior with the BitTorrent protocol, where its performance-awareness causes it to constantly alter the routing decisions (peer and piece selection). This causes fluctuations in the load experienced by the underlying native network. By using real BitTorrent traces and a comprehensive simulation with different network characteristics, we show that BitTorrent systems easily disrupt the load balance across inter-domain links. Further, we find that existing native layer traffic management schemes suffer from several downsides and are not conducive to deployment. To resolve this dilemma, we propose two BitTorrent strategies that are effective in resolving the cross-layer conflict.

The traffic exchanged between two overlay nodes in different autonomous systems (AS) is always subjected to a series of inter-domain policies. However, overlay routing often manages to get around these policy restrictions by relaying traffic through multiple legitimate segments, in order to achieve its selfish goals (e.g., better latency paths between end- systems). We focus on the violation of a generalized exit policy, which specifies the exact next hop AS and the egress inter- domain link for a destination address prefix. We characterize the different types of these exit policy violations and investigate their extent in a Planetlab testbed. It is conceivable that the native ASes will eventually realize the negative impact of the exit violations and adopt stringent strategies to enforce the exit policies, thereby causing deterioration in overlay performance. In this context, based on our findings from a previous study[l], we develop a pricing-based strategy that an overlay service provider can use to obtain permits from a near-optimal set of native ASes, in an effort to regain its routing advantage within a fixed budget. Further, we illustrate the use of this approach on our case study overlay network.

Wireless sensor networks (WSN) built using current Berkeley Mica motes exhibit low reliability for packet delivery. There is anecdotal evidence of poor packet delivery rates from several field trials of WSN deployment. All-to-one communication pattern is a dominant one in many such deployments. As we scale up the size of the network and the traffic density in this communication pattern, improving the reliability of packet delivery performance becomes very important. This study is aimed at two things. Firstly, it aims to understand the factors limiting reliable packet delivery for all-to-one communication pattern in dense wireless sensor networks. Secondly, it aims to suggest enhancements to well-known protocols that may help boost the performance to acceptable levels. We first postulate the potential reasons hampering packet delivery rates with current CSMA-based MAC layer used by the radios deployed in WSN. We then propose a set of enhancements that are aimed to mitigate the ill-effects of these factors. We pick three protocols, namely, Flooding, AODV, and Geographic routing as candidates for this study. Using TOSSIM, we perform a detailed study of these protocols and the proposed enhancements. This study serves several purposes. First, it helps us to quantify the detrimental effects of these factors. Second, it helps us to quantify the extent to which our proposed enhancements improves packet delivery performance. Concretely, we show that using Geographic routing in a WSN with 225 nodes spread over 150 feet times 150 feet, the proposed enhancements yield a 23-fold improvement in packet delivery performance over the baseline. Further, the enhancements result in fairness (measured by the number of messages received from each node at the destination). Lastly, we show that the overhead (in terms of retransmissions, acknowledgement messages, and control messages) is reasonable.

Overlay routing is known to cause undesired instability in a network by operating in a selfish manner. The objectives of overlay routing, such as optimizing end-to-end latency, are often in conflict with the objectives of traffic engineering in the native layer, which is concerned about balancing load. In our work, we build on past research that has investigated the recurring non-cooperative interaction between overlay routing and traffic engineering, and develop strategies that improve the routing performance of a particular layer with incomplete information about the other layer. In our strategies, one layer acts as a leader that predicts the follower's reaction and undertakes countermeasures to prevent future deterioration in performance. Specifically, we propose two classes of strategies - friendly or hostile - for each layer. By simulating under different network characteristics, we show that these preemptive strategies achieve near-optimal performance for the leader and increase the overall stability of the network. Furthermore, we observe that the best performance for a particular layer is achieved only when the goals of the other layer are completely violated, thereby motivating a higher level of selfishness.

Multihoming and overlay routing are used, mostly separately, to bypass Internet outages, congested links and long routes. In this paper, we examine a scenario in which multihoming and overlay routing are jointly used. Specifically, we assume that an overlay service provider (OSP) aims to offer its customers the combined benefits of multihoming and overlay routing, in terms of improved performance, availability and reduced cost, through a network of multihomed overlay routers. We focus on the corresponding design problem, i.e., where to place the overlay routers and how to select the upstream ISPs for each router, with the objective to maximize the profit of the OSP. We examine, with realistic network performance and pricing data, whether the OSP can provide a network service that is profitable, better (in terms of round-trip time), and less expensive than the competing native ISPs. Perhaps surprisingly, we find out that the OSP can meet all three objectives at the same time. We also show that the MON design process is crucial. For example, operating more than 10 overlay nodes or routing traffic through the minimum-delay overlay path, rarely leads to profitability in our simulations.

In this paper we consider how vehicular networking technology can be used to support roadside-to-roadside (r2r) communications. In this form of communication vehicles traveling along a road or highway are used to transport data between two fixed roadside locations that are too far apart to be connected. The basic idea is to have a roadside station give data to a moving vehicle as it gets close and then have the vehicle carry and then deliver the data to the other roadside station. In previous work we first considered the feasibility of such a service. In this paper we aim to take concrete steps towards making the deployment of such a service real and useable. We, therefore, focus on two main aspects of such a service: 1) The design of the data transfer mechanisms between the roadside stations and the vehicles assuming a standard 802.11 MAC protocol is in use, and 2) The design of schemes to insure reliable data transfer between the two roadside stations over the particularly challenging channel provided by the moving vehicles. We describe and evaluate several schemes to achieve data transfer reliability. We find that a rateless coding scheme is best for the transfer of small to moderate files, while a hybrid ARQ/data replication scheme performs well for larger file transfers.

The Internet is a complex structure arising from the interconnection of numerous autonomous systems (AS), each exercising its own administrative policies to reflect the commercial agreements behind the interconnection. However, routing in service overlay networks is quite capable of violating these policies to its advantage. To prevent these violations, we see an impending drive in the current Internet to detect and filter overlay traffic. In this paper, we first present results from a case study overlay network, constructed on top of Planetlab, that helps us gain insights into the frequency and characteristics of the different inter-domain policy violations. We further investigate the impact of two types of overlay traffic filtering that aim to prevent these routing policy violations: blind filtering and policy- aware filtering. We show that such filtering can be detrimental to the performance of overlay routing. We next consider two approaches that allow the overlay network to realize the full advantage of overlay routing in this context. In the first approach, overlay nodes are added so that good overlay paths do not represent inter-domain policy violations. In the second approach, the overlay acquires transit permits from certain ASes that allow certain policy violations to occur. We develop a single cost-sharing framework that allows the incorporation of both approaches into a single strategy. We formulate and solve an optimization problem that aims to determine how the overlay network should allocate a given budget between paying for additional overlay nodes and paying for transit permits to ASes. We illustrate the use of this approach on our case study overlay network and evaluate its performance under varying network characteristics.

Abstract — The routing infrastructure of the Internet has become resistant to fundamental changes and the use of overlay networks has been proposed to provide additional flexibility and control. One of the most prominent configurable components of an overlay network is its topology, which can be dynamically reconfigured to accommodate communication requirements that vary over time. In this paper, we study the problem of determining dynamic topology reconfiguration for service overlay networks with dynamic communication requirement, and the ideal goal is to find the optimal reconfiguration policies that can minimize the potential overall cost of using an overlay. We start by observing the properties of the optimal reconfiguration policies through studies on small systems and find structures in the optimal reconfiguration policies. Based on these observations, we propose heuristic methods for constructing different flavors of reconfiguration policies, i.e., never-change policy, always-change policy and cluster-based policies, to mimic and approximate the optimal ones. Our experiments show that our policy construction methods are applicable to large systems and generate policies with good performance. Our work does not only provide solutions to practical overlay topology design problems, but also provides theoretical evidence for the advantage of overlay network due to its configurability. I.

Abstract — Overlay networks have recently gained attention as a viable alternative to overcome functionality limitations of the Internet. We are concerned with scenarios where a dynamic routing protocol is employed in the overlay network to adapt overlay routing tables to changing network conditions. At the same time, the native network over which the overlay is built also runs its own set of dynamic routing protocols. We are interested in investigating the behavior of this mixed routing environment and in particular the characteristics of the interaction between these two routing layers. In this paper, we focus on the specific problem of rerouting around failed links. We first study a Dual Rerouting scenario in which the two routing layers run completely independent of each other. Our goal is to understand the effect of the various settings of routing protocol parameters on the packet loss, number of route flaps, and the optimality of the adopted overlay path. We show that Dual Rerouting provides relatively fast path recovery. But, it tends to be sub-optimal in terms of the number of route flaps and the overlay path cost inflation. This is due to the overlap of functionality between the two layers, unawareness of the other layer’s decisions, and lack of flexibility. We next investigate schemes that increase awareness of the native routing protocol and its parameters at the overlay layer. We consider three such approaches: Probabilistically Suppressed Overlay Rerouting, Deferred Overlay Rerouting and Follow-on Suppressed Overlay

Recent proposals for network virtualization provide a promising way to overcome the Internet ossification. The key idea of network virtualization is to build a diversified Internet to support a variety of network services and architectures through a shared substrate. A major challenge in network virtualization is the assigning of substrate resources to virtual networks (VN) efficiently and on-demand. This paper focuses on two versions of the VN assignment problem: VN assignment without reconfiguration (VNA-I) and VN assignment with reconfiguration (VNAII). For the VNA-I problem, we develop a basic scheme as a building block for all other advanced algorithms. Subdividing heuristics and adaptive optimization strategies are then presented to further improve the performance. For the VNA-II problem, we develop a selective VN reconfiguration scheme that prioritizes the reconfiguration of the most critical VNs. Extensive simulation experiments demonstrate that the proposed algorithms can achieve good performance under a wide range of network conditions.

Disruption tolerant networks (DTNs) are designed to overcome limitations in connectivity due to conditions such as mobility, poor infrastructure, and short range radios. DTNs rely on the inherent mobility in the network to deliver packets around frequent and extended network partitions using a store-carry-and-forward paradigm. However, missed contact opportunities decrease throughput and increase delay in the network. We propose the use of throwboxes in mobile DTNs to create a greater number of contact opportunities, consequently improving the performance of the network. Throwboxes are wireless nodes that act as relays, creating additional contact opportunities in the DTN. We propose algorithms to deploy stationary throwboxes in the network that simultaneously consider routing as well as placement. We also present placement algorithms that use more limited knowledge about the network structure. We perform an extensive evaluation of our algorithms by varying both the underlying routing and mobility models. Our results suggest several findings to guide the design and operation of throwbox-augmented DTNs

Message ferrying is a networking paradigm where a special node, called a message ferry, facilitates the connectivity in a mobile ad hoc network where the nodes are sparsely deployed. One of the key challenges under this paradigm is the design of ferry routes to achieve certain properties of end-to-end connectivity, such as, delay and message loss among the nodes in the ad hoc network. This is a difficult problem when the nodes in the network move arbitrarily. As we cannot be certain of the location of the nodes, we cannot design a route where the ferry can contact the nodes with certainty. Due to this difficulty, prior work has either considered ferry route design for ad hoc networks where the nodes are stationary, or where the nodes and the ferry move pro-actively in order to meet at certain locations. Such systems either require long-range radio or disrupt nodes' mobility patterns which can be dictated by non-communication tasks. We present a message ferry route design algorithm that we call the Optimized Way-points, or OPWP, that generates a ferry route which assures good performance without requiring any online collaboration between the nodes and the ferry. The OPWP ferry route comprises a set of way-points and waiting times at these way-points, that are chosen carefully based on the node mobility model. Each time that the ferry traverses this route, it contacts each mobile node with a certain minimum probability. The node-ferry contact probability in turn determines the frequency of node-ferry contacts and the properties of end-to-end delay. We show that OPWP consistently outperforms other naive ferry routing approaches.

Multicast is an essential service in mobile ad hoc networks (MANETs). Numerous protocols have been proposed but none of them is directly applicable in sparse MANETs, which are a form of disruption/delay tolerant networks (DTNs). In this paper, we consider multicasting in sparse MANETs with focus on two data dissemination schemes, epidemic routing (ER) and message ferrying (MF). With necessary group management schemes, both schemes can be extended for multicast. However, their performance is scenario-dependent. With this observation, a set of multicast protocols combining the essentials of MF and ER are proposed. In particular, we propose adaptive protocols targeting a balance between transmission efficiency and timely delivery in different scenarios. With simulations, we evaluate the performance of these protocols

In this work, we examine the feasibility of vehicles acting as data relays between roadside base-stations. Vehicular networks (VANETs) can be exploited due to the constrained and predictable motion of the vehicles along the roadways. We consider the feasibility of data relaying as a cost-effective scheme to provide virtual data paths between roadside base-stations. We develop a suit of protocols to achieve this relaying operation. Our results indicate that throughput on the order of 4.5 Mbps (for a peak rate of 11 Mbps) is obtained with minimal overhead for various scenarios. In scenarios where as low as 5% of the vehicles are equipped, the throughput obtained is in the order of 2 Mbps

As technology rapidly progresses, more devices will combine both communication and mobility capabilities. With mobility in devices, we envision a new class of proactive networks that are able to adapt themselves, via physical movement, to meet the needs of applications. To fully realize these opportunities, effective control of device mobility and the interaction between devices is needed. In this paper, we consider the message ferrying (MF) scheme which exploits controlled mobility to transport data in delay-tolerant networks, where end-to-end paths may not exist between nodes. In the MF scheme, a set of special mobile nodes called message ferries are responsible for carrying data for nodes in the network. We study the use of multiple ferries in such networks, which may be necessary to address performance and robustness concerns. We focus on the design of ferry routes. With the possibilities of interaction between ferries, the route design problem is challenging. We present algorithms to calculate routes such that the traffic demand is met and the data delivery delay is minimized. We evaluate these algorithms under a variety of network conditions via simulations. Our goal is to guide the design of MF systems and understand the tradeoff between the incurred cost of multiple ferries and the improved performance. We show that the performance scales well with the number of ferries in terms of throughput, delay and resource requirements in both ferries and nodes.

Summary form only given. Discrete event simulation has been used in the evaluation of computer communications networks for three or four decades. Over this period of time our simulation capability has improved significantly due to the efforts of the simulation research community. There has also been significant progress over the years by the networking research community in understanding the use of simulation in the design and evaluation of network architectures, protocols and services. I will argue in this talk that, despite these advances, we still do not have an acceptable and widely-used methodology to simulate networks which often leads to the questioning of the credibility of simulation results. This can be attributed to many reasons, including 1) confusion and uncertainty within the networking community regarding the role that simulation plays in networking research, 2) fundamental limits that make it basically impossible to simulate Internet-scale networks, 3) the difficulty in building realistic network models and 4) the lack of acceptable standards for validity and repeatability of simulation experiments. I will suggest a high-level research agenda that addresses these issues with the ultimate aim of enriching the networking research community's ability to use simulation as a meaningful tool for performance evaluation and prediction.

Delay tolerant networks (DTNs) are mobile wireless networks that are characterized by frequent partitions and potentially long message delivery delays. Such networks have the potential for use in important application environments where energy sources are limited. Therefore, efficient power management mechanisms are necessary to allow these networks to operate over a long period of time. In this paper, we leverage the observation that many DTNs are characterized by sparse connectivity, providing the opportunity to save energy by aggressively disabling node radios (sleeping). The major challenge is to balance sleeping periods with wake-up periods so that valuable and infrequent communication opportunities between nodes are not missed. We develop a power management framework that allows a node to save energy while missing few communication opportunities. The framework is tailored to the available knowledge about network connectivity over time. Further, the framework supports an explicit tradeoff between energy savings and connectivity, so that network operators can choose, for example, to conserve energy at the cost of reduced message delivery performance. We evaluate our mechanisms using ns-2 simulations. Our results show that our power management mechanisms consume from 10 % to 50 % of the energy expended when the network operates without power management. These energy savings come at the cost of some performance degradation when available knowledge is incomplete, though our tuning parameter allows a rich set of tradeoffs between energy consumption and performance.

Predicting the throughput of large TCP transfers is important for a broad class of applications. This paper focuses on the design, empirical evaluation, and analysis of TCP throughput predictors. We first classify TCP throughput prediction techniques into two categories: Formula-Based (FB) and History-Based (HB). Within each class, we develop representative prediction algorithms, which we then evaluate empirically over the RON testbed. FB prediction relies on mathematical models that express the TCP throughput as a function of the characteristics of the underlying network path. It does not rely on previous TCP transfers in the given path, and it can be performed with non-intrusive network measurements. We show, however, that the FB method is accurate only if the TCP transfer is window-limited to the point that it does not saturate the underlying path, and explain the main causes of the prediction errors. HB techniques predict the throughput of TCP flows from a time series of previous TCP throughput measurements on the same path, when such a history is available. We show that even simple HB predictors, such as Moving Average and Holt-Winters, using a history of few and sporadic samples, can be quite accurate. On the negative side, HB predictors are highly path-dependent. We explain the cause of such path dependencies based on two key factors: the load on the path and the degree of statistical multiplexing.

No abstract available.

The message ferrying (MF) scheme has been proposed as a strategy for providing connectivity in sparse partitioned ad hoc networks. A set of nodes, called ferries, are responsible for carrying messages for all nodes in the network. A ferry periodically moves around the deployed area along a pre-determined route and relays messages between mobile nodes which otherwise cannot communicate with each other directly. The MF scheme relies on the ferry to provide connectivity and is vulnerable to a single point of failure. Also, mobile nodes might take turns to be a ferry since they normally have limited resources. Therefore, ferry replacement is important for robustness in MF deployment. We propose two ferry replacement protocols: in the designation scheme, the ferry designates its successor; in the distributed election approach, nodes collaborate and elect one node among themselves as the ferry replacement. We evaluate the performance of these two replacement protocols through comprehensive simulation.

The dynamic behavior of the Internet's transmission resources makes it difficult to provide perceptually good quality streaming video. Scalable video encoding techniques have been proposed to deal with this problem. However, an encoded video generally exhibits significant data rate variability to provide consistent visual quality. We are, therefore, faced with the problem of accommodating the mismatch between the available bandwidth variability and the encoded video variability. We investigate quality adaptation algorithms for scalable encoded variable bit-rate video over the Internet. Our goal is to develop a quality adaptation scheme that maximizes perceptual video quality by minimizing quality variation, while at the same time increasing the usage of available bandwidth. We propose an optimal adaptation algorithm and a real-time adaptation algorithm based on whether the network conditions are known a priori. Experimental results show that the real-time adaptation as well as the optimal adaptation algorithm provide consistent video quality when used over both TCP-friendly rate control (TFRC) and transmission control protocol (TCP).

Multicast delivery is an efficient approach to the provision of a video-on-demand (VoD) service. Interacting with the video stream is a desirable feature for users. However, it is a challenging task to provide the functionality in the multicast environment because a lot of users share multicast delivery channels. In this paper, we propose an active buffer management technique to provide interactive functions in broadcast VoD systems. In our scheme, the client can selectively prefetch segments from broadcast channels based on the observation of the play point in its local buffer. The content of the buffer is adjusted in such a way that the relative position of the play point is kept in the middle part of the buffer. Our simulations show that the active buffer management scheme can implement interactive actions through buffering with a high probability in a wide range of user interaction levels.

The heterogeneity of the Internet's transmission resources and end system capability makes it difficult to agree on acceptable traffic characteristics among the multiple receivers of a multicast video stream. Three basic approaches have been proposed to deal with this problem: 1) multicasting the replicated video streams at different rates; 2) multicasting the video encoded in cumulative layers; and 3) multicasting the video encoded in noncumulative layers. Even though there is a common belief that the layering approach is better than the replicated stream approach, there have been no studies that compare these schemes. This paper is devoted to such a systematic comparison. Our starting point is an observation (substantiated by results in the literature) that a bandwidth overhead is incurred by encoding a video stream in layers. We argue that a fair comparison of these schemes needs to take into account this overhead, as well as the specifics of the encoding used in each scheme, protocol complexity, and the topological placement of the video source and the receivers relative to each other. Our results show that the believed superiority of layered multicast transmission relative to replicated stream multicasting is not as clear cut as is widely believed and that there are indeed scenarios where replicated stream multicasting is the preferred approach.

In this paper, we propose a multisegment optical network framework as a tool to solve a generalized category of problems related to end-to-end provisioning over interconnected optical networks. Based on the multisegment framework, we developed routing schemes for multigranularity multidomain optical networks. For examples of regional all-optical networks interconnected over an all-optical WDM backbone under a variety of traffic conditions, we present and compare numerical results. The performance results demonstrated the ability of our schemes to handle various network conditions under different control plane architectures.

We propose a cooperative patching architecture to achieve continuous live video streaming to a set of cooperative but unreliable end hosts. In this design, each end host caches an initial portion of the video content before playback. It then keeps the video that has been played out for a certain time before discarding it. An end host maintains a list of patching parents, and retrieves lost data from one of its patching parents. Any end host that has the requested video content can be a patching parent. Several parent selection algorithms are proposed and evaluated in this paper. This architecture relieves server load by completely shifting video patching responsibility to the client side. Video content is replicated in multiple locations across the overlay network to provide fast and timely data recovery. Cooperative patching is especially advantageous for legacy video systems, since it does not require modification of the video server. Simulation experiments demonstrate that our design can achieve continuous video streaming with moderate cost.

We consider the problem of how to enable the streaming of live video content from a single server to a large number of clients. One recently proposed approach relies on the cooperation of the video clients in forming an application layer multicast tree over which the video is propagated. Video continuity is maintained as client departures disrupt the multicast tree, using multiple description coded (MDC) streams multicast over several application layer trees. While this maintains continuity, it can cause video quality fluctuation as clients depart and trees are reconstructed around them. In this paper we develop a scheme using the transmission of a single-description coded video over an application layer multicast tree formed by cooperative clients. Video continuity is maintained in spite of tree disruption caused by departing clients using a combination of two techniques: 1) providing time-shifted streams at the server and allowing clients that suffer service disconnection to join a video channel of the time-shifted stream, and 2) using video patching to allow a client to catch up with the progress of a video program. Simulation experiments demonstrate that our design can achieve uninterrupted service, while not compromising the video quality, at moderate cost

Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.

A key challenge in peer-to-peer computing system is to provide decentralized and yet reliable services on top of a network of loosely coupled, weakly connected and possibly unreliable peers. This work presents an effective dynamic passive replication scheme designed to provide reliable multicast service in peer-cast, an efficient and self-configurable peer-to-peer end system multicast (ESM) system. We first describe the design of a distributed replication scheme, which enables reliable subscription and multicast dissemination of information in an environment of inherently unreliable peers. Then we present an analytical model to discuss its fault tolerance properties, and report a set of initial experiments, showing the feasibility and the effectiveness of the proposed approach.

The performance of large-scale wireless ad hoc networks is often limited by the broadcasting nature of the wireless medium and the inherent node energy constraints. While the impact of the former on network capacity extensively studied extensively in the literature, the impact of energy constraints has not received much attention. In this paper, we study the capacity limitations resulting from the energy supplies in wireless nodes. We define the energy-limited capacity of a wireless network as the maximum amount of data the network can deliver before the nodes run out of energy. This energy-limited capacity is an important parameter in networks where operating lifetime is critical, such as ad hoc networks deployed in hazardous environments and sensor networks. We study two types of static networks, networks without any infrastructure support and networks where base stations with unlimited energy are deployed to support data forwarding. We consider two kinds of traffic models motivated by ad hoc networks and sensor networks. We derive upper and lower bounds on the energy-limited capacity of these networks. While throughput has been shown to not scale with node density in static networks by previous studies, our results show that, depending on the energy consumption characteristics of wireless communication, the energy-limited capacity can scale well under both traffic models. In addition, we show that the deployment of base stations can improve the energy-limited capacity of the network, especially for networks with sensor traffic.

There is an increased interest, by content creators and owners, in content protection systems that provide the ability to control or restrict the content that can be shared on peer-to-peer file sharing systems. Some content protection systems have been proposed for centralized peer-to-peer systems (such as Napster) where a central authority controls all indexing and querying. These systems cannot be applied to decentralized peer-to-peer systems since they rely on a central server. Also, such systems limit the ability of end-users to effectively share content and can make the peer-to-peer distribution model resemble a client-server model in many respects. In this paper, we propose CITADEL, a novel content protection architecture designed to operate in decentralized peer-to-peer systems (such as Gnutella). CITADEL enforces a range of protection policies while maintaining an open peer-to-peer distribution model. CITADEL builds a protected file sharing environment over a normal peer-to-peer network using secured content objects and file sharing software enhanced to perform protection operations. A flexible content importation system that is part of CITADEL allows all users to insert new content as well as additional copies of protected content.

Analysis of server logs from multimedia servers, a FTP server, and a web server suggest that irrespective of the content type and protocol used to retrieve it, the small percentage of files that account for the most load on the server exhibit a very dynamic popularity behavior. This observation has implications for content dissemination techniques like caching, server replication, content distribution networks, and multicast. This paper focuses on the impact of multimedia popularity on multicast scheduling. Guided by the file dynamics patterns observed in the server logs, we generate synthetic multimedia server logs with varying number of server accesses and evaluate existing multicast scheduling schemes in terms of client latency and reneging of requests. Since existing scheduling schemes do not adapt gracefully to changing access conditions, we develop MWT, a new multicast scheduling scheme. MWT is fair to all multimedia files and reduces reneging, leading to better utilization of server resources during heavy access conditions.

In this paper we present three wavelength routing algorithms, "end-to-end", concatenated shortest path" and "hierarchical routing" for large-scale optical networks where optical paths traverse a number of networking segments interconnected by gateways. We analyze them with respect to the type of traffic, i.e. global vs. local and consider different requirements on wavelength routing based on gateway adaptation capabilities (wavelength merging, conversion or waveband interchange). Finally, for examples of regional all-optical networks interconnected over an all-optical WDM backbone under a variety of traffic conditions, we present and compare numerical results of blocking performances of different routing algorithms and gateway selection strategies.

Multicast routing research efforts have mostly focused on the host-group model in which multicast packets are addressed to a host group. Another multicast routing approach uses multidestination addressing, where a multicast packet carries a list of the unique (unicast) addresses of all the group members. This form of routing uses limited or no additional state beyond the existing unicast routing tables. It, therefore, scales well with the number of multicast sessions but does not scale well with the multicast group size and, in fact, requires the size of the group to be below a certain threshold. In this paper, we envision a future scenario in which both host-group and multidestination addressing routing approaches coexist within the Internet. We develop a dynamic routing context for this scenario wherein a multicast session can adapt among different routing configurations depending on the multicast group size and how this size changes over time. We consider three routing options: 1) a single multi-destination addressed flow - suitable for small-group sessions, 2) multiple multi-destination addressed flows - suitable for medium-group sessions and 3) a single host-group addressed flow - suitable for large-group sessions. Our work is concerned with the development and evaluation of protocols that allow a multicast session to dynamically switch among these three routing options as the size of the session changes.

Peer-to-peer systems have quickly become a popular way for file sharing and distribution. In this paper, we focus on the subsystem consisting of peers and their actions relative to a specific file and develop a simple theoretical file-centric model for the subsystem. We begin with a detailed model that tracks the complete system state. To deal with the large system state space, we investigate a decomposed model, which not only greatly reduces the complexity of solving the system, hut also provides a flexible framework for modeling multiple classes of peers and new system features. Using the model, we can study performance measures of a system, such as throughput, success probability of a file search, and number of file replicas in the system. Our model can also be used to understand the impact of user behavior and new system features. As examples, we investigate the effect of freeloaders, holding-enabled downloading and decoys in the paper.

In the current Internet, many applications start sessions with multiple connections to multiple servers in order to expedite the reception of data. One may argue that such aggressive behavior leads to unfair sharing of bandwidth using the current per-connection rate allocation methods. Sessions with more connections get a higher total rate than competing sessions with fewer connections. In this paper, we explore the issue of fairness of rate allocation from a session point of view. We define a multipoint-to-point session as a set of point-to-point connections started from multiple servers to a client in order to transfer an application-level object. We present session fairness definitions, propose algorithms to achieve these definitions, and compare the resulting allocations with the traditional connection fair algorithm. It is clear from our evaluations that the session fair algorithms proposed achieve a more fair distribution of session rates than the connection fair algorithm, by redistributing the rates claimed by sessions with more connections. We present some initial thoughts on the challenges involved in implementing the session fair algorithms proposed.

Dynamic behavior of the Internet's transmission resources makes it difficult to provide perceptually good quality of streaming video. MPEG-4 Fine-Grained Scalable coding is proposed to deal with this problem by distributing the data in enhancement layers over a wide range of bit rates. However, encoded video also exhibits significant data rate variability to provide a consistent quality video. We are, therefore, faced with the problem of trying to accommodate the mismatch between the available bandwidth variability and the encoded video variability. In this paper, we investigate quality adaptation of the layered VBR video generated by MPEG-4 FGS. Our goal is to develop a quality adaptation scheme that maximizes perceptual video quality through minimizing quality variation while at the same time increasing the usage of available bandwidth. We develop an optimal adaptation scheme and an online heuristic based on whether the network conditions are known a priori. Experimental results show that the online heuristic as well as the optimal adaptation algorithm provide consistent video quality when used over both TFRC and TCP.

The need to support multicast (or multipoint) communication in the Internet has been recognized for a long time. Significant effort has been expended over the last three decades by networking researchers and practitioners in designing and building multicast support capability within the Internet. In addition, several research efforts have demonstrated that highly scalable and desirable multimedia and information services can be deployed on top of a multicast-capable Internet infrastructure. Despite this, wide-spread availability and use of multicast communication is lacking in the Internet today. In this talk I will consider the history of multicast communication and services. This will be done in the context of an evolutionary model that explains the current state of multicast deployment. This exploration allows us to draw some lessons regarding the evolution of the Internet and how our approach to research and deployment can affect this evolution.

We investigate the design of a reputation system for decentralized unstructured P2P networks like Gnutella. Having reliable reputation information about peers can form the basis of an incentive system and can guide peers in their decision making (e.g., who to download a file from). The reputation system uses objective criteria to track each peer's contribution in the system and allows peers to store their reputations locally. Reputation are computed using either of the two schemes, debit-credit reputation computation (DCRC) and credit-only reputation computation (CORC). Using a reputation computation agent (RCA), we design a public key based mechanism that periodically updates the peer reputations in a secure, light-weight, and partially distributed manner. We evaluate using simulations the performance tradeoffs inherent in the design of our system.

Quality-of-service (QoS) techniques and server replication are two complementary approaches that can improve the performance observed by users. QoS techniques provide differentiated service to meet the diverse needs of applications; server replication enables load balancing across a set of servers. To combine the two approaches, we need to address one important question: how to select a server among a replicated set that satisfies the user QoS requirement. We propose a probing-based protocol to discover network resources and make reservations for requests in differentiated service networks. This approach optimizes network resource utilization with reasonable signaling overhead. Furthermore, we compare five heuristics that can be used for server selection. We also investigate two methods that can reduce probing overhead, namely caching and the technique of probing from a subset of servers.

One problem in securing group communication is the scalability of group key management in dynamic multicast sessions. The main challenge arises when a member leaves the multicast session and a rekeying of the group is required to prevent the departing member from accessing the information being multicast after they leave. Recent research developed the logical key hierarchy (LKH) protocol which uses a tree structuring of receivers and requires O(log(n)) rekeying messages when a member leaves. It has also been demonstrated that /spl Omega/(log(n)) is the best one can achieve if strict confidentiality and non-collusion are required. While strict non-collusion is required for some highly sensitive data, we argue that some commercial content delivery applications will be extremely cost sensitive and willing to tolerate some small level of collusion. In this paper we consider the question of how one might trade off the message cost of rekeying with some increased vulnerability to collusion. We consider a range of protocols. In one extreme is LKH which is completely immune from collusion. On the other extreme is a protocol based on the linear ordering of receivers (LORE), which requires O(1) messages for rekeying but in which any two receivers can collude. We describe a scheme using a hybrid structuring of receivers (HySOR) which is tunable between the LKH and LORE extremes and by which one can trade off some vulnerability to collusion for a decrease in rekeying message cost. We provide analytical as wen as simulation results to investigate the performance of HySOR and its tunability along the collusion/scalability spectrum.

Real-world traffic traces are crucial for Internet research, but only a very small percentage of traces collected are made public. One major reason why traffic trace owners hesitate to make the traces publicly available is the concern that confidential and private information may be inferred from the trace. We focus on the problem of anonymizing IP addresses in a trace. More specifically, we are interested in prefix-preserving anonymization in which the prefix relationship among IP addresses is preserved in the anonymized trace, making such a trace usable in situations where prefix relationships are important. The goal of our work is two fold. First, we develop a cryptography-based, prefix-preserving anonymization technique that is provably as secure as the existing well-known TCPdpriv scheme, and unlike TCPdpriv, provides consistent prefix-preservation in large scale distributed setting. Second, we evaluate the security properties inherent in all prefix-preserving IP address anonymization schemes (including TCPdpriv). Through the analysis of Internet backbone traffic traces, we investigate the effect of some types of attacks on the security of any prefix-preserving anonymization algorithm. We also derive results for the optimum manner in which an attack should proceed, which provides a bound on the effectiveness of attacks in general.

Multicast and anycast have received considerable attention due to their ability to support networked services. There are distinct and significant security vulnerabilities in both the multicast and anycast model including denial of service, theft or service, eavesdropping, and masquerading. The multicast problem requires a secure IGMP. The anycast problem requires secure anycast server advertisements. We generalize these two problems into a problem of group access control and propose Gothic, a complete architecture for providing group access control. Gothic centers around a novel authorization architecture. This is complemented by a proposal for a group policy management system that allows the group owner to be authenticated before being allowed to specify the group access rights. This system can be applied to other works that involve group policy. We show how Gothic operates in a number of environments including application-layer multicast, source-specific multicast, application-layer anycast and global IP-anycast. We evaluate the security and scalability of the architecture and show that it improves scalability over previous solutions while maintaining or increasing the level of security. We also propose methods of integrating Gothic with the group key management system and content distribution tree. We propose and evaluate a group access control aware group key management technique that leverages the existence of a group access control system to substantially reduce overhead.

A Video-on-Demand (VoD) service offers a large selection of videos from which customers can choose. Designers of VoD systems strive to achieve low access latency for customers. One approach that has been investigated by several researchers allows the server to batch clients requesting the same video and to serve clients in the same batch with one multicast video stream. This approach has the advantage that it can save server resources as well as server access and network bandwidth, thus allowing the server to handle a large number of customers without sacrificing access latency. VoD server replication is another approach that can allow a VoD service to handle a large number of clients, albeit at the additional cost of providing more servers. While replication is an effective way to increase the service capacity, it needs to be coupled with appropriate selection techniques in order to make efficient use of the increased capacity. In this paper, we investigate the design of server selection techniques for a system of replicated batching VoD servers. We design and evaluate a range of selection algorithms as they would be applied to three batching approaches: Batching with Persistent Channel Allocation, Patching, and Hierarchical Multicast Stream Merging (HMSM). We demonstrate that server replication combined with appropriate server selection scheme can indeed be used to increase the capacity of the service leading to improved performance.

We formulate and investigate fundamental problems that arise when multicast servers, that deliver content to multiple clients simultaneously, are replicated to enhance scalability and performance. Our study consists of two parts. First, we consider the problem under the assumption that the multicast clients are static for the duration of the multicast content distribution session. In this context, we examine two models for server behavior: fixed-rate servers, which transmit at a constant rate, and rate-adaptive servers, which adapt their transmission rate based on network conditions and/or feedback from clients. In both cases, we show that general versions of the client assignment problems are NP-hard. We then develop and evaluate efficient algorithms for interesting special cases, as well as heuristics for general cases. Second, we consider the case in which the set of clients changes dynamically during the multicast content distribution session. We again consider both fixed-rate and rate-adaptive servers. We formulate the problem as a Markov decision process, capturing the costs associated with trees, as well as the transition costs to dynamically change the trees. We use the properties of optimal solutions for small examples to develop a set of dynamic server selection heuristics.

Multicast communication enables a server to send content to multiple clients at the same time through a multicast tree. To deal with the heterogeneity of client capacities, multiple multicast groups can be used to allocate clients with similar capacity to the same group, so that the performance perceived by clients can be improved. We investigate the problem of allocating clients to constrained multicast servers, which, similar to clients, have different capacities. We explore some interesting issues raised by the constraints and propose an optimal solution to the allocation problem. We evaluate the solution and show substantial performance gain for our algorithm over those considering the server constraints separately.

Presents an approach for creating distributed, component-based simulations of communication networks by interconnecting models of sub-networks drawn from different network simulation packages. This approach supports the rapid construction of simulations for large networks by reusing existing models and software, and fast execution using parallel discrete event simulation techniques. A dynamic simulation backplane is proposed that provides a common format and protocol for message exchange, and services for transmitting data and synchronizing heterogeneous network simulation engines. In order to achieve plug-and-play interoperability, the backplane uses existing network communication standards and dynamically negotiates among the participant simulators to define a minimal subset of required information that each simulator must supply, as well as other optional information. The backplane then automatically creates a message format that can be understood by all participating simulators and dynamically creates the content of each message by using callbacks to the simulation engines. We describe our approach to interoperability as well as an implementation of the backplane. We present results that demonstrate the proper operation of the backplane by distributing a network simulation between two different simulation packages, ns2 and GloMoSim. Performance results show that the overhead for the creation of the dynamic messages is minimal. Although this work is specific to network simulations, we believe our methodology and approach can be used to achieve interoperability in other distributed computing applications as well.

As the Internet has grown in size and diversity of applications, two trends have emerged to provide good end-user perceived performance. First, servers are often replicated for better scalability of the service. Second, QoS approaches, such as the differentiated services framework, have been proposed as enhancement to the best-effort IP service. We are interested in the combination of these two trends; that is, replicated servers in QoS-based networks. We focus on the problem of selecting amongst replicated servers in the context of differentiated service networks. Our contributions are twofold. First, we design a QoS-based server-selection architecture. The architecture is scalable in the sense that server selection and resource reservation are done in an aggregated fashion and operate in the background, rather than being driven by individual client demand. At the same time, the architecture offers a fast response time to client requests for server selection. Second, we explore the design space implied by the architecture and evaluate various design options including signalling protocols, server selection/sorting algorithms and resource reservation granularity.

The heterogeneity of the Internet's transmission resources and end system capability makes it difficult to agree on acceptable traffic characteristics among the multiple receivers of a multicast video stream. Three basic approaches have been proposed to deal with this problem: 1) multicasting of replicated video streams at different rates, 2) multicasting the video encoded in cumulative layers, and 3) multicasting the video encoded in non-cumulative layers. Even though there is a common belief that the layering approach is better than the replicated stream approach, there has been no studies that compare these schemes. This paper is devoted to such a systematic comparison. Our starting point is an observation (substantiated by results in the literature) that a bandwidth penalty is incurred by encoding a video stream in layers. We argue that a fair comparison of these schemes needs to take into account this penalty as well as the specifics of the encoding used in each scheme, protocol complexity, and the topological placement of the video source and the receivers relative to each other. Our results show that the believed superiority of layered multicast transmission relative to stream replication is not as clear cut as is widely believed and that there are indeed scenarios where replication is the preferred approach.

Multicast applications can involve a large number of receivers with heterogeneous data reception capabilities. In a traditional single-rate multicast session, the transmission rate at the source is chosen to match the lowest capacity path to a receiver in the session. This can cause an under-utilization of higher capacity paths to other receivers. We have previously defined an inter-receiver fairness measure in order to quantify the effect of this underutilization. We also developed protocols that use this measure to guide the choice of the source rate for a single-rate session. In this paper we design and develop a multi-rate protocol in the context of an ATM ABR service to achieve better inter-receiver fairness for a multicast session. The multi-rate protocol we investigate is based on the use of destination set grouping (DSG) where the set of receivers in a multicast session is partitioned into disjoint subgroups. The transmitter carries a separate conversation with each subgroup. Based on a number of grouping heuristics, the DSG protocol attempts to find the partitioning of the receivers that maximizes the inter-receiver fairness of the session. The DSG protocol can result in a session receiving a higher bandwidth allocation when it is split into multiple connections. We address this issue by proposing a mechanism in which the connections split from a single multicast session are treated as a single aggregated-allocation connection (AAC). A set of examples demonstrate the effectiveness of the DSG scheme incorporating the AAC technique on improving inter-receiver fairness for multicast ABR sessions.

The memory resources required by network simulations can grow quadratically with the size of the simulated network. In simulations that use routing tables at each node to perform per-hop packet forwarding, the storage required for the routing tables is O(N/sup 2/), where N is the number of simulated network nodes in the topology. Additionally, the CPU time required in the simulation environment to compute and populate these routing tables can be excessive and can dominate the overall simulation time. We propose a new routing technique, known as Neighbor-Index Vectors, or NIx-Vectors, which eliminates both the storage required for the routing tables and the CPU time required to compute them. We show experimental results using NIx-Vector routing in the popular network simulator ns (S. McCanne and S. Floyd, 1997). With our technique, we achieve a near order of magnitude increase in the maximum size of a simulated network running ns on a single workstation. Further, we demonstrate an increase of two orders of magnitude in topology size (networks as large as 250000 nodes) by using this technique and running the simulation in parallel on a network of workstations.

Server replication improves the ability of a service to handle a large number of clients. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the "best" server, according to some optimality criteria. In the anycasting communication paradigm, a sender communicates with a receiver chosen from an anycast group of equivalent receivers. As such, anycasting is well suited to the problem of directing clients to replicated servers. This paper examines the definition and support of the anycasting paradigm at the application-layer, providing a service that uses an anycast resolver to map an anycast domain name and a selection criteria into an IP address. By realizing anycasting in the application-layer, we achieve flexibility in the optimization criteria and ease the deployment of the service. As a case study, we examine the performance of our system for a key service: replicated Web servers. To this end, we develop an approach for estimating the response time that a client will experience when accessing given servers. Such information is maintained in the anycast resolver that clients query to obtain the identity of the server with the best estimated response time. Our performance collection technique combines server push with resolver probes to estimate the expected response time without undue overhead. Our experiments show that selecting a server using our architecture and estimation technique can improve the client response time by a factor of two over nearest server selection and by a factor of four over random server selection.

IP multicasting allows a source to define a multicast group address and receivers can dynamically join and leave this group. Currently the propagation of multicast packets is controlled by two scoping methods: TTL scoping and administrative scoping. Both of these approaches require the source to control the scope of the multicast. Receiver-based scoping allows a receiver to place conditions on its multicast join that must be met in order to join successfully and remain a member of the multicast group. Such a scoping mechanism would be useful in environments where the receiver incurs a cost for its membership of the multicast group. We describe two receiver-based scoping approaches: router-supported and end-to-end. The router-supported approach requires state to be maintained in routers while the end-to-end approach uses the multicast traceroute tool and does not require state maintenance by the routers. We evaluate the performance of these approaches in terms of their accuracy, bandwidth overhead and state requirements.

In this paper we investigate multicast server selection problems. First we give a definition of the static multicast server selection problem, in which we assume a set of static clients and multicast servers and consider how one might produce an optimal allocation of the clients to the servers. We use a transformation method for deriving multicast server selection algorithms from traditional multicast routing algorithms. To investigate the dynamic behavior of client join and leave and the cost incurred during the process, we next define the dynamic multicast server selection problem, in which the clients join and leave the multicast session dynamically. The goal is to produce an optimal allocation of clients to servers with an emphasis on how this allocation behaves over time. We formulate the problem as a Markovian decision process (MDP). Our analysis of the problem leads to two heuristics which we use to propose a simple selection algorithm. Our simulation compares the performance of our proposed algorithm with other multicast server selection algorithms.

A key technique for allowing servers to handle a large volume of requests for file transfers is to multicast the data to the set of requesting clients. Typically the paths from the server to the clients will be heterogeneous in bandwidth availability. Multiple-channel multicast (MCM) is an approach that can be used to handle this heterogeneity. In this approach the data is multicast over multiple channels, each addressed as a separate multicast group. Each receiver subscribes to a set of channels (i.e., joins the corresponding multicast groups) commensurate with its own rate capabilities. Of particular interest in the design of MCM schemes is the scheduling of data transmission across the multiple channels to accommodate asynchronous requests from clients. In this paper we present and analyze a new multiple-channel multicast approach called partition organization scheduling. The scheme is designed to result in good reception efficiency when compared to existing proposals while improving on their performance when other measures of interest are considered.

Discrete event simulation is widely used within the networking community for purposes such as demonstrating the validity of network protocols and architectures. Depending on the level of detail modeled within the simulation, the running time and memory requirements can be excessive. The goal of our research is to develop and demonstrate a practical, scalable approach to parallel and distributed simulation that will enable widespread reuse of sequential network simulation models and software. We focus on an approach to parallelization where an existing network simulator is used to build models of subnetworks that are composed to create simulations of larger networks. Changes to the original simulator care minimized, enabling the parallel simulator to easily track enhancements to the sequential version. We describe our lessons learned in applying this approach to the publicly available ns software package (McCanne and Floyd, 1997) and converting it to run in a parallel fashion on a network of workstations. This activity highlights a number of important problems, from the standpoint of how to parallelize an existing serial simulation model and achieving acceptable parallel performance.

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.

We consider an environment where one or more servers carry databases that are of interest to a community of clients. The clients are only intermittently connected to the server for brief periods of time. Clients carry a part of the database for their own processing and accumulate local updates while disconnected. We call this the Intermittently Connected Database (ICDB) environment. ICDBs have a wide variety of applications including sales force automation, insurance claim processing, and mobile workforces. Our focus is on the problem of update propagation at the server in ICDBs and the associated processing at the clients. The typical client-centric approach involves the communication and processing of updates and transactions on a per-client basis, ignoring the overlap of data between clients. The complexity of this approach is in the order of the number of connecting clients, thereby limiting the scalability of the server. We propose a data-centric approach which clusters data into groups and assigns to each client one or more of these groups. The proposed scheme results in server processing complexity on the order of the number of groups, which we control. We propose various techniques for grouping and discuss the processing required at the clients to enable the grouping approach. While the client-centric approach is expected to significantly degrade with the increasing number of clients, we expect that a properly designed grouping scheme will sustain a number of clients that is significantly larger. A prototype has been developed and performance studies are in progress.

In Internet multicast, the set of receivers can be dynamic with receivers joining and leaving a group asynchronously and without the knowledge of the source(s). The Internet today uses source-based scoping by which the source determines how far its multicast transmissions will propagate. This mechanism, however, does not allow a receiver to bound the number of hops added to a multicast routing tree as a result of its join request or its continued membership. In this paper we explore the use of receiver-based scoping, in which a receiver's join request is augmented with one or more scope values. By use of these values, the receiver specifies its wish to join and remain in the multicast group as long as the number of additional hops its membership incurs is within its declared scope. In environments where a multicast receiver incurs a cost in relation to its incremental resource usage, this scoping technique can be used to give the receiver direct control over this cost. The paper is concerned with discussion of the design of the receiver-based scoping mechanism and its possible use within multicast applications. We also consider the implementation of the mechanism as an extension to the existing Internet multicast infrastructure in a manner that is independent of the multicast routing protocol in use.

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).

Server replication is an approach often used to improve the ability of a service to handle a large number of clients. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the best server, according to some optimality criteria. In this paper we target an environment in which servers are distributed across the Internet, and clients identify servers using our application-layer any-casting service. Our goal is to allocate servers to clients in a way that minimizes a client's response time. To that end, we develop an approach for estimating the performance that a client would experience when accessing particular servers. Such information is maintained in a resolver that clients can query to obtain the identity of the server with the best response time. Our performance collection technique combines server push with client probes to estimate the expected response time. A set of experiments is used to demonstrate the properties of our performance determination approach and to show its advantages when used within the application-layer anycasting architecture.

As the number and variety of Web- and network-based applications continues to increase, so does the need for flexible communication protocols and services to support them. Traditionally, a major impediment to deployment of new protocols is the need to upgrade millions of end-systems with compatible implementations. At the same time, Java-a language explicitly designed to support development and distribution of new applications via the Web-is emerging as a (potentially) ubiquitous system platform. It is therefore natural to consider whether Java might speed the introduction of protocols to better support new applications. We investigate the tradeoffs involved in using Java for protocol implementation and deployment. Using insights from a Java-based protocol suite and supporting subsystem we have implemented, we describe the benefits of using the Java language and quantify the performance cost of implementing a protocol in Java for various combinations of interpretation and compilation. We find that the present performance cost of using Java-based protocols is roughly equivalent to four years of hardware performance gains, i.e., interpreted, Java-based protocol performance on current hardware is roughly equivalent to the performance of compiled C code on four-year-old hardware.

Layered video multicast with retransmissions (LVMR) is a system for distributing video using layered coding over the Internet. The two key contributions of the system are: (1) improving the quality of reception within each layer by retransmitting lost packets given an upper bound on recovery time and applying an adaptive playback point scheme to help achieve more successful retransmission, and (2) adapting to network congestion and heterogeneity using hierarchical rate control mechanism. This paper concentrates on the rate control aspects of LVMR. In contrast to the existing sender-based and receiver-based rate control in which the entire information about network congestion is either available at the sender (in sender-based approach) or replicated at the receivers (in receiver-based approach), the hierarchical rate control mechanism distributes the information between the sender, receivers, and some agents in the network in such a way that each entity maintains only the information relevant to itself. In addition to that, the hierarchical approach enables intelligent decisions to be made in terms of conducting concurrent experiments and choosing one of several possible experiments at any instant of time based on minimal state information at the agents in the network. Protocol details are presented in the paper together with experimental and simulation results to back our claims.

In a multicast ABR service, a connection is typically restricted to the rate allowed on the bottleneck link in the distribution tree from the source to the set of receivers. Because of this, receivers in the connection can experience inter-receiver unfairness, when the preferred operating rates of the receivers are different. In this paper we explore the issue of improving the inter-receiver fairness in a multicast ABR connection by allowing the connection to operate at a rate higher than what is allowed by the multicast tree's bottleneck link. Since this can result in cell loss to some receivers, we operate with the knowledge of each receiver's application-specific loss tolerance. The multicast connection rate is not allowed to increase beyond the point where the cell loss on a path to a receiver exceeds this receiver's loss tolerance. Based on these ideas we develop an inter-receiver fairness measure and a technique for determining the rate that maximizes this measure. We show possible switch algorithms that can be used to convey the parameters needed to compute the function to the connection's source. In addition we develop a global network measure that helps us assess the effect of increasing inter-receiver fairness on the total network delivered throughput. We also briefly explore improving inter-receiver fairness through the use of multiple virtual circuits to carry traffic for a single multicast session. A set of examples demonstrate the use of the inter-receiver fairness concept in various network scenarios.

The anycasting communication paradigm is designed to support server replication by allowing applications to easily select and communicate with the "best" server, according to some performance or policy criteria, in a group of content-equivalent servers. We examine the definition and support of the anycasting paradigm at the application layer, providing a service that maps anycast domain names into one or more IP addresses using anycast resolvers. In addition to being independent from network-layer support, our definition includes the notion of filters, functions that are applied to groups of addresses to affect the selection process. We consider both metric-based filters (e.g., server response time) and policy-based filters.

We address the issue of providing efficient mechanisms for multidestination communication over one class of lightwave wavelength division multiplexing (WDM) architectures, namely, single-hop networks with tunability provided only at the receiving side. We distinguish a number of multicast traffic types, we present a number of alternative broadcast/multicast time-division multiple-access (TDMA) schedules for each type, and we develop heuristics to obtain schedules that result in low average packet delay. One of our major contributions is the development of a suite of adaptive multicast protocols which are simple to implement, and have good performance under changing multicast traffic conditions.

Deploying protocols is an expensive and time-consuming process today. One reason is the high cost of developing, testing, and installing protocol implementations. To reduce this difficulty, protocols are developed and executed within environments called protocol subsystems, and protocol software is often ported instead of being coded from scratch. Unfortunately, today a variety of protocol subsystems offer a plethora of features, functionality, and drawbacks; the differences among them often reduce the portability and reusability of protocol code, and therefore present barriers to the deployment of new protocols. In this paper, we consider differences in subsystems and their effect on the portability and reusability of protocols and protocol implementations. We then propose two different approaches, each optimized for a different situation, that allow protocol code implemented in one subsystem to be used without modification within other subsystems, and thus reduce the barriers to protocol deployment. We relate our experiences designing, implementing, and measuring the performance of each approach using, as a baseline, an AppleTalk protocol stack we have developed.

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.

Real-time multicast video distribution is an important component of many multimedia applications. Our work addresses the fairness problem in feedback-controlled multicast video distribution systems over best effort networks (such as the Internet). We have proposed, implemented and experimented with a scheme called destination set grouping (DSG), where a source maintains a small number of video streams, all carrying the same video but each targeted at receivers with different capabilities. Each stream is feedback-controlled within prescribed limits by its group of receivers. Receivers may move among groups as their capabilities or the capabilities of the network paths leading to them change. In this paper, we focus on the potential for network overloading caused by the transmission of multiple replicated streams. We propose a number of mechanisms to be implemented at the source and the receivers that can help avert this problem. We also describe an evaluation of these schemes using simulation, and discuss a comparison of replicated-stream versus layered-encoding approaches.

Because protocol software is difficult and expensive to implement and test, it is often ported between systems instead of rewritten from scratch. Unfortunately, porting protocol software can be as difficult as from-scratch development, due to inherent differences in subsystem design. Thus, protocol subsystems can have a profound effect on the portability of a protocol implementation. We propose an approach permitting the incorporation of new protocols into a subsystem other than their "native" one without the drawbacks or expense of porting and original development. Our approach is based on protocol module encapsulation, which allows unmodified protocol code developed for one protocol subsystem to be used within another. We relate our experiences designing, implementing, and measuring the performance of our protocol encapsulation modules, using an AppleTalk protocol stack as a baseline.

In a fair multicast video distribution scheme each receiver should receive a video stream with a quality that is commensurate with its capabilities or the capabilities of the path leading to it, regardless of other receivers or network paths. This fairness problem results from the fact that multicast communication trades economy of bandwidth with granularity of control. Distributing video using individual feedback-controlled point-to-point streams results in high bandwidth utilization but the granularity of control is high as communication parameters can be negotiated individually with each receiver. In contrast, using a single multicast stream has good bandwidth economy, but very low granularity of control. In this paper we propose, implement and experiment with a system that spans the spectrum represented by the two extremes above. In the scheme, called destination set grouping (DSG), a source maintains a small number of video streams, carrying the same video but each targeted at receivers with different capabilities. Each stream is feedback-controlled within prescribed limits by its group of receivers. Receivers may move among streams as their capabilities or the capabilities of the network paths leading to them change. The scheme is shown to improve fairness significantly at a small bandwidth cost.

Protocol software is often difficult and expensive to implement and test in today's computing environments. Several things are done to reduce this difficulty: communications software is subdivided into layers and organized into a protocol graph; communications software is developed within a protocol or networking subsystem; and it is often ported rather than developed from scratch. Today, a multitude of subsystems offer different features, functionality, and drawbacks; the differences among them often reduce portability and efficiency of protocol code. We consider these differences in subsystems and their effect on the portability and performance of protocol implementations. We propose an approach for combining the better features of protocol subsystems by constructing protocol graphs composed of protocols residing in different subsystems. Our approach uses adapter modules spanning the inter-subsystem boundary. We relate our experiences designing, implementing, and measuring the performance of several such adapters using an AppleTalk protocol stack we have developed as a baseline.

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.

In conventional multicast communication, the source carries a single conversation with all destination nodes. If a node on the path to any destination becomes congested the throughput to all destinations is reduced, thus treating same destination nodes unfairly. We consider a window-controlled multipoint connection and study the use of destination set grouping, where the destination set can be split into disjoint subgroups with the source carrying independent conversations with each subgroup. We present a dynamic grouping protocol which can adjust the grouping and the window sizes per group in response to changing network conditions. The performance of the protocol is studied using simulation and compared with single-group multicasting.

Multiprotocol systems can be an important tool for achieving interoperability. As the number of protocols available on such systems grows, there is an increasing need for support mechanisms that enable users to effectively access these protocols. Of particular importance is the need to determine which of several protocols to use for a given communication task. In this work, we propose architectures for a protocol discovery system that uses protocol feedback mechanisms to determine which protocols are supported. We describe the issues related to protocol discovery and present feedback mechanisms necessary to support discovery. We present a prototype implementation of a discovery system that supports multiple protocols.

We present a novel architecture for providing a reliable multicast transport service over existing protocol stacks. These protocol stacks ordinarily support reliable unicast transport layer connections over a network layer which is capable of providing an unreliable multicasting service. We propose the addition of a new single connection emulation (SCE) sublayer between the unicast transport layer and the multicast network layer. This added layer mimics the single destination network layer interface to the transport layer and interfaces with the multicast network layer to provide the necessary multicast functionality. The new architecture also enables interactions between applications and the SCE, thus allowing the applications to control the semantics of the reliable multicast connection. We discuss the design issues that need to be considered when such a sublayer is to be introduced. We also discuss an implementation of this new approach using the TCP/IP protocol stack and present some preliminary experimental results.

We consider a generalization of the multiple access problem where it is necessary to identify a subset of the ready users, not all. The problem is motivated by several "response collection" applications that arise in distributed computing and database systems. In these applications, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents communicate over a shared channel. We define three collection objectives and investigate a suite of protocols that can be used to achieve these objectives. The protocols are based on the use of polling, TDMA, and group testing. Using a binomial respondent model we analyze and, where applicable, optimize the performance of the protocols. Our concern is with cost measures that reflect the computational load placed on the system, as well as the delay incurred for achieving a particular objective.>

Considers single-hop lightwave networks with stations interconnected using wave division multiplexing. The stations are equipped with tunable transmitters and/or receivers. A predefined, wavelength-time oriented schedule specifies the slots and the wavelengths on which communication between any two pairs of stations is allowed to take place. The authors define a wide variety of schedules and develop a general framework for analyzing their throughput performance for any number of available wavelengths, any tunability characteristics, and general (potentially nonuniform) traffic patterns. They then consider the optimization of schedules given the traffic requirements and present optimization heuristics that give near-optimal results. They also investigate how the number of available wavelengths (channels) affects the system throughput, and develop techniques to efficiently share the available channels among the network stations. As a result, they obtain systems that are easy to scale while having very good performance.>

The article considers the multicast-to-some generalization of the traditional multicast paradigm. In this form of communication, a multicast group is still associated with each multicast message. It is, however, only necessary for any randomly determined subset of the multicast group to receive a multicast message. This subset is not defined a priori nor is it necessarily the same from one multicast to the next for the same group. It explores the use of this "probabilistic" multicast communication paradigm to address scalability issues in the response collection application which arises in some distributed computing applications. It also shows how this form of multicast can be used to reduce the discarding of responses to the multicast message due to buffer overflow at the multicast source.>

Multiprotocol systems are a vital tool for achieving interoperability in today's heterogeneous communication networks. An important aspect of these systems is the need to determine which of the multiple available protocols will be used to carry out a given communication task; an uninformed choice can result in failure to communicate when communication should be possible. The authors consider ways to make information about hosts' supported protocol configurations available through directory services. They discuss various representation approaches, and describe a working implementation of a multiprotocol application exemplifying their approach.>

The authors address the open issue of providing efficient mechanisms for multi-destination communication over one class of lightwave WDM architectures, namely, single-hop networks. They suggest, analyze, and optimize several alternative approaches for broadcast/multicast. One of their major contributions is the development of a suite of adaptive multicast protocols which have very good performance, are very simple to implement, and are insensitive to propagation delays.>

This paper presents a suite of randomized broadcast protocols for the problem of broadcasting a message in multihop radio networks. The protocols are compared with the randomized broadcast protocol by R. Bar-Yehuda et al. (1989, 1991, 1992). The time complexity of one of the randomized broadcast protocols presented in this paper is shown, by simulation, to be much better than those of other protocols in most of the typical cases.>

The authors consider the use of parallelism and configurability to increase throughput and reduce protocol processing latencies. They obtain experimental results on parallel protocol performance using a prototype implemented on a shared memory multiprocessor. The results demonstrate the utility of parallel protocol processing, and they indicate the further research necessary for constructing viable communication protocols for large-scale parallel machines. Based on these experiences, the design of an object-oriented framework for parallel protocol programming which facilitates parallel protocol development and helps maximize protocol performance on a wide variety of multiprocessors is presented.>

The point-to-multipoint routing problem is studied for an asynchronous transfer mode (ATM) network that uses virtual paths (VPs). ATM networks with asymmetric and symmetric VPs are considered, and the performance factors studied are bandwidth and establishment and switching costs. A VP with intermediate exit, where a node that performs VP switching can copy the switched packets for the local destination, is proposed and studied. Mathematical formulations of multicast routing problems are presented, and heuristics for finding a low cost multicast routing tree, based on the transshipment simplex algorithm, are developed.>

An inclusive approach to achieving heterogeneous system interoperability based on the use of multiprotocol architectures is considered. A detailed description of a framework and model for describing and constructing multiprotocol architectures is given. A case study based on architectures that mix protocols from the OSI and Internet suites is then described. Solutions to the problem of determining which set of protocols to use for a particular communication task are proposed.>

The problem of collecting responses in multihop radio networks is considered. A given node is to collect a specified number of responses from nodes in a radio network. The problem arises in several applications of distributed systems. A deterministic protocol and a randomized protocol for the problem are presented. The two protocols are analyzed and their performances are compared.>

Single-hop lightwave networks with stations interconnected using wavelength-division multiplexing are considered. The stations are equipped with tunable transmitters and/or receivers. Coordination between the transmitting and receiving stations is achieved by assuming synchronous control and a predefined, frequency-time oriented schedule which specifies the slots and the wavelengths on which communication between any two pairs of stations is allowed to take place. The authors define and analyze, in terms of throughput, all possible types of schedules in the situation where the number of available wavelengths is equal to the number of stations. The results are valid for the general case, i.e., nonuniform traffic. The optimization of schedules, given the traffic requirements, is considered, and optimization heuristics that give near-optimal results are presented.>

An approach to improving the performance of point-to-multipoint automatic repeat request (ARQ) protocols is considered. The approach involves splitting the destination set into disjoint groups and having the source carry out independent time multiplexed conversations with each group. The performance of memoryless and limited-memory versions of stop-and-wait and go-back-N protocols was investigated and the question of how to pick an optimal grouping of nodes was addressed. The results indicate that destination set splitting can improve the throughput of point-to-multipoint ARQ protocols, particularly if the receivers' capabilities are not identical.>

A new protocol for maintaining replicated data that can provide both high data availability and low response time is presented. In the protocol, the nodes are organized in a logical grid. Existing protocols are designed primarily to achieve high availability by updating a large fraction of the copies, which provides some (although not significant) load sharing. In the new protocol, transaction processing is shared effectively among nodes storing copies of the data, and both the response time experienced by transactions and the system throughput are improved significantly. The authors analyze the availability of the new protocol and use simulation to study the effect of load sharing on the response time of transactions. They also compare the new protocol with a voting-based scheme.>

A generalization of the multiple access problem is considered where it is necessary to identify a subset of the ready users, not all. The problem is motivated by several response collection applications that arise in distributed computing and database systems. In these applications, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents communicate over a shared channel. Three collection objectives are defined, and a suite of protocols that can be used to achieve these objectives is investigated. The protocols are based on the use of polling, time division multiple access (TDMA) and group testing. Using a binomial respondent model, the performance of the protocols is analyzed and, where possible, optimized. The main concern is with cost measures that reflect the computational load placed on the system, as well as the delay incurred for achieving a particular objective.>

article Free Access Share on Multidimensional voting Authors: Mustaque Ahamad Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile , Mostafa H. Ammar Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile , Shun Yan Cheung Emory Univ., Atlanta, GA Emory Univ., Atlanta, GAView Profile Authors Info & Claims ACM Transactions on Computer SystemsVolume 9Issue 4Nov. 1991 pp 399–431https://doi.org/10.1145/118544.118552Online:01 November 1991Publication History 37citation564DownloadsMetricsTotal Citations37Total Downloads564Last 12 Months17Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A concept called multidimensional voting, in which the vote and quorum assignments are k-dimensional vectors of nonnegative integers and each dimension is independent of the others, is introduced. Multidimensional voting is more powerful than traditional weighted voting because it is equivalent to the general method for achieving synchronization in distributed systems which is based on coteries (sets of groups of nodes), but its implementation is easier than that of coteries. An efficient algorithm for finding a multidimensional vote assignment for any given coterie is described and examples of its use are shown. It is shown how multidimensional voting can be used to easily implement novel algorithms for synchronizing access to replicated data or to ensure mutual exclusion. These algorithms cannot be implemented by traditional weighted voting.>

A protocol for maintaining replicated data that can provide both high data availability and low response time is presented. Existing protocols are designed primarily to achieve high availability by updating a large fraction of the copies, which provides some (although not significant) load sharing. In the new protocol, transaction processing is shared effectively among nodes storing copies of the data, and both the response time experienced by transactions and the system throughput are improved significantly. Also presented is an analysis of the availability of the new protocol and simulation is used to study the effect of load sharing on the response time of transactions. The new protocol is also compared with a voting-based scheme.>

The process of searching for a resource in a distributed system whose nodes are connected through a store-and-forward network is modeled. Based on this model, a lower bound on the number of messages needed for finding a resource when nothing is known about its location is shown. The model also helps to establish some results about the complexity of finding optimal algorithms to locate a resource when the probability distribution for the location of the resource is known. It is shown that the optimization problem is NP-hard for general networks. An algorithm is developed for tree networks which can be specialized to polynomial algorithms for a class of trees. (The polynomial algorithms can be used as the basis of heuristic algorithms for general networks.) An application of this algorithm for path networks can be adapted to find optimal search algorithms for bidirectional ring networks.>

The problem is discussed of determining the vote assignment and quorum that yields the highest availability in a system where node availabilities can be different and the mix of the read and write operations is arbitrary. For this purpose, an enumeration algorithm is presented that can be used to find the vote and quorum assignments that need to be considered for achieving optimal availability. An analytical method is derived to evaluate the availability of a given system for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The algorithm can also be used to obtain the optimal performance when other measures are considered.>

A protocol is presented to locate (or find) named resources in a distributed system which uses the multicast capabilities of the underlying network. Each node in the network uses a sequence of node groups, and each node group is associated with a unique multicast address. To locate a resource, the searching node sequentially polls each one of the groups until the resource is found; this scheme is a generalization of both pure polling and broadcast. To obtain an optimal division of the nodes into multicast groups, the protocol is analyzed and an efficient algorithm is given that provides a group division minimizing the expected cost per location operation.>

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered.>

The authors develop a model and define performance measures for a replicated data system that makes use of a quorum-consensus algorithm to maintain consistency. They consider two measures: the proportion of successfully completed transactions in systems where a transaction aborts if data is not available, and the mean response time in systems where a transaction waits until data becomes available. Based on the model, the authors show that for some quorum assignment there is an optimal degree of replication beyond which performance degrades. There exist other quorum assignments which have no optimal degree of replication. The authors also derive optimal read and write quorums which maximize the proportion of successful transactions.>

The authors address the problem of determining how system parameters affect the performance of the location operations when hint tables are used. To this end they approximate a distributed system incorporating hint tables in its location strategy with an analytic model. They identify a set of parameters affecting the cost of location operations and provide a criterion to help decide whether the use of hint tables should be incorporated in the design of a given system. They give a set of examples to illustrate the usage of the analytic results. These include location using: broadcast in a broadcast network; name servers in a broadcast network; broadcast is a packet switched network and name servers in a packet switched network.>

The authors consider a flexible and automated two-stage manufacturing system that is externally controlled by computer-based equipment. Communication among the components of this integrated manufacturing system is accomplished over a local area network using a token-passing medium access procedure. Messages from the manufacturing system to the control computers may contain information about the progress of the manufacturing process. Based on this data, the control computers send instructions that serve to control and modify the manufacturing process. A model of such a system is formulated and analyzed, and a set of numerical examples is discussed. The objective is to understand how the efficiency of the manufacturing system is affected by the mechanism and parameters of the communication network.>

The authors present a resource (e.g. file, process) location scheme which utilizes the multicast communication capability of local area networks (LANs). In the scheme, the universe of resource names is partitioned into a relatively small number of groups and each group is assigned a unique address. Nodes storing the locations of resources belonging to a particular group instruct their network interfaces to receive all location messages sent to the group address. To locate a resource, a node first determines the address of the group to which the resource belongs, and a multicast message is then sent to the address. The algorithm performance is studied by simulation, and approximate closed-form solutions are derived for systems operating at heavy and low loads. The scheme's performance is compared with that of broadcast, and it is shown that the proposed scheme performs much better than broadcast alone.>

Teletext is a one-way, broadcast-delivery information system. Pages of information are continuously broadcast to the users. User terminals monitor the broadcast stream and requested pages, once recognized, are captured and stored. Teletext systems possess many attractive features. Among them are simplicity of operation and insensitivity of system performance to user loads. Previous research has considered the issue of response time optimization in teletext systems. In those studies, response time was averaged over the entire user population. In this paper, we analyze an individual user's response time experience. Needless to say, this provides a better gauge of the quality of service being delivered. In addition, this perspective provides the appropriate framework for evaluating strategies that take advantage of user terminal storage capabilities to improve response time performance. To demonstrate this, one such strategy is developed and analyzed. Numerical examples that illustrate the use of the paper's results are also presented.

Teletext is a one-way information delivery system where pages of information are broadcast to all users in a continuous manner. System response time is an important consideration in the design of teletext systems. One factor contributing to response time is the order in which pages are transmitted. In this paper, we formulate the problem of determining the sequence of page transmissions as a Markovian decision process. Using this formulation we show that, from a response time point of view, a cyclic order of page transmissions is optimal. We also describe two algorithms for designing a teletext broadcast cycle.

A Markov process model of an externally controlled two-stage manufacturing system is presented. The objective is to examine the effect on system performance of the contention for the resources of the control and communication equipment in the manufacturing system. In the system under consideration, when a new part enters either of the stages, a request-for-instruction message is sent to the control equipment. The stage will then remain idle until a control-instruction message is received from the control equipment. Only then can processing on the part begin. The control and communication equipment is modeled as a queuing system that receives the request-for-instruction messages from the machines, processes these messages, and returns control-instruction messages to the appropriate machine. Part and message processing times can be different and are assumed to have exponential distributions. This model is analyzed to obtain an analytic expression for the throughput (production rate in parts per unit time) of the manufacturing system. Numerical examples that illustrate the effect of model parameters on the system throughput are also presented.

Videotex is an interactive information system which provides a variety of services to its users. Examples of such services are information retrieval, software distribution, transaction processing, and message handling. An important aspect of the quality of service experienced by a videotex user is the response time. We consider the use of mixed individual/broadcast delivery to enhance the response time performance. Broadcast delivery is attractive for information retrieval applications where several users may be requesting the same information page, and a single broadcast of this page will satisfy all requests simultaneously. Individual response, however, is required for transaction-oriented services and for the retrieval of confidential information. A queueing model is developed to study the performance of videotex systems under mixed delivery. Analytic results are derived for the mean response time. Numerical examples are presented to show the performance characteristics of mixed delivery, and how it can be used to enhance the response time performance without increasing the processing capacity of the system.

Videotex is a system which provides users with low-cost real-time access to information. In such a system, user requests are forwarded to a service computer where the desired information is retrieved and sent back to the user. In this study, we investigate the response time behavior of a videotex system where information requested by one user is broadcast to all users. A novel queueing model for broadcast delivery is developed. Using this model, we first obtain an analytic expression for the mean response time, and then we develop an efficient algorithm for its computation. Numerical results illustrating the performance characteristics of broadcast delivery are presented.