• Advertisement
Sign in to follow this  

Sending potentially large stream. UDP

This topic is 3839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Lots of talks about serialisation at the moment, I was just wondering what are your thoughts on sending packets larger than the MTU. I understand you will need to segment your packets so they fit into the MTU, use sequence numbers, and so on, but I'm open to alternatives or better designs. Ultimately, this would tie up with a 'game state' stream, which is the serialisation of all views of game entities into one single buffer, watermarked with a sequence number, and then that buffer needs to be sent through a UDP socket. I have this in mind. 1) base class C_Stream. The basic interface to serialisation. Makes no assumption about memory management.
CLASSREF(C_Stream);
class C_Stream: public SmartPtr::C_Referenceable
{
public:
	enum 
	{ 
		E_Mode_WriteOnly=0, 
		E_Mode_ReadOnly, 
		E_Mode_ReadWrite, 
		E_Mode_Count 
	};

	C_Stream(int size, int mode=E_Mode_ReadWrite, int write=0, int read=0);
	virtual ~C_Stream() {};

	virtual bool writeChunk(const void* ptr, int len)=0;
	virtual bool readChunk(void* ptr, int len)=0;

	int			 mode() const { return m_mode;  }
	int			 size() const { return m_size;  }
	int			write() const { return m_write; }
	int			 read() const { return m_read;  }

	void mode(int mode)   { m_mode = mode; }
	void write(int write) { m_write = write; assert(m_write <= m_size); }
	void read(int read)   { m_read = read; assert(m_read <= m_write);   }
	void clear()		  { m_write = m_read = 0; }

	virtual bool readOverflow(int len) const { return (m_read + len > m_write); }
	virtual bool writeOverflow(int len) const { return (m_write + len > m_size); }
		
