Computer Networks

The class B network $150.10.0.0$ has a default mask $255.255.0.0$ (/16). To make 4 subnets we borrow $n$ bits with $2^n \ge 4$, so $n = 2$.

• New prefix: $/16 + 2 = /18$
• New subnet mask: $255.255.192.0$ (third octet $11000000_2 = 192$)
• Block size in the third octet: $256 - 192 = 64$
• Hosts per subnet: $2^{14} - 2 = 16382$

The class C network $192.168.3.0$ has a default mask $255.255.255.0$ (/24). For 4 subnets we borrow $n$ bits with $2^n \ge 4$, so $n = 2$.

• New prefix: $/24 + 2 = /26$
• New subnet mask: $255.255.255.192$ (last octet $11000000_2 = 192$)
• Block size: $256 - 192 = 64$ addresses, so $64 - 2 = 62$ usable hosts per subnet

Network: 193.168.2.0/24 (class C), host bits = 8.

Eight subnets need $2^n\ge 8$, so $n=3$ borrowed bits. The new prefix is $/24+3=/27$.

New subnet mask: 255.255.255.224 (/27), since the last octet is 11100000 = 224.

Block size = $256-224=32$ addresses per subnet, so 30 usable hosts ($2^5-2$).

The address range of each subnet is first host to last host (broadcast is the last address of the block).

Transmission media are the physical or wireless paths through which data signals travel from a sender to a receiver. They carry data in the form of electrical, light or electromagnetic signals.

Types of transmission media

1. Guided (wired) media: the signal is confined to a physical conductor.
   • Twisted pair cable (UTP, STP)
   • Coaxial cable
   • Optical fibre (single-mode, multi-mode)
2. Unguided (wireless) media: the signal travels through free space (air, vacuum) as electromagnetic waves, without a physical conductor.

Unguided media in detail

Unguided media are classified by how the waves propagate: ground-wave (below 2 MHz), ionospheric/sky-wave (2-30 MHz) and line-of-sight propagation (above 30 MHz). The main types follow.

1. Radio waves (3 kHz to 1 GHz)

• Omnidirectional: they spread in all directions, so no alignment of antennas is needed.
• They penetrate walls and travel long distances, but are prone to interference from other radio sources and are susceptible to eavesdropping.
• Uses: AM/FM radio, television broadcast, cordless phones, paging, mobile communication.

2. Microwaves (1 GHz to 300 GHz)

• Unidirectional, line-of-sight; the sending and receiving antennas must be aligned, so towers are placed about 50 km apart (limited by the curvature of the earth).
• They provide high bandwidth and high data rates, and cannot penetrate walls well; they are affected by rain and fog at high frequencies.
• Types: terrestrial microwave and satellite microwave (geostationary satellite 36,000 km above the earth, with uplink and downlink frequencies).
• Uses: cellular networks, satellite TV, VSAT, long-distance telephony, wireless LAN.

3. Infrared waves (300 GHz to 400 THz)

• Short range and line-of-sight; they cannot penetrate walls, so there is little interference between rooms and better security.
• Cannot be used outside because sunlight interferes.
• Uses: TV remote controls, wireless keyboards/mice, IrDA data transfer between nearby devices.

4. Other wireless: Bluetooth (2.4 GHz short range), Wi-Fi (2.4/5 GHz) and laser/free-space optics, which also belong to unguided media.

Advantages: mobility, no cabling cost, easy installation in difficult terrain. Disadvantages: interference, weaker security, attenuation due to weather, and lower reliability than fibre.

Flow control is a set of procedures that tells the sender how much data it may transmit before it must wait for an acknowledgement from the receiver. It prevents a fast sender from overwhelming a slow receiver whose buffer is limited. It is done at the data link layer (and transport layer) using the sliding window protocols and stop-and-wait.

Go-Back-N ARQ

Go-Back-N is a sliding window protocol with automatic repeat request (ARQ) error control.

• The sender window size is $N = 2^m - 1$ for $m$-bit sequence numbers; the receiver window size is 1.
• The sender can transmit up to $N$ frames without waiting for acknowledgements, and keeps a copy of every unacknowledged frame.
• The receiver accepts frames only in order. If a frame is lost or damaged, it discards that frame and all following frames until the expected one arrives, and sends a NAK (or does not ack).
• The acknowledgements are cumulative: ACK $n$ means all frames up to $n-1$ were received.
• On a timeout or NAK, the sender goes back and retransmits the lost frame and all frames that followed it.

Example. Take $m=3$ (frames numbered 0 to 7) and let the sender use a window of 4 frames; it sends frames 0, 1, 2, 3.

1. Frames 0 and 1 arrive; the receiver sends ACK 2.
2. Frame 2 is lost. Frame 3 arrives out of order, so the receiver discards it.
3. The timer of frame 2 expires at the sender. It goes back and retransmits frames 2 and 3 (and any later ones already sent).
4. Frames 2 and 3 now arrive in order and are acknowledged. The window slides forward and transmission continues with frame 4.

Thus one lost frame forces retransmission of the lost frame and all frames sent after it, even those received correctly.

Difference from Stop-and-Wait ARQ

Routing table. A routing table is a data structure stored in a router (or host) that lists the routes to network destinations and is used to decide where to forward each packet. Each entry typically contains: the destination network address, the subnet mask, the next-hop address (gateway), the outgoing interface, and the metric (cost). A router looks up the destination IP address of the packet (longest prefix match) and forwards it to the next hop; if nothing matches, the default route is used.

Static vs dynamic routing table

Transmission media

Transmission media are the physical paths along which data signals travel from sender to receiver. They lie below the physical layer and carry the signals as electrical, light or radio waves.

Guided versus unguided media

Types of guided media

1. Twisted pair cable

Two insulated copper wires twisted together; the twisting cancels interference and crosstalk. Several pairs are bundled in a jacket.

• UTP (unshielded): cheap and common in LANs (Cat5e, Cat6, up to 100 m, 100 Mbps to 10 Gbps); connector RJ-45.
• STP (shielded): a metal foil or braid around each pair or the bundle gives less noise but is costlier and heavier.
• Advantages: cheap, flexible, easy to install. Disadvantages: limited distance and bandwidth, susceptible to noise compared with the others.

2. Coaxial cable

A central copper core, surrounded by an insulator, a braided metal shield, and an outer plastic jacket. The shield gives better noise immunity and higher bandwidth than twisted pair.

• Types: 50-ohm baseband (thin Ethernet 10Base2, thick 10Base5) and 75-ohm broadband (cable TV, internet).
• Connectors: BNC, T-connector, terminators.
• Advantages: higher bandwidth and range than twisted pair. Disadvantages: bulky, more expensive, a break stops the whole bus.

3. Optical fibre

Data are sent as pulses of light through a thin glass or plastic core. A cladding of lower refractive index surrounds the core, so light is kept inside by total internal reflection; a buffer and jacket protect it.

• Multimode (step-index or graded-index): many light paths, short distances (up to a few km), LEDs.
• Single-mode: very thin core, one path, long distances (tens of km), laser source.
• Advantages: very high bandwidth (Gbps to Tbps), low attenuation, immune to electromagnetic interference, hard to tap, light weight.
• Disadvantages: costly, installation and splicing need skill, fragile, unidirectional so two fibres are needed for duplex.

Flow control

Flow control is the set of procedures that restricts the amount of data a sender may transmit before it must wait for an acknowledgement from the receiver, so a fast sender does not overwhelm a slow receiver whose buffer and processing speed are limited. It is performed at the data link layer (and transport layer).

Stop-and-Wait ARQ

The sender transmits one frame and then stops until it receives an acknowledgement (ACK) for it. Only then is the next frame sent. ARQ (Automatic Repeat reQuest) adds error control: damaged or lost frames are retransmitted.

Working:

1. The sender sends frame 0 and starts a timer. The frames are numbered alternately 0 and 1, so a duplicate can be recognised.
2. If the receiver gets the frame correctly it sends ACK 1 (the number of the next expected frame).
3. If the ACK arrives before the timer expires, the sender sends frame 1; otherwise on time-out it resends the same frame.
4. If a frame is corrupted, the receiver discards it and sends nothing, so the sender times out and retransmits. If an ACK is lost, the sender retransmits and the receiver discards the duplicate and re-sends the ACK.

Example:

Efficiency is low on long or fast links, since the channel is idle while waiting: utilisation is $U = \dfrac{1}{1+2a}$, where $a$ is propagation time divided by frame transmission time.

Difference from Go-Back-N ARQ

Virtual circuit network

A virtual circuit (VC) network is a packet-switched network that works like a circuit-switched one in that a path is set up before data transfer, but bandwidth is not reserved exclusively; it is shared statistically. It has three phases: setup, data transfer, teardown.

• During setup a path is chosen and each switch stores an entry in its table (incoming port, incoming VCI, outgoing port, outgoing VCI).
• Every packet carries a short virtual circuit identifier (VCI), not the full destination address. A switch uses the VCI to forward and replaces it with the outgoing VCI.
• All packets of the connection follow the same path and arrive in order.
• Used by X.25, frame relay and ATM.

ATM as a virtual circuit WAN

Asynchronous Transfer Mode (ATM) is a cell-switching WAN technology designed for voice, video and data at high speed.

• Cells: all data is carried in fixed-size 53-byte cells, with a 5-byte header and 48-byte payload. Fixed small cells give predictable delay and make fast hardware switching possible; this suits real-time traffic.
• Connection-oriented: a virtual circuit is set up first. The header holds a VPI (virtual path identifier) and VCI (virtual circuit identifier). A virtual path is a bundle of virtual circuits switched together. Connections are either permanent (PVC) or switched (SVC).
• Architecture: end-point devices connect through the User-to-Network Interface (UNI) to ATM switches, which are linked by the Network-Network Interface (NNI).
• Layers: the AAL (ATM adaptation layer) converts application data into cells, the ATM layer does switching and header handling, and the physical layer transmits cells (e.g. SONET).
• Quality of service: classes such as CBR, VBR, ABR and UBR give guaranteed bandwidth and delay.

Routing table

A routing table is a data structure stored in a router (or host) that holds the information needed to forward a packet. Each entry typically has: destination network address, subnet mask, next-hop (gateway) address, outgoing interface and metric (cost). The router matches a packet's destination to the entry with the longest prefix and forwards it to the next hop; a default route is used when there is no match.

Static versus dynamic routing table

Virtual circuit network

A virtual circuit (VC) network is a packet-switched, connection-oriented network. Before data is sent, a logical path (virtual circuit) is set up between source and destination, in three phases: setup, data transfer and teardown.

