какую структуру использовать для восстановления сеанса UDP?

Question

Я работаю над реализацией движка exachange. Я получаю данные тикера через UDP, каждый многоадресный пакет UDP имеет порядковый номер. Exchange отправляет пакеты один за другим, но, поскольку UDP не гарантирует порядок, они могут (и будут) приниматься в слегка «смешанном» порядке, например:

1 2 3 5 4 6 7 10 9 8 11 12 13 14 15

Предполагая, что я получаю пакеты в правильном порядке, все будет легко - я могу просто использовать Queue, чтобы добавить пакеты и удалить их из очереди позже. Но поскольку пакеты не полностью упорядочены, у меня есть несколько проблем:

• Какую структуру использовать для хранения пакетов? Мне нужна возможность ставить в очередь и удалять пакеты, а также мне нужна возможность добавлять пакеты в произвольном порядке в массиве

• Мне нужно выполнить процедуру восстановления, если какой-то пакет потерян. Поэтому каждый раз, когда «nextPacketSequenceNumber! = CurrentPacketSequenceNumber + 1», я должен ждать, скажем, 5 мс, и, вероятно, пакет будет доставлен, если нет, то я должен восстановить. Например

  1 2 3 5 ... after 5 ms .... 4   - OK
  1 2 3 5 ... after 10 ms .... 4 - recover
  1 2 3 5 6 7  - recover
  

Answer 1

Поскольку порядковые номера являются последовательными целыми числами, массив очень хорошо работает для хранения. Но они также развиваются бесконечно, поэтому вы хотите, чтобы индекс использовался циклически, как кольцевой буфер.

Еще один способ взглянуть на это - кольцевой буфер с произвольным доступом (не только FIFO).

Answer 2

Возможно, это не самый эффективный способ сделать это, но я использовал OrderedDictionary (хотя SortedDictionary, вероятно, более подходит) для обработки вопрос заказа в прошлом. Используйте порядковый номер в качестве ключа и пакетные данные в качестве значения.

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

Answer 3

Проблема усложняется, если упорядочение является критическим - например, вы можете использовать приоритетную очередь, но вы также не хотите обрабатывать что-либо вне очереди, если только она не следующая в последовательности.Таким образом, вы можете реализовать приоритетную очередь, которая также блокируется на основе последовательности.

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

Это похоже на буферизацию джиттера в аудиопотоках для переупорядочения пакетов UDP. http://en.wikipedia.org/wiki/Jitter#Jitter_buffers

Answer 4

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