Rate adaptation is a mechanism unspecified by the 802.11 standards, yet critical to the system performance by exploiting the multi-rate capability at the physical layer.I n this paper, we conduct a systematic and experimental study on rate adaptation over 802.11 wireless networks. Our main contributions are two-fold. First, we critique five design guidelines adopted by most existing algorithms. Our study reveals that these seemingly correct guidelines can be misleading in practice, thus incur significant performance penalty in certain scenarios. The fundamental challenge is that rate adaptation must accurately estimate the channel condition despite the presence of various dynamics caused by fading, mobility and hidden terminals. Second, we design and implement a new Robust Rate Adaptation Algorithm (RRAA)that addresses the above challenge. RRAA uses short-term loss ratio to opportunistically guide its rate change decisions, and an adaptive RTS filter to prevent collision losses from triggering rate decrease. Our extensive experiments have shown that RRAA outperforms three well-known rate adaptation solutions (ARF, AARF, and SampleRate) in all tested scenarios, with throughput improvement up to 143%.

The focus of this paper is to compare two popular end-to-end congestion control algorithm in the literature, namely, AIMD (additive increase/multiplicative decrease) and AIPD (additive increase/loss proportional decrease). We clarify the definitions of AIMD and AIPD algorithms, and compare them in various aspects such as convergence, steady state throughput, fairness characteristics, and the corresponding utility functions. The comparison is based on a simple mathematical analysis and a set of simulation results using the ns-2 simulator.

We introduce nanoProtean, a new router operating system and execution environment that reduces system overhead, making it possible to process the packets produced by gigabit networks. The ovearhead decreases as the offered load per packet increases due to the following features in nanoProtean (i) a completely preemptable operating system, (ii) efficient management of the system's job queue, and (iii) system support for fine-grain sharing of processing time amongst packets. These features are a result of a novel integration of efficient thread scheduling for multiprocessors and interrupt handling. Experimental analysis used to test our systems scalability uses a technique to emulate processing requests generated in real-time at 802.3z (gigabit) line speeds and greater. Our results demonstrate 2 Gbps routing; with MAE-East tables on two processors, and system overheads decreasing from 3.6 /spl mu/s per packet to 1.64 /spl mu/s per packet on one processor. By reducing the system overhead, we also demonstrate that nanoProtean enables active networking in a router supporting gigabit connections.

Multiple access-based collision avoidance MAC protocols have typically used fixed transmission power, and have not considered power control mechanisms based on the distance of the transmitter and receiver in order to improve spatial channel reuse. This work proposes PCMA, a power controlled multiple access wireless MAC protocol within the collision avoidance framework. PCMA generalizes the transmit-or-defer "on/off" collision avoidance model of current protocols to a more flexible "variable bounded power" collision suppression model. The algorithm is provisioned for ad hoc networks and does not require the presence of base stations to manage transmission power (i.e. it is decentralized). The advantage of implementing a power controlled protocol in an ad-hoc network is that source-destination pairs can be more tightly packed into the network allowing a greater number of simultaneous transmissions (spectral reuse). Our initial simulation results show that the PCMA can improve the throughput performance of the non-power controlled IEEE 802.11 by a factor of 2 with potential for additional scalability as source-destination pairs become more localized, thus providing a compelling reason for migrating to a new power controlled multiple access wireless MAC protocol standard.

Several routing algorithms for mobile ad hoc networks (MANETs) have been proposed previously. With the exception of a few, these protocols (i) involve all nodes in the route management process, (ii) rely on the use of broadcast relays for route computation, and (iii) are primarily reactive in nature. Related work has shown that the capacity utilization in ad hoc networks decreases significantly when broadcast relays or "broadcast storms" are performed frequently. This effect is compounded when all nodes in the network take part in the route computation. We propose and study an approach based on overlaying a virtual infrastructure adaptation of the core, proposed by Sivakumar, Sinha and Bharghavan (see IEEE Journal on Selected Areas in Communications, vol.17, no.8, p.1454-65, 1999) on an ad hoc network and operating routing protocols over the infrastructure. The core enables routing protocols to use only a subset of nodes in the network for route management and avoid the use of broadcast relays. Using the ns-2 simulator we evaluate the performance of two ad hoc routing protocols, dynamic source routing (DSR) and ad hoc on demand distance vector (AODV), when they are operated over the core and compare their performance against those of their basic versions.

