Guaranteed UDP

Discussion in 'Game Development (Technical)' started by Applewood, Aug 19, 2007.

  1. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    Title says it all really. Does anyone have a link or other resource explaining how to write a guaranteed UDP system ?

    I have a very naieve system working at the moment that just sends acks then ackacks etc but this can't be the best way!

    I don't need to see code, just the basic block diagram algorithm will be fine.
     
  2. ChrisP

    Indie Author

    Joined:
    Feb 5, 2007
    Messages:
    971
    Likes Received:
    0
    I've never actually written one of these before; so take this with a grain of salt. I have studied it and thought about it though, so here are a couple of ways one might do it.

    TCP uses a pretty clever algorithm; each chunk of data has a sequence number attached to it (TCP actually uses byte counts as sequence numbers - though you don't need to go that far, especially if you keep your UDP packets small enough to avoid getting fragmented, ~500 bytes or so). Whenever one peer sends a packet, it includes the sequence number of the next expected packet. If it wants to ACK without sending any data (which it does after a smallish timeout), then it sends a packet with a zero-length payload.

    When sending, each peer keeps track of all the non-ACKed packets. When it receives a packet from the remote peer, it checks the "next expected packet" field. All packets previous to this are dumped. If there are any packets left in its queue, it assumes that it has to re-send them all, and does so. Also, if a packet isn't ACKed after X time, then it gets re-sent anyway.

    Drawbacks to this approach: You can't have non-reliable packets; your entire data stream is sequenced and ACKed. It's rather like TCP, so it has many of TCP's drawbacks (though not all, if you don't implement the whole protocol). But if you're looking for a TCP-like protocol written in UDP (perhaps so you can do NAT punchthrough) then it's worth imitating. TCP isn't ubiquitous for nothing.

    Other gotchas: If your sequence numbers can wrap [which they certainly can], then how do you figure out which packets are "previous"? Your packet queue needs some kind of time-dependent ordering. Also, how do you deal with the case where one peer sends a lot of data which is not ACKed in timely fashion? Your buffer either needs to be infinite or you have to start dropping packets.

    If you're writing an action-heavy game, a somewhat different approach is the one adopted by Quake 3. Quake 3 can aggregate all changes between one time and another into one packet (so redundant object updates are eliminated, for example - Q3 has a lot of these, since most of its updates are just position and velocity changes, so this is a big saving). So it does this quite frequently, with the base time being the last time that the client ACKed.

    In action-heavy games you'll also want to do client prediction of course. This gamedev.net article might be useful, and their multiplayer category is more generally worth a look.

    These methods sound vaguely similar, and they are, with one caveat: The TCP-like method optimistically assumes that most packets will arrive, so when packets don't arrive it slows down quite a bit (due to timeouts and so on). The Quake 3 method pessimistically assumes (until it knows otherwise) that no data has arrived, so we'd better send it all again. TCP waits and checks; Q3 just shoves data down the tubes as fast as possible.
     
  3. Nikos Beck

    Nikos Beck New Member

    Joined:
    Jun 14, 2007
    Messages:
    321
    Likes Received:
    0
    If you need to have a reliable protocol, why not use TCP? The goal of TCP is guaranteed in-order delivery. When I've had to use UDP it's because I can tolerate data loss. Is it a matter of not wanting session overhead?

    Either of the methods ChrisP described would work.
     
  4. oNyx

    Original Member

    Joined:
    Jul 26, 2004
    Messages:
    1,212
    Likes Received:
    0
  5. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    I don't need to have a reliable protocol, just optional guarantees. Out-of-order and missing packets are already dealt with, it's literally just the guaranteed resend I need to fix.

    3rd party libs are not an option as this has to work on X360, PS3 and PC. TCP is not an option because it's slow and crap for action games. NAT isn't a worry as all that stuff is resolved before I get started by either XBLA or PSN. Mostly. 3rd party libs aren't an option as both consoles use custom security and non-standard sockets.

    My current guaranteed method is for the sender to queue guarantees and resend after y time if they're not acknowledge by client x. Problem is, client x needs to send his ack as guaranteed too and therein lies the problem - you might eventually flood the system with acks before someone decides the connection is too poor to continue. That's a TRC failure for MS and probably Sony too. You also need to remember what guaranteed packets were acked in case a second ack comes and you need to know to ignore it, I think.

    It's annoying me because I found an article on this once but now I need it I just can't find it. Google isn't turning up much at all.
     
  6. princec

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    4,873
    Likes Received:
    0
  7. zoombapup

    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    Hmm, paul. I'd suggest having a look at the networking stuff they had for Cube/Saubraten. I cant remember what the lib was called, but it was built for reliable UDP.

    Also, TNL has reliable UDP (being built for a FPS game) that could give some pointers.

    I wrote a reliable UDP layer maybe 10 years back :) but cant really remember the exact details or the paper I took the implementation ideas from. I suppose it depends on how you want to qualify an ack. The GG guys wrote a great paper on a few of the more important issues (i.e. choosing when you can drop packets without problems, when you want to keep the semi-reliable in time constrained environments etc). Look for GDC networking in google?

    Kind of hard unless we know what the game is really. Different games I'd go with different scheme's depending on the data.
     
  8. Genimo

    Indie Author

    Joined:
    Dec 23, 2005
    Messages:
    92
    Likes Received:
    0
    http://enet.cubik.org/
     
  9. Dan MacDonald

    Moderator Original Member Indie Author

    Joined:
    Jul 26, 2004
    Messages:
    1,424
    Likes Received:
    0
    Dont sent the ack guaranteed per say, just keep sending it on a schedule until the server sends a new update packet. ACK's are tiny packets in most cases and aren't going to significantly slow down your game. So I would said the ACK once right when you get the packet, and then broadcast it on a fixed interval afterwards.

    Every 300 ms or so so it wont generate a huge amount of chatter on the wire.


    this will slow it down a little, but you don't want all your time critical action data going though reliable anyway.
     
  10. princec

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    4,873
    Likes Received:
    0
    What's wrong with using TCP for the reliable bits and UDP for the unreliable bits?

    Cas :)
     
  11. Xiotex

    Original Member

    Joined:
    Jul 27, 2005
    Messages:
    171
    Likes Received:
    0
    Don't worry about this. I used the net library for Cube (called Enet) for Mutant Storm Empire for PomPom for the X360 and Bliss Island for the PSP and it worked fine. It's very easy to use and the conversion process involved altering one file (win32.c).
     
  12. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    I did consider enet since it comes with source, thanks. I'll hack away at my own code for a while and if I get nowhere I might line that up to bat.

    Great job on mutant storm btw. Love it.
     
  13. Xiotex

    Original Member

    Joined:
    Jul 27, 2005
    Messages:
    171
    Likes Received:
    0
    Damn - is it on partnernet? I haven't booted the dev kit in a while!

    I would seriously consider enet. I rolled my own reliable UDP system but it fell over on the PSP because of its crappy network going to sleep thing. Enet took me less than a weekend to integrate into the PomPom engine and worked fine.

    The only issue I would have with it is because it is free it's a bit hit and miss as far as support goes.
     
  14. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    Aye, they both are.
     
  15. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    I missed the obvious.

    Please come and work with us...... :)
     
  16. Xiotex

    Original Member

    Joined:
    Jul 27, 2005
    Messages:
    171
    Likes Received:
    0
    Love to :)
     
  17. zoombapup

    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    Hehehe, thats both disturbing and beautiful at the same time, I hope you are both very happy together :)

    Sorry, just looked like a man-love-fest in the making :)
     
  18. Fabio

    Original Member

    Joined:
    Sep 30, 2005
    Messages:
    499
    Likes Received:
    0
    By the way, I had the unfortunate idea to make "circular backups" for some months on my gigabit LAN computers, till I discovered that my data had been corrupted.

    Has any other of you experienced, when moving ten or more GBs of data accross a LAN, that although the [copied] number of bytes and of files/folders is correct, if you bother to do a binary, bit by bit comparison of all the source<->dest files, some files will have 00's bytes spots (each spot is some tens of bytes in length)?

    I can repeat the problem any time, just moving some tens of GBs of files does it all the time on multiple places, on a supposedly reliable channel. It's not the gigabit switch faulty, I checked. It does it also on 100Mbs LAN, although because of its speed it takes ages to move some tens of GB's accross such a network. It must be Windows, which doesn't CRC the files and just relies on the WANNABE reliable, stupid, 16bit add-style ancient type of checksum of TCP. No surprise that every few GBs you get corrupted data which, if is cumulative, can soon destroy a lot of your precious work, as it happened to me.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer