Internet Routing Protocols: A Beginner to Advanced Guide

The internet as we know it today is a vast, interconnected network of devices. This interconnectedness is made possible by routing protocols, which are essential to directing data packets from one point to another across networks. In this blog, we’ll take a journey from understanding the basics of routing to exploring advanced concepts, covering various routing protocols used on the internet today.

Introduction to Internet Routing

Routing is the process of selecting paths in a network along which to send data packets. Think of it like a GPS navigation system for data: it determines the best route for information to travel from its source to its destination. The core function of a router is to direct this traffic efficiently, ensuring that data reaches its intended endpoint in the fastest and most reliable way possible. Without effective routing, the internet would become a chaotic mess of lost or delayed information.

Basics of Routing

A router is a networking device that forwards data packets between computer networks. It plays a crucial role in determining the path packets should take based on the information in their headers and routing tables. There are two main types of routing:

1. Static Routing: In static routing, routes are manually configured by network administrators. This approach is simple and does not require much overhead, but it can be inflexible as it does not adapt to changes in the network topology.

2. Dynamic Routing: Dynamic routing involves the use of protocols that automatically adjust routing paths based on the current network conditions. Routers use these protocols to communicate with each other, exchange information, and determine the best paths for data transmission.

At the core of routing are several fundamental concepts that beginners need to understand:

1. Packet: A packet is a small unit of data that is transmitted over a network. When data (such as a file or a message) is sent from one device to another, it is broken down into smaller packets. Each packet contains a portion of the data along with header information, which includes the source and destination IP addresses. Routers use this information to determine how to forward the packet towards its destination.

2. IP Address: An Internet Protocol (IP) address is a unique numerical label assigned to every device connected to a network. It serves as the device's identifier and helps in locating and communicating with other devices. There are two main versions of IP addresses:

   • IPv4: The most common version, consisting of four sets of numbers (e.g., 192.168.1.1), each ranging from 0 to 255.

   • IPv6: A newer version designed to overcome the limitations of IPv4, offering a larger address space (e.g., 2001:0db8:85a3:0000:0000:8a2e:0370:7334).

Fig 1.0 IPv4 vs IPv6

3. Subnet: A subnet (short for "subnetwork") is a logical subdivision of an IP network. Subnetting allows large networks to be divided into smaller, more manageable segments. Each subnet operates as a separate network, reducing congestion and improving security. For example, a company might use subnetting to separate its internal network into segments for different departments, such as HR, IT, and Sales.

4. Gateway: A gateway is a network node that acts as an access point to another network, often serving as the router for devices within a local network. It directs outgoing traffic to external networks (like the internet) and manages incoming traffic from other networks. In home networks, the gateway is typically the router provided by the ISP.

Classification of Routing Protocols

Routing protocols can be broadly classified into two categories:

1. Interior Gateway Protocols (IGP): Used within a single autonomous system (AS). Examples include RIP, OSPF, and EIGRP.

2. Exterior Gateway Protocols (EGP): Used to route data between different autonomous systems. The primary EGP used today is BGP.

Routing protocols can also be divided based on how they determine the best path:

• Distance Vector Protocols: These use the distance (hop count) to determine the best path to a destination.

• Link State Protocols: These build a complete map of the network and use algorithms like Dijkstra’s to determine the shortest path.

Fig 1.1 Distance Vector vs Link State

Common Routing Protocols Explained

1. RIP (Routing Information Protocol)

Routing Information Protocol (RIP) is one of the earliest and simplest distance-vector routing protocols. It was designed to route data within smaller, local area networks (LANs).

Working Mechanism:

• Distance Vector Algorithm: RIP uses the Bellman-Ford algorithm for path selection. It sends its entire routing table to neighboring routers every 30 seconds.

• Hop Count: The metric used by RIP is the hop count, which is the number of routers a packet must pass through to reach its destination. The maximum hop count allowed is 15, making it unsuitable for large networks.

• Slow Convergence: Due to its periodic updates (every 30 seconds), RIP has a slower convergence time, which can lead to temporary routing loops or outdated routes in rapidly changing network environments.

