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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
== Ключевые слова и синонимы ==
== Ключевые слова и синонимы ==
[[Буферизация]]
Буферизация


== Постановка задачи ==
== Постановка задачи ==
Строка 19: Строка 19:


'''Жадный алгоритм.'''
'''Жадный алгоритм.'''
   При поступлении пакета стоимостью v(p):
   При поступлении пакета стоимостью v(p):
   1. Если в буфере имеется свободное место, принять пакет p.
   1. Если в буфере имеется свободное место, принять пакет p.
   2. В противном случае отбросить (вытеснить) пакет p0, имеющий минимальную стоимость среди всех пакетов бучера и p. Если p' /p, принять p.
   2. В противном случае отбросить (вытеснить) пакет p', имеющий минимальную стоимость среди всех пакетов буфера и p. Если <math>p' \ne p</math>, принять p.


Рисунок 1. Естественный жадный алгоритм
Рисунок 1. Естественный жадный алгоритм




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


Рисунок 2. Дополнительное правило для естественного жадного алгоритма
Рисунок 2. Дополнительное правило для естественного жадного алгоритма


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


Рисунок 3. Модифицированный жадный алгоритм с вытеснением
Рисунок 3. Модифицированный жадный алгоритм с вытеснением




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




Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до p2 в работе [ ] и затем до 1.419.
Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до <math>\sqrt{2}</math> в работе [2] и затем до 1,419 в [7].


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




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




Источник — http://pco.iis.nsk.su/wega/index.php/Обмен_пакетами_при_помощи_одного_буфера