Predictive Caching Strategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Route caching strategy is important in on-demand routing protocols in wireless ad hoc networks. While high routing overhead usually has a significant performance impact in low bandwidth wireless networks, a good route caching strategy can reduce routing overheads by making use of the available route information more efficiently. In this paper, we first study the effects of two cache schemes, link cache and path cache, on the performance of on-demand routing protocols through simulations based on the Dynamic Source Routing (DSR) protocol. Since the path cache DSR has been extensively studied, we focus in this paper on the link cache DSR in combination with timer-based stale link expiry mechanisms. The effects of different link lifetime values on the performance of routing protocol in terms of routing overhead, packet delivery ratio and packet latency are investigated. A caching strategy incorporating adaptive link timeout is then proposed, which aims at tracking the optimal link lifetime under various node mobility levels by adaptively adjusting the link lifetime based on the real link lifetime statistics. The performance of the proposed strategy is then compared with the conventional path cache DSR. The results show that without a timeout mechanism, a link cache scheme may suffer severe performance degradation due to the use of broken routes, while the proposed adaptive link cache strategy achieves significantly improved performance by reducing the routing overhead when the network traffic load is high.     

Economics of “design for test” to remain competitive in the 90s

This article emphasizes the criticality of maximizing value adders and minimizing the costs of design for test (DFT) in order to remain competitive in ASIC manufacturing in the 90s.     

On the Capacity of IEEE 802.11 DCF with Capture in Multipath-Faded Channels

In this paper, we estimated the influence of capture effect over the capacity of IEEE 802.11b DCF within a single picocell. The channel utilization is examined analytically by introducing two capture models based on Rayleigh-distributed envelopes of the captured and the interfering frames divided into two local-mean power classes. Simulations in a pure Rician-faded channel depict the conditions under which both Rayleigh-faded capture models can be used to accurately predict the peak network capacity. Unlike the RTS/CTS handshake access mode, Basic access mode is significantly sensitive to the capture ratio, i.e., the receiver design. The packet size threshold over which it is convenient to switch from Basic to RTS/CTS handshake access scheme is also sensitive to the capture effect.     

Mobile ATM buffer capacity analysis

This paper extends a stochastic theory for buffer fill distribution for multiple on and off sources to a mobile environment. Queue fill distribution is described by a set of differential equations assuming sources alternate asynchronously between exponentially distributed periods in on and off states. This paper includes the probabilities that mobile sources have links to a given queue. The sources represent mobile user nodes, and the queue represents the capacity of a switch. This paper presents a method of analysis which uses mobile parameters such as speed, call rates per unit area, cell area, and call duration and determines queue fill distribution at the ATM cell level. The analytic results are compared with simulation results.This paper is partially funded by ARPA contract number J-FBI-94-223.The Mathematica code for this paper can be found on http://www.tisl.ukans.edu/sbush.     

Systems which possessg- andh- Representations

Examples are given concerning the range of applicability of recent representation results that provide a means of studying the input-output properties of nonlinear systems in terms of the familiar impulse-response concept, and which extend the concept of integral transformation to nonlinear maps. We show that such representations, which we call g- and h-representations, exist for important classes of systems governed by nonlinear integral equations. In particular, it is proved that a large class of maps that have Volterra series representations also have these representations.     

The significance of finite buffer edge effects in histogram measurements of queues

The empirically oberved fractal or self-similar nature of packet traffic implies heavy tailed queue processes for such traffic. However, based on our simulation analysis using real network data as well as standard models, we have found that the actual losses sustained are remarkably lower than those suggested by the heavy tail distribution. This can be explained by an effect observed in the tail of the histogram of a finite buffer queue process, which we call tail-raising, which contains information pertinent to performance estimation. This effect is also responsible for a significant reduction in packet losses for finite buffer systems, than would be otherwise predicted by the buffer overflow probability for heavy-tailed queues. We define a new parameter X _B on the histogram of a queue process for a finite buffer system, to calculate the tail of the queue process based on the information available in the histogram on the finite buffer. We propose an estimator that approximates X _B , namely, X _min, which is measurable because of the tail-raising effect and has a robust measurement method. The proposed estimator shows promise as a good predictor for performance metrics of queueing systems. We propose an innovative packet loss ratio estimation technique which uses histogram measurements combined with a virtual buffer scheme to find and extrapolate the objective packet loss rate using a binning strategy for histogram measurement, namely, Symmetric Logarithmic Binning (SLB).     

2-D harmonic retrieval using higher-order statistics

