Archived

This topic is now archived and is closed to further replies.

Reliable UDP/IP Techniques

This topic is 4989 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

Ok, my UDP/IP is now working. I know that UDP isn't guaranteed to arrive in any order or at all, so I was wondering what techniques are commonly used to ensure packets arrive? I could probably design my own, but I know it wouldn't be efficient or pretty. I looked around online, but all I could find was discussions about how UDP isn't reliable (I already know that ). BTW: I'm using WinSock 2.2 at the moment, and I won't use DirectPlay because I want to port my game and WinSock is a whole lot more like BSD/Berkley sockets than DirectPlay . Thanks in advance. This thread was resurrected by davedx on April 16, 2004. His post is near of the bottom of this first page. [edited by - Null and Void on April 22, 2004 3:30:10 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Reliable UDP is impelemented much like how TCP is implemented. With each packet you have assign it an id. That id tells you its sequence with respect to the stream, and acts as a unique identifier if it gets dropped.

On the reciver side you recive these packets. After a set wait period (calculated based upon latency and other factors) you send the sender the packet ids which you have recived. You can''t send the packets you haven''t recived becuase you dont know if either there weren''t any packets sent or they all got dropped, so you send the ones which you have recived. Of course its possible this ack packet could be loss, if so then on the senders side, a complete resend will occur. So assuming the ack is not lost, the sender recived the list of sent packets. It then sends packets which were loss. That''s the gist of it.

If you use this reliable UDP stream with respect to packet boundaries, you can ignore the stream consistency and use the packets as they arrive. It will give you lower transcational latency with respect to packet loss. If not then you will suffer the same behavior which TCP streams have when there is loss, high latency. That is if you want to use the reliable UDP like a data stream, the sequenece must be complete before you can send it to the application. That means waiting on packet resends. If that is the case, might as well go with TCP. However if you know that the packets are independent of each other, and can be processed as they come in, you don''t need to wait on resends.

Good Luck

-ddn



Share this post


Link to post
Share on other sites

Making UDP reliable can be a project. Like the game SubSpace, I would suggest that you _expect_ to have packets lost and (perhaps) ignore packets that are out-of-order (ie, older than other packets you have already received) since the information would be out-of-date (so to speak!)

Games like SubSpace allow a certain percentage of "Packet Loss"; I think anything over 2.5% (or heavy lag) will cause the player to be kicked into a "spectator" mode.

For Massively Multi-Player arcade-type games, SubSpace is the BEST model and working example I have seen yet. Also, it''s become a bit more mature (it''s been around several years now). Even better, the game-play is addictive and (now) free. If you''ve already played it, then you know what I mean. If not, I would highly suggest that you check out www.subspace.net and try out the game.. You can get a lot of good ideas from it.

Cheers!
// CHRIS

Share this post


Link to post
Share on other sites
DDN, when I said reliable UDP I meant just a way to verify that a packet arrived, not to keep them in the same order. If I were trying to keep them in the same order (like you said) I should just use TCP.

Win32mfc, I'm only going to be using reliable UDP for some of the packets, not all of them. Most of my network idea relies on no needing every packet, but for some of the login and logoff stuff I don't want to have any packets being lost. Would having a TCP port AND a UDP port at the same time (on the server), and TCP port for login and UDP for everything else (on the client) be a good idea? Yeah, I've played Sub Space before, it is pretty well done .

Edit: cleaning up old signatures as long as the thread is revived.

