Introduction to Policing
When you get a subscription from an ISP (for example a fibre connection) you will pay for the bitrate that you desire, for example 5, 10 or 20 Mbit. The fibre connection however is capable of sending traffic at a much higher bitrate (for example 100 Mbit). In this case the ISP will “limit” your traffic to whatever you are paying for. The contract that you have with the ISP is often called the traffic contract. The bitrate that you pay for at the ISP is often called the CIR (Committed Information Rate). Limiting the bitrate of a connection is done with policing or shaping. The difference between the two is that policing will drop the exceeding traffic and shaping will buffer it.
If you are interested to see how shaping works you should read my “traffic shaping explained” article. The logic behind policing is completely different than shaping. To check if traffic matches the traffic contract the policer will measure the cumulative byte-rate of arriving packets and the policer can take one of the following actions:
- Allow the packet to pass.
- Drop the packet.
- Remark the packet with a different DSCP or IP precedence value.
When working with policing there are three categories that we can use to see if a packet conforms the traffic contract or not:
Conforming means that the packet falls within the traffic contract, exceeding means that the packet is using up the excess burst capability and violating means that it’s totally out of the traffic contract rate. Don’t worry if you don’t know what “excess burst” is, we’ll talk about it in a bit. We don’t have to work with all 3 categories…we can also use just 2 of them (conforming and exceeding for example). It’s up to us to configure what will happen when a packet conforms, exceeds or violates.
When we use 2 categories (conforming and exceeding) we’ll probably want the packet to be forwarded when it’s conforming and dropped when it’s exceeding. When we use 3 categories we can forward the packet when it’s conforming, re-mark it when exceeding and drop it when violating. There are 3 different policing “techniques” that we have:
- Single rate, two-color (one token bucket).
- Single rate, three-color (two token buckets).
- Dual rate, three-color (two token buckets).
The single/dual rate, two/three color and “token bucket” thing might sound confusing so let’s walk through all 3 policer techniques so I can explain them to you:
Single rate, two color (one token bucket):
The basic idea behind a token bucket is pretty simple. Every now and then we put tokens in the bucket (we call this replenishing) and each time a packet arrives the policer will check if it has enough tokens in the bucket. If there are enough tokens, the packet is allowed, if not, we will drop it. Just like a real bucket, it can only hold a limited amount of tokens. In reality it’s a bit more complicated so let’s continue and dive into the details!
When we use token buckets for policing there are two important things that happen:
- Tokens are replenished into the token bucket.
- When a packet arrives, the policer will check if there are enough tokens in the bucket to allow the packet to get through.
When a packet arrives the policer will check if it has enough tokens in the token bucket, if so the packet will be forwarded and the policer will take the tokens out of the token bucket. So what is a ‘token’ anyway? When it comes to policing each token represents a single byte.
The second question is how does the policer replenish the the tokens in the token bucket?
Each time a packet is policed, the policer will put some tokens into the token bucket. The number of tokens that it will replenish can be calculated with the following formula:
Packet arrival time - Previous packet arrival time * Police Rate / 8
So the number of tokens that we put in the bucket depends on the time between two arriving packets. This time is in seconds. We will multiply the time with the police rate and divide it by 8. Dividing it by 8 is done so that we have a number in bytes instead of bits.
Let’s look at an example so that this makes more sense:
Imagine we have a policer that is configured for 128.000 bps (bits per second). A packet has been policed and it takes exactly 1 second until the next packet arrives. The policer will now calculate how much tokens it should put in the bucket:
1 second * 128.000bps / 8 = 16.000 bytes
So it will put 16.000 tokens into the token bucket. Now imagine a third packet will arrive, a half second later than the second packet…this is how we calculate it:
0.5 second * 128.000bps / 8 = 8.000 bytes
That means we’ll put 8.000 tokens into the bucket. Basically the more often we replenish the token bucket, the less tokens you’ll get. When the bucket is full our tokens are spilled and discarded.
Now when a packet arrives at the policer this is what will happen:
- If the number of bytes in the packet is less or equal than the number of tokens in the bucket, the packet is conforming. The policer takes the tokens out of the bucket and performs the action that we configured for conforming.
- If the number of bytes in the packet is large than the number of tokens in the bucket, the packet is exceeding. The policer will leave the tokens in the bucket and performs the action for exceeding packets.
With this single rate two-color policer conforming probably means to forward the packet, and exceeding means to drop it. You can also choose to remark exceeding packets.
Let’s continue with the second type of policer!
Single rate, three-color (two token buckets):
Data traffic is not ‘smooth’ like VoIP but it’s bursty. Sometimes we send a lot of packets…then it’s quiet again, couple of packets, etc. Because of this it makes sense to allow the policer to burst. This means we can temporarily send (burst) more packets than normally. When we want the policer to support this we will use two buckets. The first bucket is for Bc (committed burst) tokens and the second one for Be (excess burst) tokens. I’ll explain the two buckets in a second! By allowing the two buckets we can use three categories:
To understand how bursting works we first need to talk about the two token buckets. Let me show you a picture:
Above we see two buckets…I call them the ‘bc’ bucket and the ‘be’ bucket. Just like the single rate policer the first bucket is replenished using the following formula:
Packet arrival time - Previous packet arrival time * Police Rate / 8
When we use a single bucket, and the bucket is full we will discard the tokens. With two buckets it works differently. Above you can see that once the Bc bucket is full the ‘spillage’ will end up in the Be bucket. If the Be bucket is full then the tokens will go where no token has gone before…they are gone forever! Armed with the two buckets the policer will work as following when a packet arrives:
- When the number of bytes in the packet is less or equal than the number of tokens in the Bc bucket the packet is conforming. The policer takes the required tokens from the Bc bucket and performs the configured action for conforming.
- If the packet is not conforming and the number of bytes in the packet is less than or equal to the number of tokens in the Be bucket, the packet is exceeding. The policer will remove the required tokens from the Be bucket and performs the corresponding action for exceeding packets.
- If the packet is not conforming or exceeding it is violating. The policer doesn’t take any tokens from the Bc or Be bucket and will perform the action that was configured for violating packets.
Simply said, if we can use the Bc bucket our packets are conforming, when we use the Be bucket we are exceeding and when we don’t use any bucket it is violating.
How are you doing so far? We have one more policer type to cover!
Dual rate, three-color (two token buckets):
The dual rate policer with two token buckets also has a bursting feature but it works differently compared to the previous (single rate, three-color, two token buckets) policer that we discussed. Dual rate means that we don’t work with a single rate but we have a CIR and PIR (Peak Information Rate). This new PIR is above the CIR and allows us to burst.
- Packets that fall under the CIR are conforming.
- Packets that exceed the CIR but are below the PIR are exceeding.
- Packets above the PIR are violating.
A picture says more than a thousand words and this is very true when it comes to our policers and token buckets. Let me show you how these buckets work:
This time we have two buckets next to each other. The second bucket is called the PIR bucket and it’s not filled by spilled tokens from the Bc bucket but filled directly. So how are the buckets filled now? When we configure this dual rate policer we have to set a CIR and PIR rate. Let’s say we have a CIR rate of 128.000 bps and a PIR rate of 256.000 bps. We still have the same formula to replenish tokens: