Internet Routing and Data Link Layer Protocols: Core Concepts

Posted on Jan 26, 2025 in Computer Engineering

Goal of Routing

Each router finds a path or route to every destination and produces a forwarding table. Outcome: Packets follow computed paths if each router forwards according to its table.

Network State

Represents the set of functioning links and routers at a given time. Routing adapts to dynamic changes (e.g., link or router failures) by recomputing routes based on the current network state.

Local vs. Global Views

• Global View: The network state represents an overall view used to compute paths.
• Local View: Forwarding tables represent the traffic paths between a router and its neighbors.

Routing uses the global view to determine the best paths, while forwarding applies the local view to send packets to the next hop.

Decentralized Routing

Each router obtains the current network state and independently uses a routing algorithm to compute its forwarding table. Problem: Independent computations can lead to invalid routes.

Invalid Routes

• Loop: A packet traverses a cycle of routers, repeatedly passing through the same routers without reaching the destination. Example: A loop between router 0 and router 2.
• Blackhole: A packet is forwarded to a next hop that has failed, resulting in packet loss. Occurs because routers may use inconsistent state information—for example, router 0 thinks router 2 is down when it is not.

Routing Correctness

Decentralized routing is correct if and only if every route it produces is loop-free and blackhole-free.

• Necessary Condition: A packet will not reach its destination if the route contains a loop or blackhole.
• Sufficient Condition: If there are no loops or blackholes, in the worst case, the packet may visit every node before reaching the destination.

Verifying Correctness of Forwarding Tables

For each destination d:

1. At each router, draw an arrow to the next hop for d.
2. If you get a spanning tree, the routing table is valid for d.

Routing is correct if tables are valid for all destinations.

Shortest-Path Routing

At each router, the goal is to find the shortest path or route to every destination. Why Shortest Paths? They minimize end-to-end latency, which is most useful in a network. Decentralized routing algorithms compute these shortest paths using network graph representations.

Network as a Graph

A network can be represented as a graph G(N, E), where N is the set of vertices (routers) and E is the set of edges (links).

• Vertices: Represent nodes such as routers (u, v, …).
• Edges: Represent links between nodes ((u, v), (v, x), …).
• Edge Cost: Each edge has a cost (c_{u,v} = 2) which can represent latency or another measure of link usage. Costs could be latency or any other metric that reflects the cost of using a link.

Algorithms for Finding Least-Cost Paths

Many algorithms exist to find the shortest or least-cost paths in a graph. Two key algorithms used in routing are:

• Dijkstra’s Algorithm: Finds the shortest paths using a greedy approach.
• Bellman-Ford Algorithm: Finds least-cost paths, useful for decentralized or distributed networks.

The Dijkstra Algorithm

Also known as the Shortest-Path First (SPF) algorithm. It iteratively selects the shortest path from the source to each node in the network. Key Idea: It processes nodes in increasing order of distance from the source, ensuring the shortest paths are computed efficiently.

Dijkstra Example

Illustrates how the algorithm computes the shortest path in a network graph. Each step involves updating the shortest known distance to each node and determining the next node to process based on the smallest tentative distance.

Internet Routing

Two main types:

• Intra-Domain Routing: Routes traffic within an Autonomous System (AS), usually using shortest-path algorithms.
• Inter-Domain Routing: Routes traffic between ASes based on policies.

Different goals for each type.

Routing Algorithms vs. Protocols

Dijkstra’s Algorithm assumes the entire graph is given and runs on a single machine. In the Internet, where network state changes frequently, routing protocols are needed to distribute this state across routers.

Intra-Domain Routing Protocols

Two families:

• Link-State Protocols (based on Dijkstra’s Algorithm, e.g., OSPF, IS-IS)
• Distance-Vector Protocols (based on the Bellman-Ford Algorithm, e.g., RIP v2, IGRP)

Link-State Routing

Uses tuples <s c>, where s is the state (up or down) and c is the cost. Key Steps:

1. Reliably distribute link state.
2. Each router builds the current network state.
3. Each router runs Dijkstra’s Algorithm on this state.
4. Update forwarding tables based on results.

Protocols: OSPF (Open Shortest Path First) and IS-IS.

Reliable Dissemination (Flooding)

