Acknowledgement management... RFC

In general, a lost ack packet isn't a big deal since it will simply trigger a resend, then a dropped duplicate packet and a second ack being sent. Unless it happens very frequently of course.

Why would I ack packets more than once? You should Ack the last packet recived in the sequence and slide the window it is no longer useful to ack that packet.

What do you get by acking more than one packet? Are you trying to emulate a window by acking so many packets?

Both sides already know the window length, by acking the last contiguous packet both sides know where to position the window so there is no need to ack multiple packets. If you are worried about overloading the connection by dumping a window of packets on the line, do a conservative resend and only resend the last non acked packet until you receive a packet with a new last packet received.

Quote:

Original post by stonemetal Why would I ack packets more than once? You should Ack the last packet recived in the sequence and slide the window it is no longer useful to ack that packet. What do you get by acking more than one packet? Are you trying to emulate a window by acking so many packets? Both sides already know the window length, by acking the last contiguous packet both sides know where to position the window so there is no need to ack multiple packets. If you are worried about overloading the connection by dumping a window of packets on the line, do a conservative resend and only resend the last non acked packet until you receive a packet with a new last packet received.

This assumes packets are withheld until delivered in order? I'm assuming the OP wants to support reliable unordered messages in which case just knowing the last received sequence isn't enough. 32 bits seems a bit much tho unless you're willing to wait a bit extra to collect acks before sending; I'd settle for 16 or 8, and send multiple ack messages when more are needed.

Quote:

Original post by stonemetal Why would I ack packets more than once? You should Ack the last packet recived in the sequence and slide the window it is no longer useful to ack that packet. What do you get by acking more than one packet? Are you trying to emulate a window by acking so many packets?

I'm doing this because it has a lot of advantages:

1) You don't have to send 1 packet for every packet you receive. Which is sometimes cumbersome.
2) If you have moderate packet loss and lose an ack you don't have to automatically rerequest the data or assume that the packet was lost, since the missing ack is already on the line, which is much faster than anything else -> a lot less traffic -> speed.

My problem is if you have heavy packet loss in one direction or especially lose a lot of packets in a row. I think if you use an WLAN it is not very unusual to lose all packets for a couple of hundred ms. And depending on your actual traffic this could easilly be hundreds of packets.

I wish there were a comprehensive material on reliable UDP implementation.

All the hacks and savings aside (such as data sizes):

Each packet has a sequence number (strictly ordered)

When received, sequence number is marked as acknowledged. These acks are then sent along with outgoing packets, sent immediately, or sent periodically. Implementation and domain-specific detail.

Missing packets are sent as un-acks in the same way. Rather than sending acks, you send which packets are missing. When and how again depends on same as above.

Outstanding packets are stored somewhere. This can be a fixed or dynamic buffer, which remembers which packets are currently "on the wire". When sending, you put a packet in the buffer. If buffer is full, client is stalled or temporarily not responding.

When you receive an ack, you remove packet from buffer. When you receive un-ack, you resent the packet. Periodically, you send packets from this buffer again. If you don't receive a response from other peer in given time, or using some domain-specific criteria, you consider them timed out.

Acks/un-acks can be defined to cover all-before, so sending ack with 1234 means all packets 0-1234 arrived. Wrap-around can be handled fairly trivially.


Sequence number should be something reasonable based on transfer rate ratio and expected latency tolerance. Assuming we send 1500-byte packets, transferring 1Mb of data, and need to tolerate 5 second stalls, we may need to store at least ~3500 outstanding packets. To avoid wrap-around issues, it may be convenient to double that value, or simply use 16-bit sequence number, giving us 18 second window before wrap around becomes an issue.

The numbers and actual implementations here will depend on actual requirements. That's just basic canonical approach to ID management.

Quote:

Original post by WeirdCat I'm doing this because it has a lot of advantages: 1) You don't have to send 1 packet for every packet you receive. Which is sometimes cumbersome.

You are dealing with constant two way communication if you put the ack at the end of the messages you are sending out on a regular basis why would you ever send an ack packet for every packet you receive?

Quote:

2) If you have moderate packet loss and lose an ack you don't have to automatically rerequest the data or assume that the packet was lost, since the missing ack is already on the line, which is much faster than anything else -> a lot less traffic -> speed.

Again if you put the ack in every message(assuming regular two way communication) the missing ack is already on the line anyway. Why have a super ack? Dumping the 32 missing packets on the line is only going to increase congestion and cause more lost packets that is why when you loose a packet you stop dumping and try to just push one through then when the congestion is past you go back to shooting multiple packets at once.

Quote:

Original post by stonemetal You are dealing with constant two way communication if you put the ack at the end of the messages you are sending out on a regular basis why would you ever send an ack packet for every packet you receive? Again if you put the ack in every message(assuming regular two way communication) the missing ack is already on the line anyway. Why have a super ack? Dumping the 32 missing packets on the line is only going to increase congestion and cause more lost packets that is why when you loose a packet you stop dumping and try to just push one through then when the congestion is past you go back to shooting multiple packets at once.

I don't know what you mean with this "super ack". I think you misunderstood me I'm sending my ack vectors piggy-backed with my regular data packets, there are no special ack or super ack packets. Each ack vector consist of a reference sequence number (where the vector begins/ends) and a bit mask for the 32 following/preceding packets.

I'm assuming you care about whether the acks get there or not because you want reliable delivery of the data. Based on that assumption:

The easiest solution would be to let the sending side not get more than 32 packets ahead in sending. You have an ack window of 32 packets, which means the window closes when you haven't gotten acks back for the last 32 packets. At that point, try re-transmitting the earliest un-acked packet(s).

Similarly, if you send a packet, and haven't heard anything back for a while, re-send the earliest un-acked packet(s) on a time-out. Typically, you want to use exponential back-off in the timing of re-sends, to avoid flooding the network when the other end actually goes down.

Finally, if there's enough of a black time that you're hopelessly behind, you probably want to report "connection lost" and drop the connection.

Quote:

Original post by hplus0603 I'm assuming you care about whether the acks get there or not because you want reliable delivery of the data. Based on that assumption:

I don't want reliable delivery of the data, I just want reliable(*) notification if the packet arrived or not. I'm implementing reliable data transfer on top of that at a higher protocol level. So that my application can mix (un-)reliable and (un-)ordered data in each packet.

My question was directed at how to optimise that in respect that the ack/nack notification is very fast (highest priority), very few resends, has to scale very good from 1 packet every minute to 10000 packets every second, good data throughput and the solution should have a high lag/drop tolerance. Short: Nothing less than the wet dream of every network protocol developer. ;-)

(*) If a packet isn't (n-)acked in some time it will be assumed, that it wasn't received.

I still think that using a window of 32 packets is reasonable for your mechanism.

If you need a larger window to allow larger throughput, then you can have a second mode in the ack packets that allow you to span a larger range, and only switch to this mode when you detect that you have to.

Well, how about just collecting sequence numbers you need to acknowledge for a short period of time (to avoid sending excessive amounts of ack messages), then create the best possible ack message from that; Be it one or several bit vectors (7-bit encoded maybe?). Or is the original question how to best build such an ack message?
10000 packets per second will require a lot of available sequence numbers and a healthy size on the send/receive buffers when lag rises and spikes makes the packets pile up.
Using a window... won't that potentially stall the entire stream when loss occurs?

Quote:

Using a window... won't that potentially stall the entire stream when loss occurs?

That's the point of a window. It allows you to send up to some determined amount of data before a lost packet stalls the pipeline. The trick is to tune the window size based on the available bandwidth, queuing depth and latency to allow good throughput under light loss, but not overwhelm the network with unnecessary packets and cause congestion when loss starts shooting up. A large, fixed-size window will do terrible things to a router when congestion hits.

Yes, I definitely see the point for say a file transfer protocol, but does it still make sense for a gaming protocol to use it? When the window frame is hit I assume the client would start buffering messages locally and that doesn't really make sense for alot of game data... but then again, only reliable data would need to use the window... or? To combat congestion I guess we need to stop sending stuff alltogether and that really feels wrong for a game.

Quote:

does it still make sense for a gaming protocol to use it?

Are you saying games should somehow be allowed to flood a router that's undergoing congestion? That would just lead to collapse, instead of service degradation.

What the game should do when it detects noticeable packet loss (and "noticeable" really is just more than one out of 32) is to throttle back how much data it tries to get through the pipe, because the pipe is making indications of not being able to sustain the amount you're trying to shove through.

There is no mechanism that will allow you to magically shove through more data than the pipe can sustain. Packet loss more than the occasional wiggled wire or corrupted wireless wave means that you're exceeding capacity at some point along the chain -- the only rational response is to back off on throughput and/or send rate.

