Я разрабатываю алгоритм переупорядочивания пакетов при передаче. Каждый пакет имеет соответствующий порядковый номер в диапазоне [0, 256). Порядковый номер первого пакета может принимать любое из этих значений, после чего следующий пакет принимает следующее значение, а следующий пакет - следующее за ним, и так далее (переходя через 255).
Порядковые номера пакетов в правильном порядке выглядят следующим образом, где "n" - порядковый номер первого пакета:
n, n+1, n+2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, ....
Каждому пакету присваивается временная метка, когда он прибывает в пункт назначения, и все они прибывают примерно по порядку. (У меня нет точной цифры, но, учитывая список пакетов, отсортированных по времени прибытия, можно с уверенностью сказать, что пакет никогда не окажется более чем в пяти местах от своей позиции в списке, на которую указывает его порядковый номер.)
Я чувствую, что не могу быть первым человеком, столкнувшимся с подобной проблемой, учитывая распространенность телекоммуникаций и их историческое значение для развития информатики. Итак, мой вопрос:
Существует ли известный алгоритм переупорядочивания приблизительно упорядоченной последовательности, такой как описанная выше, с учетом циклически меняющегося ключа?
Существует ли вариация этого алгоритма, терпимая к большим кускам пропущенных элементов? Предположим, что эти куски могут быть любой длины. Меня особенно беспокоят куски с 256 или более отсутствующими элементами.
У меня есть несколько идей алгоритмов для первого варианта, но не для второго. Однако прежде чем тратить человеко-часы на проверку правильности моих алгоритмов, я хотел убедиться, что кто-нибудь в Bell Labs (или где-нибудь еще) не сделал это лучше тридцать лет назад.