Data Communication and Computer Network (old course)

Piggybacking is the technique in two-way (full duplex) communication where an acknowledgement for a received frame is not sent as a separate frame but is attached (carried in the header) to the next outgoing data frame going the opposite way. It saves bandwidth and reduces the number of frames sent.

A home computer typically connects to the Internet through a modem or router provided by an ISP, and the mail is delivered through mail servers.

Sender PC --(SMTP)--> Sender's mail server (via ISP) --(SMTP over Internet)--> Receiver's mail server --(POP3/IMAP)--> Friend's PC

Components:

• User agent (mail client): the program where I compose the message.
• Access network and ISP: the modem/router and telephone, cable or fibre line link the home computer to the ISP and then to the Internet.
• SMTP server: the sender's mail server accepts the mail with SMTP (port 25) and relays it. DNS finds the destination mail server using the MX record.
• Internet backbone: routers forward the TCP/IP packets to the destination server.
• Receiver's mailbox server: stores the mail until my friend retrieves it with POP3 or IMAP.

This is the basic model: source, transmitter, transmission system, receiver and destination.

A routing protocol is a protocol that routers use to exchange information about network topology and reachability, so that they can build and update routing tables and choose the best path for packets. Examples are RIP, OSPF and BGP.

Bit stream: 1 0 0 1 0 1

(i) Manchester encoding (IEEE 802.3 convention: a 1 is a low-to-high transition in the middle of the bit period, a 0 is a high-to-low transition):

bit:    1     0     0     1     0     1
level: _|-   -|_   -|_   _|-   -|_   _|-

Every bit has a mid-bit transition, which gives clocking; the first half of each bit is the opposite level to the second half.

(ii) ASK (Amplitude Shift Keying): the carrier is sent at high amplitude for bit 1 and at zero (or low) amplitude for bit 0, frequency and phase unchanged:

bit:   1     0     0     1     0     1
wave: /\/\/ ----- ----- /\/\/ ----- /\/\/
      (carrier present for 1, absent for 0)

Advantages of analog over digital transmission:

• It needs less bandwidth for the same information (for example voice), because no encoding to bits is required.
• It is simpler and cheaper for continuous signals such as voice and audio, since no analog-to-digital conversion is needed.
• It has no quantization error, so the signal is represented continuously.
• The existing analog infrastructure (telephone lines, radio and TV) can be used directly.

Bit stream: 0 0 0 1 1 1 0 1 0 1

(i) Manchester encoding (convention: 1 = low-to-high transition in mid-bit, 0 = high-to-low). Each bit becomes two half-bit levels, H = high and L = low:

There is always a transition in the middle of each bit period.

(ii) ASK (amplitude shift keying): the carrier is sent at high amplitude for 1 and at zero (or low) amplitude for 0. The signal is:

0 0 0 carrier off, 1 1 1 carrier on, 0 off, 1 on, 0 off, 1 on.

(iii) NRZ-I: the level inverts for each 1 and stays the same for each 0. Starting from low:

Virtual circuit switching is a packet-switching method that is connection-oriented. A logical path is first set up between source and destination, and every packet follows it.

1. Setup: a call request establishes the route, and each switch records a virtual circuit identifier (VCI) in its table.
2. Data transfer: each packet carries only the short VCI, and switches forward it using the table without a routing decision.
3. Teardown: the circuit is released after the transfer.

Packets arrive in order, and resources can be reserved. The path is not dedicated, since the links are still shared.

Difference from datagram:

Necessity of switching. Connecting every pair of devices by a direct link needs $n(n-1)/2$ links, which is impractical and costly. Switching lets many devices share a smaller set of links: the network connects a sender to a receiver only when needed, making use of the links efficient, scalable and economical.

Datagram vs Virtual circuit

Advantages of digital over analog transmission:

• Better noise immunity; signals can be regenerated by repeaters instead of amplified, so noise does not accumulate.
• Easy error detection and correction by coding.
• Allows time-division multiplexing and efficient sharing of links.
• Voice, data and video can be carried in a common form and integrated.
• Easier encryption and security.
• Digital hardware is cheaper, smaller and more reliable (VLSI).
• Easy storage and processing, with higher quality over long distances.

In distance vector routing each router maintains a table (vector) giving the least known cost and next hop to every destination.

Working:

1. At start, each router knows only the cost to its directly connected neighbours; other costs are infinity.
2. Periodically (and on change), each router sends its whole table to its immediate neighbours.
3. A router receiving a neighbour's vector computes, for each destination $y$,

$D_x(y)=\min_v\{c(x,v)+D_v(y)\}$

and updates its table if a cheaper route is found, recording $v$ as the next hop. 4. The process repeats until no table changes (convergence).

Example: if A reaches B at cost 2 and B advertises C at cost 3, A learns C at cost 5 via B.

It is simple, used in RIP, but converges slowly and suffers from count-to-infinity, reduced by split horizon and poison reverse.

In distance vector routing each router keeps a table (vector) giving the best-known distance to every destination and the next hop to use. It is based on the Bellman-Ford algorithm.

Working:

1. Each router initialises its table with distance 0 to itself and the cost of directly connected neighbours.
2. Periodically, each router sends its whole table to its immediate neighbours only.
3. When a router receives a neighbour's table, for each destination it computes: new distance = cost to neighbour + neighbour's distance to destination. If this is smaller than its current value, it updates the entry and the next hop.
4. The process repeats until no table changes (convergence).

Example. Take routers A, B, C in a line, with A-B cost 2 and B-C cost 3. At first, A knows B=2 and C=infinity. B sends A its table in which C=3. A calculates C = 2 + 3 = 5 via B, which is better than infinity, and updates its table to C=5, next hop B.

Drawbacks: slow convergence and the count-to-infinity problem (reduced by split horizon and poison reverse). Example protocol: RIP.

Ethernet LANs use CSMA/CD (Carrier Sense Multiple Access with Collision Detection) to control access to the shared medium.

1. Carrier sense: A station that has a frame to send first listens to the channel. If the channel is busy, it waits.
2. Multiple access: If the channel is idle, the station transmits at once. Many stations share the same medium.
3. Collision detection: While transmitting, the station keeps monitoring the channel. If it detects a collision (two stations transmitted at the same time), it stops sending and transmits a short jam signal so that all stations know.
4. Backoff: After the collision, each station waits a random time chosen by the binary exponential backoff algorithm, then tries again. After 16 failed attempts the frame is dropped.

The minimum frame size ensures the sender is still transmitting when a collision signal returns, so collisions can be detected.

Ethernet: CSMA/CD

Ethernet shares a medium, so it uses CSMA/CD.

1. The station senses the carrier. If the channel is idle, it transmits; if busy, it waits.
2. While sending, it keeps listening to detect a collision.
3. On a collision it stops, sends a jam signal, and waits a random time using binary exponential backoff. It then retries, up to 16 attempts.

Detecting collisions works because the cable is short and the signal is strong enough to be sensed by the sender.

Wireless LAN (IEEE 802.11): CSMA/CA

Wireless stations cannot detect collisions while transmitting (a station cannot hear while it sends, and hidden stations exist). Wi-Fi therefore avoids collisions using the DCF mode.

1. The station senses the channel. If it is idle for a DIFS period, it transmits. Otherwise it defers and counts down a random backoff timer, which freezes whenever the channel is busy.
2. After receiving a frame correctly, the receiver sends an ACK after a SIFS. If no ACK arrives, the sender assumes a collision, doubles its contention window and retries.
3. Optionally, RTS/CTS is used to solve the hidden-terminal problem. The sender sends an RTS, the receiver replies with a CTS, and other stations hearing either one set their NAV (virtual carrier sense) and stay silent for the transmission time.

Switching is the technique by which a network moves data from an input port to the correct output port so that two end systems can communicate without a direct link between every pair. Instead of a dedicated line between every pair of devices, intermediate nodes (switches) forward the data.

Types of switching:

• Circuit switching: a dedicated path is set up between sender and receiver for the whole call (set-up, data transfer, tear-down), as in the telephone network. It gives fixed delay and no congestion once connected, but wastes bandwidth when the line is idle.
• Message switching: the whole message is stored at each node and forwarded when the next link is free (store and forward). There is no set-up, but delays are long and nodes need large buffers.
• Packet switching: the message is divided into small packets, each routed independently (datagram) or along a virtual circuit, and reassembled at the destination. It uses bandwidth efficiently and is used on the Internet.

Switching therefore provides efficient sharing of links, routing and connection management in large networks.

Piggybacking is a technique in which an acknowledgement for a received frame is not sent as a separate frame but is attached (carried in the ACK field) to the next outgoing data frame going in the opposite direction. It is used in bidirectional data link protocols such as sliding window.

If no data frame is ready within a short timeout, a separate ACK frame is sent.

Merits:

• Better use of bandwidth, since no separate ACK frame is needed.
• Fewer frames are sent, so there is less overhead and lower network traffic.
• Fewer frame arrivals mean fewer interrupts and less processing at the receiver.
• The ACK field in the header is only a few bits, so the extra cost is tiny.

Demerits:

• The acknowledgement is delayed until a data frame is available, which may cause the sender's timer to expire and trigger needless retransmission.
• The data link layer must wait for a data frame and decide how long to wait, which makes the protocol more complex.
• It works only for two-way (full duplex) traffic; it gives no benefit for one-way flow.

Framing is the function of the data link layer by which the bit stream received from the network layer is divided into discrete units called frames. Each frame carries a header (addresses, control information) and a trailer (error-detecting code such as CRC) around the data.

Framing methods: character count, flag bytes with byte stuffing, start/end flags with bit stuffing, and physical-layer coding violations.

Significance:

• It provides frame boundaries so the receiver knows where a frame begins and ends.
• It allows error detection and correction on a per-frame basis, so only a damaged frame needs to be retransmitted instead of the whole stream.
• It enables flow control and acknowledgement through frame sequence numbers.
• Source and destination (MAC) addresses in the header make delivery between nodes on the same link possible and let a shared medium be used.
• It provides synchronisation between sender and receiver.

In a layered network architecture:

Service: the set of operations (primitives) that a layer provides to the layer above it. It defines what the layer does, not how. Services may be connection-oriented or connectionless, e.g. the transport layer offers reliable delivery to the application layer.

Interface: the boundary between two adjacent layers on the same machine. It defines the primitives and the services the lower layer offers to the upper layer, and how the upper layer accesses them (through service access points). A clean interface lets one layer be replaced without affecting the others.