Fig 1.2 Routing Information Protocol (RIP)

Frame Format: RIP messages are encapsulated in UDP packets using port 520. The key components of the RIP frame format include:

• Command (1 byte): Indicates whether the message is a request (1) or a response (2).

• Version (1 byte): Specifies the version of RIP (either 1 or 2).

• Address Family Identifier (2 bytes): Specifies the type of address being used (IPv4 or IPv6).

• IP Address (4 bytes): The destination IP address.

• Metric (4 bytes): The hop count metric value.

Frame Format Image:

Fig 1.3 RIP Frame Format

2.OSPF (Open Shortest Path First)

Open Shortest Path First (OSPF) is a widely adopted link-state routing protocol, known for its efficiency in large enterprise networks.

Working Mechanism:

• Link-State Algorithm: OSPF uses the Dijkstra algorithm to calculate the shortest path. Each router creates a link-state advertisement (LSA) to describe its directly connected networks, which are shared with all other routers in the area.

• Area Hierarchy: OSPF divides networks into areas to manage routing efficiently. The backbone area (Area 0) interconnects other areas, reducing the routing overhead.

• Fast Convergence: OSPF has a fast convergence time as it only updates routers when there is a change in the network topology, unlike RIP's periodic updates.

Fig 1.4 Open Shortest Path First

Frame Format: OSPF packets are encapsulated directly in IP packets with protocol number 89. The key fields in the OSPF header include:

• Version (1 byte): Indicates the OSPF version being used.

• Type (1 byte): Specifies the type of OSPF packet (Hello, Database Description, LSR, LSU, or LSA).

• Router ID (4 bytes): Unique identifier for the originating router.

• Area ID (4 bytes): Identifies the OSPF area the packet belongs to.

• Checksum (2 bytes): Ensures data integrity.

Frame Format Image:

Fig 1.5 OSPF Packet Format

3.EIGRP (Enhanced Interior Gateway Routing Protocol)

Enhanced Interior Gateway Routing Protocol (EIGRP) is a Cisco proprietary hybrid protocol, combining features of both distance-vector and link-state protocols.

Working Mechanism:

• DUAL Algorithm: EIGRP uses the Diffusing Update Algorithm (DUAL) to ensure loop-free and fast convergence. It allows EIGRP to quickly adapt to network changes.

• Composite Metric: EIGRP uses multiple metrics such as bandwidth, delay, reliability, and load to determine the best route, unlike RIP's single hop count metric.

• Partial Updates: Unlike RIP, which sends the entire routing table, EIGRP only sends updates when a change occurs, and only the affected routes are updated.

Fig 1.6 Enhanced Interior Gateway Routing Protocol

Frame Format: EIGRP packets are encapsulated in IP with protocol number 88. Key components include:

• Opcode (1 byte): Identifies the type of EIGRP packet (e.g., Hello, Update, Query, Reply, ACK).

• AS Number (2 bytes): Specifies the Autonomous System number for EIGRP.

• Sequence Number (4 bytes): Ensures the ordering of packets.

• Checksum (2 bytes): Validates packet integrity.

Frame Format Image:

Fig 1.7 EIGRP Packet Format

4. BGP (Border Gateway Protocol)

Border Gateway Protocol (BGP) is the protocol that facilitates data routing across the internet, managing how packets are forwarded between autonomous systems (AS).

Working Mechanism:

• Path Vector Protocol: BGP uses a path vector mechanism where each BGP router maintains a table of paths to different network destinations. It considers multiple factors, such as AS path length, to select the best route.

• Exterior Gateway Protocol: BGP is classified as an exterior gateway protocol (EGP) because it exchanges routing information between different autonomous systems.

• Policy-Based Routing: BGP allows network administrators to define routing policies based on factors like route preference, filtering, and load balancing.

Fig 1.8 Border Gateway Protocol

Frame Format: BGP packets are encapsulated in TCP, using port 179. Key fields include:

• Marker (16 bytes): For message authentication, set to all 1s if no authentication is used.

