Skip to content

Server: O(N) transmit and timer paths, and no SYN cookies, for thousands of connections #12

Open

Description

@pylaterreur

The README says the server's timer and transmit paths scan every connection and aren't meant for many connections yet. Following the OpenMPTCProuter discussion (Ysurac/openmptcprouter#4400), the server role there would face exactly that case: each router opens one MPTCP connection per proxied LAN flow, so a VPS with a few routers holds a few thousand connections, most of them idle, on 1–2 vCPUs. Here is where the cost comes from at e9aa443, and a proposal.

Where the time goes

  1. Endpoint::poll_transmit returns one packet per call, walking conns round-robin from the cursor and calling update_recovery() and select_control() on each connection it passes until one has something to send. With one busy connection among N idle ones, every packet costs about N connection visits. At 1 Gbit/s (~83k packets/s) and 3,000 connections that's ~250M visits per second.
  2. Endpoint::poll_timeout recomputes the earliest deadline over every connection and subflow, and handle_timeout walks every connection again. An event loop calls both on every wakeup, so each one is O(N).
  3. SYN handling: without SYN cookies, a listener at max_half_open (default 256) drops SYNs, so a SYN flood, or every router reconnecting after a server restart, locks out real clients.

Proposal

  • Transmit: a ready queue of connection handles. A connection is queued when something makes it able to send (data written, an ACK or retransmission due, a timer fired, a window opened), and poll_transmit only pops from it. Popping in FIFO order and re-queuing a connection that still has work keeps the current round-robin fairness.
  • Timers: each connection caches its next deadline (the min of what poll_timeout computes for it today), and the endpoint keeps a min-heap of (deadline, handle) with lazy deletion. poll_timeout becomes O(1) and handle_timeout only visits connections whose deadline has passed.
  • SYN cookies when the listener is at its cap, as Linux does in net/mptcp/syncookies.c. MP_CAPABLE works statelessly in v1 because the third ACK carries both keys. MP_JOIN needs a small table, since its third ACK doesn't repeat the nonces.

Behaviour stays the same: same packets, same fairness and the same public API. A test could open a few thousand idle connections next to one bulk transfer and check that the per-packet cost stays flat.

I'd be glad to send these as PRs, one per item, starting with the transmit queue and the timer heap. Would you take them, and is there a spec section in docs/ you'd like them to follow?

Activity

  1. mp0rta commented on Oct 17, 2026

    @mp0rta
    Owner

    Thanks, I had this on my list for later, but I'm tied up with mqvpn at the moment, so I'm glad you're taking it on.
    Yes, please send them as separate PRs, the transmit queue and the timer heap first. There's no spec in docs/ for this; this issue is enough.

    A few requests:

    • Keep the current full scan as a test-only oracle, and add a differential test that shows the same packets, in the same order, and the same poll_timeout. Walking a BTreeSet of ready handles from the cursor keeps today's order exactly.
    • Mark a connection ready whenever an endpoint call reaches it or its timer fires, rather than listing the causes that let it send. This includes connection(h), which hands out &mut Connection.
    • The public API stays the same (poll_timeout stays &self), with no new dependencies.
    • SYN cookies: please post a short design note here first; I would merge them after 0.3.0. My preferences:
      • FreeBSD's layout(r253210; plain TCP, as FreeBSD has no MPTCP yet) rather than Linux's: MSS, window scale and SACK in the ISN next to a 24-bit MAC, so nothing depends on TCP timestamps, which we don't have and peers may not send.
      • The secret from the endpoint's CryptoRng, as for IsnGenerator; HMAC-SHA256 is already a dependency.
      • The server key generated verifiably, as RFC 8684 §3.1 asks, rather than taking the echoed key as Linux does.
      • Joins can stay stateful (§3.2), but please bound half-open joins per connection (SUBFLOW_CAP) rather than by the listener's max_half_open: with thousands of connections, a flood of guessed tokens lands a few joins per second, and each holds a slot for the 180 s SYN R2.

    Reviews may be slow for a while. Thanks for your patience.

  2. pylaterreur commented on Oct 17, 2026

    @pylaterreur
    Author

    The two PRs are up: #14 (transmit queue) and #15 (timer heap), each with the differential test against the old full scan. Here is the SYN-cookie design note, following your preferences. There is no PR for it yet.

    SYN cookies: design note

    When. Only at a listener's max_half_open cap, and only if ListenConfig::syn_cookies is set (proposed default: on, as Linux tcp_syncookies=1 and FreeBSD do). Below the cap nothing changes. With it off, SYNs beyond the cap are dropped as today.

    Cookie (the SYN/ACK's ISS), FreeBSD r253210 layout:

     31                      8 7   5 4   2 1 0
    | 24-bit MAC              | W  | M  |S|P|    low byte XORed with the MAC's top byte
    
    • M: the peer's MSS, rounded down to one of 8 values (FreeBSD's table: 216, 536, 1200, 1360, 1400, 1440, 1452, 1460).
    • W: the peer's window scale, rounded down to one of 8 values (0 means no WS option, then 0, 1, 2, 4, 6, 7, 8). Rounding down under-estimates the peer's window, which is safe. Our own receive scale comes from our config, as in the stateful SYN/ACK.
    • S: SACK permitted. P: which key epoch (below).

    So a cookie connection gets window scaling and SACK without TCP timestamps, which we don't implement and peers may not send.

    MAC and secret. HMAC-SHA256, already a dependency. The input is the local address and port, the remote address and port, the peer's ISN, and the flag byte; the output is truncated to 24 bits. Including the peer's ISN ties the cookie to the SYN it answers.

    The secret comes from the endpoint's CryptoRng, as for IsnGenerator. There are two secrets, as in FreeBSD: an epoch is 15 s (FreeBSD's lifetime), and P is its parity. A sans-I/O core has no timer to reseed them, so the endpoint draws a fresh 32-byte secret from its CryptoRng the first time it sends or checks a cookie in a new epoch, and keeps the previous epoch's. A returning ACK is checked against the secret its P names, so a cookie lives 15–30 s.

    Nothing is drawn until a listener is at its cap. An endpoint that never sends a cookie therefore keeps today's RNG stream, so its keys, nonces and ISNs are unchanged for a given seed.

    Validation. An ACK without SYN, for no known 4-tuple, at a listener that sent cookies in the last 30 s:

    1. iss = ack - 1, irs = seq - 1.
    2. Recover the flag byte and recompute the MAC with the epoch P names. Compare the 24 bits.
    3. On a match, build the TCB as if SYN-RECEIVED had sent that SYN/ACK (MSS, WS and SACK from M, W, S), then process the segment, including any payload, through the normal path.

    A cookie connection holds no half-open slot. Like the RSTs, cookie SYN/ACKs go through a bounded queue (64).

    MP_CAPABLE (RFC 8684 §3.1). The server generates its key verifiably, not by taking the echoed key as Linux does: key_B = HMAC(secret, "key" || 4-tuple || iss), truncated to 64 bits and never 0.

    • key_B uses the same epoch's secret as the cookie.
    • When answering the SYN, if key_B's token collides with a live connection, the SYN/ACK carries no MP_CAPABLE. §3.1 requires this TCP fallback when no other verifiable key is available.
    • The third ACK carries both keys. B must equal the regenerated key_B, otherwise the segment is not a valid cookie. A is taken from the ACK, the checksum decision is recomputed from our config and the client's A bit, and the token is checked again.
    • If the third ACK is lost, the client's first data segment repeats MP_CAPABLE with both keys and is validated the same way.
    • An ACK without MP_CAPABLE makes a plain TCP connection.

    MP_JOIN (§3.2). Joins stay stateful: §3.2 relies on the 32-bit token, and the third ACK doesn't repeat the nonces. Half-open joins stop taking the listener's max_half_open slots. They count only against their connection's SUBFLOW_CAP (8), which today's "Lack of resources" refusal (RST with MP_TCPRST 0x02) already enforces.

    A flood of guessed tokens then fills at most the free slots of the connections whose tokens it hits, each held up to r2_syn (180 s), instead of starving every new connection on the listener. Two optional refinements:

    • a smaller per-connection cap on half-open joins (e.g. 2), so that a hit connection keeps room for real subflows;
    • a shorter SYN-RECEIVED lifetime for joins, since the initiator retransmits its SYN anyway.

    Tests.

    • Unit: cookie round trip, epoch expiry, forged MAC, wrong peer ISN, MSS/WS table rounding.
    • Handshakes: plain and MPTCP cookie handshakes, a lost third ACK followed by data, a token collision falling back to TCP, a wrong echoed key.
    • Integration: clients beyond the cap, with joins.
    • Differential: with syn_cookies = false, the same packets as today.
    • Interop with Linux clients, with the cap at 1 held by a spoofed SYN.

    Prior work. A Linux-layout prototype passed this kind of interop: a Linux client on base-a, m2-goodput and m2-lossy, and our own client on m1, base-a, m2-goodput and m2-lossy, all through cookies. I'd rework it to this design for a PR after 0.3.0.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions