Каков хороший способ обнаружения обтекания в счетчике сообщений фиксированной ширины? - PullRequest
Новая
       7

Каков хороший способ обнаружения обтекания в счетчике сообщений фиксированной ширины?

2 голосов
/ 07 апреля 2010

Я пишу клиентское приложение для связи с серверной программой через UDP. Клиент периодически делает запросы на данные и должен использовать самый последний ответ сервера. Сообщение запроса содержит 16-битное поле счетчика без знака, которое отображается сервером, поэтому я могу связать запросы с ответами сервера.

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

Язык реализации - C ++.

Ответы [ 5 ]

5 голосов
/ 11 апреля 2010

Обычный способ справиться с этим - выполнить вычитание по модулю.Порядковый номер a следует после порядкового номера b, если & только если (a - b) % 65536 больше (b - a) % 65536.

Для вашего примера, (65000 - 5) % 65536 равно 64995 и (5 - 65000) % 65536 равно 541, поэтому последовательностьномер 5 - после порядкового номера 65000.

4 голосов
/ 07 апреля 2010

Если я правильно понимаю, вы можете использовать некоторые окна, если вы этого еще не сделали.

То есть не принимайте сообщение, которое находится за пределами вашего окна. Например, если ваш счетчик равен 1000, вы можете ограничить диапазон идентификаторов входящих счетчиков, которые вы принимаете, до 1000 ... 1031 включительно. Таким образом, все, что находится за пределами этого диапазона, является слишком сложным для вас (что заставляет вас инициировать какой-либо протокол повторной отправки). Как только вы получите 1000, ваш верхний предел станет равным 1032. Затем, как только вы получите нижний предел счетчика 1001, ваш верхний предел будет 1033, и так далее. В итоге вы получаете раздвижное окно.

Если такой сценарий приемлем, то все, что вам нужно проверить, это то, что ваш идентификатор входящего счетчика находится в вашем принятом окне. Это будет подмножество 16-битного счетчика, поэтому вы можете проверить ...

ВходящийCounterID - lowerLimitCount

Пока вы имеете дело с беззнаковыми переменными, с вами все будет в порядке.

Надеюсь, что это помогает (и имеет смысл).

3 голосов
/ 27 июня 2012

Ваша проблема давно решена в RFC1982 , в котором говорится, что если у вас есть беззнаковые серийные номера i1 и i2, соответствующий тест будет

i1 меньше i2, если i1 <> i2, и 

    (i1 < i2 and (i2 - i1) < 2^(SERIAL_BITS - 1)) or
    (i1 > i2 and (i1 - i2) > 2^(SERIAL_BITS - 1))

(или использовать их обратный тест больше, чем)

Для 32-разрядного без знака 2 ^ (SERIAL_BITS - 1) = 2 ^ 31 = x80000000

0 голосов
/ 08 апреля 2010

Это в основном сочетание того, что было сказано, поэтому не выбирайте меня в качестве ответа, но, поскольку вы знаете

  1. что вы просили (запрос и номер запроса)

  2. что вы получили

  3. сколько времени прошло с тех пор, как вы отклонили запрос

  4. как должен выглядеть ответ на конкретный запрос

у вас должна получиться довольно неплохая система.

Со стороны создателя запроса / получателя ответа:

  1. Никогда не принимайте ответ на запрос, который вы не делали или делали так давно, что считаете его старым. Данные в таком ответе должны быть отброшены. Примите только первый ответ на ожидаемый запрос и отметьте номер запроса как не ожидающий при принятии. (обработчик (* f) () - хороший способ реализовать это)

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

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

  4. Выберите номера ваших запросов из тех, на которые вы не ответили в течение длительного времени. Если наименее недавно использованный код запроса слишком молод, зарегистрируйте событие, но попытайтесь продолжать работать. Рассматривайте все неиспользованные номера запросов как использовавшиеся давным-давно.

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

На стороне получателя запроса / ответа:

  1. Если какой-либо запрос сделан с номером запроса, вы уже работаете над ответом для регистрации события и обслуживаете только новый ответ.

Это должно работать довольно хорошо, если вы не очень быстро отправляете действительно большое количество запросов. Это не предполагает, что в сети есть кто-то, кто хочет совершать плохие поступки. Было бы тривиально реализовать отказ в обслуживании (DOS) на этой установке.

0 голосов
/ 07 апреля 2010

Я мог бы сделать так, чтобы клиент сохранил две вещи:

  • 32-разрядный внутренний счетчик без знака
  • список ожидающих запросов к серверу

С каждым запросом клиент увеличивает свой внутренний счетчик и сохраняет его в списке.В сообщении запроса он устанавливает счетчик сообщений на этот номер по модулю 65536. Когда приходит ответное сообщение, клиент просматривает свой список ожидающих запросов для совпадающего номера по модулю 65536. Если этот внутренний номер больше, чем самый высокий на данный момент,сообщение принято.Это задерживает проблему с оборачиванием до 4 миллиардов.Псевдокод следует ниже. 

unsigned long internalCounter = 0;
unsigned long highestSoFar = 0;

// On message send...
++internalCounter;
message.counter = internalCounter % 65536;
pendingList.push_back(internalCounter);

// On message receive...
for (i = pendingList.begin(); i != pendingList.end(); ++i)
{
    if (*i % 65536 == message.counter && *i > highestSoFar)
    {
        highestSoFar = *i;
        pendingList.remove(i);
        process(message);
        break;
    }
}
...