Networks

The big picture and the words we need

Before the layers, let us agree on a few words. They come back in every section, so it is worth meeting them once, slowly.

Networks come in sizes. A LAN (local area network) covers a room, a house or a school. A WAN (wide area network) covers cities or countries. The Internet is not one network: it is millions of networks joined together by routers, all speaking the same family of protocols, called TCP/IP.

Layers: the OSI and TCP/IP reference models

Imagine you want to send a birthday card to a friend in another country. You write it, a clerk puts it in an envelope with an address, a truck takes it to the airport, a plane flies it, and another postman delivers it. Nobody does the whole job, and each helper only needs to know their own part. Networks work the same way, and each helper is called a layer.

A layer offers a service to the layer above it: a promise of what it can do, like 'I will carry your packet to the next machine'. To keep that promise, the layer talks to the same layer on the other machine using a protocol: the rules and the message formats they agree on. The service says what is offered. The protocol says how the two sides do it. Because they are separate, you can change the protocol of one layer (for example, use a different cable) without touching the layers around it.

The OSI model has seven layers. The TCP/IP model has four: link, internet, transport and application. The two OSI layers in the middle, session and presentation, were seldom useful in practice, so in TCP/IP their jobs are left to each application. A classic summary: OSI is a good model whose protocols never caught on, while TCP/IP has protocols that conquered the world but a model that describes only itself well (it does not clearly separate service, interface and protocol).

Encapsulation: envelopes inside envelopes

When a message goes down the stack, each layer puts the thing it received inside its own envelope, called a header (and sometimes also a trailer at the end). At the destination the opposite happens: each layer opens its own envelope, reads it and hands what is inside to the layer above. This is encapsulation. A layer never needs to understand what is inside the envelope it carries.

Sender                              Receiver

[ Message ]                         [ Message ]
   |  + app header                     ^  - removed
[AH|Message]  (application)
   |  + transport header (segment)     ^
[TH|AH|Message]
   |  + network header (packet)        ^
[NH|TH|AH|Message]
   |  + link header/trailer (frame)    ^
[LH|NH|TH|AH|Message|LT] ---bits---> wire

Headers cost space. The overhead is the part of the sent bytes that is headers: total headers divided by total bytes sent. If an application writes 400 bytes and four layers each add 50 bytes of header, the overhead is 200 / 600, which is one third. The smaller the message, the heavier the headers weigh.

Circuit switching and packet switching

• Circuit switching (old telephone): before talking, a path is reserved from end to end. Nobody else can use that capacity, even when you are silent. Good quality, but wasteful for traffic that comes in bursts.
• Packet switching (the Internet): the message is cut into packets that share the links. Each router receives the whole packet, keeps it, and then sends it on (store-and-forward). Efficient when traffic is bursty. The price is variable delay, because packets may wait in a queue, and packets may be lost when the queue is full.

How long does a packet take?

The delay on a link has two separate parts. Transmission time is how long it takes to push all the bits onto the wire: packet size in bits divided by the link rate. Propagation delay is how long one bit takes to travel along the wire: distance divided by the speed of the signal (about 200,000 km/s in a cable or fibre). The last bit arrives after the sum of both. Convention used in the quiz: both are counted from the moment the first bit starts to leave the sender.

packet = 500 bytes = 4000 bits, link = 2 Mbps, distance = 3000 km
transmission = 4000 bits / 2,000,000 bps = 0.002 s = 2 ms
propagation  = 3000 km / 200,000 km/s    = 0.015 s = 15 ms
last bit arrives after 2 + 15 = 17 ms

The physical layer: turning bits into signals

The bottom floor has a simple job: take bits and make something travel over a medium, so the other side can read them again. It does not know what the bits mean. It only cares about voltages, light and radio waves.

Copper carries electricity, so lightning, motors and nearby cables add noise, and the signal gets weaker (attenuation) especially at high frequencies. Fibre carries light, so electrical noise cannot disturb it. That is why long and fast links use fibre.

Baud and bit rate

The symbol rate, measured in baud, is how many times per second the signal changes. If each symbol can have V different states, one symbol carries log₂ V bits. So bit rate = baud × log₂ V. A signal with 8 states and 1,000 changes per second carries 3 bits per symbol, which is 3,000 bits per second. Baud and bits per second are the same only when there are two states.

Directions of a link

