Game Networking

Note: Not built yet: reliable messages larger than one packet (the header and the API leave room for fragmentation; a message over maxReliableBytes(cfg) is refused); encryption and authentication (the handshake proves a client's address, nothing more; anyone who can read the packets can read and forge them); congestion control beyond a two-state send rate; a datagram batch (recvmmsg) on the socket; a fixed key schedule or connect tokens; and the final name of the package, which is a working name (netmsg). Tested over IPv4 on 127.0.0.1, on Windows and Linux; not yet across machines.

netmsg is the protocol a game server and a game client speak over UDP, written in Cone after Glenn Fiedler's Gaffer On Games. TCP gives an application one reliable ordered stream, so a lost packet holds everything behind it, including the newest position of a moving thing that makes the lost one worthless. The package carries two kinds of data on one connection instead:

• Latest-wins values, on streams told apart by a number. A value is sent once and never resent; a newer value for the same stream replaces it if it has not gone yet, and an older value never arrives after a newer one. Positions and snapshots are of this kind.
• Reliable messages, which arrive once, in the order sent, whatever the link does. Each is kept until a packet that carried it is acknowledged, and is put in later packets until then: the messages are resent, never the packets. Joins, chat, requests and events are of this kind.

It carries bytes and messages, not a world. What a snapshot holds, and how a client interpolates, predicts and corrects, belong to the application.

A connection looks the same to the application however it is made: over real UDP sockets, between two actors of one process with nothing in between (single player, the server in the same process as the player), or between those actors across a simulated lossy link (to try prediction and interpolation with no socket). The application is written once.

Using it#

An application talks to a connection as an actor talks to any actor: it sends messages to a Connection, and what the other end sends arrives as events at a EventHandler, a closure of the application's own that hands each event on, usually as a message to an application actor. A server's one handler serves all its clients, told apart by the id each event carries.

mod hello;

import stdio use *;
import collections use *;
import thread;
import time use Duration;
import iocore use SocketAddr;
import actors;
import netmsg use *;

actor Greeter {
  // Every event of every connection arrives here
  pub async do onNet(self, ev NetEvent) {
    match ev {
      case let j Joined { j.conn.sendReliable(bytes("hello")); }          // open: send through j.conn
      case let m Message { print <- "heard ", String.fromBytes(m.data.view()).view(), "\n"; }
      case let u Update { }                                              // a latest-wins value
      case let l Left { print <- "left\n"; }
    }
  }
}

fn bytes(s &str) List[u8] {
  var b = List[u8].empty();
  putBytes(&mut b, s);
  b;
}

fn main() {
  let g = new Greeter();
  let h = eventHandler(new Uni[fn(ev NetEvent) + Sendable](fn(ev NetEvent) [g] { g.onNet(ev); }));
  let server = mustListen(SocketAddr.localhost(0u16), NetConfig.defaults(), h);
  let client = mustConnect(SocketAddr.localhost(server.port), NetConfig.defaults(), h);
  thread.sleep(Duration.fromMillis(500i64));      // the program runs
  client.endpoint.shutdown();                     // before the program ends
  server.endpoint.shutdown();
}

This prints heard hello twice (each end greeted the other) and then left twice.

The pieces:

• NetEvent has five variants. Joined{id, conn}: the connection is open, and conn is the actor to send through. Left{id, reason}: it has ended, for a CloseReason (Local, Remote, TimedOut, Overflow, Refused or NoAnswer); nothing more arrives for that id. Message{id, data}: a reliable message. Update{id, stream, data}: the newest value of a stream. Refused{id, reliable, stream, why, size, limit}: a send of this connection's was refused and nothing was sent (below). A connection's events arrive one at a time, in the order they happened. A server numbers its clients from 1; a client's one connection is 1.
• eventHandler(f) makes an EventHandler of a closure (Uni[fn(ev NetEvent) + Sendable]); channelHandler(tx) makes one that puts each event on a Sender[NetEvent], for a thread that is not an actor (a frame loop drains the receiving end each frame). The closure must not wait. It is called under a lock, so one handler shared by many connections is called one event at a time.
• mustListen(addr, cfg, h) binds a UDP socket and accepts clients; mustConnect(addr, cfg, h) dials a server, the handshake running in the background (the handler hears Joined, or Left with NoAnswer or Refused). Each gives a BoundEndpoint: its endpoint (an actor) and the port the socket has (port 0 asks the system to choose). listen and connect give a Result[BoundEndpoint, IoError] instead of a panic when the socket cannot be bound.
• endpoint.shutdown() closes every connection (each tells its peer), sends what is queued, and closes the socket. Call it before the program ends; a program that ends in the very instant it calls it may lose the disconnect datagrams (an actor paused on I/O does not hold the program open), and the peers then time out. endpoint.connections() answers how many connections are open.

A connection#

A Connection is an actor handle, Sendable like any, with these behaviours:

• sendReliable(data), data a List[u8] of at most maxReliableBytes(cfg) bytes (1,173 with the default packet size). A message over that is refused: nothing is sent, the connection goes on, and its own handler hears Refused (with why TooLarge, the size offered and the limit). The same on every kind of connection, in-process included; fragmentation is not built. (A send is a message to an actor and answers nothing, so the refusal comes as an event, where the application already hears everything else; a caller that wants to know first compares with maxReliableBytes.) If reliableWindow (1,024) messages are already waiting, the peer is not keeping up and the connection ends with Overflow.
• sendLatest(stream, data): sets the value of stream number stream (a u16), at most maxLatestBytes(cfg) bytes (1,171). A connection carries 64 streams. A value over that, or for a 65th stream, is refused as a message is (TooLarge, TooManyStreams). A newer value replaces one still waiting; the receiver never gets an older value after a newer one, so two streams, or one stream's values over a lossy link, cannot overtake each other.
• setStreamWeight(stream, weight): when a packet cannot carry every waiting value, each waiting stream's priority grows by its weight with every packet it waits through (1 by default), and the highest goes first; a stream that did not fit keeps what it gathered, so everything is sent eventually and the important streams often (Fiedler's priority accumulator).
• close(): the other end is told (the disconnect packet is sent five times).
• await stats() answers a ConnectionStats: rttMs and rttVarMs (the smoothed round trip time, for clock synchronisation and an interpolation delay), lossPermille, good (sending at the good rate), and counts of packets and messages. All zero for an in-process pair, which has no link.

