A scalable wireless virtual LAN

This paper presents a Wireless Virtual Local Area Network (WVLAN) to support mobility in IPoverATM local area networks. Mobility is handled by a joint ATMlayer handoff for connection rerouting and MAClayer handoff for location tracking, such that the effects of mobility are localized and transparent to the higherlayer protocols. Different functions, such as Address Resolution Protocol (ARP), mobile location, and ATM connection admission are combined to reduce protocol overhead and frontend delay for connectionless packet transmission in connectionoriented ATM networks. The proposed WVLAN, through the use of ATM technology, provides a scalable wireless virtual LAN solution for IP mobile hosts.     

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.     

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.     

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.     

Symmetry relations in multidimensional Fourier transform pairs

A relation between the types of symmetries that exist in signal and Fourier transform domain representations is derived for continuous as well as discrete domain signals. The symmetry is expressed by a set of parameters, and the relations derived in this paper will help to find the parameters of a symmetry in the signal or transform domain resulting from a given symmetry in the transform or signal domain respectively. A duality among the relations governing the conversion of the parameters of symmetry in the two domains is also brought to light. The application of the relations is illustrated by a number of two-dimensional examples.Notation R the set of real numbers - R ^m R × R × ... × R m-dimensional real vector space - continuous domain real vector - L {¦ – _i , i = 1,2,..., m} - m-dimensional frequency vector - W { – _i ,i=1,2,..., m} - m-dimensional normalized frequency vector - _P {¦ – _i , i=1,2,...,m} - g(ol) g (₁,₂,..., _m ) continuous domain signal - () ( _{1 2},..., _m )=G (j ₁,j ₂,..., j _m ) Fourier transform ofg (ol) - (A,b,,,) parameters ofT- symmetry - N the set of integers - N ^m N × N × ... × N m-dimensional integer vector spacem-dimensional lattice - h(n) h (n ₁,.,n _m ) discrete domain signal - H() Fourier transform ofh (n) - v ₁,v ₂,..., v_m m sample-direction and interval vectors - V (v ₁ v ₂ ...v _m ) sampling basis matrix - [x]^* complex conjugate ofx - detA determinant ofA - X {x¦ – x _i , i=1,2,..., m} - A ^–t [A ^–1] ^t ,t stands for transpose This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739 to M. N. S. Swamy and in part by Tennessee Technological University under its Faculty Research support program to P. K. Rajan.     

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.     

Throughput performance of distributed applications in switched networks in presence of end‐system bottlenecks

The steady state throughput performance of distributed applications deployed in switched networks in presence of endsystem bottlenecks is studied in this paper. The effect of various limitations at an endsystem is modelled as an equivalent transmission capacity limitation. A class of distributed applications is characterised by a static traffic distribution matrix that determines the communication between various components of the application. It is found that uniqueness of steady state throughputs depends only on the traffic distribution matrix and that some applications (e.g., broadcast applications) can yield nonunique values for the steady state component throughputs. For a given switch capacity, with traffic distribution that yield fair unique throughputs, the tradeoff between the endsystem capacity and the number of application components is brought out. With a proposed distributed rate control, it has been illustrated that it is possible to have unique solution for certain traffic distributions which is otherwise impossible. Also, by proper selection of rate control parameters, various throughput performance objectives can be realised.     

On a “central inequality” in the theory of input-output systems

In the stability and sensitivity theory of general, nonlinear input-output systems we encounter a certain inequality concerning solely the nominal system that plays a central role in the whole theory. In particular, this central inequality, combined with other assumptions, implies (a) stability of the nominal system, (b) robustness, and (c) insensitivity of the input-output system. This paper presents conditions equivalent to this central inequality, and a further result on the stability-robustness problem.     

A reservation-based multicast (RBM) routing protocol for mobile networks: initial route construction phase

We propose a combined multicast routing, resource reservation and admission control protocol, termed Reservation-Based Multicast (RBM), that borrows the Rendezvous Point or Core concept from multicast routing algorithms proposed for the Internet, but which is intended for operation in mobile networks and routes hierarchically-encoded data streams based on user-specified fidelity requirements, real-time delivery thresholds and prevailing network bandwidth constraints. The protocol exhibits the fully distributed operation and receiver-initiated orientation of these proposed algorithms; but, unlike them, the protocol is tightly coupled to a class of underlying, distributed, unicast routing protocols thereby facilitating operation in a dynamic topology. This paper focuses on the initial route construction phase, assumed to occur during a static snapshot of the dynamic topology, and is therefore applicable to fixed networks as well, e.g. the Internet.This work was sponsored by the U.S. Navy and the American Society for Engineering Education under the U.S. Navy's Summer Faculty Research Program.Each application must specify a mechanism for ensuring that a processor is always aware of its associated entities. For example, in the current Internet architecture, a group membership protocol [2] serves a similar function of keeping routers informed of the membership their directly attached subnetworks.A processor can be viewed as either an IP router or an ATM switch.     

