The Kraft's Inequality of Scheduling for Packet-Switched Clos Networks
T.T. Lee · 2008
The traffic matrix decomposition provides an effective scheduling approach to guarantee capacity of services supported by input queued packet switches. The Birkhoff-von Neumann (BvN) decomposition is widely used to express the doubly stochastic rate matrix as a weighted sum of permutation matrices. The switch then schedules these permutation matrices, using weights corresponding to the coefficients in the decomposition. In a Clos network, each permutation matrix corresponds to a connection pattern in the middle stage. If we regard this set of predetermined connection patterns as a code book, scheduling incoming packets in the input buffer according to predetermined connection patterns is a process similar to the encoding of source signals. In light of the concerns on delay jitter, it is expected that the scheduling should be as smooth as possible. A measurement of smoothness is defined in terms of interstate time of the scheduled sequence. In this paper, we show that the smoothness of scheduling is bounded by the entropy of BvN decomposition, and satisfies the Kraft's inequality. The optimal scheduling can be achieved if and only if the Kraft's equality holds.