• Length (2 bytes): Indicates the total length of the BGP message.

• Type (1 byte): Specifies the message type (Open, Update, Notification, or Keepalive).

• BGP Identifier (4 bytes): The unique identifier of the BGP router.

Frame Format Image:

Fig 1.9 BGP Packet Format

Fig 1.10 Graph for comparison of Routing Protocol Metrics

How Routing Protocols Exchange Information

Routing protocols rely on routing tables to keep track of available paths. These tables are built and updated based on information exchanged between routers. The process of exchanging this information and updating routes is known as convergence. When a change occurs in the network, routers share updates, and the network converges once all routers have consistent routing information.

Routing protocols use various metrics to select the best path:

• Hop Count (RIP)

• Cost (OSPF)

• Bandwidth and Delay (EIGRP)

• AS Path (BGP)

The faster a network converges, the quicker it can adapt to changes, reducing packet loss and latency.

Comparing Routing Protocols

Here is a quick comparison of the four main protocols discussed:

Protocol	Type	Metric	Convergence Speed	Use Case
RIP	Distance Vector	Hop Count	Slow	Small networks
OSPF	Link State	Cost (Bandwidth)	Fast	Large enterprise
EIGRP	Hybrid	Bandwidth, Delay	Fast	Cisco-based networks
BGP	Path Vector	AS Path	Moderate	Internet backbone

Challenges in Routing

Routing Loops:

A routing loop is a situation in which a packet circulates indefinitely between routers without reaching its destination. These loops typically arise when a router is unable to find a valid route to a destination and instead forwards the packet back to a previous router. This is a major concern in both distance-vector and link-state routing protocols, though the cause and the solution for routing loops can vary depending on the protocol in use.

In distance-vector protocols like RIP, routing loops can happen when a router learns about a route with a bad metric or an incorrect next hop, but it doesn't immediately realize the path is unreachable. This leads to a circular route where the packet continues to travel between routers in the loop. For example, if Router A believes it can reach Router B through Router C, but Router C cannot reach Router B, the packet might bounce back and forth between Routers A and C.

One of the major strategies to prevent routing loops in such protocols is the use of split horizon and route poisoning. Split horizon prevents a router from advertising a route back to the router from which it was learned, which helps avoid the loop. Route poisoning marks a route as unreachable (often by setting its metric to infinity) if a router detects that the route is no longer valid.

Link-state protocols like OSPF are less prone to routing loops because they rely on a complete map of the network and calculate the best path based on a global view. However, network design and incorrect configurations can still lead to problems. OSPF's LSA flooding method ensures that routers update their knowledge about the network in a consistent manner, but design flaws can sometimes lead to temporary inconsistencies.

BGP (Border Gateway Protocol), which operates at a larger scale across the internet, is also susceptible to routing loops, though they are less frequent. In BGP, a loop prevention mechanism known as the AS Path is used, which keeps track of the Autonomous Systems (AS) the route has passed through. If a BGP route comes back to the same AS, the loop is detected and discarded.

Fig 1.11 Routing Loops

Route Flapping:

Route flapping occurs when a network route becomes unstable, oscillating between available and unavailable states in a short period. This is often seen when a router continuously advertises a route as reachable and then unreachable, leading to frequent updates in the routing table. Route flapping can have severe effects on network performance, as it forces routers to continually recalculate their routing tables, consuming valuable resources like CPU and bandwidth.

Route flapping is typically caused by physical layer issues such as network instability, misconfigurations, or failures in network links. For example, if a link between two routers goes up and down repeatedly due to hardware failure or an incorrect configuration, the routers will continuously advertise the route as being available and then unavailable.

To mitigate route flapping, protocols such as BGP use route dampening, which penalizes routes that flap frequently and suppresses their advertisements for a period of time. This prevents the network from being flooded with excessive updates and helps maintain network stability. For instance, BGP assigns a penalty to a route each time it flaps. If the penalty exceeds a certain threshold, the route is suppressed for a specific period, during which no updates will be sent.

