The highly directional nature of the millimeter wave (mmWave) beams causes several challenges in using that spectrum to meet the communication demands of immersive applications. The mmWave beams are especially susceptible to misalignments and blockages caused by user movements. As a result, mmWave channels are vulnerable to large quality fluctuations, which in turn, degrades the end-to-end performance of immersive applications. In this paper, we propose a reinforcement learning (RL) based application-layer plugin that works in conjunction with the QUIC protocol to combat the challenges of mmWave networks. The plug-in called Millimeter wave based Immersive QUIC Agent (MIQA) uses the RL model to help modulate the sending rate along with the congestion control scheme of QUIC. To evaluate the effectiveness of MIQA, we conduct experiments on a mmWave augmented immersive testbed. The evaluation results show that MIQA significantly improves the immersive experience by increasing the end-to-end throughput and by decreasing the end-to-end latency.

The highly directional nature of the millimeter wave (mmWave) beams pose several challenges in using that spectrum for meeting the communication needs of immersive applications. In particular, the mmWave beams are susceptible to misalignments and blockages caused by user movements. As a result, mmWave channels are vulnerable to large fluctuations in quality, which in turn, cause disproportionate degradation in end-to-end performance of Transmission Control Protocol (TCP) based applications. In this paper, we propose a reinforcement learning (RL) integrated transport-layer plugin, Millimeter wave based Immersive Agent (MIA), for immersive content delivery over the mmWave link. MIA uses the RL model to predict mmWave link bandwidth based on the real-time measurement. Then, MIA cooperates with TCP’s congestion control scheme to adapt the sending rate in accordance with the predictions of the mmWave bandwidth. To evaluate the effectiveness of the proposed MIA, we conduct experiments using a mmWave augmented immersive testbed and network simulations. The evaluation results show that MIA improves end-to-end immersive performance significantly on both throughput and latency.

The human genome is the ultimate identifier of an individual even though most of it is identical across human beings. Biological differences between two individuals are encoded in a set of base pair variations called Single Nucleotide Polymorphisms (SNPs), which may be indicative of an individual's personal information such as skin color and susceptibility to diseases. The large-scale nature of human genome necessitates outsourcing of genomic computations to public clouds. However, this raises some serious privacy concerns. The fact that the human reference template is public poses additional challenges. In this paper, we propose a two-cloud private read alignment algorithm using the Burrows-Wheeler Transform and the FM-Index. Our algorithm runs in the same order of complexity as the core FM-Index alignment algorithm without privacy. Our proposed scheme is able to achieve accuracy comparable to modern alignment algorithms such as Bowtie with complete privacy.

Millimeter wave (mmWave) access networks have the potential to meet the high-throughput and low-latency needs of immersive applications. However, due to the highly directional nature of the mmWave beams and their susceptibility to beam misalignment and blockage resulting from user movements and rotations, the associated mmWave links are vulnerable to large channel fluctuations. These fluctuations result in disproportionately adverse effects on performance of transport layer protocols such as Transmission Control Protocol (TCP). To overcome this challenge, we propose a network layer solution, COded Taking And Giving (COTAG) scheme to sustain low-latency and high-throughput end-to-end TCP performance in dually connected networks. In particular, COTAG creates network encoded packets at the network gateway and each access point (AP) aiming to adaptively take the spare bandwidth on each link for transmission. Further, if one link bandwidth drops due to user movements, COTAG actively abandons the transmission opportunity by conditionally dropping packets. Consequently, COTAG actively adapts to link quality changes in mmWave access network and enhances the TCP performance without jeopardizing the latency of immersive content delivery. To evaluate the effectiveness of the proposed COTAG, we conduct experiments using off-the-shelf APs and network simulations. The evaluation results show that COTAG improves end-to-end TCP performance significantly on both throughput and latency.

We present MilliCam, a system that captures the shape of small metallic objects, such as a gun, through obstructions, like clothing. MilliCam builds on the millimeter-wave (mmWave) imaging systems, which are widely used today in airport security checkpoints. Existing systems achieve high-resolution using a Synthetic Aperture Radar (SAR) principle, but require bulky motion controllers to position the mmWave device precisely. In contrast, MilliCam emulates the SAR principle by pure hand-swiping. However, alias-free, high-resolution imaging requires a linear, error-free hand-swiping motion. Furthermore, image focusing on an object of interest requires steering perfectly-shaped beam over the target-scene; but it is unavailable in off-the-shelf devices. We design a set of algorithms to enable high-quality handheld imaging: compensating for the errors in hand-swipe motion; and focusing the target-scene digitally without beam-steer. We have prototyped MilliCam on a 60 GHz testbed. Our experiments demonstrate that MilliCam can effectively combat motion errors and focus on the object in target-scene.

The design and implementation of an Internet of Things (IoT) based cyber physical framework in the context of Industry 4.0 is discussed for the field of micro devices assembly. Such frameworks hold the potential to facilitate rapid and agile collaborations among distributed engineering partners. This paper outlines the key cyber and physical components which collaborate using cloud-based principles and emerging next generation global environment for network innovation Internet technologies. An information centric systems engineering approach is proposed to help design the cyber physical interactions, which provide a foundation for implementing this cyber physical framework. The cyber modules are capable of assembly planning, path planning, virtual reality-based assembly simulation, and physical command generation. The physical assembly activities are accomplished using micro assembly work cells. An IoT-based cyber physical test bed has been created to test and validate the design and implementation aspects of the proposed framework.

Ordering is a widely used operation in distributed settings. However certain distributed settings like an on-line auction, place unique requirements on the protocol design. Firstly, all entities participate in the ordering with a communication channel(s) only with a coordinator(s), completely oblivious to other participants. This lack of intra-party communication channels makes traditional secure multi-party computations unsuitable for this scenario. Secondly, the security and functionality of the protocol should not depend on a single piece of secret information such as a secret symmetric key, ( as in the case of order-preserving encryption, OPE ). It is so because now every participating entity has to be communicated the secret key in order for them to encrypt their private data. However this means that even if just one of the entities is corrupt, the security of all the honest entities is compromised. These restrictions render both SMPC and OPE ill-suited for the above distributed setting. In this paper we propose a public order-preserving cipher generation scheme (POPC) that addresses the aforementioned challenges. POPC encodes a transform of the plaintext using a public order-preserving probabilistic encoding and generates the cipher in a two round interactive protocol. In POPC neither the correctness nor the security of the scheme depends on the possession of a single secret key. Moreover POPC needs no intra-party communication for its execution. We show POPC achieves the ideal security guarantee for any total order-preserving scheme, which is to reveal no information about the plaintexts beside the order, with a ciphertext space that is polynomial in size of the plaintext.

The focus of this article is on the adoption of immersive and haptic simulators for training of medical residents in a surgical process called Less Invasive Stabilization System (LISS) plating surgery . LISS surgery is an orthopedic surgical procedure to treat fractures of the femur bone. Development of such simulators is a complex task which involves multiple systems, technologies, and human experts. Emerging Next Generation Internet technologies were used to develop the standalone on-line haptic-based simulator accessible to the students 24/7. A standalone immersive surgical simulator was also developed using HTC Vive. Expert surgeons played an important role in developing the simulator system; use cases of the target surgical processes were built using a modeling language called the engineering Enterprise Modeling Language (eEML) . A detailed study presenting the comparison between the haptic-based simulator and the immersive simulator has been also presented. The outcomes of this study underscore the potential of using such simulators in surgical training.

System-on-Chip is a promising model for design of complex integrated circuits. In this model, designers may easily incorporate licensed and/or purchased Intellectual Property (IP) modules from other vendors to significantly reduce the design cycle time. However, the need to fulfill the legal obligations in the associated license or purchase contracts usually imposes considerable burden on the design process. The burden is often in the form of design access constraints that have to be imposed on SoC design team and/or in the form of additional costs needed to acquire a less constraining contract. To alleviate these problems, this paper proposes a encryption approach that assures confidentiality of the gate-level circuit information for the module designer while allowing the SoC designers an ability to perform gate-level digital simulations with gate-level delays. Empirical evaluation on benchmark circuits shows that, in addition to not being able to identify the gate types, an attacker cannot decrypt the delays associated with most of the gates in the circuit.

The 60 GHz wireless technology holds great potential for multi-Gbps communications and high-precision radio sensing. But the lack of an accessible experimental platform has been impeding its progress. In this paper, we overcome the barrier with OpenMili, a reconfigurable 60 GHz radio architecture. OpenMili builds from off-the-shelf FPGA processor, data converters and 60 GHz RF front-end. It employs customized clocking, channelization and interfacing modules, to achieve Gsps sampling bandwidth, Gbps wireless bit-rate, and Gsps sample streaming from/to a PC host. It also incorporates the first programmable, electronically steerable 60 GHz phased-array antenna. OpenMili adopts programming models that ease development, through automatic parallelization inside signal processing blocks, and modular, rate-insensitive interfaces across blocks. It provides common reference designs to bootstrap the development of new network protocols and sensing applications. We verify the effectiveness of OpenMili through benchmark communication/sensing experiments, and showcase its usage by prototyping a pairwise phased-array localization scheme, and a learning-assisted real-time beam adaptation protocol.

The 60 GHz wireless technology holds great potential for multi-Gbps communications and high-precision radio sensing. But the lack of an accessible experimental platform has been impeding its progress. We propose to overcome the barrier with OpenMili, a reconfigurable 60 GHz radio architecture. OpenMili builds from off-the-shelf FPGA processor, data converters and 60 GHz RF front-end. It employs customized clocking, channelization and interfacing modules, to achieve Gsps sampling bandwidth, Gbps wireless bit-rate, and Gsps sample streaming from/to a PC host. It also incorporates the first programmable, electronically steerable 60 GHz phased-array antenna. OpenMili adopts programming models that ease development, through automatic parallelization inside signal processing blocks, and modular, rate-insensitive interfaces across blocks. In this demo, we will showcase OpenMili's hardware modules, and demonstrate example communication and sensing applications based on it.

