Patent ID: 7760747
Filing Date: 2010-07-20
Classification: H04L

Abstract:
1. A network router comprising: queues storing data packets to be forwarded; and a scheduler which selects queues from which data packets are directly forwarded, the scheduler comprising: scheduling values associated with the queues; and a selection network by which the scheduling values at an input to the selection network are compared to select one of the data packets to be forwarded from the queues, and by which a changed scheduling value at the input to the selection network is compared to other scheduling values throughout the selection network to select a next data packet to be forwarded, the data packet associated with the changed scheduling value at the input to the selection network being eligible for selection as the next data packet to be forwarded through a full cormparison of all scheduling values throughout the selection network; wherein the selection network is a tree structure where each leaf of the tree structure represents one of the scheduling values of one of the queues and internal nodes of the tree structure represent winners in comparisons of scheduling values of sibling nodes of the tree structure, winners in successive comparisons being identified in each of successive nodes of the tree structure.