Skip to content

MANUAL.md

Latest commit

 

History

History
557 lines (436 loc) · 23 KB

MANUAL.md

File metadata and controls

557 lines (436 loc) · 23 KB
Raw

netsim — Full Manual

A from-scratch discrete-event packet network simulator in pure-Python stdlib. This manual documents the engine, every module's public API, how to build your own simulations, and the design of each protocol/algorithm modelled.

Scope note: netsim is a teaching/research tool. It models the behaviour of protocols (sawtooth, fairness, bufferbloat, BBR phases, HoL blocking) so you can see them emerge. It is not byte-accurate and not an RFC implementation. Simplifications are called out explicitly throughout.

Table of contents

  1. Install & run
  2. Core concept: discrete-event simulation
  3. Architecture & data flow
  4. Quick start: your first simulation
  5. API reference
  6. Algorithms in depth
  7. The 16 milestones
  8. Extending netsim
  9. Plots, GIFs, pcap tooling
  10. Limitations & simplifications
  11. Glossary

1. Install & run

No install needed for the core — it is stdlib only (Python 3.8+).

git clone git@github.com:diagonalciso/netsim.git
cd netsim

# run any milestone (set PYTHONPATH so the package imports)
PYTHONPATH=. python3 examples/m3_tcp_sawtooth.py

# run them all
for m in examples/m*.py; do echo "== $m =="; PYTHONPATH=. python3 "$m"; done

Plots and the animated GIF need matplotlib (+ pillow), kept in a venv so the core stays dependency-free:

python3 -m venv .venv && .venv/bin/pip install matplotlib pillow
PYTHONPATH=. .venv/bin/python examples/plot_all.py    # -> plots/*.png
PYTHONPATH=. .venv/bin/python examples/make_gif.py     # -> plots/sawtooth.gif

The pcap export (m16_pcap.py) writes plots/trace.pcap, openable in Wireshark or tshark -r plots/trace.pcap.

2. Core concept: discrete-event simulation

netsim has no real-time loop and no threads. The whole simulator is one clock plus a priority queue (min-heap) of future events keyed by timestamp.

while queue not empty and next_time <= until:
    now, fn = pop earliest event
    fn()                      # the handler may schedule new events

Consequences:

  • Time only advances when an event fires. A 10-hour simulation of an idle link costs nothing; a busy microsecond can cost millions of events.
  • Deterministic given the same RNG seed (set random.seed(...) for reproducible loss). Two protocols can be compared under the identical loss pattern by seeding before each run.
  • Everything — packet transmission, propagation, timers, app sends — is just a function scheduled at a future time.

This is the same model as ns-3 / OMNeT++, just stripped to ~30 lines.

3. Architecture & data flow

 apps (UDPSource / WebClient / TCP senders)
        │  host.send(pkt)
        ▼
 Host ──_egress──► Link ──(serialize: size/bw)──► (propagate: delay) ──► Node.recv
        ▲            │                                                      │
        │            ├─ queue governed by a qdisc (DropTail/RED/CoDel/…)    │
        │            └─ optional loss (iid float or GilbertElliott)         │
        │                                                                   ▼
 Receiver ◄───────────────────── ACKs travel back the same way ◄──────── Router (forwards by table)
  • A Link is one-directional: bandwidth (serialization delay = size/bw, link "busy" one packet at a time) + propagation delay (fixed, parallel) + a queue whose admit/drop policy is a pluggable qdisc.
  • A Node is a Router (forwards by forwarding table, possibly ECMP) or a Host (endpoint that runs apps and receivers).
  • Net (topology helper) builds nodes + duplex links, computes shortest-path (Dijkstra on link delay) forwarding tables, and supports link fail/heal.
  • Senders/receivers implement transport: reliability (Go-Back-N or SACK), congestion control (pluggable cc), pacing, multipath (MPTCP), streams (QUIC).

