On the large deviations approximation for the stationary distribution of skip-free regulated queueing networks

Large deviations papers like that of Ignatyuk et al. [Russ. Math. Surv. 49 (1994) 41–99] have shown that asymptotically, the stationary distribution of homogeneous regulated networks is of the form

with the coefficient being different in various “boundary influence domains” and also depending on some of these domains on n. In this paper, we focus on the case of constant exponents and on a subclass of networks we call “strongly skip-free” (which includes all Jackson and all two-dimensional skip-free networks). We conjecture that an asymptotic exponent is constant iff it corresponds to a large deviations escape path which progresses gradually (from the origin to the interior) through boundary facets whose dimension always increases by one. Solving the corresponding large deviations problem for our subclass of networks leads to a family of “local large deviation systems” (LLDSs) (for the constant exponents), which are expressed entirely in terms of the cumulant generating function of the network. In this paper, we show that at least for “strongly skip-free” Markovian networks with independent transition processes, the LLDS is closely related to some “local boundary equilibrium systems” (LESs) obtained by retaining from the equilibrium equations only those valid in neighborhoods of the boundary.

Since asymptotic results require typically only that the cumulant generating function is well-defined over an appropriate domain, it is natural to conjecture that these LLDSs will provide the asymptotic constant exponents regardless of any distributional assumptions made on the network.

Finally, we outline a practical recipe for combining the local approximations to produce a global large deviations approximation , with the coefficients K_j determined numerically.     

Shortest distance and reliability of probabilistic networks

When the “length” of a link is not deterministic and is governed by a stochastic process, the “shortest” path between two points in the network is not necessarily always composed of the same links and depends on the state of the network. For example, in communication and transportation networks, the travel time on a link is not deterministic and the fastest path between two points is not fixed. This paper presents an algorithm to compute the expected shortest travel time between two nodes in the network when the travel time on each link has a given independent discrete probability distribution. The algorithm assumes the knowledge of all the paths between two nodes and methods to determine the paths are referenced.In reliability (i.e. the probability that two given points are connected by a path) computations, associated with each link is a probability of “failure” and a probability of “success”. Since “failure” implies infinite travel time, the algorithm simultaneously computes reliability. The paper also discusses the algorithm's capability to simultaneously compute some other performance measures which are useful in the analysis of emergency services operating on a network.     

Overload effects and their prevention

The so-called “thrashing effect”, well known from virtual storage, but also reported from data-base systems and packet switching networks, has turned out to be a common phenomenon of large systems with concurrent processing. It simply means that beyond a saturation point an increase of the load (e.g. number of jobs) leads to a (sometimes sudden) decrease in performance (e.g. throughput). With growing size and complexity of computer systems and the general trend towards distribution, overload phenomena of different origin can interfere and superimpose mutually, resulting in a composite overload effect that can hardly be broken down into its constituents. Because the complexity of such systems defies detailed modeling, it is more appropriate to look at those systems in a more macroscopic, behavioral way, considering only the two externally measurable variables “load” and “throughput”. The resulting abstraction from internal details can smooth the way to a more general treatment and application. The article deals with such overload phenomena and their prevention in a general way using a control-theoretic approach. Special emphasis is placed on dynamic behavior, where load characteristics are changing with time, making feedback mechanisms necessary. The problem is approached as a dynamic optimum search problem for which different algorithms are presented and compared by simulation.     

Population Learning in a Model with Random Payoff Landscapes and Endogenous Networks

Population learning in dynamic economies with endogenous network formation has been traditionally studied in basic settings where agents face quite simple and predictable strategic situations (e.g. coordination). In this paper, we start instead to explore economies where the payoff landscape is very complicated (rugged). We propose a model where the payoff to any agent changes in an unpredictable way as soon as any small variation in the strategy configuration within its network occurs. We study population learning where agents: (i) are allowed to periodically adjust both the strategy they play in the game and their interaction network; (ii) employ some simple criteria (e.g. statistics such as MIN, MAX, MEAN, etc.) to myopically form expectations about their payoff under alternative strategy and network configurations. Computer simulations show that: (i) allowing for endogenous networks implies higher average payoff as compared to static networks; (ii) populations learn by employing network updating as a “global learning” device, while strategy updating is used to perform “fine tuning”; (iii) the statistics employed to evaluate payoffs strongly affect the efficiency of the system, i.e. convergence to a unique (multiple) steady-state(s); (iv) for some class of statistics (e.g. MIN or MAX), the likelihood of efficient population learning strongly depends on whether agents are change-averse in discriminating between options associated to the same expected payoff.     