• Simplex: one direction only (like a TV broadcast).
• Half-duplex: both directions, but taking turns (like a walkie-talkie: say 'over').
• Full-duplex: both directions at once (like a phone call). Modern switched Ethernet is full-duplex; the old shared cable was half-duplex.

How fast can a channel go?

Two famous limits answer this. Bandwidth here means the width of the band of frequencies the channel lets through, measured in hertz (Hz). Nyquist is for a perfect channel without noise: you can send at most 2B symbols per second, so with V levels the maximum is 2B log₂ V bits per second. Shannon is for a real channel with noise: the maximum is B log₂(1 + S/N), whatever the number of levels. S/N is the signal power divided by the noise power. It is often given in decibels: dB = 10 log₁₀(S/N), so 10 dB is 10 times, 20 dB is 100 times and 30 dB is 1,000 times.

Nyquist: B = 4 kHz, V = 4 levels
  max = 2 * 4000 * log2(4) = 2 * 4000 * 2 = 16,000 bps

Shannon: B = 2 kHz, 20 dB -> S/N = 100
  max = 2000 * log2(1 + 100) = 2000 * 6.66 = about 13,300 bps

Real channel with both limits: the smaller value wins (13,300)

Sending bits: coding and clocks

The receiver has to know where one bit ends and the next starts, but there is no separate wire with the sender's clock. Manchester encoding puts the clock inside the data: every bit has a transition in the middle of its time slot, and the direction of that transition (up or down) tells whether the bit is 0 or 1. Which direction means which depends on the standard. The price is that the signal changes twice as often, so it needs about twice the bandwidth. Classic Ethernet used it. The simple way, NRZ, uses one voltage for 1 and another for 0, so a long run of equal bits looks like a flat line and the clock is lost.

bits:        1 1 1 1 1 0
NRZ:         ---------_   (one flat level for 5 bits:
                           where does each bit start?)
Manchester:  a change in the middle of EVERY bit

Sharing one channel: multiplexing

• FDM (frequency division): each signal gets its own band of frequencies, like radio stations on different dials.
• TDM (time division): the signals take turns, each in its own time slot.
• CDM / CDMA (code division): everybody talks at once on the same band, but each station multiplies its bits by its own code (a chip sequence). Codes are orthogonal: their inner product is zero.

CDMA is like a party where people speak different languages: you tune your ear to your own language and the others sound like background noise. In numbers: take chips A = (+1 +1 −1 −1) and B = (+1 −1 +1 −1). Their product, element by element, is +1 −1 −1 +1, which sums to 0, so they are orthogonal. A sends bit 1 (sends A) while B sends bit 0 (sends −B). The channel adds them: (0, +2, −2, 0). To listen to A, multiply by A and divide by 4: (0 + 2 + 2 + 0)/4 = +1, bit 1. To listen to B: (0 − 2 − 2 + 0)/4 = −1, bit 0. A result of +1 means bit 1, −1 means bit 0, and 0 means that station was silent.

PCM (pulse code modulation) turns voice into bits. A telephone voice needs about 4 kHz, so it is sampled at twice that, 8,000 times per second (one every 125 µs). With 8 bits per sample, the rate is 8,000 × 8 = 64,000 bps, the classic 64 kbps voice channel.

The data link layer: framing, errors and the sliding window

The physical layer sends a stream of bits. The data link layer turns the stream into frames (small packages of bits) that travel between two machines directly connected by one link. It has three jobs: mark where each frame starts and ends, discover (or fix) damaged bits, and avoid drowning a slow receiver.

Framing: where does a frame end?

• Byte count: the header says how many bytes follow. Simple, but one wrong count ruins everything after it.
• Flag byte with byte stuffing: a special byte (the flag) marks the start and end. If the same value appears inside the data, the sender puts an escape byte before it (and before any escape byte in the data). The receiver removes the escape bytes, so the data arrives unchanged.
• Flag bits with bit stuffing: the flag is the pattern 01111110. Whenever the sender sees five 1s in a row in the data, it inserts a 0. The receiver does the reverse: after five 1s, a 0 is removed. So six 1s in a row can only be the flag.

data to send:   0 1 1 1 1 1 1 0 1
after five 1s a 0 is inserted:
stuffed data:   0 1 1 1 1 1 [0] 1 0 1
frame: 01111110 0111110101 01111110   (flag, data, flag)

Finding errors

