Many next generation applications (such as video flows) are likely to have associated minimum data rate requirements in order to ensure satisfactory quality as perceived by end-users. In this paper, we develop a framework to address the problem of maximizing the aggregate utility of traffic flows in a multi-hop wireless network, with constraints imposed both due to self-interference and minimum rate requirements. The parameters that are tuned in order to maximize the utility are (i) transmission powers of individual nodes and (ii) the channels assigned to the different communication links. Our framework is based on using a cross-decomposition technique that takes both inter-flow interference and self-interference into account. The output of our framework is a schedule that dictates what links are to be activated in each slot and the parameters associated with each of those links. If the minimum rate constraint cannot be satisfied for all of the flows, the framework intelligently rejects a sub-set of the flows and recomputes a schedule for the remaining flows. We also design an admission control module that determines if new flows can be admitted without violating the rate requirements of the existing flows in the network. We provide numerical results to demonstrate the efficacy of our framework.

Cross-layer designs in wireless network systems have been an active research area. Numerous cross-layer schemes are proposed to increase overall system performance by allowing information to be shared and controlled across protocol layers. However, the majority of the previous research work in this area is theoretic. The main obstacle which hinders researchers to real implementation is the complexity involved in lower-level driver modification and kernel programming. Moreover, common pitfalls of cross-layer scheme implementation can lead to unexpected system performance degradation. In this paper we propose unified cross-layer framework (UCF), a generic mechanism for OS to support cross-layer schemes. Through this mechanism protocol components export protocol-specific information through parameters and events to protocol components at other layers. Cross-layer extensions are activated only at necessary times according to their assigned priorities so that they can react to events and make decisions at different time scales with minimal overhead. We implement and evaluate UCF on embedded systems running NetBSD to demonstrate the modularity, ease of programming, and utility of UCF.

Transmit power and carrier sense threshold are key MAC/PHY parameters in carrier sense multiple access (CSMA) wireless networks. Transmit power control has been extensively studied in the context of topology control. However, the effect of carrier sense threshold on topology control has not been properly investigated in spite of its crucial role. Our key motivation is that the performance of a topology-controlled network may become worse than that of a network without any topology control unless carrier sense threshold is properly chosen. In order to remedy this deficiency of conventional topology control, we present a framework on how to incorporate physical carrier sense into topology control. We identify that joint control of transmit power and carrier sense threshold can be efficiently divided into topology control and carrier sense adaptation. We devise a distributed carrier sense update algorithm (DCUA), by which each node drives its carrier sense threshold toward a desirable operating point in a fully distributed manner. We derive a sufficient condition for the convergence of DCUA. To demonstrate the utility of integrating physical carrier sense into topology control, we equip a localized topology control algorithm, LMST, with the capability of DCUA. Simulation studies show that LMST-DCUA significantly outperforms LMST and the standard CSMA protocol.

Identification of a low-level point radioactive source amidst background radiation is achieved by a network of radiation sensors using a two-step approach. Based on measurements from three or more sensors, a geometric difference triangulation method or an N -sensor localization method is used to estimate the location and strength of the source. Then a sequential probability ratio test based on current measurements and estimated parameters is employed to finally decide: (1) the presence of a source with the estimated parameters, or (2) the absence of the source, or (3) the insufficiency of measurements to make a decision. This method achieves specified levels of false alarm and missed detection probabilities, while ensuring a close-to-minimal number of measurements for reaching a decision. This method minimizes the ghost-source problem of current estimation methods, and achieves a lower false alarm rate compared with current detection methods. This method is tested and demonstrated using: (1) simulations, and (2) a test-bed that utilizes the scaling properties of point radioactive sources to emulate high intensity ones that cannot be easily and safely handled in laboratory experiments.

Quality of service (QoS) provisioning is one of the most important criteria in newly emerging UWB WPANs, as they are expected to support a wide variety of applications from time-constrained, multimedia streaming to throughput-hungry, content transfer applications. Recently, the WiMedia Alliance has announced the PHY/MAC specification together with the common radio platform for UWB WPANs. The WiMedia MAC uses the contention-free reservation-based access, which supports isochronous traffic with distributed reservation protocol (DRP), and the contention-based access, which provides service differentiation for best effort and variable-rate real-time traffic with prioritized channel access (PCA), similar to the enhanced distributed coordinated access (EDCA) in IEEE 802.11e. In this paper, we conduct a comprehensive theoretical analysis and show that with the currently recommended parameter setting, EDCA cannot provide adequate QoS. In particular, without responding to the system dynamics (e.g., taking account of the number of active stations in each class), EDCA cannot allocate bandwidth in a deterministic proportional manner and the system bandwidth is underutilized. After identifying the deficiency of EDCA, we propose an enhanced QoS-provisioning framework for the PCA scheme that dynamically controls channel access to adjust allocated bandwidth depending on the change of application's bit rate, i.e., variable-rate real-time traffic. We show that in this framework, 1) variable-rate real-time traffic is adaptively guaranteed of deterministic bandwidth via a contention-based reservation access method; 2) best effort traffic is provided with deterministic proportional QoS; and 3) moreover, the bandwidth utilization in PCA is maximized. By deterministic proportional QoS, we mean that the proposed protocol will maintain the ratio, rj, of per-station throughput attained by a station of class j to that attained by a station of class 1 at the targeted value, and yet, the real amount of network bandwidth is changing according to the current available network bandwidth. We have also validated and evaluated the QoS provisioning capability and practicality of the proposed PCA framework both via simulation and an empirical study with the Multiband Atheros Driver for WiFi (MADWifi) Linux driver for Wireless LAN devices with the Atheros chipset.

In multihop wireless networks, packets of a flow originating from a source node are relayed by intermediate nodes (relay nodes) and travel towards their destination along a multihop wireless path. Since the traffic forwarding capability of each node varies according to its level of contention, ideally, a node should not transmit more packets to its relay node than the corresponding relay node can forward. Instead, each node should yield its channel access opportunity to its neighbor nodes so that all the nodes can evenly share the channel and have similar forwarding capabilities. In this manner, nodes can utilize the wireless channel effectively, and further increase the end-to-end throughput of a multihop path. We propose a fully distributed contention window adaptation (CWA) mechanism, which adjusts the channel access probability depending on the difference between the incoming and outgoing traffic at each node, in order to equate the traffic forwarding capabilities among all the nodes in the path. We implement the proposed adaptive contention algorithm on Madwifi Linux kernel driver for Wi-Fi interface with Atheros chipset and carry out an empirical study in our division building. The experiment results demonstrate how the proposed mechanism can improve end-to-end throughput performance in the multihop wireless networks.

In this paper, we describe oCast, an energy-optimal multicast routing protocol for wireless sensor networks. The general minimum-energy multicast problem is NP-hard. Intermittent connectivity that results from duty-cycling further complicates the problem. Nevertheless, we present both a centralized and distributed algorithm that are provably optimal when the number of destinations is small. This model is motivated by scenarios where sensors report to a small number of base stations or where data needs to be replicated on a small number of other nodes. We further propose an extended version of oCast, called Delay Bounded oCast (DB-oCast), which can discover optimal multicast trees under a predefined delay bound. Finally, we demonstrate the advantages of our schemes through both theoretical analysis and simulations.

We consider the placement of sensors to detect propagative sources where the sensing area of each sensor is anisotropic and arbitrarily-shaped due to the terrain and meteorological conditions. The propagation and detection times are non-negligible due to the propagation of source effects through space at a slow speed. We formulate the problem as placing the minimum number of sensors to ensure a detection time T and the coverage utility C. Both the sensing areas of sensors and the utility function U(ldr) are chosen to capture the environmental factors and the population distribution. We show this problem to be NP-hard, and present heuristic algorithms for 1-coverage and fc-coverage by adopting exiting methods. We evaluate the proposed algorithms in the realistic setting of Port of Memphis where the objective is to protect the population against chemical leaks or attacks. We utilize the SCIPUFF dispersion model to determine the sensing areas by accounting for the terrain and meteorological conditions, and use the real-life population distribution as the utility function. Based on empirical study, we make several important observations.

Many next generation applications (such as video flows) are likely to have associated minimum data rate requirements to ensure satisfactory quality as perceived by end-users. While there have been prior approaches on supporting quality-of-service (QoS) in mesh networks, they have largely ignored the issues that arise due to self-interference, the interference between different link layer transmissions of a single flow along a multi-hop path. In this paper, we develop a framework to address the problem of maximizing the aggregate utility of traffic flows in wireless mesh networks, with constraints imposed both due to self-interference and minimum rate requirements. The output of our framework is a schedule that dictates which links are to be activated simultaneously, and provides specifications of the resources associated with each of those links. Utilizing the proposed framework as a basis, we build an admission control module that intelligently manages the resources among the flows in the network and admits as many new flows as possible without violating the QoS of the existing flows. We provide numerical results to demonstrate the efficacy of our framework.

In this article, we address the issue of localization in anisotropic sensor networks. Anisotropic networks differ from isotropic networks in that they possess properties that vary according to the direction of measurement. Anisotropic characteristics result from various factors such as the geographic shape of the region (nonconvex region), different node densities, irregular radio patterns, and anisotropic terrain conditions. In order to characterize anisotropic features, we devise a linear mapping method that projects one embedding space built upon proximity measures into geographic distance space by using the truncated singular value decomposition (SVD) pseudo-inverse technique. This transformation retains as much topological information as possible and reduces the effect of measurement noise on the estimates of geographic distances. We show via simulation that the proposed localization method outperforms DV-hop, DV-distance, and MDS-MAP, and makes robust and accurate estimates of sensor locations in both isotropic and anisotropic sensor networks.

The performance of carrier sense multiple access (CSMA) wireless networks heavily depends on the level of spatial reuse, i.e., how many concurrent transmissions are allowed. Spatial reuse is primarily determined by physical carrier sense, and a key parameter for physical carrier sense is the carrier sense threshold. Our focus is on how to control the carrier sense threshold for improving network performance. We present a noncooperative game-theoretic framework, which leads to a fully distributed algorithm for tuning the carrier sense threshold. We introduce a utility function of each node, which is a nondecreasing concave function of the carrier sense threshold. A pricing function is further introduced to mitigate severe interference among nodes. The cost function is defined as the difference between the pricing and the utility functions. We prove that the noncooperative carrier sense game admits a unique Nash equilibrium (NE) under some technical conditions.We derive sufficient conditions that ensure the convergence of the synchronous and asynchronous update algorithms. Based on the analysis, we propose a fully distributed algorithm, entitled noncooperative carrier sense update algorithm (NCUA). Our simulation study indicates that NCUA outperforms standard CSMA with respect to the per-node throughput by 10-50%.

Advances in networking, sensors, medical devices and smart phones have made it feasible to monitor and provide medical and other assistance to people either in their homes or outside. Aging populations will benefit from reduced costs and improved healthcare through assisted living based on these technologies. However, these systems challenge current state-of-the-art techniques for usability, reliability, and security. In this paper we present the PAS open architecture for assisted living, which allows independently developed third party components to collaborate. Furthermore, we incorporate cell phones in PAS as the local intelligence in order to enhance the robustness and ubiquity. We discuss key technological issues in assisted living systems, such as software architecture layout, power preserving, security and privacy; and results from our pilot study in a real assisted living facility are presented.

In this paper we study the issue of topology control under the physical signal-to-interference-noise-ratio (SINR) model, with the objective of maximizing network capacity. We show that existing graph-model-based topology control captures interference inadequately under the physical SINR model, and as a result, the interference in the topology thus induced is high and the network capacity attained is low. Towards bridging this gap, we propose a centralized approach, called spatial reuse maximizer (MaxSR), that combines a power control algorithm T2P with a topology control algorithm P2T. T2P optimizes the assignment of transmit power given a fixed topology, where by optimality we mean that the transmit power is so assigned that it minimizes the average interference degree (defined as the number of interfering nodes that may interfere with the ongoing transmission on a link) in the topology. P2T, on the other hand, constructs, based on the power assignment made in T2P, a new topology by deriving a spanning tree that gives the minimal interference degree. By alternately invoking the two algorithms, the power assignment quickly converges to an operational point that maximizes the network capacity. We formally prove the convergence of MaxSR. We also show via simulation that the topology induced by MaxSR outperforms that derived from existing topology control algorithms by 50%-110% in terms of maximizing the network capacity.

In recent years, wireless ad hoc networks have become increasingly popular in both military and civilian applications due to their capability of building networks without the need for a pre-existing infrastructure. While a number of studies have been carried out to study the performance of IEEE 802.11 DCF in single-cell wireless LANs, the analysis of IEEE 802.11 DCF in multi-hop wireless networks with consideration of the effects of physical carrier sense, SINR, and collision caused by accumulative interference has been lacking. In this paper, we substantially extend Cali's work and rigorously model, with all these effects considered, channel activities governed by IEEE 802.11 DCF in multi-hop wireless networks. We show that as in single-cell WLANs, the choice of the contention window size can impact the system throughput in multi-hop wireless networks. However, the optimal value of the contention window size is quite different. Moreover, the optimal attempt probability p (the optimal window size) derived for multi-hop wireless networks with respect to maximizing the system throughput is larger (smaller) than that for single-cell WLANs. We also show that, given the minimal SINR threshold beta, the optimal carrier sense range is smaller than the conventional value used (provided that the contention window size is tuned accordingly).