• Each packet carries a short virtual circuit identifier (VCI) instead of the full destination address. Each switch has a table mapping (incoming port, incoming VCI) to (outgoing port, outgoing VCI), so forwarding is fast.
• All packets of one connection follow the same route and arrive in order; resources can be reserved, which supports quality of service.
• Examples: X.25, Frame Relay, ATM. Types: switched virtual circuits (SVC, set up on demand) and permanent virtual circuits (PVC, set up by the provider).

ATM (Asynchronous Transfer Mode)

ATM is a cell-relay WAN technology designed for high-speed transfer of voice, video and data. It uses small fixed-size cells of 53 bytes (5-byte header + 48-byte payload). Fixed small cells give predictable delay, simple fast hardware switching and low jitter, making it suitable for real-time traffic.

• Cell header: GFC/VPI, VCI, payload type, cell loss priority and header error control. Connections are identified by VPI (virtual path) and VCI (virtual channel); several VCs are bundled in a virtual path.
• Operation: the source requests a connection (signalling); switches set up routing tables; cells are then switched using VPI/VCI, which are changed at each switch; the circuit is released at the end.
• Architecture/layers: AAL (ATM adaptation layer) segments user data into 48-byte units and reassembles them; ATM layer builds cells and does switching; physical layer transmits (SONET/SDH at 155 Mbps or 622 Mbps).
• Service classes: CBR (constant bit rate), VBR (variable bit rate, real-time and non-real-time), ABR (available bit rate), UBR (unspecified bit rate).
• It is asynchronous because cells of different connections are multiplexed on demand (statistical multiplexing), not in fixed time slots.

The TCP/IP model is the protocol suite on which the Internet is built. It has four layers (the original DoD model).

1. Host-to-network (network access / link) layer. The lowest layer, covering the physical and data link functions. It defines how data is sent on the local medium: framing, physical (MAC) addressing, error detection, media access and the transmission of bits. Technologies: Ethernet, Wi-Fi, PPP.

2. Internet layer. Responsible for logical addressing and routing of packets (datagrams) from source host to destination host across multiple networks. Main protocols:

• IP (IPv4/IPv6): connectionless, best-effort delivery with logical addressing and fragmentation.
• ICMP: error and diagnostic messages (ping).
• ARP/RARP: mapping between IP and physical addresses.
• IGMP: multicast group management.

3. Transport layer. Provides end-to-end communication between processes using port numbers; it handles segmentation, flow control, error control and multiplexing.

• TCP: connection-oriented, reliable, ordered delivery with acknowledgements, retransmission, flow and congestion control.
• UDP: connectionless, unreliable but fast and with low overhead (DNS, streaming).
• SCTP also exists.

4. Application layer. Provides services directly to user applications and combines the OSI session, presentation and application functions. Protocols: HTTP/HTTPS, FTP, SMTP, POP3/IMAP, DNS, DHCP, Telnet/SSH, SNMP.

Comparison with the OSI model

Mapping: OSI application, presentation and session map to the TCP/IP application layer; OSI transport to transport; OSI network to internet; OSI data link and physical to network access.

Network topology is the arrangement (physical or logical layout) of the nodes (devices) and the links connecting them in a computer network. Common topologies are bus, star, ring, mesh and tree.

Ring topology. In a ring topology each device is connected to exactly two neighbouring devices, forming a closed loop. Data travels around the ring in one direction (or both in a dual ring), passing through every node on the way; each node's repeater regenerates the signal and forwards it. Access is usually controlled by a token (token ring, FDDI): only the node holding the token may transmit, so there are no collisions.

   [A] --- [B]
    |       |
   [D] --- [C]

Merits

• Orderly access with the token, so no collisions and predictable performance even under heavy load.
• Easy to install and reconfigure; adding or removing a device needs only changing two connections.
• Each node regenerates the signal, so the ring can cover longer distances.
• Does not need a central server or hub.
• Fault isolation is relatively easy in a dual ring.

Demerits

• Failure of a single node or link breaks the ring and halts the entire network (unless a dual ring is used).
• Data must pass through every intermediate node, so delay grows with the number of nodes.
• Troubleshooting a fault is difficult.
• Adding or removing a node disturbs the network temporarily.
• Unidirectional ring gives low efficiency compared with a star.

Local Area Network (LAN). A LAN is a privately owned network that connects computers and devices within a limited geographic area, such as a room, a building, a school or a campus (typically up to a few kilometres). It offers high data rates (10 Mbps to 10 Gbps or more), low delay and low error rate, and is owned and managed by a single organisation. Devices are connected through switches or hubs by Ethernet cable or through Wi-Fi access points.

Example: the computer laboratory of a college, where all PCs, printers and a server are connected through a switch so that they share files, printers and an Internet connection. Another is an office network or home Wi-Fi network.

Difference between LAN and PAN

Switching is the technique of connecting many source-destination pairs through intermediate nodes (switches) so that data can be sent between any two end systems without a direct link between every pair. The main methods are circuit switching, packet switching (datagram and virtual circuit) and message switching.

Circuit-switched network. A dedicated end-to-end path (circuit) is established between the sender and receiver before data transfer, kept for the entire communication and released afterwards. The phases are setup, data transfer and teardown. Example: the traditional telephone network (PSTN).

Packet-switched network. The message is divided into packets, each with a header holding addresses. The packets are sent independently (datagram) or along a virtual circuit and are forwarded hop by hop using store-and-forward, and are reassembled at the destination. No dedicated path is reserved. Example: the Internet.

Comparison

Need for wireless LAN (WLAN). A WLAN connects devices using radio waves instead of cables. It is needed because:

• It provides mobility: users can move around a building or campus and stay connected.
• It avoids the cost and effort of cabling, and is easy to install in old buildings, temporary sites and difficult terrain.
• It is flexible and scalable: devices can be added without new wiring.
• Many modern devices (phones, tablets, laptops, IoT devices) have no Ethernet port.
• It allows quick set-up of networks for events, hotspots and disaster recovery.

Architecture of IEEE 802.11. The standard defines the physical and MAC layers of WLANs. Its main components are:

1. Station (STA): any wireless device (laptop, phone) with a wireless network interface.
2. Basic Service Set (BSS): the basic building block, a group of stations that communicate with each other. It has two forms:
   • Ad hoc (independent) BSS or IBSS: stations communicate directly with each other without an access point.
   • Infrastructure BSS: stations communicate through an Access Point (AP), which also links the BSS to the wired network.
3. Access Point (AP): acts as a base station and bridge between wireless stations and the distribution system.
4. Extended Service Set (ESS): two or more infrastructure BSSs connected through a Distribution System (DS), usually a wired LAN, which lets users roam between APs. Stations in an ESS are identified by an SSID (network name), and the ESS appears as one network to the upper layers. Portals connect the DS to other (wired) LANs.

Station types by mobility: no-transition (fixed or within one BSS), BSS-transition (moves between BSSs in one ESS) and ESS-transition (moves between ESSs).

Layers. The MAC sublayer uses CSMA/CA (collision avoidance, optionally RTS/CTS) because wireless stations cannot detect collisions; it also does fragmentation, acknowledgement and power saving. The physical layer supports FHSS, DSSS, OFDM and infrared, with standards 802.11b (2.4 GHz, 11 Mbps), 802.11a (5 GHz, 54 Mbps), 802.11g (2.4 GHz, 54 Mbps), 802.11n (up to 600 Mbps) and 802.11ac/ax (higher).

(a) NAT (Network Address Translation) is a technique that lets many hosts in a private network share one or a few public IP addresses. A NAT router rewrites the IP address (and usually the port number) in packets as they pass between the private network and the Internet.

(b) How it works

Private addresses (10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16) are not routable on the Internet. The NAT router keeps a translation table.

1. Outgoing packet: Host 192.168.1.10 sends a packet from port 3000 to a web server 203.0.113.5:80. The router replaces the source with its public address and a unique port, for example 198.51.100.1:5001, and stores the mapping.
2. Table entry:

3. Incoming reply: The server replies to 198.51.100.1:5001. The router looks up the table, replaces the destination with 192.168.1.10:3000 and forwards it into the LAN.

Using ports as well as addresses (PAT or NAT overload) allows thousands of internal hosts to share a single public IP. Static NAT maps one private address to one fixed public address, dynamic NAT uses a pool of public addresses.

(c) Benefits

• Saves scarce public IPv4 addresses.
• Hides the internal network structure, giving some security, since outside hosts cannot start connections to private hosts directly.
• The internal addressing can be changed freely, and the ISP can be changed without renumbering the LAN.
• Simple to deploy for homes and offices.

Given host address $192.34.12.56/28$. The prefix is 28 bits, so the mask is $255.255.255.240$ and the host part is the last $32-28=4$ bits (block size $2^4 = 16$ addresses).

Only the last octet matters: $56 = 0011\,1000_2$.

• Mask last octet: $240 = 1111\,0000_2$.
• Network address: $0011\,1000 \;\text{AND}\; 1111\,0000 = 0011\,0000 = 48$.
• Broadcast address: set all host bits to 1, $0011\,1111 = 63$.

First address (network address): $192.34.12.48$

Last address (limited broadcast address of the block): $192.34.12.63$

Check: the block runs from 48 to 63, which is 16 addresses, and 56 lies inside it.

Why DNS is needed

IP addresses such as 142.250.190.78 are hard for people to remember and type, and they can change when a server moves or the provider changes. Names such as www.example.com are easy to remember and stay constant. The Domain Name System (DNS) is a distributed database and application-layer protocol that maps names to IP addresses (and back). Without it every user would need to know numeric addresses, and a single flat host file would be impossible to keep up to date for the whole Internet. DNS is distributed, so no single server holds all names, and it scales well.

Domain name space

The domain name space is the hierarchical, inverted-tree structure in which all DNS names are organised.

• The tree has a root at the top, with up to 128 levels below it.
• Each node has a label of up to 63 characters. A fully qualified domain name (FQDN) is the sequence of labels from the node up to the root, separated by dots, e.g. www.cs.tu.edu.np.
• Top-level domains (TLDs) come below the root: generic (com, org, edu, net), country (np, in, us) and the reverse domain (arpa).
• A domain is a subtree; a zone is the part of the tree managed by one server. Root, TLD and authoritative servers divide the work, so the namespace is spread over many servers.

Hierarchy guarantees uniqueness: two organisations can use the same host label, e.g. www, in different domains without conflict.

(a) Connection-oriented service

In a connection-oriented service a logical connection is set up between sender and receiver before data is exchanged, used for the transfer, and released afterwards. It works like a telephone call.

• Three phases: connection establishment, data transfer, connection release.
• Packets are numbered and delivered in order; acknowledgements and retransmission give reliability, and flow and congestion control can be applied.
• Examples: TCP at the transport layer, virtual circuit networks such as ATM and frame relay.
• Advantages: reliable, ordered delivery. Disadvantages: setup delay and overhead, and the connection fails if a node on the path fails.