Noise flips some bits. To notice it, we send extra check bits, called redundancy. A parity bit is the simplest: choose it so that the number of 1s in the block is even (or odd, by agreement). Data 1011 has three 1s, so the even-parity bit is 1. If one bit flips, the count becomes odd and the receiver knows. But if two bits flip, the count is even again and the error goes unseen. A single parity bit detects any odd number of flipped bits and misses even numbers.

The strength of a code is measured by its Hamming distance: the smallest number of bit positions in which two valid codewords differ. To detect e errors you need distance e + 1. To correct e errors you need distance 2e + 1 (the damaged word must still be closer to the right one than to any other). Distance 5 detects 4 errors or corrects 2. Parity has distance 2: detects 1, corrects none.

A Hamming code corrects one flipped bit. The check bits sit at positions 1, 2, 4, 8, ... and each one checks the positions whose binary number contains that power of two. After a failure, adding the numbers of the failed checks gives the exact position of the bad bit, and the receiver flips it back. With m data bits and r check bits, the r bits must say 'no error' or point to one of m + r places, so m + r + 1 ≤ 2ʳ.

The CRC (cyclic redundancy check) treats the data bits as a polynomial and divides it by a fixed generator polynomial, using arithmetic without carries (subtraction is XOR). The sender appends r zeros (r is the degree of the generator), divides, and puts the remainder in place of the zeros. The frame is now exactly divisible by the generator. The receiver divides the whole frame: any non-zero remainder means an error.

data 1101, generator x^2 + 1 = 101, so r = 2
append two zeros:  110100
110 xor 101 = 011, bring down 1 -> 111
111 xor 101 = 010, bring down 0 -> 100
100 xor 101 = 001, bring down 0 -> 010 (starts with 0)
remainder = 10, transmit 1101 10 = 110110
receiver divides 110110 by 101 -> remainder 0 -> accepted

Stop-and-wait

The simplest rule for a sender: send one frame, wait for an acknowledgement (ACK, a little 'got it' frame), then send the next. If the ACK does not come before a timer runs out, send the frame again. But a lost ACK creates a problem: the receiver already has the frame and gets it again, and it cannot tell a copy from a new frame. So each frame carries a sequence number. For stop-and-wait, one bit (0, 1, 0, 1...) is enough.

Stop-and-wait wastes the link. Each cycle lasts the transmission time of the frame plus the round trip (RTT), and the line is idle while waiting. Utilisation = t_frame / (t_frame + RTT). With a 1 Mbps link and 1,000-bit frames, t_frame = 1 ms. If the RTT is 20 ms, utilisation is 1/21, only 4.8%. To keep the link busy you would need to have about 21 frames in the air, which is the idea of the sliding window.

Another trick is piggybacking: when there is data going the other way, the ACK rides inside the header of that data frame, saving a whole frame. If there is no data to carry it, a short timer sends the ACK on its own.

Sliding window: many frames in flight

In a sliding window protocol the sender may send several frames before the first ACK arrives. The window is the list of numbers it may have outstanding. As ACKs arrive, the window slides forward. With n bits for the sequence number there are 2ⁿ numbers.

sequence:  0  1  2  3  4  5  6  7  0  1 ...
          [ sent, waiting for ACK ][ may send ]
           ^ oldest unACKed         ^ next to send
           window slides right when the ACK of 0 arrives

Medium access control: sharing one channel

In some networks many stations share one channel, like children in one room who all want to talk. If two talk at once, nobody understands anything: this is a collision. The rules that say who talks when belong to a sub-layer of the data link layer, called MAC (medium access control).

ALOHA: talk whenever you want

In pure ALOHA a station sends as soon as it has a frame, without listening. If it collides, it waits a random time and tries again. A frame is hit if any other frame starts during a window of two frame times around it (the vulnerable period). If G is the average number of attempts per frame time, the throughput is S = G e^(−2G), at most 1/(2e) ≈ 18.4%, at G = 0.5. More than 80% of the time is lost.

Slotted ALOHA divides time into slots, and stations may start only at the start of a slot. Frames either overlap completely or not at all, so the vulnerable period is just one frame time. Then S = G e^(−G), at most 1/e ≈ 36.8%, at G = 1, double the pure version. Above the best load, more attempts mean more collisions, which cause more retransmissions and even more load. That unstable behaviour is why back-off exists.

CSMA: listen first