With the growing need to address the thermal issues in modern processing platforms, various performance throttling schemes have been proposed in literature (DVFS, clock gating, and so on) to manage temperature. In real-time systems, such methods are often unacceptable, as they can result in potentially catastrophic deadline misses. As a result, real-time scheduling research has recently focused on developing algorithms that meet the compute deadline while satisfying power and thermal constraints. Basic bounds that can determine if a set of tasks can be scheduled or not were established in the 1970s based on computation utilization. Similar results for thermal bounds have not been forthcoming. In this article, we address the problem of thermal constraint schedulability of tasks and derive necessary and sufficient conditions for thermal feasibility of periodic tasksets on a unicore system. We prove that a GPS-inspired fluid scheduling scheme is thermally optimal when context switch/preemption overhead is ignored. Extension of sufficient conditions to a nonfluid model is still an open problem. We also extend some of the results to a multicore processing environment. We demonstrate the efficacy of our results through extensive simulations. We also evaluate the proposed concepts on a hardware testbed.

60 GHz technology holds tremendous potential to upgrade wireless link throughput to Gbps level. To overcome inherent vulnerability to attenuation, 60 GHz radios communicate by forming highly-directional electronically-steerable beams. Standards like IEEE 802.11ad have tailored MAC/PHY protocols to such flexible-beam 60 GHz networks. However, lack of a reconfigurable platform has thwarted a realistic proof-of-concept evaluation. In this paper, we conduct an in-depth measurement of indoor 60 GHz networks using a first-of-its-kind software-radio platform. Our measurement focuses on the link-level behavior with three major perspectives: (i) coverage and bit-rate of a single link, and implications for 60 GHz MIMO; (ii) impact of beam-steering on network performance, particularly under human blockage and device mobility; (iii) spatial reuse between flexible beams. Our study dispels some common myths, and reveals key challenges in maintaining robust flexible-beam connection. We propose new principles that can tackle such challenges based on unique properties of 60 GHz channel and cognitive capability of 60 GHz links.

Next generation wireless networks (WMNs) are designed to provide better performance than other existing personal, local, and metropolitan wireless networks, such as Wireless Local Area Networks and WiFi. In WMNs, each link has different amount of available bandwidth, and the bandwidth fluctuates dynamically based on the wireless environment. When the available bandwidth fluctuates, Transmission Control Protocol (TCP) flows experience packet losses, packet re-ordering, and timeouts, resulting in low end-to-end throughput. To alleviate the problem of low TCP throughput, we propose a Spare-bandwidth Rate-adaptive Network Coding (SRNC) scheme. In SRNC scheme, each gateway node forwards packets after network coding. Each intermediate node also adaptively uses network coding before forwarding the packets to the outgoing links. Each mesh access node decodes the network coded packets before forwarding them to the destinations. The key feature of SRNC is that each node adapts its network coding rate based on the available bandwidth on the outgoing links, such that the access nodes can decode the packets with higher probability without significantly affecting the cross-traffic. Effectiveness of the proposed scheme is evaluated using simulation. The simulation results show that the proposed scheme uses the available bandwidth on each link efficiently and it significantly improves end-to-end throughput of TCP flows.

With growing need to address the thermal issues in modern processing platforms various performance throttling schemes have been proposed in literature (DVFS, clock gating etcetera). In real-time systems such methods are often unacceptable as they can result into potentially catastrophic deadline misses. As a result real-time scheduling research has been focused in developing algorithms which meet the compute deadline while satisfying power and thermal constraints. Basic bounds that can determine if a set of tasks can be scheduled or not were established in the 70's based on computation utilization of processing power and no new results have been forthcoming that deal with thermal effect based bounds. In this paper we address the problem of thermal constraint schedulability of tasks and derive necessary and sufficient conditions for thermal feasibility of periodic task sets for a unicore system. We then extend some of these results to multi-coreprocessing environment. We demonstrate the efficacy of our results through extensive simulations.

This paper presents a recognition scheme for fine-grain gestures. The scheme leverages directional antenna and short-range wireless propagation properties to recognize a vocabulary of action-oriented gestures from the American Sign Language. Since the scheme only relies on commonly available wireless features such as Received Signal Strength (RSS), signal phase differences, and frequency subband selection, it is readily deployable on commercial-off-the-shelf IEEE 802.11 devices. We have implemented the proposed scheme and evaluated it in two potential application scenarios: gesture-based electronic activation from wheelchair and gesture-based control of car infotainment system. The results show that the proposed scheme can correctly identify and classify up to 25 fine-grain gestures with an average accuracy of 92% for the first application scenario and 84% for the second scenario.

This paper introduces GENI Cinema (GC), a system that provides a scalable live video streaming service based on dynamic traffic steering with software defined networking (SDN) and demand driven instantiation of video relay servers in NSF GENI's distributed cloud environments. While the service can be used to relay a multitude of video content, its initial objective is to support live video streaming of educational content such as lectures and seminars among university campuses. Users on any campus would bootstrap video upload or download via a public Web portal and, for scalability, have the video delivered seamlessly across the network over one or multiple paths selected and dynamically controlled by GC. The architecture aims to provide a framework for addressing several well-known limitations of video streaming in today's Internet, where little control is available for controlling forwarding paths of on demand live video streams. GC utilizes GENI's distributed cloud servers to host on-demand video servers/relays and its Open Flow SDN to achieve seamless video upload/download and optimization of forwarding paths in the network core. This paper presents the architecture and an early prototype of the basic GC framework, together with some initial performance measurement results.

Developing region road traffic has a unique characteristic of high heterogeneity in vehicle types. In this paper, we describe VividhaVahana, a smartphone sensor based system to categorize road vehicles into four predominant categories: two-wheeler bikes, three-wheeler auto-rickshaws, four-wheeler car

This paper discusses an innovative approach to teach engineering concepts using Virtual Reality based Learning Environments (VLEs). New learning modules have been created using Virtual Reality technology and introduced in interdisciplinary senior level and graduate level courses targeting mechanical, industrial and electrical engineering students. These Virtual Reality based learning environments have been used to teach micro systems related topics as part of overall efforts to enhance the learning experiences of students. The learning outcomes including student performance are discussed. The process undertaken to design and develop these VLEs are elaborated along with the technologies used to develop such environments. A brief discussion of next generation Internet technologies which hold the potential to impact engineering and K-12 education is also provided.

In this paper, we propose a strategy for individual users to purchase frequency spectrum in cognitive radio based wireless networks. From the user's perspective, the goal is to reduce the cost of acquiring the spectrum needed to meet the quality of service needs of their real-time streaming applications. The key aspect of our proposed strategy is that the users can purchase spectrum for use in future time instances based on stochastic predictions of their locations and the prices set by competing wireless service providers. Another important aspect of the proposed strategy is that the tuning of many design parameters is not required as the tuning is often needed in conventional schemes. To evaluate our proposed scheme, we model a user utility function based on the cost of spectrum purchase and its impact on the quality of service. Simulation results show that the proposed strategy performs better than baseline schemes in terms of user utility.

In this paper we introduce a novel characterization of real-time tasks based on their temperature impact. This characterization is used to analyze the schedulability of periodic real-time tasks in thermally constrained systems. The proposed characterization is important because thermal constraints are becoming increasingly vital due to rapid and increasing rise in power densities of modern architectures. As part of this work, we introduce the concept of “Accumulated Thermal Impact” (ATI), which represents cumulative temperature increase due to execution of a given task. The concept of ATI is then used to determine thermal utilization of a periodic task set, which is somewhat analogous to traditional computation utilization, and perform schedulability analysis. We also propose a speed scaling scheme for minimizing thermal utilization/system temperature. Our results show that thermal utilization of a periodic task set is strongly correlated to its thermal feasibility. The proposed speed scaling scheme is also shown to perform significantly better than current schemes in terms of thermal utilization/temperature minimization.

Recent research has shown that some defects are detect resilient under normal or high temperature, therefore tests for those defects must be applied under lower temperature. On the other hand, some tests need to be applied under high temperature to improve the detection sensitivity. Thus temperature dependent testing which applies tests at different temperature ranges is needed. This paper discusses and gives a formulation of the temperature dependent test scheduling problem. In the proposed test scheduling scheme, each test is associated with a lower temperature bound and an upper temperature bound to define the temperature range within which the test must be applied. A list schedule based test scheduling algorithm is proposed to find the earliest starting time of each test. Cooling period is inserted when the core temperature is too high and heating sequence is applied when the core temperature is below the required specified temperature for the core. Simulation studies are performed for ITC'02 SoC benchmarks and test scheduling results are shown.

Effectively scheduling tasks on heterogeneous resources is critical to maximizing the overall benefit of those resources in system-on-a-chip architectures. In this paper we focus on scheduling soft a periodic tasks alongside periodic tasks with hard deadline constraints on heterogeneous real-time systems. We introduce a method to improve a periodic task responsiveness without breaking periodic task deadline guarantees, by first scheduling periodic tasks offline, then dynamically scheduling a periodic tasks in the remaining resource slack time. Experimental results indicate that the quality of a periodic task scheduling depends highly on the slack distribution within and across resources after periodic task scheduling, and on the flexibility of the a periodic task scheduler to rearrange these compute slacks to accommodate incoming a periodic tasks.

Traditional interdomain routing algorithms such as Border Gateway Protocol (BGP) rely on bilateral peering agreements between service providers to support end-to-end connectivity in the Internet. Network end users have very little control in the selection of these routes. Instead, network users are given a route to their destination with little or no assurances on its availability or performance. This traditional approach is not likely to work well for many rapidly growing streaming and gaming applications because their performance benefits significantly from better-than-best-effort connectivity. One possible approach for supporting such connectivity is to rely on a market-based mechanism through which network end users can shop and purchase interdomain routes of their choice. This paper envisions such a market in the near future. The paper then proposes a pricing strategy for connectivity service providers, called PriceMyRoute. The strategy allows multiple service providers to effectively compete with each other in order to offer the end-to-end connections requested by network users. The approach is likely to succeed because: (i) it offers monetary compensation to service providers for providing the routing flexibility to network users, and (ii) the improved performance is an incentive for network users to purchase better-than-best-effort end-to-end connectivity. The paper compares the effectiveness of the proposed strategy with that of RouteBazaar, a recent related scheme from literature. The comparison shows that both service providers and network users are likely to be more satisfied using the proposed strategy as compared to RouteBazaar.