Key invariant: routing is by destination host name. node.table[dstname] is a Link (or, with ECMP, a list of links chosen per-flow by hash).

4. Quick start: your first simulation

A two-host ping measuring RTT (this is examples/m1_ping.py distilled):

from netsim import Sim, Link, Host, Packet

sim = Sim()
a, b = Host(sim, "A"), Host(sim, "B")
BW, DELAY = 1_000_000, 0.010                       # 1 MB/s, 10 ms each way

a.link_to(Link(sim, b, BW, DELAY), for_dst="B")    # A -> B
b.link_to(Link(sim, a, BW, DELAY), for_dst="A")    # B -> A

b.on_recv(lambda p: b.send(Packet("B", "A", p.size, p.seq, "ack")))  # echo
a.on_recv(lambda p: print(f"RTT {(sim.now - p.sent_at)*1000:.1f} ms"))

a.send(Packet("A", "B", size=100))
sim.run()

A bulk TCP flow over a bottleneck (the everyday pattern):

from netsim import Sim, Net, SackSender, SackReceiver, Cubic

sim = Sim(); net = Net(sim)
net.host("SRC"); net.host("DST"); net.router("R1"); net.router("R2")
net.duplex("SRC", "R1", 10_000_000, 0.010)
net.duplex("R1", "R2", 1_000_000, 0.010, qmax=50)   # the bottleneck
net.duplex("R2", "DST", 10_000_000, 0.010)
net.build_routes()

rx = SackReceiver(sim, net.nodes["DST"], src="SRC")
tx = SackSender(sim, net.nodes["SRC"], dst="DST", cc=Cubic())
tx.start(0.0)
sim.run(until=10.0)
print("MB/s:", rx.delivered * 1000 / 10.0 / 1e6)
print("cwnd trace points:", len(tx.log))

5. API reference

All public classes are importable from the top-level package: from netsim import …. Constants: MSS = 1000 bytes/segment, INIT_SSTHRESH = 64, MIN_RTO = 0.20 s.

Sim

Sim()
  .now                       # current simulation time (seconds, float)
  .at(t, fn)                 # schedule fn() at absolute time t
  .after(dt, fn)             # schedule fn() dt seconds from now
  .run(until=inf)            # process events in time order up to `until`

Packet

A dataclass carrying everything any layer needs (fields are reused across protocols rather than nesting headers):

field meaning
src, dst host names (routing keys)
size bytes (default 1000 = MSS); drives serialization time
seq transport sequence (data) or ACK number (ack)
kind "data" or "ack"
sent_at set by sender; used for latency/RTT
pid unique packet id
path list of router names visited (hop trace)
sack SACK blocks ((start,end), …) on ACKs
ce ECN: CE mark on data / ECE echo on ack
flow flow id — lets many connections share hosts/links
dsn MPTCP data sequence number / reused as QUIC stream offset
stream QUIC stream id

Link

Link(sim, dst_node, bw, delay, qmax=64, loss=0.0, name="",
     qdisc=None, loss_model=None)
  .enqueue(pkt) -> bool      # admit (per qdisc) then transmit
  .tap                       # set to callback(now, pkt) for packet capture
  .on_qdepth                 # set to callback(now, depth) for queue sampling
  # stats: .sent .dropped .sojourns(list of per-packet queue delays)
  • bw bytes/sec, delay seconds (propagation). Default qdisc is DropTail(qmax).
  • loss is i.i.d. per-packet drop probability; loss_model (e.g. GilbertElliott) overrides it with a correlated model.
  • One-directional. Use Net.duplex to make a pair, or wire two Links by hand.

Nodes (Node, Router, Host)

Router(sim, name)
Host(sim, name)
  .table                     # dst name -> Link (or list of Links for ECMP)
  .link_to(link, for_dst)    # manual forwarding entry

Host:
  .send(pkt)                 # sets sent_at, routes via table / default link
  .on_recv(fn)               # register a receive handler fn(pkt)
  .rx_log                    # list of (now, pkt)

Routers forward by table[pkt.dst]; with an ECMP list value the link is chosen by hash((pkt.flow, pkt.dst)) so each flow pins to one path.

Apps (UDPSource, Sink, WebClient)

UDPSource(sim, host, dst, rate_pps, size=1000, jitter=False, stop=None, flow_id=0)
  .start(t=0.0)              # CBR if jitter=False, Poisson if True

Sink()
  .attach(host, now_fn)      # records count, bytes, latencies
  .count .bytes .latencies

WebClient(sim, client, server, rate_rps=5.0, alpha=1.3, scale=8,
          cc_factory=None, stop=None)
  .start(t=0.0)              # open-loop Poisson requests, Pareto sizes
  .fcts                      # list of (size_segments, completion_time_s)

WebClient opens a fresh short SACK connection per request (each its own flow_id), models heavy-tailed object sizes (scale * paretovariate(alpha) segments), and records per-object flow-completion time.

TCP senders & receivers

TCPSender(sim, host, dst, cc=None, total=None, flow_id=0, on_done=None)   # Go-Back-N recovery
SackSender(...)            # same signature; SACK (RFC6675-style) recovery
PacedSender(...)           # SACK + rate pacing (needed for BBR)
  .start(t=0.0)
  .cwnd .ssthresh .srtt .rto
  .log                      # list of (time, cwnd, ssthresh, event)

TCPReceiver(sim, host, src, flow_id=0)
SackReceiver(...)          # adds SACK blocks on ACKs
  .delivered                # in-order segments delivered to the app
  .on_deliver               # set to callback(delivered_count, now)
  • cc is a congestion-control strategy (default Reno()).
  • total makes a finite transfer (None = infinite bulk source); on_done(now) fires when the last segment is acked.
  • flow_id lets multiple independent connections coexist on shared hosts/links (packets and ACKs are filtered by flow).
  • All senders use NewReno-style loss recovery (one backoff + one resend per loss episode) layered on either Go-Back-N or SACK retransmission.

Congestion control (cc)

Pluggable strategies. Interface a sender calls:

cc.on_ack(sender, n)       # n = newly-acked segments
cc.on_loss(sender, kind)   # kind in {"fast","timeout"}
cc.on_ecn(sender)          # ECN reaction (if not handled internally)
cc.handles_ecn             # bool; True => sender feeds per-ack marks to on_ack (DCTCP)
class summary
Reno() AIMD: +1/RTT, ×½ on loss. The sawtooth baseline.
Cubic(C=0.4, beta=0.7) cubic window growth since last loss; Linux default.
Bbr(gain=1.0) cwnd-only BBR approximation (no pacing): cwnd ≈ gain·BDP.
BbrV2() full state machine + pacing (use with PacedSender): STARTUP→DRAIN→PROBE_BW→PROBE_RTT.
DCTCP(g=1/16) proportional ECN reaction: cwnd *= 1 - alpha/2, alpha = EWMA of marked fraction. handles_ecn=True.

Queue disciplines (qdisc)

Plug into a Link via link.qdisc = … or Net.duplex(..., qdisc=…). Interface:

qdisc.admit(link, pkt) -> bool                 # at enqueue; False = drop
qdisc.drop_on_dequeue(link, pkt, enq_t) -> bool # CoDel-style drop at dequeue
class summary
DropTail(qmax=64) plain FIFO, drop when full. Big buffer ⇒ bufferbloat.
RED(minth=5, maxth=20, maxp=0.1, w=0.002, qcap=200, ecn=False) random early detect; ecn=True marks instead of dropping.
CoDel(target=0.005, interval=0.100, qcap=1000, ecn=False) controlled delay; drops by packet sojourn time.
ECNThreshold(k=20, qcap=1000) DCTCP switch marker: mark CE when instantaneous queue ≥ K.

Loss models