CSMA (carrier sense multiple access) adds a polite rule: listen before talking, and wait if somebody else is using the channel. CSMA/CD (collision detection) also keeps listening while it sends, and stops at once when it notices a collision. After a collision, each station waits a random time chosen by binary exponential backoff: after the i-th collision of the same frame, pick a random number of slots from 0 to 2ⁱ − 1 (so 0 to 1, then 0 to 3, then 0 to 7, and so on), up to a cap of 0 to 1023. With few stations the wait is short. With many, the range grows fast and spreads them out. It adapts to the load without anyone knowing it.

There is a catch. A station finds a collision only if it is still sending when the noise comes back. In the worst case the frame has almost reached the far end when it collides, and the noise needs the same time to come back: twice the propagation time (2τ). So the frame must last at least 2τ, and the minimum frame size = rate × 2τ. Faster networks need longer minimum frames or shorter cables.

10 Mbps, slot time 2*tau = 51.2 microseconds
minimum frame = 10,000,000 bps * 0.0000512 s = 512 bits = 64 bytes

Ten times faster (100 Mbps) with the SAME 64-byte frame:
  the cable would have to be 10 times shorter

Ethernet, switches and hubs

Every Ethernet interface has a MAC address of 48 bits. The first 24 bits identify the manufacturer. It names a device inside the local network only; it is not used to route between networks (that is the job of the IP address in the next layer).

A hub just repeats the bits on all the other ports, so everyone shares one channel and collisions happen. A switch reads the destination MAC address of each frame and sends it only through the right port, so several conversations can happen at the same time and there are no collisions between ports. A switch needs no configuration, because it learns by itself: when a frame from A comes in on port 1, it writes 'A is on port 1' in its table. To forward, it looks up the destination. If the destination is known, it uses that port only. If it is unknown (or the frame is a broadcast), it floods the frame out of all the other ports.

      A --1[ SWITCH ]2-- B          table at the start: empty
                  3                 1) A -> B : learns A=port1,
                  |                    B unknown: FLOOD (B and C get it)
                  C                 2) B -> A : learns B=port2,
                                       A is known: only port 1

Redundant links between switches are good against failures, but they create loops. With a loop, flooded and broadcast frames go around forever and multiply: a broadcast storm that stops the network. The spanning tree protocol elects a root switch and keeps active only the links that form a tree (no cycles by definition). The other links wait as backups.

Wireless: CSMA/CA

On a cable, a station can listen while it talks. A radio cannot do that well, so Wi-Fi (802.11) cannot detect collisions. It uses CSMA/CA (collision avoidance): wait for the medium to be idle, wait a random backoff, then send. Because the sender cannot know if there was a collision, the receiver sends an ACK for every frame, and a missing ACK means retransmit.

Radio brings the hidden terminal problem. What matters is the interference at the receiver, not at the sender. Take A and C, both within range of B but too far from each other. A sends to B. C listens, hears nothing (it cannot hear A), and also sends: the two signals collide at B. The fix is RTS/CTS: before sending, the sender asks (RTS) and the receiver answers (CTS). The CTS is heard by the neighbours of the receiver, which then stay quiet.

   A ------- B ------- C       A and C cannot hear each other
   (range of A reaches B)      A -> B ...... C also -> B
                (range of C reaches B)
                               collision at B, nobody notices

The network layer: routing, IP addresses and subnets

The data link layer is for neighbours. The network layer joins many links and many networks and must answer: which way should this packet go to reach a machine far away? Two basic services exist. A datagram (connectionless) network treats every packet alone: each carries the full destination address, and each router decides with its table at that moment. It is simple and survives failures; reliability is left to the transport layer. A virtual circuit (connection-oriented) network first sets up a path and then all packets follow it. The Internet uses datagrams.

Routing: how routers find the way

A router has a routing table. For each destination it knows the next router (or the next link) to use. Routing algorithms build these tables.

Shortest path (Dijkstra). Think of the network as towns joined by roads with costs. Dijkstra starts at the source and repeats: take the not-yet-fixed node with the smallest known distance, fix it, and update the distances of its neighbours. The cheapest path may have more hops than another one.

links: A-B 1, A-C 4, B-C 2, C-D 1      source = A
step 1: fix A (0).  B = 1, C = 4
step 2: fix B (1).  C = min(4, 1+2) = 3
step 3: fix C (3).  D = 3+1 = 4
step 4: fix D (4).  path to D: A-B-C-D, cost 4

