Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

An investigation of synchrony in transport networks

The cumulative degree distributions of transport networks, such as air transportation networks and respiratory neuronal networks, follow power laws. The significance of power laws with respect to other network performance measures, such as throughput and synchronization, remains an open question. Evolving methods for the analysis and design of air transportation networks must be able to address network performance in the face of increasing demands and the need to contain and control local network disturbances, such as congestion. Toward this end, we investigate functional relationships that govern the performance of transport networks; for example, the links between the first nontrivial eigenvalue, λ₂, of a network's Laplacian matrix—a quantitative measure of network synchronizability—and other global network parameters. In particular, among networks with a fixed degree distribution and fixed network assortativity (a measure of a network's preference to attach nodes based on a similarity or difference), those with small λ₂ are shown to be poor synchronizers, to have much longer shortest paths and to have greater clustering in comparison to those with large λ₂. A simulation of a respiratory network adds data to our investigation. This study is a beginning step in developing metrics and design variables for the analysis and active design of air transport networks. © 2008 Wiley Periodicals, Inc. Complexity, 2009     

Why organizational networks in reality do not show scale-free distributions

This paper discusses chain of command networks that are most likely to exhibit the scale-free (SF) property in organizational networks, explaining why organizational networks do not show SF distributions. We propose an evolving hierarchical tree network model without explicit preferential attachment. The model simulates several kinds of chain of command networks with the span of control ranging from extreme homogeneity to extreme heterogeneity. In addition to traditional degree distribution, a new kind of cumulative-outdegree distribution p(K _cum =k _cum ) is introduced and discussed that gives a probability that a randomly selected node has exactly k _cum children nodes. Theoretical analysis and simulation results show that even if the network size is large enough to meet the demand of large-scale networks, the SF property can emerge only when a hierarchical tree lies in two extreme situations: (1) the exact same span of control exists at all levels of an organization; (2) the node outdegree (i.e. span of control) distribution obeys a power-law distribution. The empirical investigations show that real organization networks are between the two extreme situations. This is why organizational networks in reality do not show an SF degree distribution or SF cumulative-outdegree distribution. This finding shows that the SF property is the consequence of extreme situations, even though it is very common in nature and in society. In fact, the SF property is of no value in the study of problems in organizations.     

Approximate solutions for expanding search games on general networks

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs \(a_i\) such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

     

Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics

In this paper, we propose a novel measure, viral conductance (VC), to assess the robustness of complex networks with respect to the spread of SIS epidemics. In contrast to classical measures that assess the robustness of networks based on the epidemic threshold above which an epidemic takes place, the new measure incorporates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, we show that VC provides more insight about the robustness of networks than does the epidemic threshold. We also address the paradoxical robustness of Barabási–Albert preferential attachment networks. Even though this class of networks is characterized by a vanishing epidemic threshold, the epidemic requires high effective infection strength to cause a major outbreak. On the contrary, in homogeneous networks the effective infection strength does not need to be very much beyond the epidemic threshold to cause a major outbreak. To overcome computational complexities, we propose a heuristic to compute the VC for large networks with high accuracy. Simulations show that the heuristic gives an accurate approximation of the exact value of the VC. Moreover, we derive upper and lower bounds of the new measure. We also apply the new measure to assess the robustness of different types of network structures, i.e. Watts–Strogatz small world, Barabási–Albert, correlated preferential attachment, Internet AS-level, and social networks. The extensive simulations show that in Watts–Strogatz small world networks, the increase in probability of rewiring decreases the robustness of networks. Additionally, VC confirms that the irregularity in node degrees decreases the robustness of the network. Furthermore, the new measure reveals insights about design and mitigation strategies of infrastructure and social networks.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

State-dependent routing on symmetric loss networks with trunk reservations. II: Asymptotics,optimal design

We investigate a distributed, state-dependent, dynamic routing strategy for circuit-switched loss networks which we have called Aggregated-Least-Busy-Alternative (ALBA). The networks considered are symmetric and fully connected, the offered calls form Poisson streams and routes have at most two links. In ALBA(K), the states of each link are lumped intoK (K 2) aggregates and the route of each call is determined by local information on the aggregate-states of the links of the alternate routes. The last aggregate is always the set of states reserved for direct traffic and defined by the trunk reservation parameter. The particular case of ALBA in which there is no aggregation is Least-Busy-Alternative (LBA); ALBA(2) represents the other extreme of aggregation. We consider two separate asymptotic scalings based on Fixed Point Models for ALBA(K) which were obtained and investigated in an earlier paper. In the first, it is assumed that the number of network nodes, the offered traffic and trunk group size are all large; their ratios have been chosen to reflect practical interest. The results show that there exists a threshold which delineates fundamentally different behavior: for offered traffic below the threshold, the network loss probability decreases exponentially with increasing network size, while above the threshold the decrease is only polynomial. In the related second asymptotic scaling, the asymptotically optimum trunk reservation parameter is obtained as the solution of a simple equation. Such asymptotically optimal designs are compared to the outputs of exhaustive numerical searches for some realistically sized networks and found to perform very well.Dr. Gibbens' work was done while visiting AT&T Bell Laboratories. His present address: Statistical Laboratory, University of Cambridge, 16 Mill Lane, Cambridge, CB2 1SB, UK.     

