Formula sheet

Every formula from every topic. Type to filter.

🧱 Layering, Delays & Switching

Transmission delay
Tt = L / B
Propagation delay
Tp = d / v
One packet over k store-and-forward links
k · (L/B) + sum of Tp
n packets over k links (equal sizes)
(k + n − 1) · (L/B) + sum of Tp
Bandwidth-delay product
B × RTT (bits in the pipe)
Nyquist capacity
C = 2 H log2 V
Shannon capacity
C = H log2 (1 + S/N), S/N = 10^(dB/10)

🧮 Framing & Error Control

Bit stuffing
insert a 0 after every 5 consecutive 1s in the data
CRC frame length
message + r bits, r = degree of the generator
Hamming distance d
detect d − 1, correct ⌊(d − 1)/2⌋ errors
Hamming check bits
2^r ≥ m + r + 1
12-bit Hamming (8 data bits)
r = 4, check bits at positions 1, 2, 4, 8
Internet checksum
~(sum of 16-bit words with end-around carry)

🪟 Flow Control & Sliding Window

a
a = Tp / Tt
Stop-and-wait efficiency
η = Tt / (Tt + 2Tp) = 1 / (1 + 2a)
With ack transmission
cycle = Tt + 2Tp + Tack
Sliding window efficiency
η = min(1, N · Tt / (Tt + 2Tp))
Window for full utilisation
N = 1 + 2a
Sequence numbers
GBN: N + 1 ; SR: 2N ; stop-and-wait: 2
Throughput
η × bandwidth

🔌 Medium Access & LANs

Pure ALOHA
S = G e^(−2G), max 1/(2e) ≈ 0.184 at G = 0.5
Slotted ALOHA
S = G e^(−G), max 1/e ≈ 0.368 at G = 1
CSMA/CD condition
Tt ≥ 2 Tp, so min frame = 2 Tp × B
Max cable length
d = (L/B)/2 × v
Switches to join n hosts (k ports each)
tree of switches: ⌈(n − 2)/(k − 2)⌉
Token ring: wait before assuming token lost
ring Tp + (stations × token holding time)

🌐 IP Addressing & Network Layer

Hosts in a /n block
2^(32 − n) − 2 usable
Network address
IP AND mask
Broadcast address
network OR (NOT mask)
Prefix for h hosts
smallest 32 − b with 2^b − 2 ≥ h
Fragment payload
floor((MTU − hdr) / 8) × 8
Fragment offset
bytes before this fragment / 8
Classful network counts
A: 2^7, B: 2^14, C: 2^21
ARP request
dest MAC = FF:FF:FF:FF:FF:FF (broadcast)

🧭 Routing & Congestion Control

Bellman-Ford update
D_x(y) = min over neighbours k of [ c(x,k) + D_k(y) ]
Convergence
at most n − 1 rounds of exchanges
Dijkstra with a heap
O((V + E) log V)
RIP
hop count, infinity = 16, UDP port 520
Token bucket burst length
t = C / (M − r)
Token bucket total time
t + (D − M·t) / r

🚚 Transport Layer: UDP & TCP

TCP/UDP port
16 bits (0 to 65535)
Handshake
SYN(x) → SYN+ACK(y, x+1) → ACK(y+1)
cwnd in slow start
doubles each RTT until ssthresh
After timeout
ssthresh = cwnd/2, cwnd = 1 MSS
Throughput
min(cwnd, rwnd) / RTT
Sequence bits for no wrap in MSL
2^b ≥ B(bytes/s) × MSL
Wrap time of 32-bit seq at rate B
2^32 × 8 / B seconds

📬 Application Layer: DNS, HTTP, Email

Iterative DNS lookup
root, TLD, ... , authoritative: 1 query-response per level
Non-persistent HTTP, n objects
2 RTT × (1 + n) (sequential)
Persistent without pipelining
2 RTT (first) + 1 RTT × n
Persistent with pipelining
2 RTT + 1 RTT for all objects
Parallel connections
rounds = ceil(objects / connections)
Ports
HTTP 80, HTTPS 443, DNS 53, SMTP 25, POP3 110, IMAP 143, FTP 21/20

🔐 Network Security

RSA keys
n = pq, φ = (p−1)(q−1), e·d ≡ 1 (mod φ)
RSA encrypt / decrypt
c = m^e mod n ; m = c^d mod n
Factor n from φ
p + q = n − φ + 1, then solve the quadratic
Signature
sign = D_senderPrivate(H(m)), verify with the sender public key