Sign in to follow this  
GroZZleR

Unique Identifiers and Overflowing Numbers.

Recommended Posts

GroZZleR    820
Hey all, How do you handle overflowing numbers for your unique identifiers? If you've got a number on every packet (UDP), and you need to sort some packets (lets say chat text) what do you do when the numbers overflow? Example: Player 1 sends some chat text. The server brands it with unique identifier 4.2 billion and change. Player 2 sends some chat text. The server brands it with unique identifier 0 (the integer storing the unique number has overflowed and rolled back to 0). Player 3 receives Player 2's text first, then Player 1s. Player 3's client displays 2s first, because the 0 identifier is less than the 4.2 billion of Player 1s. How do you handle overflowing of unique identifiers?

Share this post


Link to post
Share on other sites
Megahertz    286
You're prolly going to use int for a sequence number for one reason, and thats because of the possiblity of overflow with smaller data types.

You ask how overflow is handled, by using an int for the sequence number its pretty much prevented. 4.2 billion packets is a lot of packets. At 20 packets per second, it would take 6.65 years to get an overflow. In the context of games, I highly doubt anybody is gonna stay connected for that long to a game. =)

-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
doynax    850
Here's a (somewhat modified) snipped from our game, hopefully it'll at least give you an idea of how to implement this.
So if you worry about overflow just use a 64-bit type and you can still serialize them as 16-bit words.


// should last for about 30 billion years, at 20 packets/second
typedef PacketSequencer<__int64, 16> SafeSequencer;



template <typename Type, unsigned Bits>
class PacketSequence()
{
private:
const Type m_Size = Type(1) << Bits;
const Type m_Mask = Size - 1;
const Type m_Half = Size >> 1;

Type m_Low;
Type m_High;

void UpdateLimits(Type Seq) {
Seq -= m_Half;
m_Low = Seq & m_Mask;
m_High = Seq & ~m_Mask;
}

public:
PacketSequence() {
UpdateLimits(0);
}

Type Encode(Type Seq) {
return Seq & m_Mask;
}

Type DecodeType Seq) {
Seq &= m_Mask;
if(Seq < m_Low) Seq += Size;
Seq += m_High;

UpdateLimits(Seq);
return Seq;
}
};

Share this post


Link to post
Share on other sites
hplus0603    11356
For unique identifiers, I use 64-bit integers. They don't overflow, ever, for any current networked game design.

For packet sequence numbers, I use unsigned bytes, and keep a sliding window of the latest sequence number received. Anything that's less than 127 units logically before that is "in the past" and anything that's less than 127 units logically after that is "in the future" (and updates the window). For typical packet rates on typical current games, there is little to no chance of overlap (10 packets per second means the packet has to be 13 seconds late to foul things up). If you're skittish, use 2 bytes.

To calculate the signed distance using the sliding window, use something like:


unsigned char last = INITIAL_VALUE;

unsigned char received = WHATEVER_FROM_PACKET;
if( (unsigned char)(received-last) <= 127 ) {
// packet in the future
last = received;
}
else {
// packet in the past
}



You want to keep a sequence number per peer connection; i e in a star topology, you want one sequence number series per other machine you're talking to. You also want to negotiate the initial sequence number, if you don't legislate that all connnections start at a fixed value.

The code in question uses a specific property of unsigned arithmetic:


prompt> ./foo
10
246
prompt> cat foo.cpp

#include <stdio.h>

int main() {
unsigned char r = 30;
unsigned char l = 20;
printf( "%d\n", (unsigned char)(r-l) );
r = 10;
printf( "%d\n", (unsigned char)(r-l) );
return 0;
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this