(b) Bridge

A bridge is a layer-2 (data link layer) device that connects two or more LAN segments and forwards frames between them using MAC addresses.

• It filters traffic: a frame whose destination lies in the same segment is not forwarded, so collision domains are separated and traffic is reduced.
• A transparent (learning) bridge builds a forwarding table by noting the source MAC address of each incoming frame and the port it arrived on. Unknown destinations are flooded to all other ports.
• It does not change frame addresses, regenerates the signal, and can connect LANs of the same or similar types. Loops are avoided with the spanning tree protocol.
• Switches are multi-port bridges.

Link state routing

In link state routing every router learns the complete topology of the network and independently computes the best path to every destination. It is used by OSPF and IS-IS.

Steps

1. Discover neighbours: each router sends HELLO packets to find its directly connected neighbours and measures the cost (delay, bandwidth, hop) of each link.
2. Build a link state packet (LSP/LSA): it lists the router's identity, its neighbours and the link costs, with a sequence number and age.
3. Flood the LSP: the LSP is sent to all neighbours, who forward it to all their other neighbours. Sequence numbers prevent old or duplicate packets from circulating.
4. Build the link state database: after flooding every router has the same map (graph) of the network.
5. Compute shortest paths: each router runs Dijkstra's algorithm with itself as the root, and builds the routing table (next hop for each destination). The algorithm is rerun when a change is flooded.

Dijkstra's algorithm: keep a set of settled nodes; start with the source at distance 0; repeatedly add the unsettled node with smallest tentative distance; update distances of its neighbours.

Example

Network: A-B = 2, A-C = 5, B-C = 1, B-D = 4, C-D = 2. Compute from A.

Routing table of A:

Features: fast convergence, loop-free, supports metrics and hierarchical areas; requires more memory and CPU, and flooding uses bandwidth.

Client/server network

In a client/server network, one or more powerful, dedicated computers (servers) provide resources and services such as files, web pages, mail, databases and printing, and other computers (clients) request these services. Control, security and data storage are centralised on the server. Examples: web browsing, email, banking systems, a Windows domain.

Difference from peer-to-peer (P2P)

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

CSMA/CD is the medium access method of classic (half-duplex, shared medium) Ethernet. Several stations share one channel, so a rule is needed to control collisions.

Procedure:

1. Carrier sense: a station with a frame listens to the channel. If it is busy, the station waits until it is idle.
2. Multiple access: if idle, it starts transmitting (1-persistent method).
3. Collision detection: while sending, the station keeps monitoring the channel. If the signal it reads differs from what it sends, a collision has occurred.
4. Jam signal: the station sends a short jam signal so all stations know of the collision, and stops sending.
5. Back-off: it waits a random time using binary exponential back-off, choosing $K \in \{0, 1, \dots, 2^n - 1\}$ slot times after the $n$-th collision, and tries again, up to 16 attempts.

The minimum frame size (64 bytes) guarantees that a collision is detected before the sender finishes transmitting.

Why it is not needed on full-duplex Ethernet

A full-duplex Ethernet LAN uses a switch and a point-to-point link between each station and the switch, with separate paths (separate wire pairs) for transmit and receive. The medium is therefore not shared, each link carries only two devices and each direction is used by one sender. Collisions cannot occur, so no carrier sensing, collision detection or back-off is required, and the station can send at any time at full link speed.

Structure of an IPv6 address

An IPv6 address is 128 bits long, written as eight groups of four hexadecimal digits separated by colons (each group is 16 bits):

2001:0DB8:0000:0000:0008:0800:200C:417A

Abbreviation rules:

• Leading zeros in a group may be dropped: 2001:DB8:0:0:8:800:200C:417A.
• One run of consecutive all-zero groups may be replaced by :: (once only): 2001:DB8::8:800:200C:417A.

The address has a network prefix (e.g. 2001:DB8:1234::/48 global routing prefix plus 16-bit subnet ID) and a 64-bit interface identifier, often derived from the MAC address (EUI-64). Address types: unicast (global, link-local FE80::/10, unique local FC00::/7), multicast (FF00::/8) and anycast. There is no broadcast.

IPv6 versus IPv4

Congestion control

Congestion occurs when the load on the network is greater than its capacity, causing delay and packet loss. Congestion control methods are classed as open loop and closed loop.

Open-loop congestion control

Policies are designed to prevent congestion before it happens. They are applied by the source or destination, without feedback from the network.

• Retransmission policy: good timers and retransmission methods that do not add to the load.
• Window policy: Selective Repeat is better than Go-Back-N because it avoids resending good packets.
• Acknowledgement policy: receiver acknowledges several packets together or only when needed.
• Discard policy: routers drop less important packets first (e.g. in audio) when congestion is likely.
• Admission policy: a switch checks resource needs before admitting a flow, as in virtual circuit networks.

Comparison with closed-loop control

Streaming means playing audio or video while it is still being downloaded, so the user need not wait for the whole file. There are four approaches.

1. Using a web server (downloading with a plain HTTP)

The audio/video file is stored as a normal file on a web server. The browser downloads the whole file, then a media player plays it. Simple, but there is a long start-up delay, since playback begins only after the download completes.

2. Using a web server with a metafile

The browser fetches a small metafile containing the URL of the media. It starts the media player and passes the metafile; the player contacts the web server directly using the URL and plays the stream while downloading. The browser does not handle the media, so playback begins sooner.

3. Using a media server

The player contacts a separate media server (not an HTTP server) via the metafile. The media server can use UDP, which does not retransmit lost packets and so avoids delays, giving better real-time delivery. HTTP/TCP traffic and its retransmission are avoided.

4. Using a media server and RTSP

The Real-Time Streaming Protocol (RTSP) adds VCR-like control: the user can play, pause, rewind, fast-forward and record. The player sends RTSP commands (SETUP, PLAY, PAUSE, TEARDOWN) to the media server over TCP while the media itself flows over UDP/RTP. This gives the most interactive and flexible streaming.

(a) Backbone network

A backbone network is the high-capacity central part of a larger network, which interconnects several smaller LANs or subnetworks and carries the combined traffic between them. It is the "main road" of a network.

• Usually built from fibre-optic links and high-speed switches or routers, operating at Gbps to Tbps.
• Types: bus backbone (a shared bus linking LAN switches), star backbone (one central switch), distributed/collapsed backbone, and WAN backbone of an ISP connecting major cities and countries.
• Advantages: high speed, centralised management, easy to extend. A failure in the backbone affects every attached segment, so redundant links are used.

(b) ISDN (Integrated Services Digital Network)

ISDN is a digital telephone network standard (by ITU-T) that carries voice, data, video and fax over the ordinary telephone lines in digital form, giving a single access for all services.

• B channel: 64 kbps bearer channel for user data or digital voice.
• D channel: signalling and control channel, 16 kbps (BRI) or 64 kbps (PRI).
• BRI (Basic Rate Interface): 2B + D = 144 kbps, for homes and small offices.
• PRI (Primary Rate Interface): 23B + D (T1, 1.544 Mbps) or 30B + D (E1, 2.048 Mbps), for larger organisations.
• Components: TE1/TE2 terminals, TA (terminal adapter), NT1/NT2 (network termination), and the ISDN exchange. It has been replaced by DSL and broadband.

(c) ALOHA

ALOHA is a random access protocol developed at the University of Hawaii for sharing a radio channel.

• Pure ALOHA: a station sends a frame whenever it has one. If no acknowledgement arrives within the time-out, it assumes a collision and retransmits after a random back-off time. The vulnerable time is $2T_{fr}$ and maximum throughput is $S = G e^{-2G}$, reaching $\approx 18.4\%$ at $G = 0.5$.
• Slotted ALOHA: time is divided into slots equal to the frame time and a station may send only at the start of a slot. The vulnerable time is $T_{fr}$, so $S = G e^{-G}$ and maximum throughput is $\approx 36.8\%$ at $G = 1$.

Protocol

A protocol is a set of rules that governs data communication. It defines the syntax (format of data), semantics (meaning of each field and the action to take) and timing (when to send and how fast). Two devices can communicate only if they use the same protocol.

OSI model

The Open Systems Interconnection (OSI) model of ISO divides network communication into seven layers. Each layer offers services to the layer above and uses the services of the layer below. Layers are: Physical, Data Link, Network, Transport, Session, Presentation, Application.

1. Physical layer: transmits raw bits over the medium. Defines the electrical and mechanical specification (voltage, cables, connectors), data rate, line coding, transmission mode (simplex, half, full duplex), topology and synchronisation of bits. Devices: hub, repeater, cable.

2. Data link layer: node-to-node delivery of frames over a link. Functions: framing, physical (MAC) addressing, flow control, error control (detection and retransmission), and access control on shared media. Devices: bridge, switch. Sub-layers: LLC and MAC.

3. Network layer: source-to-destination delivery of packets across networks. Functions: logical (IP) addressing, routing, fragmentation, congestion control. Device: router. Protocols: IP, ICMP, ARP.

4. Transport layer: process-to-process (end-to-end) delivery of the whole message. Functions: port addressing, segmentation and reassembly, connection control, end-to-end flow and error control. Protocols: TCP, UDP.

5. Session layer: establishes, maintains and ends sessions (dialogues) between applications. It provides dialog control (who talks when) and synchronisation, adding checkpoints so a long transfer can resume after a failure.

6. Presentation layer: deals with syntax and semantics of the exchanged information. Functions: translation between character codes and data formats, encryption and decryption, compression.

7. Application layer: gives the user and applications access to the network. Services: file transfer (FTP), mail (SMTP), web (HTTP), remote login (Telnet/SSH), name service (DNS), network management.

Data moves down the sender's layers, each adding a header (encapsulation), and up the receiver's layers, each removing its header.

Error detection versus error correction

CRC (Cyclic Redundancy Check)

CRC is a strong error detection method based on binary polynomial division.

Sender

1. Choose a generator (divisor) of $k+1$ bits, e.g. $x^3 + x + 1 = 1011$ ($k=3$).
2. Append $k$ zero bits to the data.
3. Divide the augmented data by the divisor using modulo-2 (XOR) division. The $k$-bit remainder is the CRC.
4. Replace the appended zeros with the CRC and transmit the codeword.

Receiver: divide the received codeword by the same divisor. A remainder of zero means no error detected; a non-zero remainder means error, and the frame is discarded.

Example

Data $= 1001$, divisor $= 1011$. Augmented data $= 1001000$.

$$\begin{aligned} 1001 \oplus 1011 &= 0010 \to \text{bring down } 0 \to 0100 \\ 0100 \oplus 0000 &= 0100 \to \text{shift, bring down } 0 \to 1000 \\ 1000 \oplus 1011 &= 0011 \to \text{bring down } 0 \to 0110 \\ 0110 \oplus 0000 &= 110 \end{aligned}$$

