On the duality between routing and scheduling systems with finite buffer space

摘要

A duality between scheduling and routing problems associated with a set of parallel queues is established. This allows one to determine the optimal policy for either system, once it is determined for its dual system. Moreover, the evaluation of different design alternatives (e.g., allocation of buffers) can be accommodated in the same duality framework. A crucial assumption is that both systems should be Markovian. Furthermore, when there is no buffer at the controller, the scheduling policy is assumed to be preemptive. On the other hand, when there exists buffer space dedicated to the controller, both the routing and scheduling policies are assumed to be nonidling. Various applications are presented. It is shown, for instance, that the smallest residual capacity scheduling policy is optimal, as it is the dual of the well-known shortest queue routing policy.