Suppose a router uses fair queuing with three input classes, and uses the quantum algorithm of 18.5.2 Different Packet Sizes and Virtual Finishing Times. The first class sends packets of size 900 bytes, the second sends packets of 400 bytes, and the third sends packets of 200 bytes. List what would be sent by each flow in each of the first five rounds.

This is what is in 18.5.2 Different Packet Sizes and Virtual Finishing Times If not all the packets are the same size, fair queuing and weighted fair queuing are still possible but we have a little more work to do. This is an important practical case, as fair queuing is often used when one input class consists of small-packet real-time traffic. We present two mechanisms for handling different-sized packets; the two are ultimately equivalent. The first 18.5.3 Bit-by-bit Round Robin is a straightforward extension of the round-robin idea, and the second 18.5.4 The GPS Model uses a fluid model of simultaneous packet transmission. Both mechanisms share the idea of a virtual clock that runs at a rate inversely proportional to the number of active subqueues; as we shall see, the point of varying the clock rate in this way is so that the virtual-clock time at which a given packet would theoretically finish transmission does not depend on activity in any of the other subqueues.

Finally, we present the quantum algorithm 18.5.5 The Quantum Algorithm which is a more-efficient approximation to either of the exact algorithms, but which being an approximation no longer satisfies a sometimes-important time constraint.

For a straightforward generalization of the round-robin idea to different packet sizes, we start with a simplification: let us assume that each per-class subqueue is always active, where a subqueue is active if it is nonempty whenever the router looks at it.

If each subqueue is always active for the equal-sized-packets case, then packets are transmitted in order of increasing (or at least nondecreasing) cumulative data sent by each subqueue. In other words, every subqueue gets to send its first packet, and only then do we go on to begin transmitting second packets, and so on.

Still assuming each subqueue is always active, we can handle different-sized packets by the same idea. For packet P, let CP be the cumulative number of bytes that will have been sent by Ps subqueue as of the end of P. Then we simply need to send packets in nondecreasing order of CP.

Variable-packet-sized fair queuing with all subqueues active Packet transmission order: Q1, P1, R1, Q2, Q3, R2, Q4, Q5, P2, R3, R4, P3, Q6 P1 P3 Q1 P2 Q2 Q3 Q4 Q5 Q6 R1 R2 R3 R4 In the diagram above, transmission in nondecreasing order of CP means transmission in left-to-right order of the vertical lines marking packet divisions, eg Q1, P1, R1, Q2, Q3, R2, .... This ensures that, in the long run, each subqueue gets an equal share of bandwidth.

A completely equivalent strategy, better suited for generalization to the case where not all subqueues are always active, is to send each packet in nondecreasing order of virtual finishing times, calculated for each packet with the assumption that only that packets subqueue is active. The virtual finishing time FP of packet P is equal to CP divided by the output bandwidth. We use finishing times rather than starting times because if one packet is very large, shorter packets in other subqueues that would finish sooner should be sent first.