2006 · 26 citations · 23 references
BusinessComputer ScienceMathematicsComputer ArchitectureDiscrete MathematicsQueuing TheoryNetworks Of QueuesQueue ManagementQueueing AnalysisQueueing NetworksQueueing SystemsQueueing TheoryCompressorsQueueing ModelsQueues
Abstract — Queueing theory is generally known as the theory to study the performance of queues. In this paper, we are interested in another aspect of queueing theory, the theory to construct queues via switched delay lines. We consider three types of discrete-time queues: linear compressors, non-overtaking delay lines and flexible delay lines. These three types of queues correspond to certain conditional nonblocking switches and (strict sense) nonblocking switches in switching theory. Analogous to their counterparts in switching theory, there exist multistage constructions for these three types of queues. Specifically, we develop a two-stage construction of a linear compressor and a three-stage construction of a non-overtaking delay line. Similarly, there is a three-stage construction of a flexible delay line. Moreover, a flexible delay line can also be constructed by a layered Cantor network. I.
23
Sorting networks and their applications
Kenneth E. Batcher · 1968 · 2.4K citations
A Study of Non-Blocking Switching Networks
Charles Clos · Bell System Technical Journal · 1953 · 1.7K citations