We consider the problem of estimating the harmonics of a noisy 2-D signal. The observed data is modeled as a 2-D sinusoidal signal, with either random or deterministic phases, plus additive Gaussian noise ofunknown covariance. Our method utilizes recently defined higher-order statistics, referred to as mixed-cumulants, which permit a formulation that is applicable to both the random and deterministic case. In particular, we first estimate the frequencies in each dimension using an overdetermined Yule-Walker type approach. Then, the 1-D frequencies are paired using a matching criterion. To support our theory, we examine the performance of the proposed method via simulations.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

Design of High-Performance Wavelets for Image Coding Using a Perceptual Time Domain Criterion

This paper presents a new biorthogonal linear-phase wavelet design for image compression. Instead of calculating the prototype filters as spectral factors of a half-band filter, the design is based on the direct optimization of the lowpass analysis filter using an objective function directly related to a perceptual criterion for image compression. This function is defined as the product of the theoretical coding gain and an index called the peak-to-peak ratio, which was shown to have high correlation with perceptual quality. A distinctive feature of the proposed technique is a procedure by which, given a good starting filter, good filters of longer lengths are generated. The results are excellent, showing a clear improvement in perceptual image quality. Also, we devised a criterion for constraining the coefficients of the filters in order to design wavelets with minimum ringing.     

Performance Analysis of Bidding Policy for Competitive Network Providers

This paper proposes an optimum bidding policy in a competitive network provider's environment, where each network provider can bid for individual connection requests according to its own criteria. The proposed bidding policy is based on the concept of shadow price. In other words, each network provider bids only for connection requests with an expected profit exceeding its shadow price. Because such connection request brings profit in the long term, each network provider can maximize its long-term profit by adopting this bidding policy. In this paper, the optimum bidding policy for network providers is analyzed by means of the policy iteration method derived from the Markov decision theory. The economic efficiency of the bidding policy is evaluated using several numerical examples, in which each network provider adopts fixed pricing and state-dependent pricing, respectively. By adopting the bidding policy in both cases, each network provider can maximize its long-term profit while the total users' consumer surplus is slightly reduced.     

A unified partitioning and scheduling scheme for mapping multi-stage regular iterative algorithms onto processor arrays

This paper addresses the partitioning and scheduling problems in mapping multi-stage regular iterative algorithms onto fixed size distributed memory processor arrays. We first propose a versatile partitioning model which provides a unified framework to integrate various partitioning schemes such as locally sequential globally parallel, locally parallel globally sequential and multi-projection. To alleviate the run time data migration overhead—a crucial problem to the mapping of multi-stage algorithms, we further relax the widely adopted atomic partitioning constraint in our model such that a more flexible partitioning scheme can be achieved. Based on this unified partitioning model, a novel hierarchical scheduling scheme which applies separate schedules at different processor hierarchies is then developed. The scheduling problem is then formulated into a set of ILP problem and solved by the existing software package for optimal solutions. Examples indicate that our partitioning model is a superset of the existing schemes and the proposed hierarchical scheduling scheme can outperform the conventional one-level linear schedule.     

Current Mode Circuit Implementations of PWL Functions

Current-mode techniques have been used to realize improved basic building blocks of elementary piecewise linear (PWL) functions. These alternative circuit implementations, used for synthesis of precision PWL transfer characteristics, are described and compared in performance. In this paper, two optional topologies of the PWL function building blocks are proposed, based on the regulated cascode current mirror, current sources, Schottky prebiased diodes, and improved CMOS class AB prebiased diodes. The comparison of DC and high frequency performances is based on HSPICE simulation results and shows very good DC accuracy and transient time response of the proposed building blocks.     

The dangers of simplistic delay models

The identification of sensitizable paths and the determination of path delays play key roles in many delay fault testing schemes. In this paper we examine a range of gate delay models with respect to their impact on identifying both sensitizable paths and maximum circuit delays in combinational logic circuits. We provide recommendations on the minimum acceptable model for identifying critical paths, and a minimum acceptable model for determining maximum circuit delays. In particular, we recommend against the use of delay models which fail to distinguish between rise and fall delays. Such models, including the commonly-used unit-delay model, are shown to significantly misrepresent circuit delay behaviour, particularly with respect to critical paths and long false paths.This research is supported by the Natural Sciences and Engineering Research Council of Canada.     

On the analysis of two-dimensional discrete singular systems

In contrast to 1-D systems, the 2-D systems have no natural notion of causality. An artificial restriction traditionally imposed to allow recursive solution of these systems is that of recursibility. In this paper we study 2-Dsingular systems, taking advantage of the nonoriented or noncausal nature of these systems to provide a solution even if the requirement of recursibility does not hold. It is shown thatnonrecursible masks may be described using singular 2-D systems. The analysis approach relies on thefundamental matrix.Research supported by the US Fulbright Foundation in Greece and NSF Grant ECS-8805932.     

Flexibly Reconfigurable Fiber-Wireless Network using Wavelength Routing Techniques: The ACTS Project AC349 PRISMA

