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.

     

Travel times in queueing networks and network sojourns

We first describe expected values of sojourn times for semi-stationary (or synchronous) networks. This includes sojourn times for units and sojourn times for the entire network. A typical sojourn time of a unit is the time it spends in a sector (set of nodes) while it travels through the network, and a typical network sojourn time is the busy period of a sector. Our results apply to a wide class of networks including Jackson networks with general service times, general Markov or regenerative networks, and networks with batch processing and concurrent movement of units. The results also shed more light on when Little's law for general systems, holds for expectations as well as for limiting averages. Next, we describe the expectation of a unit's travel time on a general route in a basic Markov network process (such as a Jackson process). Examples of travel times are the time it takes for a unit to travel from one sector to another, and the time between two successive entrances to a node by a unit. Finally, we characterize the distributions of the sojourn times at nodes on certain overtake-free routes and the travel times on such routes for Markov network processes.This research was supported in part by the Air Force Office of Scientific Research under contract 89-0407 and NSF grant DDM-9007532.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

A generalization of Norton's theorem for queueing networks

A general framework for aggregation and decomposition of product form queueing networks with state dependent routing and servicing is presented. By analogy with electrical circuit theory, the stations are grouped into clusters of subnetworks such that the process decomposes into a global process and a local process. Moreover, the local process factorizes into the subnetworks. The global process and the local processes can be analyzed separately as if they were independent. The global process describes the behaviour of the queuing network in which each cluster is aggregated into a single station, whereas the local process describes the behaviour of the subnetworks as if they are not part of the queueing network. The decomposition and aggregation method formalized in this paper allows us to first analyze the global behaviour of the queueing network and subsequently analyze the local behaviour of the subnetworks of interest or to aggregate clusters into single stations without affecting the behaviour of the rest of the queueing network. Conditions are provided such that:

- the global equilibrium distribution for aggregated clusters has a product form;

- this form can be obtained by merely monitoring the global behaviour;

- the computation of a detailed distribution, including its normalizing constant, can be decomposed into the computation of a global and a local distribution;

- the marginal distribution for the number of jobs at the stations of a cluster can be obtained by merely solving local behaviour.

As a special application, Norton's theorem for queueing networks is extended to queueing networks with state dependent routing such as due to capacity constraints at stations or at clusters of stations and state dependent servicing such as due to service delays for clusters of stations.     

Traffic Flows and Product Form Solutions in Stochastic Transfer Networks

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions.     

Loss circuit switched communication network-performance analysis and dynamic routing

We investigate a loss circuit switched communication network with state-dependent dynamic routing strategy, wherein the state of the network at the time of call arrival determines whether or not the call is accepted and, if accepted, its route. We develop an approximate approach to the network performance analysis. The approach enhances the Fixed Point Model by treating multiple solutions of the Fixed Point Equations. Assuming that the multiple solutions correspond to the long-living network modes, we develop the aggregated Markov chain that describes the network transitions among these modes. We also propose and discuss a new state-dependent dynamic routing strategy which we call Least-Expected-Blocking strategy (LEB). LEB accepts an incoming call only if this results in a decrease in the expected blocking probability and it chooses a route that yields the maximum decrease. The new strategy outperforms the previously known strategies by the criterion of network steady blocking probability.     

The Functional Law of the Iterated Logarithm for the Empirical Process Based on Sample Means

Consider a double array of i.i.d. random variables with mean and variance and set . Let denote the empirical distribution function of Z_{1, n} ,..., Z _{N, n} and let be the standard normal distribution function. The main result establishes a functional law of the iterated logarithm for , where n=n(N) as N. For the proof, some lemmas are derived which may be of independent interest. Some corollaries of the main result are also presented.     

On centripetal flows of entities in scale‐free networks with nodes of finite capability

