Space efficient fair queuing by stochastic memory multiplexing

Abstract

A method for multiplexing the buffer space used to store messages of backlogged flows at the output port of a switch. The buffer space is partitioned among queues of variable length, with the first queue long enough to accommodate the largest expected backlog, the second queue long enough to accommodate the second-largest expected backlog, etc. Messages are dequeued from the queues for transmission in Round-Robin order. Incoming messages are enqueued in a manner that guarantees that messages of heavily backlogged flows tend to be enqueued in the longer queues, while preserving FIFO message order. If the messages are all of the same length, then the queues are partitioned into locations, of the same length as the messages, each location having an ordinal index in its queue, and the messages are enqueued so that each message of a particular flow is enqueued in a location with a different ordinal index. If the messages are of different lengths, the queues are partitioned into bins large enough to accommodate the longest messages, one or more messages may be stored in each bin, the round in which each incoming message is to be transmitted is computed in advance, and a similar enqueueing algorithm is used that is based on matching successive transmission rounds of messages of a given flow to successively indexed bins of different queues. The present invention may be used in any application involving Round Robin scheduling.