Hashing of network packet flows for efficient searching

摘要

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.

主权项

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; andsearching 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.