Due to the growing importance of coastline surveillance and protection, underwater communication is playing an increasingly important role in military networks. As compared to terrestrial networks, large propagation delays and low data rates are fundamental characteristics of underwater communication. Furthermore, due to some key differences in the factors causing fluctuations in the quality of the underwater channels, the corresponding communication links experience more prolonged data rate changes as compared to those in terrestrial networks. Large propagation delays and prolonged link data rate deteriorations severely degrade the end-to-end performance of Transmission Control Protocol (TCP) based applications. Since military applications often require the reliable data delivery provided by TCP, it is important to devise solutions to alleviate this problem. In this paper, we propose a new routing scheme called Linear Coded Digraph Routing (LCDR) to enhance the end-to-end throughput of TCP based packet flows in underwater mesh networks. LCDR is a fully distributed scheme designed to locally respond to changes in the link data rates. In LCDR, each ingress node forwards packets after network coding. Each intermediate node adaptively uses network coding before forwarding the packets to the outgoing links. Each terrestrial gateway decodes the network coded packets before forwarding them to terrestrial networks. Each node adapts its packet forwarding rate based on the available bandwidth on the outgoing links, such that the terrestrial gateway can successfully receive packets with higher probability without significantly affecting cross-traffic. The effectiveness of the proposed scheme is evaluated using simulation. The simulation results show that the proposed scheme uses the spare bandwidth on each link efficiently and it significantly improves end-to-end throughput of TCP flows.

Conventional power constrained test scheduling methods do not guarantee a thermal-safe solution. In this paper, we propose a test scheduling algorithm that satisfies the resource, power, and thermal constraints. First, in contrast to existing schemes, the proposed algorithm exploits superposition principle to perform fast and accurate thermal simulation, which, in turn, allows the algorithm to search for solutions which introduce cooling periods between tests to reduce the overall test length. Second, we propose a test partition-based method to further improve the performance of the test scheduling. We apply our test scheduling algorithm to ITC'02 SoC benchmarks and the results show considerable improvement in the total test length over existing methods.

This paper presents and analyzes novel hardware designs for high-speed network coding. Our designs provide efficient methods to perform Galois field (GF) dot products and matrix inversions, which are important operations in network coding. Encoder designs that perform GF dot products and vary with respect to the number of messages combined, Galois field size, and input message size are implemented and analyzed to evaluate design tradeoffs. We investigate single cycle, multicycle, and pipelined designs with and without feedback mechanisms for encoding multiple sets of messages. The decoder is implemented as a multi-cycle design and performs GF matrix inversion followed by multiple GF dot products. Our designs are synthesized with a 65nm standard cell library and compared in terms of area, critical path delay, and throughput. Designs combining four messages achieve throughputs of more than 30 Gbps. Our designs can scale to achieve much higher throughput through the use of additional hardware.

Disruption Tolerant Networks (DTNs) are characterized by frequent network partitioning. This causes network connectivity to be opportunistic. In recent years, many collaborative applications have been envisioned for DTNs. These applications rely on the availability of reliable group communication protocols. To address this challenge in DTNs, we propose a scalable multicasting scheme that deterministically guarantees message delivery to all receivers in the group. Also, our scheme makes controlled use of non-multicast nodes to reduce latency of message delivery. Our work introduces a new measure called termination delay, which is the delay incurred in assuring that the receivers have obtained a copy of the message. Simulation results show that the proposed scheme has much smaller delivery latency and termination delay than other schemes in literature.

Publish-Subscribe models proposed for Disruption Tolerant Networks (DTNs) assume cooperation among all nodes in the network. Although, this is a valid assumption for some networks, recent applications envisioned for DTNs involve user participation of selfish nodes that form the network. In such scenarios, users may not participate in forwarding subscriptions or the message itself if they are not interested in the content. To alleviate the selfish behavior of such nodes we propose to use incentive based data collaboration schemes. Our paper examines distributed incentive based schemes that encourage participation of selfish nodes in forwarding of messages from publishers to subscribers. We provide simulation results that show the benefit of intermediate node participation. We also demonstrate our schemes through a prototype implementation of the publish-subscribe framework in a DTN environment.

Embedded systems increasingly include heterogeneous compute resources. Yet the vast majority of real-time scheduling methods are designed for single-resource or homogeneous multi-resource systems. Heterogeneity complicates scheduling; task execution time is resource-dependent. Furthermore, the best resource for one task may not necessarily be the best resource for all tasks, so one resource may not be universally more valuable than another. This paper presents new algorithms designed specifically for heterogeneous real-time scheduling. We evaluate the algorithms' deadline miss rates for heterogeneous task sets that represent a variety of execution scenarios, and show that two of our algorithms have lower deadline miss rates than the Earliest Deadline First or Least Laxity First approaches. We also discuss how task set and system characteristics affect the schedulers' abilities to achieve a quality schedule.

Barrier coverage indicates the capability of a deployed wireless sensor network to detect intruders crossing the sensing field, and it has been widely studied in recent years. Most of the existing works are asymptotic and focusing on the critical conditions (sensor density, sensing radius, etc.) to achieve barrier coverage. However these results are not very useful in practice since the sensing field generally has finite region. Also, the critical conditions may not be adequate for making deployment decisions if sensor cost and deployment cost are taken into consideration. In this paper we analyze the probability of achieving connected barrier coverage on a finite narrow band while sensors with given sensing/communicating radius are randomly deployed with given density. Moreover, we apply our analytical result and propose a cost efficient deployment strategy that uses minimal number of sensors to achieve connected barrier coverage within at most k iterations. Both the correctness of the analysis and the performance of the proposed deployment strategy are evaluated via simulations.

Two important measures of performance for the surveillance applications of the mobile sensor networks are detection latency and system lifetime. Previous work on modeling detection delay has assumed that sensor measurements are delivered to the fusion center with zero delay. Such approaches can require excessive energy, resulting into reduced lifetime. This article argues that a trade-off between detection latency and system lifetime can be made by employing an energy aware transmission scheme. The article formulates the trade-off as an optimization problem, and presents an analytic method to model both detection latency and system lifetime. The model is substantiated by using simulation.

For core-based system-on-chip (SoC) testing, conventional power-constrained test scheduling methods do not guarantee a thermal-safe solution. Also, most of the test scheduling schemes make poor assumptions about power consumption. In deep submicron era, leakage power and wake-up power consumption can not be neglected. In this paper, we propose a partition based thermal-aware test scheduling algorithm with more realistic assumptions of recent SoCs. In our test scheduling algorithm, each test is partitioned and the earliest starting time of each partition is searched. To reduce the execution time of thermal simulation, we also exploit superposition principle to compute the power and thermal profile rapidly and accurately. We apply our test scheduling algorithm to ITC'02 SoC benchmarks and the results show improvements in the total test time over scheduling schemes without partitioning.

In this paper, we address the problem of supporting receivers that require different sessions of a multicast application based on their desired rates. We present a distributed bandwidth partitioning scheme to share the bandwidths on the links in such a way that data rate requirements of each receiver in the multicast is met. The salient features of our scheme are: (i) each receiver can simultaneously request up to their individual maximum flow rates; (ii) each node uses only local link bandwidth and flow information to partition the outgoing link bandwidth; (iii) if link bandwidths change due to cross traffic, each node can quickly adapt and repartition link bandwidths to deliver data rates requested by receivers. We show through simulations and experiments over several overlay networks at the University of Wisconsin that all receiver get their requested rates. We also integrate our scheme into a multimedia streaming application to demonstrate a usage case scenario and further evaluate its effectiveness.

We propose a test scheduling algorithm that ensures the resource compatibility and satisfies both power and thermal constraints. The proposed algorithm can start a test at an arbitrary time and it has the capability of delaying a test to let a core cool down to find a valid schedule even when traditional scheduling schemes cannot find a solution. To reduce the execution time of thermal simulation, we exploit superposition principle to compute the thermal profile rapidly and accurately. We apply our scheduling algorithm to ITC'02 SoC benchmarks and the results show a remarkable improvement in the total test length over other methods, while meeting the thermal and power constraints.

Calibrating nonlinear mobile sensors in-field is a challenging task due to the unavailability of controlled signal field and pre-calibrated sensor devices. In this paper, we propose a Density Guided blind Calibration (DGC) scheme for nonlinear mobile sensors by approximating the nonlinear calibration functions using piecewise linear functions. The DGC scheme exploits the fact that sensors moving in the same region collect similar fraction of true values in any given interval over time. The proposed scheme tackles the nonlinear calibration problem through an optimization formulation which is very easy to solve. The effectiveness of the proposed scheme is verified through simulations and an experiment with MICA2 light sensors.

Detection latency, which is defined as the time from the target arrival to the time of the first detection, is an important metric for the performance of sensor networks carrying out target detection, especially when the target is malicious or hostile. It characterizes the efficiency of detecting the presence of a target in a region of interest. Traditionally, stationary sensor networks are used to perform such sensing tasks. Consequently, nearly all research literature for the target detection problem has focused on stationary sensor networks. This paper addresses the problem of detecting the presence/absence of a target using a mobile sensor network. An analytic method is proposed to model the detection latency based on a collaborative sensing architecture. Detection latency for different node mobility models is presented. The accuracy of the analytic model is verified by simulations. This paper also compares the performance of mobile and stationary sensor networks. The comparison shows that if the target is present at the worst possible location in a given deployment, then detection latency of mobile sensor networks is considerably shorter as compared to that of stationary networks with the same number of nodes.