	bool writeBool (bool val)				{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeByte (char val)				{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeUByte(unsigned char val)		{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeShort(short val)				{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeUShort(unsigned short val)	{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeInt(int val)					{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeUInt(int val)					{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeLong(unsigned long int val)	{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeULong(unsigned long int val)	{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeFloat(float val)				{ return writeChunk((void*)&val, sizeof(val)); }
	bool writeDouble(double val)			{ return writeChunk((void*)&val, sizeof(val)); }

	bool readBool (bool &val)				 { return readChunk((void*)&val, sizeof(val)); }
	bool readByte (char &val)				 { return readChunk((void*)&val, sizeof(val)); }
	bool readUByte(unsigned char &val)		 { return readChunk((void*)&val, sizeof(val)); }
	bool readShort(short &val)				 { return readChunk((void*)&val, sizeof(val)); }
	bool readUShort(unsigned short &val)	 { return readChunk((void*)&val, sizeof(val)); }
	bool readInt(int &val)					 { return readChunk((void*)&val, sizeof(val)); }
	bool readUInt(unsigned int &val)		 { return readChunk((void*)&val, sizeof(val)); }
	bool readLong(long int &val)			 { return readChunk((void*)&val, sizeof(val)); }
	bool readULong(unsigned long int &val)	 { return readChunk((void*)&val, sizeof(val)); }
	bool readFloat(float &val)				 { return readChunk((void*)&val, sizeof(val)); }
	bool readDouble(double &val)			 { return readChunk((void*)&val, sizeof(val)); }

protected:
	int			m_mode;
	int			m_size;
	int			m_write;
	int			m_read;
};


2) C_Segment. a memory block. Holds a buffer to receive serialisation. Only holds up to the MTU size (or about).
CLASSREF(C_Segment);
class C_Segment: public C_Stream
{
public:
	C_Segment(int mode=E_Mode_ReadWrite) : C_Stream(mode, sizeof(m_buffer)) {}

	virtual bool writeChunk(const void* ptr, int len);
	virtual bool readChunk(void* ptr, int len);
	
private:
	char m_buffer[SEGMENT_SIZE];
};


3) a 'dynamic' stream. C_SegmentedStream. Has a list of segments. When running out of space, new segments are pulled from a pool (to avoid allocation). The writeChunk() / readChunk() does the dirty work.
// holds the game state, inside a list of fragments
class C_SegmentedStream: public C_Stream
{
public:
	C_SegmentedStream(int mode=E_Mode_ReadWrite);
	virtual ~C_SegmentedStream() {}

	virtual bool writeChunk(const void* ptr, int len);
	virtual bool readChunk(void* ptr, int len);

protected:
	C_SegmentRef readSegment();
	C_SegmentRef writeSegment();
	C_SegmentRef createSegment();


	C_SegmentRef m_Segments[MAX_SEGMENTS];
	int m_numsegments;
};


C_SegmentedStream::C_SegmentedStream(int mode)
: C_Stream(mode, 0)
, m_numsegments(0)
{}

bool C_SegmentedStream::writeChunk(const void* ptr, int len)
{
	if(len == 0)					{ return true; }
	if(m_mode == E_Mode_ReadOnly)	{ assert("read only"==0); return false; }
	
	// need more segments to store the data
	if (writeOverflow(len))
	{
		// create ONE segment to store the new data
		// if one isn't enough, the recursion will 
		// take care of it.
		if(!createSegment()) return false;
	}			

	// get the segment to write to
	C_SegmentRef segment = writeSegment();
	if(!segment) return false;

	int writeLeft = segment->size() - segment->write();
	int writeRight= (len - writeLeft);
	
	// we will overflow the last segment
	if(writeRight > 0)
	{
		// fill last segment
		if(!segment->writeChunk(ptr, writeLeft)) return false;
		
		// push pointers
		ptr = (const void*)((const char*)ptr + writeLeft);
		len -= writeLeft;
	
		// create new segments and write to them
		return writeChunk(ptr, len);
	}
	else
	{
		// write to last segment
		return segment->writeChunk(ptr, len);
	}
}

bool C_SegmentedStream::readChunk(void* ptr, int len)
{
	if(len == 0)					{ return true; }
	if(m_mode == E_Mode_WriteOnly)	{ assert("write only"==0); return false; }
	if(readOverflow(len))			{ return false; }

	// get the segment to read from to
	C_SegmentRef segment = readSegment();
	if(!segment) return false;

	int readLeft = segment->size() - segment->read();
	int readRight= (len - readLeft);
	
	// we will overflow the last segment
	if(readRight > 0)
	{
		// fill last segment
		if(!segment->readChunk(ptr, readLeft)) return false;
	
		// push pointers
		ptr = (void*)((char*)ptr + readLeft);
		len -= readLeft;
	
		// read remainer of the data
		return readChunk(ptr, len);
	}
	else
	{
		// write to last segment
		return segment->readChunk(ptr, len);
	}
}

C_SegmentRef C_SegmentedStream::readSegment()
{
	int segmentIndex = (read() / SEGMENT_SIZE);
	if (segmentIndex >= m_numsegments) return NULL;
	return m_Segments[segmentIndex];
}

C_SegmentRef C_SegmentedStream::writeSegment()
{
	int segmentIndex = (write() / SEGMENT_SIZE);
	if (segmentIndex >= m_numsegments) return NULL;
	return m_Segments[segmentIndex];
}
C_SegmentRef C_SegmentedStream::createSegment()
{
	if(m_numsegments >= MAX_SEGMENTS) return NULL;
	return m_Segments[m_numsegments++] = new C_Segment(mode());
}


not using a list or a pool atm, but it's for the general idea. When the stream needs to be sent, each segment is sent, with a header (segment number, stream sequence number, ...), and reconstructed at the other end. no resend, if a new stream with a higer sequence number arrives, and the old stream hasn't received all the segments, then it gets cleared and the new stream waits for segments to arrive. I can use the same system to deal with large messages, or reliable messages. I haven't figured a nice way to tie everything up together.

Share this post


Link to post
Share on other sites
Advertisement
Do you have to send it via UDP? Seems to me it would be much easier to just send the stream through a TCP socket.

Share this post


Link to post
Share on other sites
A simple way to handle sequences is something like this:

typedef map< int, Packet *> Resequencer;
Resequencer resequencer;
int current_id;

// on receive
if (packet->id == current_id) {
Packet *curr = packet;
while (curr != NULL) {
handle_packet( curr );
current_id++;
Resequencer::iterator i = sequence.find( current_id );
curr = ( i == sequence.end() ) ? NULL : i->second;
}
] else {
sequence.insert( id, packet );
}



For large packets you then have an appending buffer. When created, you initialize it to total message size, then wait until it's filled up, the resequencing will ensure that chunks arrive in order.

Gotchas:
- Two packets with same sequence id. Which is correct?
- Wraparound. How to effectively test it, what happens if you get packet with (current_id-1), what if (current_id-100)? Are they late? Or early?
- Resending (must have for UDP). How often?
- Memory use: In case of a server hick-up, all clients will lose a few packets, meaning that for a few seconds, all the resequencing buffers will be filling up (at capped bandwidth, that can be up to 100Mb+)
- Stranded packets, DoS attack - it can be somewhat trivial to fill up multiple client's resequencing queues. Just send random packets with (current_id-n .. current_id-1)

Alternative is to know exactly how big each packet of a split message is (MTU-sizeof(id)).

class Resequencer
{
void receive( Packet &packet )
{
int offset = packet.sequence * (packet.payload_size);
// probably wrong syntax
std::copy( message[offset], packet.payload, packet.payload.size );
received[packet.id] = true;
missing--;

if (missing == 0) {
// scan the "received" if all parts were received
// to prevent malicious packets
// notify packet handler with "message"
}
}
std::vector<char> message;
std::vector<bool> received;
int missing;
};


Then again, there's probably many more options to handle this. TCP and IP stack implementations are often part of Networking 101 (probably higher) courses with tasks of implementing custom resequencing, so there's plenty of material available on topic.

Share this post


Link to post
Share on other sites
1) TCP = No-No. A totally different way of doing things. I don't need full reliability and in-order, just a way to handle large unreliable packets, that will sit behind a delta-compression system. UDP is perfect, it's just the way to find a nice protocol to segment and append packets quickly, efficiently, and without unnecessary memory allocations or network overheads.

2) I can't really justify a large memory usage, nor large memory allocations or just-in-time allocations. This is potentially for consoles, and it needs smart memory management without sacrificing too much flexibility.

3) I'm not worried about attacks, there should be a security layer underneath filtering out the garbage. Of course only packets coming from previously registered peers are accepted, so each registered link will keep a re-sequencing buffer for packets arriving from a known and trusted peer.

I guess there is no escaping marking each segmented message with a id, and each segments with an id as well, and do all the re-sequencing logic very straight-forwardly.

So it's just the memory allocation, and growing and shrinking the buffers. I think the segmenting into roughly 1KB blocks is the right idea. Then I can have a very large pool of segments, and merely index them from the streams. I could even segment smaller (say 256 bytes), depending on what the average game state size is and if I run out of segments to allocate.

Share this post


Link to post
Share on other sites
Peers in the general sense. I'm talking consoles without a dedicated server and relatively low bandwidth, and no dedicated servers.

Share this post


Link to post
Share on other sites
They are still not trusted. Someone will create a gateway, console hack, or emulator that will send mal-formed packets. You can't "filter the garbage" at a lower level; robustness to mal-formed data has to be coded at each level that picks apart network data.

You may already be aware of this, but the way it was written in your post could confuse someone into believing that the unsafe client problem can be avoided somehow.

Share this post


Link to post
Share on other sites
1) Dont worry about packet size. OS automaticaly split "big data" into several IP packets. But if you need send several small packet - better archive it and send all together.

2) if you are using UDP you must solve a least two problems
a) flow control. Each packet must contain sequence. Some puckets can be drop and recivied sequnce may be unordered.
b) right identification of packet. Everyone can create packet and you can receive "bugy" packet. So .. evrery packet must contain crypted identification. Usualy used hash function from digest (created in start session) and part of whole data of packet. Reciver must checks everytime packet and hash must be equals recived digest and processed just readed packet.