We examine the transmission of entities from the peripheries of scale‐free networks toward their centers when the nodes of the network have finite processing capabilities. We look at varying network utilization, U and find that clogging of the network sets in after a threshold value has been exceeded, and that the congestion sets in at the downstream nodes (those nearer to the collector) having large numbers of upstream neighbors. Investigation of the question of the degree of correlation of several characteristics of scale‐free networks (such as the average path length to the collector <l_(min)> and the average clustering coefficient ) with the dynamics of centripetal flow in them reveals a negative answer: any correlation is indirect and will manifest in the number of producer nodes (which dictate the effective heaviness of the flow) and the interconnectedness of the feeder nodes, those nodes which are immediate neighbors of the collector node. An examination of reinforcement strategies shows dramatic improvements in both the finishing rate, and the average total transmission time, when the more centrally‐placed nodes are reinforced first, showing that the entities spend a large amount of their lifetime waiting in line at those nodes (which constitute the bottlenecks in the network) compared to the nodes in the periphery. Our results reinforce the importance of a network's hubs and their immediate environs, and suggest strategies for prioritizing elements of a network for optimization. © 2014 Wiley Periodicals, Inc. Complexity 21: 283–295, 2015     

Performance & packet traffic dynamics of Packet Switching Network model

Dynamics of packet traffic in data communication networks can be complex and often not well understood. Understanding of these complex dynamics is important for their control, prediction purposes and for the data networks design. The engineering community has described wired data networks architectures and studied them by means of a layered, hierarchical abstraction called ISO OSI (International Standard Organization Open System Interconnect) Reference Model. The Network Layer of the ISO OSI Reference Model is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using an abstraction of the Network Layer that we developed, we investigate packet traffic dynamics in our data network models of data communication networks of packet switching type, in particular near the phase transition point from free flow to congestion. We explore how these dynamics and network performance indicators are affected by network connection topology and routing algorithms. We consider static and adaptive routing algorithms. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

On the temporal analysis of special GERT networks using a modified Markov renewal process

In this paper we show how to represent a STEOR network (GERT network with only nodes of the stochastic exclusive-or Type) by a modified Markov renewal process. The computation of the renewal kernel of this process yields the temporal analysis of the network.

---

Zusammenfassung Es wird gezeigt, wie ein STEOR-Netzplan (GERT-Netzplan, der nur Knoten vom Typ stochastisch exklusiv-oder enthält) durch einen modifizierten Markowschen Erneuerungsprozeß beschrieben werden kann. Die Bestimmung der Erneuerungsfunktionen dieses Prozesses liefert die Auswertung des STEOR-Netzplans (im Sinne der Zeitplanung).

     

ATM Routing Algorithms for Multimedia Traffic in Private ATM Networks

The goal of this paper is to recommend a good Private Network-to-Network Interface (PNNI) routing algorithm for private ATM networks. A good routing algorithm has to work well with multimedia traffic with several quality of service (QoS) requirements (such as cell loss ratio, cell delay and its variation etc.) in different networks under various traffic conditions. The multiplicity of QoS requirements makes the routing problem NP-complete, so our approach to the problem is based on large scale simulations involving several empirical algorithms (compliant with the PNNI routing specification) which have been tested for different network topologies and traffic scenarios. Based on analysis of tradeoffs involving performance metrics (such as blocking rate, complexity, load distribution) we recommend a consistently good routing algorithm for single domain ATM networks.     

Two Workload Properties for Brownian Networks

As one approach to dynamic scheduling problems for open stochastic processing networks, J.M. Harrison has proposed the use of formal heavy traffic approximations known as Brownian networks. A key step in this approach is a reduction in dimension of a Brownian network, due to Harrison and Van Mieghem [21], in which the queue length process is replaced by a workload process. In this paper, we establish two properties of these workload processes. Firstly, we derive a formula for the dimension of such processes. For a given Brownian network, this dimension is unique. However, there are infinitely many possible choices for the workload process. Harrison [16] has proposed a canonical choice, which reduces the possibilities to a finite number. Our second result provides sufficient conditions for this canonical choice to be valid and for it to yield a non-negative workload process. The assumptions and proofs for our results involve only first-order model parameters.     

On the Limiting Proportion of Types

Consider a system into which units of random type enter at fixed points in time. Suppose each unit is endowed with a lifetime whose distribution is specific to its type, during which it is active (present in the system), and after which it is inactive (deleted from the system). Some unit types may tend to remain active for longer periods than others, and thus the limiting proportion of a given type within the active population may differ from the probability that an entering unit is of that type. The relation between the probabilities of types and the limiting proportion of types is shown to depend on the life distributions in a manner determined by the arrival time sequence.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.