-
Notifications
You must be signed in to change notification settings - Fork 0
FQ Codel Packet Enqueue Mechanism
The Flow Queue CoDel (FQ-CoDel) algorithm is a combined packet scheduler and Active Queue Management (AQM) algorithm developed as part of the bufferbloat-fighting community effort. A Flow is typically identified by a 5-tuple of source IP address, destination IP address, source port number, destination port number, and protocol number. A Queue is basically a queue of packets represented internally in FQ-CoDel. In most instances, each flow gets its own queue.
FQ-CoDel classifies incoming packets into different queues by hashing the 5-tuple of protocol number, source and destination IP addresses, and source and destination port numbers. Each queue is managed by the CoDel AQM algorithm. Packet ordering within a queue is preserved, since queues have FIFO ordering.
To make its scheduling decisions, FQ-CoDel maintains two ordered lists of active queues: new and old queues. When a packet is added to a queue that is not currently active, that queue becomes active by being added to the list of new queues. Later on, it is moved to the list of old queues, from which it is removed when it is no longer active.
It takes place in the following stages:
When a packet arrives, it is first classified into the appropriate queue. By default, this is done by hashing, using a Jenkins hash function on the 5-tuple of IP protocol, source and destination IP addresses, and source and destination port numbers (if they exist) and then taking the hash value modulo the number of queues.
Once the packet has been successfully classified into a queue, it is handed over to the CoDel algorithm for timestamping. It is then added to the tail of the selected queue, and the queue's byte count is updated by the packet size. Then, if the queue is not currently active, it is added to the end of the list of new queues, and its number of credits is initiated to the configured quantum (Quantum is the maximum amount of bytes to be dequeued from a queue at once). Otherwise, the queue is left in its current queue list.
The total number of enqueued packets is compared with the configured limit. If the limit is exceeded, then queue with the largest current byte count is selected and half the number of packets from this queue (up to a maximum of 64 packets) are dropped from the head of that queue (also known as Head Drop).