GilbertElliott(p=0.02, r=0.40, loss_good=0.0, loss_bad=0.5)
  .lost() -> bool            # advance Markov state, decide loss
  .steady_loss()             # long-run average loss rate

2-state burst model (GOOD/BAD). p = P(GOOD→BAD), r = P(BAD→GOOD). Pass as Link(..., loss_model=…) or Net.duplex(..., loss_model=…) to model wifi/cellular bursts (vs the i.i.d. loss= float).

FairLink

FairLink(sim, dst_node, bw, delay, flow_qcap=100, loss=0.0, name="",
         loss_model=None, target=0.005, interval=0.100)

Drop-in Link replacement implementing FQ-CoDel: one sub-queue per flow, serviced round-robin, each with its own CoDel. Isolates flows — an unresponsive hog fills only its own queue. Install by replacing the forwarding entry, e.g. net.nodes["R1"].table["DST"] = FairLink(sim, net.nodes["R2"], bw, delay).

Topology & routing (Net)

Net(sim)
  .host(name) / .router(name)            # create + return a node
  .duplex(a, b, bw, delay, qmax=64, loss=0.0, qdisc=None, loss_model=None)
       -> (link_a_to_b, link_b_to_a)     # qdisc/loss_model apply to a->b only
  .build_routes(ecmp=False)              # Dijkstra (weight = delay) forwarding tables
  .fail(a, b) / .heal(a, b)              # disable/enable an edge, then reroute
  .nodes                                 # name -> node dict

With ecmp=True, all equal-cost first hops are installed as a group and chosen per-flow by hash (see Nodes).

MPTCP

MPTCPConnection(total=None)
  .count                                 # unique connection segments delivered
MPTCPSubflow(sim, host, dst, conn, egress, cc=None, flow_id=0)  # one per path; egress = pinned link
MPTCPReceiver(sim, host, src, conn, flow_id=0)                  # one per subflow

One logical connection striped over subflows. Two sequence spaces: subflow seq (per-path SACK reliability) and DSN (connection reassembly + dedup). A subflow pulls the next unassigned DSN when its window has room, so faster paths carry more. Congestion control is uncoupled (Reno per subflow) — real MPTCP couples it (LIA); noted, not implemented.

QUIC

QUICSender(sim, host, dst, stream_sizes, cc=None, flow_id=0)
QUICReceiver(sim, host, src, stream_sizes, flow_id=0,
             on_stream_done=None, on_app=None)
  .done                                  # per-stream completion times
  .app_delivered                         # segments handed to the app

Many independent streams multiplexed over one SACK flow. Reliability is at the transport (SACK) level; delivery is per-stream, so a loss in one stream never blocks another (no head-of-line blocking). on_app(now) fires per segment delivered to the application.

Pcap export

PcapWriter(path, snaplen=128)
  .write(now, pkt)                       # attach as link.tap = pc.write
  .close()

Synthesizes Ethernet/IPv4/TCP headers (host→10.0.0.x, flow→port, transport seq→TCP seq/ack, ECN CE→IP ECN bits, valid IP checksum) and writes a libpcap file. Tap a link with link.tap = pc.write; open the result in Wireshark or tshark -r file.pcap.

6. Algorithms in depth

Reliability: Go-Back-N vs SACK

  • Go-Back-N (TCPSender): on loss, retransmit the whole window from send_base. Simple but wastes capacity re-sending already-received segments.
  • SACK (SackSender): the receiver reports exactly which segments arrived (pkt.sack); the sender uses an RFC6675-style pipe estimate — a hole with SACKed data above it is inferred lost and excluded from in-flight, so only the holes are retransmitted, and new data keeps flowing during recovery.
  • NewReno recovery (both): one congestion backoff + one resend per loss episode; further duplicate ACKs in the same episode are suppressed until send_base passes the recover mark. This prevents retransmit storms (crucial for loss-agnostic BBR on top of Go-Back-N).
  • RTO: Jacobson/Karels srtt/rttvar estimator; Karn's algorithm (no RTT sample from retransmitted segments); exponential backoff on timeout.