Protocol: the set of rules and conventions for communication between peer layers (same layer) on different machines, covering the format, order and meaning of the messages exchanged, such as TCP, IP and HTTP. Protocols are used to implement the services of a layer.

In short, a layer uses a protocol to talk to its peer on another machine, and provides a service to the layer above through an interface.

Network topology is the geometric arrangement of the nodes and links of a network, i.e. how devices are physically (or logically) connected.

Types:

1. Bus: all nodes share a single backbone cable with terminators at both ends. It is cheap and easy to install, but a break in the backbone stops the network, performance degrades with traffic, and faults are hard to isolate.
2. Star: each node connects to a central hub or switch. It is easy to add or remove nodes and a failed node does not affect others, but the central device is a single point of failure and more cable is needed.
3. Ring: each node connects to exactly two neighbours forming a closed loop, and data travels in one direction (often with token passing). It gives orderly access and equal opportunity, but one node or cable failure can break the ring (a dual ring helps).
4. Mesh: every node connects to every other (full mesh needs $n(n-1)/2$ links). It is very reliable and has dedicated links, but cabling and ports are expensive and complex.
5. Tree (hierarchical): star networks arranged in a hierarchy under a root node. It is scalable and easy to manage, but depends on the root and backbone.
6. Hybrid: a combination of two or more topologies to suit the needs of an organisation.

Multiplexing is the technique of combining several signals (data streams) from different sources so that they share one physical link or channel at the same time, and separating them again at the receiver. It makes efficient use of the capacity (bandwidth) of an expensive high-capacity link and reduces cabling cost.

At the sending end a multiplexer (MUX) merges the $n$ input lines into one high-capacity link; at the receiving end a demultiplexer (DEMUX) splits the stream back into the $n$ original outputs.

Main types:

• Frequency Division Multiplexing (FDM): the link bandwidth is divided into frequency bands, each carrying one signal at the same time (used in radio/TV broadcasting, analog telephone trunks). Guard bands separate channels.
• Time Division Multiplexing (TDM): each source gets the whole bandwidth for a short time slot in turn. It can be synchronous (fixed slots) or statistical/asynchronous (slots given only to active sources).
• Wavelength Division Multiplexing (WDM): FDM applied to light; different wavelengths share one optical fibre.
• Code Division Multiplexing (CDM): all users transmit at the same time and frequency, separated by unique spreading codes.

Error control is the set of methods used by the data link layer to detect and correct errors in frames caused by noise on the channel.

