Sign in to follow this  
Rozik

UDP with ACK

Recommended Posts

So i was thinking:) If i were to use UDP and wanted to program a Acknoledge System. Roughly i thought about the following: Someone sends a message with an ID and waits a certain time for an ACK with the same ID if the ACK doesnt come an request for ACK with the ID is sent If someone receives a request for ACK the ID is checked, and if a message with the same ID is available the ACK with the ID is resent, if the message is not there a request for the message with the ID is sent and so on... well thats just the basic thought sorry for spelling i am not english well my question now is the following: is it even worth doing something like this or does the overhead produced by the requests nullyfy the UDP advantage? Thx in advance! Rozik

Share this post


Link to post
Share on other sites
Although not really answering your question directly, I would anyways like to recommend:

a) Have you looked at RakNet? It's a UDP library with an ACK system of its own, as well as heaps of other useful goodies. Why reinvent the wheel when you don't need to, right? :)

b) Are you sure that you absolutely need UDP for this game? As has been mentioned, TCP is capable of quite a lot more than many people give it credit for. It takes care of many annoyances that UDP has, and might even end up being faster if your UDP ACK system is poorly coded. (Not saying that's the case here, just in general :P)

Share this post


Link to post
Share on other sites
Why do something that complex for ACKs that are not received? Why not just retransmit the packet if an ACK is not received? Keep in mind that on most WAN connections, propagation delay is much higher than transmission delay.

BTW, sorry for my spelling too. I'm not English either.

Share this post


Link to post
Share on other sites
I've done reliable UDP in this sort of manner:

Sender
- Attaches an ID to an outgoing packet
- Adds the packet to a "pending ack" queue, noting the system tick count
- Sends the packet

Send Queue
- Oldest packets are always on top since all pending packets are added to the end. Therefore, iterate from the beginning of the queue looking for packets older than say 2000ms.
- Any packet older than 2000ms is re-sent, and re-queued to the bottom of the queue with a new tick count
- Any packet younger than 2000ms signals the end of the queue walk. 2000ms - current tick - this packet's tick = how long to wait until checking the queue again. Feel free to sleep, eat a sandwich, etc.

Sender receives an ACK
- Walk the queue to find the packet ID.
- Remove the packet from the ACK pending queue if found.
- If not found, discard the ACK.


Receiver
- Receives a packet with an ID
- Sends an ACK to the sender
- Checks the ID against the receive queue to see if we've received it already
- If not received before, add the ID (only the ID) and tick count to the received queue, and process the packet.
- If already received this ID, toss the packet out as a duplicate.
- Walk the received packet ID queue. Anything older than 10 seconds, discard it.

Optimizations:
When the sender receives an ACK it must walk the entire queue looking for that packet ID. One optimization is to use two queues. One sorted, the other not. When an ACK is received, find the packet pointer in the sorted list, update the packet structure to mark it as deleted, then delete it only from the sorted list. Then, when the regularly-scheduled pending ACK queue is walked, delete and skip anything marked as deleted. Eventually old deleted packets will bubble up to the top and be removed then.

ACK combining
Instead of sending an immediate ACK, keep a "recent senders" list with a predetermined array to hold X number of ACK packet ID's. Each time you want to ACK a packet, retrieve (or create) the sender's list item, add the ACK packet ID to the array. Keep track of the last tick count of when you sent that sender an ACK, and when it gets over 100ms or so, send the array of ACK's to the sender and flush the buffer. The recent sender's tick count gets updated when the first new ACK hits the array.
The sender (who is now getting a bunch of ACKs in one packet) will have to iterate through all of them, but at least they all came in one lump.

In the above scenarios, one or more threads are working on processing socket I/O. Typically, one worker thread to receive packets and process the queue(s) will suffice. In it, you can issue a select() on the socket with a timeout equal to the minimum amount of time necessary to requeue the oldest unacked packet in the send queue. If the pending queue is empty, 2 seconds is the default. If select() times out (or even if it doesn't) its time to walk the queue and resend anything still pending and then calculate a new timeout for select(). If using the ACK combining optimization, then you default to 100ms timeouts and check that pending outgoing ACK list every time select() returns.

I don't do it exactly this way (I'm using IOCP sockets and a threadpool) but its close enough.

Robert

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Google for "RFC908". This is a protocol that could be implemented over UDP. The docs are pretty good at explaining how packet acknowledgment works.

Share this post


Link to post
Share on other sites
I really want to try Raknet:)

But i only got a public email and its not really for a game:) Its for a Student project

Anyone have any idea how to get my hands on Raknet if the dont respond to my shareware application?

Share this post


Link to post
Share on other sites
Quote:
Original post by Rozik
Someone sends a message with an ID and waits a certain time for an ACK with the same ID if the ACK doesnt come an request for ACK with the ID is sent

If someone receives a request for ACK the ID is checked, and if a message with the same ID is available the ACK with the ID is resent, if the message is not there a request for the message with the ID is sent


Send a message and wait for its ACK is simple but not efficient. Because you must wait for a RTT (Round Trip Time) for each message, it means that you can only send 10 messages per second when the RTT is 100 ms.
To avoid this condiction, the TCP use sliding window protocol for network flow control. If you want to design a ACK protocol, maybe you should take a look at the sliding window of TCP.

Here are some reference for Reliable UDP and I hope it helpful to you:

ENet
http://enet.cubik.org/

RUDP
http://www.faqs.org/rfcs/rfc908.html
http://www.faqs.org/rfcs/rfc1151.html

Share this post


Link to post
Share on other sites
A thing worth mentioning regarding ACKs is piggybacking; withhold sending of acks for a little while, and when an outgoing regular packet is sent tack the acknowledges to the end of it...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Rozik
Its for a Student project



ReplicaNet is well written because it is in nice separate modules that are easy to use because the documentation is top notch. As a bonus according to the ReplicaNet site license page ( http://www.replicanet.com/pricing.html ) you can already use the library for shareware and educational use, without having to apply.

Share this post


Link to post
Share on other sites
You typically want to send a smarter representation of "ack", such as "I ack all packets from N to M". It should also be legal to ack a packet more than once. That way, the first ack getting lost doesn't matter, because the next packet will contain re-acks of the same packet range (plus any new packets). You should have some policy for how far back it's useful to ack packets; for example, if you know (from other side acks) that the sender has received your acks, you can move the lower edge of your ack window forward.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

One of the 'window' methods is to send an ack piggybacked on upline messages and periodicly if not sent otherwise and send multiple acks in the form of a first packet index (2 or 4 byte) and a bitmap (16 or 32 bits) indicating which packets
in the window [ index .. index+span ] were not received. As packets are received the window slides forward (all packets below the index are ACK acknowledged) when the server sends its own index (2 or 4 byte) acknowledging reciept of the ACKs the client sent.

Packets are resent after a certain number of higher numbered packets have already been sent (and a maximum time)

I send large packets and use a 32 bit mask and start throttling if a packet is not acknowledged at about mask slot 20.


Unfortunately there is no real 'simple' reliable ACK scheme because of the possibilities of Data and ACK packets being lost (as well as out of order cases)

-----

One scheme (for small packets) has the current data being piggybacked on the subsequent packet (effectively always sent twice). This catches most of the single packet loss which is most common loss (gets rid of the usual long ACK failed resend delay). It adds extra data load though if you send alot of data.


Another scheme I use for file/block transfers (where data cant be used untilo the whole arrives) is to send all the packets (1kB - 1.5kB data each) and then get back a ACK n-bit window bitmask for all those packets (and then resend the missing ones as a set and repeat until all have been received successfully). Its alot simpler for the limited use application.


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