Previous

Content  

Next

2.5.- SFQ queuing discipline

  

Stochastic Fairness Queuing (SFQ) belongs to the family of queuing disciplines based on the fair queuing algorithm. This algorithm was proposed by John Nagle in 1987. Let's build our explanation beginning with Chuck [11] approach to this issue including a very nice figure to clear what we are studying:
Fair queuing (FQ) was proposed by John Nagle in 1987. FQ is the foundation for a class of queue scheduling disciplines that are designed to ensure that each flow has fair access to network resources and to prevent a bursty flow from consuming more than its fair share of output port bandwidth. In FQ, packets are first classified into flows by the system and then assigned to a queue that is specifically dedicated to that flow. Queues are then serviced one packet at a time in round­robin order. Empty queues are skipped. FQ is also referred to as per­flow or flow­based queuing. (See Figure 2.5.1)
 

 
FQ is like having several doors. When a packet arrives it is classified by the classifier and assigned to one of the doors. The door is the entry to a queue that is served together with some other, one packet at a time in a round-robin order. This way the service is 'fair' for every queue.
 
The key to classify a flow is a conversation, this means, a numeric representation based on the tuple [source address, source port, destination address]. More sophisticated implementations can use the tuple [source address, source port, destination address, protocol] for classification. Because it is not practical to have one queue for each conversation SFQ employs a hashing algorithm which divides the traffic over a limited number of queues. Let's see a summary of how people from Lartc [7] define this discipline:
 
   

 
Stochastic Fairness Queueing (SFQ) is a simple implementation of the fair queueing algorithms family. It is less accurate than others, but it also requires less calculations while being almost perfectly fair.
The key word in SFQ is conversation (or flow), which mostly corresponds to a TCP session or a UDP stream. Traffic is divided into a pretty large number of FIFO queues, one for each conversation. Traffic is then sent in a round robin fashion, "giving each session the chance to send data in turn".
"This leads to very fair behaviour and disallows any single conversation from drowning out the rest". SFQ is called "Stochastic" because it does not really allocate a queue for each session, it has an algorithm which divides traffic over a limited number of queues using a hashing algorithm.
Because of the hash, multiple sessions might end up in the same bucket, which would halve each session is chance of sending a packet, thus halving the effective speed available. To prevent this situation from becoming noticeable, SFQ changes its hashing algorithm quite often so that any two colliding sessions will only do so for a small number of seconds.
It is important to note that "SFQ is only useful in case your actual outgoing interface is really full!" If it is not then there will be no queue on your linux machine and hence no effect. Later on we will describe how to combine SFQ with other qdiscs to get a best-of-both worlds situation.
Some concepts have to be stood out here: first, SFQ allocates a pretty large number of FIFO queues; as was said it is not practical to have one queue for each connection or conversation. Nevertheless, increasing as large as possible the number of queues helps the fairness of the algorithm. Also, each queue is a FIFO queue. Don't forget this; we will touch this theme again when talking about RED queuing discipline later. Because number of queues are normally less than number of flows, a hashing mechanism is implemented to assign flows based on their tuple representation, to queues. Assignment is stochastic and a disturb mechanism has to be implemented to reconfigure hashing trying to improve fairness. Parameters are simple, let's see from Lartc [7]:
The SFQ is pretty much selftuning:
perturb
  Reconfigure hashing once this many seconds. If unset, hash will never be reconfigured. Not
recommended. "10 seconds is a good value."
 quantum
  Amount of bytes a stream is allowed to dequeue before the next queue gets a turn. Defaults to 1
maximum sized packet (MTU-sized). "Do not set below the MTU!"
And configuration is a dream:

You can have some statistics using the 'tc show' command; again from Lartc [7]:
  # tc -s -d qdisc show # -s = statistics; -d = details
  qdisc sfq 800c: dev eth0 quantum 1514b limit 128p flows 128/1024 perturb 10sec
Sent 4812 bytes 62 pkts (dropped 0, overlimits 0)
  • The number 800c: is the automatically assigned handle number.
  • Limit means that 128 packets can wait in this queue.
  • There are 1024 hashbuckets available for accounting, of which 128 can be active at a time (no more packets fit in the queue!).
  • Once every 10 seconds, the hashes are reconfigured.
Okay. SFQ is a very friendly queuing discipline. Because it deals with so many queues to manage as many flows as possible it is well suitable to put some order on them. Have you thought the same as we have? Of course, when we have a 'default PHB' many flows escape this way, therefore, this is a job made-to-order of our hero, the SFQ discipline. Let's reconfigure our PRIO example for having AF11 flows on class 1:1, AF21 flows on class 1:2 and rest of the flows (a default PHB) on class 1:3. We will put a TBF qdisc to control throughput on classes 1:1 and 1:2 and a SFQ qdisc on class 1:3. First, our well-known diagram:
 

 
and then, the configuration commands:
 

 
   

 
The third filter command says: anything unmatched so far should go to class 1:3, the next-higher priority.
Well, we finished with SFQ. At this place of our trip RED queuing discipline time has come.
   

Previous

Content  

Next