• Error detection: extra bits are added to each frame, such as parity bit, checksum or CRC (Cyclic Redundancy Check).
• Error correction: either forward error correction (e.g. Hamming code, which lets the receiver correct the error itself) or retransmission (ARQ).
• ARQ (Automatic Repeat reQuest): the receiver sends an ACK for a good frame and a NAK (or stays silent so the sender's timer expires) for a bad one, and the sender retransmits. Variants are Stop-and-Wait, Go-Back-N and Selective Repeat ARQ.

Flow control is the mechanism that keeps a fast sender from overwhelming a slow receiver, so that the receiver's buffer does not overflow.

• Stop-and-Wait: the sender sends one frame and waits for its ACK before sending the next. It is simple but wastes link capacity on long-delay links.
• Sliding window: the sender may send up to $W$ frames without waiting for an ACK; the window slides forward as ACKs arrive. Frames are numbered with sequence numbers. It is used by Go-Back-N and Selective Repeat and gives much better link utilisation.

Error control and flow control are normally implemented together in the same protocol (e.g. HDLC), using ACKs, sequence numbers and timers.

A simple communication model has five elements: source, transmitter, transmission system, receiver and destination.

Source -> Transmitter -> Transmission system -> Receiver -> Destination
(data g(t))  (signal s(t))   (noise added)       (signal r(t))   (data g'(t))

• Source: generates the data to be sent (e.g. a PC or telephone).
• Transmitter: converts the data into a signal suitable for the transmission medium (e.g. a modem converts digital data to analog signal).
• Transmission system: the medium (wire, fibre, air) or a whole network between source and destination. Noise and attenuation affect the signal here.
• Receiver: accepts the received signal and converts it back to data.
• Destination: takes the incoming data from the receiver and uses it.

Frequency is the number of cycles of a signal per second, measured in hertz (Hz); it describes a single signal ($f = 1/T$). Bandwidth is the range of frequencies a signal contains or a channel can pass, i.e. the difference between the highest and lowest frequency ($B = f_{max} - f_{min}$).

Data is the entity (information) that conveys meaning, such as text, numbers or voice, and can be analog or digital. A signal is the electrical or electromagnetic representation of data that is actually transmitted over the medium. Data is what is to be sent; signal is how it travels.

OSI reference model (7 layers, top to bottom):

7 Application
6 Presentation
5 Session
4 Transport
3 Network
2 Data link
1 Physical

Functions of the network layer:

• Routing: selects the best path for packets from source to destination across one or more networks (routing algorithms and tables).
• Logical addressing: gives each host a unique network address (e.g. IP address) so packets can be identified end to end.
• Packetising and forwarding: carries packets from node to node, with fragmentation and reassembly where link sizes differ.
• Congestion control: avoids too many packets entering part of the subnet.
• Internetworking: connects different networks together (gateways/routers).

A collision occurs when two or more stations transmit on a shared medium at the same time, so their signals overlap and the frames are corrupted.

CSMA/CD (Carrier Sense Multiple Access with Collision Detection): a station first listens to the channel (carrier sense); if idle it transmits, if busy it waits. While transmitting it keeps monitoring the channel; if it detects a collision it stops, sends a short jam signal, waits a random backoff time (binary exponential backoff) and tries again.

IEEE 802.3 (Ethernet) uses CSMA/CD.

The question does not state the generator pattern clearly, so I take the common generator $G(x) = x^4 + x + 1$ (bits 10011). The receiver divides the received message by the generator using modulo-2 division: if the remainder (syndrome) is zero the message is accepted as correct, otherwise it contains an error.

Dividing $11000110111$ by $10011$ gives remainder $1111$.

Because the remainder is not zero, the received message is incorrect: it was corrupted during transmission and the FCS check fails.

Framing is the data link layer function of splitting the stream of bits from the network layer into manageable units called frames, with a header and trailer so the receiver can tell where each frame starts and ends. Methods include character count, flag bytes with byte stuffing, flag bits with bit stuffing, and physical layer coding violations.

Lost ACK in Go-Back-N ARQ: the sender keeps sending frames within its window. The receiver accepts frames in order only. If an ACK is lost, the sender's timer for that frame expires before the ACK arrives. However, ACKs are cumulative, so if a later ACK arrives before the timeout it also acknowledges the earlier frames and nothing needs to be resent. If no later ACK arrives, the timer expires and the sender goes back and retransmits that frame and all frames sent after it. The receiver discards the duplicates (it already has them) and re-acknowledges.

For network 192.168.0.0 (class C):

• (i) Network address: 192.168.0.0
• (ii) Host no 5: 192.168.0.5
• (iii) This computer: 0.0.0.0
• (iv) Broadcast in network 192.168.3.0: 192.168.3.255 (host part all 1s)
• (v) Loopback through the IP layer: 127.0.0.1 (any address 127.x.x.x)
• (vi) Class type: Class C, because the first octet 192 lies in 192-223.

Use the Shannon capacity formula for a noisy channel:

$C = B\log_2\left(1 + \frac{S}{N}\right)$

Given $B = 6.1\text{ MHz}$, $S = 2\text{ W}$, $N = 0.1\text{ mW} = 10^{-4}\text{ W}$.

$\frac{S}{N} = \frac{2}{10^{-4}} = 20000$

$C = 6.1\times10^{6}\times\log_2(20001) = 6.1\times10^{6}\times 14.29 \approx 87.2\times10^{6}\text{ bps}$

The maximum data rate is about 87 Mbps.

In a token bus (IEEE 802.4), the token is passed around a logical ring of stations. If the token is lost (for example the station holding it fails, or noise corrupts it), no station can transmit and the network goes silent.

Recovery:

• Every station keeps a timer. If a station hears no activity for a long time, it concludes the token is lost.
• It then starts the claim-token process: it sends a CLAIM_TOKEN frame. If several stations do this at once, contention is resolved by address-based arbitration (the highest address wins, using timeslots).
• The winner generates a new token and re-initialises the logical ring, so normal operation resumes.
• If the next station in the ring has failed, the sender fails to get a response after retries and uses a "who follows" frame to find the next live station and removes the failed one from the ring.

The figure with the nodes A-J and link weights is not available here, so the numerical route cannot be read off; the method used is Dijkstra's shortest path algorithm:

1. Label the source A with distance 0 (permanent) and every other node with infinity (tentative).
2. From the most recently made permanent node, update the tentative distance of each neighbour as $d(v) = \min\big(d(v),\, d(u) + w(u,v)\big)$, remembering the predecessor.
3. Make the tentative node with the smallest distance permanent.
4. Repeat steps 2 and 3 until G becomes permanent.
5. Read the route by following the predecessors back from G to A; the label on G is the total length of the shortest route.

Generalised WAN block diagram:

 LAN / Hosts --- Router --- [ Communication subnet ] --- Router --- LAN / Hosts
                              (switching nodes/routers
                               joined by transmission lines)

Major components:

• Hosts (end systems): computers/LANs that run user applications and generate data.
• Switching nodes / routers (IMPs): receive packets and forward them towards the destination along the best path.
• Transmission lines (links): leased lines, fibre, microwave, satellite or telephone circuits carrying bits between nodes.
• Communication subnet: the collection of nodes and lines that carries data between hosts.
• Modems/CSU-DSU: connect hosts or routers to the carrier lines.

WAN vs LAN:

Digital data can be represented by an analog signal (modulating a carrier) in three ways:

1. ASK - Amplitude Shift Keying
2. FSK - Frequency Shift Keying
3. PSK - Phase Shift Keying

(A fourth, QAM, combines ASK and PSK.)

Waveforms for 1 0 1 1 0 1:

bit:  1      0      1      1      0      1
ASK:  big    none   big    big    none   big      (amplitude changes)
FSK:  high f low f  high f high f low f  high f    (frequency changes)
PSK:  0 deg  180    0 deg  0 deg  180    0 deg     (phase changes)

In ASK the carrier is on for 1 and off for 0; in FSK a higher frequency represents 1 and a lower one 0; in PSK the carrier phase is shifted by 180 degrees for a 0 relative to a 1.

An asynchronous ASCII character frame has 1 start bit, 7 data bits, 1 even parity bit and 1 stop bit, i.e. 10 bits in total.

Overhead bits $= 1 + 1 + 1 = 3$.

$\text{Overhead} = \frac{3}{10}\times100 = 30\%$

(of the transmitted bits; equivalently $3/7 \approx 43\%$ relative to the 7 data bits).

Multiplexing is combining several signals so they share a single link, with a multiplexer at the sender and a demultiplexer at the receiver.

ISO OSI reference model:

+---------------------+
| 7 Application       |
| 6 Presentation      |
| 5 Session           |
| 4 Transport         |
| 3 Network           |
| 2 Data link         |
| 1 Physical          |
+---------------------+

Major functions:

• Physical: transmission of raw bits, voltage levels, cables, connectors, bit synchronisation.
• Data link: framing, error control, flow control, MAC / physical addressing.
• Network: routing, logical addressing, congestion control, fragmentation.
• Transport: end-to-end delivery, segmentation, reliability, flow and error control, port addressing.
• Session: dialog control, synchronisation, checkpoints, session establishment and termination.
• Presentation: translation, encryption/decryption, compression, data formatting.
• Application: user services such as file transfer, e-mail, web access, directory services.

Framing techniques:

1. Character (byte) count
2. Flag bytes with byte stuffing
3. Flag bits (start/end flag) with bit stuffing
4. Physical layer coding violations

Bit stuffing: each frame begins and ends with the flag pattern 01111110. To stop the same pattern appearing inside the data, the sender inserts a 0 after every five consecutive 1s in the data. The receiver removes a 0 that follows five consecutive 1s.

Example: data 0111111011111

• Scan for five consecutive 1s: after 01 11111 a 0 is stuffed, and after the second run 11111 at the end a 0 is stuffed.
• Stuffed data: 011111010111110

This contains no 01111110 pattern. At the receiver, every 0 following five consecutive 1s is deleted to recover 0111111011111.

Flow control is the mechanism that regulates the rate of data transmission so that a fast sender does not overwhelm a slow receiver, whose buffers would otherwise overflow and frames be lost.

Situation requiring it: a powerful server sending at 100 Mbps to a slow device (such as an old PC or printer) that can process only 1 Mbps; without flow control the receiver's buffer fills and frames are dropped.

Techniques used in the data link layer:

• Stop-and-Wait: the sender transmits one frame and waits for its ACK before sending the next, so the receiver controls the pace. It is simple but gives poor utilisation when propagation delay is long.
• Sliding window: the sender may have up to $W$ unacknowledged frames outstanding. The receiver advertises or implies how many it can accept; each ACK slides the window forward. Frames carry sequence numbers. Go-Back-N and Selective Repeat are sliding window protocols and make better use of the link.

Sub-layers: the data link layer is divided into the LLC (Logical Link Control) sub-layer (IEEE 802.2), which provides flow and error control and interfaces to the network layer, and the MAC (Medium Access Control) sub-layer, which controls access to the shared medium.

Why MAC is needed: in a LAN, many stations share one broadcast channel. Without rules, simultaneous transmissions would collide, so the MAC sub-layer decides who may transmit and when.

CSMA/CD: a station senses the channel; if idle it transmits, otherwise waits. During transmission it listens, and if it detects a collision it stops, sends a jam signal, and retries after a random binary exponential backoff.

CSMA/CD vs token passing:

IEEE standards and MAC protocols:

The Internet uses packet switching, in two forms: datagram and virtual circuit. (Circuit switching is used by the telephone network.)

Characteristics of packet switching:

• Messages are divided into small packets, each with a header (addresses, sequence number).
• No dedicated path is reserved; links are shared by many users (statistical multiplexing), giving efficient use of bandwidth.
• Store-and-forward: a node receives a whole packet, checks it and forwards it to the next node.
• Packets may suffer variable delay, and may be lost or reordered.
• Robust: packets can be rerouted around failures.

Working:

• Datagram: each packet is routed independently using the destination address and routing tables; packets may take different paths and are reassembled at the destination (IP).
• Virtual circuit: a logical path is set up first by a call request; all packets then follow it using a virtual circuit number, and the circuit is released at the end.

Circuit switching, for comparison, sets up a dedicated physical path for the whole call, with fixed delay but wasted capacity when idle.

The problem of choosing a path is solved by routing (a routing algorithm running in the network layer, which fills the routing tables).

Desirable characteristics: correctness, simplicity, robustness (copes with failures and topology changes), stability, fairness, optimality (minimum delay/cost), low overhead, and fast convergence.

Shortest path routing: the network is modelled as a graph where nodes are routers and edges are links with a cost (hop count, distance, delay or bandwidth). To route, the algorithm finds the least-cost path between each pair of nodes, e.g. using Dijkstra's algorithm:

1. Mark the source with distance 0 and all others infinity.
2. Take the unvisited node with the smallest distance, make it permanent, and relax its neighbours: $d(v) = \min(d(v),\, d(u) + w(u,v))$.
3. Repeat until the destination is permanent.
4. Trace back via predecessors to get the path, and put the next hop in the routing table.

Each packet is then forwarded to the next hop on its shortest path.

Features of an IPv4 address:

• It is a 32-bit logical address, written in dotted decimal as four octets (e.g. 192.168.1.10).
• It has two parts: network ID (netid) and host ID (hostid).
• It is unique for each interface on the Internet; the total address space is $2^{32}$.
• It is divided into classes: A (first bit 0, 1-126), B (10, 128-191), C (110, 192-223), D (multicast, 224-239) and E (reserved).
• Special addresses exist: all 0s host = network address, all 1s host = broadcast, 127.x.x.x = loopback.
• Subnet masks can divide a network into subnets.

Dotted decimal: the address bits are 11000000 11100100 00010001 00111001, so the IP address is 192.228.17.57 (class C, since it starts with 110).

Subnet mask for 5 subnets: we need $2^n \ge 5$, so $n = 3$ bits are borrowed from the host part (giving 8 subnets). The mask is

11111111.11111111.11111111.11100000 = 255.255.255.224 (/27), with 30 usable hosts per subnet.

TCP services:

• Connection-oriented: a connection is set up with a three-way handshake and closed at the end.
• Reliable delivery: sequence numbers, acknowledgements and retransmission on timeout.
• Ordered, byte-stream delivery to the application, with duplicates removed.
• Flow control with a sliding window (receiver window size).
• Congestion control (slow start, congestion avoidance).
• Full duplex communication; multiplexing of applications using port numbers.
• Error detection with a checksum.

Comparison with UDP:

An Ethernet cable is specified in the form speed-signalling-segment length/medium, for example 10BASE5: 10 means 10 Mbps, BASE means baseband signalling, and the last part is the maximum segment length in hundreds of metres (or the medium type).

Architecture: an e-mail system has these parts:

• User Agent (UA): the program (e.g. Outlook, Gmail web) used to compose, read and manage messages.
• Message Transfer Agent (MTA): the mail server software that moves mail between servers, using SMTP.
• Mailbox / message store: disk space on the mail server where a user's incoming mail is held.
• Access protocols: POP3 or IMAP (and HTTP for webmail) for the user agent to fetch mail from the mailbox.

Sender UA --SMTP--> Sender MTA --SMTP over Internet--> Receiver MTA --> Mailbox --POP3/IMAP--> Receiver UA

Working:

1. The sender composes the message with a UA and gives the address user@domain.
2. The UA sends the message to the sender's mail server using SMTP, where it is queued.
3. The sender's MTA finds the destination mail server through a DNS MX record and transfers the message over a TCP connection (SMTP, port 25).
4. The receiving MTA places it in the recipient's mailbox.
5. The recipient's UA retrieves it using POP3 (download and delete) or IMAP (manage on the server).

A message consists of an envelope, header (From, To, Subject, Date) and body; MIME is used for attachments and non-ASCII content.

The data link layer uses ARQ (Automatic Repeat reQuest): errors are detected using a CRC/checksum, and bad or lost frames are retransmitted after a NAK or a timeout. Forms of ARQ are Stop-and-Wait, Go-Back-N and Selective Repeat.

Bit sequence: 1 0 1 1

bit:      1       0       1       1

• (i) ASK: carrier with high amplitude for 1, zero amplitude for 0: high, none, high, high.
• (ii) FSK: high frequency $f_1$ for 1, low frequency $f_2$ for 0: $f_1, f_2, f_1, f_1$.
• (iii) PSK: phase 0 degrees for 1, 180 degrees for 0: $0^\circ, 180^\circ, 0^\circ, 0^\circ$.
• (iv) NRZ-L: level depends on the bit (here 1 = low, 0 = high; the opposite convention is also used): low, high, low, low.
• (v) Manchester (1 = low-to-high mid-bit, 0 = high-to-low): _|-, -|_, _|-, _|-.
• (vi) AMI (Alternate Mark Inversion): 0 is zero level; 1s alternate between positive and negative pulses. The 1s are bits 1, 3 and 4, so the levels are $+V, 0, -V, +V$.

The IP datagram length field is 16 bits, so the maximum size is $2^{16}-1 = 65{,}535$ bytes (including the header, which is 20-60 bytes).

$f = \frac{1}{T} = \frac{1}{20\times10^{-3}} = 50\text{ Hz}$

The transmitter. It converts (encodes/modulates) the source data into a signal suitable for the transmission medium.

The network layer (layer 3) is responsible for routing. It handles logical (IP) addressing and selects the path packets take from source to destination across networks.

Bit stuffing (or byte/character stuffing in byte-oriented protocols) is used. The sender inserts an extra 0 after every five consecutive 1s in the data (or an escape byte before a flag-like byte), so the flag pattern 01111110 never appears inside the data field. The receiver removes the stuffed bits.

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance), used in IEEE 802.11 wireless LANs, avoids collisions using interframe spacing, random back-off and optional RTS/CTS exchange. Token passing (IEEE 802.5) also prevents collisions because only the token holder may transmit.

Message switching / packet switching (store-and-forward) allows data rate conversion, because each node stores the data and forwards it at the rate of the outgoing link. In circuit switching the dedicated path needs the same rate at both ends, so conversion is not possible.

Fairness. A good routing algorithm treats all end stations equally, giving each a fair chance without bias. (Other properties are correctness, simplicity, robustness, stability and optimality.)

The mask 255.255.255.224 has last octet $224 = 11100000_2$, so 5 bits are left for hosts.

$\text{Hosts per subnet} = 2^5 - 2 = 30$

The two subtracted addresses are the network and broadcast addresses.

TCP is used for file transfer (for example FTP, port 20/21), because it provides reliable, ordered, error-checked delivery of data.

The Domain Name System (DNS) translates human-readable domain names (such as www.example.com) into IP addresses, and the reverse. It is a distributed, hierarchical database of name servers, so users need not remember numeric addresses. It uses port 53.

Using Shannon's capacity formula:

$SNR_{dB} = 10\log_{10}(SNR) = 40 \Rightarrow SNR = 10^4$

$C = B\log_2(1+SNR) = 4000\log_2(10001) \approx 4000 \times 13.29$

$C \approx 53{,}150 \text{ bps} \approx 53.2 \text{ kbps}$

Framing is the data link layer function of dividing the bit stream from the network layer into manageable units called frames, with a way for the receiver to know where each frame starts and ends. Each frame carries a header, the data and a trailer.

Framing techniques:

1. Character (byte) count
2. Flag bytes with byte stuffing
3. Flag bits (start/end flag) with bit stuffing
4. Physical layer coding violations

Bit stuffing: the flag is 01111110. Whenever the sender sees five consecutive 1s in the data, it inserts a 0 after them. The receiver removes a 0 that follows five consecutive 1s.

Example: data 0110111111011111

• Original: 0110 111111 0 11111
• After each run of five 1s a 0 is inserted: 0110 11111 0 1 0 11111 0

$\texttt{011011111010111110}$

In the stuffed string no run of six 1s occurs, so the flag 01111110 cannot appear inside the data. The receiver removes the 0 after every five 1s to recover the original data.

Features of datagram packet switching:

• It is connectionless, so no call setup is needed.
• Each packet (datagram) is routed independently and carries the full source and destination address.
• Packets may take different routes and may arrive out of order, so the destination reorders them.
• There is no guaranteed delivery. Lost or duplicated packets are handled by higher layers.
• It is flexible and robust, because packets can avoid failed or congested nodes.
• Bandwidth is used efficiently through statistical sharing.
• It gives low delay for short messages because there is no setup phase.
• Each packet needs a routing decision, so header overhead is higher.

The shortest path is found with Dijkstra's algorithm. Each link has a cost (distance, delay or hop count).

Procedure (source node S):

1. Label S with distance 0 (permanent) and every other node with $\infty$ (tentative).
2. Take the working node (initially S) and, for each neighbour, compute the distance via the working node. If it is smaller than the neighbour's current label, update the label and record the predecessor.
3. Among all tentative nodes, make the one with the smallest label permanent and make it the new working node.
4. Repeat until the destination is permanent. Trace the predecessors back to get the path.

Example: links A-B = 2, A-C = 5, B-C = 1, B-D = 7, C-D = 3.

      2        1
  A ------ B ------ C
   \       |       /
    \ 5    | 7    / 3
     \_____ D ___/

From A: B = 2, C = 5. Make B permanent. Via B, C = 3 (better than 5) and D = 9. Make C permanent. Via C, D = 6 (better than 9). So the shortest path from A to D is A-B-C-D with cost 6.

IPv4 header (32 bits per row):

| Version(4) | IHL(4) | Type of service(8) |        Total length(16)        |
|        Identification(16)              | Flags(3) |  Fragment offset(13)  |
|   Time to live(8)   |  Protocol(8)     |       Header checksum(16)        |
|                         Source IP address(32)                              |
|                      Destination IP address(32)                           |
|                      Options + padding (0 to 40 bytes)                    |

i. The header length field (IHL) is 4 bits, so its maximum value is 15 words of 4 bytes: $15 \times 4 = 60$ bytes. The minimum header is 20 bytes.

ii. TTL (Time To Live) limits the life of a datagram. Each router decrements it by one, and when it reaches 0 the datagram is discarded. This prevents datagrams from looping forever in the network.

iii. The total length field is 16 bits, so the maximum datagram size is $2^{16} - 1 = 65{,}535$ bytes (header plus data).

A bridge connects two LAN segments and filters frames using a MAC address table. It usually has few ports (2 or 4) and forwards frames in software. A switch is a multiport bridge with many ports, forwards frames in hardware (ASICs) at higher speed, and gives each port its own collision domain.

A socket address is the combination of an IP address and a port number. It identifies one end of a connection uniquely. Example: 192.168.1.10:80, where 192.168.1.10 is the host and 80 is the port of the web service.

In synchronous transmission, data is sent as a continuous stream of blocks or frames without start and stop bits for each character. The sender and receiver are synchronized by a common clock (or clock recovered from the data) and special sync characters or flags. It is faster and more efficient for large volumes of data.

ARP (Address Resolution Protocol) finds the MAC (physical) address of a host when its IP address is known, so a frame can be delivered on the local network. RARP (Reverse ARP) does the opposite: a host that knows its MAC address (such as a diskless machine) asks for its IP address.

UDP is preferred when speed and low overhead matter more than reliability, for example real-time voice and video, online gaming, streaming, DNS queries and broadcast/multicast applications. It has no connection setup, no retransmission and no flow control, so delay is low and occasional packet loss is tolerable.

BGP (Border Gateway Protocol) is the exterior gateway protocol used to exchange routing information between different autonomous systems on the Internet. It is a path-vector protocol that applies routing policies and prevents loops, and it makes the global Internet routing possible.

A protocol stack is a set of network protocols arranged in layers, where each layer provides services to the layer above and uses the services of the layer below. Examples are the TCP/IP stack and the OSI stack. Data passes down the stack at the sender and up the stack at the receiver.

Yes. The data link layer uses physical (MAC) addresses, which are 48 bits, fixed in the NIC and have only local significance within one network. The network layer uses logical (IP) addresses, which are 32 bits (IPv4) or 128 bits (IPv6), assigned by configuration, hierarchical and valid across the whole internetwork. MAC addresses identify the next hop and IP addresses identify the final host.

A port address is 16 bits in length whereas an IPv6 address is 128 bits in length.

Transmission impairment is any imperfection in a transmission medium that makes the received signal differ from the transmitted one, causing errors in digital data and degraded quality in analog signals.

Major types:

1. Attenuation: loss of signal strength with distance as energy is absorbed by the medium. It is measured in decibels and is overcome with amplifiers or repeaters.
2. Distortion: change in the shape of a composite signal because its frequency components travel at different speeds and arrive with different delays (delay distortion). Equalizers reduce it.
3. Noise: unwanted signals added between sender and receiver.
   • Thermal noise: random motion of electrons.
   • Induced noise: from motors and appliances.
   • Crosstalk: coupling from a neighbouring wire.
   • Impulse noise: short spikes from lightning or switching.

The effect of noise is measured by the signal-to-noise ratio (SNR).

i) Bandwidth: the range of frequencies a channel or signal occupies, the difference between the highest and lowest frequency, $B = f_{max} - f_{min}$. Unit: hertz (Hz). In digital contexts it also means the data capacity of a link, in bits per second.

