Recent advances in molecular transduction of odorants in the Olfactory Sensory Neurons (OSNs) of the Drosophila Antenna have shown that the odorant object identity is multiplicatively coupled with the odorant concentration waveform. The resulting combinatorial neural code is a confounding representation of odorant semantic information (identity) and syntactic information (concentration). To distill the functional logic of odor information processing in the Antennal Lobe (AL) a number of challenges need to be addressed including 1) how is the odorant semantic information decoupled from the syntactic information at the level of the AL, 2) how are these two information streams processed by the diverse AL Local Neurons (LNs) and 3) what is the end-to-end functional logic of the AL? By analyzing single-channel physiology recordings at the output of the AL, we found that the Projection Neuron responses can be decomposed into a concentration-invariant component, and two transient components boosting the positive/negative concentration contrast that indicate onset/offset timing information of the odorant object. We hypothesized that the concentration-invariant component, in the multi-channel context, is the recovered odorant identity vector presented between onset/offset timing events. We developed a model of LN pathways in the Antennal Lobe termed the differential Divisive Normalization Processors (DNPs), which robustly extract the semantics (the identity of the odorant object) and the ON/OFF semantic timing events indicating the presence/absence of an odorant object. For real-time processing with spiking PN models, we showed that the phase-space of the biological spike generator of the PN offers an intuit perspective for the representation of recovered odorant semantics and examined the dynamics induced by the odorant semantic timing events. Finally, we provided theoretical and computational evidence for the functional logic of the AL as a robust ON-OFF odorant object identity recovery processor across odorant identities, concentration amplitudes and waveform profiles.

Despite recent advances in the understanding of olfactory signal processing [1], [2], [3], [4], [5], robust odorant sensing in complex environments with time-varying odorant identities and concentrations remains an open problem. Particularly, the operational principles of biological and biomimetic olfactory sensors define a new class of sampling problems in which the odorant identity and intensity are multiplicatively coupled into a volatile signal format. We solve the sampling problem by developing the Odorant Encoding Machine (OEM), a biomimetic system based on the latest insights in the architectural organization of the fruit fly early olfactory system. The OEM provides event-driven sensing, reconstruction and robust representation of odorant identity as a combinatorial code of multidimensional spike trains. Like its biological counterpart, OEM 1) decouples odorant identity and concentration encoding via a predictive coding circuit, 2) enables real-time responses to changing odorant input through an on-off circuit, and 3) provides robust representation of odorant identity with a real-time hashing circuit. Furthermore, the OEM is directly applicable for future in silico implementations.

Over the past two decades, substantial amount of work has been conducted to characterize different odorant receptors, neuroanatomy and odorant response properties of the early olfactory system of Drosophila melanogaster. Yet many odorant receptors remain only partially characterized, and the odorant transduction process and the axon hillock spiking mechanism of the olfactory sensory neurons (OSNs) have yet to be fully determined. Identity and concentration, two key characteristics of the space of odorants, are encoded by the odorant transduction process. Detailed molecular models of the odorant transduction process are, however, scarce for fruit flies. To address these challenges we advance a comprehensive model of fruit fly OSNs as a cascade consisting of an odorant transduction process (OTP) and a biophysical spike generator (BSG). We model odorant identity and concentration using an odorant-receptor binding rate tensor, modulated by the odorant concentration profile, and an odorant-receptor dissociation rate tensor, and quantitatively describe the mechanics of the molecular ligand binding/dissociation of the OTP. We model the BSG as a Connor-Stevens point neuron. The resulting spatio-temporal encoding model of the Drosophila antenna provides a theoretical foundation for understanding the neural code of both odorant identity and odorant concentration and advances the state-of-the-art in a number of ways. First, it quantifies on the molecular level the spatio-temporal level of complexity of the transformation taking place in the antennae. The concentration-dependent spatio-temporal code at the output of the antenna circuits determines the level of complexity of olfactory processing in the downstream neuropils, such as odorant recognition and olfactory associative learning. Second, the model is biologically validated using multiple electrophysiological recordings. Third, the model demonstrates that the currently available data for odorant-receptor responses only enable the estimation of the affinity of the odorant-receptor pairs. The odorant-dissociation rate is only available for a few odorant-receptor pairs. Finally, our model calls for new experiments for massively identifying the odorant-receptor dissociation rates of relevance to flies.

We introduce a novel approach for a complete functional identification of biophysical spike-processing neural circuits. The circuits considered accept multidimensional spike trains as their input and comprise a multitude of temporal receptive fields and conductance-based models of action potential generation. Each temporal receptive field describes the spatiotemporal contribution of all synapses between any two neurons and incorporates the (passive) processing carried out by the dendritic tree. The aggregate dendritic current produced by a multitude of temporal receptive fields is encoded into a sequence of action potentials by a spike generator modeled as a nonlinear dynamical system. Our approach builds on the observation that during any experiment, an entire neural circuit, including its receptive fields and biophysical spike generators, is projected onto the space of stimuli used to identify the circuit. Employing the reproducing kernel Hilbert space (RKHS) of trigonometric polynomials to describe input stimuli, we quantitatively describe the relationship between underlying circuit parameters and their projections. We also derive experimental conditions under which these projections converge to the true parameters. In doing so, we achieve the mathematical tractability needed to characterize the biophysical spike generator and identify the multitude of receptive fields. The algorithms obviate the need to repeat experiments in order to compute the neurons' rate of response, rendering our methodology of interest to both experimental and theoretical neuroscientists.

