4430
правок
Обмен пакетами при помощи одного буфера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обмен пакетами при помощи одного буфера (посмотреть исходный код)
Версия от 21:54, 3 февраля 2020
, 3 февраля 2020→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Буферизация == Постановка задачи == Рассмотрим систему бу…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим систему буферизации с гарантированным качеством обслуживания (QoS), способную хранить B пакетов. Время квантовано. В начале временного отрезка поступает набор пакетов (возможно, пустой), а в конце этого отрезка один пакет может покинуть буфер для передачи. Поскольку буфер имеет ограниченный размер, в какой-то момент может возникнуть необходимость | Рассмотрим систему буферизации с гарантированным качеством обслуживания (QoS), способную хранить ''B'' пакетов. Время квантовано. В начале временного отрезка поступает набор пакетов (возможно, пустой), а в конце этого отрезка один пакет может покинуть буфер для передачи. Поскольку буфер имеет ограниченный размер, в какой-то момент может возникнуть необходимость отбрасывания пакетов. Алгоритм управления буфером должен на каждом временном отрезке решать, какие из пакетов отбросить, а какие передать, учитывая ограниченную емкость буфера. Стоимость пакета обозначим за v(p). Системе присваивается стоимость пакетов, которые она отправляет, в противном случае прибавки стоимости не происходит. Цель алгоритма управления буферами заключается в максимизации совокупной стоимости переданных пакетов. | ||
| Строка 9: | Строка 9: | ||
В модели без вытеснения добавленные в очередь пакеты не могут быть отброшены и в какой-то момент будут переданы. В рамках этой модели наилучший | В ''модели без вытеснения'' добавленные в очередь пакеты не могут быть отброшены и в какой-то момент будут переданы. В рамках этой модели наилучший достижимый коэффициент конкурентоспособности составляет <math>\Theta (log \; \alpha)</math>, где <math>\alpha</math> – отношение максимальной и минимальной стоимостей пакетов [1, 2]. | ||
В модели с вытеснением пакеты в очереди могут в какой-то момент быть отброшены, не дождавшись обслуживания. Далее будет рассматриваться эта модель. Мансур, Пэтт-Шамир и Лэпид [9] стали первыми исследователями политик управления очередями с единственным буфером FIFO с возможностью вытеснения, доказав, что естественный жадный алгоритм (см. определение на рис. 1) обеспечивает коэффициент конкурентоспособности, не превышающий 4. Кессельман, Лоткер, Мансур, Пэтт-Шамир, Шибер и Свириденко в своей работе [6] улучшили эту границу до точного значения 2. | В ''модели с вытеснением'' пакеты в очереди могут в какой-то момент быть отброшены, не дождавшись обслуживания. Далее будет рассматриваться эта модель. Мансур, Пэтт-Шамир и Лэпид [9] стали первыми исследователями политик управления очередями с единственным буфером FIFO с возможностью вытеснения, доказав, что естественный жадный алгоритм (см. определение на рис. 1) обеспечивает коэффициент конкурентоспособности, не превышающий 4. Кессельман, Лоткер, Мансур, Пэтт-Шамир, Шибер и Свириденко в своей работе [6] улучшили эту границу до точного значения 2. | ||
Жадный алгоритм не является оптимальным, поскольку он не выполняет вытеснение пакетов до момента заполнения буфера, что может оказаться слишком поздно. Первый алгоритм, коэффициент конкурентоспособности которого строго ниже 2, предложили Кесселман, Мансур и ван Стее [7]. Этот алгоритм использует параметр | Жадный алгоритм не является оптимальным, поскольку он не выполняет вытеснение пакетов до момента заполнения буфера, что может оказаться слишком поздно. Первый алгоритм, коэффициент конкурентоспособности которого строго ниже 2, предложили Кесселман, Мансур и ван Стее [7]. Этот алгоритм использует параметр <math>\beta</math> и вводит дополнительное правило обработки поступающих пакетов, выполняемое перед правилами 1 и 2 жадного алгоритма. Это правило проиллюстрировано на рис. 2. | ||