Identification of a low-level point radiation source amidst background radiation is achieved by a network of radiation sensors using a two-step approach. Based on measurements from three sensors, the geometric difference triangulation method is used to estimate the location and strength of the source. Then a sequential probability ratio test based on current measurements and estimated parameters is employed to finally decide: (1) the presence of a source with the estimated parameters, or (2) the absence of the source, or (3) the insufficiency of measurements to make a decision. This method achieves specified levels of false alarm and missed detection probabilities, while ensuring a close-to-minimal number of measurements for reaching a decision. This method minimizes the ghost-source problem of current estimation methods, and achieves a lower false alarm rate compared with current detection methods. This method is tested and demonstrated using: (1) simulations, and (2) a test-bed that utilizes the scaling properties of point radiation sources to emulate high intensity ones that cannot be easily and safely handled in laboratory experiments.

The importance of spatial reuse in wireless ad hoc networks has been long recognized as a key to improving the network capacity. In this paper, we show that 1) in the case that the achievable channel rate follows the Shannon capacity, spatial reuse depends only on the ratio of the transmit power to the carrier sense threshold and 2) in the case that only a set of discrete data rates are available, as a control knob for sustaining achievable data rates, tuning the transmit power provides more sophisticated rate control over tuning the carrier sense threshold, provided that there is a sufficient number of power levels available. Based on the findings, we then propose a decentralized power and rate control algorithm to enable each node to adjust, based on its signal interference level, its transmit power and data rate. The transmit power is so determined that the transmitter can sustain a high data rate while keeping the adverse interference effect on the other neighboring concurrent transmissions minimal. Simulation results have shown that compared to existing carrier sense threshold tuning algorithms, the proposed power and rate control algorithm yields higher network capacity.

P2P applications are among the most popular Internet applications and constitute a majority of Internet traffic today. From the perspective of network management, a thorough understanding of the stochastic properties of P2P traffic is thus crucial to designing better traffic/resource control algorithms. However, previous work on measuring and analyzing P2P traffic focuses either on a specific type of P2P applications or report only qualitative or quantitative findings in the measured traffic, without systematically analyzing and modeling P2P traffic. In this paper, we aim to bridge the gap and perform a detailed analysis and modeling of P2P traffic of different types. We first gather and identify P2P traffic on a trans-pacific link between Japan and US. Then based on the flow level (transport layer) information, we analyze and model the marginal distributions of the traffic volume, connection duration, and connection interarrival times for P2P connections of Napster, BitTorrent (BT), eDonkey, Gnutella, and Fasttrack, respectively. We also study the burstiness property of P2P traffic generated by these five different applications and the implication/impact of connections with zero traffic volumes. A major finding of our study is that due to the different parameters/strategies used in the file sharing mechanism, P2P traffic of different applications exhibits different traffic characteristics. As a result, the traffic metrics of interest (i.e., the per-connection traffic volume, the connection duration, and the connection interarrival times) cannot be characterized uniformly with a single model among the different types of applications, but instead have to be modeled with different probability distributions.

In this paper, we devise, in compliance with the IEEE 802.11e protocol, a novel MAC-centric approach, called MACcontentioncontrol(MCC), to maximizing the bandwidth utilization and achieving proportional bandwidth allocation. We first show that approaches based on estimating the number of competing nodes and then setting the contention window size may not converge (and in some cases diverge) because of network dynamics. Then, by studying the optimality condition derived in our prior work, we identify two parameters (referred to ascontrolreferences) that remain approximately constant when the network operates at the optimal operational point,regardlessofthenumberofcompetingnodesineachAC. We instrument MCC to measure these control references, compare measurement results to their optimal control reference levels, and adjust the packet dequeuing rate from the interface queues in an additive-increase-multiplicative-decrease (AIMD) fashion and with respect to prespecified bandwidth allocation ratio associated with its AC. In some sense, MCC controls the rate of passing packets from the interface queues to to the MAC access function, and thus practically controls the effective number of competing nodes. We have conducted an extensive simulation study, and demonstrated the superiority of MCC to 802.11e in terms of both the achievable network throughput and the capability of achieving proportional bandwidth allocation. This, coupled with the fact that MCC does not require change in firmware and can be practically deployed, makes MCC a viable approach to contention control in IEEE 802.11e-operated WLANs.

In CSMA/CA-based, multi-hop, multi-rate wireless networks, spatial reuse can be increased by tuning the carrier-sensing threshold (Tcs) to reduce the carrier sense range (dcs). While reducing dcsenables more concurrent transmissions, the transmission quality suffers from the increased accumulative interference contributed by concurrent transmissions outside dcs. As a result, the data rate at which the transmission can sustain may decrease. How to balance the interplay of spatial reuse and transmission quality (and hence the sustainable data rate) so as to achieve high network capacity is thus an important issue. In this paper, we investigate this issue by extending Cali's model and devising an analytical model that characterizes the transmission activities as governed by IEEE 802.11 DCF in a single-channel, multi-rate, multi-hop wireless network. The systems throughput is derived as a function of Tcs, SINR, beta, and other PHY/MAC systems parameters. We incorporate the effect of varying the degree of spatial reuse by tuning the Tcs. Based on the physical radio propagation model, we theoretically estimate the potential accumulated interference contributed by concurrent transmissions and the corresponding SINR. For a given SINR value, we then determine an appropriate data rate at which a transmission can sustain. To the best of our knowledge, this is perhaps the first effort that considers tuning of PHY characteristics (transmit power and data rates) and MAC parameters (contention backoff timer) jointly in an unified framework in order to optimize the overall network throughput. Analytical results indicate that the systems throughput is not a monotonically increasing/decreasing function of Tcs, but instead exhibits transitional points where several possible choices of Tcscan be made. In addition, the network capacity can be further improved by choosing the backoff timer values appropriately.

In this paper, we extend both Bianchi's and Kumar's models and characterize the channel activities governed by IEEE 802.11 DCF in multi-hop wireless networks from the perspective of an individual sender. In particular, we incorporate the effect of PHY/MAC attributes (such as transmit power and physical carrier sense) that need not be considered in WLANs but become extraordinarily important in multi-hop wireless networks, and derive the throughput attained by each sender. With the use of the analytical model derived, we investigate the impact of transmit power and carrier sense threshold on network capacity, and identify a simple operating condition under which the network may attain throughput that is close to its optimal value.

In this paper, we report our work on extending the J-Sim network simulator to be an integrated environment for both simulation and model checking of network protocols. We also present a case study in which we model-checked AODV in J-Sim.

No abstract available.

Modeling and analysis of wireless traffic is fundamental to traffic engineering and resource management. The majority of existing work in this arena has focused on modeling/analyzing aggregate traffic, and little has been done in modeling/analyzing wireless traffic at the per-user level. In this paper, we bridge the gap and perform a detailed analysis and modeling on the traffic generated by individual wireless users, leveraging the data traces collected in a period of 4 months (November 2003 - February 2004) on the Dartmouth campus-wide 802.11 WLANs.Our study indicates that several parameters that characterize the wireless traffic generated by individual users are predictable, such as the traffic volume originating from a user and destined for a specific IP address, the set of destination IP addresses (for which connections initiated by a user are destined), and the patterns by which a wireless user connects to applications. We also model the per-connection traffic volume, the duration, and the interarrival time, of connections issued by a user using Weibull or Pareto distributions, and show that the burstiness of aggregate wireless traffic (which has been reported in the literature) is a direct consequence of the burstiness of the burstiness of traffic generated by individual users. These findings can be used to optimize traffic and resource management and provide better QoS (in terms of availability, resiliency, and performance).

The convergence of computer and physical world calls for next generation Wide Area Network (WAN) infrastructures for hard real-time and embedded applications. Such networks need virtual topologies to achieve scalability, configurability, and flexibility. Virtual topologies are made of virtual links, for which, the state-of-the-art building tool is Guaranteed Rate server based aggregates (GR- aggregates). However, common-practice weight assignment scheme couples GR-aggregate End-to-End (E2E) delay bound with aggregate's data throughput inverse proportionally. This is undesirable for many hard real-time embedded sensing/actuating applications, whose traffic has small data throughput but requires short E2E delay. We propose Guaranteed Delay server based aggregates (GD-aggregates), which allow assigning weights according to priorities instead of data throughput. This decouples E2E delay guarantee from data throughput, hence meets the needs of hard realtime embedded applications. In addition, GD-aggregates can be analyzed with simple closed form formulae, and can be easily planned with optimization tools.

Quality of service (QoS) provisioning is one of the most important criteria in newly emerging UWB-operated WPANs, as they are expected to support a wide variety of applica- tions from time-constrained, multimedia streaming to throughput- hungry, content transfer applications. As such, the Enhanced Distributed Coordinated Access (EDCA) mechanism has been adopted by MultiBand OFDM Alliance in its UWB MAC proposal. In this paper, we conduct a rigorous, comprehensive, theoretical analysis and show that with the currently recommended parame- ter setting, EDCA cannot provide adequate QoS. In particular, without responding to the system dynamics (e.g., taking into account of the number of active class-i stations), EDCA cannot allocate bandwidth in a deterministic proportional manner and the system bandwidth is under-utilized. After identifying the deficiency of EDCA, we propose, in compliance with the EDCA-incorporated UWB MAC protocol proposed in (15) (20), a framework, along with a set of theoretically grounded methods for controlling medium access with determin- istic QoS for UWB networks. We show that in this framework, 1) real-time traffic is guaranteed of deterministic bandwidth via a contention-based reservation access method; 2) best-effort traffic is provided with deterministic proportional QoS; and moreover, 3) the bandwidth utilization is maximized. We have also validated and evaluated the QoS provisioning capability and practicality of the proposed MAC framework both via simulation and empirically by leveraging the MADWifi (Multiband Atheros Driver for WiFi) Linux driver for Wireless LAN devices with the Atheros chipset.

Abstract — With the technical advances in ubiquitous computing and wireless networking, there has been an increasing need to capture the context information (such as the location) and to figure it into applications. In this paper, we establish the theoretical base and develop a localization algorithm for building a zero-configuration and robust indoor localization system to support location-based network services and management. The localization algorithm takes as input the on-line measurements of received signal strengths (RSSs) between 802.11 APs and between a client and its neighboring APs, and estimates the location of the client. The on-line RSS measurements among 802.11 APs are used to capture (in real-time) the effects of RF multi-path fading, temperature and humidity variations, opening and closing of doors, furniture relocation, and human mobility on the RSS measurements, and to create, based on the truncated singular value decomposition (SVD) technique, a mapping between the RSS measure and the actual geographical distance. The proposed system requires zero-configuration because the on-line calibration of the effect of wireless physical characteristics on RSS measurement is automated and no on-site survey or initial training is required to bootstrap the system. It is also quite responsive to environmental dynamics, as the impacts of physical characteristics changes have been explicitly figured in the mapping between the RSS measures and the actual geographical distances. We have implemented the proposed system with inexpensive off-the-shelf Wi-Fi hardware and sensory functions of IEEE 802.11, and carried out a detailed empirical study in our division building. The empirical results show the proposed system is quite robust and gives accurate localization results (i.e., with the localization error within 3 meters). I.

Abstract — Before a sensor network is deployed, it is important to determine how many sensors are required to achieve a certain coverage degree. The number of sensor required for maintaining k-coverage depends on the area of the monitored region, the probability that a node fails or powers off (to save energy), and the deployment strategy. In this paper, we derive the density required to maintain k-coverage under three deployment strategies: (i) nodes are deployed as a Poisson point process, (ii) nodes are uniformly randomly distributed, (iii) nodes are deployed on regular grids. Our results show that under most circumstances, grid deployment renders asymptotically lower node density than random deployment. These results override a previous conclusion that grid deployment may render higher node density than random node distributions. I.

The importance of spatial reuse in wireless ad-hoc networks has been long recognized as a key to improving the network capacity. One can increase the level of spatial reuse by either reducing the transmit power or increasing the carrier sense threshold (thereby reducing the carrier sense range). On the other hand, as the transmit power decreases or the carrier sense threshold increases, the SINR decreases as a result of the smaller received signal or the increased interference level. Consequently, the data rate sustained by each transmission may decrease. This leads naturally to the following questions:(1)How can the trade-off between the increased level of spatial reuse and the decreased data rate each node can sustain be quantified? In other words,is there an optimal range of transmit power/carrier sense threshold in which the network capacity is maximized? (2)What is the relation between the transmit power and the carrier sense threshold.In this paper, we study both problems, and show that (i)in the case that the achievable channel rate follows the Shannon capacity, spatial reuse depends only on the ratio of the transmit power to the carrier sense threshold; and (ii) in the case that only a set of discrete data rates are available, tuning the transmit power offers several advantages that tuning the carrier sense threshold cannot, provided that there is a sufficient number of power levels available. Based on the findings, we then propose a decentralized power and rate control algorithm to enable each node to adjust, based on its signal interference level, its transmit power and data rate. The transmit power is so determined that the transmitter can sustain a high data rate, while keeping the adverse interference effect on the other neighboring concurrent transmissions minimal. Simulation results have shown that, as compared to existing carrier sense threshold tuning algorithms, the proposed power and rate control algorithm yields higher network capacity.

