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

1. Алгоритм использует m вспомогательных очередей Q1, ..., Qm размерами B1, ..., Bm (допускаются различные размеры буфера для разных портов), соответственно. Эти очереди содержат вещественные числа из интервала (0, 1), в свою очередь, каждое число помечено как маркированное или немаркированное. Изначально все очереди пусты.

2. Поступление пакета. Если новый пакет поступает в очередь qi, то алгоритм равномерно случайным образом выбирает вещественное число из интервалап (0, 1), которое вставляется в очередь Qi и помечается как немаркированное. Если при поступлении пакета очередь Qi была полна, то перед вставкой нового номера удаляется число в начале очереди.

3. Пересылка пакета. Проверим, содержат ли очереди Q1, ..., Qm какие-либо немаркированные числа. Если немаркированные числа имеются, будем считать, что самое большое такое число содержит очередь Qi. Изменим метку наибольшего числа на «маркированное» и выберем очередь qi для передачи. В противном случае (при отсутствии немаркированных чисел) следует переслать пакет из любой непустой очереди, если таковая имеется.

Теорема 8 [ ]. Рандомизированный алгоритм RS является -^—y £rf 1:58-конкурентным.

Обозначим за P множество перестановок {1, ..., m}, называемых m-кортежами. Выберем ж 2 P с учетом равномерного распределения и зафиксируем его. На каждом шаге пересылки выберем среди непустых очередей ту, индекс которой располагается раньше всех других в m-кортеже ж.

Теорема 9 [9]. Рандомизированный алгоритм RP является 32-конкурентным для B = 1. Согласно теореме 7, существует рандомизированный алгоритм RP, являющийся ^-конкурентным для произвольного B.