Шектелген ресурстарды бөлісу алгоритмі: Әділ кезек құру

Scheduling algorithm for sharing of limited resources
Fair queuing is a family of scheduling algorithms used in some process and network schedulers. The algorithm is designed to achieve fairness when a limited resource is shared, for example to prevent flows with large packets or processes that generate small jobs from consuming more throughput or CPU time than other flows or processes. Fair queuing is implemented in some advanced network switches and routers.

The term fair queuing was coined by John Nagle in 1985 while proposing round robin scheduling in the gateway between a local area network and the internet to reduce network disruption from badly behaving hosts. A byte weighted version was proposed by Alan Demers, Srinivasan Keshav and Scott Shenker in 1989, and was based on the earlier Nagle fair queuing algorithm. The byte weighted fair queuing algorithm aims to mimic a bit per bit multiplexing by computing theoretical departure date for each packet. The concept has been further developed into weighted fair queuing, and the more general concept of traffic shaping, where queuing priorities are dynamically controlled to achieve desired flow quality of service goals or accelerate some flows.

Fair queuing uses one queue per packet flow and services them in rotation, such that each flow can "obtain an equal fraction of the resources". and fairness index.

The initial idea gives to each flow the same rate. A natural extension consists in letting the user specify the portion of bandwidth allocated to each flow leading to weighted fair queuing and generalized processor sharing.

This algorithm attempts to emulate the fairness of bitwise round robin sharing of link resources among competing flows. Packet based flows, however, must be transmitted packetwise and in sequence. The byte weighted fair queuing algorithm selects transmission order for the packets by modeling the finish time for each packet as if they could be transmitted bitwise round robin. The packet with the earliest finish time according to this modeling is the next selected for transmission. The complexity of the algorithm is O(log(n)), where n is the number of queues/flows.

Modeling of actual finish time, while feasible, is computationally intensive. The model needs to be substantially recomputed every time a packet is selected for transmission and every time a new packet arrives into any queue. To reduce computational load, the concept of virtual time is introduced. Finish time for each packet is computed on this alternate monotonically increasing virtual timescale. While virtual time does not accurately model the time packets complete their transmissions, it does accurately model the order in which the transmissions must occur to meet the objectives of the full featured model. Using virtual time, it is unnecessary to recompute the finish time for previously queued packets. Although the finish time, in absolute terms, for existing packets is potentially affected by new arrivals, finish time on the virtual time line is unchanged the virtual time line warps with respect to real time to accommodate any new transmission. The virtual finish time for a newly queued packet is given by the sum of the virtual start time plus the packet's size. The virtual start time is the maximum between the previous virtual finish time of the same queue and the current instant. With a virtual finishing time of all candidate packets (i. e., the packets at the head of all non empty flow queues) computed, fair queuing compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is transmitted.