Rate Limiting in IPv6 Era Using Probabilistic Data Structures

In any system where two parties communicate with each other, we hear things like rate-limiting, flow control, etc. The problem is that all systems have limits and to protect the system, you'd need to somehow control the flow of information passing through.

As you may have already figured out, we're going to talk about a specific problem regarding rate-limiting in IPv6 networks.

Packets

When we communicate through computer networks, we need to break down our data into smaller pieces called packets. These packets are basically like the letters you send through the post.

Each letter (packet) has 3 important components:

1. Source Address
2. Destination Address
3. The actual data

As you can see, real packets also have those things. (The picture only shows the IP header which doesn't include the data body)

We only care about the source and destination addresses in this context, so we call them a 2-tuple.

IP Addresses

Until now, IPv4 is still dominant in most countries but its address pool is limited, thus, It's not future-proof.

IPv6 is the successor to the IPv4 and instead of a 32-bit address, it provides 128-bit addresses so It's a huge bump in the case of the address pool.

IPv4 address pool: 4,294,967,296
IPv6 address pool: 340,282,366,920,938,463,463,374,607,431,768,211,456

Yep, that's a huge difference.

Even though IPv6 itself is not a new protocol, but the process of migrating to IPv6 from IPv4 has been a tedious and very long battle. The issue is that IPv6 is not backward compatible and lots of old hardware and software don't and will not support IPv6.

Nonetheless, IPv6 is already here and its users are rising by the day. Google's statistics show IPv6 availability of its users at around 30.30–35.10% depending on the day of the week (greater on weekends), as of April 2021.

Before continuing, you can also read another post of mine which goes through different technics on how to implement a rate-limiter:

Rate limiting using the Token Bucket algorithm

As we talked about before, that's not the case for IPv6 addresses because of its huge address pool. Even if you may see no difference in normal times, the existing risk won't be accepted by lots of people.

So what's the solution? How can we store the frequency of these events in a space-efficient data structure?
Like all solutions, we compromise.

Challenge

Even in the simplest forms of rate-limiting, we're required to store the number of times that packets with similar 2-tuple have been processed.

In most IPv4-era systems, that information is stored in an array or a tree, or some other normal data structure. They'll do the job perfectly since the IPv4 address pool is not that big so keeping all of the data won't be an issue.

For this purpose, we can use probabilistic data structures, specifically Count-Min Sketch.

Probabilistic Data Structures

Unlike normal data structures which are deterministic, probabilistic data structures are not deterministic and won't give you definite answers but only an estimation or a probability.

This kind of data structure is useful when an unknown stream of data is being processed.

You'd be amazed to find out in how many cases we don't really need deterministic data structures especially when we're processing data streams.

Probabilistic data structures are lossy but that's not really an issue for our use case since we only need to know the heavy-hitters. With an enough large space, the risk of collision should be low enough for most people.

Count-Min Sketch

The Count-Min Sketch, or CMS for short, is a probabilistic data structure to count the frequencies of events.

We can argue that the whole CMS is like a 3-D table.

1. w: a fixed width
2. d: pairwise-independent hash functions
3. c: total count of an event

w is basically an arbitrary width. The bigger it is, the lower the overestimation is.
d is a list of hash functions that shouldn't have many collisions with each other.
c is the number that we increment when an event is repeated.

The process of incrementing or estimation is really simple.

Incrementing

1. Calculate the hash of your event using the hash function h1.
2. Normalize the hash value to the w so you would get an index.
3. Increment the element w[hash] by 1.
4. Repeat the process for all hash functions in d.

Estimation

1. Calculate the hash of your event using the hash function h1.
2. Normalize the hash value to the w so you would get an index.
3. Get the value of element w[hash].
4. Repeat the process for all hash functions and then jump to 5.
5. Between all the values that you got, the lowest one is your estimation.

As you may have already guessed, the whole CMS is quite similar to other probabilistic data structures like bloom filters. It's relatively simple and quite fast.

Implementation

Now we can implement a dead simple Count-Min Sketch data structure in Python.

import mmh3

class CountMinSketch():
    def __init__(self, w, d): #1
        self.w = w
        self.d = d
        self.tables = []
        for _ in range(d):
            self.tables.append([0] * w) #2

    def hash(self, x, seed):
        return mmh3.hash(x, seed) % self.w #3

    def add(self, x):
        for i in range(self.d): #4
            self.tables[i][self.hash(x, i)] += 1 #5

    def get(self, x):
        items = []
        for i in range(self.d): #6
            items.append(self.tables[i][self.hash(x, i)]) #7
        return min(items) #8

1. We require 2 parameters to create a CMS object. w: the width of our table and d: number of hash functions.
2. We pre-populate the tables with zeros. Notice that one dimension is s and the other w which is basically a matrix.
3. This is our hash function. It requires 2 parameters. x which is the input and seed that is used to seed the mmh3 hash function. seed needs to be unique for each d. Later you'll see that I used the index of d elements for seed but that's not good :) You need to generate random numbers when creating the CMS object for each element. After generating the hash, we normalize it relative to w to generate an index for w arrays.
4. In the add function, we should iterate over all hash function elements (d).
5. For each element, we calculate a hash which itself is an index for w arrays. Now we have an index for both dimension and increment the value by one.
6. In the get function like the one in add, we iterate over all hash function elements (d).
7. Like before, we calculate the hash, and using the table index, we get the value inside and put it in a temporary array named items.
8. After going through all hash function elements (d), we select the minimum of all items and return it. This is basically our estimation.

Example

sketch = CountMinSketch(10, 10)

sketch.add("2001:0db8:85a3:0000:0000:8a2e:0370:7334")
sketch.add("2001:0db8:85a3:0000:0000:8a2e:0370:7334")

print(sketch.get("2001:0db8:85a3:0000:0000:8a2e:0370:7334")) # prints 2

Conclusion

By combining this and a simple rate-limiter explained in another post (Rate limiting using the Token Bucket algorithm
), You'll have a rate-limiter ready for IPv6.

There's lots of optimization you can do and one of them is making the object, CIDR-aware. You can also tweak the implementation or use different hash functions to get the best performance possible.

Even though we used Count-Min Sketch to store the frequency of incoming packets, but its application is extremely broad, especially when you're dealing with stream processing workloads.

This post was so fun to write and I hope you found it fun to read. :)

Links

• https://en.wikipedia.org/wiki/IPv6_deployment
• https://www.researchgate.net/figure/The-Count-Min-sketch-combines-the-counts-of-multiple-items-and-returns-the-counter_fig1_261130855
• https://www.cse.unsw.edu.au/~cs9314/07s1/lectures/Lin_CS9314_References/cm-latin.pdf