The remainder is $110$, so the transmitted codeword is $1001\,110$.

Check at the receiver: divide $1001110$ by $1011$: $1001 \oplus 1011 = 0010$, bring down 1: $0101 \to 101$, bring down 1: $1011 \oplus 1011 = 000$, bring down 0: $0000$. The remainder is $000$, so no error is detected.

If a bit is flipped, e.g. $1011110$, the remainder is non-zero and the error is detected. A CRC detects all single-bit errors, all burst errors shorter than the degree of the generator and most longer bursts. CRC-32 is used in Ethernet.

Distance vector routing

In distance vector routing each router knows only its directly connected neighbours and keeps a table (vector) giving the best known distance to every destination and the next hop. Periodically, and on change, each router sends its whole table to its neighbours. It is based on the Bellman-Ford algorithm and used in RIP.

Algorithm

1. Initially each router knows only the cost to its neighbours (the distance to itself is 0, to others infinity).
2. A router receives a vector from neighbour $N$ and, for each destination $D$, computes $d(X,D) = \min_N \big[\, c(X,N) + d(N,D) \,\big]$
3. If the result is better than its current entry, it updates the table with $N$ as next hop and later sends its changed vector on.
4. The process repeats until no table changes (convergence).

Example

Links: A-B = 2, B-C = 1, A-C = 5, C-D = 3.

Initial tables (destination: cost):

After the first exchange: A learns from B that C costs $2+1 = 3$ (better than 5), so A to C = 3 via B. B learns from C that D costs $1+3 = 4$. D learns from C that B costs $3+1 = 4$ and A costs $3+5 = 8$.

After the second exchange: A learns from B that D = $2+4 = 6$. D learns A = $3+3 = 6$ (via C, B). The final table of A:

No more changes occur, so the network has converged.

Problems: slow convergence and the count-to-infinity problem when a link fails. Remedies: split horizon, route poisoning, hold-down timers, and a small maximum hop count (RIP uses 15 as the limit, 16 as infinity).

Need for network topology

Topology is the physical or logical layout of devices and links. It is needed to:

• decide how nodes are connected and how data will flow between them;
• choose a layout that suits cost, performance and reliability needs;
• plan cabling and device placement, and the scale for future expansion;
• make fault finding and maintenance easier.

Star topology

Every device (node) is connected by a point-to-point link to a central device, a hub or switch. Nodes do not link to each other; all traffic goes through the centre. It is the common LAN layout (Ethernet with UTP and switch).

Merits

• Easy to install, configure and expand: a new node needs only one more cable.
• Failure of one node or cable affects only that node.
• Easy fault detection and isolation, and simple management from the centre.
• Good performance with a switch since each link is dedicated.

Demerits

• If the central hub/switch fails, the whole network goes down (single point of failure).
• More cable is required than for bus topology, so cost is higher.
• The number of nodes is limited by the ports on the central device.
• Cost of the hub/switch.

Protocol

A protocol is a set of rules that defines how two or more devices communicate. It has three key elements: syntax (the structure or format of the data), semantics (the meaning of each section of bits and the action to take) and timing (when data should be sent and how fast). Examples: HTTP, TCP, IP, FTP, SMTP.

Why standards are needed

Standards are agreed documents of rules and specifications. They are needed because:

• Interoperability: equipment from different vendors and countries can work together.
• Compatibility across hardware and software, so users are not tied to one manufacturer.
• Competition and lower cost: a large market develops for standard products and mass production reduces prices.
• Quality and safety: products meet a minimum level of performance.
• Growth of the Internet and global networking is possible, since networks can interconnect.

Standards are of two kinds: de facto (by widespread use, e.g. TCP/IP) and de jure (by legal approval of bodies such as ISO, ITU-T, IEEE, ANSI, IETF).

Circuit-switched network

In a circuit-switched network a dedicated physical path (circuit) is established between the sender and the receiver for the whole duration of the communication. The path is made up of links and switches; each link is divided into channels using FDM or TDM and one channel is reserved for the connection. Data flows continuously with no processing delay at switches. The classic example is the telephone network. Resources are wasted when the line is idle, but delay is small and constant.

Phases of communication

1. Connection setup: before data transfer, the source requests a connection (e.g. dialling). Each switch on the path reserves a channel and the end-to-end circuit is established, with the called party's acceptance.
2. Data transfer: data flows continuously over the dedicated circuit. All data follows the same path, in order, with no addressing needed after setup.
3. Teardown (connection release): when either side finishes, it signals the switches, which release the reserved channels so they can be used by other calls.

Virtual circuit network

A virtual circuit network is a packet-switched network that behaves like a circuit-switched one. A path is chosen and set up before data transfer, then all packets of the connection follow it, and the path is torn down at the end. Each packet carries a short virtual circuit identifier (VCI) instead of the full destination address, which each switch maps using its table (incoming port, incoming VCI, outgoing port, outgoing VCI). Resources are shared statistically, so the circuit is "virtual". Packets arrive in order.

Frame relay

Frame relay is a virtual circuit WAN standard that provides fast, low-cost packet switching at the data link layer, designed to replace X.25 and leased lines.

• Virtual circuits: connections use a DLCI (Data Link Connection Identifier), a 10-bit identifier in the frame header (so up to 1024 values) which is changed at each switch. Both PVC (permanent, set up by the provider) and SVC (switched, set up on demand) are supported, but PVC is common.
• Speed and efficiency: operates only at the physical and data link layers; there is no flow control or retransmission in the network, since links are reliable (fibre). Frames with errors are simply discarded and higher layers recover. This lowers delay and gives rates up to about 44.7 Mbps.
• Variable frame size, so it carries bursty LAN traffic well. Frame header fields include DLCI, C/R, EA, FECN, BECN and DE (discard eligibility).
• Congestion notification: FECN and BECN bits tell the destination and source about congestion.
• Devices: the user's equipment (DTE, such as a router) connects through a FRAD to the provider's switches (DCE).
• Committed Information Rate (CIR) guarantees a minimum bandwidth.

Why TCP is connection-oriented and reliable

Connection-oriented: before any data are sent, TCP creates a logical connection between the two processes with a three-way handshake (SYN, SYN+ACK, ACK). After the transfer it closes the connection (FIN/ACK exchange). State is maintained at both ends during this time.

Reliable: TCP guarantees delivery of the data in order and without errors or duplication, by:

• sequence numbers on each byte, so data can be ordered and duplicates dropped;
• acknowledgements from the receiver, with retransmission of unacknowledged segments after a time-out;
• a checksum to detect corrupted segments;
• flow control with the sliding window (receiver window size);
• congestion control (slow start, congestion avoidance).

TCP versus UDP

Architecture of the WWW. The World Wide Web is a distributed client-server system of linked documents (hypertext) stored on web servers all over the Internet and accessed by browsers over HTTP.

Main components

1. Client (web browser). Software such as Chrome or Firefox. It sends requests, receives the response and renders HTML, CSS, images and scripts. It consists of a controller, interpreters (HTML, JavaScript) and client protocols (HTTP, FTP).
2. Web server. A program (Apache, Nginx, IIS) that listens on port 80/443, accepts HTTP requests and returns the requested page or the output of a dynamic program (PHP, Node.js, CGI) together with a status code.
3. Web documents. Static (fixed content), dynamic (generated on request by a server program) and active (a program such as JavaScript that runs in the browser).
4. Protocols. HTTP/HTTPS for transfer, TCP for reliable transport, DNS for name resolution.
5. URL to identify each resource uniquely.

Working

1. The user types a URL or clicks a link.
2. The browser asks DNS for the IP address of the host.
3. It opens a TCP connection to the server (port 80 or 443).
4. It sends an HTTP request, e.g. GET /index.html HTTP/1.1.
5. The server processes the request and sends back a response with status code and the document.
6. The browser renders the page, then the connection is closed or reused (persistent connection).

Browser (client) --HTTP request--> Web server --> files / database
Browser (client) <--HTTP response-- Web server
        ^ DNS lookup for host name

URL (Uniform Resource Locator). A URL is the address that identifies a resource on the web and the way to reach it. Its general form is

protocol://host[:port]/path[?query][#fragment]

Example: https://www.example.com:443/notes/cn.html?page=2#intro

• Protocol (scheme): https
• Host: www.example.com (domain name or IP)
• Port: 443 (optional, default for the protocol)
• Path: /notes/cn.html (location on the server)
• Query and fragment: parameters and a position inside the page.

Software Defined Network (SDN). SDN is a network architecture that separates the control plane (decisions about where traffic goes) from the data plane (forwarding of packets). The control logic is moved from individual switches and routers into a logically centralised software controller, which programs the forwarding devices through an open interface such as OpenFlow. Network behaviour can therefore be managed and changed through software, not by configuring each device by hand.

Architecture (three layers)

1. Application layer. Network applications such as routing, load balancing, firewalls and monitoring, which talk to the controller through the northbound API (e.g. REST).
2. Control layer. The SDN controller (OpenDaylight, ONOS) keeps a global view of the topology, computes paths and installs flow rules.
3. Infrastructure (data) layer. Switches and routers that forward packets according to flow tables. The controller talks to them over the southbound API (OpenFlow).

Features

• Separation of control and data planes.
• Centralised control and global network view.
• Programmability through software and open APIs.
• Use of open standards (OpenFlow), so it is vendor independent.
• Simple, cheap, "dumb" forwarding hardware.
• Automation, fast provisioning and easy policy changes.
• Better traffic engineering, utilisation and security (flows can be isolated or blocked centrally).
• Scalability and support for virtualisation and cloud environments.

(a) Protocol and standards

A protocol is a set of rules that governs data communication. It defines the syntax (format and order of the data), the semantics (meaning of each field and the action to take) and the timing (when to send and how fast). Examples are TCP, IP, HTTP, SMTP.

A standard is an agreed specification that lets equipment from different vendors interoperate.

• De facto standards come from wide use without formal approval (e.g. early TCP/IP).
• De jure standards are approved by an official body such as ISO, ITU-T, IEEE, ANSI or IETF (RFCs).

Standards give interoperability, a larger market, lower cost and a guarantee of compatibility.

(b) Switch

A switch is a layer 2 device that connects hosts in a LAN and forwards frames only to the port where the destination is located. It learns MAC addresses by reading the source address of incoming frames and storing it with the port number in a MAC address table. For a known destination it forwards the frame to that one port (unicast); for an unknown destination or a broadcast it floods the frame to all ports except the incoming one. Each port is its own collision domain, so a switch removes collisions and allows full-duplex links and simultaneous communication between several pairs. Switching methods are store-and-forward, cut-through and fragment-free. Layer 3 switches can also route between VLANs.