In this paper, we investigate neural circuit architectures encoding natural visual scenes with neuron models consisting of dendritic stimulus processors (DSPs) in cascade with biophysical spike generators (BSGs). DSPs serve as functional models of processing of stimuli up to and including the neuron's active dendritic tree. BSGs model spike generation at the axon hillock level where neurons respond to aggregated synaptic currents. The highly nonlinear behavior of BSGs calls for novel methods of input/output (I/O) analysis of neural encoding circuits and novel decoding algorithms for signal recovery. On the encoding side we characterize the BSG I/O with a phase response curve (PRC) manifold and interpret neural encoding as generalized sampling. We provide a decoding algorithm that recovers visual stimuli encoded by a neural circuit with intrinsic noise sources. In the absence of noise, we give conditions on perfect reconstruction of natural visual scenes. We extend the architecture to encompass neuron models with on-off BSGs with self- and cross-feedback. With the help of the PRC manifold, decoding is shown to be tractable even for a wide signal dynamic range. Consequently, bias currents that were essential in the encoding process can largely be reduced or eliminated. Finally, we present examples of massively parallel encoding and decoding of natural visual scenes on a cluster of graphical processing units (GPUs). We evaluate the signal reconstruction under different noise conditions and investigate the performance of signal recovery in the Nyquist region and for different temporal bandwidths.

We investigate a spiking neuron model of multisensory integration. Multiple stimuli from different sensory modalities are encoded by a single neural circuit comprised of a multisensory bank of receptive fields in cascade with a population of biophysical spike generators. We demonstrate that stimuli of different dimensions can be faithfully multiplexed and encoded in the spike domain and derive tractable algorithms for decoding each stimulus from the common pool of spikes. We also show that the identification of multisensory processing in a single neuron is dual to the recovery of stimuli encoded with a population of multisensory neurons, and prove that only a projection of the circuit onto input stimuli can be identified. We provide an example of multisensory integration using natural audio and video and discuss the performance of the proposed decoding and identification algorithms.

Video Time Decoding Machines faithfully reconstruct bandlimited stimuli encoded with Video Time Encoding Machines. The key step in recovery calls for the pseudo-inversion of a typically poorly conditioned large scale matrix. We investigate the realization of time decoders employing only neural components. We show that Video Time Decoding Machines can be realized with recurrent neural networks, describe their architecture and evaluate their performance. We provide the first demonstration of recovery of natural and synthetic video scenes encoded in the spike domain with decoders realized with only neural components. The performance in recovery using the latter decoder is not distinguishable from the one based on the pseudo-inversion matrix method.

This represents a special session on information theory and neuroscience at ISIT 2011.

We present a general MIMO neural circuit architecture for the encoding of multivariate stimuli in the time domain. The signals belong to the finite space of vector-valued trigonometric polynomials. They are filtered with a linear time-invariant kernel and then processed by a population of leaky integrate-and-fire neurons. We present formal, intuitive, necessary conditions for faithful encoding and provide a perfect recovery (decoding) algorithm. We extend these results to multivariate product spaces and apply them to video encoding with MIMO neural circuits. We demonstrate that our encoding circuits can serve as measurement devices for compressed sensing of frequency sparse signals. Finally, we provide necessary spike density conditions for the decoding of infinite-dimensional vector valued bandlimited functions encoded with MIMO neural circuits.

We investigate architectures for time encoding and time decoding of visual stimuli such as natural and synthetic video streams (movies, animation). The architecture for time encoding is akin to models of the early visual system. It consists of a bank of filters in cascade with single-input multi-output neural circuits. Neuron firing is based on either a threshold-and-fire or an integrate-and-fire spiking mechanism with feedback. We show that analog information is represented by the neural circuits as projections on a set of band-limited functions determined by the spike sequence. Under Nyquist-type and frame conditions, the encoded signal can be recovered from these projections with arbitrary precision. For the video time encoding machine architecture, we demonstrate that band-limited video streams of finite energy can be faithfully recovered from the spike trains and provide a stable algorithm for perfect recovery. The key condition for recovery calls for the number of neurons in the population to be above a threshold value.

In system identification both the input and the output of a system are available to an observer and an algorithm is sought to identify parameters of a hypothesized model of that system. Here we present a novel formal methodology for identifying dendritic processing in a neural circuit consisting of a linear dendritic processing filter in cascade with a spiking neuron model. The input to the circuit is an analog signal that belongs to the space of bandlimited functions. The output is a time sequence associated with the spike train. We derive an algorithm for identification of the dendritic processing filter and reconstruct its kernel with arbitrary precision.

The recovery of (weak) stimuli encoded with a population of Hodgkin-Huxley neurons is investigated. In the absence of a stimulus, the Hodgkin-Huxley neurons are assumed to be tonically spiking. The methodology employed calls for 1) finding an input-output (I/O) equivalent description of the Hodgkin-Huxley neuron and 2) devising a recovery algorithm for stimuli encoded with the I/O equivalent neuron(s). A Hodgkin-Huxley neuron with multiplicative coupling is I/O equivalent with an Integrate-and-Fire neuron with a variable threshold sequence. For bandlimited stimuli a perfect recovery of the stimulus can be achieved provided that a Nyquist-type rate condition is satisfied. A Hodgkin-Huxley neuron with additive coupling and deterministic conductances is first-order I/O equivalent with a Project-Integrate-and-Fire neuron that integrates a projection of the stimulus on the phase response curve. The stimulus recovery is formulated as a spline interpolation problem in the space of finite length bounded energy signals. A Hodgkin-Huxley neuron with additive coupling and stochastic conductances is shown to be first-order I/O equivalent with a Project-Integrate-and-Fire neuron with random thresholds. For stimuli modeled as elements of Sobolev spaces the reconstruction algorithm minimizes a regularized quadratic optimality criterion. Finally, all previous recovery results of stimuli encoded with Hodgkin-Huxley neurons with multiplicative and additive coupling, and deterministic and stochastic conductances are extended to stimuli encoded with a population of Hodgkin-Huxley neurons.

