Обмен пакетами при переключении между несколькими очередями: различия между версиями

Обозначим за P множество перестановок {1, ..., m}, называемых m-кортежами. Выберем <math>\pi \in P</math> с учетом равномерного распределения и зафиксируем его. На каждом шаге пересылки выберем среди непустых очередей ту, индекс которой располагается раньше всех других в m-кортеже <math>\pi</math>.

'''Теорема 10 (Принцип «ноль-один» [5]). Пусть ALG – основанный на сравнении алгоритм переключения (детерминированный или рандомизированный). ALG является c-конкурентным в том и только том случае, если он достигает c-конкурентности для всех последовательностей пакетов, стоимость которых ограничена интервалом {0, 1} при любом способе разрешения ничьей при равной стоимости.'''

'''Алгоритм: GR (жадный)'''

'''Алгоритм: TLH (пересылка наибольшего заголовка)'''

'''Алгоритм: TL (пересылка наибольшего)'''

'''Алгоритм: <math>GS^A</math> (переключатель общего вида)'''

'''Теорема 12 (редукция общего вида [12]). Обозначим за <math>GS^A</math> алгоритм, полученный в результате выполнения алгоритма GS с политикой A управления буфером с одной очередью на основе событий (с вытеснением или без него), а за CA – коэффициент конкурентоспособности A. Коэффициент конкурентоспособности <math>GS^A</math> удовлетворяет соотношению <math>c_{GS^A} \le 2 \cdot C_A</math>.'''