Classless addressing. In classful addressing (A, B, C) block sizes are fixed (2^24, 2^16, 2^8 addresses), which wastes addresses. In classless addressing (CIDR, Classless Inter-Domain Routing) the address has no class; a block of any power-of-two size is allocated and written as a.b.c.d/n, where $n$ is the length of the prefix (network part). The suffix has $32-n$ bits, so the block holds $2^{32-n}$ addresses.

Rules for a block:

• The number of addresses is a power of 2.
• The first address must be divisible by the block size.

Example: 200.1.2.64/26 has $2^{6}=64$ addresses, from 200.1.2.64 to 200.1.2.127, mask 255.255.255.192. CIDR also allows route aggregation (supernetting), which reduces the size of routing tables.

Distance vector routing

Each router knows only its directly connected neighbours. It keeps a table (vector) with the distance (cost) to every destination and the next hop. Periodically, or on a change, it sends its whole vector to its neighbours only. Using the Bellman-Ford equation, a router updates

$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 the distance advertised by $v$ to $y$. Steps: (1) initialise with cost 0 to itself, link cost to neighbours and infinity to others; (2) exchange vectors with neighbours; (3) recompute using the equation; (4) repeat until no table changes (convergence). This is the principle of RIP (hop count, infinity = 16).

Example. Consider A–B cost 2, B–C cost 3 and A–C cost 7.

Initial table of A: B = 2, C = 7. Initial table of B: A = 2, C = 3. Initial table of C: A = 7, B = 3.

After A receives B's vector (C = 3): $D_A(C)=\min\{7,\; c(A,B)+D_B(C)\}=\min\{7,\;2+3\}=5$

So A reaches C via B with cost 5. Similarly C learns $D_C(A)=\min\{7,\;3+2\}=5$ via B. B's table does not change. Final tables:

No further change occurs, so the network has converged. Problems of the method are slow convergence and count-to-infinity, reduced by split horizon, poison reverse and hold-down timers.

Flow control. Flow control is a set of procedures that restrict the amount of data a sender may transmit before it must wait for an acknowledgement from the receiver. It prevents a fast sender from overwhelming a slow receiver whose buffer and processing speed are limited. It is implemented in the data link layer (hop to hop) and the transport layer (end to end).

Stop-and-wait ARQ. The sender transmits one frame and then stops and waits for its acknowledgement (ACK) before sending the next. It starts a timer when it sends the frame. Frames carry a sequence number of 1 bit (0, 1), and the ACK carries the number of the next expected frame.

Error handling

1. Damaged frame. The receiver detects the error with CRC/checksum and discards the frame without an ACK. The sender's timer expires and it retransmits the same frame.
2. Lost frame. The receiver sees nothing and sends nothing, so the timer expires and the frame is retransmitted.
3. Lost ACK. The sender times out and resends the frame. The receiver sees a duplicate (same sequence number), discards it and sends the ACK again. The sequence numbers are what make the duplicate detectable.
4. Delayed ACK. If the timeout is too short, the sender retransmits unnecessarily; again the sequence number identifies the duplicate.

The sender keeps a copy of the frame until it is acknowledged. The protocol is simple, but the channel is idle while waiting, so the efficiency is low on long-delay links:

$U=\frac{1}{1+2a},\qquad a=\frac{t_{prop}}{t_{frame}}$

Layer. Stop-and-wait ARQ resides in the data link layer (LLC sublayer) of the OSI model. The same idea is also used at the transport layer.

TCP header. TCP (Transmission Control Protocol) is a connection-oriented, reliable, byte-stream transport protocol. Each segment has a header of 20 to 60 bytes (20 bytes without options).

 0                16                 31
+-----------------+-----------------+
| Source port     | Destination port|
+-----------------+-----------------+
|        Sequence number (32)       |
+-----------------------------------+
|     Acknowledgement number (32)   |
+------+-------+------+-------------+
| HLEN |Reserv.|Flags |Window size  |
+------+-------+------+-------------+
| Checksum        | Urgent pointer  |
+-----------------+-----------------+
|      Options and padding          |
+-----------------------------------+
|              Data                 |
+-----------------------------------+

Fields

• Source port (16 bits) and destination port (16 bits): identify the sending and receiving application processes.
• Sequence number (32 bits): number of the first data byte in the segment, used for ordering and reassembly.
• Acknowledgement number (32 bits): next byte the receiver expects (valid when ACK is set).
• Header length (4 bits): size of the header in 4-byte words (5 to 15).
• Reserved (6 bits): for future use.
• Control flags (6 bits): URG (urgent pointer valid), ACK (acknowledgement valid), PSH (push data at once), RST (reset connection), SYN (open connection, synchronise sequence numbers), FIN (close connection).
• Window size (16 bits): number of bytes the sender may send, used for flow control.
• Checksum (16 bits): error detection over header, data and pseudo-header.
• Urgent pointer (16 bits): offset of the last urgent byte.
• Options (up to 40 bytes): maximum segment size, window scale, timestamps, SACK.

Uses of TCP / its header

• Reliable delivery: sequence and acknowledgement numbers with retransmission give ordered, loss-free delivery.
• Connection management: the SYN, ACK and FIN flags give the three-way handshake and the connection close.
• Flow control through the window size, and congestion control (slow start, congestion avoidance).
• Error detection via the checksum.
• Multiplexing of many applications through port numbers.
• Used by applications needing reliability: HTTP/HTTPS, FTP, SMTP, SSH, POP3/IMAP.

Packet switching. In packet switching the message is divided into small units called packets, each carrying a header with source and destination addresses and a sequence number. Packets are sent independently through the network, are stored and forwarded by routers, may take different routes, and are reassembled in order at the destination. No dedicated path is reserved; links are shared by statistical multiplexing. There are two types: datagram (each packet routed independently, as in IP) and virtual circuit (a path is set up first and all packets follow it, as in X.25 and frame relay).

Advantages

• Efficient use of bandwidth, since links are shared and idle capacity is used by other traffic.
• No call set-up delay (datagram).
• Robust: if a link or node fails, packets are rerouted.
• Different data rates and devices can communicate, with error checking per packet.
• Cheaper for bursty data traffic.
• Priority can be given to some packets.

Disadvantages

• Variable delay and jitter, so not ideal for real-time voice and video without QoS.
• Packets may be lost, duplicated or arrive out of order, so reassembly is needed.
• Header overhead on every packet.
• Routers need buffers and processing power; congestion can occur.
• Complex protocols are required for reliability.

Types of networks by geographical size

1. PAN (Personal Area Network). Covers a few metres around one person, connecting phone, laptop, headset, using Bluetooth or USB.
2. LAN (Local Area Network). Covers a room, building or campus (up to a few km). It is privately owned, with high speed (100 Mbps to 10 Gbps) and low delay, using Ethernet or Wi-Fi, switches and hubs.
3. MAN (Metropolitan Area Network). Covers a city; used by a cable TV network or an ISP, or to join several LANs of an organisation. It uses fibre or microwave links (e.g. DQDB, WiMAX).
4. WAN (Wide Area Network). Covers a country or the world, using leased lines, satellite or public networks. The Internet is the largest WAN. Speed is lower and delay higher than a LAN, and it is often owned by several organisations.

By other criteria

• Topology: bus, star, ring, mesh, tree, hybrid.
• Connection: point-to-point and broadcast (multipoint).
• Ownership or access: private networks, intranet, extranet and Internet; VPN, which runs over a public network.
• Architecture: peer-to-peer and client-server.
• Medium: wired and wireless networks (WLAN).

Given: 172.16.0.0 is a class B address, default mask 255.255.0.0 (/16), with 16 host bits.

Number of subnets. To make 2 subnets we borrow $n$ bits with $2^n\ge 2$, so $n=1$.

New prefix: /16 + 1 = /17, subnet mask 255.255.128.0.

Host bits remaining = 32 - 17 = 15.

Hosts per subnet

$2^{15}-2=32768-2=32766$

Total usable hosts in both subnets = $2\times32766=65532$. (Counting all addresses it is $2^{16}=65536$ addresses, of which 4 are network and broadcast addresses.)

Block size = 256 - 128 = 128 in the third octet.

Ranges: subnet 1 uses 172.16.0.1 to 172.16.127.254; subnet 2 uses 172.16.128.1 to 172.16.255.254.

Socket programming. A socket is an endpoint of two-way communication between two processes on a network, identified by an IP address and a port number. Socket programming is writing programs that use the socket API to exchange data, usually in a client-server model. Sockets are of two types: stream sockets (TCP, reliable) and datagram sockets (UDP, connectionless).

Typical TCP flow: the server calls socket(), bind(), listen(), accept(); the client calls socket(), connect(); both then use send()/recv() (or read()/write()) and finally close().

# server
import socket
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind(("0.0.0.0", 5000)); s.listen(1)
conn, addr = s.accept()
print(conn.recv(1024).decode())
conn.send(b"Hello client"); conn.close()

# client
c = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
c.connect(("127.0.0.1", 5000))
c.send(b"Hello server"); print(c.recv(1024).decode()); c.close()

Token bucket algorithm. It is a traffic shaping / congestion control method that allows bursts but limits the average rate. Tokens are added to a bucket at a constant rate $r$ (one token per tick); the bucket holds at most $B$ tokens and extra tokens are discarded. A packet (or byte) can be sent only if it takes a token from the bucket; if there is none, it waits or is dropped. If the host is idle, tokens accumulate, so later a burst of up to $B$ packets can be sent at once.

Example. Bucket capacity $B=5$ tokens, rate $r=2$ tokens per second, and the bucket is full at $t=0$. The host suddenly sends 8 packets.

• At $t=0$: 5 packets are sent immediately (burst), the bucket becomes empty; 3 packets are waiting.
• At $t=1$ s: 2 new tokens, so 2 packets are sent; 1 waiting.
• At $t=2$ s: 2 tokens, 1 packet is sent and 1 token remains.

So all 8 packets are sent in 2 seconds, and in the long run the rate is limited to 2 packets per second. The maximum burst in time $t$ is $B+rt$. Unlike the leaky bucket (fixed output rate), the token bucket permits bursts.

Difference between IMAP and POP3

SNMP (Simple Network Management Protocol). SNMP 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 station that sends requests and receives responses and traps.
• Agent: software on a managed device that holds the management data and answers the manager.
• MIB (Management Information Base): the database of managed objects, identified by object identifiers (OIDs).
• SMI: the rules for defining and naming the objects.

Main messages: GetRequest, GetNextRequest, SetRequest, GetResponse and Trap (an unsolicited alert from the agent, sent to port 162). SNMPv1, v2c and v3 exist; v3 adds authentication and encryption.

NGN (Next Generation Network). An NGN is a packet-based, IP-centred network that carries voice, video and data over one common infrastructure and provides services independent of the underlying transport technology. It replaces separate circuit-switched networks (PSTN) with a converged network, as defined by ITU-T.

