Routing Protocols and Internet Architecture

Network Diagnostic Tools and Connectivity Testing

Ping is a fundamental diagnostic tool used to verify connectivity between a local host and a destination host or server. It utilizes the Internet Control Message Protocol (ICMP) by generating an ICMP echo request, which is sent to a target IP address or host name. Upon receiving this request, the destination generates an ICMP echo reply. This full cycle facilitates the measurement of delay, specifically the round-trip time (RTT). The output of a ping command typically includes the size of the packet (defaulting to $64\text{ bytes}$), the sequence number, the Time to Live ($TTL$), and the RTT in milliseconds. At the end of a series of requests, ping provides a summary of statistics including the number of packets transmitted and received, the percentage of packet loss, and the minimum, average, maximum, and standard deviation of the RTT.

TraceRoute is another diagnostic tool relying on ICMP to map the specific path packets take from a source to a destination. Its mechanism involves sending ICMP requests with an incrementing $TTL$ value, starting at $TTL = 1$. Because a $TTL$ of $1$ causes the first hop router to discard the packet and return an "ICMP time exceeded" message, TraceRoute can identify each subsequent hop. It typically sends three packets for each $TTL$ value. The output displays the hop number, the IP address of the router, and three delay measurements. Asterisks ($***$) in the output indicate that a router is configured for security purposes not to return ICMP messages. Significant jumps in delay—for example, from $18\text{ ms}$ or $19\text{ ms}$ to $280\text{ ms}$—often indicate that the path has traversed an intercontinental link.

Fundamental Principles of IP Addressing and Subnetting

For any node, including hosts, servers, or routers, to participate in the Internet, it must possess a unique IP address. This configuration can be achieved through manual assignment or dynamically via the Dynamic Host Configuration Protocol (DHCP). DHCP provides three essential components for Internet communication: a unique IP address, a default gateway (the first-hop router), and a DNS server. An IPv4 address consists of $32\text{ bits}$, commonly represented in dotted-quad notation (e.g., $192.168.1.75$). This can be converted to binary by translating each decimal quad into its $8\text{-bit}$ equivalent.

Subnet masks, or net masks, serve as a method to convey the prefix information of an address. In CIDR (Classless Inter-Domain Routing) notation, an address like $192.168.1.75/24$ indicates a prefix length of $24$. The net mask for this prefix is $255.255.255.0$, which in binary consists of $24$ ones followed by $8$ zeros. Performing a bitwise AND operation between a host's IP address and its subnet mask identifies the network address. This logical structure allows routers to determine if a destination is local or requires routing to an external gateway.

Packet Encapsulation and the Forwarding Process

The delivery of data across the Internet is a multi-step encapsulation process. A Transmission Control Protocol (TCP) segment is first encapsulated into an IP datagram. The IP layer at the source host sets the destination IP address (e.g., $4.1.1.2$) and consults its forwarding table. If the destination is not local, the IP layer selects the default route to the first-hop router (e.g., $1.2.2.1$). To send the packet over a local Link Layer (such as $802.11$ WiFi), the host must determine the Medium Access Control (MAC) address of the router using the Address Resolution Protocol (ARP). Once the MAC address is retrieved, the IP datagram becomes the payload of an $802.11$ frame.

When a router receives the frame, it verifies the destination MAC address, strips the Link Layer header, and passes the IP datagram to its own IP layer. The router then performs Longest Prefix Matching (LPM) on its forwarding table. LPM ensures that the router selects the entry where the destination bits match the required prefix bits for the longest possible length. For example, if a destination address matches both a prefix of length $8$ and a prefix of length $24$, the router will prioritize the $24\text{-bit}$ match. The router then identifies the outgoing interface and the next-hop IP, repeating the process until the packet reaches the final destination.

Conceptual Differentiation: Routing vs. Forwarding

Network designers divide the Network Layer into the Data Plane and the Control Plane. Forwarding is a Data Plane function and refers to the local process at each node where a received packet's header is used to look up an interface in a forwarding table. At Layer 2 (switches), this involves matching full MAC addresses, while at Layer 3 (routers), it involving Longest Prefix Matching. An analogy for forwarding is the decision made at every individual turn when driving from one location to another.

Routing is a Control Plane function and represents the process of building and maintaining the forwarding tables. It employs distributed algorithms that exchange messages between routers to compute optimal paths from any source to any destination. Routing algorithms act as autonomous replacements for manual table configuration. An analogy for routing is the overarching selection of the best path or route before beginning a journey.

Distance Vector Routing Protocols and the Convergence Problem

The Distance Vector algorithm, exemplified by the Routing Information Protocol (RIP), requires each node to maintain a data structure called a distance vector. This vector contains the estimated distance (cost, hop count, or delay) from that node to known destinations. Routers model the network as a graph where nodes represent routers and edges represent links with specific costs. In a distance vector system, routers periodically share their entire distance vector with their immediate neighbors. When a node receives a neighbor's vector, it adds the cost of the link to that neighbor to the neighbor's reported distances. If a shorter path is discovered, the node updates its own routing table.