Asymptotically optimal importance sampling for Jackson networks with a tree topology

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node’s nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i.e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4):1306–1346, 2007), which are based on a limit Hamilton–Jacobi–Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.     

Survey on path and cycle embedding in some networks

To find a cycle (resp. path) of a given length in a graph is the cycle (resp. path) embedding problem. To find cycles of all lengths from its girth to its order in a graph is the pancyclic problem. A stronger concept than the pancylicity is the panconnectivity. A graph of order n is said to be panconnected if for any pair of different vertices x and y with distance d there exist xy-paths of every length from d to n. The pancyclicity or the panconnectivity is an important property to determine if the topology of a network is suitable for some applications where mapping cycles or paths of any length into the topology of the network is required. The pancyclicity and the panconnectivity of interconnection networks have attracted much research interest in recent years. A large amount of related work appeared in the literature, with some repetitions. The purpose of this paper is to give a survey of the results related to these topics for the hypercube and some hypercube-like networks.      

Strict Nash networks and partner heterogeneity

This paper extends the two-way flow model of network formation initiated by Bala and Goyal (Econometrica 68(5):1181–1230, 2000) by allowing for partner heterogeneity. In our model if a player i forms a link with player j, then she pays a cost of c _j and gets benefits of V _j . Our main result consists of the characterization of strict Nash networks. We find that the introduction of partner heterogeneity plays a major role in dramatically increasing the set of strict Nash equilibria. This result differs substantially from what Galeotti et al. (Games Econ Behav 54(2):353–372, 2006) find in the two-way flow connections model of network formation with player heterogeneity.     

Neural networks and flexible approximations

Email: cuny{at}cardiff.ac.uk This paper supports the view that neural networks are best seenas devices that can approximate a wide range of functions. Theauthors argue the need to consider the precise details of howthe approximations operate in practice. The paper shows howstandard network models can be regarded as polynomial functions,obtained from expanding exponential terms. Multivariate Taylor-seriesexpansions, obtained through the MAPLE software package, areused for this purpose. The expansions serve to cast light onthe role of the hidden nodes. Also considered is the relativedifficulty of fitting different types of function. Quadraticfunctions are compared with Gaussian shapes.     

Decentralized communication, trail connectivity and emergent benefits of ant pheromone trail networks

Communication improves decision-making for group-living animals, especially during foraging, facilitating exploitation of resources. Here we model the trail-based foraging strategy of Pharaoh’s ants to understand the limits and constraints of a specific group foraging strategy. To minimise assumptions we used model parameters acquired through behavioural study. Pharaoh’s ants (Monomorium pharaonis) exploit the geometry of trail networks bifurcations to make U-turns, if they are walking the wrong way. However, 7% of foragers perform apparently incorrect U-turns. These seemingly maladaptive U-turns are performed by a consistent minority of specialist U-turners that make frequent U-turns on trails and lay trail pheromones much more frequently compared to the rest of the colony. Our study shows a key role for U-turning ants in maintaining the connectivity of pheromone trails. We produced an agent-based model of a heterogeneous ant community where 7% of agents were specialised frequent U-turners whilst the remaining 93% rarely U-turned. Simulations showed that heterogeneous colonies enjoyed significantly greater success at foraging for distant food resources compared to behaviourally homogeneous colonies. The presence of a cohort of specialised trail-layers maintains a well-connected network of trails which ensures that food discoveries are rapidly linked back to the nest. This decentralised information transfer might ensure that foragers can respond to dynamic changes in food distribution, thereby allowing more individuals in a group to benefit by successfully locating food finds.     

On minimum metric dimension of honeycomb networks

A minimum metric basis is a minimum set W of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex wW with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. The honeycomb and hexagonal networks are popular mesh-derived parallel architectures. Using the duality of these networks we determine minimum metric bases for hexagonal and honeycomb networks.     

Queueing networks with dependent nodes and concurrent movements

Classical queueing network processes are useful for modeling the movement of discrete units in a network in which the nodes operate independently, the routing of units is independent of the congestion, only one unit moves at a time and its equilibrium distribution is a well-understood product form. Actual networks, however, typically have dependent nodes and concurrent movement of units. Imagine the dependencies associated with the network movements of telephone calls, manufacturing material, computer data packets, messages in a parallel-processing simulation, etc. A second generation of queueing network processes is beginning to evolve for modeling such “intelligent” networks with dependent nodes and concurrent movements. This paper describes the following fundamental processes that have been developed in this regard:

? A basic queueing network process for dependent nodes and single-unit movements. Examples include the classical Jackson, BCMP, Kelly and Kelly-Whittle networks and networks with interacting subpopulations.

? Reversible queueing network processes for dependent nodes and concurrent movements. An example is a multivariate, compound birth-death process.

? Miscellaneous partially balanced queueing networks. Examples include extensions of the basic network processes and weakly coupled and quasi-reversible networks.

     

