G07: Network design, routing, and queueing

Prerequisites and observable goals#

The central question: where does a request wait?#

A request crosses application code, transport, addressing, links, queues, and remote service work. “The network is slow” does not identify the layer or the delay. Draw an end-to-end path and label each queue, trust boundary, timeout, and message size. Then state which parts you observed rather than treating a local simulation as a network deployment.

A useful decomposition for one message is serialization delay plus propagation delay plus queueing and processing delays. Serialization of $L$ bits over a link of rate $R$ bits/s takes $L/R$ seconds. Propagation depends on distance and medium; it does not become shorter because the link can transmit more bits each second. Throughput, goodput, latency, and jitter answer different questions. Goodput excludes protocol overhead and retransmitted data. Jitter describes variation in delay, with the precise statistic needing a definition.

Address blocks and longest-prefix routing#

IPv4 uses 32 address bits. A prefix /$p$ fixes the first $p$ bits and leaves $32-p$ bits for addresses in the block. A /24 contains $2^8=256$ addresses. Conventional subnet host-allocation rules may reserve particular addresses, but routing matches the whole address block. Do not confuse total block size with a promised count of assignable hosts under every deployment rule.

A route table can contain overlapping blocks. With routes 0.0.0.0/0 to an edge gateway, 10.0.0.0/8 to a private router, and 10.2.0.0/16 to a lab router, destination 10.2.1.8 matches all three. The longest matching prefix, /16, wins. This favors the most specific available rule, not the most recently listed rule. Equal-prefix policies, administrative preferences, and routing protocols require additional mechanisms; the lab rejects duplicate prefixes instead of silently inventing a tie-break.

The offline implementation parses addresses using the standard library and rejects mixed IP families in one lookup. IPv6 follows the same longest-prefix idea over a different address width and notation, but IPv4-specific broadcast assumptions should not be copied into IPv6. The lab is not a routing daemon and sends no packets. [G-IPADDRESS]

Worked delay and capacity budgets#

A 1,500-byte message contains 12,000 bits. At 100 megabits/s, serialization is $12000/10^8=.00012$ s, or .12 ms. If propagation is 2 ms one way and there is no queueing or processing, one-way completion is approximately 2.12 ms for that message under this simple model. Doubling bandwidth halves serialization to .06 ms, not the 2 ms propagation term.

The bandwidth-delay product is $R\cdot\mathrm{RTT}$. At 100 Mb/s and round-trip time .02 s, it is 2,000,000 bits or 250,000 bytes. A sender may need roughly that much in flight to fill the path under the model. This is not automatically the correct socket buffer size: congestion control, receive windows, packet overhead, loss, and implementation limits matter.

TCP provides a reliable ordered byte stream, not application message boundaries. A successful read can return a prefix of a logical message, and multiple writes can be coalesced. Application framing must be bounded and explicit. Timeouts and connection resets can still leave a remote request outcome unknown. TLS adds authentication/confidentiality/integrity properties under correct certificate and key handling; encryption does not define your business authorization rules. [G-TCP]

Queueing assumptions before queueing formulas#

Little’s law relates long-run averages in a stable system: $L=\lambda W$, where $L$ is average number in the system, $\lambda$ the appropriate throughput, and $W$ mean time in the system. Boundaries and populations must match. Counting only waiting jobs while using total service-plus-wait time mixes definitions. In a dropping queue, offered arrival rate and admitted throughput are different.

For an M/M/1 model with Poisson arrivals of rate $\lambda$, independent exponential service of rate $\mu$, one server, an unlimited waiting room, and $\lambda<\mu$, utilization is $\rho=\lambda/\mu$ and mean system time is $W=1/(\mu-\lambda)$. The distributional assumptions are substantial. At $\lambda=80$ jobs/s and $\mu=100$, $W=.05$ s and $L=4$. At $\lambda=95$, $W=.2$ s and $L=19$. Raising utilization from .8 to .95 quadruples mean time in this model. This motivates headroom; it does not predict every tail latency distribution from utilization alone.

The lab uses deterministic service and a finite capacity, so it is not an M/M/1 simulator. It traces exact provided arrivals instead. Capacity counts both the active job and waiting jobs. A completion at exactly an arrival time occurs first. These definitions remove ambiguity before implementation.

