MULTI-QUEUE PACKET PROCESSING USING PATRICIA TREE

• US 20080130668A1
• Filed: 12/01/2006
• Published: 06/05/2008
• 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
• Granted Patent: US 7,792,129 B2
• Time in Patent Office: Days
• 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, 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.

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 system for selecting a next packet from one of a plurality of queues for storing packets, the system including;

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

a 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.

9. The system of claim 8, further including:

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

a system for scheduling the next packet for processing.

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

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

a 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 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 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 computer-readable medium, which when executed, enables a computer system to implement a method of processing packets, the method comprising:

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.

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 operable 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.