Approximate fair queuing on programmable switches reading notes

Approximate fair queuing on programmable switches

Approximating Fair Queueing on Reconfigurable Switches

significance

A fair bandwidth allocation scheme may be very suitable for today's data center environment , In this environment , Multiple applications with different network requirements often coexist . Some applications require low latency , Other applications require sustained throughput . Data center networks must also address challenging traffic patterns , Such as large insertion or fan in 、 Micro burst and synchronous flow , These can be effectively managed using a fair queuing mechanism . Fair queuing mechanism can also provide bandwidth guarantee for multiple tenants sharing cloud infrastructure .

Today's congestion control is mainly realized through end-to-end mechanism , There is little support from the network . Although this method simplifies the switch , And allow them to run at a very high speed , But it requires terminal hosts to cooperate to realize fair network sharing , This leads to inefficiency and poor performance isolation . If the switch can maintain the per stream state , Extract rich telemetry data from the network , And perform configurable per packet processing , Then the intelligent congestion control mechanism can be realized , Directly use the dynamic network state inside the network , And improve network performance .

Challenge

Although router mechanisms such as fair queuing ensure fair bandwidth allocation to all participants , And proved to be optimal in some ways , But they require complex flow classification 、 Buffer allocation and per packet scheduling . These factors make the cost of their implementation in high-speed switches very high .

these years , Several algorithms for fair bandwidth allocation have been proposed , But because of its inherent complexity , Rarely deployed in practice . These algorithms maintain state and perform operations on a per flow basis , This makes them 3-6 Tbps It is challenging to implement on hardware at the data rate of .

programme

In this paper , We use the emerging programmable switch to develop a fair queuing system with approximately linear operation （AFQ）. We take advantage of configurable per packet processing and the ability to maintain variable states within the switch , Achieve fair bandwidth allocation in all traversal streams . A new departure scheduler is further designed , It is called rotation strict priority scheduler , It allows us to transmit packets from multiple queues in approximately sorted order .

The fair queuing router performs the management task of each flow , To ensure fair bandwidth allocation . These tasks include message classification , Which stream does the message belong to , Buffer allocation , Whether the message of the stream is added to the queue or discarded , Which message stream is scheduled and which message stream is to be transmitted next .AFQ The key idea behind this is to approximate the components of the fair queuing scheme by using the characteristics available in the programmable switch .

Our design simulates the ideal bit by bit cycle described above （Bit-by-Bit Round Robin）BR Algorithm . Similar to this algorithm ,AFQ Polling , Each stream transmits a fixed number of bytes in each round . On arrival , Each packet is assigned a starting round number based on the number of bytes sent by the stream in the past , Packets are scheduled to be transmitted in increasing rounds . To realize this scheme, we need AFQ Number of completed rounds per active flow on the storage switch , And schedule the buffered packets in order . It must also periodically store and update the current number of rounds on the switch .

We use three key ideas to approximate fair queuing .

• Store the approximate number of stream bids in sublinear space ,
• AFQ Use a coarse-grained wheel , Only after all active streams have transmitted a configurable number of bytes through the output port will it increase .
• AFQ Take advantage of the multiple... Available on each port of these reconfigurable switches FIFO queue , Scheduling packets to leave in an approximate sort .

Open questions

Approximate effects

First , Using count minimum estimation means AFQ In case of conflict, the number of bids for packages may be overestimated . When the number of active flows grows beyond the estimated size , The possibility of conflict will increase , As a result, the scheduling time of the package is later than expected .

secondly , And BR Fair queuing algorithm is different ,AFQ Allow the active stream to send multiple bytes per round . Since the number of initial rounds is larger than the number of bids , also AFQ according to FIFO The order of buffering packets with the same number of rounds , therefore , If the switch receives packets with a higher number of bids earlier , It may be transmitted before the package with a low number of bids . This reordering may lead to unfairness in the round .

The trade-off of bytes per round

because AFQ Buffer only N Round of packets , Therefore, the bytes transmitted in each round must be carefully selected （BpR）, To balance fairness and the effective use of exchange buffers . If BpR Too big , A single stream may occupy a large portion of the buffer , This leads to unfair packet delay and discarding . If it's too small ,AFQ Packets will be discarded from a single stream burst , Although there is enough space to buffer them .

summary

This paper proposes a method called approximate fair queuing (AFQ) Fair bandwidth allocation mechanism , This mechanism is suitable for emerging programmable switches . Use the features available on the programmable switch to approximate the various mechanisms of the fair queuing scheduler . To be specific , We use the programmable switch state to approximate the state of each stream with respect to the number and time of packets transmitted forward ; We perform finite calculations on each packet , To calculate its position in the output scheduling ; We dynamically decide which exit queue to use for a given packet ; We designed a new method of leaving the team , It is called rotation strict priority scheduler , Transmit packets in approximately sorted order . Simulate on a real hardware test platform , indicate AFQ It accurately approximates the ideal queuing behavior , The performance is significantly improved compared with the existing scheme , And the cost is quite small .