White color tracking adjustment in television receivers using neural networks

This paper discusses the application of neural networks to the white tracking adjustment of television receivers during production. High quality levels of tracking for the color temperature 8000 K were obtained with four-layer (7-10-10-6) network. The network input set consists of brightness level, high and low luminance levels, and “x” and “y” coordinates on the chromaticity diagram for both high and low luminance. The network output set consists of recommended adjustments for brightness, red, green, and blue cutoffs, and green and blue gains. The network was trained using the back-propagation algorithm. The experimental study has shown that the application of neural networks has reduced the testing time which has led to an increase in production rate.     

Asymptotic approximations and bottleneck analysis in product form queueing networks with large populations

Asymptotic approximations are constructed for the performance measures of product form queueing networks consisting of single server, fixed rate nodes with large populations. The approximations are constructed by applying singular perturbation methods to the recursion equations of Mean Value Analysis. Networks with a single job class are studied first to illustrate the use of perturbation techniques. The leading term in the approximation is related to bottleneck analysis, but fails to be accurate if there is more than one bottleneck node. A uniform approximation is constructed which is valid for networks with many bottleneck nodes. The accuracy of the uniform approximation is demonstrated for both small and large population sizes. Next, multiclass networks are considered. The leading term in the asymptotic approximation is again related to bottleneck analysis but fails to be valid across “switching surfaces”. Across these the bottleneck nodes of the network change as a function of the fraction of jobs in the different job classes. A boundary layer correction is constructed near the switching surfaces which provides an asymptotic connection across the switching surfaces. Numerical examples are presented to demonstrate the accuracy of the results. We illustrate the asymptotic approach on some simple networks and indicate how to treat more complicated problems.     

Limitations of multi-layer perceptron networks - steps towards genetic neural networks

In this paper we investigate multi-layer perceptron networks in the task domain of Boolean functions. We demystify the multi-layer perceptron network by showing that it just divides the input space into regions constrained by hyperplanes. We use this information to construct minimal training sets. Despite using minimal training sets, the learning time of multi-layer perceptron networks with backpropagation scales exponentially for complex Boolean functions. But modular neural networks which consist of independentky trained subnetworks scale very well. We conjecture that the next generation of neural networks will be genetic neural networks which evolve their structure. We confirm Minsky and Papert: “The future of neural networks is tied not to the search for some single, universal scheme to solve all problems at once, bu to the evolution of a many-faceted technology of network design.”     

On the feasibility of IEEE 802.11 multi-channel multi-hop mesh networks

Several scientific works have considered the possibility to build Wireless Mesh Networks (WMN) using multi-channel IEEE 802.11 architectures. At the basis of these works is the notion of “non-overlapping” channels, i.e. with a frequency separation equal or greater than 25 MHz. It is now a common assumption that multiple independent transmissions over these channels can coexist without mutual interference even in physical proximity. In this work we demonstrate that this assumption does not hold in general. Through an extensive set of experiments we illustrate the presence of cross-channel interference between “non-overlapping” channels at relay nodes due to the “near-far” effect. We analyze in what manner the MAC layer reacts to such an interference and how this problem extends to higher layers, with detrimental effects on the global throughput. The central problem is that cross-channel interference is not handled adequately by the MAC layer, and in some cases single-channel multi-hop settings perform better than multi-channel. Our results highlight a serious mismatch between some routing and channel assignment schemes proposed recently by the research community, assuming full separation between non-overlapping channels, and what is achievable in practice. More generally, as the presence of cross-channel interference can not be neglected at relay nodes, our findings point to a fundamental problem in building Multi-channel Multi-hop WMN based on IEEE 802.11b/g technology.     

Adaptive networks for physical modeling

This paper presents an original link between neural networks theory and mechanical modeling networks. The problem is to find the parameters characterizing mechanical structures in order to reproduce given mechanical behaviors. Replacing “neural” units with mechanically based units and applying classical learning algorithms dedicated to supervised dynamic networks to these mechanical networks allows us to find the parameters for a physical model. Some new variants of real-time recurrent learning (RTRL) are also introduced, based on mechanical principles.

The notion of interaction during learning is discussed at length and the results of tests are presented. Instead of the classical {machine learning system, environment} pair, we propose to study the {machine learning system, human operator, environment} triplet.

Experiments have been carried out in simulated scenarios and some original experiments with a force-feedback device are also described.     

Compositional State Space Reduction Using Untangled Actions

