Generalized Processor Sharing

Generalized Processor Sharing (GPS)cite journal|first=A. K.|last=Parekh|coauthors=Gallager, R. G.|title=A Generalized Processor Sharing approach to Flow control in Integrated Services Networks: The Single Node Case|journal=Proceedings of IEEE Infocom|year=1992] 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 (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) cite journal|first=A.|last=Demers|coauthors=Keshav, S.; Shenker, S.|title=Analysis and simulation of a fair queueing algorithm|journal=Proceedings of SIGCOMM ’89|year=1989|pages=1–12] 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 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 application 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\_iover\; sum\_\{jin\; 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 network 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 the past decade. The first couple of papers on the subject are listed as references although there are clearly many more.

See also

* Fair queuing
* Weighted fair queuing
* Statistical multiplexing

References