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

Техника редукции общего вида позволяет ограничиться исследованием задач об управлении буфером с одной очередью. Ее можно применить к 1,75-конкурентному алгоритму PG, предложенному Бансалом и коллегами [7], который обеспечивает лучшее на настоящий момент соотношение и является основой алгоритма <math>GS^{PG}</math>, 3,5-конкурентного в случае буферов с несколькими очередями (при этом 3,5 все же выше коэффициента конкурентоспособности алгоритма TLH, равного 3). В рамках модели с вытеснением для двух вариантов стоимости Лоткер и Пэтт-Шамир [8] представили ''алгоритм разметки и сброса'' (mark&flush algorithm) mf, являющийся 1,30-конкурентным для буферов с одной очередью, который при помощи техники редукции общего вида можно преобразовать в 2,60-конкурентный алгоритм <math>GS^{mf}</math> для буферов с несколькими очередями.

Для общей модели без вытеснения Энделман и др. [2] представили политику для случая с одной очередью под названием «''карусель с экспоненциальными интервалами''» (Exponential-Interval Round-Robin, EIRR), являющуюся <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентной, и доказали более низкую границу, составляющую <math>\Theta(log \; a)</math>. Для случая буфера с несколькими очередями техника редукции общего вида позволяет получить <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентный алгоритм без вытеснения.