Method and apparatus for sorting packets in packet schedulers using a connected trie data structure

摘要

A method and apparatus for sorting packets by packet schedulers using a connected trie data structure is described. According to one embodiment of the invention, the packet scheduler receives a packet on a network and assigns the packet a time stamp value. The packet is inserted into a trie data structure that represents a scheduling horizon and includes a plurality of packets. The packet scheduler transmits the packet over the network based on its sorted order within the trie data structure.