Share this post


Link to post
Share on other sites
Quote:
Original post by Ramsess
1) Dont worry about packet size. OS automaticaly split "big data" into several IP packets.


Ummm, I'm fairly certain that this doesn't happen with UDP packets.

Share this post


Link to post
Share on other sites
No system is secure. Security is outside the scope anyway. If you used XBox Live for example, the transport layer of XBox Live provides encrytpion (funnily voice data should not be sent encrypted) and many other things to 'secure' communications (key exchange, ip address encryption, NAT punchthrough, ect...), between boxes to an acceptable level, and it's pretty goddamn good and unmolested so far (That might change when it gets added to Vista). Of course peers are not 'trusted' peers, but on consoles, peer to peer games are pretty common, and the host is no more secure than the peers anyway.

I wish UDP would provide a layers to fragment and unfragment packets, but it's not really it's job, since it's a connectionless protocol. To be able to reconstruct packets, you need a form of connectivity information. And as said previously, it is open to flooding so dangerous to add at a lower level layer. Anyways... No shortcuts possible.

Share this post


Link to post
Share on other sites
Quote:
Original post by Driv3MeFar
Quote:
Original post by Ramsess
1) Dont worry about packet size. OS automaticaly split "big data" into several IP packets.


Ummm, I'm fairly certain that this doesn't happen with UDP packets.