Nodes use two types of updates: periodic updates and triggered updates. Periodic updates occur even if the topology has not changed to inform neighbors that a router is still active. Triggered updates are sent immediately upon detecting a link failure to hasten network recovery. For instance, if a link to a node G fails, the detecting router (F) sets the cost to infinity and informs its neighbor (A). A then updates its cost to infinity until it receives a better advertisement from another neighbor (C).

Distance vector protocols are susceptible to the "count to infinity" problem, particularly during link failures that partition the network. If node E becomes isolated from nodes A, B, C, D, and F, and node D incorrectly advertises a path to E, nearby nodes may enter a loop where they increase their costs to E incrementally ($4$, then $5$, then $6$, and so on). This continues until the costs reach a predefined value for infinity. Partial solutions include split horizon, route poisoning, and poison reverse. A complete solution is offered by Link State routing.

Link State Routing and Dijkstra's Algorithm

Link State routing, primarily through the Open Shortest Path First (OSPF) protocol, solves many issues inherent in distance vector protocols. In this model, every node tracks the state and cost of its links to all direct neighbors. This information is packaged into a Link State Packet (LSP), which contains the node ID, a list of neighbors and costs, a sequence number to identify unique packets, and a Time to Live ($TTL$) to prevent indefinite circulation.

LSPs are disseminated through reliable flooding, where each node forwards a received LSP to all neighbors except the one from which it was received. Once a node has accumulated LSPs from every node in the network, it possesses a complete map of the topology. It then calculates the shortest paths to all destinations using Dijkstra's forward search algorithm. This contrast with the Bellman-Ford approach used in distance vector routing.

Hierarchical Routing and OSPF Areas

OSPF faces scalability issues in massive networks due to the overhead of flooding LSPs and the storage required for full topology maps. To mitigate this, networks are organized into routing areas. A routing area is a set of routers configured to exchange link state information exclusively with each other, thereby constraining the scope of flooding.

Area $0$, known as the backbone area, serves as the central hub for inter-area traffic. Border routers are members of both the backbone area and one or more non-backbone areas. These border routers aggregate or summarize the routes within their area into a single advertisement for the rest of the network. While this improves scalability, it introduces a trade-off: packets destined for a different area must traverse the backbone, which may result in suboptimal routing paths.

Inter-Domain Routing and the Border Gateway Protocol (BGP)

The Internet is composed of multiple Autonomous Systems (AS), which are areas managed by a single administrative domain (e.g., a university network or an ISP). Each AS is assigned a unique AS Number. Intra-domain routing occurs within an AS, while inter-domain routing connects across different ASes. The Border Gateway Protocol (BGP) facilitates inter-domain routing. Traffic is categorized as local (originating or ending within an AS) or transit (just passing through). Stub ASes do not handle transit traffic.

BGP is a path vector protocol, meaning it advertises the complete path of ASes to reach a destination (e.g., $AS1$ to $AS2$ to $AS3$). This allows for easy loop detection and enables policy-based routing. Policies allow administrators to prioritize paths based on business relationships rather than raw cost. For example, an AS might avoid routing traffic through a competitor's network even if it is the shortest path. BGP operates via External BGP (EBGP) for communication between border routers of different ASes and Internal BGP (IBGP) for distributing that information within an AS. In inter-domain routing, the primary goal is reachability rather than optimality.

Global Internet Structure and ISP Hierarchy

The Internet hierarchy is topped by Tier 1 ISPs, such as Sprint, AT&T, and NTT. These entities have vast geographical presences and own the transcontinental and intercontinental cables that form the Internet's backbone. Below them are regional ISPs (e.g., One New Zealand or 2degrees), which pay Tier 1 providers for global connectivity based on data volume. ISPs connect to each other either through direct peering or at Internet Exchange Points (IXPs).

Modern internet infrastructure is increasingly dominated by hyperscalers like Google, Microsoft, and Amazon. These companies operate their own massive private networks and cloud infrastructures, often bypassing traditional Tier 1 and Tier 2 ISPs. A study from $2021$ noted that these hyperscalers reach more than $76\%$ of the Internet without traversing traditional high-tier ISPs, representing a significant shift from the early, more decentralized days of the network.

Questions and Course Administration

Discussion regarding Project 1 highlighted the importance of word count limits. These limits are designed to encourage concise communication and help students prioritize the most important technical points. Tutors, who are also students, use these limits to ensure fair and timely marking. If word counts are significantly exceeded, tutors may stop reading once the limit is reached. Administrative changes include a swap in the course delivery schedule: Chris will cover weeks $5$ and $6$, while the current lecturer will return for weeks $11$ and $12$. Additionally, NUCU Assignment 1 is due tomorrow before midnight and is worth $2.5\%$ of the final grade; it serves as practice for the final exam format.