A Content-Addressable Memory Using “Switched Diffusion Analog Memory with Feedback Circuit”

For the purpose of realizing a new intelligent system and its simplified VLSI implementation, we propose a new nonvolatile analog memory called switched diffusion analog memory with feedback circuit (FBSDAM). FBSDAM has linear writing and erasing characteristics. Therefore, FBSDAM is useful for memorizing an analog value exactly. We also propose a new analog content-addressable memory (CAM) which has neural-like learning and discriminating functions which discriminate whether an incoming pattern is an unknown pattern or a stored pattern. We design and fabricate the CAM using FBSDAM by means of the 4 m double-poly single-metal CMOS process and nonvolatile analog memory technology which are developed by us. The chip size is 3.1 mm×3.1 mm. We estimate that the CAM is composed of 50 times fewer transistors and requires 70 times fewer calculation steps than a typical digital computer implemented using similar technology.     

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.     

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.     

SIVA: A System for Coverage-Directed State Space Search

We introduce SImulation Verification with Augmentation (SIVA), a tool for coverage-directed state space search on digital hardware designs. SIVA tightly integrates simulation with symbolic techniques for efficient state space search. Specifically, the core algorithm uses a combination of ATPG and BDDs to generate directed input vectors, i.e., inputs which cover behavior not excited by simulation. We also present approaches to automatically generate lighthouses that guide the search towards hard-to-reach coverage goals. Experiments demonstrate that our approach is capable of achieving significantly greater coverage than either simulation or symbolic techniques in isolation.     

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.     

Practical zero-knowledge proofs: Giving hints and using deficiencies

New zero-knowledge proofs are given for some number-theoretic problems. All of the problems are in NP, but the proofs given here are much more efficient than the previously known proofs. In addition, these proofs do not require the prover to be superpolynomial in power. A probabilistic polynomial-time prover with the appropriate trapdoor knowledge is sufficient. The proofs are perfect or statistical zero-knowledge in all cases except one.This research was supported in part by NSA Grant No. MDA904-88-H-2006.In this paper it will at times be convenient to think of the verifier as being named Vic, and the prover being named Peggy. Thus, he will refer to the verifier and she will refer to the prover.     

Routing with multiple QoS requirements for supporting multimedia applications

Distributed multimedia applications usually require multiple QoS performance guarantees. However, in general, searching such a route in the network, to support multimedia applications, is known to be NPcomplete. In this paper, we propose a new heuristic QoS routing algorithm, called QoSR_DKS, for supporting multimedia applications in highspeed networks. QoSR_DKS is a modification of rulebased Fallback routing and Dijkstra algorithms. It can search a unicast route that would have enough network resources so that multiple QoS requirements (bandwidth, delay, and delay jitter) of the requested flow could be guaranteed. Its worst case computation time complexity is the same as that of the Dijkstra algorithm, i.e., O(V²), where V is the number of nodes in the network. Extensive simulations were done with various network sizes, upto 500 nodes networks, where each node uses Weighted Fair Queueing (WFQ) service discipline. Results show that QoSR_DKS is very efficient. It could always find the QoS satisfying route, whenever there exists one (success rate is optimal), and its average computation time is near to simple shortest path Dijkstra algorithm.     

On the structure of the privacy hierarchy

An N argument function f(x ₁,...,x _N ) is called t-private if a protocol for computing f exists so that no coalition of at most t parties can infer any additional information from the execution, other than the value of the function. The motivation of this work is to understand what levels of privacy are attainable. So far, only two levels of privacy are known for N argument functions which are defined over finite domains: functions that are N-private and functions that are (N – 1)/2-private but not N/2-private.In this work we show that the privacy hierarchy for N-argument functions which are defined over finite domains, has exactly (N + 1)/2 levels. We prove this by constructing, for any N/2 t N – 2, an N-argument function which is t-private but not (t + 1)-private.This research was supported by US-Israel Binational Science Foundation Grant 88-00282.     

Testing for Function and Performance: Towards an Integrated Processor Validation Methodology

Microprocessor design teams use a combination of simulation-based and formal verification techniques to validate the pre-silicon models prior to tape-out and chip fabrication. Pseudo-random test case generation to cover the architectural space is still relied upon as the principal means to identify design bugs. However, such methods are limited to functional bugs only. Detection and diagnosis of timing (performance) bugs at the architectural level is largely an expert job. Architects guide the performance team to run manually generated test cases to validate the design from a performance viewpoint. In this paper, we will review some of the new approaches being tried out to automate the generation of performance test cases. We will show how this can be done within the basic framework of current functional validation and testing of pre-silicon processor models. Three categories of reference specifications are used in determining the defect-free pipeline timing behavior associated with generated test cases: (a) axiomatic specifications of intrinsic machine latencies and bandwidths; (b) proven analytical models for simple basic block and loop test cases; and, (c) a stable reference behavioral/functional (pre-RTL) model of the processor under development. We report experimental results obtained in performance validation studies applied to real PowerPC processor development projects.     

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.     

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.