We consider the problem of reconstructing finite energy stimuli from a finite number of contiguous spikes. The reconstructed signal satisfies a consistency condition: when passed through the same neuron, it triggers the same spike train as the original stimulus. The recovered stimulus has to also minimize a quadratic smoothness criterion. We show that under these conditions, the problem of recovery has a unique solution and provide an explicit reconstruction algorithm for stimuli encoded with a population of integrate-and-fire neurons. We demonstrate that the quality of reconstruction improves as the size of the population increases. Finally, we demonstrate the efficiency of our recovery method for an encoding circuit based on threshold spiking that arises in neuromorphic engineering.

Time encoding is a real-time asynchronous mechanism of mapping analog amplitude information into multidimensional time sequences. We investigate the exact representation of analog video streams with a Time Encoding Machine realized with a population of spiking neurons. We also provide an algorithm that perfectly recovers streaming video from the spike trains of the neural population. Finally, we analyze the quality of recovery of a space-time separable video stream encoded with a population of integrate-and-fire neurons and demonstrate that the quality of recovery increases as a function of the population size.

We consider a formal model of stimulus encoding with a circuit consisting of a bank of filters and an ensemble of integrate-and-fire neurons. Such models arise in olfactory systems, vision, and hearing. We demonstrate that bandlimited stimuli can be faithfully represented with spike trains generated by the ensemble of neurons. We provide a stimulus reconstruction scheme based on the spike times of the ensemble of neurons and derive conditions for perfect recovery. The key result calls for the spike density of the neural population to be above the Nyquist rate. We also show that recovery is perfect if the number of neurons in the population is larger than a threshold value. Increasing the number of neurons to achieve a faithful representation of the sensory world is consistent with basic neurobiological thought. Finally we demonstrate that in general, the problem of faithful recovery of stimuli from the spike train of single neurons is ill posed. The stimulus can be recovered, however, from the information contained in the spike train of a population of neurons.

Time encoding is a real-time asynchronous mechanism of mapping amplitude information into a time sequence. We investigate fast algorithms for the recovery of time encoded bandlimited signals and construct an algorithm that has provably low computational complexity. We also devise a fast algorithm that is parameter-insensitive.

A time encoding machine, consisting of a feedback loop containing an adder, an integrator and a Schmitt trigger, encodes amplitude information into a time sequence. We demonstrate how to construct a time decoding machine that perfectly recovers the amplitude information from the time sequence and is trigger parameter insensitive. We derive bounds on the error in signal recovery introduced by the quantization of the time sequence. We compare these with the recovery error introduced by the quantization of the amplitude of the bandlimited signal when irregular sampling is employed. Under Nyquist-type rate conditions, quantization of a bandlimited signal in the time and amplitude domains are shown to be largely equivalent methods of information representation.

In case of natural disasters or intentional attacks, telecommunication networks often get heavily damaged and current resilience schemes have proven to be insufficient for rapid recovery of telecommunication services from catastrophic failures. We consider wireless recovery networks as a strong candidate to provide emergency communication resources in case of such severe network outages, and to preserve, with minimal degradation in quality, the distribution of standard communication services. The focus of our work is on the modeling of wireless shadow networks and study their throughput as a function of the system parameters. We address the design problem of determining the required number of antennas and their most appropriate location for a simple topology. For directional antennas we investigate the expected throughput gain as a function of the beam-width. Furthermore, some interesting topics such as the evaluation of multi-hop constellations and modeling the antenna steering strategies, will be briefly introduced.

A time encoding machine is a real-time asynchronous mechanism for encoding amplitude information into a time sequence. We investigate the operating characteristics of a machine consisting of a feedback loop containing an adder, a linear filter and a Schmitt trigger. We show how to recover, loss-free, the amplitude information of a bandlimited signal from the time sequence.

A key consideration in building differentiated network services is the feasibility of maintaining stable and consistent service level agreements across multiple networks where allocations are made only on the edges. To investigate this, we consider a game theoretic model of capacity provisioning in a differentiated services Internet. The players are one raw-capacity seller per network, one broker per service per network, and users, to play the roles of wholesellers, retailers and end users respectively in a two-tier wholeseller/retailer market. Based on this model, we are able to construct an explicit necessary and sufficient condition for the stability of the game, which determines the sustainability of a given set of SLA configurations among peering ISP. The analytical results are validated with simulations of user and broker dynamics, using distributed progressive second price auctions as the spot market mechanism in a scenario with three interconnected networks, and two services.

This paper presents a decentralized auction-based approach to pricing of edge-allocated bandwidth in a differentiated services Internet. The players in our network economy model are one raw-capacity seller per network, one broker per service per network, and users, to play the roles of whole-sellers, retailers, and end-buyers, respectively, in a two-tier wholeseller/retailer market, which is best interpreted as a "sender-pay" model. With the progressive second price auction mechanism as the basic building block, we conduct a game theoretic analysis, deriving optimal strategies for buyers and brokers, and show the existence of networkwide market equilibria. In addition to pricing, another key consideration in building differentiated network services is the feasibility of maintaining stable and consistent service level agreements across multiple networks where demand-driven dynamic allocations are made only at the edges. Based on the proposed game-theoretic model, we are able to construct an explicit necessary and sufficient condition for the stability of the game, which determines the sustainability of any set of service level agreement configurations between Internet service providers. These analytical results are validated with simulations of user and broker dynamics, using the distributed progressive second price auction as the spot market mechanism in a scenario with three interconnected networks, and two services based on the proposed standard expedited forwarding and assured forwarding per-hop behavior.