In this work we present an end-to-end optimized video streaming system comprising of synergistic interaction between a source packetization strategy and an efficient and responsive, TCP-friendly congestion control protocol [Linear Increase Multiplicative Decrease with History (LIMD/H)]. The proposed source packetization scheme transforms a scalable/layered video bitstream so as to provide graceful resilience to network packet drops. The congestion control mechanism provides low variation in transmission rate in steady state and at the same time is reactive and provably TCP-friendly. While the two constituent algorithms identified above are novel in their own right, a key aspect of this work is the integration of these algorithms in a simple yet effective framework. This "application-transport" layer interaction approach is used to maximize the expected delivered video quality at the receiver. The integrated framework allows our system to gracefully tolerate and quickly react to sudden changes in the available connection capacity due to the onset of congestion, as verified in our simulations.

The need for simple, scalable, and incrementally deployable router-level mechanisms to support end-to-end congestion control has been well recognized in the literature. Specifically, mechanisms for early congestion detection and fair packet dropping, such as RED, have been proposed and extensively studied. It has been shown that RED does not scale well with the number of flows, is difficult to tune dynamically, and can degenerate into tail dropping behavior under a variety of conditions. To address these problems while still retaining the robust and simple of RED, we propose a new mechanism called load adaptive fair drop (LAFD), that has no tunable parameters, and adapts effectively to the offered load and the number of flows without maintaining any pre-flow state.

Corelite is a quality of service architecture that provides weighted max-min fairness for rate among flows in a network without maintaining any per-flow state in the core routers. There are three key mechanisms that work in concert to achieve the service model of Corelite: the introduction of markers in a packet flow by the edge routers to reflect the normalized rate of the flow; weighted fair marker feedback at the core routers upon incipient congestion detection; and linear increase/multiplicative decrease based rate adaptation of packet flows at the edge routers in response to marker feedback.

We describe a framework for video transmission over the Internet that features the coordinated operation of an application-layer video source coding algorithm and a transport-layer rate control mechanism. The proposed video coding scheme operates on a progressively encoded video stream and provides graceful resilience to network packet drops. The robustness is enabled through a generalized multiple description (MD) coding strategy, architectured as an adaptive array of packet-erasure correction codes. The video coding algorithm is matched to an efficient and reactive rate control mechanism that minimizes the fluctuation of rate and uses the profile of past losses to adjust the rate in a TCP-friendly manner. While the two constituent algorithms identified above are interesting in their own right, a key feature of this work is the integration of these algorithms in a simple framework that seeks to maximize the expected delivered video quality at the receiver through coordinated adaptation of the two components. We present simple simulation results to illustrate the utility of our approach.

We present a core-stateless quality of service architecture for achieving delay differentiation between flows. There are two key components in our approach: (1) per-class per-hop relative average delay-the average queueing delay perceived by the packets in a delay class at a link is inversely proportional to the delay weight of the class; (2) per-flow end-to-end delay class adaptation-the delay class of a flow is dynamically adjusted based on its perceived end-to-end delay in order to maintain the desired end-to-end average delay requirement of the flow. We show through simulations and analysis that these two components can, in concert, support end-to-end delay differentiation between flows using only simple mechanisms at the core routers in the network.

Multiple access-based collision avoidance MAC protocols have typically used fixed transmission power and have not considered power control mechanisms based on the distance of the transmitter and receiver in order to improve spatial channel reuse. We motivate transmission power control and investigate the challenges involved in implementing power control in multiple access wireless packet networks. For this work, we focus on wireless ad-hoc networks, where the links connecting source destination pairs are all wireless. Power control has been implemented in cellular networks such as CDMA (code division multiple access) for guide some time now. However these protocols depend on centralized control (i.e. base stations) and duplex communications that are not inherently, present in wireless multiple access packet networks. Our simulation results show that implementing power control in a multiple access environment can improve the throughput performance of the non-power controlled IEEE 802.11 by a factor of 2, thus providing a compelling reason for migrating to a new power controlled multiple access wireless MAC protocol standard.