An exact finite trace#

Arrivals are $0,.1,.2,1$ seconds; service takes one second; capacity is two. At time 0, accept job A, start at 0, finish at 1. At .1, accept B and schedule it from 1 to 2. At .2, two jobs are already in the system, so reject C. At 1, complete A before processing D’s arrival; B is active until 2, so accept D and schedule it from 2 to 3. The accepted jobs have response times 1, 1.9, and 2 seconds. Rejected C has no completed response latency in this model and must be counted separately, not silently omitted from a success-rate report.

Solid segments are service, dashed segments waiting. The horizontal axis has real model time; vertical rows identify jobs, not simultaneous servers. This picture explains why a finite buffer can reject work even when service itself remains correct.

Design under faults and trust boundaries#

For a small service, separate public ingress from private data access and administrative control. Specify allowed communication directions, authenticated identities, and failure behavior. A load balancer can distribute traffic but can also be a shared failure point. DNS caching can retain an old destination after a change. Retry storms can increase offered load during an outage. A deployment diagram should show these dependencies instead of simply drawing three identical boxes and calling them independent.

Use bounded request sizes, bounded work queues, admission control, connection/read deadlines, and explicit failure responses. Backpressure asks an upstream producer to slow down or stop; dropping and retrying without a bound may amplify load instead. Validate protocols with malformed/truncated inputs on local or authorized systems only. Security tests in this book are defensive contract checks, not scanning unrelated networks.

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

Smallest useful hints#

For .02, RTT is .03 seconds and a byte is eight bits. For .04, arrivals retain their input order at the same timestamp. For .05, parsing must retain an incomplete prefix between reads rather than discard it.

Complete solutions: G07#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""G07: offline prefix lookup and a one-server finite-capacity FIFO trace."""
from collections import deque
import ipaddress
import math


def route(address, routes):
    address = ipaddress.ip_address(address)
    parsed, seen = [], set()
    for prefix, destination in routes:
        network = ipaddress.ip_network(prefix,strict=True)
        if network in seen:
            raise ValueError("duplicate prefix")
        seen.add(network)
        if network.version != address.version:
            raise ValueError("mixed address families are outside this lab contract")
        parsed.append((network,destination))
    matches = [(n,d) for n,d in parsed if address in n]
    if not matches:
        return None
    network,destination = max(matches,key=lambda item:item[0].prefixlen)
    return str(network),destination


def queue_trace(arrivals, service=1., capacity=3):
    arrivals = list(arrivals)
    if len(arrivals) > 100000 or any(not math.isfinite(t) or t < 0 for t in arrivals):
        raise ValueError("bounded finite nonnegative arrival times required")
    if any(b < a for a,b in zip(arrivals,arrivals[1:])):
        raise ValueError("arrivals must be nondecreasing")
    if not math.isfinite(service) or service <= 0:
        raise ValueError("positive finite service duration required")
    if type(capacity) is not int or not 1 <= capacity <= 100000:
        raise ValueError("capacity counts waiting plus in-service jobs")
    finishes, records = deque(), []
    for job,arrival in enumerate(arrivals):
        while finishes and finishes[0] <= arrival:
            finishes.popleft()  # completions precede arrivals at the same time
        if len(finishes) >= capacity:
            records.append({"job":job,"arrival":arrival,"accepted":False,
                            "start":None,"finish":None})
            continue
        start = max(arrival,finishes[-1] if finishes else arrival)
        finish = start+service
        if not math.isfinite(finish) or finish <= start:
            raise ValueError("service endpoint overflow or no represented progress")
        finishes.append(finish)
        records.append({"job":job,"arrival":arrival,"accepted":True,
                        "start":start,"finish":finish})
    return records


if __name__ == "__main__":
    print(route("10.2.1.8",[("0.0.0.0/0","default"),("10.2.0.0/16","local")]))
    print(queue_trace([0,0,0,4]))

Readiness and continuation#

Explain the difference between offered load and admitted throughput, then compute a trace where a completion and arrival coincide. Continue with routing protocols, congestion control, network namespaces, TLS certificate operations, and measured authorized deployment. The lab prepares reasoning about those systems but does not configure a production network. [G-TCP][G-IPADDRESS]