ATM switching platforms are well suited for transporting multimedia streams with quality-of-service (QOS) requirements. This paper describes the system design of a high performance connection management system for xbind, a flexible open programmable signaling system for ATM switching platforms. The latency and throughput of call processing is improved by caching, message aggregation, and processing of requests in parallel. Using a set of general purpose UNIX work stations, we are able to attain a maximum throughput of close to 600000 call operations/h (setup and delete) with an average call setup time of 85 ms. With a low traffic load of 3600 call operations/h, an average call setup latency of 11 ms can be obtained. The system is adaptive. By adjusting various control parameters, the connection manager(s) can be dynamically configured to trade off between throughput and call setup time.

Recent advances in distributed systems and transportable software and increasing demand for better quality-of-service (QOS) control in multiservice networks are driving a re-examination of network software architectures. We established the COMET Group (Control Management and Telemedia) at Columbia University's Center for Telecommunications Research to provide a comprehensive understanding of network software architecture of the 1990s and beyond. In this paper, we present an overview of our activities, focusing on new research initiatives, international forum participation and on-going research projects. Collectively, these activities shape our vision of a new era driven by open programmable networking.

The configuration of virtual path (VP) connection services is expected to play an important role in the operation of large-scale asynchronous transfer mode (ATM) networks. A major research challenge is to understand the fundamental tradeoff between the network call throughput and the processing load on the signaling system and to provide an algorithm for VP capacity allocation that achieves an optimal network operating point while guaranteeing quality of service (QoS) at the call level and satisfies a priori bounds on the processing load of the call processors. We present a taxonomy of previous approaches to the problem and identify their strengths and weaknesses. Based on these observations, we provide an algorithm for the VP capacity allocation problem that satisfies nodal constraints on the call processing load and blocking constraints for each source-destination (SD) pair. The algorithm maximizes the network revenue under the above set of constraints and is parameterized by the number of traffic classes in the network, the method of presentation of networking resources, the admission control policy used in every link and VP, and the network routing scheme. Finally, we apply the algorithm to three sample networks and study several of its performance characteristics. In one case, we applied the calculated VP distribution to the Xunet ATM testbed and verified experimentally the predicted performance.

A framework for studying ATM network QOS mapping between various levels in the information transport protocol stack and a platform for evaluating the mapping rules by performing concurrent network and application level measurements of QOS are presented. An empirical loss mapping rule between the application (frame) level and network (cell) level is given. The rule was tested using two 10 minute motion JPEG video clips and a 30 minute MPEG-2 VBR video clip under 55 different network load conditions and gives results within a 3% error margin.

Consider an aggregate arrival process A/sup N/ obtained by multiplexing N on-off sources with exponential off periods of rate /spl lambda/ and subexponential on periods /spl tau//sup on/. For this process its activity period I/sup N/ satisfies P[I/sup N/>t]/spl sim/(1+/spl lambda/E/spl tau//sup on/)/sup N-1/P[/spl tau//sup on/>t] as t/spl rarr//spl infin/ for all sufficiently small /spl lambda/. When N goes to infinity, with /spl lambda/N/spl rarr//spl Lambda/, A/sup N/ approaches an M/G//spl infin/ type process, for which the activity period I/sup /spl infin//, or equivalently a busy period of an M/G//spl infin/ queue with subexponential service requirement /spl tau//sup on/, satisfies P[I/sup /spl infin//>t]/spl sim/e/sup /spl Lambda/Er(on)/P[/spl tau//sup on/>t] as t/spl rarr//spl infin/. For a simple subexponential on-off fluid flow queue we establish a precise asymptotic relation between the Palm queue distribution and the time average queue distribution. Further, a queueing system in which one on-off source, whose on period belongs to a subclass of subexponential distributions, is multiplexed with independent exponential sources with aggregate expected rate Ee/sub t/, is shown to be asymptotically equivalent to the same queueing system with the exponential arrival processes being replaced by their total mean value Ee/sub t/. For a fluid queue with the limiting M/G//spl infin/ arrivals we obtain a tight asymptotic lower bound for large buffer probabilities. Based on this bound, we suggest a computationally efficient approximation for the case of finitely many subexponential on-off sources. The accuracy of this approximation is verified with extensive simulation experiments.

Guided by the empirical observation that real-time MPEG video streams exhibit both multiple time scale and subexponential characteristics, we construct a video model that captures both of these characteristics and is amenable to queueing analysis. We investigate two fundamental approaches for extracting the model parameters: using sample path and second-order statistics-based methods. The model exhibits the following two canonical queueing behaviors. When strict stability conditions are satisfied, i.e., the conditional mean of each scene is smaller than the capacity of the server, precise modeling of the interscene dynamics (long-term dependency) is not essential for the accurate prediction of small to moderately large queue sizes. In this case, the queue length distribution is determined using quasistationary (perturbation theory) analysis. When weak stability conditions are satisfied, i.e., the conditional mean of at least one scene type is greater than the capacity of the server, the dominant effect for building a large queue size is the subexponential (long-tailed) scene length distribution. In this case, precise modeling of intrascene statistics is of secondary importance for predicting the large queueing behavior. A fluid model, whose arrival process is obtained from the video data by replacing scene statistics with their means, is shown to asymptotically converge to the exact queue distribution. Using the transition scenario of moving from one stability region to the other by a change in the value of the server capacity, we synthesize recent queueing theoretic advances and ad hoc results in video modeling, and unify a broad range of seemingly contradictory experimental observations found in the literature. As a word of caution for the widespread usage of second-order statistics modeling methods, we construct two processes with the same second-order statistics that produce distinctly different queueing behaviors.