Article Free Access Share on An application-level multicast architecture for multimedia communications (poster session) Authors: Kang-Won Lee Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Sungwon Ha Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Jia-Ru Li Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Vaduvur Bharghavan Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile Authors Info & Claims MULTIMEDIA '00: Proceedings of the eighth ACM international conference on MultimediaOctober 2000 Pages 398–400https://doi.org/10.1145/354384.354544Published:30 October 2000Publication History 3citation357DownloadsMetricsTotal Citations3Total Downloads357Last 12 Months11Last 6 weeks0 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 AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The goal of packet scheduling disciplines is to achieve fair and maximum allocation of channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new model for packet scheduling that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum “fair” allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.

Link-layer fairness models that have been proposed for wireline and packet cellular networks cannot be generalized for shared channel wireless networks because of the unique characteristics of the wireless channel, such as location-dependent contention, inherent conflict between optimizing channel utilization and achieving fairness, and the absence of any centralized control.

This paper describes a programmable switch architecture that can be dynamically tuned to support flexible quality of service metrics for flows in the Internet. The switch architecture consists of six key components: scheduling, flow aggregation, queueing, packet-level admission control, packet dropping, and feedback. We show that it is possible to achieve a wide range of QoS behavior ranging from strict per-flow rate and delay guarantees to coarse per-class rate assurances by programming the components appropriately.

We present our experience with the Illinois Reliable Multicast Architecture (IRMA) reliable multicast architecture. IRMA guarantees reliable, sequenced, and loosely synchronized delivery of multicast streams by supporting TCP as the multicast transport protocol at the end hosts without modifications to the standard TCP/IP stack. To support TCP as the multicast transport protocol, IRMA provides ACK aggregation, local recovery, and network level support for TCP flow/congestion control. We describe an implementation of IRMA, and evaluate its performance in a real network as well as in a simulation environment. The performance result of IRMA indicates that it may be a viable architecture for proving reliable multicast in the Internet.

Single-rate reliable multicast protocols are known to have scalability problems in the presence of a large number of receivers because the sender cannot distinguish independent packet losses at different receivers from multiple packet losses at the same receiver. In the presence of a large number of receivers, the sender may perceive a large aggregate packet loss even if no individual receiver is highly congested. Consequently, the multicast session progresses at a much slower rate than its desired sending rate. In order to solve this problem, we argue for decoupling of the mechanisms to achieve congestion control and reliability in reliable multicast protocols, and present a very simple "loss notification"-based multicast congestion control mechanism that can be used to augment both ACK-based and NAK-based reliable multicast protocols and solve the independent packet loss problem. We illustrate the efficacy of our approach via simulations using the ns2 simulator.

Linear increase/multiplicative decrease (LIMD) has typically been the congestion control paradigm of choice in the Internet. However, a major drawback of LIMD is that it reacts identically (and aggressively) to all packet losses, irrespective of the cause of loss. In this paper, we try to augment the basic LIMD congestion control with additional mechanisms to predict the cause of packet losses and react accordingly. To this end, we present the LIMD/H algorithm, which has the following features: (a) LIMD/H uses the "history" of packet losses and the evolution of transmission rate for a connection in order to distinguish between congestion-induced and non-congestion-induced packet losses; (b) LIMD/H reacts gently to non-congestion-induced losses and aggressively to congestion-induced losses, thereby achieving high efficiency, fairness, as well as quick reaction to the onset of congestion. We present an initial performance evaluation of LIMD/H using simulations and analysis.