In this paper, we consider the problem of mitigating interference and improving network capacity in wireless mesh networks from the angle of temporal-spatial diversity. In a nutshell, while the achievable throughput on a multihop wireless path is limited by intra-flow interference, the overall capacity of a multihop wireless network can be increased by exploiting temporal-spatial diversity of concurrent transmissions that exist among a number of wireless links. Connections that are routed along multihop wireless paths can be scheduled to take place simultaneously if their transmissions do not interfere with each other (significantly).To make a case of exploiting the temporal-spatial diversity to improve network capacity, we focus on transporting downstream traffic at gateway nodes with Internet access. We propose to construct, based on measurements of received signal strengths, a virtual coordinate system that is used to determine the sets of paths along which transmissions can take place with the least inter-flow interference. Based on the sets of non-interfering paths, the gateway node then determines the order with which a gateway node schedules frames of different connections to be transmitted. Through extensive simulation (with real-life measurement traces on an operational, city-wide wireless community network), we show that the downstream throughput of a gateway node in a wireless mesh network can be improved by 10-35% under a variety of network topologies and traffic distributions. This, coupled with the fact that the proposed approach requires only minor code change in the gateway nodes and does not require any additional hardware, makes it a viable option to improving network capacity in existing wireless mesh networks.

Recent studies on mobility modeling have focused on characterizing user mobility from real traces of wireless LANs (WLANs)and creating mobility models based on such characterization. However, most of the work does not study how user mobility is correlated in time at different time scales. For example, the future APs with which a user will be associated are predicted without the knowledge of when the association will take place and for how long. In this paper, we build a mathematical model for characterizing both steady state and transient behaviors of user mobility in WLANs. Specifically, we mode user mobility by a semi-Markov process, and obtain the transition probability matrix and the sojourn time distribution from the association history of WLAN users available at Dartmouth college [21]. With the steady-state characterization of user mobility in WLANs, we can estimate the long-term wireless network usage among different access points. By comparing the steady-state distributions of semi-Markov models built based on trace data collected at different time scales, we are able to characterize the degree of correlation in time and location.We also perform a transient behavior analysis of the semi-Markov process (that characterizes user mobility), and devise a timed location prediction algorithm that accurately predicts the future locations of users both the future access points they will associate themselves with and the association duration. We demonstrate the utility of timed location prediction, by showing how it can be utilized to predict the distribution of future user ocations with the time information figured in, and redistributing loads among neighboring APs. An improvement of 80% (in terms of load balance) is observed in a wide spectrum of traffic loads in the simulation.

Along with the success of IEEE 802.11-compliant WLANs, the Distributed Coordinated Function (DCF) specified as the contention-based medium access mechanism in IEEE 802.11 has been widely used to support applications in new regimes. A thorough understanding of the characteristics of IEEE 802.11 DCF is therefore a research focus. DCF assumes the binary exponential backoff algorithm (BEBA). Several existing models that characterize BEBA as a p-persistent scheme have ignored several subtle protocol details. This has practically constrained the models from being applied in a broader range of configurations, e.g., small contention window, and from being further extended, e.g. 802.11e EDCA.In this paper, we develop an analytical model that captures the subtlety, and faithfully describes the channel activities as governed by DCF. Based on the devised model, we perform a rigorous analysis on the saturation throughput performance in a single-hop WLAN. We also identify, by clearly defining and thus being able to differentiate the two terms, attempt probability and transmission probability, an erroneous extension made to Bianchi's model [3]. All the findings are corroborated by ns-2 simulation.

Advances in networking, sensors, and embedded devices have made it feasible to monitor and provide medical and other assistance to people in their homes. Aging populations will benefit from reduced costs and improved healthcare through assisted living based on these technologies. However, these systems challenge current state-of-the-art techniques for usability, reliability, and security. This is a particular challenge for open and extensible systems that combine software and hardware from many vendors and provide information to diverse clinicians. In this paper we present the I-Living architecture for assisted living that allows independent parties work together in a dependable, secure, and low-cost fashion with predictable properties. Our approach is based on an Assisted Living Service Provider (ALSP) who provides a server that collects and maintains encrypted assisted persons (APs)' records. Our ALSP can be a third party distinct from APs, communication providers, and clinicians; or it can be part of an ISP, hospital or similar enterprise. We have explored the architecture by developing a collection of applications and implementing them in a prototype system. Our system shows the feasibility and opportunity of an open approach to assisted living systems.

In this paper, we consider the problem of designing optimal asynchronous wake-up schedules to facilitate distributed power management and neighbor discovery in multihop wireless networks. We first formulate it as a block design problem and derive the fundamental trade-offs between wake-up latency and the average duty cycle of a node. After the theoretical foundation is laid, we then devise a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wake-up schedule derived. To demonstrate the usefulness of asynchronous wake-up, we investigate the efficiency of neighbor discovery and the application of on-demand power management, which overlays a desirable communication schedule over the wake-up schedule mandated by the asynchronous wake-up mechanism. Simulation studies demonstrate that the proposed asynchronous wake-up protocol has short discovery time which scales with the density of the network; it can accommodate various traffic characteristics and loads to achieve an energy savings that can be as high as 70 percent, while the packet delivery ratio is comparable to that without power management

Topology control algorithms have been proposed to maintain network connectivity while improving energy efficiency and increasing network capacity. However, by reducing the number of links in the network, topology control algorithms actually decrease the degree of routing redundancy. As a result, the derived topology is more susceptible to node failures or departures. In this paper, we resolve this problem by enforcing k-vertex connectivity in the topology construction process. We propose a fully localized algorithm, fault-tolerant local spanning subgraph (FLSS), that can preserve k-vertex connectivity and is min-max optimal among all strictly localized algorithms (i.e., FLSS minimizes the maximum transmission power used in the network, among all strictly localized algorithms that preserve k-vertex connectivity). It can also be proved that FLSS outperforms two other existing localized algorithms in terms of reducing the transmission power. We also discuss how to relax several widely used assumptions in topology control to increase the practical utility of FLSS. Simulation results indicate that, compared with existing distributed/localized fault-tolerant topology control algorithms, FLSS not only has better power-efficiency, but also leads to higher network capacity. Moreover, FLSS is robust with respect to position estimation errors.

It has long been recognized that energy conservation usually comes at the cost of degraded performance such as longer delay and lower throughput in stand-alone systems and communication networks. However, there have been very few research efforts in quantifying such trade-offs. In this paper, we develop analytical models to characterize the relationships among energy, delay and throughput for different power management policies in wireless communication. Based on the decision when to put nodes to low-power states, we divide power management policies into two categories, i.e., 1) time-out driven and 2) polling-based. M/G/1/K queues with multiple vacations and an attention span are used to model time-out driven policies while transient analysis is applied to derive the state transition probability in polling-based systems. We find that For time-out driven power management policies, the "optimal" policy exhibits a threshold structure, i.e., when the traffic load is below certain threshold, a node should switch to the low-power state whenever possible and always remain active otherwise. From our analysis, contrary to general beliefs, polling-based policies such as the IEEE 802.11 PSM are not energy efficient for light traffic load.

Techniques for sampling Internet traffic are very important to understand the traffic characteristics of the Internet [14, 8]. In spite of all the research efforts on packet sampling, none has taken into account of self-similarity of Internet traffic in devising sampling strategies. In this paper, we perform an in-depth, analytical study of three sampling techniques for self-similar Internet traffic, namely static systematic sampling, stratified random sampling and simple random sampling. We show that while all three sampling techniques can accurately capture the Hurst parameter (second order statistics) of Internet traffic, they fail to capture the mean (first order statistics) faithfully. We also show that static systematic sampling renders the smallest variation of sampling results in different instances of sampling (i.e., it gives sampling results of high fidelity). Based on an important observation, we then devise a new variation of static systematic sampling, called biased systematic sampling (BSS), that gives much more accurate estimates of the mean, while keeping the sampling overhead low. Both the analysis on the three sampling techniques and the evaluation of BSS are performed on synthetic and real Internet traffic traces. Our performance study shows that BSS gives a performance improvement of 40% and 20% (in terms of efficiency) as compared to static systematic and simple random sampling.

Tracking of moving targets has attracted more and more attention due to its importance in utilizing sensor networks for surveillance. In this paper, we consider the issue of how to track mobile targets with certain level of quality of monitoring (QoM), while conserving power. We address the target tracking problem by taking into account of both the coverage and the QoM. In particular, QoM ensures that the probability of reporting inaccurate monitoring information (such as false alarm or target miss) should be as small as possible, even in the presence of noises and signal attenuation. We also analytically whether or not the detection/observation made by a single sensor suffices to tracking the target in a reasonably populated sensor network. Our finding gives a confirmative answer and challenges the long-held paradigm that high tracking quality (low tracking error) necessarily requires high power consumption. To rigorously analyze the impact of target movement on QoM, we derive both lower and upper bounds on the number of sensors (called duty sensors) required to keep track of a moving target. Based on the analysis, we have devised a cooperative, relay-area-based scheme that determines which sensor should become the next duty sensor when the target is moving. The simulation study indicates that the number of duty sensor required in the proposed scheme is, in the worst case, approximately 1.2 times larger than the lower bound. It also indicates that a trade-off exists among QoM, the number of duty sensors required, and the load balance

In this paper, we consider the issue of localization in anisotropic sensor networks. Anisotropic networks are differentiated from isotropic networks in that they possess properties that vary according to the direction of measurement. Anisotropic characteristics result from various factors such as the geographic shape of the region (non-convex region), the different node densities, the irregular radio patterns, and the anisotropic terrain conditions. In order to characterize anisotropic features, we devise a linear mapping method that transforms proximity measurements between sensor nodes into a geographic distance embedding space by using the truncated singular value decomposition-based (TSVD-based) pseudo-inverse technique. This transformation retains as much topological information as possible and reduces the effect of measurement noises on the estimates of geographic distances. We show via simulation that the proposed localization method outperforms DV-hop, DV-distance (D. Niculescu, 2001), and MDS-map (Y. Shang et al., 2003), and makes robust and accurate estimates of sensor locations in both isotropic and anisotropic sensor networks.

In this paper, we study how the achievable throughput scales in a wireless network with randomly located nodes as the number of nodes increases, under a communication model where (i) each node has a maximum transmission power W/sub O/ and is capable of utilizing B Hz of bandwidth and (ii) each link can obtain a channel throughput according to the Shannon capacity. Under the limit case that B tends to infinity, we show that each node can obtain a throughput of /spl theta/(n/sup (/spl alpha/-1)/2/) where n is the density of the nodes and /spl alpha/ > 1 is the path loss exponent. Both the upper bound and lower bound are derived through percolation theory. In order to derive the capacity bounds, we have also derived an important result on random geometric graphs: if the distance between two points in a Poisson point process with density n is non-diminishing, the minimum power route requires a power rate at least /spl Omega/(n/sup (1-/spl alpha/)/2/). Our results show that the most promising approach to improving the capacity bounds in wireless ad hoc networks is to employ unlimited bandwidth resources, such as the ultra wide band (UWB).

In this paper, we investigate the minimum total power (termed as critical total power) required to ensure asymptotic k-connectivity in heterogeneous wireless networks where nodes may transmit using different levels of power. We show that under the assumption that wireless nodes form a homogeneous Poisson point process with density /spl lambda/ on a unit square region [0, 1]/sup 2/ and the Toroidal model [M.D. Penrose, 1997], the critical total power required for maintaining k-connectivity is /spl theta/((/spl Gamma/(e/2+k))/((k-1)l)/spl lambda//sup 1-e/2/) with probability approaching one as /spl lambda/ goes to infinity, where e is the path loss exponent. Compared with the results that all nodes use a common critical transmission power for maintaining k-connectivity [M.D. Penrose, 1999], [P.-J. Wan and C. Yi, 2004], we show that the critical total power can be reduced by an order of (log /spl lambda/)e/2 by allowing nodes to optimally choose different levels of transmission power. This result is not subject to any specific power/topology control algorithm, but rather a fundamental property in wireless networks.

A fully connected network topology is critical to many fundamental operations in wireless ad hoc networks. We study the problem of deploying additional wireless nodes to improve the connectivity of an existing wireless network. Given a disconnected network, we consider the connectivity improvement (CI) problem, i.e., how to deploy as few additional nodes as possible so that the augmented network is connected. We first prove the NP-completeness of CI, and then present a Delaunay triangulation-based algorithm, connectivity improvement using Delaunay triangulation (CIDT). We discuss several variations of CIDT, and propose two additional optimization techniques to further improve the performance. Finally, we demonstrate the effectiveness of CIDT, and compare the performance of its variations via J-Sim simulation.

A major problem with leveraging event-driven, packet-level simulation environments, such as ns2[6], J-Sim[1], OpNet[2]), and QualNet[3]), in conducting wireless network simulation is the vast number of events generated, a majority of which are related to signal transmission in the PHY/MAC layers.In this extended abstract, we investigate the operations of signal transmission in the various stages: signal propagation, signal interference, and interaction with the PHY/MAC layers, and identify where events can be reduced without impairing the accuracy. We propose to leverage the MAC/PHY state information, and devise (from the perspective of network simulation) a reactive channel model (RCM) in which nodes explicitly register their interests in receiving certain events according to the MAC/PHY states they are in and the corresponding operations that should be performed. The simulation study indicates that RCM renders an order of magnitude of speed-up without compromising the accuracy of simulation results. An advantage of RCM with respect to the implementation is that there is no need to re-design the channel model for each specific MAC layer, and the modification made in the MAC/PHY layers is quite modest (e.g., a few API changes). This, coupled with the performance gain, suggests that RCM is an attractive, light-weight mechanism for expediting wireless network simulation.

