Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches

We consider a type of on-line, traffic scheduling problem in input queued, crossbar switches. The input to a problem, at each time step, is a set of desired traffic rates. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of switch uses in which only whole packets are sent. The focus of this paper is bounding the costs incurred in using such an approximation, in terms of the additional buffer size required. We establish universal bounds on the additional buffer size due to sending only whole packets; these bounds do not depend on the particular distribution of the input traffic, require no speedup, and guarantee 100% throughput. Specifically, for an N × N input queued, crossbar switch, an on-line, packetizing algorithm is presented that guarantees 100% throughput with a buffer requirement of (N + 1)²/4 packets per input port with no speedup. The algorithm can he improved to run in O(N log N) time, using a fast algorithm for edge-coloring bipartite multigraphs. In the reverse direction, it is shown for an N × N input queued, crossbar switch, that any on-line, packetizing algorithm with no speedup requires a buffer size of N/e - 2 packets per input port. We also extend the main packetizing algorithm in this paper to a general class of switch architectures.