Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS shares this capacity according to some fixed weights.[1]
In process scheduling, GPS is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness."[2]
Generalized processor sharing assumes that traffic is fluid (infinitesimal packet sizes), and can be arbitrarily split. There are several service disciplines which track the performance of GPS quite closely such as weighted fair queuing (WFQ),[3] also known as packet-by-packet generalized processor sharing (PGPS).
In a network such as the internet, different application types require different levels of performance. For example, email is a genuinely store and forward kind of application, but videoconferencing isn't since it requires low latency. When packets are queued up on one end of a congested link, the node usually has some freedom in deciding the order in which it should send the queued packets. One example ordering is simply first-come, first-served, which works fine if the sizes of the queues are small, but can result in problems if there are latency-sensitive packets being blocked by packets from bursty, higher bandwidth applications.
In GPS, a scheduler handling
N
wi
i
(s,t]
i
j
wjOi(s,t)\geqwiOj(s,t)
Ok(s,t)
k
(s,t]
Then, it can be proved that each flow
i
Ri=
| wi | |||||||||
|
R
R
This is a minimal rate. If some flow does not use its bandwidth during some period, this remaining capacity is shared by the active flows with regard to their respective weights. For example, consider a GPS server with
w1=2,w2=w3=1
(s,t]
In GPS, and all protocols inspired by GPS, the choice of the weights is left to the network administrator.
Generalized processor sharing assumes that the traffic is fluid, i.e., infinitely divisible so that whenever an application type has packets in the queue, it will receive exactly the fraction of the server given by the formula above. However, traffic is not fluid and consists of packets, possibly of variable sizes. Therefore, GPS is mostly a theoretical idea, and several scheduling algorithms have been developed to approximate this GPS ideal: PGPS, aka Weighted fair queuing, is the most known implementation of GPS, but it has some drawbacks, and several other implementations have been proposed, as Deficit round robin or WF2Q.[4]
GPS is considered as a fair ideal, and all its approximations "use it as a reference to measure fairness."[2] Nevertheless, several Fairness measures exist.
GPS is insensible to packet sizes, since it assumes a fluid model.