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

Сетевой переключатель между несколькими очередями обслуживает m входящих очередей, обеспечивая пересылку пакетов данных, поступающих в m входных портов, через один выходной порт. На каждом временном отрезке на входные порты может поступить произвольное число пакетов, но только один пакет может пройти через общий выходной порт. Каждому пакету присвоена метка стоимости, указывающая его приоритет в сети с гарантированным качеством обслуживания (Quality of Service, QoS). Поскольку каждая очередь имеет ограниченную емкость B, а скорость поступления пакетов может быть намного выше скорости передачи, из-за недостаточного размера очереди часть пакетов может быть потеряна. Цель заключается в максимизации пропускной способности, которая определяется как суммарная стоимость переданных пакетов. Задача включает два взаимозависимых аспекта: управление буфером, а именно – принятие решения о том, какие пакеты следует пропускать в очереди, и планирование, т.е. определение того, какую очередь (по принципу FIFO) использовать для пересылки на каждом временном отрезке.

'''Задача 1 (задача с единичной стоимостью)'''. Стоимость каждого пакета равна 1. Поскольку все пакеты в этом случае оказываются одинаково важны, это упрощает политику контроля допуска: все поступающие пакеты должны быть помещены в очередь; в случае переполнения буфера не имеет значения, какие пакеты сохраняются в очереди и какие отбрасываются.

'''Задача 2 (задача общего вида)'''. Каждый пакет имеет индивидуальную стоимость, обычно принадлежащую к диапазону <math>[1, \alpha]</math>, заданному для всех пакетов. Специальный случай задачи имеет дело с двухточечной моделью, в которой стоимость пакетов принимает одно из значений <math> \{ 1, \alpha \}</math>.

'''Алгоритм SGR (полужадный)'''

На каждом временном отрезке алгоритм выполняет первое правило, применяя его к текущей конфигурации буфера.

1. Если имеется очередь, у которой в буфере находится более <math>\lfloor B/2 \rfloor</math> пакетов, обслужить очередь, имеющую в текущий момент максимальную нагрузку.

2. Если имеется очередь, максимальная нагрузка которой до сих пор была меньше B, обслужить среди этих очередей ту, которая в текущий момент имеет максимальную нагрузку.

3. Обслужить очередь, имеющую в текущий момент максимальную нагрузку. В случае ничьей (выбора между очередями с одинаковой нагрузкой) выбрать очередь с наименьшим индексом. Максимальная до настоящего момента нагрузка сбрасывается до значения 0 у всех очередей во всех случаях, когда все очереди в конфигурации SGR оказываются незаполненными.

'''Теорема 5 [3]. Алгоритм <math>E^{M^{\hat{EP'}}}</math> (который не будет здесь описываться подробно), основанный на алгоритме уровня воды и использующий частичное соответствие в графе, строящемся в онлайновом режиме, имеет коэффициент конкурентоспособности <math>e/(e - 1) (1 + (\lfloor H_m + 1 \rfloor)/B)</math>, где <math>H_m</math> обозначает m-е гармоническое число. Таким образом, <math>E^{M^{\hat{EP'}}}</math> является асимптотически <math>\frac{e}{e - 1}</math>-конкурентным для <math>B \gg log \; m</math>.'''

'''Теорема 7 (Обобщение техники [9]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, то существует рандомизированный c-конкурентный алгоритм <math>\tilde{A}</math> для всех B.'''

'''Алгоритм RS (случайный план)'''

'''Алгоритм RP (случайная перестановка)'''

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

Техника редукции общего вида позволяет ограничиться исследованием задач об управлении буфером с одной очередью. Ее можно применить к 1,75-конкурентному алгоритму PG, предложенному Бансалом и коллегами [7], который обеспечивает лучшее на настоящий момент соотношение и является основой алгоритма <math>GS^{PG}</math>, 3,5-конкурентного в случае буферов с несколькими очередями (при этом 3,5 все же выше коэффициента конкурентоспособности алгоритма TLH, равного 3). В рамках модели с вытеснением для двух вариантов стоимости Лоткер и Пэтт-Шамир [8] представили ''алгоритм разметки и сброса'' (mark&flush algorithm) mf, являющийся 1,30-конкурентным для буферов с одной очередью, который при помощи техники редукции общего вида можно преобразовать в 2,60-конкурентный алгоритм <math>GS^{mf}</math> для буферов с несколькими очередями.

Для общей модели без вытеснения Энделман и др. [2] представили политику для случая с одной очередью под названием «''карусель с экспоненциальными интервалами''» (Exponential-Interval Round-Robin, EIRR), являющуюся <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентной, и доказали более низкую границу, составляющую <math>\Theta(log \; a)</math>. Для случая буфера с несколькими очередями техника редукции общего вида позволяет получить <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентный алгоритм без вытеснения.