Patent ID: 7154885

Claim:
A packet switch for switching cells, said packet switch comprising: N input ports capable of receiving and storing cells in a plurality of input queues; N output ports capable of receiving and storing cells from said N input ports in a plurality of output queues; a switch fabric for transferring said cells from said N input ports to said N output ports, said switch fabric comprising an internally buffered crossbar having N×N internal buffers associated therewith, wherein each internal buffer is associated with a crosspoint of one of said N input ports and one of said N output ports; and a scheduling controller capable of: selecting a first one of a plurality of queued head-of-line (HOL) cells from said input queues to be transmitted to a first one of said N×N internal buffers according to a fair queuing algorithm in which each of said queued HOL cells is allocated a weight of R ij ; and selecting a first one of a plurality of HOL cells buffered in a second one of said N×N internal buffers to be transmitted to a first one of said output queues according to the fair queuing algorithm in which each of said internally buffered HOL cells is allocated a weight of R ij ; wherein a group of K queues share a combined capacity of 1, and ∑ i = 1 K ⁢ R i ≤ 1 , where R i is a guaranteed bandwidth associated with queue i, wherein any queue being non-empty over a time interval T can be guaranteed a bandwidth of R i T+E, where E is a constant.