Computer Networks formula sheet

59 formulas in 7 topics, each with when to use it. Each is explained in the topic notes.

HEADER EFFICIENCY

η = \frac{payload bits}{payload bits + header (and trailer) bits}

Fraction of transmitted bits that is useful data; with several layers, add up the headers of all layers that wrap the payload.

MESSAGE DELAY IN A CIRCUIT-SWITCHED NETWORK

T_{circuit} = T_{setup} + \frac{L}{R} + T_{prop,path}

L = message size in bits, R = rate of the reserved circuit in bits per second (R/n of the link rate when n circuits share it); T_setup is the set-up time given in the question (teardown ignored); T_prop,path is the sum of the propagation delays of all links. Switch processing is ignored unless stated.

Performance metrics: delay, throughput and link utilisation

All 19 formulas

TRANSMISSION DELAY

T_{t} = \frac{L}{R}

L = packet size in bits, R = link rate in bits per second. Depends on the packet and the rate, not on the length of the wire.

PROPAGATION DELAY

T_{p} = \frac{d}{v}

d = length of the link, v = propagation speed in the medium. Independent of the packet size and the link rate.

Data link layer: error detection, medium access control and Ethernet

All 8 formulas

DETECTION WITH MINIMUM DISTANCE D

errors always detected = d - 1

A code of minimum distance d detects every pattern of up to d - 1 bit errors.

CORRECTION WITH MINIMUM DISTANCE D

errors always corrected = ⌊ \frac{d - 1}{2} ⌋

Decoding to the nearest codeword corrects up to this many bit errors.

Routing: distance vector and link state

All 3 formulas

BELLMAN-FORD (DISTANCE-VECTOR) UPDATE

D_{x} (y) = v \in N (x) min {c (x, v) + D_{v} (y)}

For y not equal to x (D_x(x) = 0). x is the router, N(x) its neighbours, c(x,v) the (positive) link cost to neighbour v, D_v(y) the cost to destination y that v advertised. The neighbour v giving the minimum is the next hop.

DIJKSTRA RELAXATION

d (v) = min {d (v), d (u) + c (u, v)}

Applied to every neighbour v of the node u just made permanent (only tentative neighbours can improve). Requires all link costs to be non-negative.

IPv4: addressing, CIDR, fragmentation and NAT

All 9 formulas

ADDRESSES IN A BLOCK

addresses = 2^{32 - p}

For a block with prefix length p, counting the network and broadcast addresses.

USABLE HOSTS IN A BLOCK

hosts = 2^{32 - p} - 2

For a block with prefix length p. The two subtracted addresses are the network and broadcast addresses. Valid for p up to 30.

TCP: flow control, congestion control and sockets

All 8 formulas

ACKNOWLEDGEMENT NUMBER

ack = seq + L (+ 1 if the segment carries SYN or FIN)

For a segment that arrives in order, with sequence number seq and L data bytes. Because the ACK is cumulative, an out-of-order segment brings back the previous ack number again (a duplicate ACK).

SENDER'S EFFECTIVE WINDOW

usable window = min (rwnd, cwnd)

rwnd is the receiver's flow-control limit; cwnd is the congestion window from the next section.

Application layer: DNS and HTTP

All 6 formulas

TIME FOR AN ITERATIVE RESOLUTION BY THE RESOLVER

T_{DNS} = R_{host} + i \sum R_{i}

R_host is the RTT from host to local resolver and R_i the RTT from the resolver to each server it queries in turn. Assumes processing time is negligible and each query and its reply is one UDP exchange costing one RTT (no losses or retransmissions). With a cached TLD referral, drop the root term; with a cached final answer, only R_host remains.

AVERAGE ACCESS TIME WITH A WEB CACHE

T_{avg} = h T_{hit} + (1 - h) T_{miss}

h is the hit ratio (fraction of requests the cache answers), T_hit the time to get an object from the cache and T_miss the time to get it through the cache from the origin server. Assumes every request takes one of these two times.