Layered architecture

1. Access layer. Gives users and devices access to the core: DSL, cable, fibre (FTTH), Wi-Fi, 3G/4G/5G and Ethernet. Access gateways and media gateways convert traffic from legacy networks to IP.
2. Transport (core) layer. A high-capacity IP/MPLS backbone that carries all traffic, with QoS, routers, switches and media gateways to the PSTN (trunking gateways, signalling gateways).
3. Control layer. Handles session control, signalling, call routing and admission control, using the softswitch (media gateway controller) and IMS elements such as the CSCF with SIP signalling.
4. Service/application layer. Application servers provide voice, VoIP, video, messaging, IPTV, VPN and content services, plus network management, billing and security.

Key characteristics

• Separation of services from transport, so new services can be added independently.
• Packet-based transfer with QoS support.
• Open interfaces and APIs, so third parties can create services.
• Generalised mobility and unrestricted access of users to different providers.
• Converged services (voice, data, video) on one network, with lower cost.

Uses of PPP (Point-to-Point Protocol). PPP is a data link layer protocol for direct point-to-point links, such as dial-up lines, DSL (PPPoE), leased lines and SONET.

• Provides framing, with a flag byte and a protocol field that identifies the payload.
• Supports multiple network layer protocols (IP, IPX) over the same link through NCPs.
• Link control: LCP establishes, configures, tests and terminates the link, negotiating options such as MTU and compression.
• Authentication through PAP and CHAP.
• Error detection with a frame check sequence (CRC).
• Dynamic IP address assignment to the client (used by ISPs).
• Connection monitoring and optional compression and multilink bundling.

Functions of Media Access Control (MAC). The MAC sublayer of the data link layer controls how the stations share a common channel.

• Controls access to the shared medium and decides who may transmit and when (CSMA/CD in Ethernet, CSMA/CA in Wi-Fi, token passing).
• Resolves or avoids collisions.
• Framing: builds frames with source and destination MAC addresses.
• Physical addressing with the 48-bit MAC address.
• Error detection with the FCS (CRC) field.
• Interface between the LLC sublayer and the physical layer, and handling of flow of frames to and from the physical layer.

a. IPv6

IPv6 is the successor of IPv4, designed because the 32-bit IPv4 address space (about $4.3\times10^9$ addresses) is exhausted.

• 128-bit address, giving $2^{128}$ addresses, written as eight groups of 4 hex digits, e.g. 2001:0db8:0000:0000:0000:0000:0000:0001, shortened to 2001:db8::1 (leading zeros dropped, one :: for a run of zeros).
• Fixed 40-byte base header, simpler than IPv4's: no header checksum, no fragmentation by routers; extension headers are used for options.
• Header fields: version, traffic class, flow label, payload length, next header, hop limit, source and destination addresses.
• Address types: unicast, multicast and anycast (no broadcast).
• Built-in IPsec security, stateless autoconfiguration (SLAAC), better QoS through the flow label, improved mobility, and no need for NAT.
• Transition: dual stack, tunnelling and translation.

b. Microwave

Microwave is electromagnetic radiation in the frequency range of about 1 GHz to 300 GHz, used as an unguided (wireless) transmission medium.

• It is line-of-sight: transmitter and receiver antennas (parabolic dishes) must see each other, so towers are built every 25 to 50 km, with repeaters for longer distances.
• It carries high data rates and uses a narrow, directional beam.
• Advantages: no cable laying, so it is cheap over difficult terrain, and has high bandwidth.
• Disadvantages: affected by rain, fog and obstacles, subject to multipath fading, cannot pass through buildings, and needs licensing; security is weaker.
• Uses: telephone backbone, TV distribution, cellular backhaul, satellite links, point-to-point links between buildings.

Given: message $M=1101011011$ (10 bits), generator $G=10011$, i.e. $x^4+x+1$ (degree 4).

Step 1. Append 4 zeros (the degree of $G$) to the message:

$1101011011\,0000$

Step 2. Divide by $10011$ with modulo-2 arithmetic (XOR, no borrow). At each step take 5 bits; if the leading bit is 1, XOR with $10011$, otherwise XOR with $00000$; then drop the leading bit and bring down the next bit of the dividend.

The last result is the remainder; its low 4 bits give the CRC:

$R = 1110$

Step 3. Replace the appended zeros with the remainder. The transmitted frame is

$T = 1101011011\,1110 = 11010110111110$

Check. Dividing $T$ by $10011$ gives remainder 0 at the receiver, so no error is detected. (Verification: $T = M\cdot 2^4 + R$, and $M\cdot2^4 \bmod G = R$, so $T \bmod G = R\oplus R = 0$.)

Actual bits transmitted: 11010110111110

Features of the application layer. It is the top layer of the OSI/TCP-IP model and the one closest to the user.

• Provides the interface through which user applications access network services (web, email, file transfer, remote login).
• Defines application protocols: HTTP, FTP, SMTP, POP3/IMAP, DNS, Telnet/SSH, SNMP, DHCP.
• Defines message format, syntax and semantics of requests and responses, and the rules of dialogue (client-server or peer-to-peer).
• Relies on the transport layer (TCP/UDP) for delivery, identifying the service by a port number.
• Handles user authentication, resource availability and data representation where no separate presentation layer exists.
• Provides services such as directory service, mail service, file access and network management.

Why DNS is required. Computers locate each other by IP addresses (e.g. 142.250.190.78), but people remember names (www.google.com). The Domain Name System is a distributed, hierarchical database that maps host names to IP addresses (and back), so users need not memorise numbers. It lets a site change its IP address without changing its name, supports load balancing among several servers, mail routing (MX records) and aliases (CNAME). A single central file would be impossible to maintain, so the namespace is split into root, top-level (.com, .np), second-level domains, etc., each served by name servers.

DNS queries

1. Recursive query. The client asks its local (resolving) name server and demands a final answer. If the server does not know it, the server itself contacts the root, TLD and authoritative servers on behalf of the client and returns the full answer (or an error). The load is on the server.
2. Iterative query. The server answers with the best information it has: either the answer or a referral (the address of another name server to ask next). The querying host (usually the local resolver) then contacts that server, and so on, until it reaches the authoritative server. Example: the resolver asks the root, which refers to the .com server, which refers to the authoritative server for example.com, which gives the IP.
3. Non-recursive query (cached/authoritative answer). The server already knows the answer, either because it is authoritative for the zone or because it is cached from an earlier lookup, and replies at once without contacting other servers.

In practice the host sends a recursive query to its local DNS server, and that server performs iterative queries to the root, TLD and authoritative servers. Caching with a TTL reduces traffic and delay.

Reasons for the transition from IPv4 to IPv6

1. Address exhaustion. IPv4 has 32-bit addresses (about 4.3 billion); the pool is used up because of growth in hosts, mobiles and IoT. IPv6 has 128-bit addresses ($2^{128}\approx3.4\times10^{38}$).
2. Routing table growth. IPv6 uses hierarchical allocation and aggregation.
3. Header efficiency. IPv4's variable header (20 to 60 bytes, with checksum) slows routers; IPv6 has a fixed 40-byte header, no checksum and no router fragmentation.
4. Security. IPsec is built in, while it is optional in IPv4.
5. Quality of service. The traffic class and flow label support real-time traffic.
6. Auto-configuration (SLAAC) and plug-and-play, with no need for DHCP or NAT, restoring end-to-end connectivity.
7. Better mobility and multicast, with anycast and no broadcast.
8. Extensibility through extension headers.

IPv6 datagram format. The datagram has a 40-byte base header, optional extension headers and the payload (data).

| Ver(4) | Traffic class(8) |        Flow label(20)         |
| Payload length(16)        | Next header(8) | Hop limit(8) |
|              Source address (128 bits)                    |
|              Destination address (128 bits)               |
| Extension headers (optional)  ...                         |
| Data (payload)                                            |

• Version (4 bits): 6.
• Traffic class (8 bits): priority/DiffServ class of the packet.
• Flow label (20 bits): identifies a flow so that routers can give it special handling.
• Payload length (16 bits): length of the extension headers plus data, in bytes.
• Next header (8 bits): type of the next header (extension header or TCP=6, UDP=17, ICMPv6=58).
• Hop limit (8 bits): decremented at each router, packet discarded at 0 (like TTL).
• Source and destination addresses (128 bits each).
• Extension headers: hop-by-hop options, routing, fragment (done only by the source), authentication, ESP (encryption) and destination options. They are chained by the next-header field.

Connection-oriented network service. In a connection-oriented service the two end systems first set up a logical connection, then transfer data, and finally release the connection. It works like a telephone call, with three phases:

1. Connection establishment. The sender requests a connection and the receiver accepts it (e.g. the TCP three-way handshake SYN, SYN+ACK, ACK). Parameters such as buffer sizes and sequence numbers are negotiated, and a path (virtual circuit) may be fixed.
2. Data transfer. Data flows over the established connection, with sequence numbers, acknowledgements, retransmission, flow control and congestion control. Packets arrive in order and without loss or duplication.
3. Connection release. Either side closes the connection (FIN/ACK).

Characteristics: reliable and ordered delivery, a fixed path in virtual-circuit networks (X.25, Frame Relay, ATM), overhead of set-up and state maintenance, and suitability for file transfer, email and web (TCP).

Compared with connectionless service (UDP, IP datagram): connection-oriented is more reliable but slower and has more overhead; connectionless is faster, with no guarantee of delivery.

Media Access Control (MAC). MAC is the lower sublayer of the data link layer. In a shared channel (bus, wireless) several stations compete to transmit, and the MAC sublayer decides who may send and when, so that the medium is used efficiently with few collisions.

Functionality

• Channel access control. It uses a MAC protocol: random access (ALOHA, CSMA, CSMA/CD in Ethernet, CSMA/CA in Wi-Fi), controlled access (polling, token passing, reservation) or channelization (FDMA, TDMA, CDMA).
• Collision handling. With CSMA/CD a station listens before sending, detects a collision while sending, sends a jam signal and backs off for a random time (binary exponential backoff). CSMA/CA avoids collisions using RTS/CTS and acknowledgement.
• Framing. It adds the header with source and destination MAC address, and the trailer with the FCS (CRC) for error detection.
• Addressing. It uses the unique 48-bit hardware (MAC) address of the NIC to deliver frames to the right station on the LAN.
• Frame reception. It recognises frames addressed to the station (unicast, multicast, broadcast), checks the CRC and discards damaged frames.
• Interface. It provides service to the LLC sublayer above and uses the physical layer below.