The Illinois Reliable Multicast Architecture (IRMA) is a reliable multicast architecture that guarantees reliable, sequenced, and loosely synchronized delivery of multicast streams. IRMA provides ACK-based reliability, hybrid local server-initiated and sender-initiated loss recovery, and support for end-to-end flow control and congestion control. Unlike most contemporary work, IRMA supports TCP as the reliable multicast transport protocol at the end host without modifications. IRMA has been instantiated in a laboratory testbed, and its performance has been measured in various scenarios. Preliminary performance results show that IRMA is efficient and adaptive to the dynamics of the network.

We present a new transport protocol called HPF for effectively supporting heterogeneous packet flows in the Internet environment. The following are the key features of HPF: HPF supports packet flows where different packets in the same transport connection have different quality-of service requirements in term of reliability, priority, and deadlines. HPP supports application-level framing, and provides APIs for applications to specify the priority, reliability and timing requirements of each frame. HPF enables the use of application-specified priorities as hints for network routers to preferentially drop low-priority packets during congestion. This ensures that 'important data' gets through preferentially during congestion. HPF decouples the congestion control and reliability mechanisms in order to support congestion control for unreliable and heterogeneous packet flows. Preliminary performance measurements in our experimental testbed show that HPF can provide effective support for heterogeneous packet flows in the presence of dynamic network resources.

CEDAR is an algorithm for QoS routing in ad hoc network environments. It has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations, (b) the propagation of the link-state of stable high-bandwidth links in the core through increase/decrease waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. But preliminary performance evaluation shows that CEDAR is a robust and adaptive QoS routing algorithm that reacts effectively to the dynamics of the network while still approximating link-state performance for stable networks.

Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel error. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unied wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unied architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access.

Most current wireless wide area packet data networks (WWANs) are characterized by low and variable bandwidths, high and variable delays, significant non-congestion related loss, asymmetric uplink and downlink channels, and occasional blackouts.Additionally, the majority of the latency in a WWAN connection is incurred over the wireless link.Under such operating conditions, most contemporary wireless TCP algorithms do not perform very well.In this paper, we present WTCP, a reliable transport protocol that is designed to operate efficiently over commercial WWAN networks such as CDPD.WTCP is rate-based, uses only end-to-end mechanisms, performs rate control at the receiver, and uses the ratio of sending rate to receiving rate as the primary metric for rate control.We have implemented and evaluated WTCP over the CDPD network, and also simulated it in the ns-2 simulator.Our initial results indicate the WTCP can improve on the performance of comparable algorithms such as TCP-NewReno, TCP-Vegas, and Snoop-TCP by between 20% to 200% for typical operating conditions.'Most of the current deployment uses the proxy model for three reasons: (a) the connection quality of the WWAN network is too poor to sustain typical client-server applications, (b) the amount of data transfered to the mobile host must be filtered because of the orders of magnitude difference in bandwidth between the wired and WWAN connections, and (c) many portable computing devices have display and processing limitations that must be addressed by the proxy before sending the processed/filtered response to the mobile user.Permission to make digital or hard copies of all or part of this work tw personal or classroom use is gxnted without fee provided that coPi= are oat ma& or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first Page.To COPY othenvise, to rqublish, to post on servers or to redistribute to lists, reqllires prior specific permissioll and/or a fee.

We present the BTLA (base tree link augmentation) multicast routing infrastructure for heterogeneous wireless/wireline networks. BTLA has two goals: (a) to reduce the latency and overhead of joins, leaves, and handoffs in regions that experience high group dynamics and mobility, and (b) to optimize the multicast tree for stable regions that do not experience frequent group dynamics. The BTLA consists of two components: (a) pre-computed minimum height spanning trees of the multicast network called base trees that are used to generate and update multicast trees with low latency and overhead under dynamic network conditions, and (b) link augmentation-based optimization of the multicast tree using additional links in the multicast network that are not a part of the base tree, in order to reduce the size of the multicast tree. The BTLA uses the base tree approach in dynamic regions and refines it with the link augmentation approach in stable regions. Initial performance evaluation shows that the BTLA is able to effectively support multicast communication involving both static and mobile hosts.