Most existing topology control algorithms assume homogeneous wireless networks with uniform maximal transmission power, and cannot be directly applied to heterogeneous wireless networks where the maximal transmission power of each node may be different. We present two localized topology control algorithms for heterogeneous networks: Directed Relative Neighborhood Graph (DRNG) and Directed Local Spanning Subgraph (DLSS). In both algorithms, each node independently builds its neighbor set by adjusting the transmission power, and defines the network topology by using only local information. We prove that: 1) both DRNG and DLSS can preserve network connectivity; 2) the out-degree of any node in the resulting topology generated by DRNG or DLSS is bounded by a constant; and 3) DRNG and DLSS can preserve network bi-directionality. Simulation results indicate that DRNG and DLSS significantly outperform existing topology control algorithms for heterogeneous networks in several aspects.

In this paper, we consider the problem of how to represent the locations of Internet hosts in a Cartesian coordinate system to facilitate estimation of network distances among arbitrary Internet hosts. We envision an infrastructure that consists of beacon nodes and provides the service of estimating network distance between pairs of hosts without direct delay measurement. We show that the principal component analysis (PCA) technique can effectively extract topological information from delay measurements between beacon hosts. Based on PCA, we devise a transformation method that projects the raw distance space into a new coordinate system of (much) smaller dimensions. The transformation retains as much topological information as possible and yet enables end hosts to determine their coordinates in the coordinate system. The resulting new coordinate system is termed as the Internet Coordinate System (ICS). As compared to existing work (e.g., IDMaps and GNP), ICS incurs smaller computation overhead in calculating the coordinates of hosts and smaller measurement overhead (required for end hosts to measure their distances to beacon hosts). Finally, we show via experiments with both real-life and synthetic data sets that ICS makes robust and accurate estimates of network distances, incurs little computational overhead, and its performance is not susceptible to the number of beacon nodes (as long as it exceeds a certain threshold) and the network topology.

In this article, we explore the fundamental limits of sensor network lifetime that all algorithms can possibly achieve. Specifically, under the assumptions that nodes are deployed as a Poisson point process with density λ in a square region with side length ℓ and each sensor can cover a unit-area disk, we first derive the necessary and sufficient condition of the node density in order to maintain complete k -coverage with probability approaching 1. With this result, we obtain that if λ = log ℓ 2 + ( k + 2)loglog ℓ 2 + c (ℓ), c (ℓ) → −∞, as ℓ → + ∞, the sensor network lifetime (for maintaining complete coverage) is upper bounded by kT with probability approaching 1 as ℓ → + ∞, where T is the lifetime of a single sensor. Second, we derive, given a fixed node density in a finite (but reasonably large) region, the upper bounds of lifetime when only α-portion of the region is covered at any time. We also carry out several sets of experiments to validate the derived theoretical results. Numerical results indicate that the derived upper bounds apply not only to networks of large sizes and homogeneous nodal distributions but also to small size networks with clustering nodal distributions.

In this paper, we present a minimum spanning tree (MST)-based algorithm, called local minimum spanning tree (LMST), for topology control in wireless multihop networks. In this algorithm, each node builds its LMST independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: 1) the topology derived under LMST preserves the network connectivity; 2) the node degree of any node in the resulting topology is bounded by 6; and 3) the topology can be transformed into one with bidirectional links (without impairing the network connectivity) after removal of all unidirectional links. Simulation results show that LMST can increase the network capacity as well as reduce the energy consumption.

Switching the devices to low-power states in prolonged periods of inactivity is a widely used technique to conserve energy for battery-powered wireless devices. In this paper, we present a mathematical abstraction of time-out driven power management policies together with different wakeup mechanisms in wireless networks to characterize the energy-performance trade-offs. The time-out driven power management is modeled as a M/G/1/K queue with multiple vacations and an attention span. We then derive the steady state behaviors of such systems, and present a closed-form solution for systems with large buffers. The analysis reveals that the "best" power management policy to minimize the energy-delay product exhibits a threshold structure, i.e., when the traffic load is below a certain threshold, a node should switch to the low-power state whenever possible and always remain active otherwise, and suggests a threshold-based power management protocol.

We present a novel and complementary mechanism, called link-indexed statistical traffic predictor (LISP) to improve IEEE 802.11 power saving mechanism (PSM). LISP employs a simple, light-weight traffic prediction mechanism and enables each node to seek the inherent correlation between ATIM.ACKs and incoming traffic. Thereby nodes en route can stay awake in the BI in which a packet is anticipated to arrive, thus bridging a "freeway" for the packet to rapidly traverse the route. Meanwhile, the number of duty cycles is minimized and more energy is conserved. We conduct analytical and simulation studies and demonstrate the effectiveness of LISP.

In this paper, we examine the feasibility of incorporating network calculus based models in simulating TCP/IP networks. By exploiting network calculus properties, we characterize how TCP congestion control - additive increase and multiplicative decrease (AIMD), together with the queue management strategy used in routers, regulates TCP flows. We first divide the time axis into intervals (each of which consists of multiple round-trip times), and derive a TCP AIMD throughput model which derives the attainable throughput of a TCP flow, given the number of collisions in an interval. Then based on the derived throughput model, we define a set of network calculus based theorems that give upper and lower bounds on the attainable TCP throughput in each interval. Finally, we implement network calculus (NC) based simulation in ns-2, conduct simulation in both the packet mode and the network calculus-based mode, and measure the performance gain (in terms of the execution time thus reduced) and the error discrepancy (in terms of the discrepancy between NC-based simulation results and packet-level simulation results). The simulation results indicate an order of magnitude or more (maximally 30 times) improvement in execution time and the performance improvement becomes more pronounced as the network size increases (in perspective of network capacities and number of flows). The error discrepancy between NC-based simulation and packet-level simulation, on the other hand, is minimally 1-2% and maximally 8-12% in a wide spectrum of network topologies and traffic loads employed in this study. The simulation results also indicate the superiority of NC-based simulation over fluid model based simulation (the latter realized using the time stepped hybrid simulation).

Previous work on topology control usually assumes homogeneous wireless nodes with uniform transmission ranges. In this paper, we propose two localized topology control algorithms for heterogeneous wireless multihop networks with nonuniform transmission ranges: directed relative neighborhood graph (DRNG) and directed local minimum spanning tree (DLMST). In both algorithms, each node selects a set of neighbors based on the locally collected information. We prove that (1) the topologies derived under DRNG and DLMST preserve the network connectivity; (2) the out degree of any node in the resulting topology by DLMST is bounded; while the out degree of nodes in the topology by DRNG is not bounded; and (3) the topologies generated by DRNG and DLMST preserve the network bi-directionality.

Existing network simulators perform reasonably well in evaluating the performance of network protocols, but lack the capability of verifying and validating the correctness of network protocols. In this paper we have extended J-Sim - an open-source, component-based compositional network simulation environment - with the model checking capability to explore the state space created by a network protocol until either the entire state space is explored (if the state space is finite) or an error (e.g., a violation of a user-defined safety assertion) is discovered. We also exploit protocol-specific properties in the process of exploring the state space, to reduce the size of the state space and to guide the (best-first) search towards paths that can potentially locate errors in less time. As a proof of concept, we have demonstrated use of the J-Sim model checker in locating errors in an automatic repeat request (ARQ) protocol. As compared to the Maude LTL model checker, the J-Sim model checker can locate errors in a timely manner and with shorter error traces.

Topology control algorithms usually reduce the number of links in a wireless network, which in turn decreases the degree of connectivity. The resulting network topology is more susceptible to system faults such as node failures and departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized algorithm, Fault-tolerant Global Spanning Subgraph (FGSSk), which preserves k-vertex connectivity. FGSSk is min-max optimal, i.e., FGSSk minimizes the maximum transmission power used in the network, among all algorithms that preserve k-vertex connectivity. Based on FGSSk, we propose a localized algorithm, Fault-tolerant Local Spanning Subgraph (FLSSk). It is proved that FLSSk preserves k-vertex connectivity while maintaining bi-directionality of the network, and FLSSk is min-max optimal among all strictly localized algorithms. We then relax several widely used assumptions for topology control to enhance the practicality of FGSSk and FLSSk. Simulation results show that FLSSk is more power-efficient than other existing distributed/localized topology control algorithms.

In this paper, we explore the fundamental limits of sensor network lifetime that all algorithms can possibly achieve. Specifically, under the assumptions that nodes are deployed as a Poisson point process with density λ in a square region with side length l and each sensor can cover a unit-area disk, we first derive the necessary and sufficient condition of the node density in order to maintain complete k-coverage with probability approaching 1. With this result, we obtain that if #955; = log l2 + (k+2)log log l2 + c(l), c(l) → -∞, as l → +∞, the sensor network lifetime (for maintaining complete coverage) is upper bounded by kT with probability approaching 1 as l → +∞, where T is the lifetime of each sensor. Second, we derive, given a fixed node density in a finite (but reasonably large) region, the upper bounds of lifetime when only α-portion of the region is required to be covered at any time. We also carry out simulations to validate the derived results. Simulation results indicate that the derived upper bounds apply not only to networks of large areas but also to small-area networks.

The power-efficient broadcast for multi-hop wireless networks is discussed in this paper. We first investigate the trade-off between (i) using larger transmission power to reach more nodes in one hop and (ii) using smaller power and relaying broadcast messages through multiple hops. Analysis indicates that multi-hop broadcast is more power-efficient if /spl alpha/ /spl ges/ 2.2, where the power consumption model is P(r, /spl alpha/) = c/sub 0/ /spl middot/ r/sup /spl alpha// + c/sub 1/. Based on the analysis, we propose broadcast on local minimum spanning tree (BLMST). An underlying topology is first derived using local minimum spanning tree (LMST), a localized topology control algorithm. Broadcast messages are then simply relayed through the derived topology in a constrained flooding fashion. BLMST is fully localized, scalable, and power-efficient. Simulation results show that the performance of BLMST is comparable to that of existing centralized algorithms.

In this paper, we develop a fast simulation framework for IEEE 802.11-operated wireless LANs (WLANs), in which a large number of packets are abstracted as a single fluid chunk, and their behaviors are approximated with analytic fluid models and figured into the simulation. We first derive the analytical model that characterizes data transmission activities in IEEE 802.11-operated WLANs with/without the RTS/CTS mechanism. All the control overhead incurred in the physical and MAC layers, as well as system parameters specified in IEEE 802.11 [12] are faithfully figured in. We validate the model with simulation in cases in which the network is and is not saturated. We then implement, with the use of the time stepping technique [21], the fast simulation framework for WLANs in ns-2 [2], and conduct a comprehensive simulation study to evaluate the framework in terms of speed-up and errors incurred under a variety of network configurations.The simulation results indicate that the proposed framework is indeed effective in simulating IEEE 802.11-operated WLANs. It achieves as much as two orders of magnitude improvement in terms of execution time as compared to packet-level simulation. The performance improvement is more pronounced when the number of wireless nodes, the number of applications running on each wireless node, or the number of WLANs increases. The relative error, on the other hand, falls within 2% in all cases, as long as the value of the time step is appropriately determined.

In this paper, we develop a model-based frame scheduling scheme, called MFS, to enhance the capacity of IEEE 802.11-operated wireless local area networks (WLANs) for both transmission control protocol (TCP) and user datagram protocol (UDP) traffic. In MFS each node estimates the current network status by keeping track of the number of collisions it encounters between its two consecutive successful frame transmissions, and computes accordingly the current network utilization. The result is then used to determine a scheduling delay to be introduced before a node attempts to transmit its pending frame. MFS does not require any change in IEEE 802.11, but instead lays a thin layer between the LL and medium access control (MAC) layers. In order to accurately calculate the current utilization in WLANs, we develop an analytical model that characterizes data transmission activities in IEEE 802.11-operated WLANs with/without the request to send/clear to send (RTS/CTS) mechanism, and validate the model with ns-2 simulation. All the control overhead incurred in the physical and MAC layers, as well as system parameters specified in IEEE 802.11, are figured in. We conduct a comprehensive simulation study to evaluate MFS in perspective of the number of collisions, achievable throughput, intertransmission delay, and fairness in the cases of TCP and UDP traffic. The simulation results indicate that the performance improvement with respect to the protocol capacity in a WLAN of up to 300 nodes is 1) as high as 20% with the RTS/CTS and 70% without the RTS/CTS in the case of UDP traffic and 2) as high as 10% with the RTS/CTS and 40% without the RTS/CTS in the case of TCP traffic. Moreover, the intertransmission delay in MFS is smaller and exhibits less variation than that in IEEE 802.11; the fairness among wireless nodes in MFS is better than, or equal to, that in IEEE 802.11.

We devise and evaluate a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we envision a hierarchical sensor network that is composed of 1) a static backbone of sparsely placed high-capability sensors which assume the role of a cluster head (CH) upon triggered by certain signal events and 2) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a predetermined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. We address and devise solution approaches (with the use of Voronoi diagram) to realize dynamic clustering: (I1) how CHs operate with one another to ensure that only one CH (preferably the CH that is closes to the target) is active with high probability, (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with nonredundant, essential information to determine the target location, and (I3) both the packets that sensors send to their CHs and packets that CHs report to subscribers do not incur significant collision. Through both probabilistic analysis and ns-2 simulation, we use with the use of Voronoi diagram, the CH that is usually closes to the target is (implicitly) selected as the leader and that the proposed dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.

With the rapid deployment of wireless LAN technology, provisioning of QoS differentiation to different traffic classes in wireless LANs (WLANs) has become a prominent research issue. In this paper, we analyze throughput performance of a p-persistent version of 802.11 MAC protocol with multiple QoS traffic classes. (It has been validated in [F. Cali, et al., March 1998], [F. Cali, et al., December 2000], [F. Cali, et al., September 2000] that the transmission probability used in the p-persistent version of 802.11 can be "converted" to the retransmission backoff timer value in 802.11.) In particular, we derive the closed-form solution of throughput with respect to different traffic classes. With the derived analytical results, each station can fine tune its transmission probabilities for different traffic classes to achieve the targeted throughput ratio, while at the same time maximizing the total system capacity. The correctness of the analytical results is corroborated by simulation.

Broadcast has been widely used in mobile ad hoc networks (MANETs) as a communication means to disseminate information to all reachable nodes. However, the conventional broadcast scheme that broadcast packets omnidirectionally suffers from several drawbacks: excessive amount of redundant traffic, exaggerated interference/contention between neighboring nodes, and limited coverage (as a result of contention/collision). This is termed as the broadcast storm problem in S.Y.Ni et al. [1999]. In this paper, we address this problem in MANETs with the use of directional antennas. We propose three schemes: on/off directional broadcast, relay-node-based directional broadcast and location-based directional broadcast, in the increasing order of implementation complexity. We implement the proposed schemes in qualnet and compare their performances against the conventional broadcast scheme. The simulation results indicate that the proposed schemes outperform the conventional omnidirectional scheme with respect to coverage, latency, and redundancy over a wide spectrum of network topology and node mobility.

Bluetooth is a promising new wireless technology that enables portable devices to form short-range wireless ad hoc networks. In this paper, we present a new, distributed Bluetooth scatternet formation algorithm, called loop scatternet formation, which forms scatternets with slave/slave bridges only. In addition to meeting the criteria of maintaining connectivity, minimizing the number of piconets and the maximum degree of devices, the proposed algorithm formalizes the notion of network diameter and node contention. The loop scatternet thus formed incurs a much smaller network diameter and the number of node pairs for which a device has to serve, as a relay node is significantly smaller than that in the other types of scatternets. To validate the design, we derive the bounds of the number of piconets, the network diameter, and the maximum node contention. We also conduct ns-2 simulation to evaluate the performance of loop scatternets. Both analytical and simulation results validate the desirable features of loop scatternets.

Directional antennas have been recently suggested to be used in wireless ad hoc networks to reduce interference outside the antenna direction and to increase spatial reuse of wireless channels. Several MAC schemes that exploit directional antennas have been proposed, among which the two D-MAC schemes proposed in [5] may have received the most attention. In this paper, we carefully analyze how the second D-MAC scheme proposed in [5] operates in the hidden/exposed terminal scenarios and show that it not only introduces new collisions, but also reduces spatial reuse to some extent. To remedy these problems, we propose an enhanced version of the second D-MAC scheme, called fragmentation based D-MAC (FD-MAC), to reduce collision, to achieve better spatial reuse (than the second D-MAC scheme), and to improve fairness. Through ns-2 simulation, we demonstrate the effectiveness of FD-MAC, and in particular, we show that in complex scenarios such as multihop forwarding and mesh topologies, FD-MAC significantly outperforms DCF with RTS/CTS and the two D-MAC schemes, both in terms of throughput and fairness.

Energy constraint has become an important factor in the design of MAC protocols. This paper addresses the issue of providing deterministic timing guarantees in the wireless LAN while minimizing energy consumption of the wireless nodes. We present a centralized energy efficient algorithm, Scheduled Contention Free Burst (S-CFB), which is built upon the recently proposed Hybrid Coordination Function (HCF) in the IEEE 802.11 standard. Two mechanisms are proposed: 1) bundling message transmissions into multiple contention free bursts in order to reduce control overhead; 2) allowing wireless nodes to sleep by avoiding preemption whenever possible. Our performance stud), shows that SCFB meets the timing requirement for real-time messages, allows wireless nodes to switch to idle state for a longer period of time, and reduces the number of control frames required to maintain contention free transmission.