[edited by - Null and Void on April 22, 2004 3:32:01 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The method i outlined above does both. I just mentonied that if you want to keep them in sequence you can use the id for that as well.

-ddn

Share this post


Link to post
Share on other sites
Yeah, I understood what you meant . Ok, here's my idea on implementing this taking into account what I've been told so far. I think I'll add some stuff to it while I'm at it, so this is going to be my own delusional networking system type of thing. I'm typing it up as much for myself as any other reason .




Server:
Each connection will have an unsigned long counter for both received, sent, and last-received packets. They will be initially (when a user just connects) set to zero.

Each time a reliable UDP packet (but not an unreliable UDP packet) is received, this packet's ID (stored within it of course) will be tested against this received counter. Then an unreliable UDP packet will be sent saying that the packet was received (with its number contained within it). And the received counter is incremented by one. Of course the last received will be updated with its ID.

Each time a reliable UDP packet is received that "must be in order" also, it will be cached until the last received counter is equal to one less than its ID number. At the time of caching, a unreliable UDP packet will be sent out with its ID number saying that it was received. Next time a packet is asked for, it will be returned, and the received counter will be incremented one.

Any time any variety of reliable UDP packet is sent, the ID number will be that of the send counter. Then the sent counter will be incremented. It will be cached (also) wholly until a message that says it has been received is found. If a acknowledgement message isn't received, then it will be resent after some odd amount of time.

(This stuff I've already messed around with, but I figure I'd through it in here as long as I'm writing all this up) Also, the server will send out "ping" packets occasionally. Each time a ping packet is sent out, the "AliveStill" counter of that client will be decreased by one. Each time a "pong" packet is received, the client's AliveStill counter will be restored to its original value (what ever that may be).

Client:
The client will be much the same as the server, except that it must store only one sent and receive counter, and doesn't need to send out ping packets, only process them.




Hows that sound?

Edited by - Null and Void on April 26, 2001 9:13:34 PM

Edit: cleaning up old signatures as long as the thread is revived.

[edited by - Null and Void on April 22, 2004 3:32:59 AM]

Share this post


Link to post
Share on other sites
There''s really no need for ping packets unless you''re sending&expecting very little data. Just disconnect the client if you haven''t received any packet for more than say 30 seconds. Of course, if you''re writing a turn-based network game or something where there''s little traffic you''ll have to send pings.

Apart from that, everything looks fine. I''m pretty sure you''ll have to change something anyway once you got some real-life experience with your networking...

cu,
Prefect

Resist Windows XP''s Invasive Production Activation Technology!
One line of sourcecode says more than a thousand words.

Share this post


Link to post
Share on other sites
Yeah, I've rewritten my TCP/IP class three times now, and this will be my second UDP/IP one (the other one had no real features, but it worked).

You're probably correct about the pinging, I should probably have it not send ping packets unless a packet hasn't been received in a while, and each time a packet is recieved will "refill" their connection counter.

Edit: cleaning up old signatures as long as the thread is revived.

[edited by - Null and Void on April 22, 2004 3:31:40 AM]

Share this post


Link to post
Share on other sites
Why not just give every package a little max timeout and tell the Client that every max_timeout at least one package has to be sent. If no package was received for max_timeout send a request for the next packageindices that are missing on the receivestack.. So you won''t need any extra bandwidth for packages that were received. (There are more packages that get to their destination than packages that are lost :p). The Sender buffers a stack with the the packages that were sent in the last whatever timeout and so it can resend the package on request. If the package already was deleted, it sends a message to the receiver that the index of the completly lost package is supposed to be ignored or whatever.

I''d like to hear comments about my Ideas!

cya,
Phil

Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states

Share this post


Link to post
Share on other sites
civguy, the "Sliding Window Protocoll" may make it reliable but it slows down the speed of UDP a lot!! The big advantage of UDP over TCP is, that it sends immediatly (well, you can disable the Sliding Window Protocoll with TCP). This Protocoll causes a higher Latency ''cause it _waits_ until a frame is send...

cya,
Phil

Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states

Share this post


Link to post
Share on other sites
Here''s an idea, and if I sound stupid it''s because I''m better at network security than network protocols:

What if you send two UDP packets containing the same data. This way, there''s a better chance of at least one arriving. If both arrive, just discard one of them. This way, you get increased reliability without a big speed decrease, especially if there isn''t a lot of data to be transmitted.

You could even do connection testing when your program starts up so you could even send three if necessary.

Share this post


Link to post
Share on other sites
gph-gw... what if those 2-3 packets are then lost.

The way I like most if just to send a response from the reciever back to the sender acknowledging the packet has been recieved and maintain a list of pending packets and once a set timeout has passed resend the packet.

Share this post


Link to post
Share on other sites
You could send 4-5 if there's not a lot of data, and if you lose 5 packets in a row the internet is seriously congested.

On the other hand, packet collisions can occur even if the networks aren't congested. Saying this, you could send 3 packets containing the same data and then the reciever can send a UDP ACK every, say, 5 sets of 3 packets.

Edited by - gph-gw on August 28, 2001 11:24:59 PM

Share this post


Link to post
Share on other sites
It just doesn''t seem to be a very effiecent way of doing things. Particularly if you want to transfer a lot of data reliably as you say yourself (remembering not everyone has a decent conn to the internet). Although if you were to do that it is probably would be easier to switch to TCP. But for relibale connections you only want for a few packets at a time it would be much easier to retain a list of packets that have been sent and need to be guaranteed and have the reciever reply with an ACK, than to send out 5 of the same packet and have an ACK sent for them. Your method may reduce the overall latency of the packet being recieved (if the connection is lossy) at the cost of bandwidth. But as you probably won''t be using reliable UDP for anything more than login/logout the time taken is not a factor that will affect gameplay for the client or others.

Share this post


Link to post
Share on other sites
quote:
Original post by meh
It just doesn''t seem to be a very effiecent way of doing things. Particularly if you want to transfer a lot of data reliably as you say yourself (remembering not everyone has a decent conn to the internet). Although if you were to do that it is probably would be easier to switch to TCP. But for relibale connections you only want for a few packets at a time it would be much easier to retain a list of packets that have been sent and need to be guaranteed and have the reciever reply with an ACK, than to send out 5 of the same packet and have an ACK sent for them. Your method may reduce the overall latency of the packet being recieved (if the connection is lossy) at the cost of bandwidth. But as you probably won''t be using reliable UDP for anything more than login/logout the time taken is not a factor that will affect gameplay for the client or others.


No, it isn''t, and that''s why it shouldn''t be used for large amounts of data. If you want 1kb transmitted at low latency reliably then this might be a solution. My internet connection is very fast (broadband) but I have horrible latency: that''s what made me think of it.

I would test the connection first and see what the best scheme is, because my old dialups were low-speed but had small latency.

Share this post


Link to post
Share on other sites
DON''T send the same packet twice. This''ll only make things worse, as it puts more load on the network. Only resend if you didn''t get an ACK or got a resend req.

One side note that occured to me tho: If you''re using serial numbers for your packets (which you''re most definitely going to do), don''t initialize the serial number at zero. Initializing at zero makes the protocol much more predictable and potentially easier to hack by IP spoofing or similar. Picking a random (well, pseudo random) number should work just as fine with just one or two lines of additional programming.

cu,
Prefect

One line of sourcecode says more than a thousand words.

Share this post


Link to post
Share on other sites
phueppl1, there''s nothing inherently slow about the sliding window protocol. In fact the whole point is to get good performance even when the link you''re talking over is a little flakey and dropping packets.

You''re thinking of the Nagle algorthim. This is the one that collects lots of small packets into one big one so you get less load on the network.

-Mike

Share this post


Link to post
Share on other sites
Thought I''d bump this one, since I''m writing a reliable UDP protocol in C# at the moment.

A few questions... why would you only use reliable UDP for login/logout? Wouldn''t you use it for sending game data, and use TCP for login/logout/other admin stuff?

Also, the way I''m doing it, is I have a queue of packets pending. Each packet when sent is marked as sent but not acked and timestamped. The queue is regularly cycled through from front to back by the ''agent'' thread for sending packets. If it encounters a packet that''s sent and acked, it removes it from the queue. If it encounters one that''s sent but not acked, AND the time difference between when it was sent and now is greater than the average round-trip-time plus some error, it resends it.

I figure this way I can avoid having to wait for the server to ask for packets to be resent. Again, may be sacrificing a _little_ bit of bandwidth for possibly higher latency - but if someone''s connection is at the point where they''re timing out on acks, then resending the packets is going to happen anyway...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
http://www.faqs.org/rfcs/rfc908.html
http://enet.cubik.org/
http://airhook.org/

Share this post


Link to post
Share on other sites
Are you aware of the fact that it''s not just packetloss that can happen, but packets can also be multiplied many times so you''ll receive them several times?

Share this post


Link to post
Share on other sites
For video games:
I would use sequence numbers. Unless it''s absolutely necessary, you can discard old packets or packets that were never received because the next one coming in or future dated one is more important. Ideally, the client starts his sequence off at 0, and increments it by one each message sent to the server. When the server receives the datagram, it compares the sequence # in the packet to the last received sequence # from that client. If it’s <= the current #, discard the packet as it is old or a duplicate, if it’s > current #, accept it and update the current # = sequence #. If you want to receive all packets, you could end up with worse performance than TCP due to packet loss in trying to get the client to send you every update. In conjunction with this you would have a prediction algorithm to update clients and yourself accordingly, so that movement and sensitive things like this are not jerky.

If you need to ensure safe delivery of important information (like item pickups), you can use a token-bucket algorithm. Essentially the client fills up one of his buckets (maximum buckets allowed = X) with the information he wants to send to the server. He’ll fire it off and wait for a response on that particular bucket (server filled information about anything, like what other clients are doing). By using certain latency guessing or averaging algorithms, if the bucket hasn’t returned, the client can fire it off again. On the server side, it would keep track of the bucket number so it can discard duplicates. This way you can separate weapon, item, or whatever information into their own buckets and send them in pieces for the server to process. This will have guaranteed delivery without relying on another protocol, TCP, to be enabled in parallel with UDP.

For application purposes:
Use TCP? Heh, what more is there to say =)

Share this post


Link to post
Share on other sites