Hi, I'm developing my own network protocol (on top of udp) and I'd love to hear some input how to best implement my packet acknowledgement. At the moment I'm giving each packet a sequence number and acknowledge the last 32 received packets with the last received sequence number and a 32 bit vector for the consecutive packets. I think this is a very frequently used idea, but it has two essential disadvantages in my opinion: 1) If one side sends approximately 32 times more packets then the other side, packets get artificialy lost because some acks get skipped. This is not a big problem, because you simply can send empty packets which contain only acks to prevent it. 2) A bigger problem is if you have bursts of consecutive lost ack packets. Even if you assume that you have a 1:1 correspondence for send/received packets, each packet is acknowledged 32 times. And if these packets get lost you will never get an acknowledgement, although the other side has successfully received the packet. A simple solution would be to acknowledge not the latest 32 received packets, but the oldest 32 packets for which the other side hasn't received (and acknowledged) an ack. But I think this had the major drawback that your acks would probably lag behind. Has someone experience with this approach? Another idea would be to combine both ideas and acknowledge both the 32 latest and the 32 oldest packets in each step. But then you have to be very carefull that both vectors do not overlap. Perhaps someone has some new ideas or general input for me? TIA

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.

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.