Network and Data Communications

MAC address: a Media Access Control address is a 48-bit (6-byte) hardware address, burned into the network interface card (NIC) by the manufacturer. It is written in hexadecimal such as 00:1A:2B:3C:4D:5E; the first 3 bytes identify the manufacturer (OUI) and the last 3 the device. It identifies a device at the data link layer on a LAN.

CRC computation

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

Append 3 zeros: $1101011011\,000$. Divide by $1011$ using modulo-2 (XOR) division. Each time the leading bit is 1, XOR the generator into the 4 bits starting there (the working string changes in place):

The last three bits left are the remainder (CRC) $= 100$.

$\text{Transmitted frame} = 1101011011\,100 = 1101011011100$

Check: dividing $1101011011100$ by $1011$ leaves remainder $000$, so the receiver accepts it.

MAC address: a Media Access Control address is a unique 48-bit hardware address assigned by the manufacturer to a network interface card, written as six hexadecimal bytes (for example 00:1A:2B:3C:4D:5E). It identifies a device at the data link layer on a local network; the first 24 bits identify the manufacturer (OUI).

CRC computation

Message $= 1011011$, generator $x^3+x^2+1 \Rightarrow 1101$ (degree 3).

Append 3 zeros: $1011011\,000$. XOR the generator into 4 bits wherever the leading bit is 1:

The remainder (last three bits) is $001$.

$\text{Transmitted frame} = 1011011\,001 = 1011011001$

The receiver divides by $1101$; remainder $000$ means the frame is accepted.

Data: $1001100$ (7 bits). Generator $x^3+1$ gives divisor $1001$ (degree 3, so append 3 zeros).

Dividend: $1001100000$

Modulo-2 division (XOR the divisor in wherever the leading bit is 1):

1001100000
1001
----
0000100000
    1001
    ----
0000000100   -> remainder = 100

CRC (remainder) = 100

Transmitted frame = data + CRC = 1001100100

Check at the receiver: $1001100100 \div 1001$ gives remainder $000$, so no error is detected.

Data: $11011001$. The generator $x^3+x-1$ is taken modulo 2 (so $-1 \equiv +1$), i.e. $x^3+x+1$, giving divisor $1011$ (degree 3, so append 3 zeros).

Dividend: $11011001\,000$

Modulo-2 division by $1011$ (each line is the result after one XOR):

11011001000
1011
01101001000   (1101 ^ 1011 = 0110)
00110001000   (1101 ^ 1011 = 0110, window shifted)
00011101000
00001011000
00000000000   (1011 ^ 1011)

The remainder is 000, so CRC = 000.

Transmitted frame = data + CRC = 11011001000

Receiver check: the receiver divides the received frame $11011001000$ by $1011$. The remainder is $000$, so no error is detected and the data $11011001$ is accepted. If a bit were corrupted, e.g. $11011101000$, the remainder would be $111$ (non-zero) and the frame would be rejected.

Binary Amplitude Shift Keying (BASK) is a digital-to-analog modulation in which the amplitude of a carrier sine wave is changed according to the binary data, while its frequency and phase stay constant. Typically bit 1 is sent as the carrier with amplitude $A$ and bit 0 as zero amplitude (on-off keying), or a lower amplitude:

$s(t) = \begin{cases} A\cos(2\pi f_c t) & \text{for bit } 1 \\ 0 & \text{for bit } 0 \end{cases}$

The required bandwidth is $B = (1 + d)\,S$, where $S$ is the signal rate (baud) and $d$ the carrier-dependent factor ($0\le d\le 1$). BASK is simple to generate but very sensitive to noise, since noise changes amplitude.

Line coding of the bit sequence 11001010 (convention: in Manchester, bit 1 = low-to-high mid-bit transition, bit 0 = high-to-low; in Differential Manchester there is always a mid-bit transition, bit 0 = extra transition at the start of the bit, bit 1 = no transition at the start; the line is assumed low before the first bit)

(L = low level, H = high level.) Both codes have a transition in the middle of every bit, which gives self-synchronisation, and the signal rate is up to twice the bit rate.

Link state routing protocol features

• Each router discovers its neighbours and the cost of each link (using Hello packets).
• Each router builds a link state advertisement (LSA) about its own links and floods it to all routers in the area.
• Every router therefore holds the same link state database (a map of the whole topology).
• Each router independently runs Dijkstra's shortest path algorithm with itself as root to build its routing table.
• Updates are event-triggered (on topology change), with fast convergence and no routing loops. Examples: OSPF, IS-IS.

Finding the shortest path (Dijkstra)

1. Set the distance to the source as 0 and to all others as infinity; mark the source permanent.
2. Update the cost to all neighbours of the last permanent node.
3. Make the tentative node with the smallest cost permanent.
4. Repeat until all nodes are permanent.

Example: nodes A, B, C, D, E with link costs A-B 2, A-C 5, B-C 1, B-D 4, C-D 2, D-E 3. From A:

Shortest paths from A: B = A-B (2), C = A-B-C (3), D = A-B-C-D (5), E = A-B-C-D-E (8).

Disadvantages

• Requires more memory (full topology database) and CPU for running Dijkstra.
• Flooding of LSAs consumes bandwidth, especially initially.
• Complex to configure (areas, authentication).
• Inconsistent databases can cause temporary loops.

Stop-and-Wait ARQ is the simplest flow- and error-control protocol of the data link layer. The sender transmits one frame at a time and waits for an acknowledgement (ACK) before sending the next.

Design

• The sender keeps a copy of the sent frame and starts a timer.
• Frames and ACKs are numbered with 0 and 1 alternately (sequence number modulo 2), so that duplicates can be detected. The sender sequence number $S$ and receiver expected number $R$ are used; the ACK carries the number of the next frame expected.
• The receiver checks each frame (CRC). A good frame in order is accepted and ACKed; a corrupted frame is discarded silently; a duplicate is discarded but ACKed again.
• If the ACK does not arrive before the timer expires, the sender retransmits the frame.
• Sender window size = 1, receiver window size = 1.

Flow example

1. Sender sends Frame 0 and starts the timer. Receiver gets it and sends ACK 1. Sender receives ACK 1, stops the timer and sends Frame 1.
2. Frame 1 is lost. The timer expires, so the sender resends Frame 1; the receiver accepts it and sends ACK 0.
3. ACK 0 is lost. The timer expires and Frame 1 is resent; the receiver finds a duplicate, discards it and sends ACK 0 again. The sender then sends Frame 0.

Sender          Receiver
F0  ----------->        accepted
    <---------- ACK1
F1  --X (lost)
(timeout)
F1  ----------->        accepted
    <---------- ACK0

Efficiency: utilisation $= \dfrac{1}{1+2a}$ where $a=T_p/T_f$; it is poor on long, fast links because the channel is idle while waiting.

Noise, distortion and attenuation are three transmission impairments, i.e. causes of difference between the transmitted and received signal.

Network Address Translation (NAT) translates private (local) IP addresses into public (global) IP addresses at a router/firewall.

Why NAT is used

• Shortage of IPv4 addresses: many hosts in a private network share one or a few public addresses.
• Security: internal addresses are hidden from the outside world.
• Flexibility: the ISP or internal addressing can be changed without renumbering every host.

Types of NAT