In noncooperative networks users make control decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. Nash equilibria are generically inefficient and exhibit suboptimal network performance. Focusing on routing, a methodology is devised for overcoming this deficiency, through the intervention of the network manager. The manager controls part of the network flow, is aware of the noncooperative behavior of the users and performs its routing aiming at improving the overall system performance. The existence of maximally efficient strategies for the manager, i.e., strategies that drive the system into the global network optimum, is investigated. A maximally efficient strategy of the manager not only optimizes the overall performance of the network, but also induces an operating point that is efficient with respect to the performance of the individual users (Pareto efficiency). Necessary and sufficient conditions for the existence of a maximally efficient strategy are derived, and it is shown that they are met in many cases of practical interest. The maximally efficient strategy is shown to be unique and it is specified explicitly.

We consider a multiuser network that is shared by noncooperative users. Each user sets up virtual paths that optimize its own selfish performance measure. This measure accounts for the guaranteed call level quality of service, as well as for the cost incurred for reserving the resource. The interaction among the user strategies is formalized as a noncooperative game. We show that the game has a unique Nash equilibrium and that it possesses a certain fairness property. We investigate the dynamics of this game and prove convergence to the Nash equilibrium of both a Gauss-Seidel scheme and a Jacobi scheme. We extend our study to various general network topologies. Finally, the formal results and some extensions thereof are tested by emulating the schemes on an experimental network.

The design and implementation of the transport layer of a native ATM (asynchronous tranfer mode) protocol stack and its embedding into an overall architecture that provides end-to-end quality of service (QOS) is presented. Within this architecture, the typical transport functionalities are enlarged with QOS monitoring and adaptation mechanisms. A QOS-based API (application programming interface) is proposed that shields application programmers from the complexity of QOS management and control. Both unicast and multicast connections supporting interactive multimedia applications are considered.

The Binding Architecture is an open architecture for building multimedia networks that must guarantee quality of service (QOS). We explore the notion of a service in the Binding Architecture and propose a conceptual model for building scalable multimedia distribution services based on it. We begin first by examining the relation between resources, their abstractions and the services that can be built from them and use this to derive a general model for binding. Based on this model, we identify a general set of capabilities required for building any multimedia distribution service. We also describe how these capabilities can be incorporated into our view of the service creation process. Finally, we augment our discussion with the description of an example service which we have developed using this paradigm.

We provide an algorithm for the VP distribution problem that satisfies nodal constraints on the processing load and blocking constraints for each source-destination pair. The algorithm maximizes the network revenue under the above set of constraints and is independent of the number of traffic classes in the network, the method of representation of networking resources, the admission control policy used in every link and VP, and the network routing scheme. We apply the algorithm to the Xunet ATM testbed and study several of its performance characteristics.

For an ATM multiplexer we develop a recursive asymptotic expansion method for approximating the queue length distribution and investigate the radius of convergence of the queue asymptotic expansion series. The analysis focuses on "small" to "moderate" buffer sizes under the conditions of strictly stable multiple time scale arrivals. For a class of examples we analytically determine the radius of convergence using methods of linear operator theory. We also give general sufficient conditions under which the radius converges to zero; this shows roughly what situations have to be avoided for the proposed method to work well. We combine the asymptotic expansion method with the EB approximation, and give an approximation procedure for the buffer probabilities for all buffer ranges. The procedure is tested on extensive numerical examples. We suggest this procedure for efficient admission control in ATM networks.

Traditional computer networks were typically designed with system-wide optimization in mind. In noncooperative networks users make control decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. Nash equilibria exhibit, in general, suboptimal network performance. Focusing on routing, a methodology is devised for overcoming this deficiency, through the intervention of the network manager. The manager controls part of the network flow, is aware of the noncooperative behavior of the users and performs its routing aiming at improving the overall system performance. The existence of maximally efficient strategies for the manager, i.e., strategies that drive the system into the global network optimum, is investigated. Necessary and sufficient conditions for the existence of a maximally efficient strategy are derived. The maximally efficient strategy are shown to be unique and it is specified explicitly.

A conceptual framework, called the binding model, for the creation, deployment and management of multimedia services on ATM-based broadband networks with end-to-end quality-of-service (QoS) guarantees is presented. The key function of the associated binding architecture is to provide an open programmable environment that facilitates the easy creation of flexible services. We describe the implementation of a prototype binding architecture called xbind as a middleware toolkit for building open programmable ATM networks. Finally, we present our initial experiences with experimenting and deploying xbind over an ATM testbed and highlight some of the lessons learned.

An approach to sensor configuration, installation, and activation for real-time monitoring of broadband networks for performance management is presented. An objective-driven measurement strategy for establishing the dynamic and statistical databases of the network is described. Objective driven monitoring allows the activation of sensors for data collection and abstraction based on a set of objectives. The objectives are derived from the quality of service requirements for real-time traffic control and operator submitted queries. The methodology of objective-driven monitoring for selective activation of sensors is implemented as a set of rules in the knowledge base of the monitor.

