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.     

A New Scheme to Realize Crosstalk-Free Permutation in Vertically Stacked Optical MINs*

Vertical stacking is a novel alternative for constructing nonblocking multistage interconnection networks (MINs). Rearrangeably nonblocking optical MINs are attractive since they have lower complexity than their strictly nonblocking counterparts. In this paper, we study the realization of crosstalk-free permutations in rearrangeably nonblocking, self-routing banyan-type optical MINs built on vertical stacking. An available scheme for realizing crosstalk-free permutation in this type of optical MINs requires to first decompose a permutation into multiple crosstalk-free partial permutations based on the Euler-Split technique, and then to realize them crosstalk-free in different planes (stacked copies) of the MIN simultaneously. The overall time complexity of this scheme to realize a crosstalk-free permutation in an N × N optical MIN is O(N log N) which is dominated by the complexity of crosstalk-free decomposition. In this paper, we propose a new scheme for realizing permutations in this class of vertically stacked optical MINs crosstalk-free. The basic idea of the new scheme is to classify permutations into permutation classes such that all permutations in one class share the same crosstalk-free decomposition pattern. By running the Euler-Split based crosstalk-free decomposition only once for a permutation class and applying the obtained crosstalk-free decomposition pattern to all permutations in the class, crosstalk-free decomposition of permutations can be realized in a more efficient way. We show that the number of permutations in a permutation class is huge (N!)^N when log₂N is even and (2N!)^N/2 when log₂N is odd), and thus the average time complexity of crosstalk-free decomposition of a permutation becomes O(N).     

Distance of a complex coefficient stable polynomial from the boundary of the stability set

In this paper, the distance in the 1 2p norm from a complex coefficient polynomial to the border of its Hurwitz region is analyzed. Simplified expressions for 2p=1, 2, are also obtained.This work was supported in part by Comisión Investigaciones Cientificas de la Provincia de Buenos Aires (CIC) and Comisión Nacional de Investigaciones Cientificas y Técnicas (CONICET).     

Linear pseudosystolic array for partitioned matrix algorithms

We describe a class-specific linear pseudosystolic array, withK processing elements, suitable for partitioned execution of matrix algorithms. This array achieves high efficiency, exploits pipelining within cells in a simple manner, has off-cells communication rate lower than computation rate, a small storage inside each cell (whose size is independent of the size of problems), and external storage. This array has been derived from the application of the multimesh graph (MMG) method to a large class of matrix algorithms.Processing elements (cells) use the decoupled access/execute model of computation, which requires two programs in each cell: one controlling the execution of operations and the other the data transfers. All storage modules in the array are accessed as FIFO queues, without the need for addressing mechanisms. We describe the proposed instruction set, which includes single-instruction loops with no overhead, and block-loops with just one extra instruction. Moreover, cells can nest up to three loops with no added overhead. These features are needed for mapping algorithms with the MMG method.Mapping onto this array is illustrated using the LU-decomposition algorithm, and results obtained with other algorithms are also given. Estimates of performance indicate that it is possible to achieve over 85% efficiency, with low requirements in communication bandwidth and storage.This research has been supported in part by Universidad de Concepción (Grant DI-20.92.21, Linear array for matrix algorithms) and by NSF (Grant MIP-8813340, Composite operations using on-line arithmetic in application-specific parallel architectures).     

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.     

On the design of feedback controllers to achieve prescribed initial value constraints

The problem of designing a stabilizing compensator for a control system to achieve prescribed initial value constraints ⁽ⁱ⁾(0⁺)=y_i is considered. Indeed, modulo certain technical conditions, such a compensator exists if and only if y_i=0;i= 0,1,...,rp +rt –2; whererp is the relative degree of the plant andrt is the relative degree of the system input. This theorem is derived and a complete parameterization of the set of compensators that achieve the prescribed design constraints is formulated.This research was supported in part by NSF Grant No. 921106.     

Immittance-type tabular stability test for 2-D LSI systems based on a zero location test for 1-D complex polynomials

