Network Queueing

Network queueing is a very important application of queueing theory. The term 'network of queues' describes a situation where the input from one queue is the output from one or more others. This is true in many situations from telecommunications to a PC. Below is a description of some of the broad applications of network queueing describing how theories apply to them. Also there are a few general network queueing theories.

  • Computer Networks
  • A simple example of network queueing is the central server network. This consists of a CPU (Central Processing Unit), storage units it can access and input devices to access it. The task the CPU performs are queued on different criteria. Also, the storage units could have their own individual queues. Queues tend to be ordered in a number of ways. They can also be executed either on a one by one serial basis or bit by bit by Time Sharing. It is not always neccessary to treat customers in a queue equally. A priority queueing system may often be used to give some jobs preferential treatment.
  • Network communication

  • There are several broad methods connected to network communication:

  • Broadcasting

  • Markov Chains
  • A stochastic process is a Markov process if the future of the process depends only upon the present state of the process implying that the present state is a direct result of its history. A Markov process is called a Markov chain if its state space is discrete ie it moves from one clearly defined state to another.

  • The Jackson Queueing Network
  • Consider a FIFO queueing network: A queueing network is closed if there are no arrivals from outside of it. Clearly the nature of this system will be that of Markovian Chain as there are only a finite number of states of the network and the next state depends on the ones previous to it. However, a network can also be open. An open queueing network can recieve customers from outside to recieve services at its nodes. Jackson was the first to consider such systems in detail. It is assumed that the arrival rate of customers conforms to the poisson distribution. The average service time at each node and the probability of a node leaving the network is known. From this Jackson formulated a way of calculating the Markovian equilibrium state of the network. ie a tuple containing the equilibrium number of customers at every node.

  • Other Network types
  • The Gordon-Newell network is essentially a closed version of the Jackson network while the BCMP (Baskett, Chandy, Muntz and Palacios) network includes facility for different classes of customers. This requires indexing of the different service time requirements at each node plus different leaving probabilities for each class. Variations of this network are used commonly in computer systems and networks today.

  • References