We propose a compositional technique for efficient verification of networks of parallel processes. It is based on an automatic analysis of LTSs of individual processes (using a failure-based equivalence which preserves divergences) that determines their sets of “conflict-free” actions, called untangled actions. Untangled actions are compositional, i.e. synchronisation on untangled actions will not destroy their “conflict-freedom”. For networks of processes, using global untangled actions derived from local ones, efficient reduction algorithms have been devised for systems with a large number of small processes running in parallel.     

G-networks with resets

Gelenbe networks (G-networks) are product form queuing networks which, in addition to ordinary customers, contain unusual entities such as “negative customers” which eliminate normal customers and “triggers” which move other customers from some queue to another. These models have generated much interest in the literature since the early 1990s. The present paper discusses a novel model for a reliable system composed of N unreliable systems, which can hinder or enhance each other’s reliability. Each of the N systems also tests other systems at random; it is able to reset another system if it is itself in working condition and discovers that the other system has failed, so that the global reliability of the system is enhanced. This paper shows how an extension of G-networks that includes novel “reset” customers can be used to model this behavior. We then show that a general G-network model with resets has product form, and prove existence and uniqueness of its solution.     

“Chaotic relaxation” in concurrently asynchronous neural networks

In this paper we analyze a fundamental issue which directly impacts the scalability of current theoretical neural network models to applicative embodiments, in both software as well as hardware. This pertains to the inherent and unavoidable concurrent asynchronicity of emerging fine-grained computational ensembles and the consequent chaotic manifestations in the absence of proper conditioning. The latter concern is particularly significant since the computational inertia of neural networks in general and our dynamical learning formalisms manifests itself substantially, only in massively parallel hardward—optical, VLSI or opto-electronic. We introduce a mathematical framework for systematically reconditioning additive-type models and derive a neuro-operator, based on the chaotic relaxation paradigm whose resulting dynamics are neither “concurrently” synchronous nor “sequentially” asynchronous. Necessary and sufficient conditions guaranteeing concurrent asynchronous convergence are established in terms of contracting operators. Lyapunov exponents are also computed to characterize the network dynamics and to ensure that throughput-limiting “emergent computational chaos” behavior in models reconditioned with concurrently asynchronous algorithms was eliminated.     

A general treatment of dynamic integrity constraints

This paper introduces a general, set-theoretic model for expressing dynamic integrity constraints, i.e., integrity constraints on the state changes that are allowed in a given state space. In a managerial context, such dynamic integrity constraints can be seen as representations of “real world” constraints and business rules. This topic has important practical applications in many business areas. The notions of (direct) transition, reversible and irreversible transition, transition relation, and consistency of a transition relation will be introduced. The expected link with Kripke models (for modal and temporal logics) is also made explicit. Several practical examples of dynamic integrity constraints will illustrate the applicability of the theory. Some important subclasses of dynamic integrity constraints in a database context will be identified, e.g., various forms of cumulativity (which can be regarded as “transitional” inclusion dependencies concerning two different “points in time”), non-decreasing values, integrity constraints on initial and final values, life cycles, changing life cycles, and transition and constant dependencies. Several formal properties of these dependencies will be derived. For instance, it turns out that functional dependencies can be considered as “degenerated” transition dependencies. Also, the distinction between primary keys and alternate keys is reexamined, from a dynamic point of view.     

SMOCK: A Scalable Method of Cryptographic Key Management for Mission-Critical Wireless Ad-Hoc Networks

Mission-critical networks show great potential in emergency response and/or recovery, health care, critical infrastructure monitoring, etc. Such mission-critical applications demand that security service be “anywhere,” “anytime,” and “anyhow.” However, it is challenging to design a key management scheme in current mission-critical networks to fulfill the required attributes of secure communications, such as data integrity, authentication, confidentiality, nonrepudiation, and service availability. In this paper, we present a self-contained public key-management scheme, a scalable method of cryptographic key management (SMOCK), which achieves almost zero communication overhead for authentication, and offers high service availability. In our scheme, a small number of cryptographic keys are stored offline at individual nodes before they are deployed in the network. To provide good scalability in terms of the number of nodes and storage space, we utilize a combinatorial design of public-private key pairs, which means nodes combine more than one key pair to encrypt and decrypt messages. We also show that SMOCK provides controllable resilience when malicious nodes compromise a limited number of nodes before key revocation and renewal.      

Integration of neural networks and genetic algorithms for an intelligent manufacturing controller