Disruption tolerant networks (DTNs) are characterized by opportunistic connectivity due to frequent network partitioning. Protocols used in wired and wireless networks have assumed the existence of end-to-end paths from a source to a destination, which is not true in DTNs applications. Our focus in this work is to propose a scheme that deterministically guarantees message delivery to all multicast receivers in DTNs making controlled use of non-multicast nodes to reduce message delivery latency. The paper also introduces a new measure called termination delay and simulation results show that our scheme has much smaller termination delay than schemes in literature. Second, we extend our reliability scheme to provide anonymity of multicast receivers in the group. We show through simulations that even in the presence of malicious nodes the performance degradation of message delivery latency and termination latency is not any worse than schemes currently proposed in literature.

Delay Tolerant Networks are increasingly being envisioned for a wide range of applications. Many of these applications need support for quality of service (QoS) differentiation from the network. This paper proposes a method for providing probabilistic delay assurances in DTNs. In particular, the paper presents a method called Delay- Differentiated Gossiping to assure a certain probability of meeting the packets' delay requirements while using as little network resources as possible. The idea is to adapt a set of forwarding probabilities and time-to-live parameters to control the usage of network resources based on how the delay requirements are being met. Empirical results evaluating the effectiveness of the proposed method are also included. The results show that there are simple ways of assuring the delay requirements while making effective use of the network resources.

In-field calibration of sensor devices is known to be a challenging problem because there is often no access to a controlled signal field and/or a pre-calibrated device to measure the existing signal field. In this paper, we describe a blind calibration scheme that is tailored for sensor networks with mobile nodes. The scheme proposed in this paper exploits the fact that sensor devices are moving in the same region and hence the signal statistics they observe over time are almost the same. Analysis and simulation results are included to demonstrate the effectiveness of the proposed scheme.

In-field calibration of sensor devices is known to be a challenging problem because there is often no access to a controlled signal field and/or a pre-calibrated device to provide the ground truth. Nonlinear characteristics of sensor devices make the calibration problem even harder. In this paper, we describe two blind calibration schemes for nonlinear mobile sensor nodes: nullspace based calibration (NBC) and moments based calibration (MBC). Simulation results are included to demonstrate the effectiveness of the proposed schemes. MBC scheme is also used to calibrate light sensors on MICA2 motes in a light field generated by a light bulb. Results show that significant error reduction can be achieved when nonlinearity is considered.

A distributed scheduling approach to multi-user beamforming at a base-station (BS) is proposed. The scheme assumes the BS is equipped with multiple antennas and uses zero-forcing beamforming to schedule multiple users on the same time-frequency uplink/downlink channels. The optimal user set that the BS can schedule is the one that maximizes the sum-rate for the communication channel. The computational complexity of finding the optimal user set becomes intractable as the number of users exceeds 20-30. Sub-optimal schemes for maximizing the sum-rate generally require large control overhead. We propose an effective sum-rate performance metric that accounts for the control overhead required by the scheduling method. We also propose a user scheduling method that has both low complexity and low overhead. The complexity and overhead are reduced by adding one user at a time and distributing the computation of the scheduling problem across the users. Each user calculates the sum-rate that would result if they were added to the existing user set using their own channel and knowledge of the channels of existing users that is broadcast by the BS. The user with greatest sum-rate increase is scheduled. We use simulations to show that this approach can achieve significantly higher effective sum rates than previously proposed sub-optimal schemes. We also derive an approximate expression for the expected sum-rate with our distributed scheduling method and demonstrate its accuracy with simulations.

We develop a level set estimation algorithm for a novel low cost sensor network architecture, where sensors are mounted on agents moving without an explicit objective of sensing. A level set in a planar scalar field is the set of points with field values greater than or equal to a specified threshold. The distributed algorithm uses opportunistic information exchange to estimate level set boundaries locally at nodes selected using leader election. Such estimates are aggregated at the base station. Effectiveness of the proposed scheme is evaluated using simulations with data from both synthetic and measured fields. Random way point mobility model is used for node motion and accuracy and trade off of coverage with communication costs is studied.

Recent advances in antenna technology made it possible to build wireless devices with more than one antenna at affordable costs. Because multiple antennas offer wireless networks a potential capacity increase, they are expected to be a key part of next-generation wireless networks to support the rapidly emerging multimedia applications characterized by their high and diverse QoS requirements. This paper developed methods that exploit the benefits of multiple antennas to enable multi-hop wireless networks with flow-level QoS capabilities. The authors first propose a cross-layer table-driven statistical approach that allows each node to determine the amount of spatial reuse and/or multiplexing, offered by the multiple antennas that are available to it. The authors then use the developed statistical approach to derive sufficient conditions under which flow rates are guaranteed to be feasible. The derived conditions are multi-layer aware in the sense that they account for cross-layer effects between the PHY and the MAC layers to support QoS at higher layers. The authors evaluate and compare the derived sufficient conditions via extensive simulations. The authors show that the conditions result in high flow acceptance rates when used in multi-hop wireless networking problems such as QoS routing and multicommodity flow problems. The authors also demonstrate the importance and the effect of considering cross-layer couplings into the development of flow acceptance methods.

Unlike single omnidirectional antennas, multiple antennas offer wireless ad-hoc networks potential increases in their achievable throughput and capacity. Due to recent advances in antenna technology, it is now affordable to build wireless devices with more than one antenna. As a result, multiple antennas are expected to be an essential part of next-generation wireless networks to support the rapidly emerging multimedia applications characterized by their high and diverse QoS needs. This paper develops an admission control framework that exploits the benefits of multiple antennas to better support applications with QoS requirements in wireless ad-hoc networks. The developed theory provides wireless ad-hoc networks with flow-level admission control capabilities while accounting for cross-layer effects between the PHY and the MAC layers. Based on the developed theory, we propose a mechanism that multiple antenna equipped nodes can use to control flows' admissibility into the network. Through simulation studies, we show that the proposed mechanism results in high flow acceptance rates and high network throughput utilization.

Sensor networks have been envisioned to enhance the ability of human beings in observing the environment and understanding the world. A potential application of a sensor network is to detect the presence or absence of a target in a region of interest. Many heuristics have been proposed in literature for placing sensors to achieve better coverage in the monitored region. However, none of them guarantee an optimal sensor deployment especially when there are obstacles in the region. Unlike the prior work, this paper focuses on the problem of determining the optimal sensor distribution in a region with or without obstacles. The detection performance is characterized using a metric called ldquoexposurerdquo, which is defined as the least probability of detecting a target over all possible target locations subject to a fixed false alarm probability. A linear programming based approach is proposed to find the optimal sensor distribution by maximizing the exposure in a given region with or without obstacles. The optimal sensor distribution can also be used as weights of sensor measurements taken at different locations for decision-making.

An envisioned usage of sensor networks is in surveillance systems for detecting a target or monitoring a physical phenomenon in a region. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. In many applications, if the monitored region is relatively large compared to the sensing range of a node, a large number of nodes are required in the region to achieve high coverage. Using mobile nodes in such situations can be an attractive alternative. Mobility of sensor nodes has been studied in sensor networks for many purposes such as power saving, data collection, and packet delivery. However, nearly all research literature for the target detection problem has focused on stationary sensor networks. This paper investigates the problem of detecting the presence/absence of a target using mobile sensor networks. It presents an analytic method to evaluate the detection latency based on a collaborative sensing approach using nodes with uncoordinated mobility. We verify the analytic model through simulations. The analytic method provides a simple way of analyzing the tradeoff between number of nodes and detection latency in a mobile sensor network. The analysis is also used to compare the performance of mobile and stationary sensor networks with respect to these measures. Results show that if the target is present at the worst possible location in a given deployment, then detection latency of mobile sensor networks is considerably less as compared to that of stationary networks with the same number of nodes.

This paper investigates data-adaptive path planning schemes for wireless networks of mobile sensor platforms. We focus on applications of environmental monitoring, in which the goal is to reconstruct a spatial map of environmental factors of interest. Traditional sampling theory deals with data collection processes that are completely independent of the target map to be estimated, aside from possible a priori specifications reflective of assumed properties of the target. We refer to such processes as passive learning methods. Alternatively, one can envision sequential, adaptive data collection procedures that use information gleaned from previous observations to guide the process. We refer to such feedback-driven processes as active learning methods. Active learning is naturally suited to mobile path planning, in which previous samples are used to guide the motion of the mobiles for further sampling. This paper presents some of the most encouraging theoretical results to date that support the effectiveness of active over passive learning, and focuses on new results regarding the capabilities of active learning methods for mobile sensing. Tradeoffs between latency, path lengths, and accuracy are carefully assessed using our theory. Adaptive path planning methods are developed to guide mobiles in order to focus attention in interesting regions of the sensing domain, thus conducting spatial surveys much more rapidly while maintaining the accuracy of the estimated map. The theory and methods are illustrated in the application of water current mapping in a freshwater lake.

We examine the problem of determining boundaries occurring in natural phenomena using sensor networks. Sensor nodes remotely collect data about various points on the boundary. From this data, we estimate the boundary along with the confidence intervals using a regression relationship among sensor locations and the distances to the boundary. The confidence intervals are guaranteed to be narrower than a specified maximum width. Our distributed boundary estimation strategy uses a hierarchical structure of clusters of sensor nodes and requires 20-50% less messages as compared to a centralized scheme. The computed intervals show desired coverage of the true boundary points. Further, motivated by the practical need to estimate the boundary with a minimum number of sensors, we develop an adaptive approach for turning sensors on and off. The number of ON sensors in this scheme is only about 15% more than what a practical Oracle needs, to evaluate the boundary and confidence intervals around it. Our algorithms are also evaluated using data from real sensors on a testbed