Route flapping is particularly disruptive in larger networks or on the internet, where rapid recalculation of routing tables can lead to significant packet loss and delays. The use of route dampening, along with proper network monitoring and diagnostics, can help reduce the impact of this issue.

Fig 1.12 Route Flapping

Security Concerns:

With the rise of internet-scale routing, security has become a critical issue in routing protocols. One of the most concerning security threats in the realm of routing is BGP hijacking.

BGP Hijacking occurs when a malicious actor manipulates the Border Gateway Protocol (BGP) to advertise IP prefixes that they do not own. Essentially, a BGP hijacker can reroute traffic through their own network, allowing them to intercept, modify, or drop the traffic. This can have serious implications for confidentiality and availability, as it allows attackers to conduct Man-in-the-Middle (MitM) attacks or launch Denial-of-Service (DoS) attacks.

BGP itself has limited security mechanisms, and it relies heavily on trust between BGP peers. This trust-based system makes BGP vulnerable to attacks. The lack of validation in BGP updates allows attackers to inject false routing information. For example, an attacker might advertise an IP prefix that belongs to a legitimate service, and all traffic intended for that service will be directed to the attacker’s network instead.

To mitigate BGP hijacking, BGP prefix filtering, BGP monitoring, and cryptographic authentication mechanisms like BGP-SEC and RPKI (Resource Public Key Infrastructure) have been proposed. BGP-SEC provides a way to authenticate BGP updates, while RPKI uses digital certificates to verify the legitimacy of IP address ownership and BGP announcements. These techniques aim to reduce the likelihood of malicious BGP hijacking and ensure that traffic flows according to legitimate routing policies.

Future Trends in Internet Routing

The future of internet routing is shaped by evolving technologies and growing demands for more efficient and secure network management. Some of the key trends that will likely shape the future of internet routing include:

1. Software-Defined Networking (SDN): SDN separates the control plane and data plane of networking, enabling more flexible, automated, and programmable network management. Routing decisions will become more dynamic, based on software controllers, which could lead to faster convergence, more efficient routing, and better adaptability to network changes.

2. IPv6 Adoption: As the internet grows and IPv4 addresses become exhausted, IPv6 adoption will continue to rise. IPv6 offers a much larger address space and better routing efficiency. However, its widespread implementation will require modifications to existing routing protocols and infrastructure.

3. Segment Routing: Segment routing is a new approach to forwarding packets based on pre-defined segments of the network. It offers more flexibility, scalability, and simplified management compared to traditional MPLS (Multiprotocol Label Switching). Segment routing enables improved traffic engineering and efficient network path optimization.

4. Improved BGP Security: Given the increasing frequency of BGP attacks, the implementation of more robust security mechanisms will become a priority. Protocols like RPKI and BGP-SEC are expected to be deployed more widely to secure the global routing system and mitigate the risk of BGP hijacking.

5. AI and Machine Learning in Routing: The use of Artificial Intelligence (AI) and Machine Learning (ML) in routing is gaining traction. These technologies can help routers automatically learn from network traffic patterns, predict congestion, and optimize routes in real-time, further improving network efficiency.

6. Quantum Networking: As quantum computing advances, there may be new opportunities for quantum networking protocols. While still in its infancy, quantum networks could revolutionize routing by enabling secure and ultra-fast communication based on quantum principles such as entanglement.

The future of internet routing will undoubtedly focus on increasing automation, security, and efficiency as global networks continue to expand and grow more complex.

References

1. Kurose, J., & Ross, K. (2020). Computer Networking: A Top-Down Approach. Pearson.

2. Tanenbaum, A. S., & Wetherall, D. (2010). Computer Networks. Prentice Hall.

3. "RFC 2328 - OSPF Version 2." Internet Engineering Task Force (IETF). https://datatracker.ietf.org/doc/html/rfc2328

4. "RFC 4271 - Border Gateway Protocol 4 (BGP-4)." Internet Engineering Task Force (IETF). https://datatracker.ietf.org/doc/html/rfc4271

5. “Routing Protocols in Computer Networks.” Javatpoint. https://www.javatpoint.com/routing-protocols-in-computer-networks