Обмен пакетами при помощи одного буфера
Ключевые слова и синонимы
Буферизация
Постановка задачи
Рассмотрим систему буферизации с гарантированным качеством обслуживания (QoS), способную хранить B пакетов. Время квантовано. В начале временного отрезка в буфер поступает набор пакетов (возможно, пустой), а в конце этого отрезка один пакет может покинуть буфер для передачи. Поскольку буфер имеет ограниченный размер, в какой-то момент может возникнуть необходимость отбрасывания пакетов. Алгоритм управления буфером должен на каждом временном отрезке решать, какие из пакетов отбросить, а какие передать, учитывая ограниченную емкость буфера. Стоимость пакета p обозначим за v(p). Системе присваивается стоимость пакетов, которые она отправляет, в противном случае прибавки стоимости не происходит. Цель алгоритма управления буферами заключается в максимизации совокупной стоимости переданных пакетов.
В модели FIFO на временном отрезке t всегда передается первый (старейший) пакет буфера.
В модели без вытеснения добавленные в очередь пакеты не могут быть отброшены и в какой-то момент будут переданы. В рамках этой модели наилучший достижимый коэффициент конкурентоспособности составляет [math]\displaystyle{ \Theta (log \; \alpha) }[/math], где [math]\displaystyle{ \alpha }[/math] – отношение максимальной и минимальной стоимостей пакетов [1, 2].
В модели с вытеснением пакеты в очереди могут в какой-то момент быть отброшены, не дождавшись обслуживания. Далее будет рассматриваться эта модель. Мансур, Пэтт-Шамир и Лэпид [9] стали первыми исследователями политик управления очередями с единственным буфером FIFO с возможностью вытеснения, доказав, что естественный жадный алгоритм (см. определение на рис. 1) обеспечивает коэффициент конкурентоспособности, не превышающий 4. Кессельман, Лоткер, Мансур, Пэтт-Шамир, Шибер и Свириденко в своей работе [6] улучшили эту границу до точного значения 2.
Жадный алгоритм не является оптимальным, поскольку он не выполняет вытеснение пакетов до момента заполнения буфера, что может оказаться слишком поздно. Первый алгоритм, коэффициент конкурентоспособности которого строго ниже 2, предложили Кесселман, Мансур и ван Стее [7]. Этот алгоритм использует параметр [math]\displaystyle{ \beta }[/math] и вводит дополнительное правило обработки поступающих пакетов, выполняемое перед правилами 1 и 2 жадного алгоритма. Это правило проиллюстрировано на рис. 2.
Жадный алгоритм.
При поступлении пакета стоимостью v(p):
1. Если в буфере имеется свободное место, принять пакет p.
2. В противном случае отбросить (вытеснить) пакет p', имеющий минимальную стоимость среди всех пакетов буфера и p. Если [math]\displaystyle{ p' \ne p }[/math], принять p.
Рисунок 1. Естественный жадный алгоритм
0. Вытеснить (отбросить) первый пакет p' согласно порядку FIFO, такой, что [math]\displaystyle{ v(p') \le v(p) / \beta }[/math], если таковой существует (p вытесняет p').
Рисунок 2. Дополнительное правило для естественного жадного алгоритма
0'. Найти первый (т. е. ближайший к началу буфера) пакет p', такой, что его стоимость ниже [math]\displaystyle{ v(p) / \beta }[/math] и не выше стоимости пакета, следующего за p' в буфере (если таковой существует). Отбросить найденный пакет (p вытесняет p').
Рисунок 3. Модифицированный жадный алгоритм с вытеснением
В работе [7] было показано, что в случае [math]\displaystyle{ \beta = 15 }[/math] коэффициент конкурентоспособности жадного алгоритма с вытеснением (PG) составляет 1,983. Довольно сложный анализ выполняется при помощи присваивания стоимостей пакетов, обслуживаемых оффлайновым алгоритмом, пакетам, обслуживаемым алгоритмом PG.
Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до [math]\displaystyle{ \sqrt{2} }[/math] в работе [2] и затем до 1,419 в [7].
Основные результаты
Модификацию алгоритма PG предложили Бансал, Флейшер, Кимбрел, Мадьян, Шибер и Свириденко [3]. В этой версии правило 0 заменено правилом 0'.
Таким образом, изменение по сравнению с исходным алгоритмом PG заключается в том, что модифицированный алгоритм находит «локально оптимальный» пакет для исключения. Обозначим модифицированный жадный алгоритм с вытеснением как MPG.
Теорема 1 [3]. При [math]\displaystyle{ \beta = 4 }[/math] коэффициент конкурентоспособности алгоритма MPG составляет 1,75.
Для доказательства вначале было показано, что для анализа эффективности работы MPG достаточно рассмотреть только экземпляры входных данных, у которых стоимость каждого пакета равна либо 0, либо [math]\displaystyle{ \beta^i }[/math] для некоторого [math]\displaystyle{ i \ge 0 }[/math], но при этом допускается разрешение ситуаций с ничьей при помощи противника.
Затем авторы определили структуру интервалов для экземпляров входных данных. Интервал I имеет тип i, если на каждом шаге [math]\displaystyle{ t \in I }[/math] экземпляр MPG выдает пакет стоимостью не меньше [math]\displaystyle{ \beta^i }[/math], при этом I является максимальным интервалом с таким свойством.
[math]\displaystyle{ \mathcal{I}_i }[/math] – это набор максимальных интервалов типа i, а [math]\displaystyle{ \mathcal{I} }[/math] – объединение всех [math]\displaystyle{ \mathcal{I}_i }[/math]. Оно является мультимножеством, поскольку интервал типа i также может входить в интервал одного или нескольких типов j < i.
Этот подход порождает структуру интервалов, представляющую собой естественную последовательность упорядоченных корневых деревьев: корнем каждого дерева является интервал из [math]\displaystyle{ \mathcal{I}_0 }[/math], а потомками каждого интервала [math]\displaystyle{ I \in \mathcal{I}_i }[/math] являются все максимальные интервалы типа i + 1, содержащиеся в I. Эти потомки упорядочены слева направо по времени, также как и сами деревья. Интервалы типа i (и представляющие их вершины) различаются по тому, был или не был на этом интервале исключен пакет стоимостью не менее [math]\displaystyle{ \beta^i }[/math].
В завершение доказательства авторы показали, что для каждой структуры интервалов [math]\displaystyle{ \mathcal{T} }[/math] коэффициент конкурентоспособности алгоритма MPG на экземплярах со структурой интервалов [math]\displaystyle{ \mathcal{T} }[/math] может быть ограничен решением линейной программы, индексированной [math]\displaystyle{ \mathcal{T} }[/math]. Наконец, было показано, что для любого [math]\displaystyle{ \mathcal{T} }[/math] и любого [math]\displaystyle{ \beta \ge 4 }[/math] решение этой программы не превышает [math]\displaystyle{ 2 - 1 / \beta }[/math].
Применение
В последние годы одной из самых популярных тем стали сети с гарантированным качеством обслуживания. В обычных IP-сетях пакеты неразличимы, и в случае перегрузки любой пакет может быть отброшен. В коммерческой среде намного предпочтительнее предоставить более высокое качество обслуживания клиентам с более высокими тарифами или особыми требованиями. Идея сети с гарантированным качеством обслуживания заключается в том, что пакеты помечаются значениями стоимости, характеризующими их важность.
Это естественным образом приводит к возникновению задач принятия решений в сетевых переключателях в случаях, когда прибывают несколько пакетов и происходит перегрузка. Вышеописанный алгоритм может использоваться для максимизации производительности работы сети с гарантированным качеством обслуживания.
Открытые вопросы
Несмотря на значительное улучшение верхней границы для этой задачи, разрыв все же довольно велик. Сгалл [5] показал что алгоритм PG не уступает MPG по эффективности. Позднее Энглерт и Вестерманн [4] показали, что коэффициент конкурентоспособности алгоритма PG не выше [math]\displaystyle{ \sqrt{3} \approx 1,732 }[/math] и не ниже [math]\displaystyle{ 1 + 1/2 \sqrt{2} \approx 1,707 }[/math]. Таким образом, для дальнейшего улучшения требуется иной алгоритм.
Лоткер и Пэтт-Шамир [8] изучали специальный случай с двумя вариантами стоимости и разработали 1,3-конкурентный алгоритм, максимально приближенный к нижней границе 1,28, которую доказали Мансур и коллеги [9]. Остается решить задачу покрытия этого небольшого разрыва.
См. также
Литература
1. Aiello, W., Mansour, Y., Rajagopolan, S., Rosen, A.: Competitive queue policies for differentiated services. In: Proc. of the IEEE INFOCOM, pp. 431-440. IEEE, Tel-Aviv, Israel (2000)
2. Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies in QoS switches. In: Proc. 14th Symp. on Discrete Algorithms (SODA), pp. 761-770 ACM/SIAM, San Francisco, CA, USA (2003)
3. 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). Lecture Notes in Computer Science, vol. 3142, pp. 196-207. Springer, Berlin (2004)
4. Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in qos switches. In: Azar, Y., Erlebach, T. (eds.) Algorithms - ESA 2006, 14th Annual European Symposium, Proceedings. Lecture Notes in Computer Science, vol. 4168, pp. 352-363. Springer, Berlin (2006)
5. Jawor, W.: Three dozen papers on online algorithms. SIGACT News 36(1), 71-85 (2005)
6. Kesselman, A., Lotker, Z., Mansour, Y., Patt-Shamir, B., Schieber, B., Sviridenko, M.: Buffer overflow management in QoS switches. SIAM J. Comput. 33(3), 563-583 (2004)
7. Kesselman, A., Mansour, Y., van Stee, R.: Improved competitive guarantees for QoS buffering. In: Di Battista, G., Zwick, U. (eds.) Algorithms - ESA 2003, Proceedings Eleventh Annual European Symposium. Lecture Notes in Computer Science, vol. 2380, pp. 361-373. Springer, Berlin (2003)
8. Lotker, Z., Patt-Shamir, B.: Nearly optimal FIFO buffer management for DiffServ. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 134-142. ACM, New York (2002)
9. Mansour, Y., Patt-Shamir, B., Lapid, O.: Optimal smoothing schedules for real-time streams. In: Proc. 19th Symp. on Principles of Distributed Computing (PODC), pp. 21-29. ACM, New York (2000)