A dynamically reconfigurable fiber-wireless network using flexible wavelength routing techniques is proposed by the PRISMA project, which offers a forecast-tolerant solution for handling a wide variety of wireless services and capacity demands as may emerge in the fast evolving market of mobile communications. This approach can considerably increase the operation efficiency of wireless networks for broadband nomadic services (wireless LANs). It also supports the evolution from GSM and GPRS towards UMTS, and the entry of new operators and/or services into the liberalized mobile communications market. The system has been implemented in a field trial and has been operated successfully with real users and broadband nomadic services. The system concept is ready for further development into products.     

Synthesis of arbitrary digital transfer functions using allpass-based structures derived via LBR two-pair extraction procedure

The implementation of a digital filter transfer function with all transmission zeros on the unit circle is developed via the synthesis of an appropriate allpass function. The synthesis procedure is based on the LBR-extraction approach. The resulting structure is in the form of a doubly terminated cascade of lossless (LBR) two-pairs, with each two-pair realizing a single real or a pair of complex transmission zeros. The Concepts of complete and partial 1 removals, and 1 shifting are introduced and utilized during the synthesis process. The resulting structures have several properties in common with the Gray and Markel lattice filters, but do not require tap coefficients for numerator realization. The building blocks used in this paper are similar to those in certain wave-digital filters and orthogonal filters.Work supported in part by NSF Grant Number ECS 82-18310 and in part by NSF Grant Number ECS-8508017.     

Recursive identification algorithms

Mechanisms for adapting models, filters, decisions, regulators, and so on to changing properties of a system or a signal are of fundamental importance in many modern signal processing and control algorithms. This contribution describes a basic foundation for developing and analyzing such algorithms. Special attention is paid to the rationale behind the different algorithms, thus distinguishing between optimal algorithms and ad hoc algorithms. We also outline the basic approaches to performance analysis of adaptive algorithms.     

Optical-LSP Establishment and a QoS Maintenance Scheme Based on Differentiated Optical QoS Classes in OVPNs

A virtual private network (VPN) over Internet has the benefit of being cost-effective and flexible. However, it has difficulties providing sufficient QoS and adequate transmission capacity for high bandwidth services. Given the increasing demand for high bandwidth Internet and the demand for QoS assurances in a VPN over Internet, IP/generalized multi-protocol label switching (GMPLS) based on a control plane combined with a high-bandwidth, dense-wavelength division multiplexing (DWDM) optical network is seen as a very favorable approach for realizing the future optical VPN (OVPN) over IP/GMPLS over DWDM. Within this architecture, providing QoS guaranteed multimedia services with a differentiated QoS guaranteed protocol framework with QoS recovery is one of the key issues to implement. Therefore, we suggest in this paper optical-label switched path (O-LSP) establishment and its QoS maintenance scheme based on differentiated optical QoS-service (DOQoS) classes. They are the key components for this DOQoS framework in assuring end-to-end QoS in an OVPN over IP/GMPLS over DWDM architecture.     

Incorporating QoS into IP Enterprise Network Design

Recent trends in enterprise networks are radically changing the composition of these systems. Instead of having diverse data networks, each of which is dedicated to a single class of applications, corporations are moving to a unified IP (Internet Protocol) Intranet. Traffic demands on these Intranets include delay-sensitive traffic that requires better than the standard best effort service provided by IP networks. As a result, various new technologies and strategies to provide end-to-end Quality of Service (QoS) within IP enterprise networks are being developed and implemented. However, current IP network design methodologies are limited in that they can only design networks providing best effort service or else, a single delay constraint for all traffic. In this paper, we discuss a new design methodology for IP enterprise networks that takes into account the new technologies and techniques that can provide QoS. In particular, we identify and discuss the most crucial design issues that must be addressed when specialized queuing-based QoS strategies are used in the network. We describe the new constraints introduced by the underlying technologies and discuss how these factors affect the formulation of the IP Enterprise Network Design Problem. We then describe some specific features and methodologies that have been incorporated into a network design-planning tool for IP enterprise networks with QoS.     

Recursive estimation of two-dimensional processes with application to image processing

A low order quarter-plane-causal recursive model is presented to represent the class of 2-D stationary Gaussian processes with power spectra matrices factorable into a quarter-plane-causal and anti-causal parts. This model is used to develop a technique for obtaining optimal 2-D recursive estimators. The approach taken here is similar to Attasi's [8], with no commutability condition imposed on the model. Circumventing this condition allows the modeling of the 2-D processes to be achieved with fewer parameters, and enables one to find the solutions to the problems of blur and color noise which are inherent in most image degraded images. Some simulated examples illustrate these points.This research was supported in part by the U.S. Army Research Grant DAAG29-79-C-0054 and the National Science Foundation Grant ECS-8011911.