1. Static NAT: one-to-one permanent mapping of a private address to a public address. Used for servers that must be reachable from outside.
2. Dynamic NAT: private addresses are mapped to a pool of public addresses on demand. The mapping is temporary, but the number of simultaneous users is limited to the pool size.
3. PAT (Port Address Translation / NAT overload): many private addresses share a single public address, distinguished by port numbers. This is the most common type used in homes and offices.

Example: host 192.168.1.5:3000 is translated to 203.0.113.4:40001, and the NAT table maps replies back.

Quality of Service (QoS) is the set of techniques that guarantee a certain level of network performance to a data flow. It is described by four characteristics: reliability, delay (latency), jitter (variation of delay) and bandwidth.

Techniques: scheduling (FIFO, priority queuing, weighted fair queuing), traffic shaping (leaky bucket, token bucket), admission control and resource reservation (RSVP, Integrated Services), and traffic classification and marking (Differentiated Services, DSCP).

Practical significance

• Real-time applications such as VoIP, video conferencing and online gaming need low delay and jitter; file transfer and email need reliability.
• It allows an ISP or organisation to prioritise critical traffic during congestion.
• It makes better use of limited bandwidth and supports service-level agreements (SLAs) with different charges for different service classes.
• It prevents one heavy user from starving others.

File Transfer Protocol (FTP) is an application layer protocol, based on TCP, for transferring files between a client and a server over a network (ports 20 and 21).

How it works

• FTP uses two separate TCP connections:
  • Control connection (port 21): stays open for the whole session. It carries commands (USER, PASS, LIST, RETR, STOR) and replies (e.g. 220, 230, 226).
  • Data connection (port 20 in active mode): opened for each file transfer and closed after it.
• Steps: the client opens the control connection and logs in with a username and password. The client sends a command such as RETR file. The server opens the data connection, sends the file, and closes it. The client can then send further commands or QUIT.
• Active mode: the server initiates the data connection to the client. Passive mode: the client initiates both, which works through firewalls.
• Transfer can be in ASCII or binary mode. Standard FTP sends data and passwords in plain text, so SFTP/FTPS is used for security.

Time Division Multiplexing (TDM) is a digital multiplexing technique in which several low-rate signals share one high-speed link by occupying the link in turn, each for a fixed time slot. The channel's time is divided into frames, each frame contains one slot per input.

Input 1 --\
Input 2 ---+--> [MUX] ==== | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | ... ====> [DEMUX] --> outputs
Input 3 --/                 <-- frame -->  <-- frame -->
Input 4 -/

Types

• Synchronous TDM: each input gets a fixed slot in every frame, even if it has no data (wasteful), so no address is needed. Sometimes framing bits are added for synchronisation.
• Statistical (asynchronous) TDM: slots are given only to inputs that have data, so each slot carries an address. It gives better link utilisation.

Features: with $n$ inputs each of rate $R$, the link rate is at least $nR$. Data may be interleaved by bit, byte or unit. It is used in digital telephone (T1/E1) systems. Disadvantage: with synchronous TDM, idle slots are wasted.

Open-loop congestion control

Open-loop control tries to prevent congestion before it happens, by good design, without feedback from the network. Decisions are made at the source or destination and do not depend on the current network state.

• Policies applied: retransmission policy, window policy, acknowledgement policy, discarding policy, admission policy.
• Traffic shaping algorithms (leaky bucket, token bucket) also belong to this group.
• Used in ATM and TCP-based networks as a first line of defence.

POP (Post Office Protocol)

POP3 is an application layer protocol (TCP port 110) used by an email client to retrieve mail from the mail server.

• The client connects, authenticates (USER/PASS), lists (LIST) and downloads (RETR) messages, and normally deletes them from the server (DELE).
• Follows a "download and delete" model, so mail is stored on a single device. It is simple and works offline.
• Sending is done by SMTP; IMAP is the alternative that keeps mail on the server.

Throughput

Frame transmission time: $T_{fr} = \dfrac{200\ \text{bits}}{200\ \text{kbps}} = 1\ \text{ms}$.

Frames per frame time: $G = 250 \times 0.001 = 0.25$.

For pure ALOHA: $S = G e^{-2G} = 0.25\,e^{-0.5} = 0.25 \times 0.6065 \approx 0.152$

So $S\approx 0.152$, i.e. $250\,e^{-0.5}\approx 152$ frames per second reach the destination successfully (about 15% of the channel capacity).

(If the network were slotted ALOHA: $S = Ge^{-G} = 0.25e^{-0.25} \approx 0.195$, about 195 frames/s.)

Vulnerable time of slotted ALOHA

In slotted ALOHA, time is divided into slots equal to one frame time and stations may start only at the beginning of a slot. A frame can collide only with another frame sent in the same slot, so the vulnerable time is one frame time:

$T_{vul} = T_{fr} = 1\ \text{ms (here)}$

This is half of pure ALOHA's vulnerable time ($2T_{fr}$), which is why the maximum throughput doubles from $18.4\%$ ($G=0.5$) to $36.8\%$ ($G=1$).

Noise vs attenuation

Collision-free requirement for pure ALOHA

Frame transmission time:

$T_{fr} = \frac{200\ \text{bits}}{50\ \text{kbps}} = 4\ \text{ms}$

In pure ALOHA a frame can collide with any frame sent from $T_{fr}$ before to $T_{fr}$ after its start, so the vulnerable time is

$T_{vul} = 2 \times T_{fr} = 2 \times 4 = 8\ \text{ms}$

To be collision free, no other station may send a frame during this 8 ms interval, i.e. each frame must be the only transmission within 8 ms. This means at most one frame can be generated per 8 ms, i.e. an offered load of at most $1/0.008 = 125$ frames/s with perfect coordination among stations.

Congestion control refers to the techniques and mechanisms used to prevent congestion from occurring, or to remove it once it has happened. Congestion occurs when the load (number of packets sent) on the network exceeds its capacity, causing queues to grow, delay to increase, packets to be dropped and throughput to fall.

How it can be handled

1. Open-loop (prevention): policies are designed so that congestion does not occur. These are retransmission policy, window policy, acknowledgement policy, discarding policy and admission policy.
2. Closed-loop (removal): congestion is detected and then relieved, using feedback. Methods are back-pressure, choke packet, implicit signalling (source infers from delay/loss) and explicit signalling (e.g. ECN, forward/backward bits).

Acknowledgement policy

The receiver's acknowledgement policy affects congestion because ACKs are themselves traffic. The receiver may not acknowledge every packet; it can send one cumulative ACK for several packets, or send an ACK only when it has data to send (piggybacking) or when a timer expires. Fewer ACKs mean less load on the network. However, the receiver must not delay too long or the sender will time out and retransmit, adding more load.

Discarding policy

A router may discard less sensitive packets when congestion is likely to occur, so as to prevent it while keeping the quality of the message. For example, in audio transmission, low-priority packets can be dropped with only a small loss of quality. Also, in a Random Early Detection scheme, packets are dropped early as the queue grows so that senders slow down before the buffers overflow.

The OSI (Open Systems Interconnection) model divides network communication into seven layers. Its practical importance is that it gives a standard reference for designing protocols, lets vendors build interoperable products, makes troubleshooting easier by isolating faults to a layer, and lets each layer change independently of the others.

Data is encapsulated as it moves down the layers on the sender (data, segment, packet, frame, bits) and decapsulated at the receiver.

Circuit switching is a switching method in which a dedicated physical communication path (circuit) is established between the sender and receiver before data transfer and is kept for the whole conversation. It has three phases: connection setup, data transfer, connection teardown. The traditional telephone network (PSTN) uses it.

Advantages

• Dedicated path with guaranteed bandwidth and constant data rate.
• Low and constant delay once the circuit is set up, with no queuing and no packet reordering; suitable for real-time voice.
• Data arrives in order, with no header overhead on each unit.

Disadvantages

• Setup delay before communication starts.
• Inefficient: the channel stays reserved and idle during silences, so bandwidth is wasted.
• Blocking: if no free path exists, the call is rejected.
• Not suited to bursty data; a fixed data rate does not allow different speeds; failure of a link breaks the call.
• Costly for long-duration connections.

Example: when a laptop joins a Wi-Fi network it first uses DHCP to obtain, say, 192.168.1.25, mask 255.255.255.0, gateway 192.168.1.1 and DNS server 8.8.8.8. When the user then opens www.example.com, the laptop asks the DNS server, which returns the IP address 93.184.216.34, and the browser connects to it.

Reliable protocol

A reliable protocol guarantees that data is delivered correctly, completely and in order. It does this with sequence numbers, acknowledgements, error detection (checksum/CRC), retransmission after timeout or negative acknowledgement, and flow control. TCP, and data-link protocols such as Stop-and-Wait, Go-Back-N and Selective Repeat ARQ, are examples. The cost is extra overhead and delay.

Satellite network

A satellite network uses satellites in orbit as relay stations, with earth stations transmitting on the uplink and receiving on the downlink.

• Orbits: GEO (about 36,000 km, appears fixed, high delay of about 250 ms one way), MEO (e.g. GPS) and LEO (low delay, e.g. Starlink, Iridium).
• Uses: TV broadcasting, long-distance telephony, internet in remote areas, GPS navigation, weather forecasting.
• Advantages: wide coverage and broadcast capability, independent of terrestrial infrastructure.
• Disadvantages: high propagation delay, high launch cost and signal fading by weather.

The leaky bucket algorithm is a traffic-shaping technique that turns bursty traffic into a smooth, constant-rate output stream.

Concept: imagine a bucket with a small hole at the bottom. Water (packets) may be poured in at any rate, but it leaks out at a constant rate. If the bucket is full, extra water overflows (packets are discarded).

Algorithm

1. A host sends packets into a queue (the bucket) of finite capacity.
2. If the queue has room, the packet is stored; otherwise it is discarded.
3. At every clock tick, a fixed amount of data (one packet or $n$ bytes) is removed from the queue and sent into the network.

Example: bucket capacity 1000 bytes, output rate 200 bytes per tick. A host sends bursts of 600, 600, 100 bytes in the first three ticks.

The network always sees at most 200 bytes per tick, no matter how bursty the input. If at tick 2 the arrival had been 800, then $400+800=1200>1000$ and 200 bytes would be dropped. Limitation: it does not credit idle time; the token bucket does.

Bit sequence: 1 0 0 1 1 1 0 0 1. Conventions used: high = positive level, low = negative level.

NRZ-L (level): the level directly represents the bit; 1 = high, 0 = low.

NRZ-I (invert on ones): a 1 causes a transition (inversion) at the start of the bit; a 0 keeps the previous level. The initial level is assumed low.

NRZ-L suffers from loss of synchronisation in long runs of 0s or 1s; NRZ-I only for long runs of 0s.

Link state routing: every router learns the whole topology and independently computes the shortest path to every destination.

Working

1. Learn neighbours: each router sends Hello packets and finds the cost of its links.
2. Build LSA: it creates a link state advertisement listing its neighbours and link costs.
3. Flood: the LSA is sent to all routers, so all routers hold an identical link state database.
4. Compute paths: each router runs Dijkstra's algorithm with itself as root and fills its routing table.
5. Whenever a link changes, a new LSA is flooded and the tables are recomputed. OSPF is the example protocol.

Example: routers A, B, C, D with link costs A-B 1, A-C 4, B-C 2, B-D 5, C-D 1. Dijkstra from A:

• A=0; neighbours B=1, C=4.
• Choose B (1): C = min(4, 1+2) = 3, D = 1+5 = 6.
• Choose C (3): D = min(6, 3+1) = 4.
• Choose D (4).

Routing table of A:

Recursive resolution is a DNS resolution method in which the client (resolver) asks its local DNS server for a complete answer, and that server takes full responsibility for obtaining it.

Process: the client sends a recursive query to its local DNS server. If the server does not have the answer in its cache, it queries a root server, then a TLD server (e.g. .com), then the authoritative server for the domain, each time following the referral. When it gets the IP address it caches it and returns it to the client. The client only sends one query and receives one final answer (or an error).

Advantages

• Simple for the client; resolver software on the host can be minimal.
• Caching at the resolving server speeds up later queries from all its clients and reduces traffic.
• Reduces the number of messages the client must send and its wait for intermediate results.
• Lets the server hide the complexity of the DNS hierarchy and apply policy/filtering.

Disadvantage: heavier load on the recursive server.

Message $= 10010001$, generator $G(x)=x^2+x+1 \Rightarrow 111$ (degree 2).

Append 2 zeros: $10010001\,00$. Modulo-2 (XOR) division by $111$: whenever the leading bit is 1, XOR the generator into the 3 bits starting there.

All other leading bits are 0 and need no XOR. The remainder (last two bits) is $11$.

$\text{CRC} = 11$

$\text{Transmitted frame} = 10010001\,11 = 1001000111$

The receiver divides the received frame by $111$; a zero remainder means no error was detected.

TDMA (Time Division Multiple Access) is a channel-access method in which the whole bandwidth of the channel is used by every station, but the time is divided into slots and each station is assigned its own slot in a repeating frame. A station transmits only during its slot, so no collisions occur.

Frame 1                          Frame 2
| S1 | S2 | S3 | S4 |   | S1 | S2 | S3 | S4 | ...
  ^guard times between slots

Features

• All stations (e.g. mobile phones) share one carrier frequency; each sends bursts in its own slot, then stays silent.
• Synchronisation is needed between stations and the base station, and guard times separate the slots to avoid overlap.
• Each frame also has preamble (address/synchronisation) bits.
• Used in GSM (8 slots per 200 kHz carrier), satellite networks and digital cellular systems.

Advantages: efficient use of bandwidth, flexible allotment of slots, battery saving since the phone is idle outside its slot. Disadvantages: strict synchronisation is needed and unused slots are wasted when a station has nothing to send.

Features of distance vector routing

• Each router knows only its own links and the distance (cost, e.g. hop count) to every destination, kept in a distance vector table.
• Each router periodically sends its whole table only to its directly connected neighbours (e.g. every 30 s in RIP).
• A router updates its table using the Bellman-Ford equation:

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

• Routing is "by rumour": routers trust what neighbours say. RIP is the example (maximum 15 hops, 16 = infinity).

Example: A-B cost 1, B-C cost 1, C-D cost 1.

Initially A knows only B(1). After B sends its table (A:1, C:1), A learns C = 1+1 = 2 via B. After C's table reaches B and is passed on, A learns D = 3 via B.

Disadvantages

• Slow convergence after a topology change.
• Count-to-infinity problem: if the link to D fails, B and C keep passing on bad information and the cost climbs slowly to infinity. Partial remedies are split horizon, poison reverse, hold-down timers and a small maximum hop count.
• Routing loops can form temporarily.
• Periodic full-table updates waste bandwidth; the hop limit makes it unsuitable for large networks.

Binary Phase Shift Keying (BPSK) is a digital-to-analog modulation in which the phase of the carrier is changed with the data while amplitude and frequency stay constant. For bit 1 the carrier is sent with phase $0^\circ$; for bit 0 with phase $180^\circ$:

$s(t) = \begin{cases} A\cos(2\pi f_c t) & \text{bit } 1 \\ A\cos(2\pi f_c t + \pi) = -A\cos(2\pi f_c t) & \text{bit } 0 \end{cases}$

It is much less affected by noise than ASK and needs no wider bandwidth than ASK; one signal element carries one bit, so bit rate equals baud rate. It is simple, but it needs a coherent carrier for detection.

Line coding of 111000110 (high = H, low = L; line low before the first bit)

In Differential Manchester there is always a mid-bit transition; bit 0 also has a transition at the start of the bit and bit 1 has none.

Selective Repeat ARQ is a sliding-window protocol in which the sender retransmits only the frames that are lost or damaged, and the receiver accepts and buffers out-of-order frames. It avoids the waste of Go-Back-N.

Design

• Sequence numbers use $m$ bits; the sender window size and receiver window size are both at most $2^{m-1}$ (so that new frames are not confused with old ones).
• Sender: transmits frames in its window, keeps a timer for each frame, and when the ACK arrives for the first frame in the window, slides the window. On a timeout (or NAK) only that frame is resent.
• Receiver: has a window of the same size. Any good frame within the window is accepted and stored, even if out of order, and an individual ACK (or NAK for a missing frame) is returned. Frames are delivered to the network layer in order only after all earlier ones have arrived. Frames outside the window are discarded (a duplicate gets an ACK again).

Flow example (window size 4, frames 0-3):

1. Sender sends F0, F1, F2, F3.
2. F1 is lost. The receiver accepts F0 and ACKs it, and receives F2 and F3 out of order, buffers them, and ACKs them (and may send NAK1).
3. The timer for F1 expires (or NAK arrives); the sender retransmits only F1.
4. The receiver gets F1, ACKs it, and now delivers F1, F2, F3 in order. The windows slide forward and F4-F7 can be sent.

Sender: F0 F1 F2 F3        F1 (resend)   F4 ...
          \  X  \  \         |
Receiver: ACK0     ACK2 ACK3 ACK1

It gives better throughput on noisy links, but it needs a larger buffer at the receiver and more complex logic.

Networks are categorised by their geographical size and scope.

1. PAN (Personal Area Network): a very small network (a few metres) around one person, linking devices such as phone, laptop and headset by Bluetooth or USB.
2. LAN (Local Area Network): covers a building, office or campus (up to a few km). It is privately owned, high speed (100 Mbps-10 Gbps), low error rate, and uses Ethernet or Wi-Fi with switches.
3. MAN (Metropolitan Area Network): covers a city (up to about 50-100 km). Used by cable TV networks, ISPs and to interconnect LANs of a city using fibre. Standard: DQDB (IEEE 802.6).
4. WAN (Wide Area Network): covers a country, continent or the world. It uses leased lines, satellites or public carriers, with lower speed and higher delay than a LAN. The Internet is the largest WAN.

Other types: CAN (campus) and SAN (storage area network), and VPN (virtual private network) over the public internet.

SNMP (Simple Network Management Protocol) is an application layer protocol (UDP ports 161 and 162) used to monitor and manage network devices such as routers, switches, servers and printers.

Components

• Manager (NMS): the management station that sends requests and receives data.
• Agent: software on each managed device that holds management data and answers the manager.
• MIB (Management Information Base): the database of objects (variables) on the device, each identified by an OID.
• SMI: rules for naming and defining the objects.

How it works

1. The manager sends GetRequest / GetNextRequest to ask an agent for a value (e.g. interface traffic, CPU load).
2. The agent replies with GetResponse.
3. The manager can change a value with SetRequest (e.g. disable a port).
4. When a significant event occurs, the agent itself sends a Trap (to port 162) to the manager without being asked.

Uses: fault detection, performance monitoring and configuration. SNMPv3 adds authentication and encryption.

IGMP (Internet Group Management Protocol) is the network layer protocol that lets hosts tell their local router which multicast groups they want to receive, so that the router forwards multicast traffic only where there are members.

Joining a group (IGMPv2)

1. A host wanting to receive group traffic (for example 224.0.1.10) sends an unsolicited Membership Report for that group address to the group address (TTL 1), and joins the corresponding multicast MAC group.
2. The router (the multicast router on the LAN) records that the interface has at least one member for that group and starts forwarding the group's datagrams onto the LAN, requesting the traffic from upstream with a multicast routing protocol (PIM, etc.).
3. Periodically the router sends a General Membership Query (to 224.0.0.1). Each group has one host reply with a Membership Report; other hosts hearing it suppress theirs after a random delay timer, to reduce traffic.
4. When a host leaves, it sends a Leave Group message; the router sends a group-specific query, and if no report arrives, it stops forwarding that group.

Message types: query, membership report, leave report. Version 3 also allows source filtering.

Reliable vs unreliable protocols

Error checking

A protocol detects errors by adding redundant bits to the data: parity check, checksum (TCP/UDP/IP, the ones-complement sum of 16-bit words) or CRC (data link layer, as in Ethernet). The receiver recomputes the check value; if it does not match, the data is discarded. A reliable protocol then recovers through retransmission (on a timeout or negative acknowledgement), whereas an unreliable one just drops the data. Forward error correction (e.g. Hamming code) can also correct errors without retransmission.

Packet switching divides a message into small units called packets, each with a header (source and destination address, sequence number), which are sent independently across the network and reassembled at the destination. It uses store-and-forward, and the links are shared by many users (statistical multiplexing).

Types and phases

• Datagram approach (connectionless): no setup. Every packet is routed independently using a routing table, so packets may take different paths and arrive out of order; the destination reorders them.
• Virtual-circuit approach (connection-oriented): it has three phases:
  1. Setup phase: a virtual path is established and a virtual circuit identifier (VCI) is allotted in each switch.
  2. Data transfer phase: all packets of the flow follow the same path, carrying only the short VCI.
  3. Teardown phase: the circuit entries are removed.

How it works: the sender splits the message into packets; each switch/router receives a packet fully, stores it in a queue, checks errors, looks up the next hop (routing table or VC table) and forwards it. At the destination the packets are reassembled in order.

Advantages: efficient bandwidth sharing, no setup delay in datagram, fault tolerance (alternative routes). Disadvantages: variable delay and jitter, packet loss during congestion, header overhead.

Frequency Division Multiplexing (FDM) is an analog multiplexing technique in which the total bandwidth of a link is divided into several non-overlapping frequency bands, and each input signal is modulated on a different carrier frequency and sent simultaneously on one link.

Input 1 --> [Mod f1] \                       / [Demod f1] --> Output 1
Input 2 --> [Mod f2]  >--> [Mux] ==link== [Demux] -- [Demod f2] --> Output 2
Input 3 --> [Mod f3] /                       \ [Demod f3] --> Output 3

Frequency:  | Ch1 | guard | Ch2 | guard | Ch3 |

Working: each signal modulates a different carrier (AM/FM); the modulated signals are combined into a composite signal, which is sent over the shared medium. At the receiver, band-pass filters separate the bands and demodulators recover the original signals. Guard bands between channels prevent interference (crosstalk).

Uses: AM/FM radio, television broadcasting, first-generation cellular phones, cable TV. Advantages: simple, many users at the same time. Disadvantages: needs wide bandwidth, noise and crosstalk affect it, and the link bandwidth is wasted if a channel is idle.

Frame size $=200$ bits. Because the frame rate and channel bandwidth are not given, take the standard values of a $200$ kbps channel producing $1000$ frames per second.

Frame time:

$T_{fr} = \frac{200}{200\,000} = 1\ \text{ms}$

Load: $G = 1000 \times 0.001 = 1$.

Throughput of pure ALOHA:

$S = G\,e^{-2G} = 1 \times e^{-2} = 0.135$

So the throughput is about $0.135 \times 1000 \approx 135$ frames per second reach the destination successfully; the rest collide (13.5% of the offered frames succeed). The maximum possible throughput of pure ALOHA is $18.4\%$ at $G=0.5$.

Vulnerable time of pure ALOHA: a frame can collide with any frame sent during one frame time before or after its start:

$T_{vul} = 2 \times T_{fr} = 2 \times 1\ \text{ms} = 2\ \text{ms}$

(In general $T_{vul}=2\times 200/\text{bit rate}$.)

(a) Shannon capacity

Shannon's theorem gives the maximum data rate (capacity) of a noisy channel with bandwidth $B$ Hz and signal-to-noise ratio $\text{SNR}$ (as a ratio, not in dB):

$C = B\log_2(1+\text{SNR})\ \text{bps}$

It is the theoretical upper limit; no coding scheme can give error-free transmission above it, and the value does not depend on the number of signal levels. Example: a channel with $B=3000$ Hz and SNR of $30$ dB ($1000$) gives $C = 3000\log_2 1001 \approx 29\,900$ bps. To increase capacity, increase bandwidth or SNR.

(b) Connectionless service

In a connectionless service, no connection is set up before data transfer. Each packet (datagram) carries the full destination address and is routed independently, so packets may be lost, duplicated or arrive out of order, and there is no acknowledgement or flow control. It is fast with small overhead and suits short or real-time exchanges. Examples: UDP and IP, DNS queries, postal mail analogy.

Given $192.168.2.0/24$ (256 addresses, 8 host bits). Each subnet needs 48 hosts.

Host bits needed: $2^6 - 2 = 62 \ge 48$, while $2^5-2 = 30 < 48$. So 6 host bits are required, and the prefix is $/26$ ($2$ bits borrowed, giving $2^2 = 4$ subnets).

Subnet mask: /26 $= 255.255.255.192$ (block size $256-192=64$).

Each subnet provides 62 usable hosts (at least 48 are required).

Advantages of subnetting

• Efficient use of IP addresses and less waste.
• Smaller broadcast domains, so less broadcast traffic and better performance.
• Improved security, since departments can be isolated and controlled with ACLs.
• Easier management and troubleshooting, and the problems stay local.
• Hides the internal structure from the outside, with smaller routing tables.

The TCP/IP protocol suite is the layered architecture on which the Internet runs. It has four layers (some books split the bottom layer to give five).

1. Application layer

• Provides network services directly to user programs; it combines the OSI application, presentation and session functions.
• Examples: HTTP/HTTPS (web), FTP (file transfer), SMTP/POP3/IMAP (e-mail), DNS (name resolution), DHCP, SNMP, Telnet/SSH.
• Data unit: message.

2. Transport layer

• Provides process-to-process (end-to-end) delivery using port numbers.
• TCP: connection-oriented, reliable, with sequencing, acknowledgements, flow control (sliding window) and congestion control.
• UDP: connectionless, unreliable and fast, with low overhead; used for DNS queries, streaming and VoIP.
• Data unit: segment (TCP) or datagram (UDP).

3. Internet (network) layer

• Handles logical (IP) addressing, routing and packet forwarding from source host to destination host across networks.
• Main protocol: IP (IPv4/IPv6). Supporting protocols: ICMP (error and control messages), ARP/RARP (address mapping), IGMP (multicast), and routing protocols (RIP, OSPF, BGP).
• Data unit: packet (datagram).

4. Network access (host-to-network / link) layer

• Covers the physical and data link functions: framing, physical (MAC) addressing, error detection, media access and the actual bit transmission over Ethernet, Wi-Fi, PPP, etc.
• Data unit: frame, then bits.

Encapsulation: each layer adds its own header as data moves down (message, then segment, then packet, then frame) and removes it at the receiver.

(a) Pure ALOHA vs slotted ALOHA

(b) Three network layer protocols

1. IP (Internet Protocol): the connectionless, best-effort delivery protocol. It provides logical addressing, fragmentation and reassembly, and routing of datagrams. It gives no guarantee of delivery or order.
2. ICMP (Internet Control Message Protocol): reports errors and gives diagnostics for IP, for example destination unreachable, time exceeded and redirect. Echo request/reply is used by ping and traceroute.
3. ARP (Address Resolution Protocol): maps a known IP address to the MAC address of a device on the same LAN. The sender broadcasts an ARP request and the owner of the IP replies with its MAC address. (RARP does the reverse.)

Other examples are IGMP (group management), OSPF and RIP (routing).

Bit sequence: 1 1 0 0 1 0 0 1 1 1

Conventions: NRZ-L: 1 is high (+), 0 is low (−). NRZ-I: the level inverts for a 1 and stays for a 0, starting from low. Differential Manchester: there is always a transition in the middle of a bit; a 0 gives an extra transition at the start of the bit and a 1 gives none, starting from a low previous level.

(a) NRZ-L (one level per bit):

(b) NRZ-I (invert on 1):

(c) Differential Manchester (first half then second half of each bit):

In the waveform, NRZ-L and NRZ-I have no mid-bit transitions and so can lose synchronisation on long runs. Differential Manchester has a mid-bit transition in every bit, so it is self-clocking.

Example: Suppose A is linked to B (cost 1) and B to C (cost 2). In distance vector, A learns about C only from B's table: $d(A,C)=d(A,B)+d(B,C)=1+2=3$. In link state, every router floods the link costs (A-B=1, B-C=2), builds the whole graph, and runs Dijkstra itself to find that the best path A to C is A-B-C with cost 3.

Purpose of DNS: The Domain Name System is a distributed, hierarchical database that translates human-readable domain names (e.g. www.example.com) into IP addresses (and back), so users need not remember numeric addresses. It also gives mail server (MX) information and other records. It runs over UDP/TCP port 53.

Name resolution process (for www.example.com):

1. The application asks the local resolver (stub), which first checks its own cache and the OS hosts file.
2. If not found, the query goes to the local/recursive DNS server (ISP or e.g. 8.8.8.8), which checks its cache.
3. If not cached, it queries a root server, which replies with the address of the .com TLD server.
4. It then queries the TLD server, which replies with the authoritative server for example.com.
5. It queries the authoritative server, which returns the A record (IP address) for www.example.com.
6. The recursive server caches the answer (for its TTL) and returns it to the client, which then connects to that IP.

Resolution can be recursive (the server does all the work for the client) or iterative (the server returns a referral to the next server to ask). Usually the client-to-local-server query is recursive and the local server uses iterative queries.

Guided media carry the signal along a physical path (wire or fibre).

1. Twisted pair cable

• Two insulated copper wires twisted together to reduce interference and crosstalk.
• UTP (unshielded) is cheap and common in LANs (Cat5e, Cat6); STP (shielded) has better noise resistance but costs more.
• Limit about 100 m; up to 1 to 10 Gbps depending on category.

