The whole Computer Networks formula sheet, to print

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

Layering and switching: circuit, packet and virtual circuit

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.

ONE PACKET OVER K LINKS (STORE-AND-FORWARD)

T = k \cdot \frac{L}{R} + i = 1 \sum k \frac{d _{i}}{s}

The whole packet is transmitted again on every link, so transmission delay is counted k times; all links at rate R, no queueing or processing. If the links have different propagation delays, add the delays given.

A MESSAGE SENT AS N EQUAL PACKETS OVER K LINKS

T = (k + n - 1) \cdot \frac{p}{R} + i = 1 \sum k \frac{d _{i}}{s}

Each packet has p bits including its header, all links at rate R, no queueing, and the packets go back to back. The first packet needs k transmission times; each later packet arrives one transmission time after the one before it (pipelining). T is the time from the first bit leaving the source until the last bit of the last packet reaches the destination.

N EQUAL PACKETS OVER LINKS OF DIFFERENT RATES

T = i = 1 \sum k \frac{p}{R _{i}} + (n - 1) \frac{p}{R _{m i n}} + i = 1 \sum k \frac{d _{i}}{s}

R_i = rate of link i, R_min = rate of the slowest link (the bottleneck). The first packet crosses every link once; the later packets leave the bottleneck one p/R_min apart and keep that spacing. With all rates equal this reduces to the previous formula. No other traffic, no queueing apart from waiting for the packet ahead.

PAYLOAD SIZE THAT MINIMISES TOTAL DELAY

x_{opt} = \frac{M h}{k - 1}

M = message bits, h = header bits per packet, k >= 2 links of equal rate, ignoring the rounding of M/x to a whole number. Derivation: delay times R is (k-1+M/x)(x+h) = (k-1)x + (k-1)h + M + Mh/x; setting its derivative with respect to x to zero gives (k-1) = Mh/x^2. Propagation does not depend on x.

Performance metrics: delay, throughput and link utilisation

Read the notes

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.

ROUND-TRIP TIME (NEGLIGIBLE ACK SIZE)

RTT = 2 T_{p}

For a short probe or acknowledgement whose transmission delay is negligible. If transmission delays matter, add them explicitly.

ONE PACKET OVER N LINKS, STORE-AND-FORWARD

T_{end-to-end} = i = 1 \sum N (\frac{L}{R _{i}} + T_{p, i})

Each router receives the whole packet before forwarding it. Queuing and processing delays are zero unless given. With equal links this is $N (L / R + T_{p})$ .

P PACKETS BACK TO BACK OVER N EQUAL LINKS

T = (N + P - 1) \frac{L}{R} + N T_{p}

All packets have the same size L, are sent without gaps, and no queuing occurs other than waiting behind earlier packets. The first packet needs N transmission times; each later packet finishes one transmission time after the one before.

THROUGHPUT OF A PATH

Throughput = min (R_{1}, R_{2}, \dots, R_{N})

Steady transfer of a long stream over links in series with no other traffic, and a sender window large enough not to be the limit. Delays do not change this rate; they only shift when the stream starts and ends.

FILE OF F BITS IN PACKETS OF L BITS, LINKS IN SERIES

T = \frac{F}{R _{b}} + i \neq = b \sum \frac{L}{R _{i}} + i = 1 \sum N T_{p, i}

Store-and-forward; $R_{b} = min R_{i}$ is the bottleneck rate (link $b$ ); F is a whole number of packets of L bits sent back to back; no other traffic, no processing delay. Every link other than the bottleneck adds one packet transmission time. With equal links and $F = P L$ this is $(N + P - 1) L / R + N T_{p}$ . For a very large F the first term dominates.

BANDWIDTH-DELAY PRODUCT

BDP = R \times T_{p}

Number of bits that fill the link from one end to the other (bits in flight in one direction). Using $R \times RTT$ gives the bits that can be in flight during one round trip.

WINDOW-LIMITED THROUGHPUT

Throughput = min (R, \frac{W}{T _{cycle}})

W = sender window in bits (a TCP window is given in bytes, so multiply by 8). $T_{cycle}$ = time from sending the first bit of a window to receiving its acknowledgement: $T_{t} + 2 T_{p}$ for frames of transmission time $T_{t}$ , or simply RTT when transmission time is negligible. With $W = N L$ this gives $U = N / (1 + 2 a)$ , as below.

STOP-AND-WAIT UTILISATION

U = \frac{T _{t}}{T _{t} + 2 T _{p}} = \frac{1}{1 + 2 a}

