Browse Prior Art Database

Optimal TCP control block processing using probabilistic filtering

IP.com Disclosure Number: IPCOM000249210D
Publication Date: 2017-Feb-10
Document File: 5 page(s) / 66K

Publishing Venue

The IP.com Prior Art Database

Abstract

For each TCP connection a control block is maintained which is commonly referred as Transmission Control Block (TCB) or TCP Control Block (TCPCB). This control block is a data structure which contains the parameters for TCP connection, like source and destination IP address, source and destination port number, sequence number, window size etc. This data structure is maintained normally as hash chain, where the hashed value of source, destination IP address, source, destination port and other parameters are used to create the hash key. Now whenever a new TCP connection is made, this hash table needs to be traversed to check a particular port is already assigned with a particular source address or not. If a source port is not assigned to the particular source IP address, then that bind becomes successful and connection handshaking starts. Now the main problem in this scheme is that when we have multiple IP addresses with multiple port numbers, which will have a range till 2^16, and hence during worst case where the source IP address is not bound with the particular source port, a good amount of time is wasted to search the TCP hash buckets. To find the available port during connection establishment, instead of traversing the whole hash buckets of TCBs, we use Bloom filter which will give the availability of the port for the IP address in much faster time and efficient manner.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

1

Optimal TCP control block processing using probabilistic filtering

For each TCP connection a control block is maintained which is commonly referred as Transmission Control Block (TCB) or TCP Control Block (TCPCB). This control block is a data structure which contains the parameters for TCP connection, like source and destination IP address, source and destination port number, sequence number, window size etc. This data structure is maintained normally as hash chain, where the hashed value of source, destination IP address, source, destination port and other parameters are used to create the hash key. Now whenever a new TCP connection is made, this hash table needs to be traversed to check a particular port is already assigned with a particular source address or not. If a source port is not assigned to the particular source IP address, then that bind becomes successful and connection handshaking starts.

Now the main problem in this scheme is that when we have multiple IP addresses with multiple port numbers, which will have a range till 2^16, and hence during worst case where the source IP address is not bound with the particular source port, a good amount of time is wasted to search the TCP hash buckets.

To find the available port during connection establishment, instead of traversing the whole hash buckets of TCBs, we use Bloom filter which will give the availability of the port for the IP address in much faster time and efficient manner.

Architecture:

The architecture of the method is as described below. It uses a set of Bloom Filters [Ref 1] to store the buckets associated with each input. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

Bloom Filter summary:

The bloom filter is initialized so that the array of bits is all zeros. An example of a simplistic bloom filter, with a 16-bit field and three hash functions:

To add a pattern to the bloom filter, the pattern is hashed by each hash function in turn. Applying

2

the first hash function to the input results in a number between 1 and N. The corresponding bit in the array (indexed from 1 to N) is found and set to 1, thereby recording the output of the hash function. Then, the next hash function is used to set another bit and so on. Once all M hash functions have been applied, the search pattern will be “recorded” in the bloom filter as M bits that have been changed from 0 to 1.

Adding a pattern “A” to our simple bloom filter:

To test if a pattern is part of a bloom filter, the pattern is hashed by each hash function and the resulting bit pattern is tested against the bit array. If all the bits indexed by the hash functions are set to 1, then the pattern is probably recorded i...