Mobile sensor networks are being envisioned for certain applications like habitat monitoring and environmental sensing. For instance, mobile sensor nodes are attached to selected animals to gather data about their behavior. These data are uploaded to stationary units for detailed analysis over wireless ad-hoc networks. Since the mobile sensor nodes are likely to operate on batteries, reducing energy consumption for such data gathering is an important issue. This paper proposes a transmission scheme for power-adjustable radio to optimize transmit energy efficiency subject to given overflow and delay constraints. The energy efficiency is defined as the expected transmit energy to deliver one unit of data from sensor node to stationary unit. An analytical model is developed to estimate the unit energy, data throughput and delay for a sensor node in the single-hop case. Simulation results show that the model achieves very good accuracy. The proposed transmission scheme is then adapted to the multi-hop scenario. Simulations based on radio parameters from a sensor board demonstrate that high energy efficiency can be achieved by the transmission scheme in both single-hop and multi-hop cases

Efficient medium access control in wireless networks has been a challenging task. While the IEEE 802.11 standard coordinates contention effectively, it severely limits the number of concurrent communications. This results in reduced throughput and efficiency. Recent research has focused on employing multiple antennas to increase throughput in a multipath environment by enabling multiple streams between a transmit-receive pair. In this paper we show that exploiting multiuser diversity to enable concurrent communications has certain advantages over multiple streaming. We propose a medium access control (MAC) protocol that uses adaptive interference cancellation with multiple antennas to increase network throughput and to provide better fairness, while requiring minimal change to the widely-deployed 802.11 MAC structure

Two novel distributed particle filters with Gaussian mixer approximation are proposed to localize and track multiple moving targets in a wireless sensor network. The distributed particle filters run on a set of uncorrelated sensor cliques that are dynamically organized based on moving target trajectories. These two algorithms differ in how the distributive computing is performed. In the first algorithm, partial results are updated at each sensor clique sequentially based on partial results forwarded from a neighboring clique and local observations. In the second algorithm, all individual cliques compute partial estimates based only on local observations in parallel, and forward their estimates to a fusion center to obtain final output. In order to conserve bandwidth and power, the local sufficient statistics (belief) is approximated by a low dimensional Gaussian mixture model (GMM) before propagating among sensor cliques. We further prove that the posterior distribution estimated by distributed particle filter convergence almost surely to the posterior distribution estimated from a centralized Bayesian formula. Moreover, a data-adaptive application layer communication protocol is proposed to facilitate sensor self-organization and collaboration. Simulation results show that the proposed DPF with GMM approximation algorithms provide robust localization and tracking performance at much reduced communication overhead.

Sensor networks possess the inherent potential to detect the presence of a target in a monitored region. Although a stationary sensor network is often adequate to meet application requirements, it is not suited to many situations, for example, a huge number of nodes are required to monitor a large region. In such situations, mobile sensor networks can be used to resolve the communication and sensing coverage problems. This paper addresses the problem of detecting a target using mobile sensor networks. One of the fundamental issues in target detection problems is exposure, which measures how the region is covered by the sensor network. While traditional studies focus on stationary sensor networks, this paper formally defines and evaluates exposure in mobile sensor networks with the presence of obstacles and noise. To conform with practical situations, detection is conducted without presuming the target's activities and moving directions. As there is no fixed layout of node positions, a time expansion technique is developed to evaluate exposure. Since determining exposure can be computationally expensive, algorithms to calculate the upper and lower bounds on exposure are developed. Simulation results are also presented to illustrate the effectiveness of the algorithms

Multimedia applications over IEEE 802.11 wireless LANs (WLANs) such as wVoIP have recently attracted the focus of many researchers. Unlike best-effort applications, multimedia applications are delay- and/or bandwidth-sensitive. In order for these applications to achieve an acceptable QoS, the network must provide them with certain QoS guarantees. This paper proposes an admission control heuristic for applications with delay requirements in IEEE 802.11e EDCA WLANs. To develop the proposed heuristic, we first derive an analytical approximation of delays experienced by packets when delivered via IEEE 802.11e EDCA WLANs. We validate the heuristic through simulations of voice traffic

Quality-of-service (QoS) in wireless ad hoc networks is adversely affected by node mobility, changing network topologies, and uncontrolled medium contention. The paper addresses the challenges in concurrently providing a wide range of end-to-end throughput and delay assurances in such networks. The proposed solution is based on the neighborhood proportional delay differentiation (NPDD) service model. With NPDD, applications achieve their desired end-to-end QoS using dynamic class selection (DCS) algorithms. With simulations in various distinct mobile network scenarios, we demonstrate the significantly better QoS assurances achieved with the proposed mechanism as compared with best effort and strict priority approaches. With game theoretic concepts, we model DCS applications in an NPDD network as selfish players in a noncooperative game. For such games, we prove for single-hop and multihop NPDD networks the existence of an equilibrium, the feasibility of an equilibrium, and the guaranteed convergence to a feasible equilibrium when one exists.

Multi-hop hotspot networks consist typically of one or few wireless access nodes (ANs) and many self-organizing, self-coordinating, and battery-powered portable nodes (PNs). Nodes maintain cooperative connectivity among each other without any need for a wired infrastructure. On the one hand, because PNs are power-limited, efficient use of their available energy resources is crucial to their lifetimes. On the other hand, because higher rates of elastic flows provide higher QoS, it is desirable to maximize the throughput. Unfortunately, increasing lifetime and maximizing throughput are two conflicting objectives which cannot he optimized simultaneously. In this paper, we propose an extension of our earlier-presented scheme (B. Hamdaoui et al., IEEE Press Monograph on Sensor Network Op., 2004) to support elastic traffic routing in multi-hop hotspot networks. The proposed routing scheme strikes a balance between the need to keep the nodes operational with sufficient energy resources and the desire to allocate higher throughput to elastic flows. The proposed scheme also deals systematically with both objectives of maximizing the network lifetime and minimizing the total consumed energy.

A medium access control (MAC) protocol for ad hoc networks of nodes with antenna arrays is presented. The antenna array is used for transmit and receive beamforming with the purpose of increasing spatial reuse by directing nulls at active transmitters and receivers in the neighborhood. In contrast to previous work with directional antennas, our approach is applicable to flat fading multipath channels, such as in indoor or in other rich scattering environments. The MAC protocol is designed to support the control information exchange needed to direct nulls toward other users involved in existing communication sessions. Knowledge of the channel coefficients between a transmitter or receiver and its neighbors is used to design transmit or receive beamformer weights that implement the requisite nulling. Simulations are used to demonstrate the improvements in throughput and transmit powers that are obtained in this approach relative to the conventional IEEE 802.11 MAC protocol.

Multicast is an important communication mode in wireless ad hoc networks. Furthermore, an adaptive antenna array with multiple-input-multiple-output (MIMO) channel model is more suitable for wireless multipath environments. In this paper, we study energy efficient one hop multicast in such an environment. The problem is formulated as a non-linear programming problem and two heuristic algorithms are proposed to solve the problem.

Handoff is the process during which a mobile node (MN) needs to change its connectivity point to the wireless internetwork from one access node (AN) to another during an ongoing communication. If MNs are allowed to have two or more simultaneous connections to the internetwork through different ANs, then the handoff is said to be soft; otherwise, it is said to be hard. Traditionally, during forward-link soft handoff, multiple identical copies of each packet are simultaneously transmitted to the MN through the associated ANs. At the MN's physical-layer, the received signals are combined on a bit-by-bit basis resulting in improving the bit-error rate. However, this approach requires tight synchronization of the ANs involved in the soft handoff. In addition, as shown in the literature, the capacity often decreases due to the increase of the number of channels used by MNs during soft handoff. In this paper, we propose, analyze, simulate, and implement a soft handoff scheme called soft handoff over IP (SHIP) for forward-link that 1) overcomes the need for synchronization and 2) increases the capacity of the network. Through both analytic and simulation studies, we show that SHIP achieves significant performance improvements. We derive analytic expressions of the power-capacity relationship for two-dimensional (2-D) and one-dimensional (1-D) cell models. By comparing our scheme with the hard handoff, we empirically show that the capacity increases by about 30% and 20%, respectively, for the 2-D and 1-D cell models. Further, the simulation results show that SHIP saves up to 30% of the total power consumed by the ANs.

Collaboration in sensor networks must be fault-tolerant due to the harsh environmental conditions in which such networks can be deployed. We focus on finding algorithms for collaborative target detection that are efficient in terms of communication cost, precision, accuracy, and number of faulty sensors tolerable in the network. Two algorithms, namely, value fusion and decision fusion, are identified first. When comparing their performance and communication overhead, decision fusion is found to become superior to value fusion as the ratio of faulty sensors to fault free sensors increases. As robust data fusion requires agreement among nodes in the network, an analysis of fully distributed and hierarchical agreement is also presented. The impact of hierarchical agreement on communication cost and system failure probability is evaluated and a method for determining the number of tolerable faults is identified.

There is a growing interest in the use of wireless ad hoc sensor networks to monitor, detect, and track the movement of specified targets in a geographic region. A common concern in the deployment of such networks is whether or not a target can pass or intrude a sensor field without being detected. Recent papers in the literature have defined a measure called exposure to quantify the likelihood of a target passing through a sensor field without being detected. These papers differ in the definition of exposure. Also, the existing definitions of exposure are indicators of the likelihood of intrusion and not a direct measure of it. We directly work with probability of detection instead of its indicators. We also probabilistically account for the presence of noise in the sensor readings. In the presence of noise, there is a trade off between the probability of a target passing through a sensor field without detection and the false alarm probability (i.e., the probability of falsely detecting the presence of target). We analytically characterize this trade off and illustrate the trade off for example deployments. We also introduce a variant of the traversal problem called unauthorized monitoring. This problem is of interest if sensor fields are used to secure an asset. We analytically characterize the probability of detecting unauthorized monitoring. We also show a trade off between this probability and the corresponding false alarm probability in the presence of noise.

