HASHING OF NETWORK PACKET FLOWS FOR EFFICIENT SEARCHING

• US 20130266014A1
• Filed: 04/09/2013
• Published: 10/10/2013
• Est. Priority Date: 04/10/2012
• Status: Active Grant

• Current Assignee: Viavi Solutions, Inc. (Lumentum Holdings Inc.)
• Original Assignee: Scott A. Blomquist
• Inventors: BLOMQUIST, Scott A.
• Granted Patent: US 9,276,853 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/7453 using hashing

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.

Claims

1. A method implemented in a network device, comprising:

receiving data packets from a network;

for each of the received packets,

a) parsing the data packet to extract a source address and a destination address therefrom;

b) applying a hash function to the source address to obtain a first hash;

c) applying a hash function to the destination address to obtain a second hash; and

,

d) separably combining 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.

2. The method of claim 1, further comprising:

e) providing a packet store comprising a plurality of memory buckets, wherein each of the memory buckets is associated with one or more hash indices, and

f) storing each of the received packet in one of the memory buckets that is associated with the hash index generated for the packet.

3. The method of claim 2, wherein step d) comprises concatenating the first and second hashes to obtain the hash index.

4. The method of claim 3, wherein the first and second hashes are concatenated in either an ascending order of their values for all received packet, or in a descending order of their values for all received packet, so that for all received packets a greater of the first and second hashes always follows or always precedes a smaller of the first or second hashes.

5. The method of claim 2, further comprising identifying all packets stored in the packet store that belong to a selected packet flow between first and second network addresses by:

i) computing the hash index for the selected packet flow following steps b) to d) using one of the first and second addresses as the source address and the other of the first and second addresses as the destination address, and

ii) searching for one or more memory buckets that are associated with the hash index computed for the selected packet flow.

6. The method of claim 4 wherein in step (d) the first and second hashes are concatenated in the ascending order of their values so that the lesser of the first and second hashes is stored in the most significant bits of the hash index and the greater of the two hashes is stored in the least significant digits of the hash index, the method further comprising identifying all packets in the packet store that have a selected network address as either the source address or the destination address, by:

applying the hash function to the selected network address to obtain an address hash, wherein the address hash is n digits long, wherein n is an integer; and

,

searching for all buckets that satisfy one of the following criteria;

n most significant digits of the hash index of the bucket form the address hash while the remaining least significant digits at the end of the hash index form a number that is equal or greater than the address hash, or

n least significant digits of the hash index of the bucket form the address hash, while the remaining most significant digits of the hash index form a number that is equal or smaller than the address hash.

7. The method of claim 4 wherein in step (d) the first and second hashes are concatenated in the descending order of their values, the method further comprising identifying all packets in the packet store that have a selected network address as either the source address or the destination address, by:

applying the hash function to the selected network address to obtain an address hash, wherein the address hash is n digits long, wherein n is an integer; and

,

searching for all buckets that satisfy one of the following criteria;

n most significant digits of the hash index of the bucket form the address hash while the remaining least significant digits at the end of the hash index form a number that is equal or smaller than the address hash, or

n least significant digits of the hash index of the bucket form the address hash, while the remaining most significant digits of the hash index form a number that is equal or greater than the address hash.

12. The method of claim 1, further including extracting one or more additional data fields from the packet and applying one or more hash functions thereto to obtain one or more additional hashes therefrom, and wherein step d) comprises separably combining the first hash, the second hash and the one or more additional hashes to obtain the hash index.

13. The method of claim 12, wherein step d) comprises concatenating the first hash, the second hash, and the one or more additional hashes in a same ascending or descending order of their values for each of the received packets.

14. The method of claim 12, wherein the one or more additional data fields comprise at least one of:

a VLAN tag, an MPLS tag, a source port number, a destination port number, a protocol identifier (such as the “

Protocol”

field in an IP header), or a quality of service parameter.

8. A network device, comprising:

a network interface for receiving packets from a network,

a packet processor coupled to the network interface and comprising;

a packet parser for parsing each of the received packets for extracting therefrom a source address and a destination address;

a hash generator for generating a first hash from the source address and a second hash from the destination address; and

,

a hash combiner for combining 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.

9. The network device of claim 8, further including a processor usable memory coupled to the packet processor for implementing a packet store for storing the received packets, wherein the packet processor comprises a memory interface for individually associating the hash indices with memory buckets defined within the packet store, and for storing each of the received packets in one of the memory buckets associated with the hash index generated for the packet.

10. The network device of claim 9, wherein the hash combiner is configured for generating the hash index by concatenating the first and second hashes in an ascending order of their values for each of the received packets.

11. The network device of claim 9, wherein the hash combiner is configured for generating the hash index by concatenating the first and second hashes in a descending order of their values for each of the received packets.