This paper addresses the development and implementation of a “controller” for a single manufacturing machine. This prototype will serve as an important tool to study the integration of several functions and the utilization of status data to evaluate scheduling and control decision alternatives. The emphasis is on creating a prediction capability to aid in assessing the long-term system performance impact resulting from decisions made and environmental changes. This prediction capability is implemented by using neural networks, simulation, and genetic algorithms. Neural networks predict the behavior of different sequencing policies available in the system. The contribution of the genetic algorithms to the decision-making process is the development of a “new” scheduling rule based on a “building blocks” procedure initiated by the neural networks     

Knowledge acquisition using hypertext

This paper addresses the issue of supporting knowledge acquisition using hypertext. We propose a way of tightly integrating hypertext and structured object representation, using Artificial Intelligence (AI) frames for the basic representation of hypertext nodes. Epistemologically, a dual view of the resulting space is of interest. One view is that of hypertext which emphasizes nodes containg g text, including formal knowledge representation. The other view focuses on objects with certain relationships, which define a semantic network. Both in hypertext and in semantic networks the relations between chunks of knowledge are explicitly represented by links. However, in today's hypertext systems a node typically contains just informal text and references to other nodes. Our approach additionally facilitates the explicit representation of structure “inside” hypertext nodes using partitions. We show the usefulness of such a tight integration for knowledge acquisition, providing several features useful for supporting it based on a level of basic hypertext functionality. In particular, we sketch a method for doing knowledge acquisition in such an environment. Hypertext is used as a mediating “semiformal” representation, which allows experts to directly represent knowledge without the immediate support of knowledge engineers. These help then to make this knowledge operational, supported by the system's facility to provide templates as well as their links to the semiformal representation. As an example of our results of using this method of knowledge acquisition, we illustrate the strategic knowledge in our application domain. More generally, our approach supports important aspects of (software) engineering knowledge-based systems and their maintenance. Also their user interface can be improved this way.     

General structure and characteristics of quick response production system

The diversification and shorter production cycles urge manufacturers to shift their production systems from “make to stock” to “make to order” or an intermediate production system between them. The present paper deals with a production system developed by some manufacturers to meet requirements in the last decade. The system, which we call “Quick response to orders production system” or in brief “quick response production system (QRPS)”, is characterized by two key factors, i.e., “acceptable response time” and “semifinished product.” An acceptable response time is decided through the explicit or implicit approval of customers beforehand and manufacturers guarantee to ship products within an acceptable response time in a stochastic sense by processing the semifinished product according to customer order. As a result, manufacturers are able to reduce the inventory of finished products, while customers are able to enjoy the diversification of products and a stable supply from manufacturers. The general structure and characteristics of QRPS are discussed primarily from a quantitative point of view and a numerical example is shown to assist in understanding the design and operation of QRPS.     

Computer networks and interfirm relationships in the automobile industry: A comparative study of Japan and Korea

This paper presents the results of comparative research between the Japanese and Korean automobile industries through empirical research on applications in the interfirm network and the effects on management. Almost all Japanese automobile parts suppliers installed an interfirm network in the latter half of the 1980s. In the case of Korea, it was in the middle 1990s. The type of interfirm networks both in Japan and Korea are vertical networks in which the assembler takes leadership for the construction and maintenance of their interfirm network. The kind of interchanged data on the network reflects the interfirm relationship between the assembler and the parts suppliers. Data in the design and technology field are interchanged via the interfirm network more in Japan than in Korea. This result demonstrates that the assembler and the parts suppliers have a closer relationship, such as “design-in”, in Japan than in Korea.     

Smart Dust Security – Key Infection Revisited

Sensor network is a notion denoting an interesting subset of self-organising wireless networks. These networks are rather dense as each node have typically more than dozen neighbours, and large – with tens to hundreds thousands of nodes. Applications of such networks assume distributed environmental sensing performed by each sensor in the network, where data from a particular sensor gain value only when combined with data from a relatively high number of other sensors. One of the open security questions in this specific environment is a possibility to lower requirements on key distribution and key management and thus decrease production costs. One of the possible ways is “key infection”. The paper recaps a protocol and already published results. It also elaborates the concept of key infection by introducing a new variant of security amplification protocol, and presents some interesting results obtained by simulations.     

Identification of structural systems by neural networks

A method based on the use of neural networks is developed for the identification of systems encountered in the field of structural dynamics. The methodology is applied to the identification of linear and nonlinear dynamic systems such as the damped Duffing oscillator and the Van der Pol equation. The “generalization” ability of the neural networks is used to predict the response of the identified systems under deterministic and stochastic excitations. It is shown that neural networks provide high fidelity models of unknown structural dynamic systems, which are used in applications such as structural control, health monitoring of structures, earthquake engineering, etc.