Patent ID: 7554914

Claim:
In a router having a plurality of output ports adapted to be coupled with an adjacent router, a method for determining an output port upon which to transmit a packet, the method comprising: creating a list of output ports that are coupled with the adjacent router, each of the output ports having a plurality of instances in the list, for each port in the list, providing a queue; modifying the list based on network traffic; selecting an instance of a port from the list of ports; transmitting the packet over the port corresponding to the selected instance; and wherein modifying the list includes, measuring a transmission rate for each of the ports having a plurality of instances in the list of ports using a rate counter, finding one or more instances of a second port which is over-utilized based on the measured transmission rate, finding one or more instances of a first port which is under-utilized based on the measured transmission rate, and substituting in the list one instance of the second port which is over-utilized with one instance of the first port which is under-utilized, at least one instance of the second port in the list being unmodified.