2. Coaxial cable

• Central copper conductor, insulator, braided metal shield and outer jacket.
• Higher bandwidth and better noise immunity than twisted pair; used in cable TV, old Ethernet (10Base2/10Base5) and broadband.
• Types: baseband (50 ohm) and broadband (75 ohm).

3. Optical fibre

• Carries data as light pulses through a glass or plastic core with cladding (total internal reflection).
• Very high bandwidth, low attenuation, long distance, immune to electromagnetic interference and secure; costlier and harder to install.
• Single-mode (long distance, laser) and multimode (short distance, LED).

Fibre has the best performance, then coaxial, then twisted pair, while cost and installation difficulty rise in the same order.

Error control technique: Stop-and-Wait ARQ

Error control means detecting damaged or lost frames and recovering from them by retransmission (Automatic Repeat reQuest).

Working:

1. The sender transmits one frame (numbered 0 or 1) and starts a timer.
2. It waits for an acknowledgement before sending the next frame.
3. The receiver checks the frame (e.g. by CRC). If correct it sends an ACK carrying the number of the next expected frame; if damaged it discards the frame silently.
4. If the ACK does not arrive before the timer expires (lost frame, lost ACK or damaged frame), the sender retransmits the same frame.
5. The 1-bit sequence number lets the receiver recognise and discard a duplicate caused by a lost ACK.

Features: Simple and needs only one-frame buffers. But it is inefficient on long-delay links, since the link is idle while waiting; utilisation is $U = \dfrac{1}{1+2a}$ where $a = t_{prop}/t_{frame}$.

Improvements are Go-Back-N and Selective Repeat ARQ, which use a sliding window to keep the channel busy.

(a) Token Bucket

A traffic-shaping (congestion control) algorithm that allows bursts while limiting the average rate.

• Tokens are added to a bucket at a constant rate (say $r$ tokens per second) up to a maximum bucket size $b$; extra tokens are discarded.
• To send a packet (or a byte), the sender must remove a token. If no token is available, the packet waits (or is dropped/marked).
• If the sender has been idle, the bucket fills and a burst of up to $b$ packets can be sent at once; afterwards the rate falls to $r$.
• The maximum amount sent in time $t$ is $b + rt$.
• Unlike the leaky bucket (which gives a fixed output rate), the token bucket allows bursty output, and is used in QoS and traffic policing.

(b) SNMP (Simple Network Management Protocol)

An application layer protocol (UDP ports 161 and 162) used to monitor and manage network devices such as routers, switches and servers.

• Components: the manager (NMS), the agent running on the managed device, and the MIB (Management Information Base), the database of managed objects. SMI defines how objects are named and typed.
• Messages: GetRequest, GetNextRequest, SetRequest, GetResponse and Trap (an unsolicited alert from an agent).
• The manager polls agents for values (e.g. traffic counters, CPU load), changes configuration with Set, and receives traps on faults.
• Versions: SNMPv1, v2c, v3 (v3 adds authentication and encryption).

(a) Services of the Data Link Layer

1. Framing: dividing the bit stream from the network layer into frames, with start/end delimiters or length fields.
2. Physical (MAC) addressing: source and destination hardware addresses placed in the frame header.
3. Error control: detection (parity, checksum, CRC) and correction/retransmission (ARQ).
4. Flow control: stops a fast sender from overwhelming a slow receiver (stop-and-wait, sliding window).
5. Media access control: decides which station uses a shared channel (CSMA/CD, CSMA/CA, ALOHA, token passing).
6. Link management / connection services: connectionless or connection-oriented, reliable or unreliable delivery to the network layer.

(b) Shannon capacity

$C = B\log_2(1+\text{SNR})$

With $B = 5\times10^6$ Hz and SNR $= 1000$:

$C = 5\times10^6 \times \log_2(1001) \approx 5\times10^6 \times 9.967 \approx 49.8\times10^6 \text{ bps}$

Capacity is about 49.8 Mbps.

(a) Packet switched vs circuit switched networks

(b) OSI Reference Model layers (top to bottom)

7. Application: interface to the user; services such as e-mail, file transfer and web access (HTTP, FTP, SMTP).
8. Presentation: translation, encryption/decryption and compression of data (syntax).
9. Session: establishes, manages and terminates sessions; dialog control and synchronisation.
10. Transport: end-to-end (process-to-process) delivery, segmentation, flow and error control (TCP, UDP).
11. Network: logical addressing and routing of packets across networks (IP, routers).
12. Data link: framing, MAC addressing, error detection and media access, between adjacent nodes (switches, bridges).
13. Physical: transmission of raw bits over the medium; voltages, connectors, data rates, topology (hubs, cables).

(a) Why TCP is reliable

TCP guarantees delivery of data in order and without error. It does this by connection establishment (three-way handshake), sequence numbers on bytes, acknowledgements, retransmission of lost or damaged segments on timeout, checksums for error detection, duplicate removal, plus flow control (sliding window) and congestion control.

(b) Subnetting 192.168.1.0/24 into 8 subnets

Eight subnets need $2^3=8$, so borrow 3 bits: new prefix /27.

• Subnet mask: 255.255.255.224
• Block size: $256-224 = 32$ addresses per subnet (30 usable hosts).

Link State Routing is a routing algorithm in which every router learns the complete topology of the network and independently computes the shortest paths to all destinations.

Steps:

1. Discover neighbours: each router sends HELLO packets and learns its neighbours and the cost of each link.
2. Create a link state packet (LSP) listing its neighbours and link costs.
3. Flood the LSP to all routers in the area (each router forwards new LSPs on all other links).
4. Each router builds the same link state database (the full graph).
5. Each router runs Dijkstra's shortest path algorithm with itself as root to build its routing table.

Example: Network with links A-B = 2, A-C = 5, B-C = 1, B-D = 4, C-D = 1. Dijkstra from A:

• A = 0; B = 2 (via A); C = min(5, 2+1) = 3 (via B); D = min(2+4, 3+1) = 4 (via B, C).

Routing table at A:

When a link changes, only the affected LSP is flooded and routers recompute, giving fast convergence. OSPF and IS-IS are examples.

DHCP (Dynamic Host Configuration Protocol) is an application layer protocol that automatically assigns an IP address, subnet mask, default gateway and DNS server to hosts when they join a network (UDP ports 67 and 68), using the DORA steps: Discover, Offer, Request, Acknowledge.

DNS name resolution

DNS translates a domain name into an IP address. Example: a user enters www.tu.edu.np.

1. The browser checks its cache, then asks the local resolver; the OS checks its cache and hosts file.
2. The resolver forwards the query to the local (recursive) DNS server, which checks its cache.
3. If it is not there, the local server asks a root server, which answers with the address of the server for .np.
4. The local server then asks the .np server, which refers it to the server for edu.np, and so on until the authoritative server for tu.edu.np is reached.
5. The authoritative server returns the A record (the IP address), e.g. 202.x.x.x.
6. The local server caches the answer for its TTL and returns it to the client, which connects to that address.

Queries from client to local server are recursive; queries from the local server to the root, TLD and authoritative servers are iterative.

Unguided (wireless) media transmit electromagnetic waves through air or space without a physical conductor.

1. Radio waves (3 kHz - 1 GHz)

• Omnidirectional; they penetrate walls and travel long distances.
• Used in AM/FM radio, TV broadcasting, cellular phones, Wi-Fi and Bluetooth. Prone to interference.