Link-State Advertisement (LSA): Contains the link state for all links on a router. Each router sends its LSA to all neighbors, who forward it to their neighbors (excluding the sender), ensuring the LSA reaches every router with at least one functioning link. When to Initiate Flooding: Upon topology changes (link/node failure or recovery), configuration changes (link cost updates), or periodically to refresh state.

Updating Forwarding Tables

After receiving LSAs, routers run Dijkstra’s Algorithm and update their local forwarding tables.

Routing Convergence

The process by which all routers consistently reflect new LSAs. Properties at Convergence: All nodes have the same link-state database, forward packets on shortest paths, and direct traffic to the correct next hop. Convergence Time: Delay between link failure detection and full convergence. Sources of Delay: Time to detect failure, flood LSAs, and run Dijkstra’s Algorithm.

Impact of Convergence Delays

Transient inconsistency can cause loops, blackholes, or out-of-order delivery.

Example of Transient Loop

Occurs when different routers have inconsistent views of the network state. Example: Router u and w think the path to destination y goes through router v, but v thinks it goes through w, creating a loop.

Complexity of Link-State Routing

• Message Complexity: O(NE)
• Computation Complexity: O(N²)
• Convergence Complexity: O(diameter)
• Table Size: O(N)

Congestion-Adaptive Link-State Routing

Adjusts link costs based on current load, similar to Google Maps adjusting routes based on traffic. Problem: Load-dependent costs can cause oscillations between paths.

Scaling Link-State Routing

OSPF Hierarchy: Divides the network into a backbone and multiple areas to improve scalability. LSAs: Flooded within an area. Border Routers: Summarize internal distances and receive summaries from other areas via the backbone.

Distance-Vector Routing

Key Concept: Each node learns paths from its neighbors, computes paths based on these, and advertises them back. Based on: Bellman-Ford Algorithm.

Bellman-Ford Algorithm

Each node x maintains a vector Dx = [Dx(y)], representing the cost to each destination y. Distance Update: When the cost or neighbor’s distance changes, apply the Bellman-Ford equation to update the vector and propagate it to neighbors.

Distance-Vector Protocols

Define message formats for exchanging distance vectors and rules for updates. Example Protocols: RIP (v1 and v2).

Convergence in Distance-Vector Routing

Routers continuously exchange messages until all nodes have computed the least-cost paths (convergence). Issues: Loops, blackholes, and slower convergence compared to link-state protocols.

Count-to-Infinity Problem

Occurs when routers continuously increment distance estimates, causing packets to loop indefinitely. Example: If router y’s link to destination x fails, it can keep increasing the distance without limit.

Avoiding Count-to-Infinity

Poisoned-Reverse: If a router y routes to x through neighbor z, it advertises an infinite cost for x back to z, breaking the loop. Limitation: Doesn’t always prevent loops, as designing fully effective distributed algorithms is challenging.

Complexity of Distance-Vector Routing

• Message Complexity: Depends on topology.
• Computation Complexity: O(N) per update.
• Convergence Complexity: O(diameter).
• Table Size: O(N).

The Internet Today

Initially owned and operated by the US National Science Foundation, the Internet is now composed of different parts owned by various companies. Each part is called a domain or Autonomous System (AS). Inter-domain routing determines paths across these domains, ensuring Internet traffic flows over multiple ASs.

Autonomous Systems (AS)

Contain routers and end hosts managed by a single entity (e.g., USC, AT&T, or Comcast). Each AS has a unique 32-bit identifier (AS number), with about 76,000 ASs currently on the Internet.

AS Tiers

• Tier-1: Global or continental providers.
• Tier-2: Regional providers (e.g., within a U.S. state).
• Tier-3: Local providers (e.g., within a metro area).

Interconnects occur at Internet eXchange Points (IXPs).

Routing Protocols

Intra-domain routing (inside an AS) uses protocols like OSPF and IS-IS. Inter-domain routing (between ASs) uses BGP (Border Gateway Protocol).

Scaling Challenges

Routing must efficiently manage paths to billions of destinations.

• Strawman 1: Routing based on single hosts leads to large forwarding tables and high router CPU load.
• Strawman 2: Routing based on IP prefixes reduces table size and CPU use but requires balancing prefix length and path optimality.