In the paper, we devise and evaluate a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we envision a hierarchical sensor network that is composed of (a) a static backbone of sparsely placed high-capability sensors which assume the role of a cluster head (CH) upon triggered by certain signal events; and (b) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a pre-determined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. We address and devise solution approaches (with the use of Voronoi diagram) to realize dynamic clustering: (I1) how CHs cooperate with one another to ensure that for the most of time only one CH (preferably the CH that is closest to the target) is active; (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with non-redundant, essential information to determine the target location; and (I3) both packets with which sensors respond to their CHs and packets that CHs report to subscribers do not incur significant collision. Through both probabilistic analysis and ns-2 simulation, we show with the use of Voronoi diagram, the CH that is usually closest to the target is (implicitly) selected as the leader and that the proposed dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.

In this paper, we consider the problem of how to represent the locations of Internet hosts in a Cartesian coordinate system to facilitate estimate of the network distance between two arbitrary Internet hosts. We envision an infrastructure that consists of beacon nodes and provides the service of estimating network distance between two hosts without direct delay measurement. We show that the principal component analysis (PCA) technique can effectively extract topological information from delay measurements between beacon hosts. Based on PCA, we devise a transformation method that projects the distance data space into a new coordinate system of (much) smaller dimensions. The transformation retains as much topological information as possible and yet enables end hosts to easily determine their locations in the coordinate system. The resulting new coordinate system is termed as the Internet Coordinate System (ICS). As compared to existing work (e.g., IDMaps [1] and GNP [2]), ICS incurs smaller computation overhead in calculating the coordinates of hosts and smaller measurement overhead (required for end hosts to measure their distances to beacon hosts). Finally, we show via experimentation with real-life data sets that ICS is robust and accurate, regardless of the number of beacon nodes (as long as it exceeds certain threshold) and the complexity of network topology.

In this paper, we present an analytical TCP model that takes into account of several issues that were ignored in the other existing models (such as those in F. Kelly (2001) and V. Mishra et al. (2000)), i.e., the congestion window is not gradually decreased at the rate of /spl omega//sup 2/p/2, but suddenly halved upon receipt of congestion indication and the congestion window is halved at most once during one round-trip time (RTT). We also include the delayed ACK option in the model. With the use of state feedback control theory, we then design, based on the enhanced TCP model, an AQM controller to stabilize the queue length at routers. The performance of the new controller is shown, via ns-2 simulation to outperform several other schemes under a variety of network scenarios and traffic loads, in terms of fluctuation in the queue length, link utilization, and packet loss ratio.

In this paper we present three theoretically grounded methods: prediction, reconstruction and interpolation, for measuring cross traffic on the bottleneck link of an end-to-end path. The objective is to infer cross traffic as accurately as possible, while not injecting a significant amount of probe packets into the network. In the prediction-based method, we take advantage of the LRD characteristic of the cross traffic to predict the future traffic based on the recent information obtained by probe packets. In the reconstruction method, we rebuild the entire cross traffic process with the information obtained by probe packets. In the interpolation method, we periodically send closely-spaced probe packet pairs to sample cross traffic of the bottleneck link, and infer cross traffic between two sampling points using interpolation. The simulation study indicates that (i) the prediction-based and reconstruction methods can give good mean measurement of cross traffic, while the interpolation method usually captures the instantaneous value of cross traffic better; and (ii) all three methods are adaptive to the dynamic change of cross traffic and are quite robust in the presence of multiple bottleneck links on an end-to-end path.

In this paper, we present a minimum spanning tree (MST) based topology control algorithm, called local minimum spanning tree (LMST), for wireless multi-hop networks. In this algorithm, each node builds its local minimum spanning tree independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: (1) the topology derived under LMST preserves the network connectivity; (2) the node degree of any node in the resulting topology is bounded by 6; and (3) the topology can be transformed into one with bidirectional links (without impairing the network connectivity) after removal of all uni-directional links. These results are corroborated in the simulation study.

In this paper, we develop a model-based frame scheduling scheme, called MFS, to enhance the capacity of IEEE 802.11-operated wireless LANs (WLANs). In MFS each node estimates the current network status by keeping track of the number of collisions it encounters between its two consecutive successful frame transmissions, and, based on the the estimated information, computes the current network utilization. The result is then used to determine a scheduling delay that is introduced (with the objective of avoiding collision) before a node attempts for transmission of its pending frame. In order to accurately calculate the current utilization in WLANs, we develop an analytical model that characterizes data transmission activities in IEEE 802.11-operated WLANs with/without the RTS/CTS mechanism, and validate the model with ns-2 simulation. All the control overhead incurred in the physical and MAC layers, as well as system parameters specified in IEEE 802.11 are figured in.We have conducted a comprehensive simulation study to evaluate MFS in perspective of number of collisions, achievable throughput, and inter-transmission delay. The simulation results indicate that the performance improvement with respect to protocol capacity can be as high as 20% with RTS/CTS and 150% without RTS/CTS, in a WLAN of up to 300 nodes. In addition, the inter-transmission delay in MFS is smaller and exhibits less variation than that in IEEE 802.11.

Due to the slow advancement of battery technology, power management in wireless networks remains to be a critical issue. Asynchronous wakeup has the merits of not requiring global clock synchronization and being resilient to network dynamics. This paper presents a systematic approach to designing and implementing asynchronous wakeup mechanisms in ad hoc networks. The optimal wakeup schedule design can be formulated as a block design problem in combinatorics. We propose a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wakeup schedule derived. Two power management policies, i.e. slot-based power management and on-demand power management, are studied to overlay desirable communication schedule over the wakeup schedule mandated by the asynchronous wakeup mechanism. Simulation studies indicate that the proposed asynchronous wakeup protocol is quite effective under various traffic characteristics and loads: energy saving can be as high as 70%, while the packet delivery ratio is comparable to that without power management.

Sensor networks can be considered distributed computing platforms with many severe constraints, including limited CPU speed, memory size, power, and bandwidth. Individual nodes in sensor networks are typically unreliable and the network topology dynamically changes, possibly frequently. Sensor networks also differ because of their tight interaction with the physical environment via sensors and actuators. Because of this interaction, we find that sensor networks are very data-centric. Due to all of these differences, many solutions developed for general distributed computing platforms and for ad-hoc networks cannot be applied to sensor networks. After discussing several motivating applications, this paper first discusses the state of the art with respect to general research challenges, then focuses on more specific research challenges that appear in the networking, operating system, and middleware layers. For some of the research challenges, initial solutions or approaches are identified.

As multicast applications have become widely deployed on the Internet, it is increasingly important to ensure these applications respond to network congestion in a TCP-friendly manner so as to coexist with TCP connections (which constitute the majority of the Internet traffic). We present a RAte-based Congestion COntrOI scheme for Multicast, called RACCOOM, for applications that deploy source-based multicast trees as the communication paradigm. In the absence of packet loss, a RACCOOM session keeps track of the congestion status of the on-tree path with the largest round trip time (called the target path) and adjusts its sending rate using a TCP Vegas [L. S. Brakmo et al., (1995)]-like method. Upon detection of packet loss anywhere in the multicast tree, RACCOOM then responds by reducing its sending rate by half in a TCP-Reno manner. The ACK aggregation method used in RACCOOM prevents ACK implosion and yet provides the sender with a simple but comprehensive view of congestion conditions in the multicast tree. Finally, RACCOOM is equipped with mechanisms to deal with changes of the target path due to traffic change and member join/leave. To achieve TCP-friendliness, we have devised a simple method in RACCOOM to emulate how a TCP connection would behave under the same packet loss and delay characteristics. The results thus derived are used by RACCOOM to online adjust the parameters of its rate adjustment method. Alternatively, we can achieve (weighted) fairness (in terms of bandwidth sharing) among competing RACCOOM connections based on results obtained from feedback control theory. We validate the design, and demonstrate the features, of RACCOOM in ns-2. The encouraging simulation results, coupled with the fact that all the RACCOOM operations except acknowledgment aggregation (which requires modest router support) can be performed at end hosts, suggest that RACCOOM is a practical and yet effective congestion control solution for multicast applications.

In this paper, we address the problems of constructing both source-based and core-based many-to-many multicast trees for applications with delay and/or delay jitter constraints. We use the source-destination delay bound and the interdestination delay fitter bound as the QoS requirement and formulate the delay and delay jitter constrained many-to-many multicast tree (D/sup 2/M/sup 3/T) problems. For the source-based, many-to-many multicast paradigm, we extend an existing scheme that builds a one-to-many, QoS-compliant multicast tree and devise a solution scheme that first finds a feasible multicast tree for each source node in the multicast group and then a minimum cover of these multicast trees such that there exists at least one feasible multicast tree in the minimum cover for each source node. For the core-based, many-to-many multicast paradigm, we first derive a necessary and sufficient condition for a core-based multicast tree to be feasible and then devise a solution scheme based on the condition derived. We validate and evaluate both proposed schemes via simulations.

We propose an enhancement to DSR, called DSR with Connection-Aware Link-state Exchange aNd DiffERentiation (DSR-CALENDER). Specifically, to effectively collect and disseminate neighbor link states to nodes which may potentially use them, we devise a neighbor link-state information exchange mechanism: once a connection has been established, the neighbor link-state information is exchanged among nodes along the route from the source to the destination. As the information of the neighbor lists is piggybacked in data packets, the nodes on the source route are able to learn the partial topology around the neighborhood of the connection. In this manner, DSR-CALENDER balances the gain obtained from additional neighbor link states and the overhead incurred to distribute them. In the case that link failure occurs, an alternate route can be more effectively located in the route cache of the source or the intermediate nodes, and the number of times the route discovery phase is invoked can be reduced. To improve the quality of route caches, we investigate all possible sources from which a node may learn of its link states, and associate each of the sources with a different level of fidelity. In the case that a new/alternate route has to be computed, the level of fidelity is figured into the link cost so as to locate a route that likely exists. The simulation results show that with limited overhead incurred in neighbor list dissemination, DSR-CALENDER outperforms DSR with either path or link caches in terms of packet delivery ratio and route discovery overhead.

Analytical and empirical studies have shown that self-similar traffic can have a detrimental impact on network performance including amplified queuing delay and packet loss ratio. On the flip side, the ubiquity of scale-invariant burstiness observed across diverse networking contexts can be exploited to design better resource control algorithms. We explore the issue of exploiting the self-similar characteristics of network traffic in TCP congestion control. We show that the correlation structure present in long-range dependent traffic can be detected on-line and used to predict future traffic. We then devise an novel scheme, called TCP with traffic prediction (TCP-TP), that exploits the prediction result to infer, in the context of AIMD (additive increase, multiplicative decrease) steady-state dynamics, the optimal operational point for a TCP connection. Through analytical reasoning, we show that the impact of prediction errors on fairness is minimal. We also conduct ns-2 simulation and FreeBSD 4.1-based implementation studies to validate the design and to demonstrate the performance improvement in terms of packet loss ratio and throughput attained by connections.

Abstract — Analytical and empirical studies have shown that selfsimilar traffic can have detrimental impact on network performance including amplified queuing delay and packet loss ratio. On the flip side, the ubiquity of scale-invariant burstiness observed across diverse networking contexts can be exploited to better design resource control algorithms. In this paper, we explore the issue of exploiting traffic predictability to enhance the performance of active queue management (AQM). We show that the correlation structure present in long-range dependent traffic can be detected on-line and used to accurately predict the future traffic. To this end, we design and introduce two non-model-based traffic predictors: LMMSE and simple. We then figure in, with the objective of stabling the instantaneous queue length, the prediction results in the calculation of the packet dropping probability. The resulting scheme is termed as predictive AQM (PAQM).

Abstract It is well known that the performance of TCP deteriorates in a mobile wireless environment. This is due to the fact that although the majority of packet losses are results of transmission errors over the wireless links, TCP senders still take packet loss as an indication of congestion, and adjust their congestion windows according to the additive increase and multiplicative decrease (AIMD) algorithm. As a result, the throughput attained by TCP connections in the wireless environment is much less than it should be. The key problem that leads to the performance degradation is that TCP senders are unable to distinguish whether packet loss is a result of congestion in the wireline network or transmission errors on the wireless links. In this paper, we propose a light‐weight approach, called syndrome, to improving TCP performance in mobile wireless environments. In syndrome, the BS simply counts, for each TCP connection, the number of packets that it relays to the destination host so far, and attaches this number in the TCP header. Based on the combination of the TCP sequence number and the BS‐attached number and a solid theoretical base, the destination host will be able to tell where (on the wireline or wireless networks) packet loss (if any) occurs, and notify TCP senders (via explicit loss notification, ELN) to take appropriate actions. If packet loss is a result of transmission errors on the wireless link, the sender does not have to reduce its congestion window. Syndrome is grounded on a rigorous, analytic foundation, does not require the base station to buffer packets or keep an enormous amount of states, and can be easily incorporated into the current protocol stack as a software patch. Through simulation studies in ns‐2 (UCB, LBNL, VINT network simulator, http://www‐mash.cs.berkeley.edu/ns/ ), we also show that syndrome significantly improves the TCP performance in wireless environments and the performance gain is comparable to the heavy‐weight SNOOP approach (either with local retransmission or with ELN) that requires the base station to buffer, in the worst case, a window worth of packets or states. Copyright © 2001 John Wiley & Sons, Ltd.

The Mobile IP standard for mobility management on the Internet enables transparent communication between mobile hosts (MH) and their correspondent hosts (CH). However, it suffers from triangular routing and prolonged handoff latency problems. In this paper, we propose to use a temporary home agent (TA) to address both problems. TA exploits the locality of user movement observed in recent studies for personal communication services (PCS) and wireless data networks. It dynamically selects a Mobile IP-based HA based on the location of the user. The TA allocates a temporary home address, THAddr to the MH, which the MH may use as its source address. The underlying objective is to shorten the distance between a MH and its home agent, which is a critical factor in reducing handoff latency and improving routing efficiency. Through both quantitative analysis and ns-2 simulation, we show that the TA approach outperforms Mobile IP and achieves comparable performance to route optimization (RO). While the TA approach focuses on improving the performance of traffic for sessions that are initiated by the MH, methods for optimizing traffic handling for sessions initiated by CH are discussed.

In this paper, we document our design of a MAC protocol, called OSU-MAC, subject to the physical layer characteristics and constraints of a narrow-band wireless modem testbed currently being built at the Ohio State University. The narrow-band wireless modem testbed is expected to support both real-time (bus location tracking) and non-real-time (regular) data applications. A number of techniques are proposed to support QoS imposed by the real-time applications, to deal with the asymmetry on the forward and reverse channels and the half-duplex transmission constraint imposed by the physical layer, and to enhance the error control capability of OSU-MAC. We also present simulation results to demonstrate the key functional characteristics of OSU-MAC.

This paper extends the concept of multicast to quorumcast, a generalized form of multicast communication. The need of quorumcast communication arises in a number of distributed applications. Little work has been done on routing quorumcast messages. The objective of previous research was to construct a minimum cost tree spanning the source and the quorumcast group members. We further consider the path quality of a constructed spanning tree in terms of delay constraints required by applications that use the tree. As the delay-constrained quorumcast routing problem is NP-complete, we propose an efficient heuristic QoS routing algorithm. We also consider how a loop is detected and removed in the course of tree construction and how to deal with members joining/leaving the quorumcast pool. Our simulation study shows that the proposed algorithm performs well and constructs a quorumcast tree whose cost is close to that of the "optimal" routing tree.

One of the key issues in tailoring the timed-token MAC protocol for real-time applications is synchronous bandwidth allocation (SBA), whose objective is to meet both the protocol and deadline constraints. The former constraint requires that the total time allocated to all nodes for transmitting synchronous messages should not exceed the target token rotation time. The latter constraint requires that the minimum time available for a node to transmit its synchronous messages before their deadlines should be no less than the maximum message transmission time. Several nonoptimal local SEA schemes and an optimal global SBA scheme have been proposed. Local SBA schemes use only information available locally to each node and are thus preferred to global schemes because of their lower network-management overhead. If optimal local SBA schemes, if any, can be devised, they will be superior to their global counterparts both in performance and in ease of network management. In this paper, we formally prove that there does not exist any optimal local SBA scheme. We also propose an optimal global SBA scheme which has an O(nM) polynomial-time worst-case complexity, where n is the number of synchronous message streams in the system and M is the time complexity for solving a linear programming problem with 3n constraints and n variables.

In this paper, we devise a preallocation-based single-hop wavelength division multiple access (WDMA) scheme to support temporal quality of service (QoS) in star-coupled optical networks, We consider a star-coupled broadcast-and-select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the !V stations by means of time division multiplexing. Depending on the tunability characteristics (tunable or fixed tuned) of the transmitters/receivers, we classify the network architecture as tunable transmitter/fixed tuned receiver (TT-FR), fixed tuned transmitter/tunable receiver (FT-TR), and tunable transmitter/tunable receiver (TT-TR). We first characterize each real-time message stream M/sub i/, with two parameters, the relative message deadline D/sub i/ and the maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR (or FT-TR) system in which the message streams from a source station are assumed to be all destined for the same destination station. Under this assumption, no source destination conflicts may occur. We propose a preallocation-based slot assignment scheme to preallocate slots to a set of isochronous message streams, (M/sub i/=(C/sub i/, D/sub i/)|1/spl les/i/spl les/n) in such a way that, in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system and propose a binary splitting scheme to assign each message stream sufficient and well-spaced slots to fulfil its temporal requirement, subject to the source/destination conflict constraints. We rigorously prove the invariance properties, and the correctness, of the binary splitting scheme.

We propose a new active queue management algorithm, called average rate early detection (ARED). An ARED gateway measures/uses the average packet enqueue rate as a congestion indicator, and judiciously signals end hosts of incipient congestion, with the objective of reducing packet loss ratio and improving link utilization. We show (via simulation in ns-2) that the performance of ARED is better than that of RED and comparable to that of BLUE in terms of packet loss rate and link utilization. We also explore the use of ARED in the context of the differentiated services architecture. We show analytically that the widely referenced queue management mechanism, RED with in and out (RIO) cannot achieve throughput assurance and proportional bandwidth sharing. We then extend ARED and propose a new queue management mechanism, called ARED with in and out (AIO), in the assured services architecture. To share surplus bandwidth in a rate-proportional manner, we incorporate into AIO the derived analytic results, and propose an enhanced version of AIO, called the differentiated-rate AIO (DAIO) mechanism.

Reliable multicast is one of the the important and challenging problems that must be effectively resolved before multicast applications can be fully deployed on the Internet. Most existing reliable multicast schemes focus on source-based multicast trees. They either cannot be directly deployed in core-based multicast trees or may render sub-optimal performance when directly deployed. The major difficulty lies in that an on-tree router on a core-based tree does not know, due to lack of the per-source information, how to direct a retransmission request (NAK) toward the sender or some designated replier router/host. We design and evaluate a reliable multicast scheme for core-based multicast trees, called RMCM. RMCM closely emulates the optimal recovery scenario achieved in the turning point approach. Specifically we define new IP options to carry path information in both data packets and NAKs and design a simple, yet effective scheme to facilitate routers on a core-based tree to properly direct NAKs/replies, even in the existence of clouds (of reliable-multicast-incapable routers). To conduct local recovery in the case of group membership and topology changes, we devise a mechanism that selects designated hosts (called repliers) which are most likely to have the requested packet and to which NAKs will be forwarded. We also devise a delayed ACK approach so that both sources and repliers can purge data packets that have been received by all the group members. The event-driven simulation study indicates that RMCM achieves better performance than most existing repair-based reliable multicast schemes, in terms of NAK implosion control, recovery latency, recovery isolation, and capability to deal with clouds. Finally, our experiences with implementing RMCM on FreeBSD 2.2.8 show that the add-on overheads to routers are reasonably small.

We design an effective multicast routing algorithm for distributing layered multicast video to heterogeneous receivers in networks with rate-based link schedulers. The multicast tree constructed by the algorithm fulfils the QoS requirements imposed by heterogeneous receivers both in terms of bandwidth and delay, and at the same time, consumes as little network resource as possible. For the purpose of scalability, the proposed multicast routing algorithm is decentralized and can adapt to network and membership change. To facilitate construction of such a multicast tree in a distributed manner we equip each node with an auxiliary routing table, and propose procedures for updating/maintaining the auxiliary routing table. Simulation results indicate that the multicast tree constructed by the proposed algorithm is more resource efficient than those constructed by other existing algorithms, especially when there exist multiple alternative paths to multicast receivers in the network.

Several medium access control (MAC) schemes have been developed for dual-bus networks such as DQDB, Fasnet, CRMA, and Simple. However, how to guarantee the timely delivery of isochronous (real-time) messages with hard deadline constraints is one of the open issues yet to be solved. In Han, Hou and Shin (1997), we laid a formal basis for allocating prearbitrated slots to isochronous message streams in dual-bus networks and devised a slot allocation scheme to statically establish a set of isochronous message streams at system initialization. In this paper, we complement our work in Han, Hou and Shin (1997) and propose, with the necessary theoretical base established, a dynamic message stream setup and tear-down scheme for dual-bus networks. The resulting channel establishment and termination procedures are simple and can be easily implemented in dual-bus networks.

In this paper, we propose a packet eligible time calculation mechanism and its associated information update method to provide temporal QoS to multicast services, in terms of delay bound coupled with inter-message delay jitter bound and/or bounded inter-destination delay jitter bound. We assume the availability of a multicast tree on which the delay between a source and any destination falls within the end-to-end delay bound. We then exploit the idea of artificially delaying transmission of data packets until their eligible times, and model each router as a regulator followed by a packet scheduler. A data packet is not eligible to be scheduled until the current time is greater than or equal to its eligible time. For each temporal QoS required, we derive the appropriate packet eligible times. We also devise an information update method to collect/update in a decentralized manner the parameters needed in the calculation of packet eligible times. With all the parameters available, an intermediate router can calculate packet eligible times and the upper bound on the buffers needed in order to fulfill the QoS. Finally, we validate the proposed mechanism in terms of the probability of locating feasible-multicast trees and message overheads, and scalability with event-driven simulations.

In this paper, we develop efficient admission control tests for member join/leave and its associated state refresh and update procedures for receiver-initiated core-based multicast routing, e.g., core based tree (CBT) protocol, to allow construction of QoS-capable multicast trees, while making the minimum possible impact on the existing infrastructure. Specifically, we (i) derive sufficient conditions for a multicast tree to maintain its QoS; (ii) devise effective admission tests to verify whether or not a group member may join the multicast tree at adequate QoS, while not violating existing QoS guarantees to other on-tree members; and (iii) identify the minimum set of state information required for the admission tests and develop a soft state refresh and update procedure. Finally, we validate the effectiveness of the proposed mechanism by incorporating it into the CBT protocol, and evaluate it via event-driven simulations in terms of the probability of join requests being rejected, message overhead, and scalability.

In this paper, we study why the current assurance services (AS) architecture with profilers/markers at edge routers and with queue management mechanisms (RIO) at core routers cannot achieve throughput assurance and fairness. Based on the findings of the simulation study, we propose an enhanced version of the time sliding window (TSW) profiler, called the enhanced TSW (ETSW). We also design two enhanced versions of the RIO queue management mechanism, based on rigorous, analytical reasoning, called respectively, the (r,RTT)-adaptive algorithm and the dynamic RIO (DRIO) algorithm. To validate the proposed design, we implement the proposed mechanisms, along with the 2-window TCP scheme, the three color-marker scheme, and the CSFQ scheme in ns-2, and examine their behavior under a variety of network topologies and traffic sources. The simulation results indicate that both DRIO and (r,RTT)-adaptive algorithms, when combined with ETSW, do fulfill better throughput assurance and fairness, especially under the case that AS flows require different target rates, incur different round trip times, or co-exist with non-responsive UDP flows.

We develop and evaluate a set of member join/leave and state update/refresh procedures for QoS provisioning in core-based multicast routing with explicit member join and soft state refresh procedures. Specifically, in our prior work (Hung-Ying Tyan et al., 1999), we devised eligibility tests to verify whether or not a new member can join a multicast tree at adequate QoS while not violating the existing QoS guarantees to other on-tree members. We extend our prior work, identify the tradeoff between the amount of state kept at each on-tree router and the degree of collaboration among on-tree routers to conduct the tests, and develop two member join/leave procedures that range from using the most comprehensive state update procedure (and hence the least degree of collaboration among on-tree routers) to the other extreme. Also, we evaluate the proposed framework, in terms of the probability of locating feasible multicast trees, message overheads, and scalability.

Real-time communication with performance guarantees is expected to become an important feature of future computer networks used for embedded real-time systems and/or for interactive multimedia services. Given an ATM network topology, its virtual path (VP) layout, and its traffic demands, we consider in this paper the problem of selecting for each virtual circuit (VC) with user-specified end-to-end temporal QoS requirements a route (i.e., a sequence of VPs) along which sufficient resources are available to meet the delay requirements. Our objective is 1) to provide the temporal QoS guarantee for each VC to be established while not jeopardizing the QoS guarantees to other existing VCs and 2) to reduce the call blocking probability for future VCs by using the minimum possible resources. We adopt the real-time channel model to characterize the traffic characteristics and the temporal QoS requirement of a VC. We impose a deterministic guarantee that every message generated at the source node be delivered to the destination node in a time period no longer than the relative deadline. We then propose a VC routing scheme based on the distributed Bellman-Ford algorithm to identify an "appropriate" route through the network. By "appropriate", we mean that the route traverses a minimum number of VPs among all possible routes that have sufficient resources to fulfill the end-to-end temporal QoS requirement of the VG to be established. To ensure that sufficient bandwidth is available over all the VPs along the selected route, we incorporate in our proposed scheme a priority assignment method to calculate the worst-case delay which messages of a VC will experience on a VP along which the VC is routed. We study the performance of, and the message overhead incurred in, the proposed scheme. We also discuss how to extend the proposed routing scheme to accommodate multicast routing.

