Hashing of network packet flows for efficient searching
First Claim
Patent Images
1. A method comprising:
- receiving, by a network device, a data packet from a network;
parsing, by the network device, the data packet to extract a source address and a destination address;
applying, by the network device, a hash function to the source address to obtain a first hash;
applying, by the network device, a hash function to the destination address to obtain a second hash;
concatenating, by the network device, the first and second hashes to generate a hash index for the data packet,wherein the hash index defines a packet flow to which the data packet belongs;
storing, by the network device, the first and second hashes in a hash index;
identifying, by the network device, packets in a packet store that have a network address corresponding to the source address or the destination address by;
applying a hash function to the network address to obtain an address hash; and
searching a memory bucket where;
a particular quantity of most significant digits of a hash index of the memory bucket form the address hash, ora particular quantity of least significant digits of the hash index of the memory bucket form the address hash.
4 Assignments
0 Petitions
Accused Products
Abstract
The invention relates to a method and apparatus for efficient storing and retrieval of captured data packets. The packets are parsed to extract flow defining parameters such as source and destination addresses, the extracted addresses are hashed and the address hash numbers are reversibly combined, for example concatenated in a pre-defined order of their values to obtain a single hash index for a flow. The packets are then saved in a packet store in accordance and/or association with their hash index. The packets may be efficiently retrieved based on the two addresses or on a single network address.
-
Citations
20 Claims
-
1. A method comprising:
-
receiving, by a network device, a data packet from a network; parsing, by the network device, the data packet to extract a source address and a destination address; applying, by the network device, a hash function to the source address to obtain a first hash; applying, by the network device, a hash function to the destination address to obtain a second hash; concatenating, by the network device, the first and second hashes to generate a hash index for the data packet, wherein the hash index defines a packet flow to which the data packet belongs; storing, by the network device, the first and second hashes in a hash index; identifying, by the network device, packets in a packet store that have a network address corresponding to the source address or the destination address by; applying a hash function to the network address to obtain an address hash; and searching a memory bucket where; a particular quantity of most significant digits of a hash index of the memory bucket form the address hash, or a particular quantity of least significant digits of the hash index of the memory bucket form the address hash. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A non-transitory computer-readable medium storing instructions, the comprising:
one or more instructions which, when executed by a processor of a device, cause the processor to; receive a data packet from a network; parse the data packet to extract a source address and a destination address; apply a hash function to the source address to obtain a first hash; apply a hash function to the destination address to obtain a second hash; separably combine the first and second hashes to generate a hash index for the data packet, wherein the hash index defines a packet flow to which the data packet belongs; store the data packet in a memory bucket, of a plurality of memory buckets included in a packet store, that is associated with the hash index, wherein the first and second hashes are concatenated in an ascending order of their respective values so that a lesser of the first and second hashes is stored in a most significant bits digits of the hash index and a greater of the first and second hashes is stored in a least significant digits of the hash index; and identify packets in the packet store that have a particular network address corresponding to the source address or the destination address by; applying a hash function to the particular network address to obtain an address hash; and identifying at least one memory bucket, of the plurality of memory buckets, where; n most significant digits of a hash index of the memory bucket form an address hash and m least significant digits of the hash index correspond to a quantity of digits that is equal to or greater than the address hash, or n least significant digits of the hash index of the memory bucket form the address hash and m most significant digits of the hash index correspond to a quantity of digits that is equal or less than the address hash. - View Dependent Claims (9, 10, 11)
-
12. A method comprising:
-
receiving, by a network device, a data packet from a network; parsing, by the network device, the data packet to extract a source address and a destination address; applying, by the network device, a hash function to the source address to obtain a first hash; applying, by the network device, a hash function to the destination address to obtain a second hash; separably combining, by the network device, the first and second hashes to generate a hash index for the data packet, wherein the hash index defines a packet flow to which the data packet belongs; storing, by the network device, the data packet in a memory bucket, of a plurality of memory buckets included in a packet store, that is associated with the hash index, wherein the first and second hashes are concatenated in a descending order of their respective values; and identifying, by the network device, packets in the packet store that have a particular network address corresponding to the source address or the destination address by; applying a hash function to the particular network address to obtain an address hash; and identifying at least one memory bucket, of the plurality of memory buckets, where; n most significant digits of a hash index of the memory bucket form an address hash and m least significant digits of the hash index correspond to a quantity of digits that is equal to or less than the address hash, or n least significant digits of the hash index of the memory bucket form the address hash and m most significant digits of the hash index correspond to a quantity of digits that is equal or greater than the address hash. - View Dependent Claims (13, 14, 15)
-
-
16. A network device comprising:
-
a network interface for receiving a packet from a network; and a packet processor, coupled to the network interface, comprising; a packet parser configured to parse the packet and extract a source address and a destination address; a hash generator configured to generate a first hash from the source address and a second hash from the destination address; a hash combiner configured to; concatenate the first and second hashes to generate a hash index for the packet, wherein the hash index defines a packet flow to which the packet belongs; and store the first and second hashes in a hash index; and a search engine configured to identify packets in a packet store that have a network address corresponding to the source address or the destination address by; applying a hash function to the network address to obtain an address hash; and searching a memory bucket where; a particular quantity of most significant digits of a hash index of the memory bucket form the address hash, or a particular quantity of least significant digits of the hash index of the memory bucket form the address hash. - View Dependent Claims (17, 18, 19, 20)
-
Specification