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

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

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

'''Теорема 1 [3]. При <math>\beta = 4</math> конкурентоспособности алгоритма MPG составляет 1,75.'''

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

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