The packet-pair technique aims to estimate the capacity of a path (bottleneck bandwidth) from the dispersion of two equal-sized probing packets sent back to back. It has been also argued that the dispersion of longer packet bursts (packet trains) can estimate the available bandwidth of a path. This paper examines such packet-pair and packet-train dispersion techniques in depth. We first demonstrate that, in general, packet-pair bandwidth measurements follow a multimodal distribution and explain the causes of multiple local modes. The path capacity is a local mode, often different than the global mode of this distribution. We illustrate the effects of network load, cross-traffic packet-size variability, and probing packet size on the bandwidth distribution of packet pairs. We then switch to the dispersion of long packet trains. The mean of the packet-train dispersion distribution corresponds to a bandwidth metric that we refer to as average dispersion rate (ADR). We show that the ADR is a lower bound of the capacity and an upper bound of the available bandwidth of a path. Putting all of the pieces together, we present a capacity-estimation methodology that has been implemented in a tool called pathrate. We report on our experiences with pathrate after having measured hundreds of Internet paths over the last three years.

This paper describes schemes for forward and reverse links in a direct sequence code-division multiple-access-based cellular network. The primary objective is to meet the diverse quality-of-service (QoS) needs of mobile hosts (MHs), and the secondary objective is to maximize the system throughput. The QoS needs of the MHs are modeled using the notion of a service curve. Furthermore, a notion of deviation is introduced as a measure of meeting service curve. The scheme proposed in this paper jointly adapts the transmitted power and the number of spreading codes assigned to each MH for receiving/transmitting its data bits. The scheme imposes practical constraints including bounds on the transmitted power for a base station and MHs, a bound on the number of spreading codes that an MH can handle, and minimum signal-to-interference-plus-noise ratio at the receiver. The proposed solutions are evaluated using discrete event simulations. The simulation results characterize the performance of the proposed solutions for several instances of the practical constraints.

Wireless nodes within the same vicinity contend for accessing the shared medium. The contention constraints on sharing the medium depend on the medium access control (MAC) protocol. For example, in IEEE 802.11 MAC protocol-based networks, if node i is in communication with node j, then all nodes within the same transmission range of i or j cannot communicate. On the other hand, if nodes within each other's transmission range can use different frequencies (e.g., FDMA) or different codes (e.g., CDMA), then neighbor nodes can communicate simultaneously. Furthermore, if nodes are equipped with two radios (e.g., WINS sensor networks), then nodes not only can communicate concurrently but also can receive while they are transmitting. In this paper, we prove a sufficient condition under which a flow rate vector is feasible given the MAC protocol. We also prove that the sufficient condition is necessary for some MAC protocols such as those used by WINS sensor and Bluetooth [Marsan, M., 2002] networks. We give illustrative and real examples for which these conditions apply.

Emerging wireless local area network (WLAN) technologies support high data rates over relatively short distances. To achieve high data rate communication from larger distances, multihop wireless connections between mobile users and wireless Internet gateways may be necessary. In this paper, we address the challenges in providing a wide range of diverse delay assurances to end-to-end applications in a multihop WLAN. Due to node mobility and distributed medium access, multihop communication experiences substantial delay variations. The paper proposes a delay assurance mechanism based on consistent class-based service differentiation and end-to-end class selection. With simulations, the solution demonstrates remarkable enhancements in delay assurances as compared with the best effort service of IEEE 802.11 in both stationary and mobile scenarios.

In our prior work, we presented an algorithm called largest magnitude coefficient selection (LMCS) for realizing the signal-to-noise-ratio (SNR) scaling an already encoded video object to an alternate (lower) rate (higher) distortion level. We showed that LMCS retains semantically important image features and successfully avoids the common artifacts of blur and ringing noise. However, it suffers from a significant coding inefficiency problem. In this paper, we first identify the mechanisms, which lead to the problem, and consequently present a novel technique called pivoting in order to alleviate it. The comparison of the resulting algorithm, LMCS-pivot, against the conventional SNR scaling techniques demonstrates its effectiveness according to both objective and subjective performance measures.

The highly distributed infrastructure provided by sensor networks supports fundamentally new ways of designing surveillance systems. In this paper, we discuss sensor networks for target classification and tracking. Our formulation is anchored on location-aware data routing to conserve system resources, such as energy and bandwidth. Distributed classification algorithms exploit signals from multiple nodes in several modalities and rely on prior statistical information about target classes. Associating data to tracks becomes simpler in a distributed environment, at the cost of global consistency. It may be possible to filter clutter from the system by embedding higher level reasoning in the distributed system. Results and insights from a recent field test at 29 Palms Marine Training Center are provided to highlight challenges in sensor networks.

We propose a method to estimate the location of a mobile user. We assume that mobile users carry portable devices such as laptops or personal digital assistants equipped with off-the-shelf standard wireless interfaces. The infrastructure has a few fixed nodes whose locations are assumed to be known. The location estimates rely on neighborhood relationships gathered by each user through message exchanges over a wireless ad hoc network. We show that by incorporating non-neighbor constraints, one can substantially improve the accuracy of location estimation as compared to only utilizing neighbor relationships. We also compare our approach without the non-neighbor constraints with the results from a paper (Doherty, L. et al., Proc. INFOCOM, p.1655-63, 2001) based on the same model. Empirical evaluation of our algorithm for several numerical examples is also included.

In a direct sequence code division multiple access (DS-CDMA) based cellular network, meeting the diverse quality of service (QoS) needs of mobile hosts (MHs) is a challenge because of the fluctuations in the quality of the wireless channel. The QoS needs of the MHs application are modelled using a service curve. Furthermore, a notion of deviation is introduced as a measure of meeting the service curve. The paper describes a forward link scheme whose primary objective is to minimize system deviation from the service curve and the secondary objective is to maximize the system throughput. The solution includes constraints on the transmit power of the base station (BS), number of spreading codes and target signal-to-interference-plus-noise ratio (SINR) for the MHs.

The proportional differentiation model provides the network operator with the 'tuning knobs' for adjusting the per-hop quality-of-service (QoS) ratios between classes, independent of the class loads. This paper applies the proportional model in the differentiation of queueing delays, and investigates appropriate packet scheduling mechanisms. Starting from the proportional delay differentiation (PDD) model, we derive the average queueing delay in each class, show the dynamics of the class delays under the PDD constraints, and state the conditions in which the PDD model is feasible. The feasibility model of the model can be determined from the average delays that result with the strict priorities scheduler. We then focus on scheduling mechanisms that can implement the PDD model, when it is feasible to do so. The proportional average delay (PAD) scheduler meets the PDD constraints, when they are feasible, but it exhibits a pathological behavior in short timescales. The waiting time priority (WTP) scheduler, on the other hand, approximates the PDD model closely, even in the short timescales of a few packet departures, but only in heavy load conditions. PAD and WTP serve as motivation for the third scheduler, called hybrid proportional delay (HPD). HPD approximates the PDD model closely, when the model is feasible, independent of the class load distribution. Also, HPD provides predictable delay differentiation even in short timescales.

The relative differentiation architecture does not require per-flow state at the network core or edges, nor admission control, but it can only provide higher classes with better service than lower classes. A central premise in this context is that users with absolute QoS requirements should search dynamically for an appropriate class. We investigate this dynamic class selection (DCS) framework, and illustrate that, under certain conditions, DCS-capable users can meet absolute QoS requirements, even though the network only offers relative differentiation. For a single link model, we can examine whether it is feasible to satisfy all users, and when this is the case, compute the minimum acceptable class selection for each user. Users converge in a distributed manner to this minimum acceptable class, if the DCS equilibrium is unique. However, suboptimal DCS equilibria may also exist. Simulations of a delay-based DCS algorithm show the relation between class differentiation and DCS, and demonstrate how to control the trade-off between the performance and cost of a flow.

The packet pair technique estimates the capacity of a path (bottleneck bandwidth) from the dispersion (spacing) experienced by two back-to-back packets. We demonstrate that the dispersion of packet pairs in loaded paths follows a multimodal distribution, and discuss the queueing effects that cause the multiple modes. We show that the path capacity is often not the global mode, and so it cannot be estimated using standard statistical procedures. The effect of the size of the probing packets is also investigated, showing that the conventional wisdom of using maximum sized packet pairs is not optimal. We then study the dispersion of long packet trains. Increasing the length of the packet train reduces the measurement variance, but the estimates converge to a value, referred to as the asymptotic dispersion rate (ADR), that is lower than the capacity. We derive the effect of the cross traffic in the dispersion of long packet trains, showing that the ADR is not the available bandwidth in the path, as was assumed in previous work. Putting all the pieces together, we present a capacity estimation methodology that has been implemented in a tool called pathrate.

Most existing multicast protocols for wireless ad-hoc networks operate at the network layer and make no assumption about the underlying link and physical layer protocols. This results in inefficiency in the usage of bandwidth and power. In this paper, we assume a DS-CDMA based wireless ad-hoc network and propose two schemes, Centralized-Tree Distributed-Power (CTDP) and Distributed-Tree Distributed-Power (DTDP), tailored to the link and physical layer protocols. Both schemes seek to construct a multicast tree and determine the power levels at which the nodes should transmit to satisfy the SINR requirements of all receiving nodes with the least total transmit power. Empirical evaluation shows that CTDP is more efficient than DTDP in terms of consumed transmit power but at significantly higher computation cost. On the other hand, DTDP is fully distributed and thus may be better suited for mobile wireless ad-hoc networks.

Multi-threading and multiscaling are two fundamental microarchitecture approaches that are expected to stay on the existing performance gain curve. Both of these approaches assume that integrated circuits with over billion transistors will become available in the near future. Such large integrated circuits imply reduced design tolerances and hence increased failure probability. Conventional hardware redundancy techniques for desired reliability in computation may severely limit the performance of such high performance processors. Hence we need to study novel methods to exploit the inherent redundancy of the microarchitectures, without unduly affecting the performance, to provide correct program execution and/or detect failures (permanent or transient) that can occur in the hardware. This paper proposes a time redundancy technique suitable for multiscalar architectures. In the multiscalar architecture, there are usually several processing units to exploit the instruction level parallelism that exists in a given program. The technique in this paper uses a majority of the processing units for executing the program as in the traditional multiscalar paradigm while using the remainder of the processing units for re-executing the committed instructions. By comparing the results from the two program executions, errors caused by permanent or transient faults in the processing units can be detected. Simulation results presented in this paper demonstrate that this can be achieved with about 5-15% performance degradation.

