Browse Prior Art Database

Models for Queue Length in Clocked Queuing Networks

IP.com Disclosure Number: IPCOM000149501D
Original Publication Date: 1989-Jan-31
Included in the Prior Art Database: 2007-Apr-01

Publishing Venue

Software Patent Institute

Related People

Percus, Ora E.: AUTHOR [+3]

Abstract

by Ora E. Percus J. K. Percus Ultracomputer Note #I53 January, 1989

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 21

Models for Queue Length in Clocked Queuing Networks

   by
Ora E. Percus
J. K. Percus Ultracomputer Note #I53
January, 1989

    This work was supported in part by the Applied Mathematic.al Scicnccs Program of the US Department of En- ergy under contract DE-FG02-88ER2505.2.

[This page contains 1 picture or other non-text object]

Page 2 of 21

1.. Introduction

   Digital computers in practice are synchronous machines running on a clock cycle, a mode of operation which is mandatory when parallel operations are to be performed. The information that is routed from node to node through the internal networks of an efficiently designed machine will not always be transmitted at once through a node, but. may have to wait, effectively in a queue. Although the analysis of networks with queues has an ancient and honorable history, this analysis has become routine only for stationary operation in continuous time. Transient problems or, much more importantly from our present point of view, discrete clock-regulated transmissions, have been considered in the main from the direction of general existence theorems, or for highly oversimplified models.

   ?tre would like in this paper to make a start towards systematic analysis of discrete-time networks with queues. In conformity with several current network realizations [l]?
the unit element

of the networks we consider will be the 2 x 2 buffered switch, which we can regard as a system of two queues working in parallel, each one with a deterministic server of unit serving time. A message

I I

Fig. 1. 2 x 2 buffered switch

entering either of the two inputs of the switch goes with probability 1/2 to either of the two output queues of the switch. Any node in this network will see a time series, each element of which is the presence or absence of an information packet to be transmitted to the next node. Thus we are observing the transformation of discrete time series by the ba.sjc processes of passage through a queue and of mising.

   Continuous time stationary queuing systems in such as Jackson networks [5] are characterized as Poisson processes, only one parameter being necessary to describe which member of the class is

[This page contains 1 picture or other non-text object]

Page 3 of 21

under consideration, and with the guarantee that elementary transformation processes do not take one out of this class. The situation is very different with discrete clock-regulated networks, even for stationary operation, which will be our principal concern. For example, it has been shown that if independent uncorrelated Bernoulli streams of 0's and 1's (packet absent or present) enter the input of the switch of Fig. 1, then each output is instead a highly correlated multi-parameter renewal process [4], and subsequent mixing at the next input complicates this further. 'C-ltimately. one would like to work with the full c...