CAM01-2: Capacity Maximizing Packet Scheduling Algorithms for Interconnection Networks with Finite Buffers

In this paper, we analyze the throughput of interconnection networks, viewed as multi-stage queueing networks with infinite input queues, but finite internal cross-stage ones. We find that for very general arrival processes and arbitrarily fixed network topology, the stability region with finite internal buffers is identical to that for the corresponding network with infinite internal buffers, and is achievable via special scheduling policies. In particular, we define and study a class of throughput maximizing policies, known as projective cone scheduling (PCS) algorithms, which activate a set of concurrent service rates to all queues in the network based on observed backlog levels.