Mobility Management for Hierarchical Wireless Networks

In this paper, we consider the mobility management in large, hierarchically organized multihop wireless networks. The examples of such networks range from battlefield networks, emergency disaster relief and law enforcement etc. We present a novel network addressing architecture to accommodate mobility using a Home Agent concept akin to mobile IP. We distinguish between the physical routing hierarchy (dictated by geographical relationships between nodes) and logical hierarchy of subnets in which the members move as a group (e.g., company, brigade, battalion in the battlefield). The performance of the mobility management scheme is investigated through simulation.     

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.     

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.     

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.     

Microsystems Engineering: A Great Stride Forward in Microelectronics Technology

The development of new-generation technological and engineering concepts by the example of microsystems technology and microsystems engineering approaches is considered.     

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

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.     

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.     

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.     

Biasing a differential pair in low-voltage analog circuits: a systematic approach

This paper deals with a systematic approach to the common mode and the differential mode biasing of a differential transistor pair. Four different variants will be shown, two of these variants show practical importance; a practical circuit of one of these variants turns out to be the traditional long-tailed pair. This variant is mainly suited, if the input signal operates at voltage level, whereas another variant has great advantages if operation at current level occurs. Besides, the latter variant turns out to be very favorable in circuits operating with a single low supply voltage. Two practical circuits based on this variant are given.     

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.     

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.     

Is the Data Encryption Standard a group? (Results of cycling experiments on DES)

The Data Encryption Standard (DES) defines an indexed set of permutations acting on the message space ={0,1}⁶⁴. If this set of permutations were closed under functional composition, then the two most popular proposals for strengthening DES through multiple encryption would be equivalent to single encryption. Moreover, DES would be vulnerable to a known-plaintext attack that runs in 2²⁸ steps on the average. It is unknown in the open literature whether or not DES has this weakness.Two statistical tests are presented for determining if an indexed set of permutations acting on a finite message space forms a group under functional composition. The first test is a meet-in-the-middle algorithm which uses O(K) time and space, where K is the size of the key space. The second test, a novel cycling algorithm, uses the same amount of time but only a small constant amount of space. Each test yields a known-plaintext attack against any finite, deterministic cryptosystem that generates a small group.The cycling closure test takes a pseudorandom walk in the message space until a cycle is detected. For each step of the pseudorandom walk, the previous ciphertext is encrypted under a key chosen by a pseudorandom function of the previous ciphertext. Results of the test are asymmetrical: long cycles are overwhelming evidence that the set of permutations is not a group; short cycles are strong evidence that the set of permutations has a structure different from that expected from a set of randomly chosen permutations.Using a combination of software and special-purpose hardware, the cycling closure test was applied to DES. Experiments show, with overwhelming confidence, that DES is not a group. Additional tests confirm that DES is free of certain other gross algebraic weaknesses. But one experiment discovered fixed points of the so-called weak-key transformations, thereby revealing a previously unpublished additional weakness of the weak keys.Support for this research was provided in part by the National Science Foundation under contract number MCS-8006938 and by the International Business Machines Corporation.     

Perspectives on Analytical Modeling of Small Geometry MOSFETs in SPICE for Low Voltage/Low Power CMOS Circuit Design

The present state of the art in analytical MOSFET modeling for SPICE circuit simulation is reviewed, with emphasis on the circuit design usage of these models. It is noted that the model formulation represents an upper limit of what is possible from any type of model, but that good parameter extraction is required to most closely approach that limit. The individual model types presently in common use are examined, with discussion of the behavior of each model, its strengths and weaknesses, its applicability to certain types of circuits, and criteria that a circuit design consumer can employ to judge a model before using it for circuit design. Some related issues, such as node charge and gate capacitance modeling, charge conservation, and statistical simulation of process variations, are also evaluated. Finally, new trends, directions, and requirements of MOSFET modeling for circuit simulation are considered.     

A necessary and sufficient condition for right coprime factorization of nonlinear feedback systems

In this short note, we establish a simple, yet precise, necessary and sufficient condition for the right coprime factorization of a nonlinear feedback control system. As a consequence, we also obtain similar conditions for the stable right coprime factorizations of the nonlinear feedback control system.     

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.     

Controllability of the 2-D roesser model

Necessary and sufficient conditions for controllability of 2-D Roesser model are formulated. One can check controllability of 2-DRM using well-known tests for 1-D systems. Conditions are dual to the conditions for reconstructability of the system: transposed controllable 2-DRM is reconstructable. A numerical example is presented.