Generalized Processor Sharing
Encyclopedia
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 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) also known as packet-by-packet generalized processor sharing (PGPS).
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
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, 
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:
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 studied extensively.
Infinitesimal
Infinitesimals have been used to express the idea of objects so small that there is no way to see them or to measure them. The word infinitesimal comes from a 17th century Modern Latin coinage infinitesimus, which originally referred to the "infinite-th" item in a series.In common speech, an...
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
Weighted fair queuing
Weighted fair queuing is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows.WFQ is a generalization of fair queuing . Both in WFQ and FQ, each data flow has a separate FIFO queue...
(WFQ) 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 forwardStore and forward
Store and forward is a telecommunications technique in which information is sent to an intermediate station where it is kept and sent at a later time to the final destination or to another intermediate station. The intermediate station, or node in a networking context, verifies the integrity of...
kind of application, but videoconferencing
Videoconferencing
Videoconferencing is the conduct of a videoconference by a set of telecommunication technologies which allow two or more locations to interact via two-way video and audio transmissions simultaneously...
isn't since it requires low latency
Low latency
Low latency allows human-unnoticeable delays between an input being processed and the corresponding output providing real time characteristics. This can be especially important for internet connections utilizing services such as online gaming and VOIP....
. 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
Weighted round robin
Weighted round robin is a scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing...
over the application types assigns each application type i a weight
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, 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: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 studied extensively.