Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Общее использование процессоров (GPS) — это идеальный алгоритм планирования для планировщиков процессов и сетевых планировщиков. Он связан с принципом справедливой очереди, который группирует пакеты в классы и распределяет между ними пропускную способность. GPS распределяет эту пропускную способность в соответствии с некоторыми фиксированными весами. В планировании процессов GPS представляет собой «идеализированный алгоритм планирования, достигающий абсолютной справедливости. Все практические планировщики аппроксимируют GPS и используют его в качестве эталона для измерения справедливости». Общее использование процессоров предполагает, что трафик является непрерывным (пакеты бесконечно малого размера) и может быть разделен произвольно. Существует несколько дисциплин обслуживания, которые достаточно точно воспроизводят поведение GPS, например, взвешенная справедливая очередь (WFQ), также известная как пакетное обобщенное использование процессоров (PGPS).
Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair queuing principle which groups packets into classes and shares the service capacity between them. GPS shares this capacity according to some fixed weights. In process scheduling, GPS 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.
Внедрение, параметризация и справедливость
В GPS и всех протоколах, вдохновленных GPS, выбор весов остается за администратором сети. Обобщенное совместное использование процессора предполагает, что трафик является непрерывным, то есть бесконечно делимым, так что, когда у типа приложения есть пакеты в очереди, он будет получать ровно ту долю сервера, которая задается приведенной выше формулой. Однако трафик не является непрерывным и состоит из пакетов, возможно, переменного размера. Поэтому GPS в основном представляет собой теоретическую концепцию, и было разработано несколько алгоритмов планирования для приближения к этому идеалу GPS: PGPS, также известный как взвешенная справедливая очередь, является наиболее известной реализацией GPS, но имеет некоторые недостатки, и было предложено несколько других реализаций, таких как Deficit Round Robin или WF2Q. GPS считается справедливым идеалом, и все его приближения используют его в качестве эталона для оценки справедливости. Тем не менее, существует несколько показателей справедливости. GPS нечувствителен к размерам пакетов, поскольку основывается на модели непрерывного трафика.
In GPS, and all protocols inspired by GPS, the choice of the weights is left to the network administrator. 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 idea, and several scheduling algorithms have been developed to approximate this GPS ideal: PGPS, aka Weighted fair queuing, is the most known implementation of GPS, but it has some drawbacks, and several other implementations have been proposed, as Deficit round robin or WF2Q. GPS is considered as a fair ideal, and all its approximations "use it as a reference to measure fairness." Nevertheless, several Fairness measures exist. GPS is insensible to packet sizes, since it assumes a fluid model.