Fair queuing

Fair queuing is a family of scheduling algorithms used in network switches and routers, and in some process schedulers, to share a limited resource fairly among competing flows or jobs. Instead of serving packets strictly in arrival order, which lets a flow of large packets or a burst of traffic crowd out the rest, it keeps one queue per flow and serves the queues in rotation, so that each active flow receives an equal fraction of the link, on average the link rate divided by the number of active flows. The term was coined by John Nagle in 1985, in a proposal for round-robin scheduling at the gateway between a local network and the internet, and a byte-weighted version by Alan Demers, Srinivasan Keshav and Scott Shenker followed in 1989. That version orders packets by the finish time they would have under bit-by-bit round-robin sharing, tracked on a virtual clock, and its selection step costs time logarithmic in the number of flows. The idea was later developed into weighted fair queuing and the wider practice of traffic shaping.