It does, so long as you don't go over the limit of the UDP protocol itself (~64K, though I wouldn't try to use a payload of more then 62KB to avoid overflowing at a routing point). That's what the the Don't Fragment and Fragment Offset flags are for. The difference between IP level fragmenting of packets and TCP fragmenting of streams is that IP fragmenting dramatically raises the chance of the packet being dropped (there is no resend, if the packets don't come in correctly they just get dropped). So you can let packets be automatically fragmented by the IP stack on the rare instance that they are bigger then the discovered network MTU - if you are constantly sending packets bigger then that though you probably want to be switching to TCP, as you'll need to reinvent it anyway.

Share this post


Link to post
Share on other sites
Can't you just send small packets under say 1400 bytes or something... For state updates you can number off all of the game object states and if you hit the limit break off and start a new packet. So like 22 objects might be updated in one stream then 25 in another depending on how much data needs to be sent. Then again without reliable UDP some of the game entities might not get updated due to dropped packets.

For one of my games I separated moving object from static objects so I updated all the static objects and the client sent an approval packet to show all of the objects that were updated. This made certain that the static objects were 100% updated and the server verified it. Then moving objects would be updated by state changes. If you get an update call for a game entity ID that doesn't exist then it obviously needs to be added and a request is queued for the full state update of the object. This is done when bandwidth is not needed.

I've never done this in C++, but I'd just use my packet manager:
Clicky
and augment it so that if the packet size + gameObject.SerializeFullStateSize > MTU then send the packet refresh it and start writing the next game object too it. Like GameEntity.SerializeFullState(packet). Very efficient and easy to do. At least that's how I've always handled it. The just update the changed state in reference to the players.

My games tend to be top down shooters, so I tend to update the game entities outside of the player's field of view so the player never notices that say a tank is driving in from the left. By the time it gets anywhere close to the player it's been updated and synced in with the game.

Share this post


Link to post
Share on other sites
I tried that way before, but it wasn't very good (for me at least). I am in the process of designing a full delta compression system. that involves having to stream the whole game state (game views more precisely) into one buffer, and tag that state with one single sequence number. Hence the likely occurence of having the whole package exceed the MTU (or even the UDP send buffer at game start snapshot).

I did have a per-entity delta compression, but it was way overkill, inefficient and cumbersome (having to pack aknowledgements into a table to minimise message overheads). Too many overheads and complications.

[Edited by - oliii on July 17, 2007 11:52:58 AM]

Share this post


Link to post
Share on other sites
Game tick number != packet number.

When acknowledging data, you only need to acknowledge the packet number you received; the sending end can remember which entities at what tick numbers went into that packet.

Share this post


Link to post
Share on other sites
What is "per-entity delta compression"? If you are trying to save bits by assuming that there is any common delta to work off of, are you somehow avoiding the fact that floating point operations are handled slightly differently on different x86 architectures?

Share this post


Link to post
Share on other sites
Quote:
Original post by pTymN
What is "per-entity delta compression"? If you are trying to save bits by assuming that there is any common delta to work off of, are you somehow avoiding the fact that floating point operations are handled slightly differently on different x86 architectures?


When client connects to world, it subscribes to objects it's interested in (or in range).

When a client subscribes to an entity, entity sends its full state.

When a client disconnects, it unsubscribes from entity.

When an entity is destroyed, it notifies all subscribers that it's going away.

Whenver a shared value of an entity changes, the entity sends new value to all subscribers. (name, value) pair indicating the change.


Deltas can also be grouped and cached (you don't send on every change, but accumulate over a certain period - time, game ticks, depends on simulation type).

Each delta is then sent to dispatcher, which sends it to remote subscribers. This gives you state consistency when it's impossible/impractical to synchronize full state.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement