UDP with ACK
Author
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
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)
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)
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.
BTW, sorry for my spelling too. I'm not English either.
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
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
Google for "sliding window protocol". There's tons of info out there on this sort of thing.
Google for "RFC908". This is a protocol that could be implemented over UDP. The docs are pretty good at explaining how packet acknowledgment works.
Author
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?
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?
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
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...
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
