Generalized processor sharing

Generalized processor sharing (GPS) is an ideal scheduling algorithm for network schedulers.

It is related to the Fair queuing principle, that groups the packets into classes, and share the service capacity between them. The GPS shares this capacity according to some fixed weights.

In processor scheduling, generalized processor sharing is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness." 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), 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 flows (also called "classes", or "sessions") is configured with one weight ${\displaystyle w_{i}}$ for each flow. Then, the GPS ensures that, considering one flows ${\displaystyle i}$, and some time interval ${\displaystyle (s,t]}$ such that the flow ${\displaystyle i}$ is continuously backlogged on this interval (i.e. the queue is never empty), then, for any other flow ${\displaystyle j}$, the following relation holds

...
Wikipedia