Wide field indexing for packet tracking
View Patent ↗Methods, apparatus, and computer readable storage media for accumulating traffic statistics. A traffic receiver may receive a packet and determine a flow identifier associated with the received packet. A hash function may be applied to the flow identifier to generate a memory pointer. One or more records may be retrieved from a statistics memory based on the memory pointer. A determination may be made if the flow identifier associated with the received packet matches a flow identifier value contained in one of the one or more retrieved records. When a match occurs, the retrieved record containing the matching flow identifier value may be updated and the updated record may be stored in the statistics memory.
1. A method to accumulate traffic statistics, comprising: receiving a packet; determining a flow identifier associated with the received packet; applying a hash function to the flow identifier to generate an address pointer; retrieving one or more records from a statistics memory based on the address pointer, the one or more records being a portion of a total number of records stored in the statistics memory, each of the one or more records containing a respective flow identifier; determining if the flow identifier associated with the received packet matches the flow identifier value contained in one of the one or more retrieved records; when a match occurs updating the retrieved record containing the matching flow identifier value, and storing the updated record in the statistics memory, when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records, determining whether or not each of the one or more retrieved records contains valid statistics data; and when one or more retrieved records is identified as not containing valid statistics data, initializing the identified record based on the received packet and storing the initialized record in the statistics memory.
2. The method of claim 1 , wherein determining a flow identifier associated with the received packet comprises: extracting one or more fields from the received packet, applying masks to the one or more extracted fields; and combining unmasked bits from the extracted fields to form the flow identifier.
3. The method of claim 1 , wherein the statistics memory is configured to store a plurality of records, logically organized as a table with c columns and r rows, where r and c are integers greater than one, and retrieving one or more records comprises retrieving c records from a row identified by the address pointer.
4. The method of claim 3 , wherein applying a hash function comprises applying a cyclic redundancy check polynomial to the flow identifier to generate the address pointer.
5. The method of claim 1 , wherein initializing the identified record comprises: setting a value for a number of received packets field within the identified record to one; and writing the flow identifier associated with the received packet to a flow identifier field within the identified record.
6. The method of claim 5 , wherein initializing the empty record further comprises:
writing a latency time of the received packet to one or more of a minimum latency time field, a maximum latency time field, and an average latency time field within the identified record.
7. The method of claim 1 , further comprising: when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records and all of the one or more retrieved records contain valid statistics data, incrementing a counter indicating a number of collisions.
8. A traffic receiver, comprising: a statistics memory configured to store a plurality of records; and logic circuits configured to: receive a packet; determine a flow identifier associated with the received packet; apply a hash function to the flow identifier to generate an address pointer; retrieve one or more records from the statistics memory based on the address pointer, the one or more records being a portion of a total number of records store in the statistics memory, each of the one or more records containing a respective flow identifier value; determine if the flow identifier associated with the received packet matches the flow identifier value contained in one of the one or more retrieved records; when a match occurs, update the retrieved record containing the matching flow identifier value and store the updated record in the statistics memory; when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records, determining whether or not each of the one or more retrieved records contains valid statistics data; and when one or more retrieved records is identified as not containing valid statistics data, initializing the identified record based on the received packet and storing the initialized record in the statistics memory.
9. The traffic receiver of claim 8 , the logic circuits further configured to: extract one or more fields from the received packet; apply predetermined masks to the one or more extracted fields; and combine unmasked bits from the extracted fields to form the flow identifier.
10. The traffic receiver of claim 8 , wherein the statistics memory is logically organized as a table with c columns and r rows, where c and r are integers greater than one, and the one or more records retrieved from the statistics memory is c records from a row identified by the address pointer.
11. The traffic receiver of claim 10 , the logic circuits further configured to apply a cyclic redundancy check polynomial to the flow identifier to generate the address pointer.
12. The traffic receiver of claim 8 , wherein the logic circuits are configured to initialize the identified record by actions including: setting a value of a number of received packets field within the identified record to one, and writing the flow identifier associated with the received packet to a flow identifier field within the identified record.
13. The traffic receiver of claim 12 , wherein the logic circuits are configured to initialize the identified record by further actions including:
writing a latency time of the received packet to one or more of a minimum latency time field, a maximum latency time field, and an average latency time field within the identified record.
14. The traffic receiver of claim 8 , the logic circuits further configured to: when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records and all of the one or more retrieved records contain valid statistics data, incrementing a counter indicating a number of collisions.
15. A machine-readable storage medium storing configuration data that, when used to configure one or more programmable logic devices, causes the programmable logic devices to include logic circuits configured to: receive a packet; determine a flow identifier associated with the received packet; apply a hash function to the flow identifier to generate an address pointer; retrieve one or more records from the statistics memory based on the address pointer, the one or more records being a portion of a total number of records store in the statistics memory, each of the one or more records containing a respective flow identifier value; determine if the flow identifier associated with the received packet matches the flow identifier value contained in one of the one or more retrieved records; when a match occurs, update the retrieved record containing the matching flow identifier value and store the updated record in the statistics memory; when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records, determining whether or not each of the one or more retrieved records contains valid statistics data; and when one or more retrieved records is identified as not containing valid statistics data, initializing the identified record based on the received packet and storing the initialized record in the statistics memory.
16. The machine-readable storage medium of claim 15 , the logic circuits further configured to: extract one or more fields from the received packet; apply predetermined masks to the one or more extracted fields; and combine unmasked bits from the extracted fields to form the flow identifier.
17. The machine-readable storage medium of claim 15 , wherein the statistics memory is logically organized as a table with c columns and r rows, where c and r are integers greater than one, and the one or more records retrieved from the statistics memory are c records from a row identified by the address pointer.
18. The machine-readable storage medium of claim 15 , the logic circuits further configured to apply a cyclic redundancy check polynomial to the flow identifier to generate the address pointer.
19. The machine-readable storage medium of claim 15 , wherein the logic circuits are configured to initialize the identified record by actions including: setting a value of a number of received packets field within the identified record to one, and writing the flow identifier associated with the received packet to a flow identifier field within the identified record.
20. The machine-readable storage medium of claim 19 , wherein the logic circuits are configured to initialize the identified record by further actions including:
writing a latency time of the received packet to one or more of a minimum latency time field, a maximum latency time field, and an average latency time field within the identified record.
21. The machine-readable storage medium of claim 15 , the logic circuits further configured to: when the flow identifier associated with the received packet does not match any of the flow identifier values contained in the one or more retrieved records and all of the one or more retrieved records contain valid statistics data, incrementing a counter indicating a number of collisions.