Hierarchical Addressing

IP addresses reflect network location. ISPs assign IP blocks (e.g., 200.23.16.0/23) to customers. This structure enables route aggregation, reducing the number of entries in routing tables by summarizing multiple destinations under one prefix.

Route Aggregation

Simplifies routing by representing multiple customer addresses with a single prefix. Example: France Telecom aggregates USC’s campuses under one route from AT&T, hiding internal details and reducing routing updates. Longest Prefix Match: Ensures packets match the most specific route.

Multi-Homing

When a company connects to multiple ISPs (e.g., USC-HSC connects to AT&T and ESNet) for fault-tolerance and load balancing. Multi-homing may require breaking aggregation to optimize routing paths.

Policy Routing

Allows ASs to control routing paths based on business relationships.

• Customer-Provider Relationship: Customers pay providers to carry traffic to and from the Internet.
• Peer-to-Peer Relationship: ISPs exchange traffic between their customers without payment if the traffic is roughly balanced.

BGP (Border Gateway Protocol)

A path-vector protocol that finds paths on an inter-AS graph. Nodes represent ASs, and links represent inter-AS connections. Each AS advertises path-vectors to neighbors, containing the IP prefix (destination) and the AS path.

Selecting Loop-Free Paths

AS path lists prevent loops—routers discard routes containing their own AS number. Example: If AS A receives a route from AS C that contains its own AS number, it rejects the route.

Selecting Best Paths

ASs may receive multiple routes to a destination. Policy-based selection: ASs prioritize routes from customers over those from peers or providers. Example: If AS A receives routes to D from customer C and peer B, it selects C’s route due to customer preference.

Selective Advertising

ASs selectively advertise routes to control traffic. Example: AS C may use a route through A but not advertise it to peer B to avoid transiting traffic between peers.

Route Aggregation with BGP

ASs aggregate customer routes to reduce table size and improve scalability. Example: AS C aggregates routes from B and D into a single prefix before advertising to provider A.

BGP vs. Distance-Vector Protocols

• Distance-vector: Uses a vector of <destination, distance> pairs.
• BGP: Uses vectors of <IP prefix, AS path> pairs.
• Loop prevention: BGP discards routes containing the AS’s own number.
• Policy control: BGP selects and advertises paths based on policy rather than shortest paths.

BGP: Border Gateway Protocol

Border Gateway Protocol (BGP) is a routing protocol that manages how packets are routed between different Autonomous Systems (ASes) on the Internet. It is implemented as software and runs on border routers, which are AS routers that connect to at least one router in another AS. All other AS routers are internal. Border routers communicate with routers in other ASes via external BGP (e-BGP) sessions, which are TCP connections for reliability. These sessions exchange routes, referred to as external routes, between ASes. Within an AS, internal BGP (i-BGP) sessions allow border routers to share external routes.

BGP Route Propagation

BGP propagates routes through ASes by communicating with neighboring AS border routers via e-BGP. The receiving AS then distributes these external routes to its own routers using i-BGP. For example, a border router in AS 2 may receive a route from AS 3 and propagate it to other routers within AS 2. When forwarding to another AS, the local AS number is added to the AS Path for tracking.

BGP Policy-Based Route Selection

An AS may receive multiple routes to the same destination (prefix). Each border router applies policy-based route selection to determine the best route based on administrative preferences rather than purely technical metrics. For example, if a router in AS 1 receives routes to a prefix from AS 2 and AS 3, it can select the route based on its internal policy, which could prioritize shorter AS paths or lower costs.

The Role of Intra-Domain Routing

BGP relies on intra-domain routing protocols, such as OSPF, to determine how packets should be forwarded within an AS. For an external destination, a border router finds the best internal route to the egress border router using shortest-path metrics from intra-domain routing. This ensures packets reach the appropriate border router efficiently.

BGP Sessions and Message Types

BGP uses TCP for reliable communication and exchanges four types of messages:

• Open (establishes a session)
• Update (announces new or changed routes)
• Keep-alive (checks session viability)
• Notification (reports errors)

Update messages can withdraw routes that are no longer valid or announce new routes with attributes such as AS Path, LocalPref, NextHop, and Multi-Exit Discriminator (MED).