A new algebraic test is developed to determine whether or not a two-variable (2-D) characteristic polynomial of a recursive linear shift invariant (LSI, discrete-time) system is stable (i.e., it does not vanish in the closed exterior of the unit bi-circle). The method is based on the original form of a unit-circle zero location test for one variable (1-D) polynomials with complex coefficients proposed by the author. The test requires the construction of a table, in the form of a sequence of centrosymmetric matrices or 2-D polynomials, that is obtained using a certain three-term recursion, and examination of the zero location with respect to the unit circle of a few associated 1-D polynomials. The minimal set necessary and sufficient conditions for 2-D stability involves one 1-D polynomial whose zeros must reside inside the unit circle (which may be examined before the table is constructed), and one symmetric 1-D polynomial (which becomes available after completing the table) that is required not to have zeros on the unit circle. A larger set of intermediate necessary conditions for stability (which may be examined during the table's construction) are also given. The test compares favorably with Jury's recently improved 2-D stability test in terms of complexity and munerical stability.     

Performance evaluation of optimum combining and maximal ratio combining in the presence of co‐channel interference and channel correlation for wireless communication systems

Antenna diversity is an important technique to combat fading and reduce cochannel interference (CCI). In this paper, we present an analytical approach to derive bit error rate (BER) for Optimum Combining (OC) and Maximal Ratio Combining (MRC) in the presence of CCI. The paper has two parts. In the first part, the analysis of BER for OC with two cochannel interferers and MRC with an arbitrary number of interferers is presented for Marray antenna systems under the assumption that the channels of users are independent of each other. In the second part, the analysis of BER for OC and MRC in the presence of one dominant cochannel interferer is presented for dual antenna systems by assuming that the channels of the desired user or cochannel interferer are correlated. For DPSK signal, an exact BER expression is derived. The work presented here also yields an upper bound for BPSK or QAM signal based on the results of Foschini and Salz (1983).     

Efficient Location and Paging Area Planning in Future Cellular Systems

Efficient resource utilisation in future cellular systems is partly related to the location update and paging operations, which rely on proper planning of location and paging areas, and the application of efficient paging schemes. Important is the design of low complexity planning algorithms that may enable the system to dynamically adapt to new traffic and mobility conditions. In this paper we define and solve versions of the location and paging area planning problems focusing also on algorithms that are applicable in real-time. Thus, they can be used to adapt location and paging areas to traffic and mobility conditions. Starting from a formal definition and an optimal formulation, we solve efficiently by means of a low complexity heuristic, a general version of the location area planning problem. Regarding paging area planning, we provide a low complexity algorithm, under the assumption that the scheme applied falls within the last interaction based paging (LIBP) category. The results presented, and the low cost and complexity induced by the proposed schemes, indicates that the real-time application of the schemes is feasible.     

A hybrid analysis/simulation for ATM performance with application to quality-of-service of CBR traffic

A discrete time queueing model for the performance of an ATM system is analyzed using matrix analytic methods. Time is segmented into slots with each slot equal to the transmission time of one ATM cell. The ATM system is modeled as a single server queue with Markovian arrivals and service time equal to one slot. The arrival process includes as a special case the superposition of on-off sources, possibly heterogeneous. The queueing model is of the M/G/1 type. By exploiting the structure of the M/G/1 type Markov chain, the complexity of the solution to the problem is reduced to only the inversion of a 2×2 matrix irrespective of the size of the Markov chain. This simplification allows us to investigate Constant Bit Rate (CBR) traffic performance (or quality-of-service) issues through a hybrid analysis/simulation approach. Specifically, we analyze the impact of on-off background traffic on the probability of consecutive cell losses, cell delay variation, and traffic shaper or playback buffer underflow and overflow probabilities of CBR traffic sources.     

Fast correlation attacks on certain stream ciphers

Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbert of feedback taps is small (t<10 ifp0.75). The computational complexity of Algorithm A is of orderO(2^ck), wherek denotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthk of the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). On the other hand, for correlation probabilitiesp0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk100 andt10).This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland.     

Time‐varying modeling of a nonstationary signal