Without a socket#

pairInProcess(handlerA, idA, handlerB, idB) joins two connections in this process. What one sends, the other's handler hears, in order, at once: nothing is lost or late, and there are no packets. A game whose server and player are in one process (single player) joins them this way and runs the same server and the same player as it would over UDP; the ids are what each handler's events carry (a server's handler shared by several pairs gives each a different one). pair.a and pair.b are the two connections.

pairSimulated(cfg, aToB, bToA, seed, handlerA, idA, handlerB, idB) joins them the same way but runs the real protocol between them: packets, acknowledgements, resends, the rate control, across a LinkSim that does what aToB and bToA (each a LinkConfig) say. A thread ticks both ends every millisecond, so the delays are real time. Call stop() on the result when done. This is for trying prediction and interpolation with no socket.

A LinkConfig is lossPermille (the chance in 1,000 that a packet is dropped), latencyMs, jitterMs (a random extra delay up to this), duplicatePermille, reorderPermille and reorderMs (a packet held back this long, so later ones pass it). LinkConfig.perfect() does nothing; LinkConfig.lossy(loss, latency, jitter) loses, delays and jitters.

startLossyRelay(server, toServer, toClient, seed) does the same to real sockets: an actor that takes datagrams from clients on a port of its own (relay.port, on 127.0.0.1) and passes them to the server, and the server's answers back, through a LinkSim each way for each client. A client that connects to the relay's port meets loss, delay, duplication and reordering with the real protocol on real UDP. relay.stop() ends it.

Configuration#

A NetConfig, the same on both ends (NetConfig.defaults(), whose fields are public), holds: maxPacket (the largest datagram sent, 1,200 bytes, so that a packet and its headers fit the smallest IPv6 path), goodRate (30 packets a second) and badRate (10), badRttMs (250), keepAliveMs (100), timeoutMs (10,000), resendMinMs (40), connectRetryMs (250), connectTimeoutMs (5,000) and a server's maxClients (64).

The protocol#

Every number is written most significant byte first. Every datagram begins with the four bytes NMS1 (the protocol and its version), then a kind byte.

Packets#

Kind	Contents	Size
0 Request	the client's salt (8 bytes), zero padding	1,200
1 Challenge	the client's salt, the server's cookie (8)	21
2 Response	the client's salt, the cookie, zero padding	1,200
3 Accept	the session (8)	13
4 Payload	the session (8), sequence (2), ack (2), ack bits (4), count of reliable messages (1), count of values (1), the messages, the values	23 to 1,200
5 Disconnect	the session	13
6 Denied	the client's salt	13

A reliable message in a payload packet is its id (2 bytes), a length with two reserved flag bits (2) and its bytes. A value is its stream (2), its sequence in the stream (2), a length with two reserved bits (2) and its bytes. The reserved bits are for fragmentation; a packet that sets either is refused as malformed.

Acknowledgement and loss#

Each payload packet carries its own 16-bit sequence number, the sequence of the newest packet received (the ack), and a bitfield telling which of the 32 packets before that one have arrived: so each acknowledgement is sent about 33 times and survives heavy loss. Sequence numbers wrap and compare so (a is newer than b when it is ahead by less than half the range). A packet is never resent. A packet is lost when it is 33 packets behind the newest ack and unacknowledged; the loss measure (lossPermille) is a moving average of those fates over about 64 packets. The round trip is measured from the packets acknowledged and smoothed as RFC 6298 does (an eighth of each sample, and a mean deviation); it includes the peer's wait for its next packet, since an acknowledgement rides on one.

Reliable messages#

A message has an id, 16 bits, counting from 0. The sender keeps it until a packet that carried it is acknowledged, and puts it in a packet when it has not been sent, or was last sent longer ago than the resend delay (the smoothed round trip plus four times its deviation, not under resendMinMs, 100 ms before there is a measurement). Due messages go first, oldest first, while they fit. The receiver keeps messages that arrive early in a ring and gives the application each in order once its predecessors have come; a message it has already delivered, or one more than 1,024 ahead, is ignored. At most 1,024 messages are queued or unacknowledged.

Latest-wins values#

Each stream numbers its values; the receiver delivers a value only if its number is newer than the last delivered on that stream. After the reliable messages, the streams that have a value waiting are added to the packet by priority until the next would not fit; the sender then forgets the values it sent.

Rate#

A connection sends at most 30 packets a second, and 10 when the smoothed round trip is over 250 ms (Fiedler's two-state controller): it goes back to 30 only after the round trip has stayed under the limit for a penalty time, which starts at 4 s, doubles (up to a minute) when it goes bad again soon after being good, and halves (down to a second) for every ten seconds spent good. A packet is sent when there is something to say: a message due, a value waiting, or a reliable message to acknowledge; otherwise a keep-alive every 100 ms, which carries acknowledgements. Nothing arriving for 10 s ends the connection (TimedOut).

The handshake#

A client sends a Request with a random 64-bit salt, padded to 1,200 bytes, every 250 ms. The server answers with a 21-byte Challenge carrying a cookie: SipHash-2-4, under a 128-bit key only the server holds, of the client's address as text, its salt and the time in ten-second steps. The server keeps nothing for a Request. The client answers with a Response (padded to 1,200 bytes) carrying the cookie; the server recomputes it, accepting the current time step and the one before, and so believes the client can receive at the address it claims. The session is the salt xor the cookie; the server opens the connection and answers Accept, and every later packet in either direction carries the session, a packet with another being dropped. A spoofed source address therefore never gets a connection, and a server cannot be used to amplify an attack: the replies are a sixtieth of what asked for them. A full server answers Denied. A client whose Accept is lost connects on the first payload packet the server sends. The connection attempt fails after connectTimeoutMs.

There is no encryption: the session is a shared secret, and anyone who can read the packets can read the data and forge packets. The place for it is the handshake (a key agreed there) and the payload packet (where it would be used).

The sans-IO core#

The protocol is plain data and functions, with no socket, no clock and no thread, so it runs inside an actor, on an OS thread, or in a test on a synthetic clock. A ConnectionCore is one connection's half: ConnectionCore.make(cfg, session, now); sendReliable(bytes) and sendLatest(stream, bytes) (each answers false when refused); receive(packet, now, events) acts on one datagram (false if it is not this connection's or is malformed); poll(now, out, events) appends the packets to send and the events that happened; nextDeadline() says when to call poll next; and rtt(), lossPermille(), stats(), close(). The events are CoreEvent.Reliable{data}, CoreEvent.Latest{stream, data} and CoreEvent.Closed{reason}. ChallengeGate is the server's side of the handshake (handle(addr, datagram, now, reply) answers a GateVerdict) and ClientHandshake the client's. SimPair joins two ConnectionCores across two LinkSims on a clock the caller moves, which is how the protocol's tests run:

var clock = Clock.synth();
var p = SimPair.make(NetConfig.defaults(), LinkConfig.lossy(200u32, 40i64, 30i64),
                     LinkConfig.lossy(200u32, 40i64, 30i64), 1u64, clock.now());
p.a.sendReliable("one");
var ms = 0i64;
while ms < 3000i64 {
  clock.advance(Duration.fromMillis(1i64));
  p.step(clock.now());                    // packets arrive, both ends are polled, packets go into the links
  ms = ms + 1i64;
  // p.eventsB holds what b has heard
}

The wire level is public too (putU16 and the rest, PacketReader, seqNewer, sipHash24), and so are the actors a socket needs: Endpoint owns the socket and routes each datagram to the Connection it belongs to, sending each connection's packets through the socket. An application reaches its endpoint through listen and connect and uses only shutdown.

What runs where#

A UDP endpoint is an actor holding an aio UdpSocket, so it needs no thread of its own (every aio user in the program shares one I/O thread): a behaviour of the endpoint awaits each datagram in turn and handles it, sends the datagrams connections give it, and sleeps until the earliest deadline any connection has, to tick the ones that are due (aio's sleep; it never waits on a worker thread, and there is no fixed tick). Each connection is an actor that drives its ConnectionCore. Nothing waits in an actor. On Windows the I/O thread's loop is an I/O completion port, on Linux epoll; netmsg binds no operating system call of its own. The events still reach the application through one closure shared by every connection (under a lock), since actors cannot yet be generic.

Comes back in#

• The Standard Library — the catalogue of packages.
• HTTP, TLS and URLs — the other networking packages.