Congestion control

  • Reno — additive increase (+1 segment/RTT) in congestion avoidance, multiplicative decrease (×½) on loss. Produces the canonical sawtooth.
  • Cubic — window is a cubic function of time since the last loss: grows fast when far below the prior maximum, cautiously near it. Higher throughput than Reno on high-BDP links; fills buffers more.
  • Bbr (cwnd-only) — estimates bottleneck bandwidth (windowed max of delivery rate) and min RTT; targets cwnd ≈ gain·BDP, ignores loss. Without pacing, gain≈1 approximates the steady-state in-flight cap.
  • BbrV2 (paced) — the real shape: STARTUP ramps exponentially until bandwidth plateaus; DRAIN empties the startup queue; PROBE_BW cruises and cycles the pacing gain [1.25, 0.75, 1×6] to probe; PROBE_RTT periodically drops cwnd to 4 to re-measure min RTT. Pacing (via PacedSender) keeps the queue near-empty, giving high throughput and low latency.
  • DCTCP — for ECN-marking switches: tracks alpha, an EWMA of the fraction of marked packets per window, and reduces cwnd *= 1 - alpha/2. Combined with a threshold marker it parks the queue near K with tiny variance.

Queue management & bufferbloat

A big DropTail buffer kept full by greedy TCP adds huge standing latency (bufferbloat). AQM fixes it: RED drops/marks probabilistically as the average queue grows; CoDel drops by packet sojourn time (self-tuning, target 5 ms). ECN lets the queue signal congestion by marking instead of dropping (no retransmits). FQ-CoDel adds per-flow fair queueing so one flow can't hurt another's latency — the only thing that tames an unresponsive hog.

7. The 16 milestones

Each examples/mN_*.py is self-contained and prints its result.

# file demonstrates headline result
1 m1_ping clock + link delays RTT = 2·(serialize+prop), exact
2 m2_bottleneck queueing + tail drop throughput capped at bottleneck, queue full
3 m3_tcp_sawtooth Reno AIMD slow-start spike → linear ramps (sawtooth)
4 m4_fairness 2 flows share link Jain ≈ 0.98 (AIMD convergence)
5 m5_routing Dijkstra + failover reroute on link fail, restore on heal
6 m6_bufferbloat DropTail/RED/CoDel queue delay 52 → 13 → 4 ms
7 m7_cc_bakeoff Reno/CUBIC/BBR same throughput, BBR ~3 ms vs Reno ~48 ms
8 m8_sack SACK vs Go-Back-N SACK ~98% efficient under loss vs 80%
9 m9_bbr_pacing paced BBRv2 phases 0.97 MB/s, 0 drops, ~4 ms; PROBE_RTT dips
10 m10_ecn / m10_coexist ECN; multi-flow ECN: 0 drops; Reno-vs-BBR 25/75, buffer-dependent
11 m11_web / m11_wifi / m11_viz FCT; bursty loss; live viz CoDel cuts short-FCT 3×; loss episodes matter; ASCII anim
12 m12_dctcp / m12_fqcodel DCTCP; FQ-CoDel DCTCP 7 ms full-throughput; FQ 842→32 ms vs flood
13 m13_mptcp MPTCP 0.99 → 1.98 MB/s; graceful on a lossy path
14 m14_quic QUIC vs TCP HoL worst app stall TCP 601 ms vs QUIC 300 ms
15 m15_ecmp leaf-spine ECMP 9.4 → 26.6 MB/s across 3 balanced spines
16 m16_pcap pcap export 300-frame Wireshark/tshark-readable trace

Non-milestone helpers: plot_all.py (PNG figures), make_gif.py (animated sawtooth GIF).

8. Extending netsim

Add a congestion control: implement on_ack(s, n), on_loss(s, kind), on_ecn(s); mutate s.cwnd / s.ssthresh and call s._record(label) so it shows in tx.log. Pass an instance as cc= to any sender.

