Formula sheet, every chapter

Every node has a dedicated point-to-point link to every other node. That is why it costs so much: it needs a lot of wiring and N − 1 I/O ports on each device.

Encapsulation: layer N − 1 carries the whole PDU of layer N in its data part without looking inside it. Layer n − 1 provides a service to layer n through the interface between them.

The number of bits sent per second. Defined by the physical layer, along with bit synchronisation between the sender and receiver clocks.

f

frequency in Hz: cycles per second

T

period in seconds: time for one cycle

Frequency and period are the inverse of each other.

Bit rate

bits sent per second (bps). Also called digital bandwidth, transmission speed or link capacity.

Bit interval

time needed to send one bit (the digital signal's "period")

λ

wavelength: the distance one cycle occupies (how far a simple signal travels in one period)

f

frequency

The second form comes from substituting T = 1/f. Wavelength depends on both the frequency and the medium.

How long one bit takes to travel from one node to the other.

• Distance in metres (m)
• Speed in m/s
• Answer in seconds

The propagation speed depends on the medium. Light travels at about 3 × 10⁸ m/s in a vacuum, slower in air, and at about 2/3 of that (≈ 2 × 10⁸ m/s) in a cable.

How long it takes to push the entire message onto the link.

The number of bits that can fill the link at one time: the length of the link measured in bits.

When a formula needs the message size in bits:

A twisted-pair twist length is 7.5–10 cm (lower quality) or 0.6–0.85 cm (better quality): more twists mean less interference.

Burst length is counted from the first corrupted bit to the last corrupted bit, so the bits in between need not all be wrong. Higher data rates mean longer bursts.

k

bits in the dataword

r

redundant (check) bits added

n

bits in the codeword actually sent

Simple parity check is C(5, 4): 4 data bits + 1 parity bit.

• Detects every single-bit error.
• Detects a burst only if an odd number of bits changed.

Data goes into a table. The last column holds a parity bit for each row and the last row a parity bit for each column.

• Detects 1, 2 or 3 errors, but not all 4-bit errors.
• Can correct a single-bit error: the bad row and bad column cross at it.

Each power of x that is present becomes a 1, and each missing power a 0, starting from the highest power.

r

degree of the generator = number of divisor bits − 1 = CRC length

• Sender: split into words (16-bit in the Internet), set the checksum to 0, add the words with one's complement addition (a carry out wraps back into the sum), then complement the sum.
• Receiver: add every word including the checksum, then complement. 0 means accept; anything else means reject.

Send the codewords with the extra block R. Any one corrupted block can be rebuilt without a retransmission. Chunk interleaving works on the same idea: multimedia can afford to lose one chunk from each packet.

The sender stuffs one extra 0 after every five consecutive 1s in the data, so the data can never look like the flag. When the receiver sees five 1s, it checks the next bit: a 0 is removed (unstuffed), and a 1 means the flag has arrived.

Byte-oriented framing: put an ESC byte before any flag byte or ESC byte that appears in the data. The receiver removes each ESC and treats the next byte as plain data.

R

channel rate in bps

M

number of nodes (stations)

T_{prop, max} is the time a bit takes to travel between the two stations that are furthest apart. The longer it is, the worse CSMA performs.

On a collision, stop sending, transmit the 48-bit jam signal, back off for a random time, then rerun the persistence method. CSMA/CD is used by Ethernet (IEEE 802.3) on a bus or a star built around a hub.

One minislot per station. Stations that reserved a slot then send their frames at the full rate R, in order, after the reservation frame.

Type codes: IP 0800, ARP 0806, Novell IPX 8137, AppleTalk 809B.

Flat (not hierarchical) and burned into the NIC's ROM. Vendor prefixes on the slides: Cisco 00-00-0C, Juniper 00-05-85.

That digit holds the least significant bit of the first byte. All F's (all 1s) is broadcast, a special case of multicast.

Full duplex needs full-duplex NICs, two wire pairs, a switch (not a hub) and point-to-point links. Each station is then its own collision domain, so CSMA/CD is not needed.

Count each link once, even when a switch port meets a router interface. Everything hanging off one hub (or a chain of hubs) is a single collision domain together with the port it plugs into.

B

link bandwidth

N

hosts sharing the hub

• Learn: if the source MAC address is not in the table, add it with its incoming port. If it is already there, update the port and the time.
• Destination found, different port: forward out of that port.
• Destination found, same port: drop the frame.
• Destination not found: flood out of every port except the one it came in on.
• Broadcast or multicast: send out of all ports.

32 bits = 4 octets. Each octet is 0–255 in dotted-decimal notation.

n

mask (prefix) length: the /n

Subtract 2 because the first address (host bits all 0) is the network address and the last (host bits all 1) is the broadcast address.

Limited broadcast is 255.255.255.255. Routers never forward it. A directed broadcast (network ID + host bits all 1s) is forwarded to the target network.

Shortcut: where the mask octet is 255, copy the IP octet; where it is 0, write 0. Only convert the one octet in between to binary.

Slash to decimal: /12 = 255.240.0.0, /18 = 255.255.192.0, /26 = 255.255.255.192, /30 = 255.255.255.252.

A valid subnet mask is longer than the class's default mask and no longer than /30.

1. Subtract 1 from the number of subnets needed.
2. Convert the result to binary and count its bits.
3. Add that count to the default mask.
4. The weight is 2 raised to the position of the last 1-bit in the mask, counted from the right of its octet. This equals 256 − the mask octet.
5. The first subnet is the original network address. Keep adding the weight to that octet, and stop when the result would pass 255.

So data = total length − header length. The header checksum covers the header only and is recomputed at every router, because fields such as the TTL change.

Stops lost packets from looping between routers forever.

Fragmentation happens at the source or at any router; reassembly happens only at the destination. The packet must fit the next link's MTU.

The best path is the one with the minimum total cost from source to destination. The cost metric can be hops, distance, delay, capacity, reliability, or a mix of these.

D_x(y)

least cost from router x to destination y

c(x, v)

cost of the link from x to its neighbour v

D_v(y)

neighbour v's advertised cost to y

In round one a router knows only its direct neighbours, and every other entry is ∞ (unreachable). It updates whenever a neighbour's vector changes or a link goes up or down.

Inside one AS (interior): RIP, OSPF, EIGRP. Between ASs (exterior): BGP.

1. Go through the rows from the longest mask to the shortest.
2. The first row where the AND gives that row's network address wins: forward to its next hop through its interface.
3. No match: use the default route 0.0.0.0/0, which matches everything.
4. No default route: send a "host unreachable" error back to the sender.

• Network-specific: one row per destination network, not per host.
• Host-specific: one row for a single host address, checked first.
• Default route 0.0.0.0/0: everything else.

Source and destination hosts need no forwarding table: they use their default router.

The first segment's sequence number is the initial sequence number (ISN), which is chosen at random when the connection is set up.

ACKs are cumulative: ACK = X means every byte up to X − 1 arrived, and the receiver expects byte X next. If the timer runs out before the ACK arrives, the sender retransmits.

5000 bytes ÷ 1000 bytes = 5 segments (example 9.8).

Windows are announced during the three-way handshake (SYN, SYN+ACK, ACK) and can change at any time. Both sides have their own windows because TCP is full duplex.

Well-known ports 0–1023 are assigned by IANA and given to servers. A connection is identified by the pair of socket addresses (source IP, source port, destination IP, destination port), so two clients can both use source port 49888 to reach port 80.

TCP is 20 bytes by default and up to 60 with options. UDP's checksum covers the whole segment and is optional.

DNS normally uses UDP because a request and its response each fit in one datagram.

The root's label is the empty dot. Only an FQDN can be resolved to an IP address. A PQDN (partial name) is completed by the resolver, which adds the local suffix.

The primary server loads its zone from a disk file. The secondary server loads everything from the primary; this copy is called a zone transfer.

Caching saves the result of a lookup so the next query for a name outside the server's domain is answered faster.