No errors, acknowledgement transmission time and processing time negligible. If the ACK has a non-negligible transmission time $T_{a c k}$ , the cycle is $T_{t} + 2 T_{p} + T_{a c k}$ .

EFFECTIVE THROUGHPUT

Throughput = U \times R

R = link rate. Equivalently, one frame of $L$ bits is delivered per cycle: $L / (T_{t} + 2 T_{p})$ .

STOP-AND-WAIT WITH FRAME LOSS

U = \frac{1 - p}{1 + 2 a}

Each frame is lost independently with probability p, acknowledgements are never lost, and every failed attempt costs one full cycle $T_{t} + 2 T_{p}$ (timeout equal to the cycle). The expected number of transmissions per frame is $1/ (1 - p)$ .

USEFUL THROUGHPUT WITH HEADER OVERHEAD

Useful throughput = U \times R \times \frac{L - H}{L}

L = whole frame in bits including the header, H = header bits. Use this only when the question asks for data (payload) throughput; otherwise headers count as transmitted bits.

SLIDING-WINDOW UTILISATION

U = min (1, \frac{N}{1 + 2 a})

N = sender window in frames, $a = T_{p} / T_{t}$ , no errors, ACK transmission negligible. Applies to Go-Back-N and Selective Repeat alike when there are no losses. $N = 1$ gives stop-and-wait.

WINDOW NEEDED TO KEEP THE LINK BUSY

N_{m i n} = ⌈ 1 + 2 a ⌉

Smallest window giving $U = 1$ . Equivalently, the window must cover one full cycle: $N T_{t} \geq T_{t} + 2 T_{p}$ .

GENERAL RULE FOR SEQUENCE NUMBERS

W_{s} + W_{r} \leq 2^{k}

$W_{s}$ = sender window, $W_{r}$ = receiver window, both in frames; k = bits in the sequence number. Go-Back-N has $W_{r} = 1$ , giving $W_{s} \leq 2^{k} - 1$ ; Selective Repeat with $W_{s} = W_{r}$ gives $W_{s} \leq 2^{k - 1}$ .

MAXIMUM WINDOW, GO-BACK-N

N_{m a x}^{GB N} = 2^{k} - 1

k = bits in the sequence number. A window of $2^{k}$ would make a whole new window look like a retransmission of the old one.

MAXIMUM WINDOW, SELECTIVE REPEAT

N_{m a x}^{S R} = 2^{k - 1}

Sender and receiver windows are equal; the two windows together must not exceed the $2^{k}$ numbers.

SEQUENCE BITS FOR A GIVEN WINDOW

k_{GB N} = ⌈ lo g_{2} (N + 1)⌉, k_{S R} = ⌈ lo g_{2} (2 N)⌉

N = sender window size in frames. Use $N_{m i n}$ from the utilisation formula when the question asks for the field that keeps the link fully busy.

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

Read the notes

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.

CRC FRAME LENGTH

n = m + r, r = de g G (x)

m data bits plus an r-bit remainder give an n-bit frame; the generator has r + 1 bits.

NUMBER OF HAMMING CHECK BITS

2^{r} \geq m + r + 1

The smallest r for which the syndrome can point to any single-bit error in an (m + r)-bit codeword.

TRANSMISSION TIME AND THE RATIO A

T_{t} = \frac{L}{B}, a = \frac{T _{p}}{T _{t}}

L = frame length in bits, B = bandwidth in bits per second, T_p = one-way propagation delay. A small a means a station hears another's frame early in its transmission, so carrier sensing works well.

PURE ALOHA THROUGHPUT

S = G e^{- 2 G}

S is the fraction of time that carries a successful frame; the maximum is about 18.4% at G = 0.5.

SLOTTED ALOHA THROUGHPUT

S = G e^{- G}

The maximum is about 36.8% at G = 1.

MINIMUM FRAME SIZE FOR CSMA/CD

L \geq 2 T_{p} B

L = frame length in bits, T_p = one-way propagation delay (distance divided by propagation speed), B = bandwidth in bits per second. Put another way, the transmission time must be at least 2 T_p.

Routing: distance vector and link state

Read the notes

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.

DIJKSTRA RUNNING TIME

T = O (n^{2}) (array), T = O ((n + e) lo g n) (binary heap)

n routers, e links; a straightforward implementation scans for the minimum, a heap makes extraction logarithmic.

IPv4: addressing, CIDR, fragmentation and NAT

Read the notes

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.

NUMBER OF SUBNETS (CIDR CONVENTION)

