5. Reliability

UDP loses, duplicates and reorders datagrams. Most of the game does not mind: an input or a snapshot is replaced by the next one a few milliseconds later. Events (a spawn, a death, a player leaving) happen once and must arrive. This section specifies how each datagram acknowledges those of the peer, how events are resent until acknowledged, and how a peer notices that the other one is gone. It relies on the sequence, ack and ack_bits fields of the header (section 2).

5.1 Acknowledgements

Each peer numbers its datagrams as section 2.2 requires. The first datagram a peer sends in a session MUST have sequence 0.

Each peer keeps, for the datagrams it received from the other one:

• ack: the most recent sequence received, compared as in section 2.2;
• ack_bits: bit n (bit 0 being the least significant) set when sequence ack − 1 − n was received too.

Every datagram sent, whatever its type, MUST carry the current values in its header: each datagram thus acknowledges the last 33 datagrams of the peer, and acknowledgements need no packet of their own. Before anything was received, ack MUST be 65535 (the sequence before the peer's first one) and ack_bits MUST be 0.

When a datagram is received:

1. If its payload is invalid, the datagram MUST be dropped and MUST NOT be acknowledged (section 1.5). So MUST a Snapshot whose baseline the client does not have (section 4.8): its acknowledgement tells the server which snapshots can be baselines.
2. If its sequence is more recent than ack, the sequence becomes the new ack, and ack_bits is shifted left by the difference, the previous ack becoming the bit of its distance. Bits pushed past bit 31 are forgotten.
3. If its sequence is 1 to 32 steps before ack, the bit of its distance is set.
4. Otherwise (the same sequence as ack, more than 32 steps before it, or 32768 away from it), the datagram MUST NOT change ack or ack_bits. A datagram whose sequence was already acknowledged is a duplicate: a receiver SHOULD ignore its payload, except the events of an Event datagram, which are filtered by their own ids (5.3).

For example, after receiving sequences 0, 1 and 4, then 3 late, ack is 4 and ack_bits is 0b1101: 3, 1 and 0 were received, 2 was not.

A sender reads the ack and ack_bits of every datagram it receives, invalid payloads excepted, and takes each sequence they acknowledge as delivered. It MUST ignore an ack more recent than the last sequence it sent, and acknowledgements of sequences it never sent: so the initial ack of 65535 acknowledges nothing.

5.2 Event datagrams

The payload of an Event datagram (type 5) is a list of events:

Field	Type	Content
count	u8	Number of events that follow, 1 to 255
then, count times:
id	u16	Id of the event (5.3)
length	u16	Number of bytes of the event
data	length bytes	The event, as specified in section 4.4

A datagram MUST NOT exceed 1200 bytes (section 1.3), so an event holds at most 1200 − 18 − 1 − 2 − 2 = 1177 bytes. A receiver MUST drop the whole datagram, without acknowledging it or handing over any of its events, when count is 0, when an event goes past the end of the datagram, or when bytes remain after the last event.

Two events, AA BB with id 0 and an empty one with id 1:

02  00 00  02 00  AA BB  01 00  00 00
cnt id     len    data   id     len

5.3 Sending and resending events

The sender gives each event an id: 0 for its first event of the session, then 1 more for each event, going from 65535 back to 0. Ids are compared like sequences (section 2.2).

• An event is delivered once the peer acknowledges (5.1) a datagram that carried it.
• An event not delivered MUST be sent again in a new Event datagram, with the same id and the same bytes, when it was last sent at least the resend delay ago. The delay SHOULD be a little more than the round trip time; the Aegis2D implementation uses 100 ms.
• A datagram SHOULD carry the oldest events due first; several events, new or resent, MAY share a datagram.
• A sender MUST NOT have more than 256 events not delivered at once. Past that, the peer has stopped acknowledging; the session is considered lost (5.5).

The receiver hands each event over to the game once: it keeps the most recent id it received and which of the 255 ids before it were received, and ignores an event whose id it received already, or that is 256 or more ids before the most recent one (thanks to the limit above, such an event was received and acknowledged long ago). Events MAY be handed over in another order than they were sent; an event that depends on another one says so in its own data (section 4.5).

5.4 Example

The client sends an event with id 7 in its datagram of sequence 120, which is lost. 100 ms later the event is due again and leaves in datagram 126, which arrives. The server's next snapshot carries ack = 126: the client takes event 7 as delivered and never sends it again. Had the copy in datagram 120 only been late, the server would have handed the event over on the first copy and ignored the second.

5.5 Heartbeat and timeouts

Acknowledgements only reach a peer inside datagrams, and a silent peer cannot be told apart from one that is gone. Every peer therefore sends something regularly.

• Heartbeat. A peer in a session MUST send a datagram at least every 50 ms: when it has sent nothing to the other one for 50 ms, it sends a Heartbeat (type 6). During a game, inputs (every tick) and snapshots (20 per second) already meet this rule, and heartbeats only flow while a peer has nothing else to say (a client on a menu, a server waiting for players).
• Payload. A Heartbeat has an empty payload: the header alone, 18 bytes, carrying the acknowledgements. A receiver MUST drop a Heartbeat with bytes after the header.
• Timeout. A peer that has received no valid datagram from the other one for 5 seconds MUST consider the session lost: the server ends the session and tells the other players (section 4.4), the client shows that the connection was lost. Only valid datagrams count: an invalid or foreign one does not keep a session alive.
• Events never acknowledged. A sender that would need more than 256 events in flight (5.3) MUST also consider the session lost: the peer still sends datagrams but acknowledges nothing.
• Leaving. A peer that leaves on purpose SHOULD send a Disconnect (type 7, empty payload) three times in a row, as it is not resent. A receiver ends the session on the first one; a lost Disconnect is caught by the timeout, or on the server by the closing of the TCP connection (section 1.3).

The 50 ms heartbeat keeps acknowledgements within a round trip plus 50 ms, below the 100 ms resend delay of 5.3 on a usual network, so few events are resent for nothing; a resend that was not needed costs a few bytes, never a duplicate event.

5.6 Summary

Type	Acknowledges the peer	Acknowledged	Resent
Connect, Accept	yes	yes	until answered, by the handshake (section 3.4)
Input, Snapshot	yes	yes	no: the next one replaces it
Event	yes	yes	its events, until acknowledged (5.3)
Heartbeat	yes	yes	no
Disconnect	yes	yes	no: sent three times (5.5)

Every datagram carries the acknowledgements of the peer and is acknowledged in turn, but only the events of Event datagrams are resent.

Value
Acknowledgement window	33 datagrams (ack and the 32 bits of ack_bits)
Resend delay	100 ms
Events in flight	256 at most
Largest event	1177 bytes
Heartbeat	at least one datagram every 50 ms
Session timeout	5 s without a valid datagram

Implementation

net::ReliableChannel (aegis2d/net/reliability.hpp) implements 5.1 to 5.3 for one peer: next_header() numbers each datagram and fills its acknowledgements, send() queues an event, write_events() writes the Event datagram of the events due, and receive() and read_events() take in what the peer sent. net::AckTracker keeps ack and ack_bits. The acknowledgements also give the round trip time: ReliableChannel::rtt() smooths the time between sending a datagram and receiving the first acknowledgement of it, as TCP does (RFC 6298). The unit tests exchange 1,800 events under 10% loss, and 70,000 events each way under 30% loss, with datagrams delayed, reordered and duplicated: every event arrives once. The heartbeat and the timeouts of 5.5 belong to the sessions of the game server and of the client, which use the values of 5.6.