Attributes of BGP Routes

The AS Path lists the ASes traversed by a route in reverse order, enabling loop prevention by discarding routes that include the current AS number. LocalPref is a 32-bit number used within an AS to rank route preferences (higher is better). MED indicates preferred exit points between ASes; lower values are preferred. For example, if a customer connects to a provider at two locations, it can assign a lower MED to the preferred link, enabling efficient routing. The NextHop attribute specifies the IP address of the next-hop router for a route. For e-BGP sessions, this is typically the IP address of the neighbor router. For i-BGP sessions, the NextHop remains unchanged, and intra-domain routing must resolve how to reach this address. Ensuring the NextHop is reachable within the AS is critical for successful packet forwarding.

Hot-Potato and Cold-Potato Routing

In hot-potato routing, traffic is handed off to the next AS as soon as possible, minimizing the sending AS’s burden. Conversely, in cold-potato routing, traffic is carried further within the sending AS to optimize delivery. Adjusting MED values allows providers to influence these behaviors.

Route Processing in BGP

Border routers process updates by applying import policies, selecting the best route using a series of tie-breaking rules, and applying export policies before forwarding routes. Import policies often prefer routes from customers over peers or providers by assigning higher LocalPref values.

Common Tie-Break Rules

If multiple routes are equally preferred, BGP uses a sequence of tie-breaking rules: first, select the route with the highest LocalPref; second, the shortest AS Path; third, the lowest MED; and finally, the route with the nearest exit point, as determined by intra-domain routing.

Challenges in BGP

BGP has been in use for nearly 30 years but faces several challenges. Misconfigurations can disrupt routing, such as when a customer fails to export a route to its provider. Route hijacking occurs when an AS falsely announces another AS’s prefix, leading to traffic blackholing. Solutions include route filtering and authentication. Delayed convergence is another issue, as BGP can take minutes or even hours to stabilize after changes. With standard policies, BGP always converges, but with arbitrary policies, convergence is not guaranteed.

SDN: Software-Defined Networking

Software-Defined Networking (SDN) separates the control plane and data plane to provide centralized network control and enable rapid feature evolution. The data plane forwards packets based on local forwarding state, handling tasks like destination-based forwarding. The control plane computes forwarding states using global network state, supporting least-cost paths for intra-AS routing and policy-compliant paths for inter-AS routing. Traditional network upgrades require designing new protocols, deploying them on routers, and waiting for vendor support, which can take years. SDN eliminates these delays by introducing high-level abstractions and generalized router forwarding hardware.

Traffic Engineering with SDN

SDN simplifies traffic engineering by allowing the network to split traffic across multiple paths or route traffic types differently, even when they share the same destination. For example, SDN can split traffic between paths u→v→w→z and u→x→y→z, ensuring that link capacities are not exceeded and congestion is avoided.

Components of SDN

SDN consists of three key components:

1. Apps: Operate on global network state to determine paths or switch actions. Apps are written to introduce new features without modifying network hardware.
2. Centralized Controller: Acts as a network operating system, providing abstractions to apps and updating forwarding tables at switches based on app instructions.
3. Switches: Primarily hardware-based but include a software control agent to communicate with the controller.

The SDN Controller

The controller serves as the interface between applications and switches. It manages network state and communicates with switches using two-way protocols. Applications interact with the controller via a RESTful API to retrieve device state (e.g., port status, forwarding tables) or update configurations. Apps never directly communicate with switches.

State Management

The controller gathers information about the network by querying switches for port statuses, table entries, and traffic statistics. When an app updates state, the controller ensures that the necessary changes are communicated to the switches. This is analogous to how an operating system updates a disk when a program writes to a file.

OpenFlow Protocol

OpenFlow is the standard protocol for communication between SDN controllers and switches. It supports two types of communication:

• Controller-to-switch (e.g., querying features, setting configurations, adding/removing table entries)
• Switch-to-controller (e.g., sending packets to the controller, updating port status, or notifying about deleted entries)

OpenFlow enables generalized forwarding by allowing switches to match on any packet header field and perform specified actions such as forwarding, dropping, or modifying packets.

Match-Action Framework