ii) Bit rate: the number of bits transmitted per second. Unit: bits per second (bps), with multiples kbps, Mbps and Gbps.

iii) Amplitude: the maximum height (strength) of a signal measured from its zero level, which shows its intensity. Unit: volt (V) for voltage signals, ampere (A) for current, or watt (W) for power.

The OSI model has seven layers.

1. Physical: transmits raw bits over the medium. It defines voltages, cables, connectors, data rate and topology.
2. Data link: framing, physical (MAC) addressing, error detection, flow control and media access control. It gives reliable node-to-node delivery.
3. Network: logical (IP) addressing, routing, packet forwarding and congestion control. It gives source-to-destination delivery across networks.
4. Transport: end-to-end (process-to-process) delivery using port addresses, segmentation and reassembly, flow control, error control and connection management (TCP, UDP).
5. Session: establishes, manages and terminates sessions between applications, with dialog control and synchronization (checkpoints).
6. Presentation: translation between data formats, encryption/decryption and compression.
7. Application: gives network services to the user, such as e-mail, file transfer, web access and remote login.

Sliding window protocol lets the sender transmit several frames before it needs an acknowledgement, so the link is used efficiently.

Working:

• Frames are numbered sequentially. The sender keeps a window of sequence numbers it may send without acknowledgement. With $n$-bit sequence numbers the window is at most $2^n - 1$ (Go-Back-N) or $2^{n-1}$ (selective repeat).
• The sender transmits frames inside the window and keeps a copy of each until it is acknowledged.
• The receiver has its own window of sequence numbers it will accept. On receiving a correct frame it sends an acknowledgement (ACK), which can be piggybacked on data going the other way.
• When an ACK arrives, the sender's window slides forward and new frames can be sent. The receiver's window slides as frames are delivered in order.
• If a frame is lost or damaged, a timer expires. In Go-Back-N the sender retransmits that frame and all later ones. In selective repeat only the missing frame is resent.

This gives flow control, since the sender can never have more unacknowledged frames than the window size, and error control through ACKs and retransmission.

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) is the access method of wired Ethernet (IEEE 802.3).

Working:

1. A station with a frame to send listens to the channel (carrier sense).
2. If the channel is idle, it transmits. If busy, it waits until idle (1-persistent).
3. While transmitting it keeps listening. If another station transmits at the same time, a collision is detected.
4. On collision, the station sends a short jam signal so that all stations know, and stops.
5. It waits a random time using binary exponential back-off and tries again, giving up after a maximum number of attempts (16).

The minimum frame size must be large enough for the sender to detect a collision before it finishes transmitting.

Difference from CSMA/CA:

• CSMA/CD detects collisions after they occur and is used in wired LANs, since a station can listen while sending. CSMA/CA tries to avoid collisions before they occur and is used in wireless LANs (802.11), where a station cannot detect collisions while transmitting.
• CSMA/CA uses interframe spacing, random back-off before transmission, and ACKs (optionally RTS/CTS) to confirm delivery.

i. The first octet is 192, which is in the range 192 to 223, so it is Class C.

ii. The prefix is /26, so there are $32 - 26 = 6$ host bits.

$\text{Valid hosts} = 2^6 - 2 = 62$

iii. The subnet mask for /26 is 26 ones followed by 6 zeros: 11111111.11111111.11111111.11000000.

$\text{Subnet mask} = 255.255.255.192$

