CS 4251/6250 — Quiz 2 study notes

0 · Exam intel (from the transcripts)

I read every transcript for hints. These are the ones that change how you should study:

0.1 · The 3-day plan

Method: research on learning techniques (Dunlosky et al., 2013) rates practice testing and spacing as the two most effective study methods. Interleaving (mixing problem types) is also supported. Re-reading and highlighting score low. So the plan is: read the theory once → solve problems from memory → check → come back to the hard ones on a later day → finish with a timed, mixed mock quiz. Keep an error log: one line per miss, noting whether it was a concept gap or a careless slip.

1 · Congestion control, part 3: model-based vs performance-oriented (PCC)

Lecture 9 · HW2 Q1 · the only congestion-control content after Quiz 1, so expect one question here.

1.1 The same loss event can mean four different things

Every algorithm from Quiz 1 is an event → action table: “when X happens, do Y”. Each rule quietly bakes in an interpretation of what the event means. The designer decided in advance what a loss or an RTT change “usually” means and hard-coded the right reaction for that case.

The problem: you see “100 Mb/s, 1% loss”, but the hidden cause decides what the useful response is:

1.2 Two philosophies

BBR's evolution as a case study (the slide's example of how model-based designs grow):

• BBRv1 models the path as a pipe with two numbers: the bottleneck bandwidth (estimated as the largest delivery rate seen over the last ~10 round trips, a “windowed max”) and the propagation RTT (the smallest RTT seen over the last ~10 s, a “windowed min”). It sends at that bandwidth and periodically probes 25% higher to check whether more bandwidth appeared. It ignores loss completely. Inside Google's own network that worked, but on the Internet it was unfair to loss-based flows: CUBIC backs off on loss while BBRv1 keeps going, and in shallow buffers BBRv1 caused heavy loss.
• BBRv2 adds congestion-informed limits: loss and ECN marks now cap how much it keeps in flight. Its probing cycle got named phases: CRUISE (hold steady), REFILL (refill the pipe before a probe), UP (probe for more bandwidth), DOWN (drain the queue the probe created).
• BBRv3 refines when to stop probing, and how to tell a real bandwidth plateau (the path is full) from self-limitation (the application simply isn't giving it more data, so the delivery rate looks flat for a reason unrelated to the network).

Each fix added rules for more corner cases, and the original elegant model became less elegant. That is the critique PCC starts from: instead of an ever-growing model of the path, just measure which rate works better.

1.3 PCC Allegro (2015): randomized controlled trials on the rate

Step 1 — how a trial is scored: Allegro's utility

u(x) = T · S(L)  −  x · L          T = x(1 − L)          S(L) = 1 / (1 + e^(α(L − 0.05))),  α = 100

Worked example (x = 100 Mb/s, the same numbers as problem 1.3): L = 1% → S = 0.98, u = 99·0.98 − 1 = 96.2 · L = 4% → S = 0.73, u = 96·0.73 − 4 = 66.2 · L = 6% → S = 0.27, u = 94·0.27 − 6 = 19.3.

Why the sigmoid at all? With the plain score x(1−L), a sender that sends a bit more almost always delivers a bit more, even while everyone's loss climbs. Selfish senders all keep pushing until loss is very high (a bad Nash equilibrium: nobody gains by backing off alone). The sigmoid makes high loss wreck your own score, so everyone stops near 5%.

Step 2 — which direction to move: the trials

• Decision rule: if both pairs agree (“the lower rate scored higher” twice), move that way. If they disagree, the result is inconclusive: stay at r, repeat, and increase ε to compare rates farther apart, where a real difference is easier to see through noise.
• Slide example (r = 100, ε = 2%): pair 1 sends 98 then 102 and scores 94, 90 → lower wins. Pair 2 sends 102 then 98 and scores 96, 93 → higher wins. They disagree → stay at 100, widen ε.
• Why random order and two pairs? The network changes during the test (a queue may be building). With a fixed order, the second trial would always be measured in worse conditions and always lose. Random order turns that drift into a disagreement between pairs (detected) instead of a consistent wrong answer.

Step 3 — why comparing two nearby rates finds the best rate

Step 4 — the control loop

• States: STARTING (double the rate while utility keeps rising, like slow start) → DECISION (run the trial pairs) → ADJUSTING (keep moving in the winning direction). If utility falls while adjusting, step back once and return to DECISION.
• Step size: Allegro's trials give only a direction. How far it moves follows a preset schedule; it ignores how much better the winning rate scored. This is the weakness Vivace fixes.
• Fairness among PCC flows (Q&A): for some utility functions (not all), the paper proves via game theory that competing PCC senders converge to the fair allocation. The proof assumes everyone sees comparable signals (similar loss). Real networks are messier, so convergence isn't guaranteed. Against CUBIC, PCC is unfair: it tolerates ~5% loss and grabs the bandwidth.
• Oscillation (Q&A): PCC keeps probing a bit above and below the optimum, so its rate oscillates around the peak. Only if all senders ran their trials in lockstep would the trials come out inconclusive exactly at the peak. PCC has no tendency to synchronize, unlike Reno, whose sawtooths synchronize over time.

1.4 PCC Vivace (2018): a better utility and gradient-based steps

Vivace keeps Allegro's loop (monitor intervals, trial rates, compare scores) and changes two things, which map onto Allegro's two problems:

Change 1 — the score now includes delay: what dRTT/dt means

RTT = propagation delay (fixed for a given path) + queueing delay (waiting in the bottleneck buffer). On a fixed path, when RTT goes up the queue is growing, and when it goes down the queue is draining.

dRTT/dt (the “RTT gradient”) is how fast the RTT is changing during the MI: the slope of a line through the RTT samples, roughly (RTT at the end − RTT at the start) / MI length. Both are in ms, so it has no unit. Example: RTT goes 40 → 60 ms during a 100 ms MI → dRTT/dt = 20/100 = 0.20.

Where (x − C)/C comes from: if you send at x into a bottleneck that drains at C, the queue grows by (x − C) bits every second. Queueing delay = queued bits / C, so the delay grows by (x − C)/C seconds every second. At x = 120 Mb/s and C = 100 Mb/s: (120 − 100)/100 = 0.2, the same 0.20 slope as above. So the slope measures how far above capacity you are right now.

u(x) = x^t  −  b · x · (dRTT/dt)  −  c · x · L          0 < t < 1 ;  b, c > 0 are tuning weights
whiteboard writes the same thing as  U(x) = x^α₁ − α₂·x·dRTT/dt − α₃·x·L

Worked example (problem 1.4, simplified u = x − 2·x·dRTT/dt, no loss, C = 100): x = 120 → slope 0.2 → u = 120 − 2·120·0.2 = 72 · x = 110 → slope 0.1 → u = 110 − 22 = 88 · x = 90 → slope −0.1 → u = 90 + 18 = 108. Sending closer to capacity, or a bit under it while a queue drains, scores better.

Change 2 — how far to move: the gradient

What is the gradient for? Deciding how big a step to take. After a pair of trials Vivace has two points on the score-vs-rate curve: (r₋, U₋) and (r₊, U₊). The slope between them,

g ≈ (U₊ − U₋) / (r₊ − r₋)          "how much score do I gain per extra Mb/s, around my current rate"

• The sign of g gives the direction: g > 0 means the higher rate scored better, so go up.
• The size of g says how far you are from the best rate: near the peak the curve is flat (g ≈ 0); far away it is steep (|g| large).

Δr = θ · g          new rate = r + Δr

• θ turns “score per Mb/s” into “Mb/s to move” (like a learning rate). It is a confidence amplifier: when several steps in a row go the same way, θ grows (bolder steps); when the direction flips, it resets (careful again).
• Bound: |Δr| is capped at a fraction of r, because measurements are noisy and one bad g could otherwise cause a huge jump.

Worked example (problem 1.5): at r = 80, trials at 76 and 84 score U₋ = 61.0 and U₊ = 58.6. g = (58.6 − 61.0)/(84 − 76) = −2.4/8 = −0.3 (the higher rate scored worse, so go down). With θ = 10: Δr = 10 · (−0.3) = −3 → new rate 77 Mb/s.

PCC vs the Quiz 1 algorithms (the one Part 1 link on the quiz)

Lecture 19: the PCC question includes a part “connecting it to the general congestion control material”, and that is the only Part 1 content on the quiz.

• Link to NUM (Part 1): every congestion controller implicitly maximizes some utility (Reno ≈ −1/(RTT²x), i.e. α = 2 fairness). Copa writes its utility down and turns it into a fixed target-rate rule. PCC writes its utility down and searches for the best rate online by experiment. Concave utilities (log, x^t with t < 1) are what make competing senders converge to a fair split, in NUM and in PCC alike.
• Link to the model-based critique: Reno, CUBIC, Vegas, Copa, BBR each assume what a signal means (loss = overflow, delay = my queue). When the assumption is wrong (random loss, another flow's queue, shallow buffers) the hard-wired response is wrong. PCC avoids naming the cause, at the price of designing the utility, the trial length and the exploration.
• Link to bufferbloat: loss-based schemes and Allegro both fill buffers; delay-aware ones (Vegas, Copa, BBR, Vivace) keep the queue short.

1.5 Learning a rate vs learning a policy; where AI fits

• A policy is a function from what the sender has observed (recent RTTs, loss, rates) to an action (new rate or cwnd). Reno is a hand-written policy.
• Allegro / Vivace don't learn a policy: they learn the rate itself, live, by running experiments on the real network.
• Remy (MIT, 2013): a computer search, run offline in simulation, produces a table of rules (“if the observed conditions look like this, change the window like that”). Deployed, the table is fixed.
• Aurora: a neural network trained offline with reinforcement learning (trial and error in simulation, rewarded by a utility). Deployed, its weights θ are fixed.

A fixed learned policy still produces a changing sending rate, because its inputs (the observations) keep changing. Systems point: TCP lives inside the operating-system kernel, and kernel code generally avoids floating-point math. Neural models need floats, so they run as an ordinary program in user space. The transport reports RTT/loss/throughput through an API and the model answers with a rate or cwnd. The cost is the round trip between kernel and program: the model can't react to every ACK, only every RTT or every few RTTs.

1.6 HW2 Q1 patterns: BBR after a route change, PCC β, exploration

BBRv1 on a longer-RTT route: the min-RTT filter (10 s window) keeps the old, small RTT, so BBR underestimates the BDP and sets cwnd ≈ 2·BW·RTT_old, which is too small. The sender becomes cwnd-limited, so delivery-rate samples drop. When the high samples expire from the 10-round max-BW filter, the BW estimate drops too, which shrinks cwnd further. This feedback spiral lasts until the min-RTT entry expires (≈10 s / ProbeRTT). Fix (HW answer): when several RTT samples are consistently above the stored min, temporarily drain inflight. If the RTT stays high at low load, it is a longer propagation delay: reset the min-RTT filter, recompute BDP/cwnd, and re-probe bandwidth. If the RTT falls back, it was queueing, so keep the old min. This is imperfect, because a persistent queue from other traffic also keeps the baseline high.

PCC with delay preference U = g − β·q (g = goodput in Mb/s, q = average queueing delay in ms). β is the exchange rate: how many Mb/s of goodput you are willing to give up to save 1 ms of queueing delay. Bigger β = more delay-sensitive.

Exploration vs exploitation: a trial must span at least one RTT (often several) to see its own effect. Shorter trials cause misattribution. Longer trials average out noise but cost throughput or queueing, and if conditions change during the trial the result mixes regimes or is stale. Trials should be long enough to be reliable and short enough to stay relevant.

2 · QUIC

Lecture 10 · HW2 Q2. Organizing question: besides “how fast?”, what must transport do for an app like a phone video page?

2.1 Handshake: how many RTTs before the response?

• TLS = the protocol that authenticates the server and agrees on encryption keys. In TCP it runs on top of the finished TCP connection (layered, so the RTTs add up). In QUIC it is built into the transport handshake.
• Why 0-RTT is restricted: an attacker can capture and replay the first flight. Early data therefore only carries requests that are safe to repeat (e.g., a GET, not “transfer $100”), and the server must agree to accept it.

2.2 Why not just modify TCP? Ossification

A TCP change has to reach three places: the endpoint stacks (OS kernels, APIs), the peer (negotiation), and the path. The path is the real problem. Middleboxes are devices in the middle of the path that look inside packets: firewalls, NATs (which rewrite addresses and ports), load balancers, even home Wi-Fi routers. Many were built to expect TCP exactly as it looked years ago, so when they see something unfamiliar they “normalize” it (rewrite it to a standard form), strip it, or drop the packet as suspicious. Example: both endpoints support a new TCP option, but a firewall deletes it from the SYN, so the endpoints never learn the other side supports it and silently fall back to old behaviour (the slide's “the middlebox removes its signal”). The cycle: devices see a narrow set of behaviors → implementations depend on them → new values fail → fallback preserves the old assumptions. A brand-new transport protocol number would be dropped even more often.

Side effect: many implementations (Google, Cloudflare, Akamai, Meta…). Even with RFC 9000–9002, each makes its own assumptions, so interop problems appear (“Google server needs Google client” early on). IETF interop matrices helped.

2.3 Head-of-line blocking and streams

Head-of-line (HOL) blocking = data that already arrived can't be used because something in front of it in the delivery order is missing. Like a supermarket queue where everyone waits behind one person whose card was declined. TCP delivers one ordered byte stream, so if bytes 1000–1999 are lost, bytes 2000+ sit in the receiver's buffer, unusable, until the retransmission arrives, even when they belong to a completely different object.

• HTTP/1.1: a separate TCP connection per object avoids cross-object HOL blocking, but costs handshakes, state, and CPU/threads.
• HTTP/2: many HTTP streams multiplexed over one TCP byte order. One lost TCP segment blocks all objects (TCP-level HOL).
• QUIC: congestion control, flow control, and encryption are per connection. Delivery order and reliability are per stream.

2.4 Reliability: packet numbers vs stream offsets

Why two numbering systems? They answer two different questions. Stream ID + offset answers “which bytes are these and where do they go?”, so the receiver can put data in place no matter which packet carried it. The packet number answers “which transmission is this?” and is never reused. In TCP, a retransmitted segment has the same sequence number as the original, so when an ACK comes back the sender can't tell whether it acknowledges the original or the copy. Its RTT sample is ambiguous. In QUIC every ACK names exactly one transmission, so RTT samples and loss detection are clean.

Example from the slides: packet 100 (A: offset 0, len 1000) is lost and its bytes are resent in packet 110 with the same A offset 0, len 1000. Then stream A can deliver bytes 0–1999 in order. An ACK reports packets received (“ACK 101–103”), not the next deliverable stream offset, so packet 100's fate is uncertain (delayed or lost).

• Packet threshold: a packet is declared lost when a sufficiently higher packet number is acknowledged (RFC 9002 default: 3 higher).
• Time threshold: an older unacked packet passes an RTT-based deadline (RFC: 9/8 × RTT).
• Probe timeout (PTO): when ACK progress stalls (e.g., the last packets of a short flow, or lost ACKs), send a probe to elicit ACKs. It is a shorter timer than TCP's RTO. PTO expiry alone does not declare loss.
• Cost: ACK frames list ranges of packet numbers (like SACK), plus per-stream metadata. That means more header bytes and slightly lower goodput (useful application bits per second, i.e. throughput minus headers and retransmissions) than TCP's compact cumulative ACK.

2.5 Connection migration

TCP's connection is its 4-tuple (src IP, dst IP, src port, dst port); a new IP kills it (timeout → app exception → new handshake → recover app state). QUIC uses connection IDs to locate state; packet protection authenticates the traffic. The client switches to a different issued CID (so the paths aren't trivially linkable), validates the new path, and re-learns what the new path supports (Wi-Fi 20 ms/100 Mb/s vs cellular 80 ms/10 Mb/s): “a surviving connection does not imply a surviving path model.”

• Connection ID (CID): an identifier in every QUIC packet header that the server uses to look up the connection's state. TCP looks up state by the 4-tuple, so a new IP address means “unknown connection”.
• Why switch to a different CID? Privacy: if the same ID appeared on Wi-Fi and cellular, an observer could link the two paths to one user.
• Path validation: the server sends a PATH_CHALLENGE with 8 random bytes to the new address; only the real client there can echo them in a PATH_RESPONSE. This proves the new address is reachable and really belongs to the peer, so an attacker can't redirect traffic by spoofing addresses.
• Re-learn the path: cwnd and RTT estimates from Wi-Fi (20 ms, 100 Mb/s) are wrong for cellular (80 ms, 10 Mb/s), so congestion control starts over for the new path while the streams continue.

2.6 HW2 Q2 pattern: scheduling buffered streams

Flow control vs congestion control: flow control protects the receiver (it advertises how many more bytes it can buffer: a credit per stream and one for the whole connection); congestion control protects the network (cwnd). The sender may send only what both allow.

All data is already at the sender, but the congestion window limits what is in flight, and the scheduler decides which stream gets those slots. Prioritizing B helps B even with everything buffered. The cost is that lower-priority streams wait, and they can starve if high-priority data keeps arriving. Method: build a table time | ACKs received | cwnd | packets sent, then add one-way delay to get arrival and display times.

3 · Traffic engineering (TE) foundations

Lecture 11 · HW2 Q3. Unit 2 zooms into one operator's private WAN. Its inputs are aggregates (a traffic matrix), not individual flows.

The picture from the whiteboard: a content provider (Meta, Google, Microsoft) owns a private WAN that connects its data centers to each other and to PoPs, where it hands traffic to several ISPs and on to users. Because one operator owns the whole network (and often the sending hosts), it can decide where traffic goes and how much each service may send, which the public Internet cannot.

3.1 Slow down, or move the traffic?

• ECMP (equal-cost multi-path) is what routers do by default when several shortest paths exist. For each packet it computes a hash (a scrambled number) of header fields (src/dst IP, ports, QoS) and uses it to pick a path. Every packet of the same flow has the same fields, so it always takes the same path, which keeps packets in order. Consequences: it splits flows, not bytes, and splits them equally, ignoring that the paths have different capacities. Equal flow counts ≠ equal load: 100 tiny flows on one path and one 100 Gb/s flow on the other is not balance.
• Min-MLU on parallel disjoint paths ⇒ equalize utilizations ⇒ split proportional to capacity; MLU* = D / Σc.
• TE vs congestion control: CC changes demand (rates). TE redistributes traffic. TE fixes an inefficient mapping but not insufficient resources (demand above the cut). Beyond the cut, CC or admission control must cut demand.

3.2 From NUM to TE, and why minimize peak utilization

They form a feedback loop: TE moves traffic, which changes the RTTs and bottlenecks each flow sees, which changes the rates CC picks, which changes the demand TE measures. The separation of timescales breaks the loop: CC reacts every few milliseconds and handles fast fluctuations, while TE recomputes every few minutes on averages. From TE's view CC is “already settled”; from CC's view the routes are fixed.

Why TE needs its own objective: take the 12 Gb/s example and compare the splits 8/4 and 9/3. Both fit (utilizations 0.8 & 0.8 vs 0.9 & 0.6), so every sender gets its full 12 Gb/s with no loss and no queueing. The senders' utilities are identical either way, so they can't say which split is better. The operator needs a network-level goal, such as the lowest MLU, which prefers 8/4 (busiest link 0.8, not 0.9).

min  ρ
s.t. Σ_p x_kp = d_k                 (carry each demand)
     Σ_{k,p : e∈p} x_kp ≤ ρ·c_e     (every link)
     x_kp ≥ 0                       12-Gb/s example: a/10 = (12−a)/5 → a* = 8, ρ* = 0.8

RFC 9522 definition: TE = performance evaluation and optimization of operational IP networks, using measurement, characterization, modeling, and control of traffic. Objectives come in two classes. Traffic performance: loss, delay, delivered throughput, service commitments. Resource use: avoid persistent hotspots, use alternate capacity, preserve headroom, minimize cost (leased or transit links). A “best” routing is best only for a stated objective. Policy can remove otherwise useful paths.

Control surfaces: traffic management (limit a sending rate / reject requests, i.e. admission), routing (move demand), resource constraints (reserve headroom, exclude paths). Which ones you have depends on the operator's authority.

3.3 The practical TE loop: five problems

3.4 Scale forces trade-offs

4 · Mechanisms that make TE possible: MPLS and SDN

Lecture 12. The professor's warning: MPLS and SDN are not separate worlds. Real networks are hybrids: a centralized controller programs an MPLS data plane.

4.1 MPLS: forward on a label, not on the IP prefix

• LSR (label-switched router) forwards using only the label. Its MPLS table is separate from the IP forwarding table (the FIB, “forwarding information base”), so its MPLS decisions can differ from what IP routing would do.
• Why: ① fixed-length exact-match lookup is faster in hardware than longest-prefix match. IP lookup must find, among many overlapping prefixes (10.0.0.0/8, 10.1.0.0/16, 10.1.2.0/24…), the most specific one that matches; a label is simply an exact key into a table. ② Flexibility: traffic to the same destination can take different paths, chosen by source, ports, QoS class, or ingress port (destination-based IP can't do this). ③ Fast reroute: backup paths are precomputed.
• LSP (label-switched path): ingress classifies and pushes a label → transit LSRs swap labels → egress (or the penultimate hop) pops. Labels are local to each router, so “10” at R3 has nothing to do with “10” at R1. Labels can be stacked (nested virtual networks, source routing).
• Signaling = how routers learn which labels to use. Distributed version: OSPF and IS-IS (link-state routing protocols, which already flood every link's status to every router) are extended (“-TE”) to also flood each link's bandwidth and how much is already reserved. With that map, the ingress computes a path that has room, then sends an RSVP-TE message along it: each router on the way reserves the bandwidth and tells its upstream neighbour which label to use. Today this is usually centralized: a controller, or a PCE (path computation element, a server whose job is computing paths), computes the paths and programs the routers.

Units of traffic: packets/flows → forwarding equivalence class (FEC, forwarded the same way) → traffic trunk (FEC + TE attributes: bandwidth, burst, priority, preemption, resilience, path preference, policing) → LSP over the physical links.

Constraint-based route selection (CSPF): ① trunk request (e.g., A→F, 6 Gb/s, exclude RED) → ② prune links with insufficient allocatable bandwidth or excluded colors → ③ run shortest path on what remains and instantiate the LSP. Trunks placed one at a time are order-dependent: e.g. two 6 Gb/s trunks and two 10 Gb/s paths, where trunk X can use either path but trunk Y can only use path 1. Place X first on its shortest path, path 1, and Y no longer fits; place Y first and both fit. So several trunks may need joint optimization. Resilience: a 100 Gb/s trunk over three 400 Gb/s links that must survive one link failure → reserve 50 on each (any two survivors carry 100). General rule: with k equal links and up to f failures, the worst case leaves k − f links, so each must hold D/(k − f); here 100/(3 − 1) = 50, i.e. 150 reserved in total for a 100 Gb/s trunk. That is wasteful, so operators oversubscribe (committed sum > capacity, e.g., 450 on 400) because a worst case on every trunk at once is unlikely. Another way to avoid waste (Q&A): program the backups into the TE solution as an ordered preference, e.g., “S→D traffic uses link 1 first; above 50 Gb/s spill to link 2; beyond that to link 3”, so the last link is rarely used. If backups aren't part of the TE solution, a failure has to wait for the next TE computation. TE is a feedback process: observe → decide → act → check. Reroute only when the expected benefit justifies the path change.

4.2 SDN refresher (the parts the case studies build on)

Traditional per-router control plane: every router runs OSPF/IS-IS/BGP and computes its own FIB. For TE that leaves only link weights as a knob: you can't steer u→z onto a non-shortest path without changing weights (which moves everyone else's traffic too), you can't split one destination's traffic across two paths, and you can't route two classes to the same destination differently.

• Controller components (3 layers): ① interface to apps: abstractions such as the network graph, a RESTful API, and an intent API (northbound) · ② network-wide state management (link, host, switch info, statistics, flow tables) as a distributed, robust database · ③ communication with devices (OpenFlow, SNMP: southbound).
• Flow table (generalized forwarding): match on L2/L3/L4 header fields (wildcards) → actions: forward, drop, modify (e.g., push or pop a label), send to the controller · priority disambiguates overlapping matches · counters (bytes, packets) feed TE measurement.
• Link-failure walk-through: ① switch sends an OpenFlow port-status message → ② the controller updates link state → ③ the routing app (registered callback) is invoked → ④ it recomputes routes from the graph → ⑤ flow tables are computed → ⑥ new tables are installed via OpenFlow. That takes hundreds of ms to seconds, slower than local distributed repair, which is why every case study uses hybrid control (local fast reaction + central global optimization).
• Why SDN: easier management, fewer misconfigurations, programmable table-based forwarding, centralized computation, open interfaces → faster innovation (the mainframe-to-PC analogy: vertically integrated and closed vs horizontal and open).
• SDN + MPLS TE architecture: service demand + TE policy → controller / PCE (TE database + constraint-based path computation) ← topology, capacity, telemetry; it programs the LSPs via RSVP-TE or per-hop programming; packets follow the installed LSP.

5 · Meta's Express Backbone (EBB)

Lectures 12–14 · HW2 Q5. The professor's framing: Meta = the nitty-gritty details of a hybrid design (Google = nuanced allocation/fairness, Microsoft = failure handling).

5.1 Two networks, four planes

Separating them keeps large internal bursts from hurting user traffic and allows different routing and ops choices. (Google: B2/B4. Microsoft: CORE/SWAN.) All three started with cheap, less reliable internal networks that became critical, then reliable, and are now being merged. Meta was IPv6-native from day one (Google's later v4→v6 migration was a multi-year effort).

5.2 Architecture: who does what

• Estimating demand: the best short-term predictor of demand is current demand. Hosts could report per-TCP-flow counters (Google's approach), but switches keep no per-flow state at Tb/s line rate. sFlow: the router's forwarding chip (ASIC) copies the header of 1 of every N packets (e.g. 1 in 10 000) plus interface byte counters, the switch CPU agent sends sample records to a collector, and the collector estimates bytes per (DC pair, class). Sampling also lets the router run a simple counter instead of per-packet work, and report a tiny fraction of the traffic (a router carrying 1 Tb/s doesn't send 1 Tb/s to the collector). How to pick N (Q&A): methodically, from the traffic distribution and the confidence interval you want; in practice standards often settle on a conventional “magic number”. Sampling loses little because traffic is heavy-tailed (Pareto): a few heavy hitters carry most of the bytes, and those are what TE cares about. Sampling at ingress edge routers is enough to build the full matrix: every DC-to-DC byte enters EBB exactly once, at the edge router next to its source DC, so counting there counts each byte once; the destination DC comes from the sampled header. Scaling up: if 300 sampled packets in a minute were DC1 → DC2 gold, with N = 10 000 and 1 500-byte packets, the estimate is 300 × 10 000 × 1 500 B ≈ 4.5 GB per minute ≈ 0.6 Gb/s.
• Open/R is a distributed routing platform (not just a protocol) that Meta runs on every router. It replaces OSPF/IS-IS and lets TE applications add their own information. Its parts, as on the slide: Spark discovers neighbours (hello messages); LinkMonitor tracks link health and measures each link's RTT; KvStore is a key-value store replicated across all routers, holding adjacencies and prefixes; Decision computes routes from it; FIB programs them into the hardware. KvStore is eventually consistent: different routers may briefly see different versions, but they converge. That is fine for link state (like a “likes” counter that is briefly off by one) but not for something like a bank balance.
• Two-stage failure response: local recovery (LSP agent activates a preinstalled backup, hundreds of ms) → global reoptimization in a later controller cycle. Reachability after a failure doesn't guarantee capacity: several rerouted demands may pile onto the backup.

5.3 TE policy: multicommodity flow and service classes

commodity k = (source DC, destination DC, class), demand d_k, candidate paths P_k
decision    x_kp = Gb/s of k on path p
carry       Σ_p x_kp = d_k
share links Σ_{k,p∋e} x_kp (+ burst margins) ≤ U · c_e      ← couples the demands
objective   min U  (MLU)   — or min Σ cost·x (latency) for gold

In words: a commodity is one “kind” of traffic that must get from A to B (here: one DC pair in one service class). “Multicommodity flow” means many such demands share the same links. The decision is how many Gb/s of each commodity go on each of its allowed paths. The “carry” line says each demand is fully routed; the “share links” line adds up every commodity on each link and keeps it under the target, which is what makes the demands compete. A burst margin is extra capacity set aside on top of the average rate so short bursts of high-priority traffic don't overflow the link.

Constraints say what is possible; the objective chooses what is preferred.

HPRR: Meta's heuristic (HW2 Q5, explicitly examinable)

Solving the exact LP with millions of variables every minute is too slow. Heuristic Path ReRouting reroutes one LSP at a time. It accepts a reroute only if the max utilization along the new route (after the move) is lower than the max along the current route (before). Candidate routes come from Dijkstra with exponential link cost w_e = exp[α(u′_e/u* − 1)] (u′ = the link's utilization if the LSP uses it). The current route is also a candidate.

• LSP granularity gap: 8 Gb/s over links of 10 and 6. Arbitrary split 5/3 gives MLU 0.5. Four 2-Gb/s LSPs force splits in {0,2,4,6,8}, so the best is 6/2 → MLU 0.6. More, smaller LSPs close the gap but cost more forwarding state and computation.
• Local optimum: moving one LSP at a time can get stuck where only a swap (two simultaneous moves) helps. HW Q5.2: link L carries 4 Gb/s of fixed background plus A (6); link R carries B (4); both 10 Gb/s. Current max = 10/10 = 1.0. Move A to R: R becomes 10/10 = 1.0, not lower, so rejected. Move B to L: 14/10 = 1.4, rejected. HPRR is stuck at 1.0, yet moving both (A → R, B → L) gives L = 8, R = 6, MLU 0.8. Fix: consider pairs of moves, at a higher combinatorial cost (still not globally optimal).
• Sum-of-costs bias: a 2-hop route pays two link costs, so HPRR can prefer a 1-hop route with a higher MLU. That is deliberate (longer isn't always better for Meta). Fix: use the route's bottleneck (post-move MLU) as the metric. That doesn't fix the joint-optimization issue.

5.4 Route programming: segment routing, Binding SIDs, versioned updates

• Baseline (install per-path rules at every router): many forwarding updates per path change.
• Static labels + source routing: every router gets fixed label→interface rules at startup, and the controller only changes the label stack at the source (headend). A packet's path is in its header. A segment (label) can name a node (“get to router D by its shortest path”) or an adjacency (“leave through this specific link”). Slide example: A pushes [16104, 203]. 16104 = node SID of D, so the packet goes A → B/C → D on shared shortest-path entries (popped one hop early: PHP). At D, 203 = adjacency SID for the D → E link.
• Limit: EBB hardware reportedly handles a stack depth of 3 (lookups must stay shallow in the header; hashing behavior). The slide's 5-hop example needs 5 labels, so longer paths need a Binding SID: a label naming a programmed continuation at an intermediate router. A dynamic SID per (site pair, class) can point to a next-hop group, giving weighted ECMP across several continuations, i.e., a path bundle.

Without this, “eventual consistency” updates (send all messages, let them land whenever) create transient black holes (A switches before J has its rule) or loops (an old J→A rule). Meta: one version bit in the packet (it alternates 0/1, since only two versions coexist), and the source flips only after the transaction is acknowledged by all routers. This is cheap, though not the most efficient option. Google instead stages updates (e.g., downstream first) so every intermediate state is safe. Side effect: mid-update, packets of one flow may take different paths, so the sender sees an RTT change that isn't congestion.

5.5 Capacity planning uses the same TE model

Basic TE: given capacities, choose rates. Planning: choose capacities so that TE stays feasible for every demand matrix in a set H and every failure in a set S (cˢ = surviving capacity). Building fiber takes months or years, so the forecast comes from compute commitments (GPUs, CPUs, storage being bought per site), not from product teams' guesses.

Traffic between groups must cross the cut links. It is enough to check simple cuts (single or few links) rather than all exponentially many. Scale: several thousand machines; 1 M routing scenarios in < 3 min; full plan for 300+ nodes and 1000+ links in < 6 h (via decomposition and parallelism).

Left open at the end of the Meta case (answered by Google): enforcing tenant shares under unpredictability, sharing capacity across planes, solving huge LPs efficiently.

6 · Google: intent, Orion, bandwidth functions, B4, BwE, dSDN

Lectures 14–16 · HW2 Q4. Google's “DNA” is expressing desired behavior: intent, and fairness via bandwidth functions. B4 = the internal inter-DC WAN (sites become vertices, inter-site capacity becomes edges); B2 = the user-facing one.

6.1 Intent-based networking (RFC 9315)

Intent = a declarative statement of goals and outcomes: what to achieve, not how (like SQL, not Python). It separates the TE/ops people from device configuration (what the RFC calls “nerd knobs”).

Examples of intent: steer traffic from geography X away from geography Y unless the destination is in Y · avoid vendor V's equipment for customer C even at reduced service · smart-city signal traffic on dedicated, redundant, non-fate-sharing slices. Non-examples: configure an interface's IP (configuration) · “alert when utilization > threshold” (a rule) · “deny P1 unless from P2” (an access policy tied to prefixes; if the prefixes change, the “intent” breaks).

Unwrapping an intent means making explicit its traffic scope (S, A→C), required service (8 Gb/s when S offers that much), maintenance scope (no forwarding on e), failure assumptions, and preferences (shorter paths). Lifecycle: Interpret → Check & plan (feasible?) → Fulfill (paths, splits, host limits, update order) → Assure (observe) → Respond (repair, re-plan, or report that the contract can't be met). Intents can be infeasible (8 Gb/s across a 6 Gb/s cut) or conflicting (two mandatory 8 Gb/s services on one 10 Gb/s bottleneck). Then identify the conflict and ask for a changed contract, a different maintenance plan, or more capacity.

6.2 Orion: Google's SDN controller (per domain)

• Pub-sub (publish–subscribe) = components announce changes to a shared store, and whoever cares has subscribed and gets notified. Nobody needs to know who else is listening.
• Reconciliation works like a thermostat: compare desired with actual, act to close the gap, check again. If a switch reboots and loses a rule, the Flow Manager sees “desired has rule X, observed doesn't” and reinstalls it, with no special recovery code.

• NIB as pub-sub: components subscribe to state changes. The alternative, the NIB invoking registered callbacks, would make the NIB aware of every reaction and turn it into a bottleneck that is hard to reason about.
• Reconciliation at every layer: desired state moves down, observed state moves up, and each controller acts to reduce the difference. This repairs drift, e.g., rules missing after a restart.
• A route request is a sequence of state changes: ① Request: an app writes a route intent (“prefix P reachable via these ports”) into the NIB → ② Resolve: the Routing Engine (subscribed) computes flows and node dependencies → ③ Realize: the Flow Manager programs switches → ④ Report: observed state confirms, with acks back up the chain.
• Intent depends on the layer: service contract → global TE choice (aggregate over site paths and splits) → domain routing (switches) → switch programming (entries, next-hop groups).

6.3 Sharing policies, then bandwidth functions

With source control (Google also controls the sending hosts, so it can cap how fast each app sends), TE also chooses the admitted rate r_i ≤ d_i: how much of app i's demand d_i is let into the network, not just where it goes. That needs a language for how to share, even within one class. The slide's bar chart splits one 8 Gb/s link three ways: equal 4 / 4, weighted + capped 6 / 2, priority to app 2 0 / 8. Same physical limit, different policy. The whiteboard example (two apps on a 10 Gb/s link):

Real policies are hierarchies (Q&A). At the root: a few classes with strict priority between them, often softened by minimum guarantees (strict only beyond some allocation). Inside each class the split continues, e.g., Instagram and Facebook Marketplace are both business-critical, but Instagram gets a guarantee because it is far more bandwidth-hungry. The hierarchy is global; its configuration is nuanced. Bandwidth functions are Google's language for expressing exactly this. (A vertical bandwidth-function segment would mean infinite priority; you can write it mathematically but it makes no practical sense.)

Lecture numbers (App1 = min(3s, 6), App2 = min(s, ·)): C = 4 → s = 1 → (3, 1): both unsatisfied, so the 3:1 weight shows in the rates. C = 8 → s = 2 → (6, 2): App1 hits its cap. C = 12 → s = 6 → (6, 6): the extra goes to App2. A function whose slope changes (e.g., App1 gets its first 4 Gb/s with strict priority, then App2 grows faster) expresses policies that no single fixed weight ratio can, even work-conserving. That is the punchline of HW2 Q4.

Freezing at other bottlenecks, and routing freedom

A group is frozen once any link on its path is full (or it hits its cap). The others keep growing. The routes decide where growth stops, and TE can change the operating point (both cases carry 8 Gb/s on A–B).

Aggregation: add heights at the same s

Parent P = child1 + child2 (add vertically, never add the s coordinates). Every bend has a child-level explanation: slope 4 while both grow, slope 1 after child 1 caps, slope 0 when everyone is satisfied. Decompose: read the parent backward (allocation → local s), then read each child forward at that s. Example: parent gets 11 → s = 5 → children (6, 5). Aggregates keep the policy information that a single total-demand number would lose. Solve a small problem on aggregates, then split it locally (and distributed) to children.

6.4 The B4 allocation algorithm (waterfill over paths)

Goal: max-min fairness in fair-share coordinates. Raise the smallest shares first, and keep raising the groups that can still grow. Each flow group (FG) uses its cheapest path first. When a link on that path fills, the group's rate at that point stays on the filled path and further growth spills to its next path in cost order. A group freezes when it hits its demand cap or has no path with spare capacity. Lecture example (directed links; cost 1 per link, except A–D costs 10):

The two groups' bandwidth functions (read from the slide's plot): FG1 (A→B) = 11s up to s = 1.5 (16.5 Gb/s), then slope 1 up to its cap of 20 at s = 5. FG2 (A→C) = s/2 (cap 10). FG1 is far more important at first (weight 11 vs ½).

Quantization: hardware can't split 0.762

Why it's needed: the algorithm above produces exact fractions (FG1 sends 8.33/20 = 5/12 of its traffic on A→C→B). A switch splits traffic by hashing flows into a small number of equal buckets, so it can only do fractions like 0, ½, 1 (with K = 2 buckets). The allocation has to be rounded to what the hardware can express.

Switches implement splits with a finite number of equal forwarding-weight units (e.g., K = 2 → 0%, 50%, 100%). Rounding each group independently can overload a shared link: FG1 (½, 5⁄12, 1⁄12) → (½, ½, 0) and FG2 (⅓, ⅔) → (½, ½) put 20·½ + 5·½ = 12.5 Gb/s on A–C (capacity 10). B4 then greedily adjusts to fit. Final result: FG1 = 10 AB + 10 ACB, FG2 = 5 on ADC (FG1 leaves the D route, FG2 takes all of it).

6.5 BwE: the Bandwidth Enforcer (making the shares real at the sources)

TE ↔ BwE loop: TE (B4) gives paths + split weights; BwE gives prioritized demand. TE can change routing; BwE holds routing fixed and carries budgets down to sender limits. Both speak bandwidth functions. On each host, the BwE limit caps TCP. If cwnd/RTT is below the limit, congestion control is what binds; otherwise the limit binds. Benefits: predictability, protecting the network from bursts, and a clear answer to “why am I limited?” (“that's the fair share in your contract”). Costs: an enforcer on every host (a bug can cripple the fleet), complex control loops at sub-minute to minute scale, and debugging whether BwE or CC is limiting you. Delayed updates waste capacity (HW2 Q4.3): if a team's demand drops below its budget, the spare isn't redistributed until the next parent cycle. Fix: event-driven updates or demand reports, at the cost of more messages and computation.

Orion in B4: the global TE chooses paths network-wide. In each domain, a TE app turns those choices into RouteAdverts for the Routing Engine and coordinates backup and fallback. The Path Exporter summarizes physical paths and capacity for TE and BwE (failures change what it exports). Raven integrates BGP and IS-IS so central TE and conventional routing coexist. Summary slide: new abstraction (bandwidth functions) → more precise TE input · source control → division within a class + network protection · all allocation can be expressed as intent and enforced globally.

6.6 Did SDN simplify or complicate WAN operations? → dSDN (2024)

Data: of the 41 largest B4 outages over four years, 42% were control-only and 10% control-and-data, so 52% had a control-related root cause (the rest of the pie: 32% data-plane only, 16% other). What changed since SDN's birth: router vendors opened up. Operators now run their own software on router CPUs (Meta runs Open/R on every vendor's box).

(MPLS + RSVP-TE is a distributed mechanism for reservation, but it doesn't solve the global TE problem either.) Not covered: WAN hardware and topology design, DC/WAN commonalities.

7 · Microsoft: SWAN, TeaVaR, OneWAN

Lectures 16–17 (taught by the TA). Microsoft's DNA: failure handling, and historically solving the optimization problem exactly with an LP solver (Meta and Google use heuristics).

7.1 SWAN: centralized TE for high utilization

1. Collect: hosts tell their service's broker (a per-service server that gathers demand and later hands out rate limits) how much they want to send; brokers pass totals to the controller. Network agents on the switches report topology and link state.
2. Compute: an optimal, fair allocation, class by class. Interactive traffic (user-facing, latency-sensitive) is allocated first; background traffic (bulk copies, backups) gets what remains. Within a class SWAN wants max-min fairness and high throughput. It gets there approximately by solving a series of LPs: each one maximizes total throughput while not letting any flow fall below the level it reached in the previous round, so the smallest flows are raised first, like water-filling. Output: a rate for each tunnel between each pair of DCs.
3. Realize: brokers rate-limit hosts; network agents configure only the edge (ingress) switches. Core routers have statically configured label-switched paths, so SWAN just picks tunnels and weights at the edge (e.g., tunnel 1: 50%, tunnel 2: 30%, tunnel 3: 20%). Each tunnel entry is a rule, and the rule table is small. Recomputed about every 5 min.

Congestion-free updates with scratch capacity

Switches don't update simultaneously, so mid-update a link can carry some flows' old rates and others' new rates. Lecture example (links 100 Gb/s): initial U(F1 80, F2 20) / L(20, 80) → target swap. If F2 moves first, U = 80 + 80 = 160. If F1 moves first, L overloads. Splitting into chunks without spare room still overloads.

For every link e and every step i → i+1:
     Σ_f  max( x_f,e(i) , x_f,e(i+1) )  ≤  c_e          ← worst case: any mix of old/new
Flow conservation each stage:  Σ_e x_f,e(i) = d_f
Objective: maximize headroom (slack); if infeasible with k stages, try k+1

Whiteboard version of the lecture LP (a = F1, b = F2; u = upper, l = lower link):
  variables per stage i:   a_u^i, a_l^i, b_u^i, b_l^i
  each flow fully carried: a_u^i + a_l^i = 80,   b_u^i + b_l^i = 80
  upper link, step i→i+1:  max(a_u^i, a_u^{i+1}) + max(b_u^i, b_u^{i+1}) + h ≤ 100
  (same for the lower link) · stage 0 and stage 3 are fixed · maximize h, h ≥ 0
With scratch capacity s (fraction kept free on every link): at most ⌈1/s⌉ − 1 steps
     (s = 10% → ≤ 9 · s = 20% → ≤ 4 · bigger s = fewer steps but less usable capacity)

Changing the tunnel set with limited rule space

If the new allocation uses different tunnels, you must install new rules before removing old ones. With infinite rule space: add all new rules, shift traffic congestion-free, delete old ones. In reality the table is small, so keep spare rule entries (scratch rule capacity). Lecture: from {1,2} to {3,4} with one spare slot: add 3 → compute an optimal allocation restricted to {2,3} → congestion-free shift → remove 1 → add 4 → shift to {3,4} (that allocation was already computed at the start) → remove 2. Getting to the target takes a series of LPs (allocation LPs for intermediate tunnel sets plus congestion-free plan LPs).

7.2 TeaVaR: utilization with an availability guarantee

EBB, B4, and SWAN recover reactively: fast local reroute, then the controller re-optimizes seconds to minutes later. Until then, allocations made for “all links up” can't be met, so there is no availability guarantee.

The slide's numbers, worked out. P(fail): top L1 = 10⁻³, middle L2 = 10⁻¹ (flaky), bottom L3 = 10⁻³, independent.

• A 1-failure-tolerant allocation (20 Gb/s spread so any two survivors carry it) is met whenever at most one link is down: 1 − 0.02% = 99.98%. So 20 Gb/s can be guaranteed at β = 99.98%, while the 2-failure guarantee only allows 10.
• Sending 10 + 10 on only the two reliable links (ignoring the flaky middle) is met whenever both are up: ≈ 99.8%, not 99.98%.

Independence:     P(scenario q) = Π_links  P(link state in q)       (2^n scenarios for n links)
Loss of a flow in q:  1 − (demand still deliverable on surviving tunnels)/(demand)
                      (no rerouting inside the scenario)
L(x, q) = MAX over flows of that loss                                  ← worst-off flow
Loss distribution for allocation x: values L(x,q) with probabilities P(q)
V(x) = VaR_β = β-percentile of that distribution  (smallest v with P(L ≤ v) ≥ β)
TeaVaR:  x*, V* = argmin_x V(x)  s.t. link capacities
Guarantee: scale every allocation by (1 − V*) → satisfiable β of the time

Lecture loss example (scenario q4: L1 down, L2 and L3 up): F1 sends (2, 3, 5) and F2 sends (4, 3, 3) on (L1, L2, L3), demand 10 each. F1 loses 2/10 = 0.2, F2 loses 4/10 = 0.4, so L(x, q4) = 0.4 (the max over flows). Probability primer: dependent events use P(A∩B) = P(A)·P(B|A); independent ones use P(A∩C) = P(A)·P(C). The p-th percentile is the value below which p% of samples fall.

7.3 OneWAN: merge the split WANs

Challenges: ① routing-table scale (~10⁵ DC routes vs ~10⁶ Internet routes) ② fast failure repair ③ scaling the TE optimization ④ estimating Internet demand (not under your control) ⑤ migrating live traffic seamlessly.

• Max-flow = the most traffic that can be pushed from A to the destination through a given entry router, limited by the smallest capacities along the way.

• Router roles: aggregation routers keep the full IP tables (BGP with Internet and DC prefixes) and choose the egress next hop. Backbone routers keep no prefixes and just forward on MPLS labels the controller programs (TE paths and rates, as in SWAN). The agg→backbone hop is handled locally by steering, not inside the central LP, which keeps the LP smaller.
• Label stack along the path (slide): ingress edge → (BGP) → ingress aggregation router pushes [egress-site label, BGP next-hop node SID] (traffic steering) → ingress backbone router swaps the outer label for a TE path label (traffic engineering across the backbone) → egress backbone router pops it, leaving only the BGP next-hop SID (segment routing) → egress aggregation router pops that and forwards on IP → egress edge (BGP). Only the aggregation routers ever look at IP prefixes.
• Vocabulary: a trunk = all traffic from one source backbone router to one destination site in one priority class (the unit the optimizer allocates). Shared risk = links that can fail together because they share something physical, e.g. two “different” links running through the same fiber conduit. Committed share = capacity promised to a priority class in advance. Scavenger = the lowest priority, which only uses capacity nobody else wants.
• Solver chain: candidate paths (low-delay paths with fewer shared risks, plus max-flow paths) → reserve each priority's committed share → priority 0 (best-effort and higher): max-min fair rate per trunk → minimum cost while keeping fair rates; priority 1 (scavenger): max-min fair with the remaining capacity → balance link utilization (min MLU) → add risk-diverse paths (avoid shared risks) and re-optimize.
• Tractability: trunk = (source backbone router, destination site, class); compute paths only for pairs with demand · prune trunks < 500 Mb/s (only 2.5% of traffic) → 5× fewer constraint rows, 7× fewer variables · faster LP solvers (CLP, GLOP: about 5× faster than SWAN's original) with dual simplex and cost perturbation.

8 · Network verification

Lecture 18 (the last Unit 2 lecture; it's on the quiz). The question: can we guarantee that configurations are error-free? Not intent (that is human-readable), but the thousands of configurations generated from reconciling hundreds of intents. Updates, versioning, and TeaVaR plan for failures, but nothing so far catches a human or config error (a 4 typed instead of a 5 in a prefix).

8.1 The running example

8.2 The verification map

Model components: configuration (route rules, filters) · packet class (the headers in scope, as symbolic packets: one variable stands for every packet in the class, e.g. “any TCP packet to D on port 443, from any source address and port”, and the solver reasons about all of them at once instead of testing them one by one) · environment (which links are up or failed) → possible forwarding steps → compose → feasible paths and prefixes. A digital twin (a simulated copy of the network that you feed test packets) only checks the cases you thought to try; with billions of possible packets × failure combinations it can't cover them all. Symbolic search covers the whole modeled space in one query.

In the table: ∃ = “there exists”, ∀ = “for every”, ¬ = “not” (full symbol table in §8.3). A prefix of a path is its beginning part, e.g. S, B, S is a prefix that already repeats S.

8.3 Encoding in first-order logic

Letters used below: h = a packet header (symbolic: stands for every packet in a class at once); e = the environment, i.e. which links are up; x = the routing and forwarding choices; u, v = routers; S, D = source and destination.

Packet class    H_p = { h : h.dstIP ∈ D_IP ∧ h.proto = TCP ∧ h.dport = p }   (any src IP / src port)
ACL (ordered)   hit_i(h)   = match_i(h) ∧ ¬( match_1(h) ∨ … ∨ match_{i−1}(h) )   ← first match wins
                permit(h)  = ∨_i ( hit_i(h) ∧ action_i = allow )
One hop         N(u,v,h,e) = sel(u,v,h,e) ∧ up(u,v,e) ∧ permit_{u→v}(h)
                             (route selected ∧ link up ∧ ACL permits — ALL three)
Path            Path(v0…vm,h,e) = ∧_{i
The same lines in plain words
Packet class: “all TCP packets to D's addresses on port p, from any source” — one symbol h covers all of them.

hiti: rule i matches the packet and no earlier rule did, so rule i is the one that decides. permit: the deciding rule says allow.

N(u, v): the packet can really move from u to v: routing picks v as next hop, the link is up, and the filter lets it through. All three are needed.

Path: every consecutive hop along a router sequence works. R(S, D): some such path goes from S to D.

Backward layers: R₀ = routers already at D; R₁ adds routers that can reach a router in R₀ in one working hop; and so on. S can reach D if S ever joins a layer. In a small network, as many layers as the longest path suffice.

≤ 1 failure as “every pair has one up”: if two links were both down, the clause (upa ∨ upb) for that pair would be false. Requiring every pair's clause to be true is the same as “at most one link is down”, using only and/or/not (pure SAT).

Query: “is there a failure case we allow, consistent with how the network behaves, in which the requirement fails?”

📈 How to read this figureThe reachability layers for a web packet with S–F failed. 0 steps: only D. ≤ 1 step: F joins, because F→D is selected, up, and permitted. B does not join: B→D is selected and up, but B's ACL denies port 443. ≤ 2 steps: S's only working next hop would be B, which is not in the previous layer, so S never joins. Web from S is unreachable: a counterexample.
Scenarios in scope with ≤ 1 failure on 4 links: none, S–F, F–D, S–B, B–D (5 cases, one symbolic query).
Before the repair, web is dropped for S–F down and for F–D down, so the query is SAT with counterexample “S–F down, web packet”.
After the repair (B permits web), it is delivered in all 5, so UNSAT.

8.4 SAT vs SMT; Minesweeper
SAT (Boolean satisfiability): given true/false variables and a formula over them, find values that make the formula true, or prove none exist. Here every variable is Boolean (link states, next hops, forwarding, reachability). It is NP-complete (no known algorithm is fast on every input), but modern solvers are fast on most practical instances. SMT (satisfiability modulo theories) adds richer domains:
bit-vectors (addresses), integers (route metrics), linear arithmetic (capacity: x₁ + x₂ ≤ 5, latency bounds). Use SMT to capture capacity, availability, or latency requirements.
Minesweeper (SIGCOMM 2017) is a compiler for router configurations: parse configs and topology → encode routing and forwarding as SMT constraints → search for violations.
It encodes the three kinds of routing policy: export (which routes a router advertises to each neighbour), import (which advertised routes it accepts) and selection (which accepted route it prefers). For example c ↔ a ∧ up ∧ accept: S has a usable route from B exactly when B advertised it, the S–B link is up, and S's import policy accepts it. It also encodes route preferences and interactions between protocols.
It checks stable routing states: states where routing has settled, so no router would change its choice given what its neighbours advertise and its policies. E.g. after S–F fails, the only stable state has S selecting the route via B, and the solver then checks the requirement in that state.
An ACL can also be implemented as “don't advertise”, so the routing configuration is analyzed too, not just the filters.
The caveats A SAT result is solid evidence (a concrete counterexample). UNSAT is only as good as the model: missing ACLs, an external controller that reacts to failures, or humans “fixing” things live are all outside it.
Richer models cost more computation (NP-hard). The research is about expressive-but-efficient encodings and network-specific algorithms.
Unit 2 summary (last slide): private WANs control their traffic (choose routes, divide capacity among tenants, rate-limit at sources for predictability) but still need CC for RTT-scale reactions.
Centralized control gives an easier interface and globally optimal decisions, but it must coexist with distributed control and is a logical single point of failure. Modeling failure to hedge against it is a critical operation.
✍ iPadProblem 8.1 — Scenario table for the running example calc
Routing: S uses S–F–D when S–F and F–D are both up; otherwise it settles on S–B–D. F's ACL: deny TCP/23, permit everything else. B's ACL (first match): TCP/443 → deny; TCP/22 → permit; default → deny.
Requirements: web (443) delivered under any ≤ 1 link failure; SSH (22) goes through F in normal operation; telnet (23) never delivered.
For each scenario (none, S–F, F–D, S–B, B–D down), is web / SSH / telnet delivered, and via which node?
Which requirements are violated, and in which scenarios?
Repair B's ACL minimally and state the verification result after the repair.
Show solution
down
path
web
SSH
telnet
none
S–F–D
✓
✓ via F
blocked at F
S–F
S–B–D
✗ dropped at B
✓ via B
blocked (default deny)
F–D
S–B–D
✗ dropped at B
✓ via B
blocked
S–B
S–F–D
✓
✓ via F
blocked at F
B–D
S–F–D
✓
✓ via F
blocked at F
(b) Only web reachability under failure fails (S–F down, F–D down). The waypoint holds in normal operation; isolation holds everywhere.

(c) Change B's first rule to TCP/443 → permit (or delete it). Web is then delivered in all 5 scenarios, so the query “≤ 1 failure ∧ model ∧ web not delivered” is UNSAT; telnet is still default-denied.
✍ iPadProblem 8.2 — Reachability layers calc
Same network and buggy ACL as 8.1, for a web packet. Using N(u,v) = selected ∧ up ∧ permit and backward layers R₀ = {D}, Rk = Rk−1 ∪ {v : N(v,u) for some u ∈ Rk−1}:
Compute R₀, R₁, R₂ with F–D down.
With S–B down.
With F–D down after the repair.
Why do two layers suffice here?
Show solution
R₀ = {D}. F→D: link down ✗. B→D: selected and up, but the ACL denies 443 ✗ → R₁ = {D}. S→B is selected but B ∉ R₁ → R₂ = {D}. S unreachable.
R₁ = {D, F} (B→D still denies web). S→F is selected, up, and permitted → R₂ = {D, F, S}. Reachable.
R₁ = {D, B}, R₂ = {D, B, S}. Reachable.
The longest loop-free path (the diameter) is 2 hops, so k = 2 covers every possible path.
✍ iPadProblem 8.3 — Encoding an ordered ACL short
B's ACL in order: r1: src ∈ 66.6.0.0/16 → deny; r2: TCP/443 → permit; r3: TCP/22 → permit; r4: default → deny.
Decide: web from 66.6.1.1; web from 10.0.0.1; telnet from 10.0.0.1; SSH from 66.6.7.7.
Write hit₂(h) and permit(h) in first-order logic.
An engineer swaps r1 and r2. Which decision changes, and what kind of requirement does that violate?
Show solution
deny (r1) · permit (r2) · deny (r4) · deny (r1).
hit₂(h) = match₂(h) ∧ ¬match₁(h) = (h.proto = TCP ∧ h.dport = 443) ∧ ¬(h.src ∈ 66.6.0.0/16).
permit(h) = (hit₂(h)) ∨ (hit₃(h)), since only r2 and r3 allow (equivalently ∨i hiti ∧ actioni = allow).
Web from 66.6.1.1 becomes permitted: an isolation violation (the blocked source now reaches D). Order matters, which is why the encoding includes ¬(earlier matches).
✍ iPadProblem 8.4 — Writing requirements and the query short
For the network in 8.1 (links SF, FD, SB, BD), write:
Isolation for telnet.
Waypointing for SSH. Does it imply SSH is delivered?
Loop freedom.
“At most one link down” as pure Boolean clauses. How many clauses?
The solver query that checks “web survives every single-link failure”, and how to read SAT vs UNSAT.
Show solution
∀h ∈ H23, ∀e allowed: ¬R(S, D, h, e).
∀h ∈ H22, ∀ delivered paths π = (S … D): F ∈ π. No: it constrains delivered paths only, so dropping all SSH satisfies it vacuously. Add reachability if SSH must arrive.
¬∃ path prefix v₀…vm, ∃ i ≠ j : vi = vj (checked on prefixes, since a loop never delivers).
Every pair has an up link: (upSF ∨ upFD), (upSF ∨ upSB), (upSF ∨ upBD), (upFD ∨ upSB), (upFD ∨ upBD), (upSB ∨ upBD): C(4,2) = 6 clauses.
Allowed(e) ∧ M(C, h, e, x) ∧ h ∈ H443 ∧ ¬R(S, D, h, e). SAT → the assignment is a counterexample (which link failed, the packet, the forwarding state). UNSAT → no violation exists within the model's scope.
✍ iPadProblem 8.5 — Why symbolic search? calc
(a) How many failure scenarios are in scope for ≤ 1 failure on 4 links? ≤ 2 failures? (b) For 50 links with ≤ 2 failures? All subsets? (c) Why model packets symbolically (H443) instead of enumerating headers?
Show solution
(a) 1 + 4 = 5; 1 + 4 + 6 = 11. (b) 1 + 50 + 1225 = 1,276; all subsets 2⁵⁰ ≈ 10¹⁵. (c) A class like “any src IP, any src port, TCP, dport 443” covers ~2⁴⁸+ concrete headers. Simulation (a digital twin) can't enumerate them; one symbolic query covers them all.
✍ iPadProblem 8.6 — SAT, SMT, Minesweeper MCQ
Which statements are correct?
☐ A. If the solver returns UNSAT for (allowed failures ∧ model ∧ ¬property), the property is guaranteed in the real network under all conditions.
☐ B. A SAT result yields a concrete counterexample: a failure condition, a packet, and forwarding state that violate the property.
☐ C. Pure Boolean SAT can't directly express “the sum of competing traffic on a link ≤ its capacity” over integer rates; SMT can.
☐ D. Minesweeper derives routing and forwarding constraints from router configurations, including import policies and route preferences, and checks stable routing states.
☐ E. Waypointing alone guarantees that packets are delivered.
☐ F. Loop freedom is checked on forwarding prefixes, because a looping packet may never be delivered.
Show solution
Correct: B, C, D, F
A ✘ — Only within the modeled scope. Missing behaviors (external controllers, humans, unmodeled ACLs) aren't covered.
B ✔ — The witness explains the problem.
C ✔ — SMT adds integers, bit-vectors, linear arithmetic.
D ✔ — A compiler for configs; stable states after failures.
E ✘ — It constrains only delivered paths; add reachability.
F ✔ — A loop witness can end before delivery.

9 · Cumulative refresher: Quiz 1 material (Lectures 1–8)
Compressed from your Quiz 1 and exam-1 reference. Expect at most one or two questions here, probably wrapped around PCC/BBR ideas.
Topic
The one thing to remember
End-to-end argument
Correctness (e.g., a file arriving intact) can only be completely verified at the endpoints. Link-level checks only improve performance. Fate-sharing: keep connection state at the endpoints so the network survives router failures.
NUM
max Σ U(x_s) s.t. Ax ≤ c. Source rule U′(x) = path price. log utility → proportional fairness; α→∞ → max-min; α = 2 → Reno-like (min potential delay); linear → max throughput (starves long flows).
Reno / AIMD
+1 per RTT, halve on loss. x ∝ 1/(RTT·√p) → RTT unfairness. Needs ≈ 1 BDP of buffer to stay at full utilization. CUBIC grows on wall-clock time (RTT-fair).
Fluid models
dW/dt = [inc·(1−p) − dec(W)·p] / R: read the increase term (AI if constant, MI if ∝W) and the decrease term (MD if ∝W, AD if constant).
Copa
d_q = RTT_standing − RTT_min; λ_target = 1/(δ·d_q); λ_current = cwnd/RTT_standing. Current > target → decrease. ±v/δ per RTT; about 1/δ packets queued; competitive mode.
Vegas
Q = (W/RTT_min − W/RTT)·RTT_min (packets queued). Q < α → +1; Q > β → −1; otherwise hold (α=1, β=3 typical). Starves beside Reno.
Bufferbloat
queue delay = bytes queued × 8 / link rate. A huge FIFO plus loss-based CC gives seconds of delay. Fix with AQM (CoDel) or delay-aware CC.
BBR
BtlBw = windowed max delivery rate (10 rounds); RTprop = windowed min RTT (10 s). BDP = BtlBw·RTprop; cwnd ≈ 2·BDP; must pace. PROBE_BW gains 1.25/0.75/1×6. PROBE_RTT drains inflight to refresh the min RTT. v1 ignores loss (unfair); v2 adds loss/ECN; v3 refines.
ECN / DCTCP
Marks give a signal before buffer-overflow loss, with no retransmission. Standard ECN response = react as if one loss (once per RTT), not proportionally. DCTCP: cwnd ← (1 − α/2)cwnd.
CoDel
Sojourn time per packet. Bad queue = min sojourn > target (5 ms) for a whole interval (100 ms). Drop gaps then shrink as 100/√count. Persistent delay matters, not the average or the max.
INT
Switches stamp per-hop info (queue length, tx bytes, timestamp, capacity). This reveals which hop is congested, which an ECN bit can't. Header overhead grows with hops, so it is used in datacenters.


📈 How to read this chart (BBR's model of the path)x-axis: how much data the sender has in flight. Blue: the delivery rate the receiver sees. Orange: the RTT. Left of the BDP line, more in-flight data means more delivered (the pipe isn't full) and the RTT stays at its minimum (no queue). At the BDP (bandwidth × min RTT) the pipe is exactly full: maximum delivery rate and minimum RTT, the optimal point BBR aims for. Right of it, extra data only builds a queue: delivery stays flat and the RTT climbs, until the buffer overflows at “loss”. Loss-based algorithms (Reno, CUBIC) operate out near the loss line; BBR tries to stay at the knee.
9.1 Bridges: Part 1 ideas that Part 2 reuses
The professor said Quiz 2 may use “ideas that depend on information we covered before quiz one”. These are the links most likely to be tested. The § numbers point into your Exam 1 reference (networks-exam1/notes/EXAM_REFERENCE.md), the full source for Lectures 1–8.
Part 2 topic
Part 1 idea it builds on
Exam 1 ref.
TE vs congestion control (§3)
The two knobs: change rates (CC, endpoints) or routes (TE, control plane). Controlling both is rare, except in hyperscaler WANs.
§3.1, §4.6
Min-MLU, MCF (§3, §5)
Routing matrix A and link loads Ax; NUM's Ax ≤ c becomes TE's Σ x_kp ≤ U·c_e.
§3.2, §3.5
B4 waterfill, bandwidth functions (§6)
Max-min fairness by water-filling; weighted utilities (w·log x); fairness is a property of the utility. Parking lot: max-min (½, ½, ½) vs proportional (⅓, ⅔, ⅔).
§3.3, §3.4
PCC utilities (§1)
Utility functions, concavity (one hill, so climbing works), Copa's utility ln x − δ ln d.
§3.4–3.5, §6.1
PCC vs Copa / BBR (§1)
Model-based vs model-less; Copa targets 1/δ queued packets (delay magnitude); BBR estimates BtlBw and RTprop.
§10.1, §6, §10.3–10.8
PCC rate-based vs windows (§1.4 aside)
Windows vs rates; pacing hybrid: cap inflight at cwnd, pace at 2·cwnd/RTT.
§5.3
QUIC ossification (§2)
Internet ossification then vs now: one company now owns server, network and client, so it can deploy (BBR, QUIC).
§7.2
QUIC reliability (§2)
End-to-end argument: reliability belongs at the endpoints; definition of reliability (all delivered, in order).
§2.5, §2.1
SDN pros/cons, dSDN (§4, §6.6)
SDN's real benefits (cheap hardware, global optimization) vs cost (network-wide blast radius); “single point of failure” = a logically centralized wrong decision, not a dead machine.
§2.1
dSDN fate-sharing (§6.6)
Clark's fate-sharing: state is lost only if the entity that needs it is lost. dSDN applies it to control: control depends only on the routers and links it manages.
§2.3
Data plane vs control plane timescales (§4, §5)
Data plane: per packet, nanoseconds. Control plane: seconds to minutes. Hence local fast reroute + slow central TE.
§2.1
BwE, entitlements, source control (§5, §6.5)
Deployment authority: the feasible mechanism depends on who controls the bottleneck and the sender. Private WANs control both, which is why host rate limits work there and not on the open Internet (cf. why ECN and source quench failed).
§10.2, §9.3, §2.6
TeaVaR, SWAN headroom (§7)
The “finite / delayed / distributed” framing: operators keep failure headroom and can't plan to use 100%.
§3.7
How to use this (about 15 min, Day 3): Lecture 19 said Part 1 appears only inside the PCC question, so focus on the PCC, rate-vs-window and NUM rows. read your Exam 1 reference §1 (formula sheet) and §11–13 (comparison tables), then this table, then do problems 9.9–9.10. If any row feels unfamiliar, open the § it points to.
✍ iPadProblem 9.1 — NUM: fairness on two links calc
Two links, 10 Mb/s each. Flow 0 crosses both; flow 1 uses only link 1; flow 2 only link 2. Find the allocation under (a) max throughput (linear utility), (b) proportional fairness (log utility), (c) max-min fairness.
Show solution
(a) x₀ = 0, x₁ = x₂ = 10 (total 20; the long flow starves).
(b) Maximize log x₀ + 2·log(10 − x₀): 1/x₀ = 2/(10 − x₀) → x₀ = 10/3 ≈ 3.33, x₁ = x₂ = 6.67.
(c) Equal share on each bottleneck → 5, 5, 5.
✍ iPadProblem 9.2 — Copa decision calc
Copa, δ = 0.5, cwnd = 20 packets, RTT_min = 40 ms, RTT_standing = 50 ms. Compute d_q, the target and current rates (packets/s), and the next adjustment and its size per RTT (v = 1).
Show solution
① Queueing delay = standing RTT − minimum RTT: dq = 50 − 40 = 10 ms. ② Copa's target rate is the rate at which this flow would keep 1/δ packets queued: λtarget = 1/(δ·dq) = 1/(0.5·0.010 s) = 200 pkt/s. ③ Current rate = cwnd / standing RTT = 20/0.050 s = 400 pkt/s. ④ Current > target means it is queueing more than it wants → decrease. Each ACK changes cwnd by v/(δ·cwnd), and there are ≈ cwnd ACKs per RTT, so ≈ v/δ = 1/0.5 = 2 packets per RTT.
✍ iPadProblem 9.3 — Vegas decision calc
Vegas, W = 24 packets, BaseRTT = 40 ms, current RTT = 50 ms, α = 1, β = 3. Compute Q = (W/BaseRTT − W/RTT)·BaseRTT and the action.
Show solution
Expected rate (if nothing were queued) = W/BaseRTT = 24/0.040 s = 600 pkt/s. Actual rate = W/RTT = 24/0.050 s = 480 pkt/s. The difference (120 pkt/s) is data sitting in queues instead of moving; multiplying by BaseRTT turns it into a packet count: Q = 120 × 0.04 = 4.8 packets of this flow queued. Vegas wants between α = 1 and β = 3; 4.8 > β → too much queued → decrease cwnd by 1 (it would increase if Q < α and hold if in between).
✍ iPadProblem 9.4 — Bufferbloat calc
A 50 Mb/s bottleneck with a FIFO holding 2 MB of waiting data; base RTT 30 ms. (a) Queueing delay for a packet behind 2 MB? (b) Resulting RTT? (c) Max waiting data (kB) to keep queueing ≤ 10 ms?
Show solution
(a) A packet must wait until everything ahead of it is transmitted. Convert bytes to bits first: 2 MB × 8 = 16 Mb. At 50 Mb/s that takes 16/50 = 0.32 s = 320 ms. (b) RTT = base RTT + queueing delay = 30 + 320 = 350 ms, more than 10× the base: that is bufferbloat. (c) Reverse it: the link drains 50 Mb/s × 0.010 s = 0.5 Mb in 10 ms, and 0.5 Mb ÷ 8 = 62.5 kB. Any queue larger than that adds more than 10 ms.
✍ iPadProblem 9.5 — BBR estimates calc
Delivery-rate samples 80, 95, 90 Mb/s; RTT samples 30, 25, 40 ms. (a) BtlBw, RTprop, BDP (kB)? (b) Why does BBR periodically cut inflight in ProbeRTT? (c) Why must BBR pace?
Show solution
(a) Max → 95 Mb/s; min → 25 ms; BDP = 95×10⁶ × 0.025 = 2.375 Mb = ≈ 297 kB. (b) To drain the queue so it can measure (refresh) the true min RTT, since max BW and min RTT can't be observed at the same time. (c) Without pacing, bursts build queues and delivery samples underestimate or distort the bottleneck rate.
✍ iPadProblem 9.6 — CoDel MCQ
CoDel with target 5 ms and interval 100 ms. Experiment 1: sojourn time stays at 6 ms for 300 ms. Experiment 2: sojourn alternates 3 ms (20 ms) and 30 ms (5 ms). Which are correct?
☐ A. Experiment 1 meets the persistent-delay condition after about 100 ms, even though its maximum is lower than experiment 2's.
☐ B. Experiment 2 enters dropping as soon as a 30 ms sojourn is observed.
☐ C. If experiment 1 persists, successive drop gaps shrink as 100/√count ms (100, 70.7, 57.7, 50 …).
☐ D. CoDel's target must be re-tuned whenever the link rate changes because it is measured in bytes.
Show solution
Correct: A, C
A ✔ — The minimum sojourn stays above target for a whole interval.
B ✘ — Within every interval the min is 3 ms < 5, so it's good queueing (a burst).
C ✔ — Control law.
D ✘ — Sojourn time is in time units, independent of link rate.
✍ iPadProblem 9.7 — Reading fluid models calc
A sender updates once per RTT R; it sees a loss indication with probability p. What algorithm does each describe?
(i) dW/dt = [3(1−p) − p·W/2]/R. (ii) dW/dt = [(1−p)·W/4 − p·W/2]/R. (iii) For (i), the equilibrium window.
Show solution
(i) AIMD: +3 packets per RTT without loss, halve (−W/2) on loss. (ii) MIMD: ×1.25 per RTT without loss, ×0.5 on loss. (iii) Set dW/dt = 0: 3(1−p) = pW/2 → W* = 6(1−p)/p.
✍ iPadProblem 9.8 — ECN, INT, end-to-end MCQ
Which are correct?
☐ A. ECN marks let the sender respond to congestion before buffer overflow causes loss, without retransmitting the marked packets.
☐ B. With Reno's standard ECN response, if 20% of a window's packets are marked the window shrinks by exactly 20%.
☐ C. INT records can show which hop had the largest queue; a single ECN mark can't.
☐ D. By the end-to-end argument, reliable link-level retransmission makes an endpoint file checksum unnecessary.
☐ E. BBRv1 reduces its rate in response to ECN marks.
Show solution
Correct: A, C
A ✔ — Signal before loss.
B ✘ — It reacts like one loss: halve, once per RTT.
C ✔ — Per-hop telemetry.
D ✘ — Only the endpoints can verify the complete transfer; link checks just help performance.
E ✘ — v1 ignores loss and ECN; v2 adds them.
✍ iPadProblem 9.9 — Bridges between Part 1 and Part 2 MCQ
Which statements are correct?
☐ A. dSDN's fate-sharing applies Clark's principle to control: control should depend only on the routers and links it manages, so it fails only when they do.
☐ B. Host rate limits (BwE) work in Google's WAN for the same reason ECN never deployed on the open Internet.
☐ C. Min-MLU traffic engineering and NUM congestion control turn the same knob: both adjust source sending rates.
☐ D. QUIC's fast rollout fits the Part 1 “de-ossification” story: one company controlling servers, clients and much of the traffic can change transport behavior quickly.
☐ E. In B4's waterfill, if every flow group has the same bandwidth function B(s) = s and no cap, the result is max-min fair.
☐ F. SDN's single-point-of-failure risk is mainly the controller machine crashing, which replication solves.
Show solution
Correct: A, D, E
A ✔ — Clark: state is lost only when the entity that needs it is lost. dSDN: control runs on the routers, in-band, so no separate control network or server can fail independently.
B ✘ — Opposite reasons. BwE works because one authority controls both the senders and the network. ECN (and ICMP source quench) failed because authority on the open Internet is fragmented and networks don't trust each other.
C ✘ — Different knobs: CC changes rates with routes fixed; TE changes routes with demand fixed (Exam 1 ref §3.1).
D ✔ — Exam 1 ref §7.2: deployability went up because one company can own the server, much of the network and the client. QUIC also runs in user space, so updating the app updates the transport.
E ✔ — Equal slopes mean equal priority, so raising the common fair share s is exactly water-filling: max-min fairness.
F ✘ — Controllers are replicated. The risk is a logically centralized wrong decision (a bug or bad config) applied network-wide: the blast radius.
✍ iPadProblem 9.10 — Parking lot: max-min, proportional, and bandwidth functions calc
Two 10 Gb/s links in series. A long flow L crosses both links; S1 uses only link 1; S2 uses only link 2. Everyone has unlimited demand.
Max-min fair rates (water-filling)?
Proportionally fair rates (maximize log L + log S1 + log S2)?
Run B4-style waterfill with bandwidth functions B(s) = s for all three groups.
Repeat (c) with S1's function changed to B(s) = 2s. What do you notice?
Show solution
Raise all equally; both links fill together at 5: L = S1 = S2 = 5.
By symmetry S1 = S2 = 10 − L. Maximize log L + 2·log(10 − L): 1/L = 2/(10 − L), so L = 10/3. L = 3.33, S1 = S2 = 6.67. The long flow pays two link prices, so it gets less.
Equal functions = max-min. Link 1: s + s = 10 → s = 5, and link 2 likewise. (5, 5, 5), same as (a).
Link 1: L + S1 = s + 2s = 10 → s = 10/3. L = 10/3 and S1 = 20/3 freeze (link 1 is full). S2 keeps growing on link 2 until L + S2 = 10 → S2 = 20/3.
Result (3.33, 6.67, 6.67). The bandwidth function reproduced the proportionally fair outcome: by choosing slopes, the operator picks the fairness notion. Fairness is a property of the utility (Exam 1 ref §3.4).

10 · Mock Quiz 2 (do it on Day 3, timed)
Rules 60 minutes (the real quiz is long, so rehearse under pressure), only your two printed cheatsheets (as on the real quiz), calculator OK. It's the last section of the iPad PDF. Score MCQs exactly like the real quiz: +1 per correct mark, −1 per wrong mark, floor 0 per question.
Then open the solutions below and write an error log: for each miss, was it a concept gap (re-read that section, redo its problems) or a careless slip (units, misread)?
The questions are deliberately a little harder than Quiz 1, since the professor said Quiz 2 would be.
✍ iPadProblem M.1 — Performance-oriented congestion control (12 pts) MCQcalc
(a) Which statements are correct?
☐ A. Allegro's default utility counts throughput only while the loss rate stays below about 5%.
☐ B. Vivace penalizes the magnitude of the RTT, as Copa does with queueing delay.
☐ C. In Vivace, a larger magnitude of the estimated utility gradient produces a larger rate change, subject to a bound.
☐ D. When Allegro's two trial pairs disagree, it moves in the direction of the pair with the larger utility difference.
☐ E. Under random non-congestive loss, PCC can keep increasing its rate because higher rates still yield higher utility, without identifying the cause of the loss.
(b) A Vivace sender at 200 Mb/s tests 190 and 210 Mb/s and measures U(190) = 150, U(210) = 146. With θ = 25, compute g, Δr, and the new rate.
Show solution
Correct: A, C, E
A ✔ — Sigmoid(L − 0.05).
B ✘ — It penalizes the gradient dRTT/dt.
C ✔ — Δr = θg, bounded.
D ✘ — It stays at r and widens ε.
E ✔ — No cause identification; just utility comparison.
(b) g = (146 − 150)/(210 − 190) = −0.2; Δr = 25·(−0.2) = −5 → 195 Mb/s.
✍ iPadProblem M.2 — QUIC scheduling and semantics (12 pts) calcMCQ
(a) All buffered at t = 0: A (2 chunks), B (1 chunk), C (2 chunks); one chunk per packet; RTT 60 ms (30 each way); ACKs immediate; no loss; cwnd starts at 1 and grows by 1 per RTT.
Give each object's display time under C-first, and under round robin in the order A, B, C.
(b) Which statements are correct?
☐ A. With HTTP/2 over one TCP connection, a lost packet of one object can delay delivery of other objects whose bytes already arrived.
☐ B. QUIC 0-RTT can be used on the first-ever connection to a server.
☐ C. A QUIC retransmission reuses the original packet number so the receiver can match it to the lost packet.
☐ D. All QUIC streams in a connection share one congestion controller.
Show solution
(a) C-first: t0 C1; t60 C2, A1; t120 A2, B1 → C 90, A 150, B 150 ms. RR (A, B, C): t0 A1; t60 B1, C1; t120 A2, C2 → B 90, A 150, C 150 ms.
Correct: A, D
A ✔ — TCP-level head-of-line blocking.
B ✘ — It needs remembered resumption state.
C ✘ — A new packet number; stream offsets identify the bytes.
D ✔ — CC is per connection.
✍ iPadProblem M.3 — Traffic engineering with classes (12 pts) calc
Three disjoint paths: P1 (10 Gb/s, 5 ms), P2 (10 Gb/s, 8 ms), P3 (20 Gb/s, 30 ms). Demands: interactive 6 Gb/s (requires path latency ≤ 10 ms) and bulk 18 Gb/s.
The controller aggregates both classes and minimizes MLU, and each path carries the classes in proportion. Loads, MLU, and interactive traffic on P3?
Find a policy-compliant allocation with the same MLU. What does the network need for it?
Interactive grows to 22 Gb/s, bulk drops to 10. Is the aggregate feasible? Is the policy feasible? What should the operator do?
Show solution
24/40 = MLU 0.6: P1 6, P2 6, P3 12. Interactive is 25% of each path → 3 Gb/s on P3 (violates the policy).
P1 + P2 carry 12: all 6 interactive + 6 bulk; P3 12 bulk → MLU 0.6. It needs traffic classification, per-class demand estimates, and per-class forwarding rules/weights.
Aggregate 32 ≤ 40: feasible (MLU 0.8). Policy: interactive may only use P1 + P2 = 20 < 22, so it is infeasible. Admit/rate-limit interactive to 20 (P1, P2 full) and put bulk on P3 (0.5), or renegotiate the policy. TE can't create low-latency capacity.
✍ iPadProblem M.4 — Mechanisms (10 pts) MCQ
Which statements are correct?
☐ A. An MPLS label is 20 bits, and the S bit marks the bottom of the label stack.
☐ B. CSPF prunes links that can't meet a trunk's bandwidth or color constraints before running shortest path.
☐ C. With Meta's version bit, the source may start tagging packets v1 as soon as it has sent the update messages to the new path's routers.
☐ D. sFlow lets switches keep exact per-flow byte counts at line rate.
☐ E. Under the hose model, a site's total egress is bounded, but how it splits across destinations may change.
☐ F. A Binding SID lets an intermediate router supply the rest of a label stack, working around a stack-depth limit.
Show solution
Correct: A, B, E, F
A ✔ — label 20 | Exp 3 | S 1 | TTL 8.
B ✔ — Prune → shortest path → install.
C ✘ — It must wait for acknowledgments that every v1 rule is installed.
D ✘ — It samples 1-in-N packets; switches keep no per-flow state.
E ✔ — That is the point of the hose.
F ✔ — Continuation at the BSID node.
✍ iPadProblem M.5 — HPRR (12 pts) calc
Parallel directed links L and R, 10 Gb/s each, with fixed background 2 Gb/s on each. Unsplittable LSPs: A = 6 and C = 3 on L, B = 4 on R.
HPRR considers A, then B, then C, repeating passes until nothing changes. A move is accepted only if the max utilization on the new route after the move is lower than the max utilization on the LSP's current route before it.
Run HPRR. Final placement and MLU.
Is it optimal among unsplittable placements? Justify.
What MLU would arbitrary splitting achieve?
Show solution
Start: L = 2 + 6 + 3 = 11 (1.1), R = 6 (0.6).

Pass 1: A → R: after R = 12 → 1.2, not < 1.1 ✗. B → L: after L = 15 → 1.5, not < 0.6 ✗. C → R: after R = 9 → 0.9 < 1.1 ✓ → L = 8 (0.8), R = 9 (0.9).

Pass 2: A → R: after 15 ✗. B → L: after 12 → 1.2, not < 0.9 ✗. C → L: after 11 → 1.1, not < 0.9 ✗. Stop: L {A}, R {B, C}, MLU 0.9.
Enumerate the subsets on L: {A} → 0.9; {B, C} → L 9, R 8 → 0.9; every other subset ≥ 1.1. So 0.9 is optimal; HPRR got lucky here (contrast 5.3).
Total 13 + 4 = 17 over 20 → 0.85.
✍ iPadProblem M.6 — Bandwidth functions and intent (14 pts) calcMCQ
(a) Two groups share one bottleneck: A(s) = min(4s, 8), B(s) = min(s, 10). Allocations at C = 6, 14, 20 Gb/s.
(b) A and B are the children of an aggregate that is allocated 9 Gb/s. Children's rates?
(c) Which statements are correct?
☐ A. If service S offers 2 Gb/s and receives 2 Gb/s, an intent of “≥ 8 Gb/s for S” is confirmed.
☐ B. Orion's reconciliation repairs drift such as rules missing after a component restart.
☐ C. TE gives BwE paths and split weights; BwE enforces budgets at hosts and reports prioritized demand to TE.
☐ D. A non-work-conserving 2:1 policy can leave capacity unused while one group still has unmet demand.
Show solution
(a) C = 6: 5s = 6 → s = 1.2 → (4.8, 1.2). C = 14: A caps at s = 2 (total 10); 8 + s = 14 → s = 6 → (8, 6). C = 20: B caps at 10 → (8, 10), 2 unused.

(b) Aggregate slope 5 until s = 2 (10 Gb/s): 5s = 9 → s = 1.8 → (7.2, 1.8).
Correct: B, C, D
A ✘ — Offered = delivered = 2 says nothing about 8 Gb/s availability.
B ✔ — Desired vs observed state, at every layer.
C ✔ — The TE ↔ BwE loop.
D ✔ — E.g., (8, 5.33) with 2.67 unused while Y wanted 6.
✍ iPadProblem M.7 — SWAN and TeaVaR (14 pts) calc
(a) Links U and L, 50 Gb/s each. F1: (U 30, L 10) → (U 10, L 30). F2: (U 10, L 30) → (U 30, L 10). Can the update happen in one step? Check a plan through the intermediate state F1 (20, 20), F2 (20, 20). What's SWAN's step bound with this 20% scratch?
(b) F1 sends (4, 4, 2) and F2 sends (1, 3, 6) on links (L1, L2, L3); demands 10 each. Compute L(x, q) for “L1 down” and “L3 down”.
(c) The only scenarios are none (0.90), L1 down (0.06), L3 down (0.04). VaR at β = 0.95 and at 0.99, and the rate per flow guaranteed in each case.
Show solution
(a) One step: U = max(30,10) + max(10,30) = 60 > 50 ✗. 0→1: U max(30,20) + max(10,20) = 50 ✓, L max(10,20) + max(30,20) = 50 ✓. 1→2: U max(20,10) + max(20,30) = 50 ✓, L 50 ✓. Valid 2-stage plan. Bound ⌈1/0.2⌉ − 1 = 4.

(b) L1 down: F1 4/10 = 0.4, F2 1/10 = 0.1 → 0.4. L3 down: F1 0.2, F2 0.6 → 0.6.

(c) CDF: 0 → 0.90, 0.4 → 0.96, 0.6 → 1.00. β = 0.95 → V = 0.4 → guarantee 10·0.6 = 6 Gb/s per flow. β = 0.99 → V = 0.6 → 4 Gb/s per flow.
✍ iPadProblem M.8 — Verification (14 pts) calcMCQ
S routes via A when S–A and A–D are up, otherwise via B. Requirement: DNS (UDP/53) from S reaches D under any single link failure.
A's ACL: permit all. B's ACL (first match): r1 UDP → deny; r2 UDP/53 → permit; r3 default → permit.
Write the verification query. Is it SAT or UNSAT? Give a witness if SAT.
Fix the configuration and re-evaluate.
How many failure scenarios are in scope, and how many pairwise clauses encode “≤ 1 failure”?
(d) To also require “DNS + other traffic on B–D ≤ 10 Gb/s”, which solver class do you need?
Show solution
(a) Allowed(e) [≤ 1 failure] ∧ M(config, h, e) ∧ h ∈ HUDP/53 ∧ ¬R(S, D, h, e). SAT: witness “S–A down (or A–D down), DNS packet, S→B selected, B's r1 denies”. r1 shadows r2.

(b) Swap r1 and r2 (or delete r1 if UDP needn't be blocked). Re-check: DNS is delivered in all 5 scenarios → UNSAT (holds within the model).

(c) 5 scenarios (none + 4 single failures); C(4,2) = 6 clauses.

(d) SMT (integer or linear arithmetic over rates); pure SAT is Boolean only.

11 · One-page formula and fact sheet (for printing, use the fuller EXAM2_CHEATSHEET.pdf instead)
── PCC (L9) ─────────────────────────────────────────────────────────────────────────────
Allegro   u = T·Sigmoid(L−0.05) − x·L,  T = x(1−L)       trials r(1±ε), ≥1 RTT each, wait 1 RTT
          pairs agree → move; disagree → stay, ε↑       STARTING(×2) → DECISION → ADJUSTING
Vivace    u = x^t − b·x·dRTT/dt − c·x·L      g ≈ (U₊−U₋)/(r₊−r₋)     Δr = θ·g (θ grows, Δr bounded)
fluid     dRTT/dt ≈ (x − C)/C     (slope, not magnitude)
PCC-β     U = g − β·q   (β = Mb/s traded per ms)   tie when β = Δg/Δq
BBR route change: min-RTT filter 10 s keeps old RTT → cwnd = 2·BW·RTT_old too small → rate = cwnd/RTT_new
                  → BW filter (10 rounds) drops → spiral until min-RTT expires
── QUIC (L10) ─────────────────────────────────────────────────────────────────────────────
response time (fresh): TCP+TLS1.3 = 3 RTT · QUIC = 2 RTT · QUIC 0-RTT = 1 RTT (needs state + server OK)
stream ID+offset = byte identity (same on resend) · packet number = transmission (new on resend)
loss: packet threshold (3 higher acked) · time threshold (9/8 RTT) · PTO = probe, doesn't declare loss
per-connection: CC, flow-control credit, crypto · per-stream: order/delivery · migration: CID + PATH_CHALLENGE
scheduler tables: t | ACKs | cwnd | sent → arrive = t + one-way delay
── TE (L11, L13) ──────────────────────────────────────────────────────────────────────────
MLU = max_e load_e/c_e      parallel disjoint paths: x_p = D·c_p/Σc,  MLU* = D/Σc
min ρ s.t. Σ_p x_kp = d_k ; Σ_{k,p∋e} x_kp ≤ ρ c_e ; x ≥ 0
mean latency = Σ x_p·lat_p / D          TE can't beat the cut: D > cut ⇒ admission / CC
staged move with headroom h: move ≤ h per step, alternate, confirm each
── MPLS / SDN (L12) ───────────────────────────────────────────────────────────────────────
MPLS shim 32 b = label 20 | Exp/TC 3 | S 1 | TTL 8  · push / swap / pop · labels local per router
CSPF: prune (bw, colors) → shortest path → install; sequential trunks are order-dependent
survive f of k parallel links: reserve D/(k−f) per link (total D·k/(k−f))
flow table: match · action (fwd/drop/modify/to-controller) · priority · counters
── Meta (L12–14, HW Q5) ───────────────────────────────────────────────────────────────────
CBB (external) / EBB (internal) · 4 planes, own controllers · sFlow 1-in-N sampling → DC×DC×class matrix
estimate = samples × N × avg size × 8 / interval  · Open/R: Spark, LinkMonitor, KvStore (eventual), Decision, FIB
classes ICP > Gold (shortest RTT + burst margin) > Silver > Bronze (K-shortest + min MLU)
strict priority + buffer carving · entitlements + host rate limits
HPRR: one LSP at a time; accept iff maxutil(new route, after) < maxutil(current route, before)
      w_e = exp[α(u′_e/u* − 1)], route cost = Σ w_e (penalizes hops); stuck states need swaps
label stack depth 3 → Binding SID continuation · version bit: install v1 everywhere, all ACK, then flip src
hose: E_i, I_j (2n numbers) vs pipe n(n−1)  ·  max i→j ≤ min(E_i, I_j)
── Google (L14–16, HW Q4) ─────────────────────────────────────────────────────────────────
intent (what) > policy (preference) > configuration (exact state) · lifecycle: interpret, check+plan, fulfill, assure, respond
Orion per domain (BGP between) · NIB pub-sub · reconcile desired↓ observed↑ · request→resolve→realize→report
B(s): slope = weight, flat = cap · pick s with Σ B_i(s) = C · freeze at bottleneck/cap · aggregate: add heights
B4: cheapest path first, spill on fill, freeze; quantize splits (K units); fix overload greedily
BwE: host (HTB) → job → cluster → global; usage ↑ budgets ↓ · waste from stale budgets = Δrate × interval
dSDN: 52% of 41 largest outages control-related; TE on every router, in-band, ingress source-routes
── Microsoft (L16–17) ─────────────────────────────────────────────────────────────────────
SWAN: interactive then background (iterative LP ≈ water-fill); edge-only config; static core labels
congestion-free: Σ_f max(x_f(i), x_f(i+1)) ≤ c_e  · scratch s ⇒ ≤ ⌈1/s⌉−1 steps · spare rule entries for tunnel changes
TeaVaR: P(q) = Π P(link state); flow loss = unmet/demand; L(x,q) = max over flows; V = β-percentile;
        min V(x); guarantee = allocation × (1−V*) β of the time · k-failure: n links of c → (n−k)·c
OneWAN: agg routers (full BGP, choose egress) / backbone (MPLS) · steer: latency filter → max-flow weights
        prune trunks < 500 Mb/s (2.5% traffic → 5× rows, 7× vars) · CLP/GLOP 5×
── Verification (L18) ─────────────────────────────────────────────────────────────────────
N(u,v,h,e) = sel ∧ up ∧ permit · hit_i = match_i ∧ ¬(earlier) · R_k backward from D, k ≤ diameter
query Allowed ∧ M ∧ ¬P → SAT = counterexample; UNSAT = holds in model only
≤1 of n links down: C(n,2) pairwise clauses (up_a ∨ up_b) · scenarios Σ_{i≤k} C(n,i)
SAT (Boolean) vs SMT (+integers, bit-vectors) · Minesweeper: config compiler, stable routing states
── Units ───────────────────────────────────────────────────────────────────────────────────
1 B = 8 b · 1 MB = 10⁶ B · Gb/s × s = Gb → ÷8 = GB · delay = bits/rate · BDP = rate × RTT
Built from the course slides, transcripts, HW2 and its model answers, and your Quiz 1. Good luck. You've got this.