class Tahoe:
    name = "tahoe"
    def on_ack(self, s, n):
        s.cwnd += 1 if s.cwnd < s.ssthresh else 1.0/s.cwnd
        s._record("tahoe")
    def on_loss(self, s, kind):
        s.ssthresh = max(s.cwnd/2, 2); s.cwnd = 1.0; s._record(kind)  # always to 1
    def on_ecn(self, s):
        self.on_loss(s, "fast")

Add a queue discipline: implement admit(link, pkt) -> bool and drop_on_dequeue(link, pkt, enq_t) -> bool; set link.qdisc = YourQdisc(...). len(link.q) is the current backlog; link.sim.now the time.

Add a topology: use Net — host/router/duplex/build_routes. For custom routing, set node.table[dstname] to a Link (or list for ECMP) yourself after build_routes().

Tap traffic: set link.tap = fn (called fn(now, pkt) at transmit) or link.on_qdepth = fn to sample queue depth for plots.

9. Plots, GIFs, pcap tooling

  • examples/plot_all.py → plots/*.png: sawtooth, fairness, bufferbloat bars, cc cwnd traces, cc throughput-vs-latency tradeoff, SACK efficiency, BBRv2 phases, multi-flow coexistence.
  • examples/make_gif.py → plots/sawtooth.gif: animated cwnd + bottleneck queue.
  • examples/m16_pcap.py → plots/trace.pcap: open in Wireshark or tshark -r plots/trace.pcap. Data segments appear as 10.0.0.x:PORT → 10.0.0.y:80 [PSH,ACK]; ECN-marked packets carry the IP ECN/CE bits.

All three require the venv (matplotlib/pillow); the pcap writer itself is stdlib, only inspection needs Wireshark/tshark.

10. Limitations & simplifications

Honest list — none of these are bugs, they are deliberate scope cuts:

  • Bytes ≈ segments. Everything is in MSS-sized packets; no partial segments, no Nagle, no delayed ACKs.
  • No real headers on the wire (except synthesized in the pcap exporter).
  • Cubic / BBR are teaching approximations, not the Linux implementations. BBR pacing is modelled in BbrV2 but ProbeRTT/Drain are simplified.
  • MPTCP congestion control is uncoupled (real MPTCP couples it for fairness).
  • QUIC models stream multiplexing + per-stream delivery, not the crypto, connection IDs, or 0-RTT.
  • Routing is static shortest-path (Dijkstra on delay) + ECMP; no BGP/OSPF dynamics beyond fail/heal reroute.
  • ACKs are per-segment (no ACK thinning); reverse-path congestion is usually avoided by giving ACK paths ample bandwidth.
  • Single RNG stream — seed it for reproducibility and fair A/B comparisons.

11. Glossary

  • BDP — bandwidth-delay product = bw × RTT; the amount of data "in flight" to keep a path full.
  • cwnd / ssthresh — congestion window / slow-start threshold (in segments).
  • AIMD — additive-increase/multiplicative-decrease (Reno's law).
  • AQM — active queue management (RED, CoDel) — manage the queue before it overflows.
  • bufferbloat — excess latency from a large buffer kept persistently full.
  • ECN / CE / ECE — explicit congestion notification; CE = "congestion experienced" mark on data; ECE = echo back on the ACK.
  • SACK — selective acknowledgement; tells the sender exactly which segments arrived so it retransmits only the holes.
  • HoL blocking — head-of-line blocking; in-order delivery stalls everything behind one missing segment.
  • ECMP — equal-cost multipath; spread flows across equal-length paths.
  • DSN — data sequence number (MPTCP connection-level ordering).
  • FCT — flow completion time; how long an object/transfer takes end to end.
  • sojourn — time a packet spends sitting in a queue.

netsim — built milestone by milestone. See README.md for the quick tour and the milestone checklist.