Datagram packet switching: the message is divided into packets, and each packet (datagram) is treated independently. Each packet carries the full destination address. At each node the router looks at the destination address and forwards the packet along the best route at that moment, so packets of the same message may take different paths and arrive out of order. The destination reassembles them. No connection is set up first.

Difference from virtual circuit:

(i) IPv4 versus IPv6

(ii) WDM versus FDM

(iii) Internet versus WWW

(iv) 802.3 Ethernet versus 802.5 Token Ring

$B = f_{max} - f_{min} = 33.6\text{ MHz} - 11\text{ kHz} = 33{,}600 \text{ kHz} - 11 \text{ kHz} = 33{,}589 \text{ kHz}$

The bandwidth is 33.589 MHz.

Frequency Division Multiplexing (FDM) is preferred for analog data transmission, because each analog signal is assigned its own frequency band and all are sent together on the shared medium. (TDM is preferred for digital signals.)

IP address 196.16.4.140 in binary:

32-bit form: 11000100.00010000.00000100.10001100

The first octet begins with 110, so this is a Class C address. Its default subnet mask is 255.255.255.0 (11111111.11111111.11111111.00000000, i.e. /24).

Shannon's channel capacity is the theoretical maximum data rate of a noisy channel with bandwidth $B$ (Hz) and signal-to-noise power ratio $S/N$:

$C = B\log_2\left(1+\frac{S}{N}\right)\ \text{bps}$

It shows that capacity rises with bandwidth and SNR, and that error-free transmission is possible at any rate below $C$ but not above it.

Connection-oriented service of the data link layer has three phases:

1. Connection establishment: both sides initialise variables and counters (sequence numbers, buffers).
2. Data transfer: frames are sent and received in order, with acknowledgements, flow control and error control.
3. Connection release: the connection is closed and the resources are freed.

A token is a special control frame or bit pattern that circulates among the stations and gives the holder the right to transmit.

• IEEE 802.4 (Token Bus): the token is passed among stations on a bus that form a logical ring, in order of descending station address.
• IEEE 802.5 (Token Ring): the token is a 3-byte frame (start delimiter, access control, end delimiter) that circulates around the physical ring. A station with data captures the free token and sends its frame in its place.

A station may transmit only while it holds the token, so there are no collisions.

In 1-persistent CSMA, a station with a frame to send senses the channel. If it is idle, the station transmits at once. If it is busy, the station keeps sensing continuously and transmits the moment the channel becomes idle, with probability 1. If two or more stations are waiting, they collide.

In p-persistent CSMA, an idle channel is used with probability $p$, and with probability $1-p$ the station defers to the next time slot.

Nyquist rate, with $B=3500$ Hz and $L=8$ levels:

$C = 2B\log_2 L = 2\times3500\times\log_2 8 = 2\times3500\times3 = 21{,}000\ \text{bps}$

Shannon capacity, with SNR = 25 dB:

$\frac{S}{N}=10^{25/10}=10^{2.5}\approx316.2$

$C = B\log_2\left(1+\frac{S}{N}\right)=3500\times\log_2(317.2)=3500\times8.31\approx29{,}080\ \text{bps}$

So the Nyquist maximum is 21 kbps, and the maximum theoretical information rate is about 29.1 kbps. The eight-level scheme at 21 kbps is below this limit, so it is achievable.

Thermal noise power is $N = kTB$, where $k = 1.38\times10^{-23}$ J/K.

$T = 15 + 273 = 288$ K and $B = 6\times10^{6}$ Hz.

$N = 1.38\times10^{-23}\times288\times6\times10^{6}\approx2.38\times10^{-14}\ \text{W}$

$N_{dBW}=10\log_{10}(2.38\times10^{-14})\approx-136.2\ \text{dBW}$

The noise power is about -136.2 dBW.

(i) TCP and UDP

(ii) ARP and RARP

Message $M = 1001101$, generator $G(x)=x^3+x+1 \Rightarrow 1011$ (degree 3).

Append 3 zeros: 1001101000. Divide by 1011 using modulo-2 division:

CRC remainder = 101.

Transmitted frame = message + CRC = 1001101101.

Check: dividing the received frame by 1011 gives remainder 000.

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) is the MAC method of Ethernet (IEEE 802.3). A station listens before transmitting, and it keeps listening while transmitting. If it detects a collision, it stops, sends a jam signal and retries after a random back-off.

Algorithm

1. Prepare the frame and set attempts = 0.
2. Sense the channel. If it is busy, wait until it is idle (persistent sensing).
3. When the channel is idle, start transmitting and keep monitoring the channel.
4. If no collision is detected until the whole frame is sent, the transmission is successful. Stop.
5. If a collision is detected:
   • stop sending and transmit a short jam signal so all stations know;
   • set attempts = attempts + 1; if attempts exceeds 16, abort and report an error;
   • choose a random $K$ from $0$ to $2^{\min(attempts,10)}-1$ (binary exponential back-off);
   • wait $K\times$ slot time, then go to step 2.

For collisions to be detected, the frame transmission time must be at least twice the propagation delay.

ALOHA is a random-access MAC protocol developed at the University of Hawaii. Any station may send a frame whenever it has data. If the acknowledgement does not arrive in time, it assumes a collision, waits a random time and retransmits.

Pure ALOHA: stations transmit at any time. A frame is vulnerable for two frame times ($2T_{fr}$). Maximum throughput is $S = Ge^{-2G}$, about 18.4% at $G=0.5$.

Slotted ALOHA: time is divided into slots equal to one frame time, and stations transmit only at the start of a slot. The vulnerable period falls to one frame time ($T_{fr}$). Throughput is $S = Ge^{-G}$, with a maximum of about 36.8% at $G=1$.

Framing is how the data link layer splits the bit stream from the network layer into discrete frames, each with a header and trailer, so the receiver can tell where a frame starts and ends and can check it for errors.

Techniques:

1. Character (byte) count
2. Flag bytes with byte stuffing
3. Flag bits with bit stuffing
4. Physical layer coding violations

Character count method: a field in the header gives the number of characters in the frame, including the count field itself. The receiver reads the count and knows where the frame ends.

Example, four frames of 5, 5, 8 and 8 characters:

| 5 | A B C D | 5 | E F G H | 8 | I J K L M N O | 8 | P Q R S T U V |
  Frame 1       Frame 2        Frame 3              Frame 4

The weakness is that if a count is corrupted (for example, the 5 in frame 1 becomes 7), the receiver loses synchronisation and cannot find the start of the next frame. This is why the method is rarely used alone.

The transmitter (with the encoder or modulator) converts the source signal into a form suitable for transmission over the medium. For example, a modem converts digital data to an analog signal.

In selective-reject (selective repeat) ARQ, only the damaged frame is retransmitted. Frames that arrive after it are correct but out of order, so the receiver stores them in a buffer. When the missing frame arrives, the receiver puts the frames in the right order and delivers them to the upper layer. The sender also keeps copies of unacknowledged frames for retransmission.

Routers are classified in these ways:

• By routing method: static (non-adaptive) and dynamic (adaptive) routers.
• By protocol use: interior routers (RIP, OSPF) and exterior or border routers (BGP).
• By location or function: internal routers, edge routers, core routers, border (gateway) routers.
• By number of protocols handled: single-protocol and multi-protocol routers.

• Network support layers: the physical, data link and network layers (layers 1 to 3). They deal with the physical aspects of moving data between devices, such as electrical specification, physical addressing, transport timing and reliability.
• User support layers: the session, presentation and application layers (layers 5 to 7). They allow interoperability between software systems.

The transport layer (layer 4) links the two groups, and it makes sure that what the lower layers deliver is in a form the upper layers can use.

In NRZ-L, the signal level depends on the bit value: for example, a high level for 0 and a low level for 1 (or the reverse). A long run of identical bits gives no change, which causes synchronisation problems.

In NRZ-I, the level depends on the bit transition: the signal inverts at the start of a 1 bit and stays the same for a 0 bit. Long runs of 1s still produce transitions that help synchronisation, but long runs of 0s do not.

The first octet 223 lies in 192 to 223, so this is a Class C address. The default mask is 255.255.255.0: the first 24 bits are the network part and the last 8 bits are the host part.

• Network address: 223.124.123.0
• Host address: 89 (0.0.0.89)

A switch is more intelligent. A hub is a simple repeater that broadcasts every incoming signal to all its ports. A switch reads the destination MAC address of each frame, keeps a MAC address table, and forwards the frame only to the port where the destination is. This reduces collisions and traffic and gives each port its own collision domain.

• Mesh: each device is linked to every other device, so the number of cable links is $\dfrac{n(n-1)}{2}$.
• Ring: each device is linked to the next, and the last to the first, so the number of cable links is $n$.

The data link layer provides these services to the network layer:

1. Framing: splitting the bit stream into frames.
2. Physical (MAC) addressing: identifying the sender and receiver on the link.
3. Unacknowledged connectionless service: frames are sent without any acknowledgement.
4. Acknowledged connectionless service: each frame is acknowledged.
5. Acknowledged connection-oriented service: connection setup, ordered and reliable delivery, release.
6. Error control: detecting and correcting errors with CRC, parity and ARQ.
7. Flow control: stopping a fast sender from overwhelming a slow receiver.
8. Media access control: deciding who may use a shared link.

The MAC protocol that avoids collisions is CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance), used in wireless LANs (IEEE 802.11), where a station cannot listen while it transmits and so cannot detect collisions.

Working:

1. The station senses the channel. If it is busy, it waits.
2. When the channel becomes idle, the station waits for a fixed IFS (inter-frame space).
3. The station then chooses a random back-off time in a contention window and counts down only while the channel stays idle. If the channel turns busy, the counter pauses and later resumes.
4. When the counter reaches zero, the station sends the frame. With RTS/CTS, it first sends a short RTS (request to send), and the receiver replies with a CTS (clear to send). Other stations hearing these set their NAV (network allocation vector) and keep quiet.
5. The receiver sends an ACK after a correct frame. If no ACK arrives in time, the sender assumes a collision, doubles the contention window and tries again.

In packet switching, a message is divided into small packets, which are sent through the network and reassembled at the destination. Each link is shared, and a store-and-forward method is used. There are two techniques:

1. Datagram approach (connectionless): each packet (datagram) is treated independently and carries the full destination address. Different packets of one message may take different routes, so they may arrive out of order and the destination must reorder them. There is no setup, and routing can adapt around a failure.

2. Virtual circuit approach (connection-oriented): a logical path is set up first, and all packets follow it, carrying a short virtual circuit number. Packets arrive in order. There are two types: switched virtual circuit (SVC), set up on demand, and permanent virtual circuit (PVC), set up in advance.

Packet switching uses bandwidth efficiently, but delay is variable.

The address 192.168.1.0 is Class C with the mask 255.255.255.0 (/24, 8 host bits).

For 4 departments we need 4 subnets, so borrow 2 bits ($2^2=4$). The new mask is /26, which is 255.255.255.192.

Each subnet has $2^6=64$ addresses, of which $2^6-2=62$ are usable hosts.

Analog transmission sends a continuously varying signal. Digital data must first be modulated onto a carrier (ASK, FSK, PSK). Over long distance, amplifiers are used, and they amplify noise along with the signal, so noise accumulates.

Digital transmission sends discrete signal levels (1s and 0s). Digital data is encoded as line codes (NRZ, Manchester); analog data is first sampled and digitised (PCM). Over long distance, repeaters regenerate the signal, so noise does not accumulate.

The three fundamental characteristics are:

1. Delivery: data must reach the correct intended destination, and only that destination.
2. Accuracy: data must be delivered without alteration.
3. Timeliness: data must be delivered in time, with little delay, which matters for real-time audio and video.

(Jitter, the variation in packet arrival time, is also often considered under timeliness.)

An analog signal is preferred when the source data is naturally analog and the cost or bandwidth of digitising it is not justified, for example:

• the available bandwidth is small, since an analog signal needs less bandwidth than its digital version;
• simple, cheap, short-distance systems such as radio and television broadcast, or a basic telephone local loop;
• transmission over media that only pass analog signals, such as radio waves and the voice-grade telephone line.

The seven OSI layers form three groups by function:

1. Network support layers (layers 1 to 3): physical, data link and network layers, which handle the physical transmission of data between devices.
2. User support layers (layers 5 to 7): session, presentation and application layers, which let unrelated software systems work together.
3. Transport layer (layer 4): it links the two groups, ensuring end-to-end reliable delivery of data from the lower layers to the upper layers.

Therefore the model can justifiably be seen as three parts.

The data link layer and the transport layer have these features in common:

• Error control: detecting errors and retransmitting (ARQ).
• Flow control: using sliding window to prevent a fast sender from swamping a slow receiver.
• Sequencing: numbering frames or segments so they are delivered in order.
• Acknowledgement and retransmission of lost data.
• Connection-oriented services: connection setup, data transfer and release.

The data link layer does this between two directly connected nodes (hop by hop); the transport layer does it end to end.

In CSMA, if two stations sense an idle channel and send at the same time, a collision occurs. Because CSMA has no collision detection, the stations carry on transmitting their whole damaged frames and the channel is wasted for the full frame time.

It is overcome with CSMA/CD: stations keep listening while sending, stop at once when a collision is detected, send a jam signal and retransmit after a random back-off. This saves the time that would be wasted.

A circuit-switched network sets up a dedicated physical path (or reserved channel) between sender and receiver before data transfer begins. The network does not inspect, interpret, buffer or modify the data on that path; it just passes the bits through at the agreed rate. Hence it places no restriction on the code, format, framing or protocol used by the end stations, so any bit stream is carried unchanged. This property is called bit-stream (code and protocol) transparency.

(255.255.254.0)

A class B network has 16 host bits. 100 subnets need 7 subnet bits ($2^7 = 128 \ge 100$), leaving $16-7=9$ host bits, which give $2^9-2 = 510 \ge 500$ usable hosts. The mask therefore has $16+7 = 23$ network bits: 255.255.254.0.

UDP is used where speed and low overhead matter more than reliability, or where a small request-reply is exchanged:

• Real-time multimedia: VoIP, video conferencing, live streaming, online games (late packets are useless, retransmission is pointless).
• Query-response services such as DNS, DHCP, SNMP, TFTP.
• Broadcast and multicast applications, since UDP is connectionless.

• Within the same domain (autonomous system): interior gateway protocols (intra-domain routing) such as RIP, OSPF and IGRP.
• Between different domains: exterior gateway protocols (inter-domain routing), mainly BGP (earlier EGP).

The native protocol of the WWW is HTTP (HyperText Transfer Protocol). It is an application-layer, client-server, request-response protocol that runs over TCP (port 80; HTTPS uses 443). It is stateless, since the server keeps no memory of earlier requests.

Justification. A WAN spans cities or countries and is built by joining many LANs and sub-networks using routers and leased/switched links. Each LAN may use its own topology (bus, star, ring), and the routers are interconnected in a mesh or partial-mesh pattern. Because several different topologies are combined in one network, a WAN is a hybrid topology.

Simple design

• LAN A (star) connects to router R1.
• LAN B (bus) connects to router R2.
• LAN C (ring) connects to router R3.
• R1, R2 and R3 are joined to each other (and to further routers) by point-to-point links, forming a mesh in the backbone.

Working principle

1. A host sends its data to the local router (the gateway) in packets.
2. The router reads the destination address and consults its routing table, which is built by routing protocols such as RIP, OSPF or BGP.
3. The packet is forwarded hop by hop over the carrier links (leased line, frame relay, ATM, MPLS, etc.) using packet switching, store-and-forward.
4. The last router delivers the packet to the destination LAN and host.
5. Alternate paths in the mesh give reliability: if a link fails, routers choose another route.

Time Division Multiplexing (TDM) is a digital multiplexing technique in which several low-rate signals share one high-rate link by occupying it in turn, each for a fixed time slot. It has two types.

1. Synchronous TDM

Each input is assigned a fixed time slot in every frame, whether or not it has data. The slots repeat in a cyclic order, and the receiver demultiplexes by slot position.

• Problem: wasted capacity. If a source is idle its slot goes empty, so the link is poorly utilised. Also all inputs must be synchronised, and framing bits are needed.

2. Asynchronous (statistical) TDM

Slots are given dynamically only to inputs that have data. Since the slot position no longer identifies the source, every slot carries an address (header) identifying the sender.

• Problem: overhead of address bits in each slot, and extra complexity of buffering and control. If the load is higher than the link capacity, buffers overflow and data is delayed or lost.