I see your point. I've read up on congestion control a bit and I still believe that a simple go-back-n sliding window isn't useful for a game oriented UDP library... you may (almost) as well use TCP. But then again, maybe no one suggested that.
Other versions of congestions control are interesting tho... i've done some simulating and altho straight no-window acking is hard to beat, even under congestion, i've so far gotten the best numbers out of a counting-acks "window" with some backoff and hole detection. The numbers i'm watching are mostly related to latency, not throughput.
If anyway wants the test code drop me a mail.

Backing up a bit:

Quote:

Both sides already know the window length, by acking the last contiguous packet both sides know where to position the window

The problem with doing only contiguous acks is that you can get unnecessary re-sends. If you look at TCP, it introduced selective ack (SACK) as an extension to get around this. I believe that you need something smarter than just ack the last contiguous to be fully efficient -- but you can probably get 90% of the way there with ack-last-contiguous and sufficient memory, smarts and window size.

Quote:

Original post by hplus0603If you look at TCP, it introduced selective ack (SACK) as an extension to get around this. I believe that you need something smarter than just ack the last contiguous to be fully efficient -- but you can probably get 90% of the way there with ack-last-contiguous and sufficient memory, smarts and window size.

What I don't like about selective ack is that it needs possibly a lot of sequence numbers (and therefore a lot of bytes). Even if you combine it with some kind of run-length encoding (RLE) you get possibly very big ack data if you have a constant packet loss like every 4th packet.

I think if I want to handle very long packet loss segments as well as constant single packet loss efficiently I have to use an adaptive scheme with at least 2 different representations of ack data.

Quote:

Original post by WeirdCat What I don't like about selective ack is that it needs possibly a lot of sequence numbers (and therefore a lot of bytes). Even if you combine it with some kind of run-length encoding (RLE) you get possibly very big ack data if you have a constant packet loss like every 4th packet.

I may be confused; but didn't you say you used bit vectors for acks? Assuming you wait a short while before sending acks you should be able to get away with a few bits per ack in average; and simultaneously get negative acks thru (holes in the vector) which enables you to resend faster than the resend timer would do.
Compared to resending the entire rest of the window for a single missing packet you're making a killing :-)

Quote:

Original post by fenghus I may be confused; but didn't you say you used bit vectors for acks? Assuming you wait a short while before sending acks you should be able to get away with a few bits per ack in average; and simultaneously get negative acks thru (holes in the vector) which enables you to resend faster than the resend timer would do.

Just because packet n hasn't arrived at time n+1 doesn't mean it's lost. UDP gives no order guarantees.

Quote:

Compared to resending the entire rest of the window for a single missing packet you're making a killing :-)

The efficiency of chosen scheme will depend on failure characteristics - not on protocol encoding. The entropy needed to convey loss of data is small, and depends almost exclusively on expected on-the-wire window.

- Connection loss: from some point, packets will not arrive.
- Out-of-order: packets arrive in random order, within some short period of time. Difference in required acknowledgments will come from different wait times for ack transmission.
- Random, single occurrence packet loss: enough to send the ID of packet lost
- Consistent, random packet loss: The overhead here will come from large number of resends, which will dwarf any ack management scheme.

For last case: if you have 5% packet loss, and average packet is 400 bytes, if means you need to send 400 extra bytes for every 20 packets. With 2 byte packet explicit IDs, that's 40 bytes of acks per 400 bytes lost, or 0.5% overhead per data successfully transferred (8000 bytes, not even counting UDP/IP overhead). With latest-only ack/nack scheme, that's 4 bytes (1 ack for latest of 20, 1 nack).

But most of this is beyond the point.

Reliable transmission, even moreso if robust, is inefficient. The main reason for choice of UDP is that it allows peers to continue functioning when data is lost permanently.

Reliable transport with resends will break real-time requirements either way. The time of these resends also depends on latency. Typical internet latency should be considered to be 250ms, with up to 5sec tolerance. Anything requiring a round-trip is simply not real-time. Hence most data is sent in a way which allows the peer to continue even if part of it is lost.

For low-latency networks, this is all mostly a non-issue, since they will typically offer high enough throughput for the overhead to be insignificant compared to UDP/IP header overhead.

But the by far biggest savings can be obtained at application level, not on wire.