Сортировка элементов по циклическому порядковому номеру

Question

Я разрабатываю алгоритм для переупорядочения пакетов в передаче.Каждый пакет имеет связанный порядковый номер в [0, 256).Порядковый номер первого пакета может принимать любое из этих значений, после чего следующий пакет принимает следующее значение, а следующий пакет - значение после этого и т. Д. (Переворачивание после 255).

порядковые номера пакетов в правильном порядке будут выглядеть следующим образом, где «n» - порядковый номер первого пакета:

n, n + 1, n + 2, ...,254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, ...

Каждый пакетдается временная метка, когда он прибывает в пункт назначения, и все они прибывают примерно по порядку.(У меня нет точной цифры, но учитывая список пакетов, отсортированных по отметке времени прибытия, можно с уверенностью сказать, что пакет никогда не будет находиться на расстоянии более пяти точек от его позиции в списке, указанном его порядковым номером.)

Я чувствую, что не мог быть первым человеком, который столкнулся с такой проблемой, учитывая распространенность телекоммуникаций и ее историческое значение для развития информатики.Тогда мой вопрос:

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

2. Есть ли вариант этого алгоритма, который допускает большие фрагменты отсутствующих элементов? Предположим, что эти фрагменты могут быть любой длины.Я особенно обеспокоен кусками из 256 или более пропущенных элементов.

У меня есть несколько идей для алгоритмов для первого, но не для второго.Прежде чем я потрачу трудозатраты на проверку правильности своих алгоритмов, я хотел убедиться, что кто-то в Bell Labs (или где-либо еще) еще не сделал этого лучше тридцать лет назад.

Answer 1

Интересная проблема!

Моим решением будет сортировка пакетов по времени прибытия и локальная сортировка окна элементов (скажем, 10) по кругу в соответствии с номером их пакета. Вы можете уточнить это разными способами. Если разница между двумя последовательными номерами пакетов (расположенными в соответствии с временем прибытия) превышает определенное пороговое значение, вы можете установить барьер между ними (то есть вы не можете сортировать через барьеры). Кроме того, если разница во времени между пакетами (расположенными в соответствии с временем прибытия) больше некоторого порога, вы можете установить барьер (это, вероятно, должно решить проблему 2).

Answer 2

Я не знаю, действительно ли это решение где-либо используется, но вот что я бы попробовал (при условии отсутствия пропущенных пакетов, максимального «перемешивания» в пять позиций и максимального порядкового номера 255):

n = 0;
max_heap h = empty;
while( true ) do
  while( h.top().index != 0 ) do
    p = next_packet;
    i = n - p.seq;
    if( i > 0 ) i = i - 255;
    h.add( i, p );
  done

  p = h.pop();
  n = n + 1;
  p.increase_indexes( 1 );
  // Do something with it
done

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

Я не уверен, как вы могли бы адаптировать это к отсутствующим пакетам. Скорее всего, с использованием некоторого тайм-аута или максимального смещения, после чего пакетные данные объявляются «следующими», а куча обновляется соответствующим образом.

Я не думаю, что эта проблема вообще возможна, если вы пропустите более 256 пакетов. Возьми подпоследовательности

127,130,128,129

Может быть несколько причин для этого

1) Пакеты 128 и 129 вышли из строя и должны быть переупорядочены

2) Пакеты 128 и 129 были потеряны, затем было потеряно 253 пакета, поэтому порядок правильный

3) Смесь 1 и 2

Answer 3

Использовать приоритетную очередь.

После каждого приема каждого пакета:

• помещать его в очередь.
• повторно удалять верхний элемент очереди какпока это тот, которого вы ждете.

По второму вопросу:

• В общем, нет, его невозможно решить.
• Если прибытие пакета имеет некоторую периодичность (например, ожидание пакета через каждые 20 мс), то вы можете легко обнаружить это, очистить очередь, и после получения 5 пакетов вы будете знать, как обрабатывать снова ...