Considers a multi-user network that is shared by noncooperative users. Each user sets up virtual paths that optimize its own, selfish, performance measure. This measure accounts for both the guaranteed call level quality of service, as well as for the cost incurred for reserving the resource. The interaction between the user strategies is formalized as a game. The authors show that this game has a unique Nash equilibrium, and that it possesses a certain fairness property. They investigate the dynamics of this game, and prove convergence to the Nash equilibrium of both a Gauss-Seidel scheme and a Jacobi scheme. They extend their study to various general network topologies.

We propose a distributed security architecture for incorporation into object oriented distributed computing systems, and in particular, into OMG's CORBA based object architectures. The primary objective of the security architecture is to make CORBA resilient to both component failures and malicious attacks. The core of the architecture is the notion of secure ORB node-an ORB node enhanced with "pluggable" system security objects interacting through generic security service APIs. System security objects coupled with protocols among them facilitate creation and management of clients, objects, and security information. Security services addressed in the paper include, but are in no way limited to, client/object authentication, access control, and integrity and confidentiality protections.>

A wide variety of deflection routing strategies using packet state information are compared in terms of delay performance using a toroidal network with uni-directional links. It is found that deflection strategies based on packet age, the number of deflections experienced or path length prediction work equally well and are superior to random deflection. Strategies based on source to destination shortest path distance or current location to destination shortest path distance were significantly inferior to random deflection. This ranking was found to hold with or without the inclusion of nodal input buffers.

The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by K users is investigated. The performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. Previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. To overcome this difficulty, a more general approach to study the existence of Nash equilibria for decentralized control schemes is introduced. This approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. For the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of K interdependent linear programs. Employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. Brouwer's theorem implies, then, that the best reply function has a fixed point.

An open architecture that achieves seamless binding between networking and multimedia devices is proposed. The building blocks of the binding architecture consist of a set of interfaces, methods and primitives. The former abstract the functionalities of multimedia networking devices and are realized as objects organized into a binding interface base. The methods and primitives are invoked for implementing binding applications. The binding architecture is embedded into a reference model for multimedia networking architectures that supports a clean separation between binding interfaces and binding algorithms. Communication between the objects realizing the binding interfaces is supported by CORBA. Public interfaces in the binding interface base are specified using CORBA IDL. The architecture is illustrated with a simple connection management algorithm and an example of computational binding.

In noncooperative networks users make control decisions that optimize their individual performance measure. Focusing on routing, two methodologies for architecting noncooperative networks are devised, that improve the overall network performance. These methodologies are motivated by problem settings arising in the provisioning and the run time phases of the network. For either phase, Nash equilibria characterize the operating point of the network. The goal in the provisioning phase is to allocate link capacities that lead to systemwide efficient Nash equilibria. The solution of such design problems is, in general, counterintuitive, since adding link capacity might lead to degradation of user performance. For systems of parallel links, it is shown that such paradoxes cannot occur and that the optimal solution coincides with the solution in the single-user case. Extensions to general network topologies are derived. During the run time phase, a manager controls the routing of part of the network flow. The manager is aware of the noncooperative behavior of the users and makes its routing decisions based on this information while aiming at improving the overall system performance. We obtain necessary and sufficient conditions for enforcing an equilibrium that coincides with the global network optimum, and indicate that these conditions are met in many cases of interest.>

This paper presents a solution to provide connectivity between a general-purpose workstation and a public broadband-ISDN trial system. The solution involves the creation of a low-level network layer software which is transparent to the existing TCP/IP protocol stack supported by the workstation operating system. This solution allows existing applications to communicate over the B-ISDN without modification, and future applications to be developed efficiently. Network management capability is also provided at the interface software to enable future research on terminal-end B-ISDN management using a standard network management framework.

A scalable and reusable emulator was designed and implemented for studying the behavior of SS7 networks. The emulator design was largely based on public domain software. It was developed on top of an environment supported by PVM, the Parallel Virtual Machine, and managed by OSIMIS/spl minus/the OSI Management Information Service platform. The emulator runs on top of a commercially available ATM LAN interconnecting engineering workstations. As a case study for evaluating the emulator, the behavior of the Singapore National SS7 Network under fault and unbalanced loading conditions was investigated.>

Just as broadband networks will enable user-to-user communications to extend from textural services to those employing multimedia, they will also enable a management environment that can take advantage of increased bandwidth and multimedia technology. The fundamental advances incorporated in such an environment can provide efficient solutions to the problem of information management. To establish this environment, the authors tackle the fundamental problems of observability and controllability of broadband networks. A virtual world provides a next-generation network management interface through which a user can observe and interact with the network directly in real time. The system that the authors are developing uses a 3D virtual world as the user interface for managing a large gigabit ATM network. It provides the capability for experimentation in all aspects of network transport, control and management.>

The application of probabilistic reasoning to fault diagnosis in linear lightwave networks (LLNs) is investigated. The LLN inference model is represented by a Bayesian network (or causal network). An inference algorithm is proposed that is capable of conducting fault diagnosis (inference) with incomplete evidence and on an interactive basis. Two belief updating algorithms are presented which are used by the inference algorithm for performing fault diagnosis. The first belief updating algorithm is a simplified version of the one proposed by Pearl (1988) for singly connected inference models. The second belief updating algorithm applies to multiply connected inference models and is more general than the first. The authors also introduce a t-fault diagnosis system and an adaptive diagnosis system to further reduce the computational complexity of the fault diagnosis process.>

