Generalized processor sharing

Generalized processor sharing (GPS)^[1] was developed as a service discipline to share the capacity of congested communications links in an efficient, flexible and fair manner. It is not possible to implement generalized processor sharing exactly since it assumes fluid traffic (infinitesimal packet sizes), but GPS is useful as a benchmark against which realizable service disciplines can be measured. There are several service disciplines which track the performance of GPS quite closely such as weighted fair queuing (WFQ) ^[2] also known as packet-by-packet generalized processor sharing (PGPS).

Details

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.

Weighted round robin over the application types assigns each application type i a weight $w_{i}$ such that the weights for all the application types add up to 1. In every "round" of the round robin, the server serves each application type in proportion to its weight. Suppose that in a given round, $B$ is the set of application types that currently have queued packets. Then the fraction of bits belonging to type i that would be served is: ${w_{i} \over \sum _{j\in B}w_{j}}.$

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 tool for benchmarking practical scheduling algorithms that approximate the GPS ideal. GPS and its approximations have been studies extensively.

References

^ Parekh, A. K. (1992). "A generalized processor sharing approach to flow control in integrated services networks: The single node case". Proceedings of IEEE Infocom. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Demers, A. (1989). "Analysis and simulation of a fair queueing algorithm". Proceedings of SIGCOMM ’89: 1–12. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[parekh-1] Parekh, A. K. (1992). "A generalized processor sharing approach to flow control in integrated services networks: The single node case". Proceedings of IEEE Infocom. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[demers-2] Demers, A. (1989). "Analysis and simulation of a fair queueing algorithm". Proceedings of SIGCOMM ’89: 1–12. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[1]

[2]

Details

See also

References