Jump to content
  • Advertisement
Sign in to follow this  
oliii

Sending potentially large stream. UDP

This topic is 4019 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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!