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

1. A computer-implemented method comprising:

receiving a packet over a network;

assigning the packet a time stamp value;

inserting the packet into a trie data structure, wherein the trie data structure represents a scheduling horizon and the trie data structure includes a plurality of packets; and

transmitting the packet from the trie data structure over the network,

wherein each packet in the trie data structure is associated with a leaf node,

wherein each leaf node of the trie data structure represents a region of time stamps storing the plurality of packets with finish number increments in a specific region associated with each leaf node.

2. The method of claim 1 , wherein the scheduling horizon is defined for a self clocked fair queuing scheduling component of a network node system.

3. The method of claim 1 , where the leaf nodes of the trie data structure are connected into a linked list.

4. The method of claim 1 , wherein one or more of the leaf nodes are linked to a previous two leaf nodes in the linked list.

5. The method of claim 1 , wherein at least a subset of the trie data structure is dynamically allocated.

6. The method of claim 1 , wherein at least a subset of the trie data structure is dynamically deallocated.

7. The method of claim 1 , wherein the trie data structure is a connected trie data structure.

8. The method of claim 1 , wherein the trie data structure is a multibit connected trie data structure.

9. The method of claim 1 , wherein the trie data structure is a multibit connected trie data structure that uses bitmap compression.

10. The method of claim 1 , wherein one ore more of the leaf nodes are linked to a previous two leaf nodes in the linked list.

11. The method of claim 1 , wherein one or more of the leaf nodes are linked to a subsequent two leaf nodes in a linked list.

12. The method of claim 1 , further comprising fetching two leaf nodes from the linked list to be processed for transmission across the network using a single memory access.

13. The method of claim 1 , further comprising hiding enqueuing latencies using a transmission buffer.

14. The method of claim 1 , further comprising optimizing a height of the trie data structure based on a value of each connection weight and a size of each packet of the plurality of packets.

15. A system comprising:

a trie data structure, the trie data structure representing a scheduling horizon; and

a packet scheduler component, the packet scheduler component to insert a set of packets in the trie data structure, and the packet scheduler component to insert each packet into the trie data structure,

wherein each packet in the trie data structure is associated with a leaf node,

wherein the leaf nodes of the trie data structure represents a region of time stamps storing the set of packets with finish number increments in a specific region associated with each leaf node.

16. The system of claim 15 , wherein the scheduling horizon is defined for a self clocked fair queuing scheduling component of a network system.

17. The system of claim 15 , wherein the system is a network node system.

18. The system of claim 15 , wherein the leaf nodes of the trie data structure are connected into a linked list.

19. The system of claim 15 , wherein the leaf nodes of the trie data structure are connected into a doubly linked list.

20. The system of claim 15 , wherein at least a subset of the trie data structure is dynamically allocated.

21. The system of claim 15 , wherein least a subset of the trie data structure is dynamically deallocated.

22. The system of claim 15 , wherein the trie data structure is a connected trie data structure.

23. The system of claim 15 , wherein the trie data structure is a multibit connected trie data structure.

24. The system of claim 15 , wherein the trie data structure is a multibit connected trie data structure that uses bitmap compression.

25. The system of claim 15 , wherein one or more of the leaf nodes are linked to a previous two leaf nodes in the linked list.

26. The system of claim 15 , wherein one or more of the leaf nodes are linked to a subsequent two leaf nodes in a linked list.

27. The system of claim 15 , wherein the packet scheduler component further to fetch two leaf nodes from the linked list to be processed for transmission across the network using a single memory access.

28. The system of claim 15 , wherein the packet scheduler component further to hide an enqueuing latency using a transmission buffer.

29. The system of claim 15 , wherein the packet scheduler component further to optimize a height of the trie data structure based on a value of each connection weight and a size of each packet of the set of packets.

30. A machine-accessible medium that provides instructions that, if executed by a machine, will cause said machine to perform operations comprising:

receiving a packet over a network;

assigning the packet a time stamp value;

inserting the packet into a trie data structure, wherein the trie data structure represents a scheduling horizon and the trie data structure includes a plurality of packets; and

transmitting the packet from the trie data structure over the network,

wherein each packet in the trie data structure is associated with a leaf node,

wherein each leaf node of the trie data structure represents a region of time stamps storing the plurality of packets with finish number increments in a specific region associated with each leaf node.

31. The machine-accessible medium of claim 30 , wherein the scheduling horizon is defined for a self clocked fair queuing scheduling component of a network node system.

32. The machine-accessible medium of claim 30 , where the leaf nodes of the trie data structure are connected into a linked list.

33. The machine-accessible medium of claim 32 , where the leaf nodes of the trie data structure are connected into a doubly linked list.

34. The machine-accessible medium of claim 30 , wherein at least a subset of the trie data structure is dynamically allocated.

35. The machine-accessible medium of claim 30 , wherein at least a subset of the trie data structure is dynamically deallocated.

36. The machine-accessible medium of claim 30 , wherein the trie data structure is a connected trie data structure.

37. The machine-accessible medium of claim 30 , wherein the trie data structure is a multibit connected trie data structure.

38. The machine-accessible medium of claim 30 , wherein the trie data structure is a multibit connected trie data structure that uses bitmap compression.

39. The machine-accessible medium of claim 32 , wherein one or more of the leaf nodes are linked to a previous two leaf nodes in the linked list.

40. The machine-accessible medium of claim 32 , wherein one or more of the leaf nodes are linked to a subsequent two leaf nodes in a linked list.

41. The machine-accessible medium of claim 32 , further comprising fetching two leaf nodes from the linked list to be processed for transmission across the network using a single memory access.

42. The machine-accessible medium of claim 30 , further comprising hiding enqueuing latencies using a transmission buffer.

43. The machine-accessible medium of claim 30 , further comprising optimizing a height of the trie data structure based on a value of each connection weight and a size of each packet of the plurality of packets.