Sign in to follow this  
oliii

Making a reliable message system with UDP : SOLVED

Recommended Posts

ok, this is to do with the way TCP/IP retransmits data, due to packet loss. Forgetting about fragmentation. So, server transmits a packet. packet gets lost, server retransmits. until an Ack is received, then the messages is destroyed. imagine the situation when the client receives the message late, but does transmit the ack. <code> server send msg(0) server waits... server send msg(1) client receive msg(0) client send ack(0) server receive ack(0) server destroys message client receive msg(1) client send ack(1) server receive ack(1), does nothing (message destroyed). so effectively, the client receives the message twice, which can be a problem. The only way I can see to solve this, if that the client checks if he already sent an ack for a message, so it needs to keep track of messages received from server, to make sure it wont receive it twice. Problem is, how long the client waits, and so on. maybe I should not bother, and use a TCP / IP socket for reliable messages for each connections. [Edited by - oliii on November 26, 2005 3:27:27 AM]

Share this post


Link to post
Share on other sites
I would either forget it and use TCP, or use an existing networking library that has built a reliable protocol ontop of UDP. There's really no reason to write your own.

Share this post


Link to post
Share on other sites
You could have a look at Enet, which implements a low-level hybrid protocol on top of UDP. The source is available and quite slim so you could draw some ideas there. Better is indeed to start using something like it, because it already does what you're intending plus more (automatic throttling, platform-independency, etc.).

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
I would either forget it and use TCP, or use an existing networking library that has built a reliable protocol ontop of UDP. There's really no reason to write your own.


I want to learn that stuff. I don't want to learn how to use libraries.

Share this post


Link to post
Share on other sites
As far as I understand, TCP 'blocks', until it received the missing packet (with number checks). I don't really want to do that. So the whole channel is paused until the packet is received. When the packet is received, the next packet can then be received and aknowledged. If the number is lower, it means it has already been received, and can be discarded as a duplicate.

'but' it's an easy solution. So you're right, I might do that. Park the reliable packets somewhere into a backlog queue, and to hell with the latency. Reliable messages should be used for things that don't require speed, like for example chat text, and so on.

I might take on the idea of Enet about using a channel ID to avoid contention, for different types of reliable messages. Chat logs which are big messages, but unimportant and can be discarded in case of message overflow, weapon effects which are of medium size but not super critical, game settings variables sent to clients, which are small in size, but potentially critical, Game FSMs which are critical, and smal size and should never overflow or game would be horribly out of sync and would hang because of a missed state change, ... One for each, so they don't lag each other in case of big packet drops.

Fragmenting packets would be straight forward too.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
Quote:
Original post by SiCrane
I would either forget it and use TCP, or use an existing networking library that has built a reliable protocol ontop of UDP. There's really no reason to write your own.


I want to learn that stuff. I don't want to learn how to use libraries.


Sorry, being offensive. I should have indicated my intentions more clearly.

I'm moving towards a one UDP connection does it all, with a bunch of reliable channels.

I'm also considering delta-compression, but that's for another day.

Share this post


Link to post
Share on other sites
If you can accept the fact that your implementation of whatever-on-top-of-udp isn't going to be groundbreaking, and are just doing it for learning, then good luck with it. There's a lot more to think about than the issues you've described so far, though. Take a look through this thread, which is about java but still aplies: UDP Vs TCP/IP Some interesting points are raised, especially on page 2.

Share this post


Link to post
Share on other sites
ok, I'm kinda new about internet protocols, but not exactly a noob. I've been doing a lot of work on multiplayer games, but never went down to the engine part (SOckets, protocols, ect...). So just to keep it going, this is the problems I know linked to the internets.

- latency (variable).
- packet loss (variable, and can be quite big).
- out-of-order messages.
- packets either UPD or TCP/IP are always valid and uncorrupted.
- TCP / IP have a larger header overhead.

from what I can see, an packet numbering protocol, the way used in Enet (and what I propose) would take care of all those problems.

[ UDP header ] [ my header ] [ data chunk ]

[ my header ]
for reliable packet :
---------------------
- 6 bits : Which Reliable Channel (this limits to 0-62 channel id).
- 1 bit : Start of a sequence. ) set to true for a non-sequenced packet.
- 1 bit : End of a sequence. } set to true for a non-sequenced packet.
- 1 short : packet number in channel.

for unreliable packet :
-----------------------
- one byte : set to 0xFF (channel 63, which is invalid, and not a sequence).

I'm not discussing NAT problems, firewalls, spoofing and other connection specifics.

What is wasteful with that scheme, is that you send packets, that will arrive to the client, but that the client will 'drop' because it's not the the one with the right packet number, since the client waits for one particular packet to arrive before processing packets with higher numbers.

Anything I missed, I'll be glad to hear about it. I'm sure there are other problems, TCP / IP looks more complicated than that. :)

EDIT : erm.. actually not. the server won't send packet updates, only for the first message in its send buffer. so not too bad. It's just a high latency problem.

Share this post


Link to post
Share on other sites
Looking over your example in the top, I dont see where the client sending the ack is delayed or where the same message is destoyed twice.

Sooo, lets take the following:


<Server sends message 01 and saves it in a resend queue>
<Some time passes>
<Server sends message 02 and saves it in a resend queue>
<Client recieves message 01>
<Client sends ack 01 to server>
<Server recieves ack 01 and removes packet 01 from the resend queue>
<Client recieves message 02>
<Client sends ack 02 to server>
<ack 02 to the server gets lost/delayed>
<Server has not recieved an ack from the client in a certain amount of time so it resends the message in its resend queue (currently only packet 02)>
<Client recieves message 02 again but since it has already recieved this packet it drops it, also it resends an ack for the highest consecutive message ID it has recived (currently 02)>
<Server recieves ack 02 and removes packet 02 from the resend queue, also it disables the resend timer until it sends out another message requiring an ack>



Getting this all working with correct timings can be a pain. You want to wait long enough for the packets to have time to get to the destination and the acks to get back before triggering the resends. Ping times on the net however vary so itll need to be dynamic.

I've implemented most of the above and it works for the most part, but under a decent load it starts to break down and flood itself with resends. The part I'm missing is throttling back on sending packets when PL starts to happen. Also adding some sort of sliding window to the system is sorely needed. Heh the funny part is if I ever add that and get it working, It'll be pretty close to what TCP/IP does.


"If you can accept the fact that your implementation of whatever-on-top-of-udp isn't going to be groundbreaking"

Enet and Raknet wouldnt be around if people followed thinking like this. Sometimes its good not to reinvent the wheel, but its pretty hard to build a better wheel without knowing something about how the original was made.

-=[ Megahertz ]=-


Share this post


Link to post
Share on other sites
Sorry, I didn't mean that in a negative way. It is true however that the protocols in question have been around for a long time without tremendous advances. My (unqualified) opinion about that is that we're tied down by legacy infrastructure.

I just wanted to help by pointing out a thread where people smarter than I am discussed at length the issues of named libraries and various methods of home-brew implementation. The good stuff starts halfway down page 2, so oliii don't think I mean to imply anything about your level of competence here.

Share this post


Link to post
Share on other sites
sorry, msg(0) and (1) are the same message, (1) being a resend of (0).

but you see, the client needs to keep a copy of the message (or at least some limited information), in case the server resends it, so the client knows it's a duplicate, and don't process it twice. That in my opinion is bad and seemed wasteful, overly complicated. That's what I'm trying to avoid.

Also, the message has to store guids of messages as part of the message, to tell which message is which. I don't really want to enforce that in a UPD wrapper. Message number is different in a sense that it's not a real GUID and incures no extra complexity (re-usable GUIDs can be a pain).

I like the straight forward method of reliable, in-sequence data streams. Latency, as I said, should not be a problem for reliable message. If it is, you have a flaw in your system.

It's just my opinion anyway. Also, as you said, data streams avoids flooding the client with constant resends. YOu only have one resend per channel, which is manageable.

Share this post


Link to post
Share on other sites
Quote:
Original post by lightbringer
Sorry, I didn't mean that in a negative way. It is true however that the protocols in question have been around for a long time without tremendous advances. My (unqualified) opinion about that is that we're tied down by legacy infrastructure.

I just wanted to help by pointing out a thread where people smarter than I am discussed at length the issues of named libraries and various methods of home-brew implementation. The good stuff starts halfway down page 2, so oliii don't think I mean to imply anything about your level of competence here.


non taken. It's late, I'm tired, and the head hurts with bitstreams, protocols, wrappers, and to much coffee. I'll have a look at the thread, it looks intresting, but it's 10 pages long! :)

Share this post


Link to post
Share on other sites
Not really. If you do read the TCP protocol with all the safety stuff, you're in for a long read indeed. But I found RFC908 to be rather simple and straight-to-the-point. If you want to look at the source code a *very* simple reliable-over-UDP library, then AirHook is it (http://airhook.ofb.net/).

-cb

Share this post


Link to post
Share on other sites
Quote:
but you see, the client needs to keep a copy of the message (or at least some limited information), in case the server resends it, so the client knows it's a duplicate, and don't process it twice. That in my opinion is bad and seemed wasteful, overly complicated. That's what I'm trying to avoid.


Not really. Each packet sent will have a unique sequential ID. If at any time you recieve a packet with an ID that is equal to or less than the most current packet ID recieved, its a duplicate/late packet and can be disregarded.

You will however need to cache a copy of an early packet until you get all the packets leading up to it.

<Client gets packet 01>
<Client searches buffered list for packets>
<Client gets packet 02>
<Client searches buffered list for packets>
<Client gets packet 03>
<Client searches buffered list for packets>
<Client gets packet 06> (This packet is not directly in sequence past the most current packet ID recieved. So its cached in a buffered list of packets)
<Client searches buffered list for packets>
<Client gets packet 04>
<Client searches buffered list for packets>
<Client gets packet 05>
<Client searches buffered list for packets> (Client finds that a buffered packet with an ID 06 is directly after the most current packet ID recieved, pops it off the list and then processes it like any other packet)
<Client gets packet 07>
<Client searches buffered list for packets>
<etc..>


-=[ Megahertz ]=-





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