Capacity Estimation of Cyclic Queues

Abstract

In many data communication and telephone switching systems, one processor must perform more than one type of task. In some systems it is advantageous to place the different tasks in different queues and have the processor serve the queues in a cyclic manner. Moreover, the system design often imposes a (finite or infinite) limit on the number of entries that may be served per cycle from any given queue; this limit typically varies from queue to queue. This paper will derive the capacity estimation of such systems. We consider systems which, in addition to servingnqueues cyclically, must execute maintenance (or other low-priority jobs) without severely disrupting the queues' performance. For two alternative methods of scheduling the maintenance, we compute steady state values of i) the average cycle time, ii) the average number of entries of each queue served per cycle, iii) the average time spent at each queue per cycle, iv) the average amount of elapsed time necessary to complete a given amount of maintenance execution real time, and v) if the arrival rate to queuei,\lambda_{i}, is proportional toN, the number of customers in the system, i.e.,\lambda_{i} = N\alpha_{i}, then we a) compute the value ofNwhich saturates the system and b) predict which queue will first become saturated asNis increased towards this value.