Multi-queue packet processing using Patricia tree
View Patent ↗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.
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.