We describe a scheme called TCP-SMART to improve the end-to-end throughput of TCP connections in the spotty wide band environment. In this scheme, a TCP-SMART agent at the base station uses local retransmissions, acknowledgment filtering, and selective generation of duplicate acknowledgments to increase the TCP throughput despite extended periods of poor channel conditions and short disconnections. When compared to other schemes, TCP-SMART achieves higher end-to-end TCP throughput.

In a Code Division Multiple Access (CDMA) network, multiple mobile hosts (MHs) can simultaneously transmit over the wireless channel by using different codes. To assure an acceptable quality of service for all users' flows, the network usually tunes the transmit powers of all MHs to achieve a certain level of signal strength as compared to the noise and the interference (SINR) for each user. The traditional assumption in power control schemes is that the SINR requirement is statically determined for each user flow.

User mobility management is one of the important components of mobile multimedia systems. In a cell-based network, a mobile should be able to seamlessly obtain transmission resources after handoff to a new basestation. This is essential for both service continuity and quality of service assurance. We present strategies for accommodating continuous service to mobile users through estimating resource requirements of potential handoff connections. A diverse mix of heterogeneous traffic with diverse resource requirements is considered. We investigate static and dynamic resource allocation schemes. The dynamic scheme probabilistically estimates the potential number of connections that will be handed off from neighboring cells, for each class of traffic. The performance of these strategies in terms of connection blocking probabilities for handoff and local new connection requests are evaluated. The performance is also compared to a scheme previously proposed by Yu and Leung (see IEEE Journal on Selected Areas in Communications, vol.15, p.1208-25, 1997). The results indicate that using dynamic estimation and allocation, we can significantly reduce the dropping probability for handoff connections.

Internet applications and users have very diverse service expectations, making the current same-service-to-all model inadequate and limiting. In the relative differentiated services approach, the network traffic is grouped in a small number of service classes which are ordered based on their packet forwarding quality, in terms of per-hop metrics for the queueing delays and packet losses. The users and applications, in this context, can adaptivelychoose the class that best meets their quality and pricing constraints, based on the assurance that higher classes will be better, or at least no worse, than lower classes. In this work, we propose the proportional differentiation model as a way to refine and quantify this basic premise of relative differentiated services. The proportional differentiation model aims to provide the network operator with the 'tuning knobs' for adjusting the quality spacing between classes, independent of the class loads; this cannot be achieved with other relative differentiation models, such as strict prioritization or capacity differentiation. We apply the proportional model on queueing-delay differentiation only, leaving the problem of coupled delay and loss differentiation for future work. We discuss the dynamics of the proportional delay differentiation model and state the conditions under which it is feasible. Then, we identify and evaluate (using simulations) two packet schedulers that approximate the proportional differentiation model in heavy-load conditions, even in short timescales. Finally, we demonstrate that such per-hop and class-based mechanisms can provide consistent end-to-end differentiation to individual flows from different classes, independently of the network path and flow characteristics.

User mobility management is one of the important components of mobile multimedia systems. In a cell-based network, a mobile should be able to seamlessly obtain transmission resources after handoff to a new base station. This is essential for both service continuity and quality of service assurance. In this paper, we present strategies for accommodating continuous service to mobile users through estimating resource requirements of potential handoff connections. A diverse mix of heterogeneous traffic with diverse resource requirements is considered. The investigate static and dynamic resource allocation schemes. The dynamic scheme probabilistically estimates the potential number of connections that will be handed off from neighboring cells, for each class of traffic. The performance of these strategies in terms of connection blocking probabilities for handoff and local new connection requests are evaluated. The performance is also compared to a scheme previously proposed by Yu and Leung (see IEEE J. Select. Areas Commun., vol.15, p.1208-25, 1997). The results indicate that using dynamic estimation and allocation, we can significantly reduce the dropping probability for handoff connections.

Tasks in a real-time control application are usually periodic and they have deadline constraints by which each instance of a task is expected to complete its computation, even in the adverse circumstances caused by component failures. Techniques to recover from processor failures often involve a reconfiguration in which all tasks are assigned to fault-free processors. This reconfiguration may result in processor overload where it is no longer possible to meet the deadlines of all tasks. In this paper, we discuss an overload management technique which discards selected task instances in such a way that the performance of the control loops in the system remain satisfactory even after a failure. The technique is based on the rationale that real-time control applications can tolerate occasional misses of the control law updates, especially if the control law is modified to account for these missed updates. The paper devises a scheduling policy which deterministically guarantees when and where the misses will occur. The paper also proposes a methodology for modifying the control law to minimize the deterioration in the control system behavior as a result of these missed control law updates.

The growing demand for mobility has increased the need to develop more efficient, reliable and cost effective services for data transmission over the air interface. The air interface, as compared to the wired domain, is characterized by a high bit-error-rate, limited bandwidth, and intermittent connectivity. In addition, power in the hand-held devices and laptops is limited by the battery technology. We present AFEC, an adaptive forward error-correction scheme, which makes effective use of the air interface by minimizing the number of data bits transmitted to convey message packets in a real-time stream over an air interface. Through simulations, we show that AFEC outperforms the traditional single forward error-correction scheme.

Bit errors are fairly common during transmission in a wireless network.As a result, a straight-forwarcl application of existing packet fair queueing (PFQ) algorithms from wire-Iine to wireless networks results in an ine~cient use of ~he Kmited wireless bandwidth.In this paper, we propose a simple approach for adapting the existing PFQ algorithms for the wire]ine networks to provide the same kind of long-term fairness guarantees while making efficient use of the wireless bandwidth.In the proposed approach, long-term fairness guarantees are provided by supplementing the bandwidth given to sessions which have not received satisfactory service in the short -t erm due to poor quahty of their wireless channel.To efficiently keep track of the amount of supplemental bandwidth for each session, the paper introduces the concept of a long-term fairness server.This concept.also allows one to easily integrate the proposed approach with any of the existing PFQ algorithms.

Mobile computers typically have limited energy for computing and communications due to short battery lifetimes. Encoding, decoding, and transmission of video information require significant computing and communication resources. Low power encoding and decoding schemes have been researched extensively. In this paper, we focus on processing encoded video for transmission under low battery power conditions. Such processing, while conserving battery power, attempts to reduce deterioration of video quality.

In this paper, we first evaluate the performance degradation caused by unequal bandwidths on the execution of conventional parallel algorithms such as the fast Fourier transform on an ATM-based Network of Workstations. We then present a strategy based on dynamic redistribution of data points to reduce the bottlenecks caused by unequal bandwidths. We also extend this strategy to deal with processor heterogeneity. Using analysis and simulation we show that there is a considerable reduction in the runtime if the proposed redistribution strategy is adopted. The basic idea presented in this paper can also be used to improve the runtimes of parallel applications in connection-oriented environments.

A real time message stream is said to have an (m, k) firm guarantee requirement if at least m out of any k consecutive messages from the stream must meet their deadlines to ensure adequate quality of service. M. Hamdaoui and P. Ramanathan (1995) recently proposed a scheduling policy called Distance based Priority Assignment (DBP) to better service multiple real time streams, each with its own (m, k) firm guarantee requirement. The key assumption in the DBP technique is that all messages reach their destination in one hop. This assumption, however, is not valid in most networks because there is often no direct connection between the source and the destination nodes of a real time stream. The DBP scheme is extended to deal with streams in which the messages traverse more than one hop in reaching their destination. Through empirical evaluation, it is also shown that this extended DBP scheme, called DBP-M, performs better than existing policies in reducing the probability of not meeting the (m, k) firm guarantee requirement.

A real-time stream is said to have (m, k)-firm deadlines if at least m out of any k-consecutive customers from the stream must meet their respective deadlines. Such a stream is said to have encountered a dynamic failure if fewer than m out of any k consecutive customers meet their deadlines. Hamdaoui and Ramanathan recently proposed a scheduling policy called Distance Based Priority (DBP) in which customers are serviced with a higher priority if their streams are closer to a dynamic failure. In terms of reducing the probability of dynamic failure, Hamdaoui and Ramanathan also showed, using simulation, that the DBP policy is better than a policy in which all customers are serviced at the same priority level. In this paper, an analytic model is developed for computing the probability of dynamic failure of a real-time stream for the DBP and the single priority schemes. This model is useful for providing statistical quality of service guarantees to real-time streams. The probability of dynamic failure computed using this model is compared to the results from a discrete-event simulator. The comparison shows that the model is accurate for low and moderate loads.

Tasks in a real-time application usually have several stringent timing, resource, and communication requirements. Designing a distributed computing system which can meet all these requirements is a challenging problem. In this paper, we alleviate this problem by proposing a technique to determine a lower bound on the number of processors and resources required to meet the constraints of the application. We also extend the technique to estimate the cost of a system which meets all the application constraints. The proposed technique deals with most constraints found in real-time applications including deadlines, release times, resource requirements, precedence relationships, and non-zero communication times. It also derives these bounds for two different models of distributed systems.

The fiber distributed data interface (FDDI) is suitable for real-time communication because of the high speed and the performance guarantees it provides. However, these guarantees are achieved at the expense of non-real-time traffic because the real-time messages are given higher priority over non-real-time messages,resulting in excessive delays for non-real-time messages. In this paper, we propose a scheme for reducing the response time of non-real-time messages while still providing the same guarantees to real-time messages. In particular, the proposed approach gives higher priority to real-time messages only when it is absolutely necessary in order for them to meet their deadlines. Non-real-time messages are thus transmitted ahead of real-time messages whenever possible. We present an algorithm for determining when and by how much the transmission of a real-time message can be deferred without jeopardizing its deadline. The proposed approach is evaluated through simulation. The simulation results show that a substantial reduction in the mean response time of non-real-time messages is achieved when using the proposed approach.