2. Microwaves (1 - 300 GHz)

• Unidirectional, line-of-sight; need aligned antennas (towers, dishes).
• Terrestrial microwave links (a repeater about every 40-50 km) and satellite microwave links.
• Used in cellular networks, satellite communication, point-to-point links. Cannot penetrate walls well; affected by rain.

3. Infrared (300 GHz - 400 THz)

• Short range, line-of-sight; does not pass through walls (so little interference between rooms and good security).
• Used in remote controls, and short-range device-to-device transfer.

4. Satellite and laser / light waves (briefly)

• Satellites relay signals over very wide areas (GEO, MEO, LEO); laser/optical links give high bandwidth but need clear line of sight.

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

Conventions: Manchester: 1 is a low-to-high transition in mid-bit, 0 is high-to-low. NRZ-I: the level inverts on a 1 and stays for a 0, starting from low. NRZ-L: 1 is high (+), 0 is low (−).

(i) Manchester (first half, second half):

(ii) NRZ-I:

(iii) NRZ-L:

Noise, distortion and attenuation are the three main transmission impairments.

ALOHA is a random-access MAC protocol developed at the University of Hawaii for shared channels.

Pure ALOHA

• Any station transmits a frame whenever it has data.
• After sending, it waits for an acknowledgement (time-out $2\times$ maximum propagation delay). If none arrives it waits a random back-off time and retransmits.
• A frame collides with any other frame sent within one frame time before or after it, so the vulnerable time is $2T_{fr}$.
• Throughput $S = Ge^{-2G}$, with a maximum of about 18.4% at $G = 0.5$.

Slotted ALOHA

• Time is divided into slots of length $T_{fr}$; stations may transmit only at the start of a slot (needs clock synchronisation).
• Collisions are only complete overlaps within the same slot; the vulnerable time is $T_{fr}$.
• Throughput $S = Ge^{-G}$, with a maximum of about 36.8% at $G = 1$ (double that of pure ALOHA).

Diagram (time axis):

Pure ALOHA:     A: |==F1==|            |==F1'==|
                B:      |==F2==|          (overlap with F1 -> collision, both retransmit)

Slotted ALOHA:  slot:  |  1  |  2  |  3  |  4  |
                A:        F1                       (sent at slot start)
                B:        F2                       (same slot -> collision)
                B:                    F2'          (retransmitted in a later slot)

(a) Sliding Window Protocol

A flow and error control technique that allows the sender to transmit several frames before receiving an acknowledgement, keeping the channel busy.

• Frames are numbered with sequence numbers $0$ to $2^m-1$.
• The sender window is the set of frames that may be sent (or are sent and unacknowledged); the receiver window is the set of frames it can accept.
• When an ACK arrives, the sender window slides forward; when the receiver gets an in-order frame, its window slides.
• Window size: 1 in Stop-and-Wait, up to $2^m-1$ in Go-Back-N, and $2^{m-1}$ in Selective Repeat.
• Piggybacking of ACKs on data frames improves efficiency. TCP also uses a sliding window for flow control.

(b) HTTP (HyperText Transfer Protocol)

The application layer protocol of the World Wide Web, working on the client-server model over TCP (port 80; HTTPS uses port 443).

• The browser (client) sends a request (method such as GET, POST, PUT, DELETE, headers and optional body); the web server sends a response (status code like 200 OK or 404 Not Found, headers, body).
• It is stateless: each request is independent (cookies and sessions add state).
• HTTP/1.0 used a new connection per request; HTTP/1.1 has persistent connections; HTTP/2 multiplexes requests.

Go-Back-N ARQ

• The sender may send up to $N = 2^m-1$ frames (window size) without waiting for ACKs; the receiver window size is 1 (accepts only the next in-order frame).
• The receiver sends cumulative ACKs. If a frame is lost or damaged, the receiver discards it and all later frames.
• On time-out (or NAK) the sender goes back and retransmits the lost frame and every frame sent after it.

Sender:   0 1 2 3 4 5 ...
Frame 2 lost
Receiver: accepts 0,1; discards 3,4,5 (out of order), ACK 2 requested
Sender:   time-out -> resends 2 3 4 5

Simple receiver, but wasteful: good frames are resent.

Selective Repeat ARQ

• Sender and receiver windows are both $2^{m-1}$.
• The receiver accepts and buffers out-of-order frames, sending individual ACKs (or NAK for the missing one).
• Only the lost or damaged frame is retransmitted, and the receiver reorders before delivery.

Frame 2 lost
Receiver: accepts 0,1,3,4,5 (buffers 3,4,5), NAK 2
Sender:   resends only 2 -> delivers 2,3,4,5 in order

More efficient in bandwidth, but needs a more complex sender and receiver with buffers.

CRC example (message $1010001$, generator $x^3+x+1 = 1011$)

Append 3 zeros: $1010001000$. Dividing by $1011$ modulo 2 gives remainder $110$.

Transmitted frame = 1010001110

At the receiver: $1010001110 \div 1011$ gives remainder $000$, so the frame is accepted as error-free. If any bit were altered, the remainder would be non-zero and the frame would be discarded.

(a) Limitations of IPv4

1. Address exhaustion: the 32-bit address space (about 4.3 billion) is too small for today's devices.
2. Poor address allocation: the classful scheme wasted large blocks; NAT/CIDR are only workarounds.
3. Routing table growth: weak aggregation makes backbone routing tables large and slow.
4. No built-in security: IPsec is optional.
5. No built-in QoS or real-time support: the Type of Service field is rarely used.
6. Complex header: variable-length header with options and a checksum recomputed at each hop.
7. Configuration: manual or DHCP; no auto-configuration; broadcast-heavy (ARP).

(b) Layers of the TCP/IP suite

1. Application: user services and protocols (HTTP, FTP, SMTP, DNS, DHCP, SNMP).
2. Transport: process-to-process delivery by TCP (reliable, connection-oriented) and UDP (unreliable, connectionless), using port numbers.
3. Internet (Network): logical addressing and routing of packets with IP; ICMP, ARP, IGMP and routing protocols support it.
4. Network access (Link and Physical): framing, MAC addressing, error detection and transmission of bits over Ethernet, Wi-Fi, PPP, etc.

Why TCP is reliable (2 marks)

TCP delivers data correctly and in order using connection setup (three-way handshake), sequence numbers, cumulative acknowledgements, time-out based retransmission of lost segments, a checksum for corrupted segments, discarding of duplicates, and flow control with a sliding window.

Congestion (1 mark)

Congestion is a condition in which the load (number of packets) offered to a network or router exceeds its capacity, causing queue overflow, long delays and packet loss, and so a fall in throughput.

Congestion control mechanisms (7 marks)

Congestion control is divided into two kinds.

1. Open-loop (prevention): policies applied before congestion happens.

• Retransmission, window and acknowledgement policy, discarding policy and admission policy.
• Leaky bucket: packets leave at a constant rate, however bursty the input; excess is dropped when the bucket overflows.
• Token bucket: tokens accumulate at rate $r$ up to $b$; a packet needs a token, allowing bursts of up to $b$ and an average rate $r$.

2. Closed-loop (removal): reacting after congestion is detected.

• Backpressure: a congested node tells its upstream node to slow down.
• Choke packet: the router sends a message directly to the source asking it to reduce its rate.
• Implicit signalling: the source infers congestion from delays or lost packets.
• Explicit signalling: routers set bits in packets (e.g. ECN, FECN/BECN) to warn the source.