In this paper, a method for modeling a nonstationary signal using timevarying parameters by considering that the signal is generated by a linear, timevarying (LTV) system with a stationary white noise input is presented. This method is based on the Wold–Cramer (WC) representation of a nonstationary signal. Because the relationship between the generalized transfer function of an LTV system and the timevarying coefficients of the difference equation of a discretetime system is not addressed so far in the literature, therefore, in this paper a solution to this problem is proposed. A simple relationship between the system generalized transfer function and the timevarying parameters of the system is derived, then an MLS algorithm is developed to solve for the system timevarying parameters. Computer simulation illustrating the effectiveness of our algorithm is presented.     

Gaussian radial basis functions and inner product spaces

An approximation result is given concerning Gaussian radial basis functions in a general inner product space. Applications are described concerning the classification of the elements of disjoint sets of signals, and also the approximation of continuous real functions defined on all of ⁿ using radial basis function (RBF) networks. More specifically, it is shown that an important large class of classification problems involving signals can be solved using a structure consisting of only a generalized RBF network followed by a quantizer. It is also shown that Gaussian radial basis functions defined on ⁿ can uniformly approximate arbitrarily well over all of ⁿ any continuous real functionalf on ⁿ that meets the condition that |f(x)|0 as x.     

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.     

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

Noise considerations for mixed‐signal RF IC transceivers

This paper discusses design tradeoffs for mixedsignal radio frequency integrated circuit (RF IC) transceivers for wireless applications in terms of noise, signal power, receiver linearity, and gain. During air wave transmission, the signal is corrupted by channel noise, adjacent interfering users, image signals, and multipath fading. Furthermore, the receiver corrupts the incoming signal due to RF circuit nonlinearity (intermodulation), electronic device noise, and digital switching noise. This tutorial paper gives an overview of the design tradeoffs needed to minimize RF noise in an integrated wireless transceiver. Fundamental device noise and the coupling of switching noise from digital circuits to sensitive analog sections and their impact on RF circuits such as frequency synthesizers are examined. Methods to minimize mixedsignal noise coupling and to model substrate noise effects are presented.     

Systematic Width-and-Length Dependent CMOS Transistor Mismatch Characterization and Simulation

This paper presents a methodology for characterizing the random component of transistor mismatch in CMOS technologies. The methodology is based on the design of a special purpose chip which allows automatic characterization of arrays of NMOS and PMOS transistors of different sizes. Up to 30 different transistor sizes were implemented in the same chip, with varying transistors width W and length L. A simple strong inversion large signal transistor model is considered, and a new five parameters MOS mismatch model is introduced. The current mismatch between two identical transistors is characterized by the mismatch in their respective current gain factors /, V _TO threshold voltages , bulk threshold parameters , and two components for the mobility degradation parameter mismatch ₀ and _e. These two components modulate the mismatch contribution differently, depending on whether the transistors are biased in ohmic or in saturation region. Using this five parameter mismatch model, an extraordinary fit between experimental and computed mismatch is obtained, including minimum length (1 m) transistors for both ohmic and saturation regions. Standard deviations for these five parameters are obtained as well as their respective correlation coefficients, and are fitted to two dimensional surfaces f(W, L) so that their values can be predicted as a function of transistor sizes. These functions are used in an electrical circuit simulator (Hspice) to predict transistor mismatch. Measured and simulated data are in excellent agreement.     

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.     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

Some results on robust stability of general input-output systems

We consider general input-output systems governed by nonlinear operator equations that relate the system's input, state, and output. The systems under consideration need not be of a feedback type. Assuming that the governing equations depend on a parameterA in a linear space that is allowed to vary in a vicinity N_r(A₀) of a nominal valueA ₀, we study conditions under which the system is stable for each AN_r (A₀), i.e., when the system is robust. By stability we essentially mean that the input-output map is continuous. Depending on the type of continuity used, two concepts of robustness are introduced. The main theorem shows that a certain generalized monotonicity condition imposed on the nominal system combined with a Lipschitz-like condition imposed on the perturbed system guarantees robustness. Moreover, several particular cases of the governing equations are investigated. As examples, we consider (1) a singular system of nonlinear ordinary differential equations (a semistate equation), (2) a feedback system, and (3) a feedback, feedforward system. At the end of this paper some extensions and modifications of the presented theory are discussed.