Each switch maintains a match-action table. Incoming packets are matched to flow specifications based on header fields, and the corresponding action (e.g., forward, drop, modify) is performed. Flow specifications can include wildcards to match groups of packets with similar properties. For example, a specification like src=1.2.*.*, dest=3.4.*.* matches packets whose source IP starts with 1.2 and destination IP starts with 3.4.

Controller Reliability and Scalability

SDN ensures reliability by running backup controllers that take over in case of a primary controller failure. For large networks, the controller’s workload is partitioned, with each partition managed by a separate controller that communicates with others as needed.

Modern SDN Deployments

SDN is widely deployed in data centers at companies like Google, Facebook, and Microsoft and in wide-area networks (WANs) at Google and Microsoft. Modern SDN switches now support multiple match-action tables, which are reconfigurable and allow the addition of new actions, enabling faster feature evolution.

The Data Link Layer

The data link layer operates at each hop on the Internet, transferring packets between adjacent nodes or within a local area network (LAN). It interacts with diverse transmission media, including wireless (radio, microwave) and wired (copper, fiber), which connect adjacent devices. The unit of transmission is called a frame, which encapsulates a packet from the network layer.

Functions of the Data Link Layer

The key functions of the link layer include:

• Framing, which encapsulates network layer data;
• Link access, which determines when to transmit frames;
• Reliable delivery, which reduces packet drops on error-prone links;
• Error detection and correction, which ensures frame integrity during transmission.

Different link layer protocols implement these functions based on the transmission medium’s properties. For example, reliability mechanisms are often unnecessary for fiber optic links due to their low error rates.

Link Layer Implementation

The data link layer operates on the network interface card (NIC), a hardware device connected to the transmission medium. The NIC also implements physical layer functions. On the sender side, it encapsulates packets with a frame header and adds error detection or correction information. On the receiver side, it checks for errors, decapsulates the frame, and passes the packet to the network layer.

Error Detection and Correction

Since all transmission media have a non-zero bit error rate (BER), the link layer incorporates error detection and correction mechanisms. The sender adds k error detection/correction (EDC) bits to the frame, which are derived from the frame’s n data bits. The receiver computes its own EDC bits and compares them with the transmitted EDC. Mismatches indicate errors. Techniques include:

• Parity Code: Detects single-bit errors by ensuring an even number of 1s in the frame.
• Two-Dimensional Parity: Detects and corrects single-bit errors by arranging bits in a grid and using row/column parities.
• Cyclic Redundancy Check (CRC): A stronger error detection method used in many link layers. CRC adds r check bits, enabling detection of burst errors less than r+1 bits. The key idea is to choose r bits so that the frame <D,R> is divisible by a generator G (mod 2).

Link Access (Medium Access)

In shared media, the Medium Access Control (MAC) protocol regulates frame transmission to avoid collisions. For point-to-point links (e.g., Ethernet switches to hosts or routers connected by fiber), no sharing occurs. In broadcast links (e.g., wireless LANs, traditional Ethernet), MAC ensures orderly access.

MAC Protocols

There are three main types of MAC protocols:

1. Partitioning: Divides the channel into smaller units, such as time slots (Time-Division Multiplexing, TDM) or frequencies (Frequency-Division Multiplexing, FDM). These methods may underutilize the medium if nodes have no data to send.
2. Random Access: Nodes transmit whenever they have data, leading to possible collisions. Examples include Slotted ALOHA and Carrier-Sense Multiple Access (CSMA), where nodes sense the channel before transmitting. Collision recovery is achieved using backoff algorithms like binary exponential backoff.
3. Turn-Taking: Nodes transmit in a predefined order using a token-passing mechanism.

Ethernet

Modern Ethernet employs switched Ethernet with point-to-point links, eliminating collisions and the need for CSMA/CD. Ethernet headers include fields for synchronization (preamble), source and destination MAC addresses, higher-layer protocol type, and error detection (CRC).

Addressing in Ethernet

MAC addresses are flat 48-bit identifiers unique to each NIC. The first 24 bits identify the vendor (e.g., Dell), and the last 24 bits are adapter-specific. Unlike IP addresses, MAC addresses are not hierarchical and do not encode location information.

Routing in Extended LANs

Ethernet bridges extend LANs by connecting multiple LAN segments. While plug-and-play behavior is preserved, loops in the topology can cause broadcast storms, where packets circulate indefinitely. To prevent this, Ethernet uses the Spanning Tree Protocol (STP), which constructs a loop-free topology by selectively disabling redundant links.

Comparison with IP Routing

Ethernet forwarding tables are populated dynamically through self-learning, whereas IP forwarding tables rely on routing algorithms and hierarchical addressing. Ethernet’s plug-and-play behavior and flat addressing enable ease of use but limit scalability compared to IP.

Link Layer Protocols

The link layer provides key services for framing, addressing, routing, forwarding, and discovery, enabling communication across adjacent nodes within a local area network (LAN). Each protocol is designed to meet specific network requirements, ensuring reliability, efficiency, and scalability.

Routing in Switched Ethernet

Broadcast storms can occur if cycles exist in a network topology. When a device broadcasts a message, switches may forward the packet repeatedly due to loops, leading to congestion. To avoid this, Spanning Tree Protocol (STP) constructs a loop-free spanning tree topology. This approach maintains Ethernet’s plug-and-play behavior by ensuring a decentralized, automatic spanning tree construction process that adjusts dynamically to link or switch failures.

Spanning Tree Protocol (STP)

STP elects one switch as the root of the spanning tree. All other switches maintain paths to this root. Tie-breaking ensures consistent operation when multiple switches compete to be the root or when multiple shortest paths exist. Switches exchange messages in the form (Y,d,X), where Y is the proposed root, d is the distance to the root, and X is the sender’s ID. Initially, all switches elect themselves as the root, broadcasting (X,0,X). When a switch receives a message (Y,d,Z), it updates its root information if Y is smaller than its current root, or if d + 1 provides a shorter path. Switches periodically exchange messages to maintain the tree, restarting the election process if the root or a link fails.

Forwarding in Ethernet

Initially, switches use flooding to forward frames when no specific forwarding rules exist. Over time, switches learn from packets by observing source MAC addresses and updating their forwarding tables with entries mapping each MAC address to a port. When a packet arrives:

• If the destination MAC is in the forwarding table, the switch sends the packet to the corresponding port.
• If no entry exists, the switch floods the packet across all ports except the incoming port.

Entries in the forwarding table are soft state, meaning they expire after a timeout unless refreshed by traffic. This ensures robustness to changes or failures.

Self-Learning Example

If node A sends a packet to B, the switches initially flood the packet. Upon receiving the packet, the switches update their forwarding tables with A’s MAC address and the port from which the packet arrived. When B responds, the switches learn B’s MAC address similarly, optimizing future packet forwarding.

Discovery Protocols

Ethernet hosts must discover network information to communicate effectively. At initialization, a host knows only its own MAC address. Discovery protocols include:

1. DHCP (Dynamic Host Configuration Protocol): Assigns a host its IP address, netmask, gateway, and DNS server IPs. The process begins with a DHCP Discover broadcast, followed by DHCP Offers from servers. The host selects an offer with a DHCP Request, which is acknowledged with a DHCP ACK. DHCP leases addresses for a fixed duration, requiring renewal to maintain the assignment.
2. ARP (Address Resolution Protocol): Resolves IP addresses to MAC addresses within a LAN. If the target MAC is unknown, the host broadcasts an ARP Request containing the target IP. The matching host replies with an ARP Response, which is cached in the ARP table with a time-to-live (TTL).

ARP Table

Maintains mappings of (IP→MAC) pairs. If an entry expires due to inactivity, it is removed, requiring re-discovery. ARP supports both local communication (finding other hosts’ MAC addresses) and remote communication (resolving the next-hop router’s MAC).

Shared Concepts in ARP and DHCP

: Both protocols rely on broadcasts for discovery, which scales to LANs but not beyond. Learned information is cached to reduce re-discovery overhead, with a TTL ensuring robustness to failures. | Comparison of IP and Ethernet Forwarding: IP forwarding uses aggregated, hierarchical addressing and computes loop-free paths based on routing protocols. Ethernet uses flat, non-aggregated MAC addressing and builds a loop-free topology with STP. IP forwarding tables are computed from routing algorithms, while Ethernet forwarding tables are populated dynamically from packet observations.

v