A framework for joint scheduling and admission control in broadband switching systems based on a principle of separation between these two levels of control is developed. It is shown that an admission control strategy can be tailored to a particular mix of traffic by using high-level information from the scheduler. This principle is presented in the context of asynchronous time-sharing (ATS) in which explicit guarantees of cell-level and call-level quality of service (QOS) are given to several traffic classes. The separation principle allows the formulation of an optimal admission control policy that maximizes the expected system utility and maintains all QOS guarantees. Several heuristic admission control policies are considered and compared with the optimal policy. The admissible load region is introduced as a means of quantifying the capacity of a switch under the QOS constraints at the cell and call levels. Numerical calculations for a single MAGNET II switching node carrying two classes of real-time traffic are used to illustrate the effects of different scheduling and admission control policies on both the expected utility and the admissable load region.>

A proactive distributed cooperative control algorithm for resource scheduling of broadband networks based on asynchronous time sharing is presented. The problem setting for distributed, cooperative proactive scheduling is described. An overview of the distributed cooperative algorithm is presented. The general control principles underlying the effectiveness of the cooperative algorithm are discussed. The formal details of the distributed cooperative algorithm and its underlying single noise scheduling algorithm are considered. Simulation results comparing the distributed cooperative algorithm with other networkwide scheduling algorithms are reported.>

A joint scheduling and admission control algorithm is presented for Asynchronous Time-Sharing (ATS)-based switching nodes carrying real-time traffic. Systems based on ATS guarantee quality of service, at both the levels of cells and calls, for three well-defined traffic classes. A mechanism is outlined by which an admission control strategy can be tailored to a particular mix of traffic classes. A mechanism is outlined by which an admission control strategy can be tailored to a particular mix of traffic by making use of high-level information from the scheduler. This mechanism is based on a principle of separation between scheduling and admission control. A linear programming formulation is used to find the admission control policy which will maximize the expected system utility while maintaining the guaranteed quality of service. The admissible load region is introduced as a means of quantifying the capacity of a switch under the QOS constraints at the cell and call levels. Numerical calculations for a single MAGNET II switching node carrying two classes of real-time traffic are used to illustrate the effects of different scheduling and admisssion control policies on both the expected utility and the admissible load region.

Admission control is a tool in the management of the grade of service provided by the network to ongoing connections and new sessions. When the admission decision is based on the clipping loss, the authors model the node load by a Markov modulated point process and show that, if the two conjectures introduced hold, the optimum admission control that guarantees quality for all sessions in the node is of a threshold type. If the conjectures fail to hold, then the result holds for Poisson arrivals. The authors characterize the threshold and show that for the admission decision, the admission controller needs to compare the arrival rate matrices to the threshold. This threshold is based on the partial order on the lattice of arrival rate matrices.>

Packet blocking in the multiclass M/G/1/B queueing systems is studied by rate conservation methods. It is assumed that two classes of traffic are accessing the queue. Recursive forms are obtained for the packet loss probability and conditional probability of consecutive blocking for class one traffic, with the other class modeling the background traffic. The latter characterizes the distribution of the number of consecutively class one packets blocked. It is shown that these quantities depend essentially on the joint distribution of the queue length and the residual service time. This joint distribution is recursively computed by analyzing, through rate conservation principles, the embedded queue at arrival times.>

A real-time scheduling algorithm for Asynchronous Time Sharing based switching nodes is presented.Three classes of traffic sources are considered to load the swit thing nodes: real-time video sources with guaranteed maximum end-to-end delay S1 for all cells; realtime voice sources with guaranteed end-to-end delay SII, c% cell loss rate and average gap length q; and data traffic with guaranteed minimum average throughput and maximum average time delay.The proposed algorithm is compared with other known algorithms in terms of complexity in implementation, knowledge structures and performance.Our investigations are supported throughout by simulation results.

Whether or not the introduction of traffic classes improves upon the performance of ATM networks is discussed within the framework provided by a class of networks that guarantees quality of service. To provide a meaningful comparison the authors define the concept of a schedulable region, a region in the space of loads for which the quality of service is guaranteed. The authors show the dependence of the schedulable region on the scheduling algorithm employed, quality of service parameters, and traffic statistics. An efficient real-time scheduling algorithm is introduced that substantially increases the schedulable region without incurring prohibitive complexity costs. The schedulable region associated with this algorithm is compared with the ones generated by the static priority scheduling algorithm and a variant of the minimum laxity threshold algorithm. The size and shape of the schedulable region is explored by means of simulations.>

Real-time traffic measurements on MAGNET II, an integrated network testbed based on asynchronous time sharing, are reported. The quality of service is evaluated by monitoring the buffer-occupancy distribution, the packet time-delay distribution, the packet loss, and the gap distribution of the consecutively lost packets. The experiments show that both time-delay and buffer-occupancy distributions of multiplexed video sources display a marked bimodal behavior, which does not seem to depend on the buffer size. The reliance of the network designer on traffic sources that do not exhibit substantial correlations can lead to implementations with serious congestion problems. For asynchronous-time-sharing-based networks with different traffic classes, the impact of a traffic class on the performance of the other classes tends to be diminished when compared to single-class-based asynchronous transfer mode (ATM) networks.>