We propose a novel MAC protocol, called quality-of-service guarantee multiple access (QGMA), in wireless local area networks to support the quality-of-service required by embedded real-time applications and multimedia-integrated distributed control. As compared to other existing MAC protocols, QGMA achieves high system utilization, and provides a deterministic bound on the connection establishment delay and temporal QoS for real-time applications. In particular by having the base station handle resource arbitration and utilize different scheduling algorithms to arbitrate access to data slots on a wireless channel, mobile hosts (MHs) are relieved from the burden of coordinating all the ongoing activities, and moreover different levels of temporal QoS can be easily achieved.

There has been an increasing need of highly predictable, timely, and dependable communication services with QoS guarantees on an end-to-end basis either for embedded real-time applications or for multimedia-integrated distributed control. Performance objectives used in conventional networks-such as maximizing the throughput, minimizing the response time, or providing fairness to users-are not of the most important concern for both types of applications. Instead, resources should be appropriately reserved and managed to support multidimensional quality of service (QoS) on an end-to-end basis, as well as application-specific tradeoffs among them. The main intent of the paper is thus to address and demonstrate an environment-an integrated set of network resource management techniques, middleware layers, and network software-for supporting multi-dimensional QoS on an end-to-end basis in distributed real-time environments. The authors first provide an analytic QoS framework Then, they elaborate on the algorithms and mechanisms to provide such network services. To empirically analyze the behavior of the proposed components, they are currently implementing them as software layers on top of the Sun Solaris operating system, and comment on the implementation status.

In this paper, we propose a fast restoration mechanism for virtual path-based ATM networks. Given an ATM network topology, the capacity of each physical link, and the primary virtual path (VP) layout at system initialization, the proposed mechanism pre-assigns to each primary VP one backup VP such that (P1) the failure of a single node/link does not lead to the failure of both the primary and backup VPs, (P2) the alternate backup VP is routed on a path with the shortest hop count among all possible paths with sufficient bandwidth between the two VP terminators, and (P3) the maximum link load is minimized. During system operation, if a physical node/link fails, the proposed mechanism restores the VPs that traverse the failed node/link simply by redirecting cells on the failed VPs to their corresponding backup VPs. Moreover, the proposed mechanism also locates (i) new VPs for injured backup VPs that traverse the failed node/link, and (ii) second-generation backup VPs for newly-activated backup VPs that replace their corresponding failed primary VPs, both in a decentralized manner. We elaborate on all the component algorithms, and discuss how to configure the functionalities as software daemons that reside at each network node. The proposed mechanism is shown via event-driven simulation to be practically feasible in fast restoring failed VPs in a cost effective manner.

To complement the prior work of Kung-Ying Tyan, Chao-Ju Hou, Bin Wang and Ching-Chih Han (see Proc. IEEE 17th Real-Time Systems Symposium, Washington DC, 1996), we address the problem of dynamically establishing/terminating real-time message streams in response to call setup/clear requests in single-hop star-coupled WDMA-based optical networks. We consider a network architecture in which N stations are connected to a star coupler with W data channels (W/spl les/N) and one control channel. Each of the W data channels is slotted and shared by the N stations by means of time division multiplexing. The control channel is used for stations to coordinate the call establishment and termination operations. We propose a distributed, dynamic slot allocation scheme to allocate/deallocate, in response to call setup/clear requests, time slots on the W data channels to message streams, with the objective of meeting message deadlines. We formally prove the properties, and the correctness of, the proposed dynamic slot allocation scheme.

Several access schemes have been suggested for dual-bus network topology, e.g., DQDB, Fasnet, CRMA, and Simple. It is therefore important to provide various services in this type of networks. This paper addresses the issue of guaranteeing the timely delivery of isochronous (real-time) messages with hard deadlines in slotted dual-bus networks. We propose a slot allocation scheme which can allocate bandwidth for a set of isochronous message streams and provide deterministic deadline guarantees. The proposed slot allocation scheme is guaranteed to find a feasible slot allocation in the sense that all messages can be transmitted in a timely manner as long as the total message density is less than or equal to a certain threshold, where the total message density is defined as the summation of the ratio of maximum message size to message deadline over all streams. We also discuss the implementation details of this scheme, and compare our scheme with another bandwidth allocation scheme proposed by D. Saha et al. (1994).

This paper addresses the problem of allocating (assigning and scheduling) periodic task modules to processing nodes in distributed real-time systems subject to task precedence and timing constraints. Using the branch-and-bound technique, a module allocation scheme is proposed to find an "optimal" allocation that maximizes the probability of meeting task deadlines. The task system within a planning cycle is first modeled with a task flow graph which describes computation and communication modules, as well as the precedence constraints among them. To incorporate both timing and logical correctness into module allocation, the probability of meeting task deadlines is used as the objective function. The module allocation scheme is then applied to find an optimal allocation of task modules in a distributed system. The timing aspects embedded in the objective: function drive the scheme not only to assign task modules to processing nodes, but also to use a module scheduling algorithm (with polynomial time complexity) for scheduling all modules assigned to each node, so that all tasks maybe completed in time. In order to speed up the branch-and-bound process and to reduce the computational complexity, a dominance relation is derived. Several numerical examples are presented to demonstrate the effectiveness and practicality of the proposed scheme.

Real-time communication with performance guarantees is expected to become an important feature of future computer networks. Given an ATM network topology, its virtual path (VP) layout, and its traffic demands, we consider in this paper the problem of selecting for each virtual circuit (VC) with timing requirements a route (i.e., a sequence of VPs) along which sufficient resources are available to meet the user-specified end-to-end delay requirements. Our objective is to (i) provide the timing guarantee for the VC, while not jeopardizing the QoS guarantees to other existing VCs. We adopt the real-time channel model to characterize the traffic characteristics and the timing requirements of a VC. We then propose a distributed VC routing scheme based on the distributed Bellman-Ford algorithm to identify an "appropriate" route through the network. By "appropriate", we mean that the route traverses a minimum number of VPs among all possible routes that have sufficient resources over to fulfill the end-to-end timing requirement of the VC. To ensure that there are sufficient bandwidths over all the VPs along the selected route, we incorporate in our proposed scheme a priority assignment method to calculate the minimum worst-case traversal time which messages of a VC will experience on a VP along which the VC is routed. We also comment on the performance of, and the message overhead incurred in the proposed scheme.

Based on the POPSMAC protocol proposed in Chung-Sheng Li et al. (1993), we propose an improved medium access protocol for wavelength division multiple access (WDMA) photonic networks. Using the same set of photonic devices as in POPSMAC, the proposed protocol alleviates the drawbacks of the POPSMAC protocol, e.g., invalid data transmissions following receiver collisions and possible acknowledgement packet collisions with header/data packets, while retaining many advantages of POPSMAC. As a result, the network performance in terms of the throughput and the packet delay is improved. Analytical models based on the timing diagram analysis, the continuous-time Markov chain, and the randomization technique are developed to assess the performance of the proposed protocol. The performance is evaluated in terms of channel utilization, mean packet delay, and packet delay distribution with variations in the number of nodes, the offered traffic, the size of data packets, and the network propagation delay. Numerical results show that the proposed protocol achieves better channel utilization and incurs lower packet delays than POPSMAC.

We devise a preallocation based single hop wavelength division multiple access (WDMA) scheme to support time constrained communication in star coupled optical networks. We consider a star coupled broadcast and select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the N stations by means of time division multiplexing. Networks with different transceiver configurations, i.e., TT-FR, FT-TR, and TT-TR systems, are investigated. We characterize each real time message stream M, with two parameters, relative message deadline D/sub i/ and maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR system in which the message streams from a source station are assumed to be all going to the same destination station. Under this assumption, no source/destination conflicts may occur. We propose a preallocation based slot assignment scheme to allocate slots to a set of isochronous message streams, {M/sub i/=(C/sub i/, D/sub i/))|1/spl les/i/spl les/n}, so that in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system, and propose a binary splitting scheme to assign each message stream sufficient and well spaced slots to fulfill its timing requirement, subject to source/destination conflict constraints. We rigorously prove the invariant properties and the correctness of the binary splitting scheme.