Distance vector (Bellman-Ford; RIP is an example): each router tells only its neighbours how far it thinks it is from every destination, and each updates its table with what it hears. Good news travels fast. Bad news travels slowly, and this is the count-to-infinity problem. Example: A — B — C in a line. B reaches C in 1, A reaches C in 2. The B–C link breaks. B hears from A 'I reach C in 2' (A does not know the route goes through B), so B thinks 'then I reach C in 3'. A hears B's 3 and says 4. They keep raising the numbers, one by one. RIP defines 16 hops as 'infinity' to stop it, and uses split horizon (do not tell a neighbour a route you learned from it), sometimes with poisoned reverse (tell it that route is infinite). These help, but loops through three routers can still happen.

Link state (OSPF is an example): each router finds its neighbours, measures the cost of the links and floods that information, in numbered packets, to everybody. All routers get the same map of the network and each runs Dijkstra on its own. It converges quickly and has no count to infinity.

Between organisations (BGP). The Internet is divided into autonomous systems (AS): networks run by one organisation. Inside an AS a protocol like OSPF finds the best path. Between ASes the goal is not the shortest path but a path allowed by each organisation's rules (for example, not carrying a competitor's traffic for free). BGP is a path vector protocol: for each destination it announces the whole list of ASes on the path. The list lets a router see a loop immediately (it sees its own AS) and gives the data needed for policy decisions.

Congestion and quality of service

Congestion is when the traffic of many sources together is more than part of the network can carry. Packets wait in queues and are dropped. It is a global problem. Flow control is local to the two ends: it stops a fast sender from drowning a slow receiver. Both say 'send slower', but for different reasons.

A token bucket shapes traffic. Tokens drop into a bucket at rate R, up to a capacity B. Each unit sent uses a token. After a quiet time the bucket is full, so a burst may leave at the peak rate M while tokens last. The bucket drains at M − R (tokens still arrive). The burst lasts S = B / (M − R), then the rate falls to R.

B = 6 Mbit, R = 1 Mbps, peak M = 7 Mbps
S = B / (M - R) = 6 / (7 - 1) = 1 s
sent in the burst = M * S = 7 Mbit  (= B + R*S = 6 + 1)

IPv4 addresses, masks and subnets

An IPv4 address has 32 bits, written as four numbers from 0 to 255 (for example 192.168.10.77). It has two parts: the first bits name the network, the rest name the host in it. The prefix /n says that the first n bits are the network. The mask is n ones followed by zeros. Applying a logical AND of the address with the mask clears the host bits and gives the network address. Setting all host bits to 1 gives the broadcast address. With 32 − n host bits there are 2^(32−n) addresses, but the first (network) and the last (broadcast) are reserved, so there are 2^(32−n) − 2 usable hosts. Each bit taken from the prefix doubles the block.

172.16.5.200/27   mask 255.255.255.224   (block size 256-224 = 32)
200 is in the block 192..223 of the last number
network   172.16.5.192
broadcast 172.16.5.223
hosts     172.16.5.193 .. 172.16.5.222   2^5 - 2 = 30 hosts

To send, a machine applies its own mask to the destination. If the result equals its own network, the destination is on the same link: the machine finds the MAC address with ARP and sends directly. If not, the frame goes to the MAC of the default router, but the IP packet keeps the final destination address.

ARP (address resolution protocol) links the two kinds of address. The machine asks everybody, by broadcast, 'who has this IP address?', the owner answers with its MAC, and the answer is kept for a few minutes in a cache.

With CIDR, routing tables hold prefixes of any length. A destination may match several; the router picks the longest matching prefix, the most specific one. Contiguous blocks can be joined (aggregation) into one shorter prefix that covers exactly the same addresses, which keeps Internet tables small. Four /24 blocks form a /22 only if they are consecutive and the first one starts at a multiple of 4 in the third number.

routes: 172.16.0.0/12 -> A,  172.16.8.0/21 -> B,  0.0.0.0/0 -> C
packet to 172.16.9.1  : matches /12 and /21  -> longest = /21 -> B
packet to 172.20.1.1  : matches /12 only     -> A
packet to 8.8.8.8     : matches only /0      -> C (default)

aggregate: 10.1.0.0/24 + 10.1.1.0/24 + 10.1.2.0/24 + 10.1.3.0/24 = 10.1.0.0/22

The IPv4 packet: TTL, fragments and ICMP