The problem of scheduling multiple streams of real-time customers, is addressed in this paper. The paper first introduces the notion of (m, k)-firm deadlines to better characterize the timing constraints of real-time streams. More specifically, a stream is said to have (m, k)-firm deadlines if at least m out of any k consecutive customers must meet their deadlines. A stream with (m, k)-firm deadlines experiences a dynamic failure if fewer than m out of any k consecutive customers meet their deadlines. The paper then proposes a priority-based policy for scheduling N such streams on a single server to reduce the probability of dynamic failure. The basic idea is to assign higher priorities to customers from streams that are closer to a dynamic failure so as to improve their chances of meeting their deadlines. The paper proposes a heuristic for assigning these priorities. The effectiveness of this approach is evaluated through simulation under various customer arrival and service patterns. The scheme is compared to a conventional scheme where all customers are serviced at the same priority level and to an imprecise computation model approach. The evaluation shows that substantial reductions in the probability of dynamic failure are achieved when the proposed policy is used.

Networks that use the timed token protocol (such as the 100 Mbit/s FDDI network) are well suited for real-time applications because they guarantee, to each node, an average bandwidth and a bounded access time to the communication network. This guarantee is necessary but not sufficient for the timely delivery of deadline-constrained messages; protocol parameters must be carefully selected to ensure that these messages meet their deadlines. This paper addresses the issue of selecting the protocol parameters TTRT (target token rotation time) and the synchronous capacities assigned to each node. The objective is to guarantee that each synchronous message is transmitted before its deadline. An upper bound is derived on the worst case achievable utilization (WCAU) of any parameter selection scheme. The WCAU of a scheme is defined as the maximum utilization U such that the scheme guarantees all synchronous messages as long as their utilization is less than U. An algorithm for selecting the above parameters is proposed, The algorithm is shown to have a WCAU that is very close to the upper bound.>

The problem of placing resources in a k-ary n-cube (k>2) is considered in this paper. For a given j/spl ges/1, resources are placed such that each nonresource node is adjacent to j resource nodes. We first prove that perfect j-adjacency placements are impossible in k-ary n-cubes if n>

A real-time channel is a communication mechanism commonly used to guarantee timely delivery of messages between two nodes of a distributed system. It is established at the request of an application task. In the request, the task specifies its worst-case traffic pattern and the required timing constraints. The system accepts the request only if it can guarantee the requested timing constraints without jeopardizing the guarantees provided to the established channels. The main objective of the scheme proposed in this paper is to increase the fraction of channel establishment requests accepted by the system. The proposed scheme increases the fraction of accepted requests by exploiting the existence of multiple routes between two nodes of a distributed system. In particular, unlike existing schemes, it carefully partitions a message and sends the message partitions along different routes to guarantee their timely delivery. In partitioning the message, it also ensures that the overhead of re-sequencing the partitions sent along different routes is minimal. The end result is a better channel establishment procedure for guaranteeing sequenced, timely delivery of messages in a real-time application.>

This paper surveys the state of the art in real-time computing. It introduces basic concepts and identifies key issues in the design of real-time systems. Solutions proposed in literature for tackling these issues are also briefly discussed.>

The fiber distributed data interface (FDDI) is suitable for real-time communication. A scheme for reducing the response time of non-real-time messages while still providing the same quality of service to real-time messages is proposed. In the proposed approach, non-real-time messages are transmitted ahead of real-time messages unless it is absolutely necessary to transmit real-time messages first in order to meet their deadlines. Simulation results show that a substantial reduction in the mean response time of non-real-time messages is achieved when using the proposed approach.

An approach to checkpointing and rollback recovery in a distributed computing system using a common time base is proposed. A common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with the idea of pseudo-recovery points to develop a checkpointing algorithm that has the following advantages: reduced wait for commitment for establishing recovery lines, fewer messages to be exchanged, and less memory requirement. These advantages are assessed quantitatively by developing a probabilistic model.>

The authors address the problem of testing the check bits in RAMs with on-chip ECC. A solution is proposed in which the check bits are tested in parallel with the testing of the information bits. The solution entails finding parity-check matrices such that all the check bits are tested while the information bits are being tested, without any increase in the length of the test sequence. The resulting parity-check matrix is such that there is no loss in error-correction capabilities and with minimal penalty in the worst-case delay of the error-correcting logic.>

Reliable and timely delivery of messages between processing nodes is essential in distributed real-time systems. Failure to deliver a message within its deadline usually forces the system to undertake a recovery action, which introduces some cost (or overhead) to the system. This recovery cost can be very high, especially when the recovery action fails due to lack of time or resources. Proposed in this paper is a scheme to minimize the expected cost incurred as a result of messages failing to meet their deadlines. The scheme is intended for distributed real-time systems, especially with a point-to-point interconnection topology. The goal of minimizing the expected cost is achieved by sending multiple copies of a message through disjoint routes and thus increasing the probability of successful message delivery within the deadline. However, as the number of copies increases, the message traffic on the network increases, thereby increasing the delivery time for each of the copies. There is therefore a tradeoff between the number of copies of each message and the expected cost incurred as a result of messages missing their deadlines. The number of copies of each message to be sent is determined by optimizing this tradeoff. Simulation results for a hexagonal mesh and a hypercube topology indicate that the expected cost can be lowered substantially by the proposed scheme.

The authors present a formal analysis of virtual cut-through in a C-wrapped hexagonal mesh multicomputer, called the HARTS (hexagonal architecture for real-time systems). In virtual cut-through, packets arriving at an intermediate node are forwarded to the next node in the route without buffering if a circuit can be established to the next node. The hexagonal mesh is first characterized using a combinatorial analysis to determine the probability that a packet will establish a cut-through at an intermediate node. Given this parameter the probability distribution function for packet delivery times in HARTS is derived. The delivery times obtained from the analytic model are then compared against results collected from a simulator of the routing hardware designed for use in HARTS. The results from both the analytic model and the simulator further reinforce the choice of the virtual cut-through routing scheme for use in HARTS.>

A clock synchronization scheme that strikes a balance between hardware and software solutions is proposed. The proposed scheme is a software algorithm that uses minimal additional hardware to achieve reasonably tight synchronization. Unlike other software solutions, the guaranteed worst-cast skews can be made insensitive to the maximum variation of message transit delay in the system. The scheme is particularly suitable for large partially connected distributed systems with topologies that support simple point-to-point broadcast algorithms. Examples of such topologies include the hypercube and the mesh interconnection structures.>

The authors propose a clock distribution scheme that minimizes the difference in the length of clock lines, which is the foremost factor responsible for clock skew in a VLSI circuit. The scheme uses the hierarchy created by the clock buffers to parallelize the distribution of the clock signal. At each hierarchical level, an exhaustive search of paths with intelligent pruning is used to determine the optimal layout of clock lines at that level. Unlike other related work in this area, both delay and skew are taken into account in determining the layout.>

The design and implementation of a VLSI routing controller for use in the Hexagonal Architecture for Real-Time Systems (HARTS), which is currently being built, are presented. The routing controller is a microprogrammed unit designed to function as an intelligent front-end interface for the interconnection network. Unlike other routine controllers known to date, this routing controller allows for the flexibility to investigate several low-level routing algorithms by downloading the appropriate microcode into the routing controller. The design was carried out using the combination of Seattle Silicon Technology's silicon compiler and Mentor Graphic's schematic capture and simulation tools. The implementation is targeted for a 64-pin package using a 1.2- mu m CMOS process.>

An approach to checkpointing and rollback recovery in a distributed computing system using a common time base is proposed. First, a common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with a pseudorecovery block approach to develop a checkpointing algorithm that has the following advantages: (i) maximum process autonomy, (ii) no wait for commitment for establishing recovery lines, (iii) fewer messages to be exchanged, and (iv) less memory requirement.>

A simple algorithm for broadcasting in a hypercube multicomputer containing faulty nodes/links is proposed. The algorithm delivers multiple copies of the broadcast message through disjoint paths to all the modes in the system. Its salient feature is that the delivery of the multiple copies is transparent to the processes receiving the message and does not require the processes to know the identity of the faulty processors. The processes on nonfaulty nodes that receive the message identify the original message from the multiple copies using some scheme appropriate for the fault model used. The algorithm completes in n+1 steps if each node can simultaneously use all of its outgoing links. If each node cannot use more than one outgoing link at a time, then the algorithm requires 2n steps.>

Various methods, both with software and hardware, have been proposed to synchronize a set of physical clocks in the system. Software methods are very flexible and economical but suffer an excessive time overhead, whereas hardware methods require no time overhead but are unable to handle transmission delays in clock signals. The effects of nonzero transmission delays in synchronization have been studied extensively in the communication area in the absence of malicious or Byzantine faults. The authors show that it is easy to incorporate the ideas from the communication area into the existing hardware clock synchronization algorithms in order to take into account the presence of both malicious faults and nonzero transmission delays.>

Clock synchronization in the presence of malicious faults is one of the main problems associated with the design of a multiprocessor system. Although over the past few years many different algorithms have been proposed for overcoming this problem, they are not suitable for a large real-time multiprocessor system due to their excessive time overhead, asymmetric structure, and/or large number of interconnections. To remedy this problem, we propose a new method in this paper that i) requires little time overhead by using phase-locked clock synchronization, ii) needs a clock network very similar to the processor network, and iii) uses only 20-30 percent of the total number of interconnections required by a fully connected network for almost no loss in the synchronizing capabilities. Both ii) and iii) are made possible by grouping the various clocks in the system into many different clusters and then treating the clusters themselves as single clock units as far as the network is concerned. The method is significant in that regardless of their size multiprocessor systems can be built at an inexpensive cost without sacrificing both the synchronization and fault tolerance capabilities. To show the feasibility of our method, an example hardware implementation is presented. This implementation turns out to be much simpler than the other existing methods and also retains the symmetry and synchronizing capabilities of the network.