Multi-queue packet processing using Patricia tree

• US 7,792,129 B2
• Filed: 12/01/2006
• Issued: 09/07/2010
• Est. Priority Date: 12/01/2006
• Status: Active Grant

• Current Assignee: Lenovo International Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Rodriguez, Jorge R., Balakrishnan, Ganesh
• Primary Examiner(s): Wilson; Robert W
• Application Number:
  US11/565,668
• Publication Number:
  US 20080130668A1
• Time in Patent Office: 1,376 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6285 Provisions for avoiding starvation of low priority queues

Abstract

Aspects of the invention provide an improved solution for processing packets in a packetized communications network. For example, a next packet in a set of incoming packets placed in a plurality of queues is selected by obtaining a random/pseudo-random search key and identifying one of the plurality of queues based on the search key and a Patricia tree that includes at least one child node for each of the plurality of queues. A greedy algorithm can be used to select an alternative queue should the first selected queue be empty.

Claims

1. A method of processing packets, the method comprising:

selecting a next packet from one of a plurality of queues for storing packets using a computer device, the selecting including;

obtaining a search key, the search key comprising at least one of a random or a pseudo-random value; and

identifying one of the plurality of queues based on the search key and a Patricia tree that includes at least one child node for each of the plurality of queues, wherein the Patricia tree implements a relative weight for each of the plurality of queues.

2. The method of claim 1, further including:

removing the next packet from the identified one of the plurality of queues; and

scheduling the next packet for processing.

3. The method of claim 1, the selecting further including:

determining that the identified one of the plurality of queues is empty; and

identifying an alternative one of the plurality of queues based on at least one property of the plurality of queues.

4. The method of claim 3, the at least one property comprising at least one of:

a number of packets in each of the plurality of queues or a length of packets in each of the plurality of queues.

5. The method of claim 3, the identifying the alternative being further based on at least one of:

a controller bandwidth or a link bandwidth.

6. The method of claim 1, further comprising storing an incoming packet in one of the plurality of queues based on a priority for the incoming packet.

7. The method of claim 1, further comprising processing the selected next packet.

8. A system for processing packets, the system comprising:

a computing device including;

a selecting system for selecting a next packet from one of a plurality of queues for storing packets, the system for selecting including;

an obtaining a system for obtaining a search key, the search key comprising at least one of a random or a pseudo-random value; and

a first identifying system for identifying one of the plurality of queues based on the search key and a Patricia tree that includes at least one child node for each of the plurality of queues, wherein the Patricia tree implements a relative weight for each of the plurality of queues.

9. The system of claim 8, further including:

a removing system for removing the next packet from the identified one of the plurality of queues; and

a scheduling system for scheduling the next packet for processing.

10. The system of claim 8, the system for selecting further including:

a determining system for determining that the identified one of the plurality of queues is empty; and

a second identifying system for identifying an alternative one of the plurality of queues based on at least one property of the plurality of queues.

11. The system of claim 8, further comprising a storing system for storing an incoming packet in one of the plurality of queues based on a priority for the incoming packet.

12. The system of claim 8, further comprising a next packet processing system for processing the selected next packet.

13. The system of claim 8, wherein the packets comprise storage requests in a storage network.

14. A computer program comprising program code stored on a non-transitory computer readable storage medium which when executed by a computer system performs the following steps:

selecting a next packet from one of a plurality of queues for storing packets, the selecting including;

obtaining a search key, the search key comprising at least one of a random or a pseudo-random value; and

identifying one of the plurality of queues based on the search key and a Patricia tree that includes at least one child node for each of the plurality of queues, wherein the Patricia tree implements a relative weight for each of the plurality of queues.

15. The computer program of claim 14, the method further including:

removing the next packet from the identified one of the plurality of queues; and

scheduling the next packet for processing.

16. The computer program of claim 14, the selecting further including:

determining that the identified one of the plurality of queues is empty; and

identifying an alternative one of the plurality of queues based on at least one property of the plurality of queues.

17. The computer program of claim 16, the at least one property comprising at least one of:

a number of packets in each of the plurality of queues or a length of packets in each of the plurality of queues.

18. The computer program of claim 14, the method further comprising storing an incoming packet in one of the plurality of queues based on a priority for the incoming packet.

19. The computer program of claim 14, the method further comprising processing the selected next packet.

20. A method of generating a system for processing packets, the method comprising:

providing a computer system configured to;

select a next packet from one of a plurality of queues for storing packets, the selecting including;

obtaining a search key, the search key comprising at least one of a random or a pseudo-random value; and

identifying one of the plurality of queues based on the search key and a Patricia tree that includes at least one child node for each of the plurality of queues, wherein the Patricia tree implements a relative weight for each of the plurality of queues.