A recursive analysis technique for multi-dimensionally infinite Markov chains

Abstract

Performance analysis of multiserver systems with multiple classes of jobs often has a common source of difficulty: the state space needed to capture the system behavior grows infinitely in multiple dimensions. For example, consider two processors, each serving its own M/M/1 queue, where one of the processors (the "donor") can help the other processor (the "beneficiary") with its jobs, during times when the donor processor is idle [5, 16] or when some threshold conditions are met [14, 15]. Since the behavior of beneficiary jobs depends on the number of donor jobs in system, performance analysis of beneficiary jobs involves a two dimensionally infinite (2D-infinite) state space, where one dimension corresponds to the number of beneficiary jobs and the other dimension corresponds to the number of donor jobs. Another example is an M/M/2 queue with two priority classes, where high priority jobs have preemptive priority over low priority jobs (see for example [1, 3, 4, 8, 10, 11, 12, 17] and references therein). Since the behavior of low priority jobs depends on the number of high priority jobs in system, performance analysis of low priority jobs involves 2D-infinite state space, where each dimension corresponds to the number of each class of jobs in system. As we will see, when there are m priority classes, performance analysis of the lowest priority classes involves m dimensionally infinite state space.

Additional details