MAGNET II is a testbed for integrated networks. It was designed and implemented based on requirements of real-time network management and control. Quality-of-service requirements explicitly appear in the design specifications of the network on the media access level. Switching is based on the concept of asynchronous time sharing. The core of the network distinguishes between three traffic classes. The quality of service of these classes is monitored and controlled by the traffic-control architecture of the network. Monitoring is supported by observation units distributed throughout the system. The main network resources, switching bandwidth, communication bandwidth, and buffer space, are observable and controllable.>

A class of ADPCM speech predictor architectures that are based on models of the human auditory system is developed. The transfer function of the predictor is of the pole/zero type with fixed poles and adaptive zeros. Choice of the fixed poles is made using auditory models, in contrast with the standard trial-and-error techniques. A state-space formulation of the prediction filter provides the connection between the standard fixed pole/adaptive zero models and the transversal filter model of the auditory system. Two realizations of the prediction filter are described: a parallel realization, which directly uses the auditory models, and a cascade realization, which allows direct manipulation of the poles and zeros of the filter. The gradient search method is applied to identify the filter coefficients.>

Load-balancing algorithms for Jacksonian networks are derived. The state of the network is represented by the total number of packets for which the source has not yet received an acknowledgement. The networks studied are subject to state-independent routing and state-dependent and state-independent flow control. The objective is to maximize the throughput of the network so that the end-to-end expected packet time delay does not exceed an upper bound. The optimal flow control is shown to be of a window type, while the routing policy balances the traffic inside the network. Several load-balancing algorithms are evaluated.>

A two dimensional, linear state-space model of the cochlea of the human ear, the receiver side of the speech communications paradigm, is investigated. The ear is viewed as a serial to parallel converter of information: the input to the cochlear model is a time dependent single channel signal, whereas the output of the cochlear model is a spatially discretized representation of the displacement of the basilar membrane from its rest position. A characterization of the system response of the cochlear filters is given. An approach to detecting known signals at the input using only the information available at the output based upon methods akin to 'beamforming' for a linear array is presented. The detector threshold is set using an adaptive technique that uses spatially local information. Simulation results showing the capabilities of the detection system for processing speech signals are also discussed.>

SPEED is a software environment that provides facilities for creating networks of programs on a single or multiple processors. A mouse-driven user interface is provided for creating and controlling these networks. Routines and utilities are included for the programmer to develop high-throughput communications among the processes. Program and data control parameters can be set by the user or initialized automatically. An example of speech processing using models of the human auditory system is given.

Fundamental issues arising in the design and implementation of architectures and protocols for integrated local area networks (ILAN's) supporting video, voice, graphics, data, and facsimile, are addressed, and open questions are identified. To characterize the performance of ILAN's, a set of performance evaluation guidelines is established. A class of conceptual solutions for ILAN's is proposed, and its expected performance is obtained by means of simulation. The class includes priority assignment schemes, parametrized sequential and simultaneous scheduling algorithms, and centralized and decentralized access control mechanisms. Our analysis, based upon simulations, shows that the bandwidth freed up by the video and voice calls during periods of little movement in the images and silence periods in the speech signals can be efficiently utilized for graphics and data transmission. The optimal priority mechanism among the different user classes depends on the traffic mix. Finally, it is argued that additional experimentation providing empirical data is imperative for understanding the real-time behavior of ILAN's. Consequently, a network testbed (NTB) called MAGNET is proposed for evaluating the performance of the proposed theoretical systems. It consists of an adaptive ILAN whose mediaaccess protocol is controlled by an Expert System.

MAGNET is a Network Testbed (NTB) designed to evaluate the performance of local area network architectures and protocols supporting integrated services such as televideo, video conferencing, telephone, computer communication, and facsimile. The integrated local area network (ILAN) presented in this paper has been designed to support the research activities intended for MAGNET. An active slotted ring topology was chosen to implement adaptive sequential-type access mechanisms that are a function of the network loading. The ILAN is based on fiber optic technology with wavelength-division multiplexing of two 100 Mbit/s channels. The media-access protocol provides higher levels with the capability of implementing two modes of operation referred to as circuit-switching, and packet-switching modes, respectively. Provisions have also been made for implementing simultaneous scheduling as well as centralized and decentralized access control schemes. Finally, the reconfigurable structure of the network testbed enables the study of the reliability and availability of ILAN's.

The problem of optimal flow control of an M/M/m queuing system in equilibrium is investigated.The rate of the Polsson input process to the system is controlled so as to maximize the throughput of the queue subject to a constraint that the average time delay not exceed a specified value T. The optimum control is shown to be a window type mechamsm (bang-bang control).The input rate ), and the window size L, the maximum number of packets in transit w~thm the system, are determined as explicit functions of the maximum tolerated time delay T, the maximum input capacity to the queue c, the service rate ~, and the number of servers m.The throughput as a function of the Ume delay for the M/M/m system is then discussed.

A study of the design requirements of the data link control protocol leads us to consider a throughput time delay criterion as a performance measure for optimal flow control of computer communication networks. A closed network model consisting of a\cdot /M/1queuing system (the receiver node) controlled by an exponential queuing system with variable rate (the source node) is considered. The flow control maximizing the throughput of the M/M/1 queuing system in equilibrium under a bounded average time delay criterion is shown to be a window flow control mechanism. The window sizeLcan be easily derived from the maximum tolerated average time delayTand the maximum offered loadc. The dependence of the maximum throughput on the average time delay is also analyzed.

The problem of optimal control of a M/M/m queueing system is investigated. As in the M/M/l case the optimum control is shown to be a window type mechanism. The window size L depends on the maximum allowable time delay T and can be explicitly computed. The throughput time delay function of the M/M/m system is briefly discussed.