Routing tables can be wrong for a moment and send packets in circles. The TTL (time to live) field protects against that: the source sets a number, each router subtracts one, and when it reaches zero the packet is thrown away and the source is warned. ICMP is the protocol routers use to send such warnings ('destination unreachable', 'time exceeded'). The ping command is built on it. Traceroute sends packets with TTL 1, 2, 3, ... and reads the 'time exceeded' answers to discover each router on the path.

Every link has an MTU, the largest packet it accepts. If an IPv4 packet is larger, the router breaks it into fragments, each with its own header. The offset field says where the data belongs, counted in units of 8 bytes, and the MF (more fragments) bit says if more follow. Only the destination puts the pieces back together.

packet = 20 header + 2000 data, MTU = 1000
max data per fragment = 1000 - 20 = 980 -> use 976 (multiple of 8)
fragment 1: data 976, offset 0,   MF = 1
fragment 2: data 976, offset 122, MF = 1   (976 / 8 = 122)
fragment 3: data  48, offset 244, MF = 0   (1952 / 8 = 244)

NAT and IPv6

There are not enough IPv4 addresses (about 4.3 billion). NAT (network address translation) lets a whole home or company use private addresses (10.0.0.0/8, 172.16.0.0/12 and 192.168.0.0/16) and show a single public address to the Internet. The NAT box uses port numbers to tell the conversations apart, like a receptionist who gives each call an extension. The cost is that outsiders cannot start a connection to a machine inside, which breaks the old idea that every machine can be reached from everywhere.

IPv6 is the real fix: addresses have 128 bits, practically endless. The header was simplified: fixed size (40 bytes), no checksum, and routers do not fragment. A router that gets a packet too big for the next link discards it and tells the source with an ICMPv6 message; the source learns the smallest MTU of the path and adjusts the size of its packets.

The transport layer: ports, UDP and TCP

IP brings a packet to the right machine, but one machine runs many programs at once: a browser, a game, a music player. The transport layer delivers the data to the right program and, when needed, makes the delivery reliable. It works only at the two ends; routers in the middle do not look at it.

Programs are told apart by port numbers, 16-bit numbers (0 to 65,535). The pair (IP address, port) is a communication end point, a socket. Some ports are well known: 80 for HTTP, 443 for HTTPS, 53 for DNS, 25 for SMTP. It works like an apartment building: the IP address is the building and the port is the apartment.

UDP: the light one

UDP adds almost nothing to IP: ports to reach the right program, and a checksum to detect damaged data. It has no connection, no acknowledgement, no retransmission, no flow control. The header is only 8 bytes. It is the right tool when late data is useless, such as a voice call or a game: it is better to skip a lost piece and go on than to stop and wait for a retransmission. Applications that need reliability on top of UDP must build it themselves.

TCP: the reliable one

TCP gives the application a reliable stream of bytes in the right order. It numbers the bytes, confirms what arrives, resends what is lost, and slows down when the receiver or the network is overloaded.

Opening a connection: the three-way handshake. Each side picks an initial sequence number and needs the other side to confirm it. First the client sends SYN with its number. Then the server answers SYN+ACK: it confirms the client's number and sends its own, in one segment. Finally the client sends an ACK. Three segments are enough. The third one has a deeper purpose: networks can delay and duplicate packets, so an old SYN may arrive long after. The server cannot know alone whether it is new. The final ACK, which confirms a number the server chose just now, proves that the client is really taking part.

Client                        Server
  |---- SYN, seq=x ---------->|
  |<--- SYN+ACK, seq=y, ack=x+1|
  |---- ACK, ack=y+1 -------->|
  |        (data flows)        |
  |---- FIN ----------------->|   closing:
  |<--- ACK ------------------|   each direction
  |<--- FIN ------------------|   is closed
  |---- ACK ----------------->|   separately

Numbers and acknowledgements. TCP numbers every byte. The sequence number of a segment is the number of its first byte. The acknowledgement number is the number of the next byte expected, and it is cumulative: it confirms everything before it. So if a segment has sequence number s and n bytes of data, it covers bytes s to s + n − 1 and the ACK is s + n. Example: s = 4000, n = 300 gives ACK 4300. A lost ACK is usually repaired by the next, bigger ACK.

Flow control protects the receiver. In every segment it advertises its free buffer space, the receive window. If the application reads slowly, the window shrinks, even to zero, and the sender must slow down. Congestion control protects the network, and the sender estimates it, in a second window called the congestion window (cwnd). The sender may have in flight at most min(cwnd, receive window) unacknowledged bytes.

Congestion control has these ideas (the unit is the MSS, the maximum segment size):

