Design of hardware switch with programmable full function rate limiter

Programmable full function rate limiter design hardware switch

Fully Functional Rate Limiter Design on Programmable Hardware Switches

significance

The rate limiter is on the network QoS Management plays a key role , Such as bandwidth allocation and performance isolation .

Challenge

Rate limiters can be implemented at different locations in the network ( for example , NIC, Switch ); However , In some cases , The network operator cannot access the terminal host , Rate limiting can only be implemented on network devices ( for example , Mobile core network ,IaaS The cloud provides bare metal ).

However, the recent trend of programmable switches provides an opportunity to implement such intra network rate limits .

Although current programmable hardware switches provide a certain degree of packet processing flexibility , But there are still some constraints :

• The data flow in the switch is unidirectional , Only from the switch buffer to the switch circuit ;
• The programmability is limited to working on the switch circuit , Not applicable to buffers ;
• The computation on the switch is limited , Multiplication, division and other operations and time logic are not supported ;
• Switching memory is difficult to extend to multi stream processing .

programme

The design space of the rate limiter includes algorithm selection

• Leaking barrel
• Token bucket

Excessive traffic strategy

• Traffic shaping
• Flow regulation

Implementation method

• Based on timers
• Based on events

Due to the limitations of programmable hardware switches , We can only implement token bucket algorithm with traffic supervision .

In the rate limiting algorithm , The committed rate and burst size are configured , And maintains a variable token . Tokens accumulate over time , The burst size is used as the threshold to constrain . For each packet , If there are enough tokens , Then send a packet , Reduce tokens ; otherwise , The message will be discarded . Token accumulation over time can be achieved in two ways .

The performance of the rate limiter is insufficient due to hardware limitations : Timer based rate limiter pairs TCP unfriendly , Throughput oscillations ; The event based rate limiter is not flexible in rate control .

Since the message arrival interval of event based rate limiter is usually less than the refresh interval based on timer , Even less than RTT. such , Token accumulation 、 Update and consumption will be more timely , So as to achieve more stability 、 More accurate rate control .

However , Event based rate limiters are inflexible in rate control . Because when the token is updated , The product of time interval rates needs to be multiplied , At present, programmable hardware does not support, so only a limited rate can be configured .

Realize multiplication . In order to overcome the problem of limited computation , We propose an approximate multiplication table (AMT).AMT The key idea of is to pre calculate the intermediate results and store them in the table , Then all calculations at run time are converted into table lookups . Since arbitrary granularity and range cannot be calculated in advance ( Real number field ) The multiplication of and the product of multipliers , So it is actually an approximation algorithm . Storage space needs to be ( Particle size ) And accuracy ( The error in the result ) Trade-offs between . Again , We can also use the approximate division table (ADT) Divide .

Memory efficiency optimization . Scarce switch memory is a potential scalability limitation ( According to the number of configured rate limits ), Thus, the memory usage of token bucket algorithm is improved .

Open questions

summary

A fully functional rate limiter with the following features is implemented :

• Committed rate saturation
• Low oscillation
• Rate control flexibility
• High storage efficiency .