4670
правок
Обмен пакетами при переключении между несколькими очередями: различия между версиями
Материал из WEGA
Обмен пакетами при переключении между несколькими очередями (посмотреть исходный код)
Версия от 09:14, 11 января 2020
, 11 января 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Теорема 9 [9]. Рандомизированный алгоритм RP является 3/2-конкурентным для B = 1. Согласно теореме 7, существует рандомизированный алгоритм <math>\tilde{RP}</math>, являющийся 3/2-конкурентным для произвольного B. | '''Теорема 9 [9]. Рандомизированный алгоритм RP является 3/2-конкурентным для B = 1. Согласно теореме 7, существует рандомизированный алгоритм <math>\tilde{RP}</math>, являющийся 3/2-конкурентным для произвольного B.''' | ||
'''Пакеты с произвольной стоимостью''' | '''Пакеты с произвольной стоимостью''' | ||
Определение 1. Алгоритм переключения ALG называется алгоритмом, основанным на сравнении, если он основывает свои решения на относительном порядке стоимостей пакетов (выполняя только сравнения), безотносительно их фактических значений. | Определение 1. Алгоритм переключения ALG называется ''алгоритмом, основанным на сравнении'', если он основывает свои решения на относительном порядке стоимостей пакетов (выполняя только сравнения), безотносительно их фактических значений. | ||
Теорема 10 (Принцип «ноль-один» [ ]). Пусть ALG – основанный на сравнении алгоритм переключения (детерминированный или рандомизированный). ALG является c-конкурентным в том и только том случае, если он достигает c-конкурентности для всех последовательностей пакетов, стоимость которых ограничена интервалом {0, 1} при любом способе разрешения ничьей при равной стоимости. | '''Теорема 10 (Принцип «ноль-один» [5]). Пусть ALG – основанный на сравнении алгоритм переключения (детерминированный или рандомизированный). ALG является c-конкурентным в том и только том случае, если он достигает c-конкурентности для всех последовательностей пакетов, стоимость которых ограничена интервалом {0, 1} при любом способе разрешения ничьей при равной стоимости.''' | ||
| Строка 92: | Строка 92: | ||
Поместить новый пакет в очередь, если | Поместить новый пакет в очередь, если | ||
• очередь неполна | • очередь неполна | ||
• либо пакет с наименьшей стоимостью в очереди имеет более низкую стоимость по сравнению с новым пакетом. В этом случае пакет наименьшей стоимости будет отброшен, а новый пакет будет помещен в очередь. | • либо пакет с наименьшей стоимостью в очереди имеет более низкую стоимость по сравнению с новым пакетом. В этом случае пакет наименьшей стоимости будет отброшен, а новый пакет будет помещен в очередь. | ||
| Строка 103: | Строка 105: | ||
Теорема 11 [ | '''Теорема 11 [5]. Алгоритм THL является 3-конкурентным.''' | ||
| Строка 113: | Строка 115: | ||
'''Алгоритм: | '''Алгоритм: <math>GS^A</math> (переключатель общего вида)''' | ||
1. Управление буфером: применять политику A управления буфером для всех m входных очередей. | 1. Управление буфером: применять политику A управления буфером для всех m входных очередей. | ||
2. Планирование: запустить симуляцию алгоритма TL (в ослабленной модели с возможностью вытеснения) с онлайновой входной последовательностью | 2. Планирование: запустить симуляцию алгоритма TL (в ослабленной модели с возможностью вытеснения) с онлайновой входной последовательностью <math>\sigma</math>. Принять все решения о планировании алгоритма TL, т. е. на каждом временном отрезке переслать пакет в заголовке очереди, используемой симулятором TL. | ||
Теорема 12 (редукция общего вида [ ]). Обозначим за | '''Теорема 12 (редукция общего вида [12]). Обозначим за <math>GS^A</math> алгоритм, полученный в результате выполнения алгоритма GS с политикой A управления буфером с одной очередью на основе событий (с вытеснением или без него), а за CA – коэффициент конкурентоспособности A. Коэффициент конкурентоспособности <math>GS^A</math> удовлетворяет соотношению <math>c_{GS^A} \le 2 \cdot C_A</math>.''' | ||
== Применение == | == Применение == | ||
