This paper introduces a special collection of research contributions written to honour Professor Erol Gelenbe of his 70th birthday which was celebrated on September 20–25, 2015 at Imperial College in London where he holds the Dennis Gabor Professorship and is Head of the Intelligent Systems and Networks Group in the Department of Electrical and Electronic Engineering (see http://san.ee.ic.ac.uk/Gelenbe2015). All but three of the fourteen papers presented here were written by his students and descendants. These papers are centered on probability models related to computer systems and networks, an area where Erol plays a pioneering role in which he remains very active with many innovations and new directions that he has introduced in the last ten or twelve years. We first briefly review Erol's work in these areas, and then discuss each of the contributions that appear here together with their links to Erol's own published research.

We focus on Erol Gelenbe's scientific and technical contributions to probability models in the computer and information sciences, but limit our survey to the last fifteen years. We start with a brief overview of his work as a single author, as well as his work in collaboration with over 200 co-authors. We discuss some of his recent and innovative work regarding a new probability model that represents Intermittent Energy Sources for Computing and Communications, introducing Energy Packet Networks which are a probabilistic representation of the flow, storage and consumption of electrical energy at the microscopic level (in electronic chips), and at the macroscopic level (e.g. in buildings or data centers) and for its routing and dynamic usage by consuming units (such as computer elements, chips or machines). We next discuss his work on designing computer and communication systems that parsimoniously use energy in order to achieve a satisfactory level of quality of service (QoS). Trade-offs between system QoS and energy consumption are also considered. Then we turn to Prof. Gelenbe's pioneering work on Autonomic Communications and the design and implementation of CPN, the Cognitive Packet Network, and we also briefly review his spiking random neural network that was used in CPN. This is followed by a brief review of work that he conducted since 1999 on human evacuation from dangerous or catastrophic environments, and the design of technology driven Emergency Management Systems. His research since the late 2000s on Gene Regulatory Networks is then covered together with its application to the detecting possible disease from microarray data. Finally, we briefly discuss some novel analytical models that he developed in this period with publications appearing in journals of physics and applied mathematics.

The purpose of this paper is to analyze the so-called back-off technique of the IEEE 802.11 protocol in broadcast mode with waiting queues. In contrast to existing models, packets arriving when a station (or node) is in back-off state are not discarded, but are stored in a buffer of infinite capacity. As in previous studies, the key point of our analysis hinges on the assumption that the time on the channel is viewed as a random succession of transmission slots (whose duration corresponds to the length of a packet) and mini-slots during which the back-off of the station is decremented. These events occur independently, with given probabilities. The state of a node is represented by a two-dimensional Markov chain in discrete-time, formed by the back-off counter and the number of packets at the station. Two models are proposed both of which are shown to cope reasonably well with the physical principles of the protocol. The stability (ergodicity) conditions are obtained and interpreted in terms of maximum throughput. Several approximations related to these models are also discussed.

The introduction of the class of queueing networks called G-networks by Gelenbe has been a breakthrough in the field of stochastic modeling since it has largely expanded the class of models which are analytically or numerically tractable. From a theoretical point of view, the introduction of the G-networks has lead to very important considerations: first, a product-form queueing network may have non-linear traffic equations; secondly, we can have a product-form equilibrium distribution even if the customer routing is defined in such a way that more than two queues can change their states at the same time epoch. In this work, we review some of the classes of product-forms introduced for the analysis of the G-networks with special attention to these two aspects. We propose a methodology that, coherently with the product-form result, allows for a modular analysis of the G-queues to derive the equilibrium distribution of the network.

We study G-networks with positive and negative customers and signals. We consider two types of signals: they can make a subnetwork of queues operational or down. As signals are sent by queues after a customer service completion, one can model the availability of a sub-network of queues controlled by another network of queues. We prove that under classical assumptions for G-networks and assumptions on the rerouting probabilities when a subnetwork is not operational, the steady-state distribution, if it exists, has a product form steady state distribution. Some examples are given.

The random neural network is a biologically inspired neural model where neurons interact by probabilistically exchanging positive and negative unit-amplitude signals that has superior learning capabilities compared to other artificial neural networks. This paper considers non-negative least squares supervised learning in this context, and develops an approach that achieves fast execution and excellent learning capacity. This speedup is a result of significant enhancements in the solution of the non-negative least-squares problem which regard (a) the development of analytical expressions for the evaluation of the gradient and objective functions and (b) a novel limited-memory quasi-Newton solution algorithm. Simulation results in the context of optimizing the performance of a disaster management problem using supervised learning verify the efficiency of the approach, achieving two orders of magnitude execution speedup and improved solution quality compared to state-of-the-art algorithms.

A large increase in the number and types of vehicles occurred due to the growth in population. This fact brings the need for efficient vehicle classification systems that can be used in traffic surveillance and intelligent transportation systems. In this study, a multi-type vehicle classification system based on Random Neural Networks (RNNs) and Bag-Of-Visual Words (BOVWs) is developed. A 10-fold cross-validation technique is used, with a large dataset, to assess the proposed approach. Moreover, the BOVW–RNN's classification performance is compared with LIVCS, a vehicle classification system based on RNNs. The results reveal that BOVW–RNN classification system produces more reliable and accurate classification results than LIVCS. The main contribution of this paper is that the developed system can serve as a framework for many vehicle classification systems.

Markov chains (MCs) are widely used to model systems which evolve by visiting the states in their state spaces following the available transitions. When such systems are composed of interacting subsystems, they can be mapped to a multi-dimensional MC in which each subsystem normally corresponds to a different dimension. Usually the reachable state space of the multi-dimensional MC is a proper subset of its product state space, that is, Cartesian product of its subsystem state spaces. Compact storage of the matrix underlying such a MC and efficient implementation of analysis methods using Kronecker operations require the set of reachable states to be represented as a union of Cartesian products of subsets of subsystem state spaces. The problem of partitioning the reachable state space of a three or higher dimensional system with a minimum number of partitions into Cartesian products of subsets of subsystem state spaces is shown to be NP-complete. Two algorithms, one merge based the other refinement based, that yield possibly non-optimal partitionings are presented. Results of experiments on a set of problems from the literature and those that are randomly generated indicate that, although it may be more time and memory consuming, the refinement based algorithm almost always computes partitionings with a smaller number of partitions than the merge-based algorithm. The refinement based algorithm is insensitive to the order in which the states in the reachable state space are processed, and in many cases it computes partitionings that are optimal.

Motivated by applications to multi-antenna wireless networks, we propose a distributed and asynchronous algorithm for stochastic semidefinite programming. This algorithm is a stochastic approximation of a continuous-time matrix exponential scheme which is further regularized by the addition of an entropy-like term to the problem's objective function. We show that the resulting algorithm converges almost surely to an ɛ-approximation of the optimal solution requiring only an unbiased estimate of the gradient of the problem's stochastic objective. When applied to throughput maximization in wireless systems, the proposed algorithm retains its convergence properties under a wide array of mobility impediments such as user update asynchronicities, random delays and/or ergodically changing channels. Our theoretical analysis is complemented by extensive numerical simulations, which illustrate the robustness and scalability of the proposed method in realistic network conditions.

Autonomic computing is emerging as a significant new approach to the design of computer services. Its goal is the development of services that are able to manage themselves with minimal direct human intervention, and, in particular, are able to sense their environment and to tune themselves to meet end-user needs. However, the impact on performance of the interaction between multiple uncoordinated self-optimizing services is not yet well understood. We present some recent results on a non-cooperative load-balancing game which help to better understand the result of this interaction. In this game, users generate jobs of different services, and the jobs have to be processed on one of the servers of a computing platform. Each service has its own dispatcher which probabilistically routes jobs to servers so as to minimize the mean processing cost of its own jobs. We first investigate the impact of heterogeneity in the amount of incoming traffic routed by dispatchers and present a result stating that, for a fixed amount of total incoming traffic, the worst-case overall performance occurs when each dispatcher routes the same amount of traffic. Using this result we then study the so-called Price of Anarchy (PoA), an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. We give explicit bounds on the PoA for cost functions representing the mean delay of jobs when the service discipline is PS or SRPT. These bounds indicate that significant performance degradations can result from the selfish behavior of self-optimizing services. In practice, though, the worst-case scenario may occur rarely, if at all. Some recent results suggest that for the game under consideration the PoA is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem.

Motivated by applications in areas such as cloud computing and information technology services, we consider GI/GI/1 queueing systems under workloads (arrival and service processes) that vary according to one discrete time scale and under controls (server capacity) that vary according to another discrete time scale. We take a stochastic optimal control approach and formulate the corresponding optimal dynamic control problem as a stochastic dynamic program. Under general assumptions for the queueing system, we derive structural properties for the optimal dynamic control policy, establishing that the optimal policy can be obtained through a sequence of convex programs. We also derive fluid and diffusion approximations for the problem and propose analytical and computational approaches in these settings. Computational experiments demonstrate the benefits of our theoretical results over standard heuristics.

We study layered queueing systems comprised two interlacing finite M/M/• type queues, where users of each layer are the servers of the other layer. Examples can be found in file sharing programs, SETI@home project, etc. Let Li denote the number of users in layer i, i=1, 2. We consider the following operating modes: (i) All users present in layer i join forces together to form a single server for the users in layer j (j≠i), with overall service rate μjLi (that changes dynamically as a function of the state of layer i). (ii) Each of the users present in layer i individually acts as a server for the users in layer j, with service rate μj.

These operating modes lead to three different models which we analyze by formulating them as finite level-dependent quasi birth-and-death processes. We derive a procedure based on Matrix Analytic methods to derive the steady state probabilities of the two dimensional system state. Numerical examples, including mean queue sizes, mean waiting times, covariances, and loss probabilities, are presented. The models are compared and their differences are discussed.

Mobile networks are universally used for personal communications, but also increasingly used in the Internet of Things and machine-to-machine applications in order to access and control critical services. However, they are particularly vulnerable to signaling storms, triggered by malfunctioning applications, malware or malicious behavior, which can cause disruption in the access to the infrastructure. Such storms differ from conventional denial of service attacks, since they overload the control plane rather than the data plane, rendering traditional detection techniques ineffective. Thus, in this paper we describe the manner in which storms happen and their causes, and propose a detection framework that utilizes traffic measurements and key performance indicators to identify in real-time misbehaving mobile devices. The detection algorithm is based on the random neural network which is a probabilistic computational model with efficient learning algorithms. Simulation results are provided to illustrate the effectiveness of the proposed scheme.