Some Problems in Queueing Systems with Resequencing

Abstract

The aim of this thesis is to solve some problems associated with queueing systems with resequencing of customers. Resequencing is associated with the presence of some disordering system which operates on an input arrival stream of customers and delays each customer by a random amount, so that they may leave the system in a different order than the one in which they entered it. However, if the constraint that the customers should leave the system in the same order in which they entered it, is imposed, then a customer may have to undergo an additional delay, which is known as resequencing delay. Such situations typically arise due to packet switching in a computer communication network, in an interconnection network of a multi-processor architecture and concurrency control schemes of distributed data bases among other places. The presence of resequencing makes the analysis of the queueing system intractable in most cases, and very few analytical results are known about these systems. Two general representation results for resequencing systems are the principal tools used in the thesis. The first representation gives the delay in a general resequencing system, in a recursive sample path form. It is used to investigate multistage resequencing systems and also to deduce some interesting structural properties of multiple server resequencing systems. It is shown that hop- by-hop resequencing leads to greater delay compared to end-to-end resequencing in N stage infinite server systems in the sense of strong stochastic ordering. The effect of varying the number of servers on the resequencing delay in a finite server system is investigated for both single stage as well as two stage disordering systems, and also several useful structural properties which can be used to develop bounds for intractable resequencing systems, are identified. The second represenation provides a Markovian state space description for the two server resequencing system with exponential interarrival and service times. The state occupation probabilities are calculated for the M/M/2/B queue with resequencing using this representation. The optimal policy for assigned cutomers to the two servers in the case when they have different service rates, to minimize the total delay (including the resequencing delay), is investigated using dynamic programming arguments. The optimal policy is shown to be of the threshold type in the number of customers in the main queue buffer and independent of the number of customers in the resequencing buffer.