Network Functions Virtualization (NFV). NFV replaces dedicated hardware appliances (routers, firewalls, load balancers, NAT, IDS, DPI, EPC) with software called Virtualized Network Functions (VNFs) that run on standard commodity servers, switches and storage using virtualisation.

Why it is required

• Cost. Proprietary hardware is expensive; commodity servers lower the capital cost (CAPEX) and operating cost (OPEX), including power and space.
• Faster service deployment. A new service is installed as software in minutes rather than by buying and installing a box over months.
• Flexibility and scalability. VNFs can be scaled up or down, or moved, on demand, and capacity is shared between services.
• Less vendor lock-in and hardware lifecycle problems; software is upgraded without replacing hardware.
• Resource efficiency by sharing the same hardware among many functions.
• Automation and orchestration of the network, which supports 5G and cloud services.
• Innovation: easier testing of new services at lower risk.

NFV architecture (ETSI)

1. NFVI (NFV Infrastructure): physical compute, storage and network, plus the virtualisation layer (hypervisor).
2. VNFs: the software implementations of the network functions, with their element managers.
3. NFV MANO (Management and Orchestration): the NFV Orchestrator, the VNF Manager and the Virtualized Infrastructure Manager, which handle life cycle, resources and policies.

Take a class C network, e.g. 192.168.1.0 with default mask 255.255.255.0 (/24), 8 host bits.

Number of subnet bits. For 3 subnets we need $2^n\ge3$, so $n=2$ (giving 4 possible subnets, of which 3 are used).

New mask. /24 + 2 = /26, i.e. 255.255.255.192 (last octet 11000000).

Hosts per subnet. Host bits = 8 - 2 = 6, so $2^6-2=62$ usable hosts. Block size (subnet increment) = 256 - 192 = 64.

Value of the new subnet mask: 255.255.255.192 (/26), giving subnets of 62 usable hosts each.

Token bucket. The token bucket is a traffic shaping (congestion control) algorithm that controls the average rate of data sent into a network but allows controlled bursts.

Working mechanism

1. A bucket can hold at most $B$ tokens (its capacity).
2. Tokens are generated at a constant rate $r$ (e.g. one token every $1/r$ seconds) and put into the bucket. If the bucket is full, new tokens are discarded.
3. To send a packet (or $n$ bytes) the sender must remove a token (or $n$ tokens). If enough tokens are available they are consumed and the packet is sent at once.
4. If there are not enough tokens, the packet waits in a queue (shaping) or is dropped/marked (policing) until tokens arrive.
5. When the source is idle, tokens accumulate up to $B$. Later the source can send a burst of up to $B$ packets back to back, after which the rate falls to $r$.

Maximum burst/output in time $t$:

$\text{data sent}\le B+r\,t$

Example. $B=4$, $r=1$ token/s, bucket full. A burst of 6 packets arrives: 4 are sent immediately, the 5th at $t=1$ s and the 6th at $t=2$ s. The long-term rate does not exceed 1 packet/s.

Difference from leaky bucket: the leaky bucket outputs at a fixed rate and smooths bursts completely, whereas the token bucket saves unused credit and allows bursts, so it suits bursty traffic.

PPP (Point-to-Point Protocol). PPP is a data link layer protocol (RFC 1661) used to carry network layer packets over a direct point-to-point link, such as a dial-up modem, DSL (PPPoE), leased line or SONET. It provides framing (flag 01111110, address, control, protocol, payload, FCS), error detection with a CRC, support for several network protocols, authentication and negotiation of options.

PPP is made up of three parts: framing, the Link Control Protocol (LCP), and Network Control Protocols (NCPs); the authentication protocols PAP and CHAP are used in between.

Link setup (phases)

1. Link dead. There is no physical connection. When a carrier is detected (or the user requests a connection), the link moves to the establish phase.
2. Link establishment (LCP). The two ends exchange LCP packets (Configure-Request, Configure-Ack, Nak, Reject) to negotiate options such as maximum frame size (MTU), authentication protocol, compression and magic number. If agreed, the link is open.
3. Authentication (optional). The peer proves its identity: PAP (password sent in clear text in a two-way handshake) or CHAP (three-way challenge-response with a hashed value, safer). If it fails the link is terminated.
4. Network-layer configuration (NCP). One NCP per network protocol is run. For IP, IPCP assigns or negotiates the IP address, DNS and compression parameters.
5. Open (data transfer). Network packets are exchanged inside PPP frames.
6. Link termination. When data transfer is finished, LCP sends Terminate-Request and Terminate-Ack, and the physical link is released, returning to the dead phase.

Wireless (unguided) media carry signals through free space as electromagnetic waves, without a physical conductor. Two common ones are radio waves and microwaves.

1. Radio waves

• Frequency range: about 3 kHz to 1 GHz. They are omnidirectional: the antenna radiates in all directions, so the sender and receiver need not be aligned.
• They pass through walls and travel long distances, but are easily interfered with by other transmitters and electrical equipment. Lower frequencies reflect from the ionosphere and can travel beyond the horizon.
• Because a band is shared, transmission is regulated by government licensing.
• Uses: AM/FM radio, television broadcast, cordless phones, paging, mobile cellular networks.
• Advantages: wide coverage, no line of sight, cheap receivers. Disadvantages: low data rate at low frequencies, interference, poor security because anyone in range can listen.

2. Microwaves

• Frequency range: about 1 GHz to 300 GHz. They are unidirectional, so the transmitting and receiving dish antennas must be aligned in line of sight.
• Because of the curvature of the earth, terrestrial microwave towers are placed about every 40-50 km with repeaters between them. Signals do not pass well through walls and are affected by heavy rain.
• Narrow beams allow high data rates and many links in the same area without interference. Higher bands (above 4 GHz) are used for satellite links.
• Uses: point-to-point telephone and data links, satellite communication, cellular backhaul, wireless LANs, Bluetooth.
• Advantages: high bandwidth, no cable laying across rivers or hills. Disadvantages: line of sight required, weather and obstruction effects, costly towers.

ICMP (Internet Control Message Protocol)

IP is an unreliable, connectionless protocol with no error reporting or query mechanism. ICMP, a network-layer protocol carried inside IP datagrams (protocol number 1), makes up for this. It does not correct errors; it reports them to the source.

Message types:

• Error-reporting messages: destination unreachable, source quench (congestion), time exceeded (TTL reaches 0 or reassembly timeout), parameter problem, and redirect (a better route exists).
• Query messages: echo request/reply (used by ping), timestamp request/reply, address-mask request/reply, router solicitation/advertisement.

Message format: 8-bit type, 8-bit code, 16-bit checksum, then type-specific data. Error messages also carry the IP header and first 8 bytes of the datagram that caused the problem. ping and traceroute are built on ICMP.

IGMP (Internet Group Management Protocol)

IP multicasting sends one packet to a group of hosts. IGMP lets hosts tell their local multicast router which groups they want to join, and lets routers keep track of group membership on each network. It manages group membership only; routing of multicast packets is done by multicast routing protocols such as DVMRP, MOSPF and PIM.

Main messages:

• Membership query (general or group-specific): sent by the router to see who is still a member.
• Membership report: sent by a host to join a group or answer a query.
• Leave report: sent by a host when it leaves a group.

Multicast addresses are class D (224.0.0.0 to 239.255.255.255). IGMP messages are encapsulated in IP datagrams (protocol number 2) with TTL 1, so they stay on the local network.

Advantages of layered architecture

• Divide and conquer: a complex communication task is split into smaller, manageable functions, so each layer is easier to design, implement and debug.
• Modularity and independence: each layer uses only the services of the layer below and offers services to the layer above. A layer can be changed (for example, Ethernet replaced by Wi-Fi) without affecting the other layers, provided the interface stays the same.
• Standardisation and interoperability: each layer has a defined protocol and interface, so products of different vendors work together.
• Easy troubleshooting and maintenance: faults can be isolated to a particular layer.
• Abstraction: a higher layer need not know how the lower layer works (information hiding).
• Easier teaching and development: new protocols can be added at one layer without redesigning the whole system.

TCP/IP protocol stack

TCP/IP has four layers (some books split the lowest into physical and data link, giving five). Data passes down the stack at the sender, each layer adding its header (encapsulation), and up at the receiver, where headers are removed.

Working in brief

1. The application produces data (for example, an HTTP request).
2. TCP splits it into segments, adds source and destination port numbers, sequence numbers and checksum.
3. IP adds the source and destination IP addresses and routes the packet hop by hop using routing tables.
4. The network access layer adds the MAC addresses and a trailer (FCS) and sends the frame as signals.
5. At the destination the process is reversed: frame, packet, segment, data, and the port number delivers the data to the right application.

Compared with the OSI model, TCP/IP is protocol-driven, has fewer layers, and is the model the Internet actually uses.

Services of the transport layer

• Process-to-process delivery: using port numbers, data is delivered to the correct application process, not just the host.
• Segmentation and reassembly: a large message is divided into segments with sequence numbers and reassembled at the receiver.
• Connection management: connection establishment, maintenance and release (TCP three-way handshake and termination), or connectionless service (UDP).
• Flow control: prevents a fast sender from overwhelming a slow receiver (sliding window).
• Error control: detects corrupted, lost, duplicated or out-of-order segments (checksum, acknowledgements, retransmission).
• Congestion control: reduces the sending rate when the network is congested (slow start, congestion avoidance).
• Multiplexing and demultiplexing: several applications share one network connection and are separated at the receiver by port number.
• Addressing: socket address = IP address + port number.

Distance Vector Algorithm

In distance vector routing, each router keeps a table (vector) with the best known distance (cost) to every destination and the next hop. Each router periodically sends its whole vector only to its directly connected neighbours. Each router uses the Bellman-Ford equation:

$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 the cost from $v$ to $y$ as advertised by $v$.

Steps: (1) initialise: distance 0 to itself, link cost to neighbours, $\infty$ to others; (2) exchange vectors with neighbours; (3) recompute using the equation; (4) repeat until no table changes (convergence).

Example. Network with routers A, B, C, D and link costs A-B = 1, B-C = 2, A-C = 5, C-D = 1.

Initial tables of A (distance to A, B, C, D): 0, 1, 5, $\infty$.

Initial vectors: B = (1, 0, 2, $\infty$); C = (5, 2, 0, 1); D = ($\infty$, $\infty$, 1, 0).

After one exchange, A gets B's and C's vectors:

• To C: $\min(5+0,\;1+2)=3$ via B.
• To D: $\min(1+\infty,\;5+1)=6$ via C.

A's table: A = 0, B = 1, C = 3 (via B), D = 6 (via C).

After the second exchange, C has updated its distance to A: $\min(5, 2+1)=3$ via B, and B has learned D = 3 through C. When A receives B's new vector (B to D = 3), A calculates $1+3=4<6$, so D = 4 via B.

Final table of A: B = 1, C = 3, D = 4; no further changes, so the network has converged.