Working principle. Selective Repeat ARQ is a sliding-window protocol in which the sender transmits several frames without waiting for acknowledgement (window size up to $2^{m-1}$ for $m$-bit sequence numbers). The receiver also has a window and accepts frames that arrive out of order, buffering them. Each frame is acknowledged individually. If a frame is damaged or lost, the receiver sends a NAK (or the sender's timer for that frame expires), and only that frame is retransmitted. When the missing frame arrives, the receiver delivers all buffered frames to the network layer in correct order.

Merit over Go-Back-N: Only the erroneous frame is retransmitted, so bandwidth is used efficiently, especially on noisy or high-delay links.

Demerit over Go-Back-N: The receiver needs a buffer and logic to store and reorder out-of-order frames, and the sender needs a timer per frame, so it is more complex and costly. Window size is limited to half the sequence-number space.

In pure ALOHA a station sends a frame whenever it has one, so a frame collides with any other frame transmitted during the vulnerable period of two frame times ($2T_{fr}$). Maximum throughput is only $S = Ge^{-2G}$, with maximum $\frac{1}{2e} \approx 18.4\%$ at $G = 0.5$.

In slotted ALOHA, time is divided into slots equal to one frame time, and a station may transmit only at the start of a slot. Frames either collide completely or do not collide at all, and the vulnerable period is reduced to one frame time ($T_{fr}$). Throughput becomes $S = Ge^{-G}$, with maximum $\frac{1}{e} \approx 36.8\%$ at $G = 1$.

Thus slotted ALOHA halves the collision probability and doubles the maximum throughput, which is why it is an improvement (at the cost of needing clock synchronisation).

Shortest path routing finds the least-cost path between a source and destination, where "cost" may be a metric such as hop count, distance, delay or monetary cost. The logic is to model the subnet as a weighted graph (routers are nodes, links are edges) and select the path with the least total weight. The main logics are:

1. Shortest by number of hops. Every link has weight 1; the path with the fewest routers is chosen. Example: A to D via A-B-D (2 hops) is preferred to A-B-C-D (3 hops).

2. Shortest by distance. Weights are physical lengths of links. Example: A-C-D with 3 + 4 = 7 km beats A-B-D with 5 + 6 = 11 km.

3. Shortest by delay / bandwidth / cost. Weight is a mean queuing and transmission delay, or the inverse of the bandwidth, or tariff, and the lowest sum is chosen. Example: if A-B-D has delays 10 ms and 20 ms (30 ms) and A-C-D has 15 ms and 5 ms (20 ms), A-C-D is chosen even if it has the same hop count.

A weighted combination of these metrics can also be used. The path is computed by an algorithm such as Dijkstra's: label the source 0 as permanent, relax the tentative labels of its neighbours, make the smallest tentative label permanent, and repeat until the destination is permanent.

IP address. An IP address is a logical, hierarchical address that uniquely identifies a host's connection to the Internet. IPv4 addresses are 32 bits long, written in dotted decimal (e.g. 192.168.1.10), and consist of a network part (netid) and a host part (hostid).

IPv4 datagram (frame) format. A datagram has a header (20 to 60 bytes) followed by data. The header fields are:

• Version (4 bits): IP version, 4.
• IHL / header length (4 bits): header length in 32-bit words (min 5).
• Type of service (8 bits): priority and delay/throughput/reliability preferences.
• Total length (16 bits): header plus data, up to 65,535 bytes.
• Identification (16 bits): identifies fragments of the same datagram.
• Flags (3 bits): DF (do not fragment), MF (more fragments).
• Fragment offset (13 bits): position of the fragment in the original datagram.
• Time to live (8 bits): hop limit, decremented by each router; the datagram is discarded at 0.
• Protocol (8 bits): upper-layer protocol (6 = TCP, 17 = UDP, 1 = ICMP).
• Header checksum (16 bits): error detection over the header only.
• Source address (32 bits) and destination address (32 bits).
• Options (variable) and padding: security, record route, timestamp, etc.
• Data: payload from the transport layer.

DHCP (Dynamic Host Configuration Protocol) automatically assigns IP configuration (IP address, subnet mask, default gateway, DNS server) to hosts. A DHCP server can allocate addresses in three ways:

1. Manual (static) allocation: The administrator maps a host's MAC address to a fixed IP address in the server. The host always receives the same address.
2. Automatic allocation: The server assigns an IP address from its pool the first time the host connects, and the host keeps that address permanently.
3. Dynamic allocation: The server leases an address from the pool for a limited time. When the lease expires (or the host releases it) the address returns to the pool and can be reused. This is the most common method since it reuses a limited address space.

Process (DORA): the client broadcasts DHCP Discover; the server replies with DHCP Offer; the client sends DHCP Request for the offered address; the server confirms with DHCP Acknowledgement. The client renews the lease before it expires.

The transport layer provides process-to-process (end-to-end) delivery. Its services are:

1. Process-to-process communication: Using port numbers, data is delivered to the correct application process on the host, not just to the host.
2. Segmentation and reassembly: Messages from the application are split into segments with sequence numbers and reassembled at the destination.
3. Connection control: Connection-oriented service (TCP) sets up, maintains and releases a connection; connectionless service (UDP) sends each segment independently.
4. Flow control: Prevents a fast sender from overwhelming a slow receiver, using a sliding window end to end.
5. Error control: Detects damaged, lost, duplicate or out-of-order segments using checksums, acknowledgements and retransmission.
6. Congestion control: Regulates the sending rate to avoid overloading the network.
7. Multiplexing and demultiplexing: Several applications share one network connection; the transport layer multiplexes at the sender and demultiplexes at the receiver by port number.
8. Addressing: Service access points (ports) and socket addresses identify the applications.

The Domain Name System (DNS) is a distributed, hierarchical database that translates human-friendly host names (e.g. www.example.com) into IP addresses.

Architecture

• Name space: a tree with the root at the top, then top-level domains (.com, .edu, .np, ...), second-level domains and so on. A domain name is the path read from the node up to the root.
• Root servers: know the addresses of the TLD servers.
• TLD servers: know the authoritative servers of each second-level domain.
• Authoritative name servers: hold the actual records (A, MX, NS, CNAME) of a zone.
• Local (resolver) name server: the client's own server, which accepts queries and does the lookup, caching results.

Working

1. An application calls the resolver on the host with a name.
2. The resolver asks the local name server.
3. If it is not in its cache, the local server asks a root server, which refers it to the TLD server, which refers it to the authoritative server (iterative queries; recursive query is also possible).
4. The authoritative server returns the IP address.
5. The local server caches it (for the record's TTL) and replies to the host, which then connects using the IP address.

• Bit rate is the number of bits transmitted per second (bps).
• Baud rate (signalling rate) is the number of signal units (signal changes) per second.

They are related by $\text{bit rate} = \text{baud rate} \times \text{bits per signal element}$. They are equal only when each signal element carries one bit; with multi-level signalling (e.g. 4 levels carrying 2 bits) the bit rate is greater than the baud rate.

The basic characteristics of a signal are:

• Amplitude: the peak value (strength) of the signal.
• Frequency: number of cycles per second (Hz); the inverse of the period.
• Period: time for one cycle.
• Phase: position of the waveform relative to time zero.
• Wavelength: distance covered by one cycle.
• Bandwidth: the range of frequencies the signal occupies.

Shannon's theorem gives the maximum data rate (channel capacity) of a noisy channel:

$C = B \log_2\left(1 + \frac{S}{N}\right)$

where $C$ is the capacity in bits per second, $B$ the bandwidth in Hz, and $S/N$ the signal-to-noise power ratio. Error-free transmission is theoretically possible at any rate below $C$, but not above it.

A bridge connects two or more LAN segments at the data link layer and makes them work as one network. It filters traffic by learning MAC addresses: a frame is forwarded to another segment only if the destination is there, otherwise it is kept local. This divides the network into separate collision domains, reduces traffic and collisions, extends the network's size and number of stations, and can connect LANs of different types.

Asynchronous communication is a transmission mode in which data is sent one character (or byte) at a time without a shared clock between sender and receiver. Each character is framed by a start bit and one or more stop bits, which let the receiver synchronise for that character, and gaps of arbitrary length may occur between characters. It is simple and cheap but has high overhead (about 20 percent for 8-bit data) and is used for keyboards and serial ports.

A socket address is the combination of an IP address and a port number. It uniquely identifies a process running on a host, and a pair of socket addresses (source and destination) identifies a connection.

Example: 192.168.10.5:80 means port 80 (a web server) on the host with IP 192.168.10.5.

An IP address identifies only the host (or its interface), but many applications run on one host at the same time (web browser, e-mail, file transfer). The port address (16-bit number) identifies the particular process or service, so the transport layer can deliver incoming data to the correct application, and so multiple applications can use the network simultaneously (multiplexing). Well-known ports such as 80 (HTTP) and 25 (SMTP) also let clients locate services.

DNS (Domain Name System) maps human-readable domain names to IP addresses (and the reverse), so users do not need to remember numeric addresses. It is a distributed, hierarchical database of name servers. It also supplies other information such as mail server records (MX) and aliases (CNAME).

The type of network is decided mainly by the following factors:

1. Geographical area covered: LAN covers a room, building or campus (up to a few km); MAN covers a city (about 5 to 50 km); WAN covers countries or continents.
2. Ownership and management: a LAN is privately owned by one organisation; a MAN may be private or public; a WAN is typically built from public carriers' links and is often shared.
3. Data rate and delay: LANs have high speed (10 Mbps to Gbps) and low delay; MANs are medium; WANs have lower speeds and larger delay.
4. Transmission media and technology: LANs use twisted pair, coaxial or fibre with Ethernet or token ring; MANs use fibre, DQDB or FDDI; WANs use leased lines, satellite, microwave, ATM or frame relay with routers.
5. Error rate: LANs have low error rates; WANs have higher error rates.
6. Cost and number of connected stations.

Using Shannon's formula $C = B\log_2(1 + S/N)$.

Convert SNR from decibels:

$\frac{S}{N} = 10^{40/10} = 10^4 = 10000$

Then

$C = 3600 \times \log_2(1 + 10000) = 3600 \times \log_2(10001) \approx 3600 \times 13.288 \approx 47{,}836 \text{ bps}$

The theoretical information rate is about 47.8 kbps.

The TCP/IP model is the protocol suite on which the Internet is built. It has four layers (some texts show five by splitting the lowest layer).

1. Host-to-network (Network access) layer: Defines how data is physically sent over the local network. It handles framing, physical addressing (MAC), media access and transmission of bits (Ethernet, Wi-Fi, PPP). It covers the OSI physical and data link layers.

2. Internet layer: Provides logical addressing and routing of packets across networks, independent of the medium. Protocols: IP, ICMP, ARP, RARP, IGMP. It gives connectionless, best-effort delivery.

3. Transport layer: Provides end-to-end, process-to-process delivery with port addresses. TCP gives reliable, connection-oriented delivery with segmentation, flow control, error and congestion control; UDP gives unreliable, connectionless delivery.

4. Application layer: Provides services to the user and applications, combining OSI session, presentation and application layers. Protocols: HTTP, FTP, SMTP, Telnet, DNS, DHCP, SNMP.

Data moves down the layers at the sender, each layer adding its header (encapsulation), and up at the receiver where headers are removed.

Why CSMA/CD is unsuitable

• CSMA/CD needs a station to detect a collision while it is transmitting. A wireless radio cannot transmit and listen at the same time on the same channel, since its own signal overwhelms the weak incoming signal.
• Because of the hidden terminal problem (two stations out of each other's range both send to a common receiver) and the exposed terminal problem, a station cannot reliably sense whether the channel is busy at the receiver. Collisions occur at the receiver and are not heard by the senders.
• Signal fading and limited range mean not every station hears every other station.

Suitable protocol: CSMA/CA (IEEE 802.11 DCF)

1. The station senses the channel. If it is idle for a DIFS period, it transmits (otherwise it waits and uses a random backoff counter that counts down only while the channel is idle).
2. Optionally, the sender sends a short RTS (request to send); the receiver replies with CTS (clear to send). Other stations hearing the RTS or CTS set their NAV (network allocation vector) and keep silent for the duration, which solves the hidden terminal problem.
3. The data frame is sent, and the receiver replies with an ACK after SIFS. If no ACK arrives, the sender assumes a collision, increases its backoff window and retries.

i. Class: The first octet is 198, which lies in 192 to 223, so it is Class C (default mask 255.255.255.0, 8 host bits).

ii. Hosts per subnet: For 6 subnets we need $n$ bits with $2^n \ge 6$, so $n = 3$ (8 subnets). Host bits left: $8 - 3 = 5$.

$\text{Valid hosts per subnet} = 2^5 - 2 = 30$

iii. Subnet mask: Network bits = $24 + 3 = 27$. The last octet is 11100000 = 224, so the mask is 255.255.255.224 (/27).

TCP is preferred when reliable, ordered delivery of all data matters more than speed or low overhead.

Reasons

• Reliability: TCP uses sequence numbers, acknowledgements, checksums and retransmission, so lost or corrupted segments are recovered. UDP gives no such guarantee.
• Ordered delivery: segments are reassembled in order at the receiver.
• Flow control and congestion control: the sliding window and congestion algorithms prevent overloading the receiver and the network.
• Connection-oriented: a connection is set up with a three-way handshake and closed properly, suitable for long sessions.

Typical uses: web browsing (HTTP/HTTPS), e-mail (SMTP, POP3, IMAP), file transfer (FTP), remote login (SSH, Telnet), banking and database transactions. In these, losing even one byte makes the data useless or incorrect.

UDP is preferred only for delay-sensitive or simple request-reply applications such as voice, video and DNS.

Role. A DHCP (Dynamic Host Configuration Protocol) server automatically gives hosts the network configuration they need: an IP address, subnet mask, default gateway and DNS server addresses. It removes manual configuration, avoids address conflicts, and lets a limited pool of addresses be reused by leasing them for a limited time. It is an application-layer, client-server protocol using UDP (server port 67, client port 68).

Working (DORA)

1. Discover: a new host (with no IP) broadcasts a DHCPDISCOVER message to find a server.
2. Offer: a server replies with DHCPOFFER containing an unused address from its pool, with mask, gateway, DNS and lease time.
3. Request: the client broadcasts DHCPREQUEST to accept the offer (which also tells other servers it was declined).
4. Acknowledge: the server sends DHCPACK confirming the lease; the client configures its interface.

The client renews the lease before it expires, or sends DHCPRELEASE when finished, returning the address to the pool. If the server and clients are on different networks, a relay agent forwards the messages.

Adaptive routing. Routing decisions change dynamically as the network topology and traffic (load) change. Routers exchange information and recompute routes periodically. Examples: distance vector and link state routing. It responds to failures and congestion but is more complex.

Non-adaptive (static) routing. Routes are computed in advance and loaded into routers at boot time; they do not change with the current traffic or topology. Examples: shortest path routing, flooding. It is simple but cannot react to failures or congestion.

Shortest path algorithm (Dijkstra). The subnet is a weighted graph; the aim is the least-cost path from a source to all other nodes.

1. Mark the source with distance 0 (permanent); all others have distance infinity (tentative).
2. For the node just made permanent, update the tentative distance of each neighbour: $d(v) = \min(d(v), d(u) + w(u,v))$.
3. Make the tentative node with the smallest distance permanent.
4. Repeat until the destination is permanent; the path is traced back through predecessors.

Example. Edges: A-B = 2, A-C = 5, B-C = 1, B-D = 4, C-D = 1. From A:

• Start: A = 0. Neighbours: B = 2, C = 5.
• Fix B (2): C becomes min(5, 2+1) = 3, D = 2+4 = 6.
• Fix C (3): D becomes min(6, 3+1) = 4.
• Fix D (4).

The shortest path from A to D is A-B-C-D with cost 4.

Signals are modulated, that is, a low-frequency baseband signal is impressed on a high-frequency carrier, because:

• Efficient radiation needs antenna size comparable to the wavelength, and high carrier frequencies make antennas practical.
• It allows frequency-division multiplexing, so many signals share one medium without interference.
• The signal is matched to the passband of the channel (e.g. a digital signal over a telephone line, or radio spectrum).
• It reduces noise and interference and allows longer-distance transmission.

Advantages of optical fibre:

• Very high bandwidth and data rate (Gbps to Tbps).
• Low attenuation, so long distances need fewer repeaters.
• Immune to electromagnetic interference and crosstalk.
• Greater security, as tapping is difficult.
• Light weight and small diameter compared with copper cable.
• Resistant to corrosion and does not cause electrical hazards or sparks.

Piggybacking improves the efficiency of bidirectional data transfer. Instead of sending a separate acknowledgement frame, the receiver delays the ACK and attaches it to the next outgoing data frame going in the same direction. This saves bandwidth and reduces the number of frames, as the ACK uses only a few bits in the data frame header.

ARQ (Automatic Repeat reQuest) corrects errors by retransmission. The receiver detects errors in a frame (using CRC or checksum). If the frame is correct, it sends an acknowledgement (ACK); if it is damaged, it sends a NAK or discards it silently. The sender keeps a copy and a timer for each frame, and if no ACK arrives before the timer expires (or a NAK arrives) it retransmits the frame. Stop-and-Wait, Go-Back-N and Selective Repeat are ARQ schemes.

Time Division Multiplexing (TDM) is preferred in digital transmission. Digital signals are naturally divided into time units (bits or bytes), so each source can be given its own time slot on the shared high-speed link. TDM uses the full link bandwidth in each slot, needs no guard bands or analog filters, is less affected by noise and intermodulation, and is easy to implement with digital circuits (as in T1/E1 and SONET). FDM, by contrast, suits analog signals.

ARP (Address Resolution Protocol) is required because data is delivered on a LAN using the physical (MAC) address, while applications and IP use logical (IP) addresses. When a host knows only the IP address of the next hop, ARP broadcasts a request and the owner replies with its MAC address, which is then cached in the ARP table so the frame can be built.

The Time To Live (TTL) field in the IP header limits the life of a packet. Each router decrements it by 1; when it reaches 0 the packet is discarded and an ICMP Time Exceeded message is sent. This prevents packets from looping endlessly in the network.

CIDR (Classless Inter-Domain Routing) is used to avoid the waste of addresses and the growth of routing tables caused by classful addressing. It allows variable-length prefixes (e.g. 192.168.1.0/22) so blocks of the right size can be allocated, and several networks can be aggregated into one routing entry (route summarisation).

• Sending email: SMTP, TCP port 25 (587 for submission).
• Receiving email: POP3, TCP port 110, or IMAP, TCP port 143.

Private IPv4 ranges (RFC 1918):

• Class A: 10.0.0.0 to 10.255.255.255 (10.0.0.0/8)
• Class B: 172.16.0.0 to 172.31.255.255 (172.16.0.0/12)
• Class C: 192.168.0.0 to 192.168.255.255 (192.168.0.0/16)

The basic communication model has five components:

1. Source: generates the data to be transmitted (e.g. a computer or phone).
2. Transmitter: converts the data into signals suitable for the transmission medium (e.g. a modem).
3. Transmission system: the medium or network (wire, fibre, radio, or a network of switches) that carries the signal.
4. Receiver: converts the received signal back into data.
5. Destination: takes the incoming data (e.g. a computer or printer).

Data flows from source to transmitter, across the transmission system, to the receiver and finally the destination. The message, sender, receiver, medium and protocol are the five essential elements, with protocols defining the rules that make the exchange meaningful. Noise on the medium may corrupt the signal, so error control is needed.

Divisor $x^3+1$ is $1001$ (degree 3), so append 3 zeros to the data: $11000011000$.

Divide modulo 2:

• 1100 XOR 1001 = 0101, bring down: 1011 XOR 1001 = 0010, bring down: 0100 (leading 0, shift), 1000 XOR 1001 = 0001, then bring down remaining bits: 0010, 0100, 1001...

Carrying out the full long division of $11000011000$ by $1001$ gives quotient $10000101$... and remainder $000$.

Check: $D\cdot x^3 = x^{10}+x^9+x^4+x^3$. Since $x^3\equiv 1$ mod $(x^3+1)$, $x^{10}\equiv x$, $x^9\equiv 1$, $x^4\equiv x$, $x^3\equiv 1$, so the remainder is $x+1+x+1=0$.

CRC = $000$, so the transmitted frame is

$11000011\,000 = 11000011000$

Network Address Translation (NAT) maps private (non-routable) IP addresses inside a network to one or more public IP addresses, so many hosts can share a limited number of public addresses. It conserves IPv4 addresses and hides the internal network.

Working: A NAT router keeps a translation table. For an outgoing packet it replaces the private source address (and port) with its public address (and a unique port) and records the mapping. For the reply, it looks up the table and rewrites the destination back to the private host.

Types:

• Static NAT: one-to-one fixed mapping.
• Dynamic NAT: private addresses mapped from a pool of public addresses.
• PAT / NAT overload: many private hosts share one public address, distinguished by port numbers.

Drawback: breaks end-to-end addressing and complicates some protocols (e.g. IPsec, peer-to-peer).

Distance vector routing (Bellman-Ford): each router keeps a table of the best known distance (cost) and next hop to every destination. Periodically, each router sends its whole table only to its directly connected neighbours. A router receiving a vector updates its table using

$D_x(y)=\min_v\{c(x,v)+D_v(y)\}$

where $c(x,v)$ is the cost to neighbour $v$ and $D_v(y)$ is $v$'s advertised distance to $y$. Repeating this converges to the least-cost routes. RIP is an example. Problems: slow convergence and count-to-infinity.

Difference from shortest path (link-state/Dijkstra) routing:

Ethernet uses CSMA/CD (Carrier Sense Multiple Access with Collision Detection).

Working principle:

1. Carrier sense: a station with a frame listens to the channel before sending.
2. If the channel is idle, it transmits; if busy, it waits until idle (1-persistent).
3. Collision detection: while transmitting, the station keeps listening. If the signal on the line differs from what it sent, a collision has occurred.
4. On collision, the station stops and sends a short jam signal so all stations know.
5. It then waits a random time using binary exponential backoff: after the $n$-th collision it picks $K$ randomly from $0$ to $2^n-1$ slot times and waits $K\times$ slot time before retrying.
6. After a maximum number of attempts (16) the frame is dropped and an error is reported.

For detection to work, the frame transmission time must be at least twice the propagation delay, so a minimum frame size (64 bytes in classic Ethernet) is required.

An IP address is a logical address that uniquely identifies a host's connection to a network. IPv4 addresses are 32 bits long, written in dotted decimal (e.g. 192.168.1.10), and divided into a network part and a host part.

IPv4 header (20 to 60 bytes):

 0       4       8              16   19                  31
+-------+-------+---------------+--------------------------+
| Ver   | IHL   | Type of Service|     Total Length        |
+-------+-------+---------------+-----+--------------------+
|        Identification         |Flags| Fragment Offset    |
+---------------+---------------+-----+--------------------+
|  Time to Live |   Protocol    |     Header Checksum      |
+---------------+---------------+--------------------------+
|                    Source IP Address                     |
+----------------------------------------------------------+
|                 Destination IP Address                   |
+----------------------------------------------------------+
|                 Options (if any) + Padding               |
+----------------------------------------------------------+

• Version (4 bits): 4 for IPv4.
• IHL (4 bits): header length in 32-bit words.
• Type of Service (8 bits): priority/QoS.
• Total length (16 bits): header plus data, up to 65535 bytes.
• Identification, Flags, Fragment offset: used for fragmentation and reassembly.
• TTL (8 bits): hop limit.
• Protocol (8 bits): upper-layer protocol (6 TCP, 17 UDP, 1 ICMP).
• Header checksum (16 bits): error detection on the header.
• Source and destination address (32 bits each).
• Options: optional, with padding to a 32-bit boundary.

DHCP (Dynamic Host Configuration Protocol) uses UDP, with port 67 at the server and port 68 at the client. It automatically assigns an IP address, subnet mask, default gateway and DNS server to hosts.

Working (DORA):

Client                                   DHCP Server
  | --- 1. DHCP Discover (broadcast) ------> |
  | <-- 2. DHCP Offer (IP, mask, lease) ---- |
  | --- 3. DHCP Request (accept offer) ----> |
  | <-- 4. DHCP Acknowledgement ------------ |

1. Discover: the new client broadcasts (source 0.0.0.0, destination 255.255.255.255) to find servers.
2. Offer: a server offers an unused IP address with configuration and lease time.
3. Request: the client broadcasts its acceptance of one offer, so other servers withdraw theirs.
4. Acknowledgement: the server confirms the lease and the client starts using the address.

The address is leased for a fixed time; the client renews at about 50% of the lease and releases it when no longer needed.

A LAN covers a small area (a room, building or campus) and is usually privately owned, with high data rates and low error rates and delay. A WAN spans cities, countries or continents, uses leased or public carrier links, and has lower speed, higher delay and higher cost.