Home

How to test for duplicate packets

jwatte's picture
November 7, 2008 - 11:25 — jwatte

If you're using UDP for your networking, you will typically mark your packets with a "packet ID." That packet ID will be used to detect the case of duplicated UDP packets, and sometimes also dropped packets. For a typical game or other real-time application, that sends maybe 20 packets a second, you don't need to make this ID larger than one byte, because 255 values divided by 20 packets a second means twelve seconds until a packet ID repeats. On most real-time systems, you will disconnect a user if there's more than a five second gap of packets.

When you need to detect whether a given packet ID is duplicate or not, or perhaps "out of window," you don't need to build anything like a complicated hash table. Just use a bit mask of the last 32 packet IDs you've received, and test against that, sliding the mask over as you receive successively larger packet IDs (and make sure to handle the wrap back to 0).

Here's a sketch of how that algorithm might work (in C#, but a C++ translation is simple to make):

public class DuplicateChecker {
 
  public DuplicateChecker() {
    dups = 0;
    lastId = 0;
  }
 
  uint dups;
  int lastId;
 
  // Call IsDuplicate() on a given packet ID. This will do two things:
  // 1) check whether a packet is considered a duplicate
  // 2) advance the window of allowable packets, if the packet ID is 
  // within a certain range
  public bool IsDuplicate(byte id) {
    // adjust to be in window
    int iid = id;
    if (iid - lastId > 127) {
      iid -= 256;
    }
    else if (iid - lastId < -127) {
      iid += 256;
    }
    if (iid > lastId) {
      if (iid - lastId > 31) {
        // a large jump in packet numbers -- maybe signal a problem?
        dups = 1;
      }
      else {
        // use a bit mask for which packets have been received
        dups <<= (iid - lastId);
        dups |= 1;
      }
      lastId = iid & 255;
    }
    else if (lastId - iid < 32) {
      bool ret = (dups & (1 << (lastId - iid))) != 0;
      dups |= (1 << (lastId - iid));
      return ret;
    }
    // a very late packet -- maybe signal a problem?
    return true;  // out of window; assume it's duplicate
  }
}