Network robustness and irreversibility of information diffusion in Complex networks

Complex networks are characterized based on a newly proposed parameter, “degree of diffusion α”. It defines the ratio of information adopters to non-adopters within a diffusion process over consecutive penetration depths. Furthermore, the perfectness of a social network is evaluated by exploring different variations of α such as the reverse diffusion (α_reverse) and the random-kill-diffusion (RKD) processes. The analysis of α_reverse and RKD processes shows information diffusion irreversibility in small-world and scale-free but not in random networks. It also shows that random networks are more stable toward attacks, resulting a complete information diffusion process over the entire network. Finally, a real Complex network example, represented as a “virtual friendship network” was analyzed and found to share properties of both random and small-world networks. Therefore, it is characterized to be somewhere between random and small-world network models or in other words, it is a randomized small-world network model.     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Strong approximations for Markovian service networks

Inspired by service systems such as telephone call centers, we develop limit theorems for a large class of stochastic service network models. They are a special family of nonstationary Markov processes where parameters like arrival and service rates, routing topologies for the network, and the number of servers at a given node are all functions of time as well as the current state of the system. Included in our modeling framework are networks of M _t /M _t /n _t queues with abandonment and retrials. The asymptotic limiting regime that we explore for these networks has a natural interpretation of scaling up the number of servers in response to a similar scaling up of the arrival rate for the customers. The individual service rates, however, are not scaled. We employ the theory of strong approximations to obtain functional strong laws of large numbers and functional central limit theorems for these networks. This gives us a tractable set of network fluid and diffusion approximations. A common theme for service network models with features like many servers, priorities, or abandonment is “non-smooth” state dependence that has not been covered systematically by previous work. We prove our central limit theorems in the presence of this non-smoothness by using a new notion of derivative. This revised version was published online in June 2006 with corrections to the Cover Date.     

Path Boxplots: A Method for Characterizing Uncertainty in Path Ensembles on a Graph

Graphs are powerful and versatile data structures that can be used to represent a wide range of different types of information. In this article, we introduce a method to analyze and then visualize an important class of data described over a graph—namely, ensembles of paths. Analysis of such path ensembles is useful in a variety of applications, in diverse fields such as transportation, computer networks, and molecular dynamics. The proposed method generalizes the concept of band depth to an ensemble of paths on a graph, which provides a center-outward ordering on the paths. This ordering is, in turn, used to construct a generalization of the conventional boxplot or whisker plot, called a path boxplot, which applies to paths on a graph. The utility of path boxplot is demonstrated for several examples of path ensembles including paths defined over computer networks and roads. Supplementary materials for this article are available online.     

Can tools help unify organization theory? Perspectives on the state of computational modeling

Scholars engaged in the study of work group and organizational behavior are increasingly calling for the use of integrated methods in conducting research, including the wider adoption of computational models for generating and testing new theory. Our review of the state of modern computational modeling incorporating social structures reveals steady increases in the incorporation of dynamic, adaptive, and realistic behaviors of agents in network settings, yet exposes gaps that must be addressed in the next generation of organizational simulation systems. We compare 28 models according to more than two hundred evaluation criteria, ranging from simple representations of agent demographic and performance characteristics, to more richly defined instantiations of behavioral attributes, interaction with non-agent entities, model flexibility, communication channels, simulation types, knowledge, transactive memory, task complexity, and resource networks. Our survey assesses trends across the wide set of criteria, discusses practical applications, and proposes an agenda for future research and development. Michael J. Ashworth is a doctoral candidate in computational organization science at Carnegie Mellon University, where he conducts research on social, knowledge, and transactive memory networks along with their effects on group and organizational learning and performance. Practical outcomes of his work include improved understanding of the impact of technology, offshoring, and turnover on organizational performance. Mr. Ashworth has won several prestigious grants from the Sloan Foundation and the National Science Foundation to pursue his research on transactive memory networks. Journals in which his research has appeared include Journal of Mathematical Sociology, International Journal of Human Resource Management, and Proceedings of the International Conference on Information Systems. His recent work on managing human resource challenges in the electric power industry has been featured in the Wall Street Journal and on National Public Radio's ``Morning Edition.' Mr. Ashworth received his undergraduate degree in systems engineering from the Georgia Institute of Technology. Kathleen M. Carley is a professor at the Institute for Software Research International in the School of Computer Science at Carnegie Mellon University. She is the director of the center for Computational Analysis of Social and Organizational Systems (CASOS), a university-wide interdisciplinary center that brings together network analysis, computer science and organization science (www.casos.ece.cmu.edu). Prof. Carley carries out research that combines cognitive science, dynamic social networks, text processing, organizations, social and computer science in a variety of theoretical and applied venues. Her specific research areas are computational social and organization theory; dynamic social networks; multi-agent network models; group, organizational, and social adaptation, and evolution; statistical models for dynamic network analysis and evolution, computational text analysis, and the impact of telecommunication technologies on communication and information diffusion within and among groups. Prof. Carley has undergraduate degrees in economics and political science from MIT and a doctorate in sociology from Harvard University.