What's a good way to detect wrap-around in a fixed-width message counter?

Question

I'm writing a client application to communicate with a server program via UDP. The client periodically makes requests for data and needs to use the most recent server response. The request message has a 16-bit unsigned counter field that is echoed by the server so I can pair requests with server responses.

Since it's UDP, I have to handle the case where server responses arrive out of order (or don't arrive at all). Naively, that means holding on to the highest message counter seen so far and dropping any incoming message with a lower number. But that will fail as soon as we pass 65535 messages and the counter wraps back to zero. Is there a good way to detect (with reasonable probability) that, for example, message 5 actually comes after message 65,000?

The implementation language is C++.

Answer 1

If I understand things correctly, you may be able to use some windowing, if you are not already.

That is, do not accept an message that is outside your window. For example, if your counter is at 1000, you may limit your range of incoming counter IDs you will accept to 1000...1031 inclusive. Thus anything outside that range is too much for you to handle (forcing you to initiate some resend protocol). Once you get 1000, your upper limit will go to 1032. Then once you get your lower limit counter of 1001, your upper limit will be 1033, and so on. What you end up with is a sliding window.

If such a scenario is acceptable, then all you have to check is that your incoming counter ID is within your accepted window. This will be a subset of the 16 bit counter, so you can test ...

incomingCounterID - lowerLimitCount < windowSize

As long as you are dealing with unsigned variables, you should be fine.

Hope this helps (and makes sense).

Answer 2

I could have the client save two things:

• an unsigned 32-bit internal message counter
• a list of pending server requests

With each request, the client increments its internal counter and saves it in the list. In the request message, it sets the message counter to this number modulo 65536. When a response message comes in, the client walks its list of pending requests for a matching number modulo 65536. If this internal number is greater than the highest so far, the message is accepted. This delays the wrap-around problem to around 4 billion. Pseudocode follows below.

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;
    }
}

Answer 3

This is mostly of a combination of what's been said, so don't choose me as the answer, but since you know

1. what you have asked for ( the request and request number )

2. what you have gotten

3. how long it has been since you have mad a request

4. what a response to a particular request should look like

you should be able to get a fairly good system going.

From the request maker/response taker side:

1. Never accept a response for a request you haven't made or made so long ago that you would consider it old. The data in such a response should be dropped. Only accept the first response of an expected request and mark the request number as not-expecting upon acceptance. (handler (*f)() is a good way to implement this)

2. Anytime a response is recieved you should record a the current time in association with that request number to help you when you start to recycle request numbers. This should be done for accepted and non-accepted responses (those dropped in 1).

3. Do not accept responces which are not legal data for the resuest made. If such a responce is received drop it and if you can determine that making the actual request that is supposed to be using that request code again will not cause bad side effects on the other machine then you may want to repeat the request with a new request code (if any are untouched for long enough -- see 4) and mark the older request code as not expecting.

4. Choose your request numbers from the ones that you haven't seen responces on in the longest amount of time. If the least recently used request code is too young log the event, but try to keep working. Treat all unused request numbers as having been used a long time ago.

5. Bring up your response listening code before your request sending code so that it can see if there are any old responses coming down the pipe from the last run of this program.

On the request taker/response maker side:

1. If any request is made with a request number that you are already working on a response for log the event and only service the new response.

This should work fairly well unless you are sending out a really high number of requests very fast. This does not assume that there is anyone on the network that wants to do bad things. It would be trivial to implement a denial of service (DOS) on this setup.

Answer 4

The usual way to handle this is do to a modulo subtraction. Sequence number a is after sequence number b if & only if (a - b) % 65536 is greater than (b - a) % 65536.

For your example, (65000 - 5) % 65536 is 64995 and (5 - 65000) % 65536 is 541, so sequence number 5 is after sequence number 65000.