Generalized processor sharing

Generalized Processor Sharing (GPS) was developed as a service discipline to share the capacity of congested communications links in an efficient, flexible and fair manner. It isn't really possible to implement Generalized Processor Sharing exactly since it assumes fluid traffic (infinitessimal 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 Queueing (WFQ) also known as Packet-by-Packet Generalized Processor Sharing (PGPS).

More Detail

In network such as the internet, different application types require different performance from the network. For example, email is a genuinely store and forward kind of application, but video conferencing 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.

Some thought yields that a weighted round robin over the application types would make sense. Application type i is assigned a weight $w_{i}$, (assume that the weights for all the applicaiton types add up to 1) and in every "round" of the round robin, the server would serve each application type in proportion to its weight. More precisely, suppose that in a given round, $B$ is the set of application types that actually 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 Processing Sharing simply assumes that the traffic is fluid so that whenever an application type has packets in the queue, it will receive a fraction of the server given by the formula above. GPS can be analyzed in many kinds of situations so that anetwork performance can be predicted. But clearly, traffic is not fluid and consists of packets, possibly of variable sizes. Then why bother with GPS? Simply because it is possible to approximate the GPS ideal with clever packet based service disciplines, and then the analytical results of GPS can be applied to these realizable service disciplines in order to predict their performance.

GPS, and service disciplines that approximate it, have been studied extensively in over past decade. The first papers on this are listed as references although there are clearly many more.

References

[1] A. Demers, S. Keshav, and S. Shenkar, "Analysis and simulation of a fair queueing algorithm", Proceedings of SIGCOMM ’89, (1989), pp. 1–12.

[2] A. K. Parekh and R. G. Gallager. "A Gener- alized Processor Sharing approach to °ow con- trol in Integrated Services Networks|The Single Node Case." Proceedings of IEEE Infocom 1992.