Patent ID: 7072353

Claim:
A method of allocating bandwidth for use at a packet switch having a plurality of inputs and a plurality of outputs for switching to specified ones of said outputs, and a plurality of corresponding input buffers having input-output queues, and associated counters, said method comprising the steps of dividing time into a plurality of frames of time slots, each frame having a specified integer value of time slots; loading said counters associated with said input-output queues to a negotiated integer value once per said frame; said inputs sequentially selecting said outputs that are available to which said inputs send packets in specified future time slots, wherein priority is given to those of input-output queues whose associated ones of said counters having positive values; said selection of outputs by said inputs being done using a pipeline technique where input i, i=0,1, . . . , N−1 chooses output for time slot k in time slot k−┌(N−i)/p┐, where p is the number of selections made in one time slot, N is the number of inputs of said switch, and ┌(N−i)/p┐ is the smallest integer greater or equal to * (N−i)/p, and wherein a schedule is calculated within multiple time slots, wherein schedules for multiple future time slots being calculated in each time slot; and decrementing said counters of selected queues by 1.