Optimum scheduling and memory management in input queued switches with finite buffer space

The goal of this paper is to design optimal scheduling and memory management so as to minimize packet loss in input queued switches with finite input buffers. The contribution is to obtain closed-form optimal strategies that minimize packet loss in 2×2 switches with equal arrival rates for all streams. For arbitrary arrival rates, the contribution is to identify certain characteristics of the optimal strategy, and use these characteristics to design a near-optimal heuristic. A lower bound for the cost associated with packet loss for N×N switches is obtained. This lower bound is used to design a heuristic which attains near-minimum packet loss in N×N switches with arbitrary N. These policies reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case. The framework and the policies proposed here apply to buffer-constrained wireless networks as well.