CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions

We suggest some simple variants of the CBC MAC that enable the efficient authentication of arbitrary-length messages. Our constructions use three keys, K1, K2, K3, to avoid unnecessary padding and MAC any message M {0,1}* using max{1, |M|/n} applications of the underlying n-bit block cipher. Our favorite construction, XCBC, works like this: if |M| is a positive multiple of n then XOR the n-bit key K2 with the last block of M and compute the CBC MAC keyed with K1; otherwise, extend Ms length to the next multiple of n by appending minimal 10 padding ( 0), XOR the n-bit key K3 with the last block of the padded message, and compute the CBC MAC keyed with K1. We prove the security of this and other constructions, giving concrete bounds on an adversarys inability to forge in terms of his inability to distinguish the block cipher from a random permutation. Our analysis exploits new ideas which simplify proofs compared with prior work.     

On Hautus-type conditions for controllability of implicit linear discrete-time systems

Four notions of controllability for general (i.e., possibly nonregular) implicit linear discrete-time systems are considered. Relationships between them are studied. A Hautus-type characterization of all of these notions is also given.This work was performed under the auspices of RP.I.02: Teoria sterowania i optymalizacji ciagych ukadów dynamicznych i procesów dyskretnych.     

Linear systems in a saturated mode and convergence as gain becomes large of asymptotically stable equilibrium points of neural nets

We study solutions of the linear system in a saturated mode

Finite-Memory Systems

Let K be a field, k and n positive integers and let matrices with coefficients in K. For any function

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.     

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

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.     

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.     

Floor acquisition multiple access (FAMA) in single‐channel wireless networks

The FAMANCS protocol is introduced for wireless LANs and adhoc networks that are based on a single channel and asynchronous transmissions (i.e., no time slotting). FAMANCS (for floor acquisition multiple access with nonpersistent carrier sensing) guarantees that a single sender is able to send data packets free of collisions to a given receiver at any given time. FAMANCS is based on a threeway handshake between sender and receiver in which the sender uses nonpersistent carrier sensing to transmit a requesttosend (RTS) and the receiver sends a cleartosend (CTS) that lasts much longer than the RTS to serve as a busy tone that forces all hidden nodes to back off long enough to allow a collisionfree data packet to arrive at the receiver. It is shown that carrier sensing is needed to support collisionfree transmissions in the presence of hidden terminals when nodes transmit RTSs asynchronously. The throughput of FAMANCS is analyzed for singlechannel networks with and without hidden terminals; the analysis shows that FAMANCS performs better than ALOHA, CSMA, and all prior proposals based on collision avoidance dialogues (e.g., MACA, MACAW, and IEEE 802.11 DFWMAC) in the presence of hidden terminals. Simulation experiments are used to confirm the analytical results.     

A Markov modulated fluid queueing system with strict priority

We investigate a Markov modulated fluid queueing system with strict priority. The input process is composed of two fluid flows which are stored in buffer1 and buffer2, respectively. The rates of these fluid flows depend on the current state of a finite state Markov chain. Buffer1 has full assignment of priority (=strict priority) for service and so buffer2 is served at a residual service rate when buffer1 is empty. We explicitly derive the stationary joint distribution of the two buffer contents in the system by a spectral decomposition method. In the case of a twostate Markov chain, the joint distribution is explicitly expressed in terms of the system parameters. Also the joint moments and tail distributions of the two buffer contents are obtained and some numerical examples are presented.     

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.     

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.     

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.     

The CAM-Brain Machine (CBM): Real Time Evolution and Update of a 75 Million Neuron FPGA-Based Artificial Brain

This article introduces ATR's CAM-Brain Machine (CBM), an FPGA based piece of hardware which implements a genetic algorithm (GA) to evolve a cellular automata (CA) based neural network circuit module, of approximately 1,000 neurons, in about a second, i.e. a complete run of a GA, with 10,000 s of circuit growths and performance evaluations. Up to 65,000 of these modules, each of which is evolved with a humanly specified function, can be downloaded into a large RAM space, and interconnected according to humanly specified artificial brain architectures. This RAM, containing an artificial brain with up to 75 million neurons, is then updated by the CBM at a rate of 130 billion CA cells per second. Such speeds should enable real time control of robots and hopefully the birth of a new research field that we call brain building. The first such artificial brain, to be built by ATR starting in 2000, will be used to control the behaviors of a life sized robot kitten called Robokoneko.     

Building video‐on‐demand servers

We have designed and implemented a controllable software architecture for a VideoonDemand (VOD) server. With the proposed software architecture, many system design issues can be investigated. For example, we studied several disk striping schemes in the storage subsystem and examined the impact of the disk striping schemes on the utilization of system resources. In the processing component, we observed that additional concurrent video streams can be supported by using efficient memory interleaving. Buffering with a large memory space in the processing subsystem is a common technique to alleviate the latency variance of accessing different system components. By employing userlevel control and scheduling, the variance can be decreased thereby reducing the resulting buffer space needed for each video stream. In the network subsystem, we adopted a serverdriven approach for investigating MPEG2 video delivery over Asynchronous Transfer Mode (ATM) networks. The VOD server controls the pace of video transmission and reduces the complexity of the client. Since the client has limited buffer space (due to cost considerations), we have reduced the buffer requirement by regulating the transmission based on timing information embedded in the MPEG2 streams. Our research and experimental results are based on a VOD server which is currently under construction. The prototype server is based on an SGI sharedmemory multiprocessor with a mass storage system consisting of RAID3 disk arrays. Using 30 RAID3 disk arrays, preliminary experimental results show that the prototype server can potentially support more than 360 highquality video streams with careful design and coordination of the different system components.     

An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols

We develop an algorithm that allows an ARQ protocol to dynamically optimize the packet size based on estimates of the channel biterrorrate. Our algorithm is particularly useful for wireless and satellite channels where the biterrorrates tend to be relatively high and time variable. Our algorithm uses the acknowledgment history to make estimates of the channel biterrorrate, based on which the optimal packet size can be chosen. We develop a Markov chain model for the analysis of the system, under static channel conditions, and show that the algorithm can achieve close to optimal performance using a history of just 10,000 bits. We also use the Gilbert–Elliott twostate Markov channel to model dynamic channel conditions. We show, through simulation, that the algorithm performs well even under rapidly changing channel conditions. Finally, we discuss a maximum likelihood approach for choosing the packet size, which performs almost optimally but is much easier to implement.