• Slow start: begin with cwnd = 1 MSS. Each ACK adds 1 MSS, so the window doubles every RTT: 1, 2, 4, 8, 16. It is exponential, despite the name. It goes on until cwnd reaches the threshold ssthresh.
• Congestion avoidance: above ssthresh, grow by only 1 MSS per RTT (additive increase), carefully.
• Timeout (serious congestion, not even ACKs come back): ssthresh = half of the current window, cwnd = 1 MSS, and slow start again.
• Three duplicate ACKs: the receiver keeps repeating the last in-order ACK when later segments arrive. One or two may be just reordering, three mean a loss. Fast retransmit resends the missing segment without waiting for the timer. In TCP Reno, fast recovery then sets ssthresh and cwnd to half and goes on growing by 1 MSS per RTT.

cwnd
 20|        /|
 16|      /  |
 12|    /    |        /|
 10|  /      |      /  |    +1 MSS per RTT,
  8|/        |    /    |    halve at each loss
  6|         |  /
  4|         |/
   +--------------------------> time

How long to wait? The timeout. If the timer is too short, TCP resends for nothing. If it is too long, loss recovery is slow. So TCP follows the real delay with a moving average: SRTT = α·SRTT + (1 − α)·R, with α = 7/8, where R is the newest measurement. The old value has a big weight, each new sample a small one. Example: SRTT = 60 ms and R = 100 ms give 7/8 × 60 + 1/8 × 100 = 52.5 + 12.5 = 65 ms. The timeout is the SRTT plus a safety margin based on the variation.

Nagle's algorithm fights tiny segments. While there is sent data not yet acknowledged, small writes wait in a buffer until the ACK arrives or a full segment is ready. It adapts to the network by itself. Interactive applications that hate waiting, such as games, turn it off.

Closing. The side that closes first sends the last ACK and then waits in the state TIME_WAIT for twice the maximum segment lifetime. If that last ACK was lost, the other side will send its FIN again, and someone must still be there to answer. It also lets old duplicate segments of this connection die in the network before the same port pair is reused.

The application layer: DNS, e-mail, the Web and streaming

The top floor is what people actually use. Programs here follow protocols that run over TCP or UDP. We will see how names become addresses, how e-mail travels, how the Web works, and how videos and popular sites reach you quickly.

DNS: the phone book of the Internet

People like names (www.example.com). The network understands only numeric addresses. DNS (domain name system) translates one into the other. No machine knows everything, so the names form a tree: the root, then the top-level domains (.com, .org, .br), then the names below. Each part of the tree is a zone, run by its own administrator, with an authoritative server that has the final word about it.

              . (root)
           /     |     \
        .com   .org    .br          top-level domains
         |
    example.com                      a zone
         |
  www.example.com                    a name

Your computer asks a local resolver (usually run by your provider). If the resolver does not know, it asks the hierarchy with iterative queries: each server answers with what it knows, either the final answer or a referral to whom to ask next. For www.example.com with an empty cache, the order is: a root server (it points to .com), then a .com server (it points to the authoritative server of example.com), and finally the authoritative server (it gives the address). In practice, the cache avoids almost every trip to the root and the top-level servers.

Every answer has a TTL (time to live): for how many seconds it may be reused without asking again. A high TTL means less load and faster answers, but changes spread slowly. A low TTL is the opposite. If an address with TTL 300 is cached at time 0 and the administrator changes it at 100 s, clients behind that cache keep the old address until 300 s. That is why people lower the TTL days before moving a service.

E-mail

E-mail does two separate jobs. SMTP pushes a message from the sender to the server of the recipient. The user then reads the mailbox with an access protocol, IMAP or POP3, which pulls it. To find where to send a message to ana@example.org, the sending server asks DNS for the MX records of example.org: they name the mail servers of the domain, in order of preference. The part after the @ is a domain, not a machine name.

The Web and HTTP

HTTP is a request-and-answer protocol. The browser sends a request ('GET this page') and the server answers with a code and the content. HTTP is stateless: each request is handled alone, with no memory of the previous one. A cookie adds memory: the server asks the browser to store a small text and send it back with every request. Usually the cookie holds only a session identifier, and the real data stays on the server.

