Обмен пакетами при переключении между несколькими очередями
Ключевые слова и синонимы
Онлайновая буферизация пакетов; онлайновая маршрутизация пакетов
Постановка задачи
Сетевой переключатель между несколькими очередями обслуживает m входящих очередей, обеспечивая пересылку пакетов данных, поступающих в m входных портов, через один выходной порт. На каждом временном отрезке на входные порты может поступить произвольное число пакетов, но только один пакет может пройти через общий выходной порт. Каждому пакету присвоена метка стоимости, указывающая его приоритет в сети с гарантированным качеством обслуживания (Quality of Service, QoS). Поскольку каждая очередь имеет ограниченную емкость B, а скорость поступления пакетов может быть намного выше скорости передачи, из-за недостаточного размера очереди часть пакетов может быть потеряна. Цель заключается в максимизации пропускной способности, которая определяется как суммарная стоимость переданных пакетов. Задача включает два взаимозависимых аспекта: управление буфером, а именно – принятие решения о том, какие пакеты следует пропускать в очереди, и планирование, т.е. определение того, какую очередь (по принципу FIFO) использовать для пересылки на каждом временном отрезке.
Различаются два сценария:
(а) с единичной стоимостью пакетов (все пакеты имеют одинаковую стоимость) и
(б) с произвольной стоимостью пакетов.
Задача рассматривается как онлайновая, то есть на любом временном отрезке t известны только пакеты, поступающие на этом отрезке, и ничего не известно о пакетах, которые поступят в будущем. Эффективность онлайновых переключателей в QoS-сетях изучается при помощи конкурентного анализа, в ходе которого пропускная способность онлайнового алгоритма сравнивается с пропускной способностью оптимального оффлайнового алгоритма, знающего всю последовательность пакетов заранее.
Если не указано иное, предполагается, что контроль допуска разрешает вытеснение, т. е. пакеты, однажды попавшие в очередь, не обязательно должны быть переданы и могут быть отброшены.
Задача 1 (задача с единичной стоимостью). Стоимость каждого пакета равна 1. Поскольку все пакеты в этом случае оказываются одинаково важны, это упрощает политику контроля допуска: все поступающие пакеты должны быть помещены в очередь; в случае переполнения буфера не имеет значения, какие пакеты сохраняются в очереди и какие отбрасываются.
Задача 2 (задача общего вида). Каждый пакет имеет индивидуальную стоимость, обычно принадлежащую к диапазону [math]\displaystyle{ [1, \alpha] }[/math], заданному для всех пакетов. Специальный случай задачи имеет дело с двухточечной моделью, в которой стоимость пакетов принимает одно из значений [math]\displaystyle{ \{ 1, \alpha \} }[/math].
Основные результаты
Пакеты с единичной стоимостью
Детерминированные алгоритмы
Теорема 1 [1]. Для любого размера буфера B коэффициент конкурентоспособности каждого детерминированного онлайнового алгоритма не может быть меньше [math]\displaystyle{ (e_B + \frac{2}{B}) / (e_B - 1 + \frac{1}{B}) \ge \frac{e}{e - 1} \approx 1,58 }[/math], где [math]\displaystyle{ e_B = ((B + 1)/B)^B }[/math].
Теорема 2 [4]. Каждый сохраняющий работу онлайновый алгоритм является 2-конкурентным.
Теорема 3 [1]. Для любого размера буфера B коэффициент конкурентоспособности любого жадного алгоритма, который всегда обслуживает самую длинную очередь (LQF), не может быть меньше [math]\displaystyle{ 2 - \frac{1}{B} }[/math], если [math]\displaystyle{ m \gg B }[/math].
Алгоритм SGR (полужадный)
На каждом временном отрезке алгоритм выполняет первое правило, применяя его к текущей конфигурации буфера.
1. Если имеется очередь, у которой в буфере находится более [math]\displaystyle{ \lfloor B/2 \rfloor }[/math] пакетов, обслужить очередь, имеющую в текущий момент максимальную нагрузку.
2. Если имеется очередь, максимальная нагрузка которой до сих пор была меньше B, обслужить среди этих очередей ту, которая в текущий момент имеет максимальную нагрузку.
3. Обслужить очередь, имеющую в текущий момент максимальную нагрузку. В случае ничьей (выбора между очередями с одинаковой нагрузкой) выбрать очередь с наименьшим индексом. Максимальная до настоящего момента нагрузка сбрасывается до значения 0 у всех очередей во всех случаях, когда все очереди в конфигурации SGR оказываются незаполненными.
Теорема 4 [1]. Если значение B четно, алгоритм SGR является [math]\displaystyle{ \frac{17}{9} \approx 1,89 }[/math]-конкурентным. Если значение B нечетно, алгоритм SGR является [math]\displaystyle{ \frac{17}{9} + \frac{\delta_B}{9} }[/math]-конкурентным, где [math]\displaystyle{ \delta_B = \frac{2}{B + 1} }[/math].
Теорема 5 [3]. Алгоритм [math]\displaystyle{ E^{M^{\hat{EP'}}} }[/math] (который не будет здесь описываться подробно), основанный на алгоритме уровня воды и использующий частичное соответствие в графе, строящемся в онлайновом режиме, имеет коэффициент конкурентоспособности [math]\displaystyle{ e/(e - 1) (1 + (\lfloor H_m + 1 \rfloor)/B) }[/math], где [math]\displaystyle{ H_m }[/math] обозначает m-е гармоническое число. Таким образом, [math]\displaystyle{ E^{M^{\hat{EP'}}} }[/math] является асимптотически [math]\displaystyle{ \frac{e}{e - 1} }[/math]-конкурентным для [math]\displaystyle{ B \gg log \; m }[/math].
Рандомизированные алгоритмы
Теорема 6 [1]. Коэффициент конкурентоспособности каждого рандомизированного онлайнового алгоритма не может быть меньше [math]\displaystyle{ \varrho = 1,4659 }[/math] для любого размера буфера B ([math]\displaystyle{ \varrho = 1 + \frac{1}{\alpha + 1} }[/math], где [math]\displaystyle{ \alpha }[/math] – единственный положительный корень уравнения [math]\displaystyle{ e^{\alpha} = \alpha + 2 }[/math]).
Теорема 7 (Обобщение техники [9]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, то существует рандомизированный c-конкурентный алгоритм [math]\displaystyle{ \tilde{A} }[/math] для всех B.
Алгоритм RS (случайный план)
1. Алгоритм использует m вспомогательных очередей [math]\displaystyle{ Q_1, ..., Q_m }[/math] размерами [math]\displaystyle{ B_1, ..., B_m }[/math] (допускаются различные размеры буфера для разных портов), соответственно. Эти очереди содержат вещественные числа из интервала (0, 1), в свою очередь, каждое число помечено как маркированное или немаркированное. Изначально все очереди пусты.
2. Поступление пакета. Если новый пакет поступает в очередь [math]\displaystyle{ q_i }[/math], то алгоритм равномерно случайным образом выбирает вещественное число из интервала (0, 1), которое вставляется в очередь [math]\displaystyle{ Q_i }[/math] и помечается как немаркированное. Если при поступлении пакета очередь [math]\displaystyle{ Q_i }[/math] была полна, то перед вставкой нового номера удаляется число в начале очереди.
3. Пересылка пакета. Проверим, содержат ли очереди [math]\displaystyle{ Q_1, ..., Q_m }[/math] какие-либо немаркированные числа. Если немаркированные числа имеются, будем считать, что самое большое такое число содержит очередь [math]\displaystyle{ Q_i }[/math]. Изменим метку наибольшего числа на «маркированное» и выберем очередь [math]\displaystyle{ q_i }[/math] для передачи. В противном случае (при отсутствии немаркированных чисел) следует переслать пакет из любой непустой очереди, если таковая имеется.
Теорема 8 [4]. Рандомизированный алгоритм RS является [math]\displaystyle{ \frac{e}{e - 1} \approx 1,58 }[/math]-конкурентным.
Алгоритм RP (случайная перестановка)
Обозначим за P множество перестановок {1, ..., m}, называемых m-кортежами. Выберем [math]\displaystyle{ \pi \in P }[/math] согласно равномерному распределению и зафиксируем его. На каждом шаге передачи выберем среди непустых очередей ту, индекс которой располагается раньше всех других в m-кортеже [math]\displaystyle{ \pi }[/math].
Теорема 9 [9]. Рандомизированный алгоритм RP является 3/2-конкурентным для B = 1. Согласно теореме 7, существует рандомизированный алгоритм [math]\displaystyle{ \tilde{RP} }[/math], являющийся 3/2-конкурентным для произвольного B.
Пакеты с произвольной стоимостью
Определение 1. Алгоритм переключения ALG называется алгоритмом, основанным на сравнении, если он основывает свои решения на относительном порядке стоимостей пакетов (выполняя только сравнения), безотносительно их фактических значений.
Теорема 10 (Принцип «ноль-один» [5]). Пусть ALG – основанный на сравнении алгоритм переключения (детерминированный или рандомизированный). ALG является c-конкурентным в том и только том случае, если он достигает c-конкурентности для всех последовательностей пакетов, стоимость которых ограничена интервалом {0, 1}, при любом способе разрешения ничьей при равной стоимости.
Алгоритм GR (жадный)
Поместить новый пакет в очередь, если
• очередь неполна
• либо пакет с наименьшей стоимостью в очереди имеет более низкую стоимость по сравнению с новым пакетом. В этом случае пакет наименьшей стоимости будет отброшен, а новый пакет будет помещен в очередь.
Алгоритм TLH (пересылка наибольшего заголовка)
1. Управление буфером: использовать алгоритм GR независимо для всех m входных очередей.
2. Планирование: на каждом временном отрезке переслать пакет с наибольшей стоимостью среди всех пакетов в заголовке (первой позиции) очереди.
Теорема 11 [5]. Алгоритм THL является 3-конкурентным.
Алгоритм TL (пересылка наибольшего)
1. Управление буфером: использовать алгоритм GR независимо для всех m входных очередей.
2. Планирование: на каждом временном отрезке переслать пакет с наибольшей стоимостью среди всех пакетов в очереди.
Алгоритм [math]\displaystyle{ GS^A }[/math] (переключатель общего вида)
1. Управление буфером: применять политику A управления буфером для всех m входных очередей.
2. Планирование: запустить симуляцию алгоритма TL (в ослабленной модели с возможностью вытеснения) с онлайновой входной последовательностью [math]\displaystyle{ \sigma }[/math]. Принять все решения о планировании алгоритма TL, т. е. на каждом временном отрезке переслать пакет в заголовке очереди, используемой симулятором TL.
Теорема 12 (редукция общего вида [12]). Обозначим за [math]\displaystyle{ GS^A }[/math] алгоритм, полученный в результате выполнения алгоритма GS с политикой A управления буфером с одной очередью на основе событий (с вытеснением или без него), а за [math]\displaystyle{ C_A }[/math] – коэффициент конкурентоспособности A. Коэффициент конкурентоспособности [math]\displaystyle{ GS^A }[/math] удовлетворяет соотношению [math]\displaystyle{ c_{GS^A} \le 2 \cdot C_A }[/math].
Применение
Сценарий с единичной стоимостью пакетов моделирует большинство современных сетей – например, IP-сети, поддерживающие только услуги типа "best effort" (наивысший возможный уровень сервиса), одинаковым образом обрабатывая все пакеты; сценарий с произвольной стоимостью пакетов подразумевает поддержку всего спектра возможностей QoS.
Техника редукции общего вида позволяет ограничиться исследованием задач об управлении буфером с одной очередью. Ее можно применить к 1,75-конкурентному алгоритму PG, предложенному Бансалом и коллегами [7], который обеспечивает лучшее на настоящий момент соотношение и является основой алгоритма [math]\displaystyle{ GS^{PG} }[/math], 3,5-конкурентного в случае буферов с несколькими очередями (при этом 3,5 все же выше коэффициента конкурентоспособности алгоритма TLH, равного 3). В рамках модели с вытеснением для двух вариантов стоимости Лоткер и Пэтт-Шамир [8] представили алгоритм разметки и сброса (mark&flush algorithm) mf, являющийся 1,30-конкурентным для буферов с одной очередью, который при помощи техники редукции общего вида можно преобразовать в 2,60-конкурентный алгоритм [math]\displaystyle{ GS^{mf} }[/math] для буферов с несколькими очередями.
Для общей модели без вытеснения Энделман и др. [2] представили политику для случая с одной очередью под названием «карусель с экспоненциальными интервалами» (Exponential-Interval Round-Robin, EIRR), являющуюся [math]\displaystyle{ (e \left \lceil \ln \alpha \right \rceil) }[/math]-конкурентной, и доказали более низкую границу, составляющую [math]\displaystyle{ \Theta(log \; a) }[/math]. Для случая буфера с несколькими очередями техника редукции общего вида позволяет получить [math]\displaystyle{ (e \left \lceil \ln \alpha \right \rceil) }[/math]-конкурентный алгоритм без вытеснения.
Открытые вопросы
Из теоремы 3 известно, что коэффициент конкурентоспособности любого жадного алгоритма в модели с единичной стоимостью пакетов равен не менее чем 2, если m >> B. Чему равна строгая верхняя граница жадных алгоритмов в противоположном случае B >> m?
В доказательстве нижней границы e/(e — 1) в теореме 1 используется соотношение m >> B, тогда как теорема 5 дает e/(e — 1) в качестве верхней границы для B >> log m. В работе [4] приведена нижняя граница 1,366, не зависящая от B и m. Каков оптимальный коэффициент конкурентоспособности для произвольных B и m?
Используя технику редукции общего вида из теоремы 7, можно улучшить коэффициент конкурентоспособности для алгоритмов управления буфером с несколькими очередями в случае достижения улучшенных результатов работы алгоритмов управления буфером с одной очередью. На сегодня лучшими значениями для нижней и верхней границ являются [math]\displaystyle{ \frac{\sqrt{13} + 5}{6} \approx 1,43 }[/math] [2] и 1,75 [7], соответственно. Как уменьшить разрыв между этими значениями?
См. также
Литература
1. Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. SIAM J. Comput. 35, 278-304 (2005)
2. Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies for QoS switches. In: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 761-770 (2003)
3. Azar, Y., Litichevskey, M.: Maximizing throughput in multi-queue switches. In: Proc. 12th Annual European Symp. on Algorithms (ESA), 53-64 (2004)
4. Azar, Y., Richter, Y.: Management of multi-queue switches in QoS Networks. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), 82-89 (2003)
5. Azar, Y., Richter, Y.: The zero-one principle for switching networks. In: Proc. 36th ACM Symp. on Theory of Computing (STOC), 64-71 (2004)
6. Azar, Y., Richter, Y.: An improved algorithm for CIOQ switches. In: Proc. 12th Annual European Symp. on Algorithms (ESA). LNCS, vol. 3221,65-76 (2004)
7. Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., Sviridenko, M.: Further improvements in competitive guarantees for QoS buffering. In: Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP), 64-71 (2004)
8. Lotker, Z., Patt-Shamir, B.: Nearly optimal FIFO buffer management for two packet classes. Comput. Netw. 42(4), 481-492 (2003)
9. Schmidt, M.: Packet buffering: randomization beats deterministic algorithms. In: Proc. 22nd Annual Symp. on Theoretical Aspects of Computer Science (STACS). LNCS, vol. 3404, 293-304 (2005)