In this paper, we present the MCEDAR (multicast core extraction distributed ad hoc routing) multicast routing algorithm for ad hoc networks. MCEDAR is an extension to the CEDAR architecture and provides the robustness of mesh based routing protocols and the approximates the efficiency of tree based forwarding protocols. It decouples the control infrastructure from the actual data forwarding infrastructure. The decoupling allows for a very minimalistic and low overhead control infrastructure while still enabling very efficient data forwarding.

Many current wireless wide area packet data networks are characterized by very low and variable bandwidths, very high and variable delays, significant non-congestion related loss, asymmetric uplink and downlink channels, and occasional blackouts. Additionally, the majority of the latency in a WWAN connection is incurred over the wireless link. Under such operating conditions, most contemporary wireless TCP algorithms do not perform very well. Sinha, Venkitaraman, Sivakumar and Bharghavan (see Proc. of ACM Mobicom '99, 1999) we presented WTCP, a reliable transport protocol that is designed to operate efficiently and fairly over wireless wide area networks. WTCP is rate-based, uses only end-to-end mechanisms, performs rate control at the receiver, and uses the ratio of sending rate to receiving rate as as the primary metric for rate control. In this paper, we evaluate the performance of WTCP over CDPD networks. We have implemented and evaluated WTCP over the CDPD network, and also simulated it in the ns-2 simulator. Our performance results indicate that WTCP can improve on the performance of comparable algorithms such as TCP-NewReno and TCP-Vegas by between 20% to 200% for typical operating conditions.

We present CEDAR, a core-extraction distributed ad hoc routing algorithm for quality-of-service (QoS) routing in ad hoc network environments, CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations; (b) the propagation of the link-state of high bandwidth and stable links in the core through increase/decrease waves; and (c) a QoS-route computation algorithm that is executed at the core nodes using only locally available state. The performance evaluations show that CEDAR is a robust and adaptive QoS routing algorithm that reacts quickly and effectively to the dynamics of the network while still approximating the performance of link-state routing for stable networks.

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair-scheduling algorithms because of two unique characteristics of wireless media: (1) bursty channel errors and (2) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however, a base station has only a limited knowledge of the arrival processes of uplink flows. We propose a new model for wireless fair-scheduling based on an adaptation of fluid fair queueing (FFQ) to handle location-dependent error bursts. We describe an ideal wireless fair-scheduling algorithm which provides a packetized implementation of the fluid mode, while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless FFQ model.

IP multicasting provides a mechanism for location independent addressing and packet delivery to a group of hosts that belong to a multicast group. It also provides efficient mechanisms for hosts to join and leave multicast groups. The problem of supporting macro and micro level host mobility in the Internet involves similar issues of location independent addressing, address translation, packet forwarding and location management of mobile hosts. We have developed a new approach called MSM-IP for supporting host mobility using IP multicasting as the sole mechanism for addressing and routing packets to mobile hosts. In this paper, we present the performance of UDP and TCP over MSM-IP, and compare it with their performance over Mobile-IP. Our analysis shows that our approach is very effective in supporting seamless mobility for both handoffs and interface changes within and across networks. The performance of both UDP and TCP are better when used with MSM-IP than with Mobile-IP. We briefly explain our approach, and present performance results, and explain the results.

In this paper we examine several aspects of performance and connection management during handoffs and interface switching in mobile computing environments. We demonstrate the insufficiency of network layer mobility protocols to preserve high-performance operation of reliable transport protocols such as TCP under certain circumstances. We also introduce a mobility-aware transport, Mobile TCP, that maintains robust operation despite lossy mobile activity. Experimental results are presented and discussed.

This paper studies the performance of a large class of scheduling algorithms, and investigates the interaction between the application and the network to improve performance under congestion. The following key ideas are presented in this paper: (a) we show the performance and scalability trade-offs between providing separation and multiplexing among flows; (b) we show that a bounded buffer FIFO scheduler performs approximately as well as a weighted round robin scheduler with per-flow queues in most practical situations, but requires significantly less overhead in terms of per-flow state; and (c) we show how link layer schedulers can use application-level hints in order to increase the perceived goodness of connections at higher layers.

This work proposes a self-organizing, dynamic infrastructure called a spine for efficient routing in ad hoc networks. We present a scalable framework for routing that encompasses a range of knowledge at each spine node, and identify the trade-offs involved for routing at different points in this range. Our routing algorithm requires only partial topology information at each spine node, consisting of the spine structure, dependants of each spine node, propagation of long-lived links, and snooped routing information from ongoing flows. Through worst-case theoretical bounds and simulation of typical scenarios, we show that the spine-based routing with only partial topology information provides good routes at low overhead.

b order to support diverse communication-intensive redtirne and non red-time data flows over a scarce, varying and shared wireless channel with location-dependent and bursty errors, we defie a service model that has the following charxteristi~short-tern fairness among flows which perceive a clean channel, worst-case delay bounds for packets, short-term throughput bounds for flows with clean channels and Iong-tem throughput bounds for dl flows with bounded channel error, optimal schedulable region, and support for both delay sensitive and error sensitive data flows.We present a wireless fair service algorithm, and show that it achieves the requirements of the service model through both analysis and simulation.The key aspects of the dg~ rithm are the following (a) an enhanced fair queueing based service scheme that supports decoupling of delay and bandwidth, (b) graceful service compensation for lagging flows and graceful service degradation for leading flows, (c) support for red-time delay sensitive flows as well as non realtime error sensitive flows, and (d) implementation of the wireless fair service rdgorithm within the fiarnework of the simple and robust CSMA/CA wireless medium access pro tocol.

State-of-the-art mobile computing environments must deal with scarce and dynamically varying resources-in particular, the network quality of service. Applications which execute in such environments need to adapt to the dynamic operating conditions in order to preserve the illusion of seamlessness for the end-user as far as possible. The paper proposes a framework for adaptation which provides applications with runtime support for quality of service negotiation, monitoring, and notification. Applications only need to specify the policy of adaptation at a high level, and are shielded from the mechanics of adaptation. The paper describes the design and implementation of the framework of adaptation as a part of the Prayer mobile computing environment.

We impose a virtual backbone structure on the ad-hoc network, in order to support unicast, multicast, and fault-tolerant routing within the ad-hoc network. This virtual backbone differs from the wired backbone of cellular networks in two key ways: (a) it may change as nodes move, and (b) it is not used primarily for routing packets or flows, but only for computing and updating routes. The primary routes for packets and flows are still computed by a shortest-paths computation; the virtual backbone can, if necessary provide backup routes to handle interim failures. Because of the dynamic nature of the virtual backbone, our approach splits the routing problem into two levels: (a) find and update the virtual backbone, and (b) then find and update routes. The key contribution of this paper is to describe several alternatives for the first part of finding and updating the virtual backbone. To keep the virtual backbone as small as possible we use an approximation to the minimum connected dominating set (MCDS) of the ad-hoc network topology as the virtual backbone. The hosts in the MCDS maintain local copies of the global topology of the network, along with shortest paths between all pairs of nodes.

Handoffs enable seamless migration of virtual connections between cells as users move in an indoor wireless ATM environment. Most current handoff schemes in such environments operate at the network layer without any explicit data link layer support for reducing cell loss during handoffs. In this paper we present a new data link layer mechanism that will minimize the delay and delay variation due to handoffs. Our handoff scheme inserts specially marked cells in the data cell flow. Analysis and simulation of our approach show a reduction in delay by 50%, and reduction in delay variance by an order of magnitude.

We present a two-level hierarchical routing architecture for ad hoc networks. Within each lower level cluster, we describe a self-organizing, dynamic spine structure to (a) propagate topology changes, (b) compute updated routes in the background, and (c) provide backup routes in case of transient failures of the primary routes. We analyze and bound the worst case of movements between upper level clusters to show that this hierarchical architecture scales well with network size.

IP multicasting provides a mechanism for location independent addressing and packet delivery to a group of hosts that belong to a multicast group. It also provides efficient mechanisms for hosts to join and leave multicast groups. The problem of supporting macro and micro level host mobility in the Internet involves similar issues of location independent addressing, address translation, packet forwarding and location management of mobile hosts. In order to exploit the commonality of goals in the two problems, we have investigated a new approach for supporting host mobility using IP multicasting as the sole mechanism for addressing and routing packets to mobile hosts. Mobile hosts are identified by unique multicast IP addresses, and use the IP multicasting infrastructure to route packets destined for mobile hosts. We have implemented a mobile computing environment which uses this routing approach, and our performance analysis shows that it is very effective in supporting seamless mobili...

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair scheduling algorithms because of two unique characteristics of wireless media: (a) bursty channel errors, and (b) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however a base station has only a limited knowledge of the arrival processes of uplink flows.In this paper, we propose a new model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error bursts. We describe an ideal wireless fair scheduling algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless fluid fair queueing model.

Emerging indoor mobile computing environments seek to provide a user with an advanced set of communication-intensive applications, which require sustained quality of service in the presence of wireless channel error, user mobility, and scarce available resources. In this paper, we investigate two related approaches for the management of critical networking resources in indoor mobile computing environments:• adaptively re-adjusting the quality of service within pre-negotiated bounds in order to accommodate network dynamics and user mobility.• classifying cells based on location and handoff profiles, and designing advance resource reservation algorithms specific to individual cell characteristics.Preliminary simulation results are presented in order to validate the approaches for algorithmic design. A combination of the above approaches provide the framework for resource management in an ongoing indoor mobile computing environment project at the University of Illinois.

Recent years have witnessed the rapid growth of mobile computing environments. One of the major concerns in such environments is security, specially in the context of wireless communications. We describe some of the important issues which need to be addressed in designing a security scheme for mobile communications. These include autonomy of communicating entities, mobility of the users, limitations of the hardware, etc. We describe a scheme which addresses the above issues, and provides a correct and efficient mechanism to establish secure communications. Our scheme provides authentication of the communicating entities, location privacy, and secure messaging.>

Mobile computing is a major area of current research. A variety of wirelessly networked mobile devices now make it possible for a physically untethered computer to function in a fully networked manner. Recent research has focussed on providing the mobile user a seamless environment of wired and wireless networks. One of the major hurdles in providing such a seamless environment is that wireless media are inherently less secure.

We present RiskExpert, an expert system tool that can be used by management for analyzing metrics data and predicting fixture results based on past trends and expert knowledge. The expert advice generated by RiskExpert from metric data analysis can greatly aid in reducing various risks involved in a software project life cycle, such as cost overruns and schedule delays. RiskExpert also allows the manager to pose questions on expected results for hypothetical projects that can be dynamically created, enabling him to pose What If? questions and analyze the results if he had done things a different way.>

In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digital assistants. Providing adequate network connectivity for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation's Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTS-CTS-DATA packet exchange and binary exponential back-off. Using packet-level simulations, we examine various performance and design issues in such protocols. Our analysis leads to a new protocol, MACAW, which uses an RTS-CTS-DS-DATA-ACK message exchange and includes a significantly different backoff algorithm.

We have built a distributed discrete-event simulator called Empathy. This paper describes some aspects of the Empathy simulation algorithm. Optimistic simulation incurs enormous memory overhead. In this paper, we propose an algorithm for optimistic simulation that is based on the concept of local conservative control for commitment of events. This algorithm reduces the memory overhead by an average of 30% and reduces the aggregate computational time for simulation by up to 25%.>

Optimistic distributed discrete-event simulation incurs significant memory overhead because it stores state vectors with each processed but uncommitted message. The authors propose an application-independent scheme that substantially reduces this overhead, while also improving the simulation performance. Global control in optimistic simulation is replaced by local conservative control, and the concept of hierarchical layers of commitment of messages is introduced. The memory overheads imposed by Time Warp are reduced, and the performance of the Time Warp algorithm is improved. These two objects are achieved by ensuring that the state of the system as a whole is not impeded by the slowness of a few logical processes.>