Counting round trips. Convention: opening a TCP connection costs 1 RTT (the handshake), and each request with its answer costs 1 RTT (the time to send the data itself is ignored). With non-persistent HTTP, every object needs a new connection, so 2 RTT each. With persistent HTTP, the same connection is reused: 1 RTT for the handshake, then 1 RTT per object. A page with 1 HTML file and N images, no parallel connections: non-persistent 2(N + 1) RTT, persistent 2 + N RTT. With N = 4: 10 against 6.

HTTP caching works in two phases. While the stored copy is within its lifetime (the max-age of the Cache-Control header), the browser uses it without asking the server. After that, it makes a conditional request, sending the validator it received (ETag or Last-Modified). If nothing changed, the server answers 304 Not Modified with no body, saving the transfer. Example: max-age=60 and ETag, and the page is needed again after 90 s: a conditional request is made.

Content delivery and streaming

A CDN (content delivery network) keeps copies of content in many places around the world. The most common trick to lead you to the nearest copy is in DNS: the CDN's DNS server returns a different address depending on where the question comes from. Content travels less, delay drops, and load is spread out.

Video and audio are played at a fixed rate, but arrive with a variable delay. The player keeps a few seconds in a playout buffer: it fills when the network is fast and drains when it is slow. The price is a small delay at the start, fine for a recorded video but bad for a live call, which needs a very small buffer.

Network security

Messages cross machines owned by strangers. Security asks: can someone read it? Can someone change it? Am I really talking to who I think? Three different properties answer these questions, and each needs its own mechanism.

Symmetric and asymmetric keys

In symmetric cryptography both sides share the same secret key. It is fast, but how do they agree on the key without a spy hearing it? Asymmetric (public-key) cryptography solves this: each person has a pair of keys, a public key that everyone may know and a private key that is kept secret. What one key locks, only the other opens. To send a secret to Bob, you lock with Bob's public key, and only Bob's private key opens it.

Hashes and signatures

A cryptographic hash function (SHA-256 is one) turns a message of any size into a short, fixed-size digest, like a fingerprint. It must be easy to compute, practically impossible to invert, and collision resistant (very hard to find two messages with the same digest). Changing one letter changes the digest completely.

A digital signature uses the key pair the other way around: you sign with your private key and everyone verifies with your public key. It gives authorship, integrity, and non-repudiation (you cannot deny it). In practice, the digest of the message is signed, not the whole message, because it is much shorter.

A MAC (message authentication code) is like a signature made with a shared secret key: it proves that the message was not changed and that it came from someone who has the key.

Certificates and trust

Public-key tricks only work if the public key you received really belongs to who claims it. Otherwise a man in the middle could give you his own key. A certificate fixes this: a trusted third party, the certification authority (CA), signs a statement 'this key belongs to this name'. Your browser checks the signature by following a chain of certificates up to a root CA that it already trusts. The certificate attests the link between an identity and a public key, nothing more.

Proving who you are: challenge and response

How to prove that you know a secret without sending it? In challenge-response, the verifier sends a value and the other side returns that value transformed with the secret. If the challenge were always the same, an attacker could record one good answer and play it again (a replay). So the verifier sends a fresh random number, a nonce (number used once), every time. An old answer is useless for a new challenge.

Protocols such as TLS (the lock in the browser) and IPsec combine these pieces. Public keys and certificates let the two sides agree on a key and know who the other is. Then fast symmetric encryption protects the data, and a MAC over every message detects any change before the data is used.

Putting it all together

Let us follow one click: you type www.example.com in your browser. Every layer does its small job, in order.

1. Application (DNS): the browser asks the resolver for the address of www.example.com. The cache or the DNS tree answers with an IP address.
2. Network (ARP): the address is outside your subnet, so your machine finds the MAC address of the default router with ARP.
3. Transport (TCP): a three-way handshake opens a connection to port 443 or 80.
4. Application (HTTP): the request goes out and the answer comes back, with a status code.
5. Network, link and physical: each packet crosses routers (longest prefix match, TTL going down), each hop is a frame with new MAC addresses, and the bits are signals on cables, fibre or radio.

Some mistakes happen again and again in exams and in real life. Check this list before you answer.

• Mixing bandwidth (how much per second) with latency (how long it takes).
• Forgetting that the usable hosts of a subnet are 2^(32−n) − 2.
• Mixing the MAC address (one link only) with the IP address (end to end).
• Thinking that the receive window and the congestion window are the same thing.
• Thinking that slow start is slow: it doubles every RTT.
• Using the whole sequence space as the window in selective repeat: the limit is half.
• Believing that encryption alone protects against changes to the message.