Fair queuing
Fair queuing ( English for fair queuing is) a network-scheduling algorithm . The primary goal of fair queuing is the fair treatment of the sources of a transmission component, which can be achieved by assigning a separate queue to each data flow (and thus each source of the transmission component) on each output line of the transmission component . The packets from the queues are removed and sent using the round robin method . In this way each source of the transmission component is restricted to the same part of the total bandwidth of the output line.
disadvantage
A problem with fair queuing is that those senders who send long packets are preferred, as sending larger packets takes more time. This problem can be solved by expanding fair queuing: fair queuing with byte-by-byte round robin .
A second problem is that fair queuing does not take into account the priority of data flows (there is a data flow from every source ). Some sources have a higher priority than others or some data flows require a higher bandwidth than others. One solution to this problem is to expand fair queuing to weighted fair queuing .
Fair queuing with byte-by-byte round robin
In principle, fair queuing is identical to round robin, except that a separate queue is created for each source.
In order to increase fairness in packet-based networks (and not to allocate more bandwidth to the sender with the larger packets), the following fair queuing for packet-based networks can be considered:
A package n is assigned a so-called completion time . This is calculated according to the formula
where is the arrival time of the package itself and its length. is the completion time of the predecessor (same source). If the queue is empty, the transmission of the respective packet can of course begin immediately. Otherwise the transfer of the predecessor must be awaited.
example
The method therefore allows shorter packages to be pushed ahead of longer ones, because z. B. Source Q1 with 50-byte packets every 10 ms and source Q2 with 150-byte packets in 10 ms are treated as follows:
| (1) F (Q1,1) = max (0,0) + 50 = 50 (transmitted immediately, the 1st packet is in the queue for Q1)
(2) F (Q2,1) = max (0,0) + 150 = 150 (transmitted as soon as the medium is free and the virtual time reaches 1000) (3) F (Q1,2) = max (10.50) + 50 = 100 (moves forward (2), see below) (4) F (Q2,2) = max (10.150) + 150 = 300 (5) F (Q1,3) = max (20,100) + 50 = 150 (advances (4), see below) (6) F (Q2,3) = max (20,300) + 150 = 450 |
It would then be transmitted in the following order: (1) (3) (2) (5) (4) (6)
(2) (5), since we assume first-come-first-served
For the sake of simplicity, we assume that no data has been transmitted, only the order of transmission should be observed. The data is virtually piling up. Otherwise a different packet sequence could result (depending on the bandwidth).