TCP congestion control uses a congestion window (cwnd) in addition to the receiver window:

• Slow start: cwnd starts at 1 MSS and doubles every RTT (exponential growth) until it reaches the threshold ssthresh.
• Congestion avoidance: beyond ssthresh cwnd grows by 1 MSS per RTT (additive increase).
• On loss: if a time-out occurs, ssthresh is set to cwnd/2 and cwnd drops to 1 (slow start restarts). On 3 duplicate ACKs (fast retransmit/fast recovery), ssthresh = cwnd/2 and cwnd continues from ssthresh (multiplicative decrease).

Noise is any unwanted signal (thermal noise, crosstalk, impulse noise, induced noise) that gets added to the transmitted signal in the medium and corrupts it, causing errors.

Attenuation is the loss of signal strength (energy) as the signal travels through the medium; it rises with distance and frequency and is measured in decibels. It is corrected using amplifiers or repeaters.

Shannon capacity

$C = B\log_2(1+\text{SNR})$

With $B = 10\times10^6$ Hz and SNR $= 2000$:

$C = 10^7\log_2(2001) \approx 10^7 \times 10.966 \approx 1.097\times10^8 \text{ bps}$

Capacity is about 109.7 Mbps.

Nyquist maximum rate (noiseless channel) with $L = 8$ levels and $B = 3500$ Hz:

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

Shannon maximum rate for SNR $= 25$ dB:

$\text{SNR} = 10^{25/10} = 10^{2.5} \approx 316.2$

$C = B\log_2(1+\text{SNR}) = 3500\times\log_2(317.2) \approx 3500\times8.309 \approx 29{,}083 \text{ bps}$

So the Nyquist limit is 21 kbps, and the maximum theoretical information rate (Shannon) is about 29.1 kbps. (A practical 8-level scheme is limited to the lower of the two figures, i.e. 21 kbps, on this channel.)

Principle of distance vector routing

Each router keeps a table (vector) giving the best known distance (cost) and next hop to every destination. Periodically, and when a change occurs, it sends its table to its directly connected neighbours only. On receiving a neighbour's table, a router applies the Bellman-Ford equation:

$d_x(y) = \min_v \{\, c(x,v) + d_v(y) \,\}$

and updates its table if a shorter route is found. Repeating this, all routers converge to the shortest paths. It is simple, but converges slowly and suffers from count-to-infinity (reduced by split horizon and poison reverse). RIP is an example.

Circuit switching vs packet switching

Network 192.168.15.0/28 gives the prefix length /28: mask $255.255.255.240$, so the block size is $256-240=16$ addresses per subnet (14 usable hosts). Taking 8 consecutive subnets of this size:

Subnet mask (all subnets): 255.255.255.240

The eight subnets together cover 192.168.15.0 to 192.168.15.127.

Network topology is the arrangement (physical or logical) of the nodes and links in a network, i.e. how devices are connected to each other.

1. Bus topology

• All devices connect to a single shared backbone cable with terminators at both ends.
• Cheap and easy to install and needs little cabling, but a break in the backbone brings down the network; performance falls with traffic and faults are hard to find.

2. Star topology

• Every device connects to a central hub or switch.
• Easy to install, manage and troubleshoot; failure of one cable affects only one device. But the central device is a single point of failure and more cable is needed.

3. Ring topology

• Each device connects to exactly two neighbours, forming a closed loop; data travels in one direction (often with token passing).
• Orderly access and predictable performance, but a single break or node failure can stop the ring (dual rings help) and adding nodes disrupts the network.

Others: mesh (fully or partly connected; reliable but costly), tree and hybrid.

IPv6 header fields (fixed 40 bytes)

1. Version (4 bits) = 6
2. Traffic Class (8 bits), for priority/QoS
3. Flow Label (20 bits), for flows needing special handling
4. Payload Length (16 bits)
5. Next Header (8 bits), the type of the next extension header or upper layer protocol
6. Hop Limit (8 bits), similar to IPv4 TTL
7. Source Address (128 bits)
8. Destination Address (128 bits)

IPv6 addressing

• Addresses are 128 bits, written as eight groups of four hex digits separated by colons, e.g. 2001:0db8:0000:0000:0000:ff00:0042:8329. Leading zeros can be dropped and one run of zero groups replaced by ::, giving 2001:db8::ff00:42:8329.
• Types: Unicast (one interface; global unicast 2000::/3, link-local FE80::/10, unique local FC00::/7), Multicast (FF00::/8; a group of interfaces), and Anycast (the nearest of a group of interfaces). There is no broadcast.
• The loopback address is ::1 and the unspecified address is ::.
• An address has a network prefix (e.g. /64) and an interface identifier, which can be auto-configured (SLAAC).

DNS (Domain Name System) is a distributed hierarchical database that maps domain names to IP addresses, using UDP/TCP port 53. The hierarchy is root, top-level domain (.com, .np), second-level domain (example) and so on, and each level is served by name servers.

Resolution of www.example.com:

1. The application asks the local stub resolver, which checks the browser/OS cache and the hosts file.
2. If not found, it sends a recursive query to the local (recursive) DNS server, which checks its cache.
3. The local server asks a root server, which refers it to the .com TLD servers.
4. It asks the TLD server, which refers it to the authoritative name server for example.com.
5. It asks the authoritative server, which returns the A record (IP address) of www.example.com.
6. The local server stores the answer in its cache for the TTL period and returns it to the client; the client connects to that IP address.

The client-to-local-server query is usually recursive, and the local server's queries to the root, TLD and authoritative servers are iterative. Caching reduces delay and load.

Transmission medium: the physical path between the sender and receiver over which data signals travel. It is either guided (wired) or unguided (wireless).

Types of guided media

1. Twisted pair cable

• Pairs of insulated copper wires twisted to reduce interference. Types: UTP (unshielded; common in LANs, Cat5e/Cat6) and STP (shielded).
• Cheap and easy to install; limited to about 100 m and lower bandwidth.

2. Coaxial cable

• Inner copper conductor, insulation, metal shield and outer jacket.
• Better shielding and bandwidth than twisted pair; used for cable TV and older Ethernet; bulkier.

3. Optical fibre cable

• Data is sent as light pulses through a glass/plastic core surrounded by cladding (total internal reflection). Single-mode fibre is used for long distance and multimode fibre for short distance.
• Very high bandwidth, low attenuation, immune to electromagnetic interference and secure; but costly and harder to install.

DHCP (Dynamic Host Configuration Protocol)

An application layer protocol (client UDP port 68, server port 67) that automatically gives hosts an IP address and other configuration (subnet mask, default gateway, DNS server, lease time), removing the need for manual setup.

• A DHCP server holds a pool of addresses and leases an address to a client for a limited time.
• The process is DORA: the client broadcasts Discover; the server replies with Offer; the client sends Request for the offered address; the server sends Acknowledge.
• Leases are renewed or released, so addresses are reused efficiently. A DHCP relay agent allows one server to serve several subnets.

ALOHA protocol

A random-access MAC protocol for a shared channel.

• Pure ALOHA: stations transmit whenever they have a frame; if no ACK arrives, they retransmit after a random delay. Vulnerable time $2T_{fr}$; maximum throughput about 18.4% ($Ge^{-2G}$).
• Slotted ALOHA: time is divided into slots and transmission begins only at a slot boundary. Vulnerable time $T_{fr}$; maximum throughput about 36.8% ($Ge^{-G}$).