In hard real time systems, each task must not only be functionally correct but also meet its timing constraints. A common approach to characterizing hard real time tasks with repetitive requests is the periodic task model. In the periodic task model, every task needs to be executed once during each of its periods. The execution of a task in one period is independent of the execution of the same task in another period. Hence, the executions of the same task in two consecutive periods may be right next to each other, or at the far ends of the two periods. While the periodic task model can serve as a simple paradigm for scheduling tasks with repetitive requests, it may not be suitable for all real time applications. For example, in some real time systems, the temporal distance between the finishing times of any two consecutive executions of the same task must be less than or equal to a given value. In other words, each execution of a task has a deadline relative to the finishing time of the previous execution of the same task. Scheduling algorithms designed for the periodic task model may not provide efficient solutions for tasks with temporal distance constraints. We propose the (preemptive) distance constrained task system model which can serve as a more intuitive and adequate scheduling model for "repetitive" task executions. We design an efficient scheduling scheme for the model, and derive a schedulability condition for the scheduling scheme. We also discuss how to apply the scheduling scheme to real time sporadic task scheduling and to real time communications.

The 'optimal' (in some sense) amount of time used for (or the optimal number of times) retrying an instruction upon detection of an error in a computing system is usually determined under the assumption that the system is composed of a single module, within which all fault activities are confined until some module-replacement action is taken. However, a computing system is usually composed of at least three modules, namely, CPU, memory, and I/O, and the execution of an instruction often requires the cooperation of two or more modules. It is thus more realistic to consider the fault activities in multiple-module systems. In this paper, we first relax the single-module assumption and model the fault activities in a multiple-module system as a Markov process. We apply the randomization method to decompose the continuous-time Markov chain into a discrete-time Markov chain subordinated to a Poisson process. Using this decomposition, we can derive several interesting measures, such as (1) the conditional probability of successful retry given a retry period and the fact that a non-permanent fault has occurred, (2) the mean time-to-system recovery, and (3) the distribution of the time until which all modules in the system enter a fault-free state. All the measures derived are used to determine, along with the parameters characterizing fault activities and costs of recovery techniques, (a) whether or not retry should be used as a first-step recovery means upon detection of an error, and (b) the best retry period or number of retries that satisfies a given criterion, e.g., a specific probability of successful retry.

We rigorously analyze load sharing (LS) in a distributed real-time system, called HARTS (Hexagonal Architecture for Real-Time Systems), while considering LS-related communication activities, such as task transfers and state-change broadcasts. First, we give an overview of the general distributed real-time LS approach described previously, and then adapt it to HARTS by exploiting the topological properties of HARTS. Second, we model task arrival/completion/transfer activities in HARTS as a continuous-time Markov chain from which we derive the distribution of queue length and the rate of generating LS-related traffic-task transfer-out rate and state-region change broadcast rate. Third, we derive the distribution of packet delivery time as a function of LS-related traffic rates by characterizing the hexagonal mesh topology and the virtual cut-through capability of HARTS. Finally, we derive the distribution of task waiting time (the time a task is queued for execution plus the time it would spend if the task is to be transferred), from which the probability of a task failing to complete in time, called the probability of dynamic failure, can be computed. The results obtained from our analytic models are verified through event-driven simulations, and can be used to study the effects of varying various design parameters on the performance of LS while considering the details of LS-related communication activities.

In 1993, the authors described the design of the AN2 switch which supports high-performance distributed computing. The switch's operation is based on the parallel iterative matching algorithm to find a maximal matching between the inputs and the outputs of the switch. The number of iterations needed to find a maximal matching in their algorithm is N in the worst case, and of time complexity O(log N) in the average case, where N is the size of the switch. We propose an improved parallel iterative matching algorithm which uses the priority lists, instead of randomness, to determine the input/output pairs that can be matched in each iteration. We show that tire proposed algorithm does not suffer from the starvation problem, and needs at most [N/2] iterations to find a maximal matching. We also show via probability analysis and simulation that the proposed algorithm outperforms the original one in the average case, especially when the switch size is large, e.g., for N/spl ges/32. All these merits make it attractive to apply the algorithm to large switches used in ATM networks with high QoS requirements.

DQDB is a MAC protocol jointly adopted by IEEE and ANSI as the candidate protocol for MANs, and has been studied by many researchers. Previously, we laid a formal basis for guaranteeing the timely delivery of isochronous (real-time) messages with hard deadlines, and devised a slot allocation scheme for allocating pre-arbitrated (PA) slots to isochronous message streams in DQDB networks. In this paper, we extend our work and address on how to improve the performance (in terms of bandwidth utilization) of the slot allocation scheme using the concept of slot reuse. We devise several slot reuse schemes to assign spatially non-intersecting message streams to the same virtual connections (i.e., the sets of PA slots identified by the same VCI numbers). The proposed slot reuse schemes are simple, can be easily incorporated into the slot allocation scheme described previously, and require only a minor change in the current DQDB standards.

The distributed queue dual bus (DQDB) protocol has been jointly adopted by IEEE and ANSI as a standard (IEEE802.6) for metropolitan area networks (MANs). As such, how to provide various services in the DQDB protocol has attracted increasing attention. In particular, how to guarantee the timely delivery of isochronous (real-time) messages with hard deadline constraints is one of the open issues yet to be solved. Previously, we laid a formal basis for allocating pre-arbitrated (PA) slots to isochronous message streams in DQDB networks and devised a slot allocation scheme to statically establish a set of isochronous message streams at system initialization. In this paper, we complement our previous work and propose a dynamic channel setup and tear-down scheme for DQDB networks. The resulting channel establishment and termination procedures are simple, can be easily implemented in DQDB networks, and do not require any changes in the current DQDB standards.

In recent years a number of load sharing (LS) mechanisms have been proposed or implemented to fully utilize system resources. We design and implement a decentralized LS mechanism based on the Condor package, and give in this paper a description of our design and implementation approaches. Two important features of the design are the use of region-change broadcasts in the information policy to provide each workstation with timely state information at the minimum communication cost, and the use of preferred list in the location policy to avoid task collisions. With these two features, we remove the central manager workstation in Condor, configure its functionalities into each participating workstation, and thus enhance the capability to tolerate single workstation failure and the reliability of Condor. We also discuss the experiments we conduct on the LS mechanism and the observations we obtained from empirical data.>

Consideration is given to the problem of designing and incorporating a timeout mechanism into load sharing (LS) with state-region change broadcasts in the presence of node failures in a distributed real-time system. Failure of a node is diagnosed by the other nodes through communication timeouts, and the timeout period used to diagnose whether a node is faulty or not usually depends on the dynamic changes in system load, the task attributes at the node, and the state the node was initially in. We formulate the problem of determining the "best" timeout period T/sub out//sup (i)/ for node i as a hypothesis testing problem, and maximize the probability of detecting node failures subject to a pre-specified probability of falsely diagnosing a healthy node as faulty. The parameters needed for the calculation of T/sub out//sup (i)/ are estimated online by node i using the Bayesian technique and are piggy-backed in its region-change broadcasts. The broadcast information is then used to determine T/sub out//sup (i)/. If node n has not heard from node i for T/sub out//sup (i)/ since its receipt of the latest broadcast from node i, it will consider node i failed, and will not consider any task transfer to node i until it receives a broadcast message from node i again. On the other hand, to further reduce the probability of incorrect diagnosis, each node n also determines its own timeout period T/sub out//sup (n)/, and broadcasts its state not only at the time of state-region changes but also when it has remained within a broadcast interval throughout T/sub out//sup (n)/.>

In a heterogeneous distributed real-time system, transferring an unguaranteed task at a node to another node currently with the most abundant resources is not necessarily the best decision. We propose a new load sharing (LS) algorithm for real-time applications which takes into account the effect of future task arrivals on locating the best receiver for each unguaranteed task. Upon arrival of a task at a node, the node first checks whether it can complete the task in time using the minimum-laxity-first-served discipline. If the node cannot guarantee the arrived task, or if some of existing guarantees were to be invalidated as a result of inserting the task into its queue, then the node must locate a remote node to which each unguaranteed task is to be transferred. The LS algorithm minimizes not only the probability of transferring an unguaranteed task T to an incapable node with Bayesian analysis, but also the probability that a remote node fails to guarantee T because of future arrivals of tighter-laxity tasks with queueing analysis. All parameters needed for a node's LS decision are collected/estimated online using time-stamped region-change broadcasts (TSRCBs) and Bayesian estimation. By using TSRCBs, the collected state information can be used to estimate other nodes' states. Use of Bayesian estimation makes the LS algorithm adaptive to dynamically varying workloads with little computational overhead. Simulation results show that the proposed LS algorithm outperforms other LS algorithms in minimizing the probability of dynamic failure, task collisions and excessive task transfers.>

In a distributed real-time system, uneven task arrivals temporarily overload some nodes and leave others idle or underloaded. Consequently, some tasks may miss their deadlines even if the overall system has the capacity to meet the deadlines of all tasks. An effective load-sharing (LS) scheme is proposed as a solution to this problem. Upon arrival of a task at a node, the node determines whether the node can complete the task in time under the minimum-laxity first-served policy. If the task cannot be guaranteed, or if guarantees of some other tasks are to be violated as a result of the addition of this task to the existing schedule, the node looks up the list of loss-minimizing decisions and determines the best node among a set of nodes in its physical proximity, called its buddy set, to which the task(s) may be transferred. This list of decisions is periodically updated using Bayesian decision analysis and prior/posterior state distributions. These probability distributions are derived from the information collected via time-stamped state-region change broadcasts within each buddy set. By characterizing the inconsistency between a node's "observed" state and the corresponding true state with prior and posterior distributions, the node can first estimate the states of other nodes, and then use them to reduce the probability of transferring a task to an "incapable") node. Moreover, the use of prior and posterior distributions and Bayesian analysis has made the proposed scheme robust to the variation of design parameters that usually require fine-tuning for adaptive LS. The performance of the proposed scheme is evaluated via simulation, along with five other schemes: no LS, LS with state probing, LS with random selection, LS with focused addressing, and perfect LS.>

In this paper, we apply the load sharing (LS) mechanism proposed in [1, 2] to HARTS, an experimental distributed realtime system [3] currently being built at the Real-Time Computing Laboratory of the University of Michigan.

In a distributed real-time system, nonuniform task arrivals may temporarily overload some nodes while leaving some other nodes idle. As a result, some of the tasks on an overloaded node may miss their deadlines even if the overall system has the capacity to meet the deadlines of all tasks. A decentralized, dynamic load sharing (LS) scheme has been proposed as a solution to this problem. Analytic queuing models to comparatively evaluate this LS scheme as well as three other schemes-no LS, LS with random selection of a receiver node, and LS with perfect information- are developed. The evolution of a node's load state is modeled as a continuous-time semi-Markov process, where cumulative execution time (CET), rather than the commonly-used queue length (QL), is employed to describe the workload of a node. The proposed scheme is compared against other LS schemes. The validity of analytic models is checked with simulations. Both analytic and simulation results indicate that by using judicious exchange/use of state information and Bayesian decision mechanism, the proposed scheme makes a significant improvement over other existing LS schemes in minimizing the probability of dynamic failure.>

The authors address the problem of allocating (assigning and scheduling) periodic task modules to processing nodes (PNs) in distributed real-time systems subject to task precedence and timing constraints. Using the branch-and-bound technique, a module allocation algorithm (MAA) is proposed to find an optimal allocation that maximizes the probability of meeting task deadlines. To incorporate both timing and logical correctness into module allocation, the probability of meeting task deadlines is used as the objective function. The MAA is then applied to find an optimal allocation of task modules in a distributed system. The timing aspects embedded in the objective function drive the MAA not only to assign task modules to PNs, but also to use a module scheduling algorithm for scheduling all modules assigned to each PN so that all tasks may be completed in time. Several numerical examples are presented to demonstrate the effectiveness and practicality of the proposed algorithms.>

The authors propose a new loading sharing (LS) algorithm for real-time applications that accounts for the effect of future task arrivals on locating the best receiver for each unguaranteed task. The LS algorithm minimizes not only the probability of transferring an unguaranteed task T to an incapable node with Bayesian analysis, but also the probability that a remote node fails to guarantee T because of future arrivals of higher-laxity tasks with queuing analysis. All parameters needed for a node's LS decision are collected/estimated online using time-stamped region-change broadcasts and Bayesian estimation. Simulation results show that the proposed LS algorithm outperforms other existing algorithms in minimizing the probability of dynamic failure, task collisions, and excessive task transfers. The performance improvement becomes more pronounced as the degree of system heterogeneity increases.>

The probability of a station/node failing to deliver packets before their deadlines, called the probability of dynamic failure, P/sub dyn/, and the in -bounded delivery time, which is defined as the time period between the arrival of a packet and its delivery with probability greater than 1- in , are important performance parameters for the communication subsystems of a distributed real-time system. The parameters are derived and are used to evaluate the token passing protocol, the token ring scheduling protocol, and the P/sub i/-persistent protocol and a priority-based variation thereof. The communication subsystem equipped with different contention protocols as embedded Markov chains is modeled. The probability distributions of the access delay are then derived, from which P/sub dyn/ and T/sub in / can be calculated. Using P/sub dyn/ and I/sub in / as indices, the performances of these contention protocols are evaluated and compared over a wide range of traffic.>