# US 2021/0243123 A1 · Method and system for handling of data packet/frames using an adapted bloom filter

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0243123 A1
- Document ID: US20210243123A1
- Status: Published application
- Kind: A1
- Application number: 16/995,915
- Filed: 2020-08-18
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: Ovh
- Applicants: Ovh
- Inventors: Clement ROUSSEAU; Tristan GROLEAT
- Web page: https://patentgrep.com/patent/US20210243123A1

## CPC

- H04L 1/1642: {Formats specially adapted for sequence numbers}
- H04L 45/7453: using hashing
- G06F 11/08: Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F 16/2255: {Hash tables}
- G06F 16/24532: {of parallel queries}
- H04L 43/106: using time related information in packets, e.g. by adding timestamps
- H04L 45/7459: using Bloom filters
- H04L 49/901: using storage descriptor, e.g. read or write pointers
- H04L 67/535: {Tracking the activity of the user (network monitoring arrangements H04L43/00; recording of computer activity G06F11/34)}
- H04L 1/18: Automatic repetition systems, e.g. Van Duuren systems
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and system are disclosed for handling a received content word in a system comprising a memory of memory words, wherein: each memory word comprises Bloom Filter structures. The method comprises hashing the content word into a fixed-size word, pointing to the memory word corresponding to an address of the fixed-size word, pointing to, and reading, the Bloom Filter structure in the pointed memory word corresponding to an address in the fixed-size word, and reading and writing the content of the Bloom Filter structures so as to keep track of a number of occurrences of the received content word over a sliding window of time.

## Claims

### Claim 1

A method for handling a content word in a system comprising i (i>=1) memories of 2N memory words of R bits each, and wherein:
each memory word comprises at least 2S Bloom Filter (BF) structures;
each BF structure comprises Floor(R/2S) bits of which P bits define a Flags field, M bits define a Timestamp field, Q bits define a Counter field, such that P+M+Q=Floor(R/2S) and P is a power of 2; and
an absolute time value has increments of time units, and a current time value is the absolute time value modulo 2M;
the method comprising:
a) receiving the content word;
b) hashing the content word into i fixed-size words, each comprising 3 fields Ai, Bi, Ci, of respectively N, S and square root(P) bits;
c) pointing to i memory words, corresponding respectively to A;
d) pointing to, and reading, i BF structures respectively in the i pointed memory words, corresponding respectively to B;
e) checking whether all i pointed and read BF structures have a valid Timestamp field, and if not:
for BF structures among the i pointed and read BF structures having an invalid Timestamp field: writing a “1” in a bit of the Flags field corresponding to C, writing a “0” in all other bits of the Flags field, and resetting to “0” the Counter field; and for BF structures among the i pointed and read BF structures having a valid Timestamp field: writing a “1” in a bit of the Flags field corresponding to Ci; and
for all BF structures among the i pointed and read BF structures: updating the Timestamp field with the current time value, and going to step a);
f) checking whether all bits of the Flags field in all i pointed and read BF structures are at “1”, and if not:
writing a “1” in the bit of the Flags field corresponding to Ci; and
for all BF structures among the i pointed and read BF structures: updating the Timestamp field with the current time value, and going to step a);
g) checking whether all bits in Counter fields in all i pointed and read BF structures are at “1”, and if not:
for BF structures among the i pointed and read BF structures having a Counter field equal to the Min of Counter fields in the i pointed and read BF structures: incrementing by one the value of the Counter field; and
for all BF structures among the i pointed and read BF structures: updating the Timestamp field with the current time value, and going to step a); and
h) for all BF structures among the i pointed and read BF structures: updating the Timestamp field with the current time value, and going to step a).

### Claim 2 (depends on 1)

The method of claim 1, further comprising reading all the BF structures in all memory words of at least one of the i memories, and for each such read BF structure, checking whether the content of the Timestamp field is valid, and if not: writing a “0” in all bits of the Flags field; resetting to “0” the Counter field; and updating the Timestamp field with the current time value.

### Claim 3 (depends on 1)

The method of claim 1, wherein the content word is a concatenation of addresses including Internet Protocol source and destination addresses.

### Claim 4 (depends on 1)

The method of claim 1, wherein each BF structure comprises 4 bits for the Flags field, 4 bits for the Timestamp field, and 1 bit for the Counter field.

### Claim 5 (depends on 1)

The method claim 1, wherein a Timestamp field is valid when the absolute value of the difference between the value of the Timestamp field and the current time value is less than a predetermined value.

### Claim 6 (depends on 5)

The method of claim 5, wherein the predetermined value is 2(M−1).

### Claim 7 (depends on 2)

The method of claim 2, wherein method steps are performed at a period of time equal or less than 2(M−1) time units.

### Claim 8 (depends on 1)

The method of claim 1, wherein i is >=3 and at least two of the i fixed-size words are identical.

### Claim 9

A system for handling a content word comprising i (i>=1) memories (101) of 2N memory words of R bits each, wherein:
each memory word comprises at least 2S BF structures;
each BF structure comprises Floor(R/2S) bits of which P bits define a Flags field, M bits define a Timestamp field, Q bits define a Counter field, such that P+M+Q=Floor(R/2S) and P is a power of 2; and
an absolute time value has increments of time units, and a current time value is the absolute time value modulo 2M;
the system being configured to:
receive the content word;
hash the content word into i fixed-size words, each comprising 3 fields Ai, Bi, Ci, of respectively N, S and square root(P) bits;
point to i memory words, corresponding respectively to A;
point to, and read, i BF structures respectively in the i pointed memory words, corresponding respectively to B;
check whether all i pointed and read BF structures have a valid Timestamp field, and if not:
for BF structures among the i pointed and read BF structures having an invalid Timestamp field: write a “1” in a bit of the Flags field corresponding to C, write a “0” in all other bits of the Flags field, and reset to “0” the Counter field; and for BF structures among the i pointed and read BF structures having a valid Timestamp field: write a “1” in a bit of the Flags field corresponding to Ci; and
for all BF structures among the i pointed and read BF structures: update the Timestamp field with the current time value;
check whether all bits of the Flags field in all i pointed and read BF structures are at “1”, and if not:
write a “1” in the bit of the Flags field corresponding to Ci; and
for all BF structures among the i pointed and read BF structures: update the Timestamp field with the current time value;
check whether all bits in Counter fields in all i pointed and read BF structures are at “1”, and if not:
for BF structures among the i pointed and read BF structures having a Counter field equal to the Min of Counter fields in the i pointed and read BF structures: increment by one the value of the Counter field; and
for all BF structures among the i pointed and read BF structures: update the Timestamp field with the current time value.

### Claim 10 (depends on 9)

The system of claim 9, further configured to read all the BF structures in all memory words of at least one of the i memories, and for each such read BF structure, check whether the content of the Timestamp field is valid, and if not: write a “0” in all bits of the Flags field; reset to “0” the Counter field; and update the Timestamp field with the current time value.

### Claim 11 (depends on 9)

The system of claim 9, wherein the content word is a portion of a data packet/frame exchanged between two communicating devices, and is intercepted so as to determine whether an identical content word has been exchanged between the two communicating devices over a sliding window of absolute time.

### Claim 12 (depends on 9)

The system of claim 9, wherein the i memories are Quad Data Rate SRAMs.