Drawbacks: slow convergence and the count-to-infinity problem, reduced by split horizon, poison reverse and hold-down timers. RIP is a protocol using this algorithm.

IPv4 versus IPv6

Cyclic Redundancy Check (CRC)

CRC is an error-detection method. The sender treats the data as a binary polynomial, appends $n$ zeros ($n$ = degree of the generator, i.e. generator length minus 1), divides by the generator using modulo-2 (XOR) division and appends the remainder to the data. The receiver divides the received codeword by the same generator; a zero remainder means no error was detected.

Example. Data = 100100, generator = 1101 (so $x^3+x^2+1$, $n=3$).

Append three zeros: 100100000. Long division by XOR with 1101 wherever the leading bit is 1 (shift one place each step):

The last three bits give the remainder 001.

Transmitted codeword = data + remainder = 100100001.

Receiver check: dividing 100100001 by 1101 gives remainder 000, so the frame is accepted. If a bit were flipped in transit, for example 100110001, the division gives a non-zero remainder and the error is detected.

CRC detects all single-bit and burst errors shorter than the generator length, and any odd number of errors if the generator has factor $(x+1)$.

TCP is connection-oriented: before data is exchanged, the two ends establish a connection using a three-way handshake. It synchronises initial sequence numbers (ISN) and window sizes of both sides.

Steps

1. SYN (client to server): the client sends a segment with SYN = 1 and an initial sequence number, say $seq = x$. The client moves from CLOSED to SYN-SENT.
2. SYN + ACK (server to client): the server, which was in LISTEN state, replies with SYN = 1, ACK = 1, its own initial sequence number $seq = y$ and acknowledgement number $ack = x+1$. It moves to SYN-RECEIVED.
3. ACK (client to server): the client sends ACK = 1 with $seq = x+1$ and $ack = y+1$. Both sides enter the ESTABLISHED state and data transfer can start.

Client                         Server
  |---- SYN, seq=x ------------>|
  |<--- SYN+ACK, seq=y, ack=x+1-|
  |---- ACK, seq=x+1, ack=y+1 ->|
  |        ESTABLISHED          |

Points

• The SYN segment consumes one sequence number although it carries no data, which is why the acknowledgement is $x+1$.
• The random ISN prevents old duplicate segments from being accepted and makes spoofing harder.
• A third step is needed so that the server knows the client received its ISN, giving a reliable two-way agreement.
• Connection release uses four steps (FIN, ACK, FIN, ACK). A SYN flood attack exploits half-open connections.

Purpose of DNS

The Domain Name System is a distributed, hierarchical database that maps human-friendly domain names (such as www.example.com) to IP addresses (and back, by reverse lookup), because people remember names more easily than numbers and the machines need IP addresses. It uses UDP/TCP port 53. It also provides mail-server (MX) lookup, aliases (CNAME) and load distribution.

DNS hierarchy

Root servers, then top-level domain (TLD) servers (.com, .org, .np), then authoritative servers of an organisation. Each zone's authoritative server holds the records of its names.

Resolving a name (example: www.example.com)

1. The application calls the local resolver, which first checks its own cache (and the hosts file).
2. If not found, the resolver sends a query to the local (recursive) DNS server of the ISP.
3. If the local server has no cached answer, it asks a root server, which replies with the address of the .com TLD server.
4. The local server asks the TLD server, which replies with the authoritative server of example.com.
5. The local server asks the authoritative server, which returns the IP address record (A record).
6. The local server caches the answer (for its TTL) and returns it to the resolver, which gives it to the application. The browser then connects to that IP.

Query types: recursive (client asks the server to do the entire resolution) and iterative (server returns the best referral and the asker continues). Caching reduces traffic and delay.

Guided (wired) media guide the signal along a physical path. The main types are twisted pair, coaxial cable and optical fibre.

1. Twisted-pair cable

• Two insulated copper wires twisted together, which reduces crosstalk and electromagnetic interference. Several pairs are bundled in one jacket.
• UTP (unshielded): cheap, easy to install, categories Cat5e/Cat6 support 100 Mbps to 10 Gbps up to 100 m; used in LANs and telephone lines. STP (shielded): metal foil shield gives better noise protection but is costlier and heavier.
• Connector: RJ-45 (RJ-11 for telephone).

2. Coaxial cable

• A central copper conductor, surrounded by an insulator, a braided metal shield and an outer plastic jacket.
• Better shielding and bandwidth than twisted pair, supporting longer distances. Types: 50-ohm baseband (Ethernet 10Base2/10Base5) and 75-ohm broadband (cable TV).
• Connectors: BNC, F-type. Disadvantages: bulky, more expensive than UTP, bad connectors cause signal loss.

3. Optical fibre

• Transmits data as light pulses by total internal reflection inside a glass or plastic core surrounded by cladding.
• Single-mode (thin core, laser, long distance, tens of km) and multimode (thicker core, LED, shorter distance).
• Advantages: very high bandwidth (Gbps to Tbps), low attenuation, immune to electromagnetic interference, secure, thin and light. Disadvantages: costly, difficult to install and splice, fragile, unidirectional (a pair is needed).

Comparison: fibre gives the best speed and distance; coaxial is in the middle; UTP is cheapest and the most common for short distances.

Both are sliding window ARQ (Automatic Repeat reQuest) protocols of the data link layer that let the sender transmit several frames before receiving an acknowledgement, improving link utilisation compared with stop-and-wait. Frames are numbered; with $m$-bit sequence numbers the sender window is up to $2^m-1$ in Go-Back-N and $2^{m-1}$ in Selective Repeat.

Go-Back-N ARQ

• Sender window size up to $2^m-1$; receiver window size is 1 (accepts frames only in order).
• The sender keeps copies of all unacknowledged frames and starts a timer.
• If a frame is lost or damaged, the receiver discards that frame and all later frames (out of order) and sends no ACK for them (or a NAK).
• When the timer expires (or a NAK arrives), the sender goes back and retransmits the lost frame and all frames after it, even those that arrived correctly.
• ACKs are cumulative (ACK $n$ confirms all frames before $n$).
• Simple and needs little buffering at the receiver, but wastes bandwidth on noisy links.

Selective Reject (Selective Repeat) ARQ

• Both sender and receiver windows are of size up to $2^{m-1}$.
• The receiver accepts and buffers out-of-order frames within its window, and sends a NAK or individual ACK for the missing frame.
• The sender retransmits only the lost or damaged frame. The receiver reorders buffered frames and delivers them in sequence to the network layer.
• More efficient in bandwidth, but more complex: the receiver needs a buffer and sorting logic, and the sender needs one timer per frame.

Example: frames 0-5 are sent and frame 2 is lost. Go-Back-N resends 2, 3, 4, 5; Selective Reject resends only 2.

HTTP (HyperText Transfer Protocol)

HTTP is the application-layer protocol of the World Wide Web, used by browsers (clients) to request and receive web pages and other resources from web servers. It follows a client-server request/response model over TCP, by default on port 80 (HTTPS uses 443). It is stateless: the server keeps no memory of earlier requests (cookies are used to maintain state). HTTP/1.0 uses non-persistent connections; HTTP/1.1 uses persistent connections by default.

HTTP request message

Parts:

1. Request line: method, URL and version, for example GET /index.html HTTP/1.1. Methods: GET (fetch), POST (send data), HEAD, PUT, DELETE, etc.
2. Header lines: Host: www.example.com, User-Agent, Accept, Accept-Language, Connection: keep-alive, Cookie.
3. A blank line.
4. Entity body: present for POST/PUT (form data); empty for GET.

HTTP response message

1. Status line: version, status code, phrase, for example HTTP/1.1 200 OK. Codes: 1xx informational, 2xx success, 3xx redirection (301 Moved Permanently), 4xx client error (404 Not Found), 5xx server error (500 Internal Server Error).
2. Header lines: Date, Server, Content-Type: text/html, Content-Length, Last-Modified, Set-Cookie.
3. A blank line.
4. Entity body: the requested resource (HTML, image, etc.).

Software Defined Networking (SDN)

A software defined network is a network architecture that separates the control plane (decision-making: which path packets take) from the data plane (forwarding of packets) and moves the control logic into a logically centralised, programmable software controller. In a traditional network each router or switch contains both, configured box by box; in SDN the switches become simple forwarding devices that follow rules installed by the controller.

Architecture (three layers)

1. Application layer: network applications such as routing, load balancing, firewall, traffic engineering, which use the controller through the northbound API (e.g. REST).
2. Control layer: the SDN controller (OpenDaylight, ONOS, Ryu) holds a global view of the network, computes routes and installs flow rules.
3. Infrastructure (data) layer: physical or virtual switches that forward packets according to flow tables.

The controller communicates with the switches through the southbound API, the best known being OpenFlow. A flow table entry has match fields, actions (forward, drop, modify) and counters. When a packet matches no entry, the switch asks the controller.

Advantages: central control and easy management, programmability and automation, faster deployment of new services, better use of resources and traffic engineering, vendor independence and lower cost.

Disadvantages: the controller is a single point of failure and a bottleneck (needs replication), and it is a security target.

(a) Leaky bucket

The leaky bucket is a traffic shaping algorithm used for congestion control. It converts bursty traffic into a steady, constant-rate output.

• Imagine a bucket with a small hole at the bottom. Water (packets) may be poured in at any rate, but leaks out at a constant rate.
• Packets from the host arrive at irregular rates and are placed in a finite queue (the bucket). Packets are sent out at a fixed rate $\rho$ regardless of the input rate.
• If the bucket is full when a packet arrives, the packet is discarded (or marked). Bursts shorter than the bucket capacity are smoothed.
• In a variant for variable-size packets, a fixed number of bytes per clock tick is sent.

Example: a host sends data at 12 Mbps for 2 s and is then silent for 8 s; the bucket outputs a steady lower rate, e.g. 2 Mbps for the whole 10 s.

Limitation: the output rate is always fixed, even if the network is idle, so it cannot use spare capacity (the token bucket algorithm allows bursts).

(b) FTP (File Transfer Protocol)

FTP is an application-layer protocol for transferring files between a client and a server over TCP. It is defined to be reliable and uses two separate connections:

• Control connection (port 21): stays open for the whole session and carries commands (USER, PASS, LIST, RETR, STOR, QUIT) and replies (three-digit codes such as 220, 226, 530).
• Data connection (port 20 in active mode): opened for each file transfer or directory listing and closed afterwards.

Modes: active (server connects back to the client's data port) and passive (server gives a port and the client connects, which works through firewalls). Transfer types: ASCII or binary; structure: file, record, page; transmission: stream, block, compressed.

FTP requires authentication (user name and password, or anonymous login), but sends data and passwords in plain text, so SFTP or FTPS is used for security.