subnets = 2^{s}

s is the number of host bits borrowed (new prefix length minus old prefix length). All-zeros and all-ones subnets are allowed.

NUMBER OF SUBNETS (OLDER CLASSFUL CONVENTION)

subnets = 2^{s} - 2

Only when the question excludes the all-zeros and all-ones subnet numbers.

BLOCK SIZE IN THE INTERESTING OCTET

block size = 256 - (mask value in that octet)

The interesting octet is the one where the mask is neither 255 nor 0. Subnets start at multiples of the block size in that octet. If p is a multiple of 8 there is no such octet: the host part is whole octets.

MAXIMUM DATA PER FRAGMENT

D_{m a x} = 8 ⌊ \frac{MTU - H}{8} ⌋

H is the header length in bytes (20 without options). Data in every fragment except the last must be a multiple of 8 bytes.

NUMBER OF FRAGMENTS

n = ⌈ \frac{L - H}{D _{m a x}} ⌉

L is the original total length in bytes, H the header length. Assumes a single fragmentation at one link and the same header length H in every fragment.

FRAGMENT OFFSET FIELD

offset = \frac{bytes of data before this fragment}{8}

Measured from the start of the original datagram's data. MF = 1 for every fragment except the last.

DATA BYTES CARRIED BY A FRAGMENT

first = 8 \times offset, last = 8 \times offset + (total length - 4 \times HLEN) - 1

Byte positions in the original data, numbered from 0. Total length is in bytes; HLEN is in 4-byte words.

TCP: flow control, congestion control and sockets

Read the notes

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.

MAXIMUM THROUGHPUT WITH WINDOW W

Throughput = min (\frac{W}{RTT}, link rate)

W is in bits when the rate is in bits per second. Assumes no loss, header overhead ignored and ACK transmission time negligible. When the window equals the bandwidth-delay product, the pipe is exactly full. If a question defines one cycle as RTT plus the transmission time of the window (or of a segment), use that cycle in place of RTT.

LINK UTILISATION (SLIDING WINDOW, CONTINUOUS)

Utilisation = min (1, \frac{W}{link rate \times RTT})

Link rate times RTT is the bandwidth-delay product. Keep it in the same unit as W (bits or bytes).

SEQUENCE-NUMBER WRAP-AROUND TIME

T_{wrap} = \frac{2 ^{32} \times 8}{rate in bits per second} seconds

The sequence field is 32 bits and counts bytes, so $2^{32}$ bytes pass before numbers repeat, if the sender sends continuously at the full rate.

MINIMUM SEQUENCE-NUMBER BITS

n_{m i n} = ⌈ lo g_{2} (rate in bytes per second \times lifetime in seconds) ⌉

The condition is that sequence numbers (counting bytes) must not wrap around while a segment can still be alive in the network. The lifetime is the maximum segment lifetime given in the question. Convert the rate from bits to bytes per second by dividing by 8.

RETRANSMISSION TIMEOUT (STANDARD ESTIMATOR)

RTO = SRTT + 4 \times RTTVAR

SRTT $\leftarrow (1 - \frac{1}{8}) SRTT + \frac{1}{8} R$ and RTTVAR $\leftarrow (1 - \frac{1}{4}) RTTVAR + \frac{1}{4} ∣ R - SRTT ∣$ , where R is a new RTT sample. RTTVAR is updated first, using the old SRTT. On the first sample, SRTT = R and RTTVAR = R/2, so RTO = 3R.

MULTIPLICATIVE DECREASE

ssthresh_{new} = max (⌊ \frac{cwnd}{2} ⌋, 2) MSS

cwnd is the window at the moment the loss is detected. Unless the question says otherwise, take cwnd/2 in whole MSS (rounded down for an odd window).

Application layer: DNS and HTTP

Read the notes

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.

NON-PERSISTENT, SERIAL

T = 2 (n + 1) RTT

Each of the n+1 files costs 1 RTT for the handshake and 1 RTT for request and response.

NON-PERSISTENT, M PARALLEL CONNECTIONS

T = 2 RTT + 2 ⌈ \frac{n}{m} ⌉ RTT

Base file fetched alone first; objects then go in batches of m. Assumes equal object times and negligible transmission time.

PERSISTENT WITHOUT PIPELINING

T = (n + 2) RTT

One handshake, one RTT for the base file, one RTT for each object.

PERSISTENT WITH PIPELINING

T = 3 RTT

One handshake, one RTT for the base file, one RTT for all objects together (requests sent without waiting). Transmission time is ignored.