Archived

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

udp reliability algorithms

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

...no offense, but you''re probably more likely to get answers if you actually ask questions... what problems are you having? or were you just looking for links to webpages? (i suggest spending some quality time with google if that''s the case)

-noh

Share this post


Link to post
Share on other sites
http://www.gamasutra.com has some good articles that discuss this. Just go to their search page and put in "UDP" ( you may have to register, but no biggy).

Share this post


Link to post
Share on other sites
Well, the following is from a mail I recently sent to the SDL mailing list. It might be useful since it''s kept general. Note, I didn''t edit it from the original mail I sent. Anyway, here goes:

<---
This is what Quake and Half-Life use, and what I''ve implemented into my own
game (more or less). The protocol supports both reliable and unreliable data,
however it does not (for simplicity) allow data to arrive out of order, as
this would make the processing of commands unnecessarily complex anyway, and
the focus of the protocol is on unreliable data.

Every packet is prefixed with a short header, which includes a sequence (SEQ)
and an acknowledge (ACK) number. The highest two bits of these numbers are
reserved for other purposes.
Whenever a packet is sent, the SEQ is increased by one. The sent ACK is
always the last received sequence number. Unreliable data is just sent like
this.

Whenever there''s reliable data to send, a bit in the SEQ is set, indicating
reliable data. If the packet only contains part of a block of reliable data,
a second bit is also set.
After a packet with reliable data has been sent, the sender will not send
anymore packets with reliable data until the previous one is acknowledged.

On the recieving end, packets with illogical SEQ/ACK (this includes old SEQs)
are silently ignored. This will prevent most IP spoofing attacks.
If the packet doesn''t contain reliable data, its contents are simply
forwarded to the game logic.
If, on the other hand, it does contain reliable data, a number of things is
done:
First of all, the protocol keeps track of a "reliable sequence". The reliable
sequence is a single bit which is flipped whenever a reliable packet is
recieved. This reliable sequence is sent together with the ACK of a packet.
If a party receives a flipped reliable sequence bit, it knows that the
previous reliable packet has been received.

Secondly, if there is more reliable data to wait for (second bit in ACK is
set), the data is stored for later. Otherwise, all the reliable data received
up to now is forwarded to the game logic.

Unreliable packets are never resent (obviously)
Reliable packets are resent when we recieve an ACK greater than the original
SEQ number of the reliable packets without a change of the reliable sequence
bit.
Additionally, the protocol forces an empty packet every 500ms if no other
data is being sent.

Whenever a reliable packet is sent, the code looks for unreliable data that
might be put into the packet as well. The receiving game logic doesn''t have
to differentiate between reliable and unreliable data.

This protocol works pretty well for a shooter situation: both sides keep
sending data; the server sends frame updates at a constant rates, and the
client regularly sends movement commands. All these events are unreliable
(note that a client''s movement command also contains the two previous
movement commands as backup).
The occasional reliable data will eventually reach the other side without
impacting overall performance.

However, the maximum reliable data bandwidth is rather low, because no new
reliable data is sent until the previous block is acknowledged. So if you
really need lots of reliable data, you need to come up with something else.
--->

cu,
Prefect

Share this post


Link to post
Share on other sites
umm u say that if u send a reliable packet adn dont get nething in return
then ull never be able to send another reliable thing
what happens when u dont get a reliable thing
resend every 100ms? 200? 10?
thats what i would like to know
ta

Share this post


Link to post
Share on other sites
Well, we''re talking about an FPS here, and in a typical FPS situation the server will send a world update every frame, and the client will send a movement command every frame. So that''s not an issue in an FPS.

If this is not the case, you should probably send "keepalive" packets, maybe two or three per seconds or so. That''s obviously only a hack...

cu,
Prefect

Share this post


Link to post
Share on other sites
Do000d: a common way is to resend an unacknowledged reliable packet after N seconds, where N is a function of the RTT (round trip time) The RTT is roughly twice the time it takes for data to travel from your computer to their computer... twice the ping

For example, if you measure the RTT to be 50ms, and you''ve programmed it to resend after 1.5RTT, you''ll resend after 75ms... the longer you wait the more likely you''ll be to catch transmissions that just took a long time, however you''ll have lower efficiency... if you don''t wait long enough, you''ll resend packets that just haven''t had enough time to reach you

granat: different context. in networking terms a frame is the chunk of data that is sent at a given time (not necessarily the same as a packet)

Share this post


Link to post
Share on other sites