Multi-queue packet processing using Patricia tree
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19)
-
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.
Specification