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

[[Буферизация]]

Рассмотрим систему буферизации с гарантированным качеством обслуживания (QoS), способную хранить ''B'' пакетов. Время квантовано. В начале временного отрезка поступает набор пакетов (возможно, пустой), а в конце этого отрезка один пакет может покинуть буфер для передачи. Поскольку буфер имеет ограниченный размер, в какой-то момент может возникнуть необходимость отбрасывания пакетов. Алгоритм управления буфером должен на каждом временном отрезке решать, какие из пакетов отбросить, а какие передать, учитывая ограниченную емкость буфера. Стоимость пакета обозначим за v(p). Системе присваивается стоимость пакетов, которые она отправляет, в противном случае прибавки стоимости не происходит. Цель алгоритма управления буферами заключается в максимизации совокупной стоимости переданных пакетов.

   2. В противном случае отбросить (вытеснить) пакет p0, имеющий минимальную стоимость среди всех пакетов бучера и p. Если p' /p, принять p.

   0. Вытеснить (отбросить) первый пакет p0 согласно порядку FIFO, такой, что v(p0) < v(p)//S, если таковой существует (p вытесняет p0).

   0'. Найти первый (т. е. ближайший к началу буфера) пакет p0, такой, что его стоимость ниже v{p)lf$ и не выше стоимости пакета, следующего за p0 в буфере (если таковой существует). Отбросить найденный пакет (p вытесняет 0).

В работе [7] показано, что при условии f$ = 15 коэффициент конкурентоспособности жадного алгоритма с вытеснением (PG) составляет 1,983. Довольно сложный анализ выполняется при помощи присваивания значений пакетов, обслуживаемых оффлайновым алгоритмом, пакетам, обслуживаемым алгоритмом PG.

Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до p2 в работе [ ] и затем до 1.419.

Модификацию алгоритма PG предложили Бансал, Флейшер, Кимбрел, Мадьян, Шибер и Свириденко [3]. В этой версии правило 0 заменено правилом 00.

Таким образом, изменение по сравнению с исходным алгоритмом PG заключается в том, что модифицированный алгоритм находит «локальнооптимальный» пакет для исключения. Обозначим модифицированный жадный алгоритм с вытеснением как MPG.

'''Теорема 1 [3]. Для f$ = 4 конкурентоспособности алгоритма MPG составляет 1,75.'''

Для доказательства вначале было показано, что для анализа эффективности работы MPG достаточно рассмотреть только экземпляры входных данных, у которых стоимость каждого пакета равна либо 0, либо f$l для некоторого i > 0, но при этом допускается разрешение ситуаций с ничьей при помощи противника.

Затем авторы определили структуру интервалов для экземпляров входных данных. Интервал I имеет тип i, если на каждом шаге t 2 экземпляр IMPG выдает пакет стоимостью не меньше ft', при этом I является максимальным интервалом с таким свойством.

Ii – это набор максимальных интервалов типа i, а I – объединение всех коллекций Ii. Оно является мультимножеством, поскольку интервал типа i также может входить в интервал одного или нескольких типов j < i.

Этот подход порождает структуру интервалов, представляющую собой естественную последовательность упорядоченных корневых деревьев: корнем каждого дерева является интервал из %, а потомками каждого интервала I 2 Ii являются все максимальные интервалы типа i + 1, содержащиеся в I. Эти потомки упорядочены слева направо по времени, также как и сами деревья. Интервалы типа i (и представляющие их вершины) различаются по тому, был или не был на этом интервале исключен пакет стоимостью не менее f$l.

В завершение доказательства авторы показали, что для каждой структуры интервалов T коэффициент конкурентоспособности алгоритма MPG на экземплярах со структурой интервалов T может быть ограничен решением линейной программы, индексированной T. Наконец, было показано, что для любого T и любого /3 > 4 решение этой программы не превышает 2 — 1/f$.

Это приводит к возникновению задачи принятия решений в сетевых переключателях, когда прибывают несколько пакетов и происходит перегрузка. Вышеописанный алгоритм может использоваться для максимизации производительности работы сети с гарантированным качеством обслуживания.

Несмотря на значительное улучшение верхней границы для этой задачи, разрыв все же довольно велик. Сгалл [5] показал что алгоритм PG не уступает MPG по эффективности. Позднее Энглерт и Вестерманн [4] показали, что коэффициент конкурентоспособности алгоритма PG не выше p3 & 1:732 и не ниже 1 + 1/2 p2 fa 1:707. Таким образом, для дальнейшего улучшения требуется иной алгоритм.