This content originally appeared on DEV Community and was authored by Amir Keshavarz
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:
- Source Address
- Destination Address
- 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.
-
w: a fixed width -
d: pairwise-independent hash functions -
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
- Calculate the hash of your event using the hash function
h1. - Normalize the hash value to the
wso you would get an index. - Increment the element
w[hash]by 1. - Repeat the process for all hash functions in
d.
Estimation
- Calculate the hash of your event using the hash function
h1. - Normalize the hash value to the
wso you would get an index. - Get the value of element
w[hash]. - Repeat the process for all hash functions and then jump to
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
- We require 2 parameters to create a CMS object.
w: the width of our table andd: number of hash functions. - We pre-populate the tables with zeros. Notice that one dimension is
sand the otherwwhich is basically a matrix. - This is our hash function. It requires 2 parameters.
xwhich is the input andseedthat is used to seed the mmh3 hash function.seedneeds to be unique for eachd. Later you'll see that I used the index ofdelements 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 towto generate an index forwarrays. - In the
addfunction, we should iterate over all hash function elements (d). - For each element, we calculate a hash which itself is an index for
warrays. Now we have an index for both dimension and increment the value by one. - In the
getfunction like the one inadd, we iterate over all hash function elements (d). - 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. - 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("128.3.202.200")
sketch.add("128.3.202.200")
print(sketch.get("128.3.202.200")) # 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
This content originally appeared on DEV Community and was authored by Amir Keshavarz
Amir Keshavarz | Sciencx (2021-06-17T15:01:01+00:00) Rate Limiting in IPv6 Era Using Probabilistic Data Structures. Retrieved from https://www.scien.cx/2021/06/17/rate-limiting-in-ipv6-era-using-probabilistic-data-structures/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.