Router Packet Forwarding Decisions - CSU359 - Shoolini University

Router Packet Forwarding Decisions

2024, September 9

0. Router

A router is a network device that connects different networks and forwards data between them. Routers operate at Layer 3 (the Network Layer) of the OSI model, meaning they use logical addressing (IP addresses) to determine the best path for forwarding packets to their destination. Routers play a crucial role in directing traffic across large-scale networks such as the internet.

0.1 Functions of a Router

The primary function of a router is to direct traffic between different networks. However, it performs several specific tasks to achieve this:

0.2 How a Router Works

When a router receives a data packet, it examines the packet’s destination IP address. Using its routing table, the router determines the best route to forward the packet. The process typically follows these steps:

0.3 Types of Routers

Routers come in various forms, depending on the scale and purpose of the network:

0.4 Routing Table

The routing table is a critical component of a router. It stores information about possible routes to different network destinations. Each entry in a routing table typically includes:

0.5 Routing Protocols

Routers use routing protocols to dynamically share and update routing information with other routers in the network. Common routing protocols include:

0.6 Importance of Routers in Networking

Routers are essential for the proper functioning of the internet and other large networks. They ensure that data can travel from its source to its destination, even when multiple paths or networks are involved. By selecting the best path based on metrics and administrative distances, routers help ensure efficient and reliable data transmission.

1. How a Router Creates a Packet, What Happens to a Packet, and How it Travels

Data transmission over a network involves packets, which are small units of data that travel through the network from the source to the destination. Routers are essential in creating, forwarding, and ensuring that these packets reach their destination efficiently. Let’s break this down into the key phases: packet creation, the packet lifecycle, and how packets travel across the network.

1.1 How a Packet is Created

When a device needs to send data over a network, the data is split into smaller units called packets. These packets consist of two key parts:

For example, in an IP packet, the header includes the destination IP address, which the router uses to make forwarding decisions. Once the packets are created, they are sent to the network layer for routing.

1.1.1 IP Packet Structure

An IP packet typically has the following structure:


+-------------------------------+
|        Header (20 bytes)       |
|  Source IP | Destination IP    |
|  TTL | Protocol | Checksum     |
+-------------------------------+
|           Payload              |
|         (Data)                 |
+-------------------------------+

The Header contains critical information for routing, while the Payload carries the actual content being transmitted.

1.2 What Happens to a Packet (The Packet Lifecycle)

Once a packet is created, it goes through a series of stages as it moves through the network:

1.2.1 Encapsulation

Before a packet is transmitted, it is encapsulated at each layer of the OSI model. The packet is placed into a frame at the Data Link Layer (Layer 2), which includes the MAC addresses of the source and destination devices. Encapsulation allows the packet to be transmitted over different types of physical media (e.g., Ethernet, Wi-Fi).


+-------------------------------+
|    Ethernet Frame (Header)     |
|  Source MAC | Destination MAC  |
+-------------------------------+
|        IP Packet (Payload)     |
|  Source IP | Destination IP    |
+-------------------------------+
1.2.2 Packet Forwarding

As the packet travels through the network, routers use the information in the IP header to decide where to forward it next. The packet is passed from router to router until it reaches its destination. Each router looks up the destination IP address in its routing table and forwards the packet to the next hop. The key process here is called Longest Prefix Match (explained in section 2).

1.2.3 Time to Live (TTL)

Each IP packet contains a TTL (Time to Live) field, which prevents packets from circulating endlessly in the network. The TTL value starts at a set number (e.g., 64) and decreases by 1 each time the packet is forwarded by a router. If the TTL reaches 0, the packet is discarded, and an error message is sent back to the source. This mechanism ensures that packets do not loop endlessly if there is a routing issue.

1.3 How a Packet Travels Through the Network

Packets travel through networks based on their destination IP address and the routing protocols in use. Let’s take an example of a packet traveling across multiple networks:

1.3.1 Step-by-Step Packet Travel
  • Step 1: Packet Creation: A device (e.g., a computer) creates a packet with the destination IP address of the remote server it wants to communicate with.
  • Step 2: First Router (Default Gateway): The packet is sent to the local router (usually the default gateway). This router checks the destination IP and forwards the packet to the next router based on the routing table.
  • Step 3: Intermediate Routers: The packet moves from router to router. Each router looks at the destination IP address and forwards the packet using the best route, determined by the routing protocol and the Longest Prefix Match.
  • Step 4: Reaching the Destination Network: Eventually, the packet reaches the router on the destination network. This router forwards the packet to the correct device (e.g., a web server).
  • Step 5: De-encapsulation: The final device receives the packet, strips off the headers, and processes the payload (data).

1.4 Path Selection and Routing Protocols

The path that a packet takes through the network is determined by the routing protocols used by the routers. Common routing protocols include RIP, OSPF, EIGRP, and BGP (explained in detail in section 4). These protocols help routers dynamically select the most efficient route based on factors such as hop count, bandwidth, and link reliability.

1.4.1 Example of Packet Travel with OSPF

In an OSPF network, routers calculate the cost of each link and use this to determine the best path for packets. If one link has a high bandwidth and another has a lower bandwidth, OSPF will prefer the higher bandwidth link (with the lower cost). This ensures that packets travel through the fastest available path.

1.5 Packet Fragmentation

When a packet travels through different networks, it might pass through links with different maximum transmission unit (MTU) sizes. If the packet is too large to be transmitted on a particular link, the router may break it into smaller fragments, which are reassembled at the destination.

For example, if a packet size exceeds 1500 bytes (the default Ethernet MTU), the packet will be fragmented into smaller pieces before being forwarded, and the destination host will reassemble these fragments.

2. Determine How a Router Makes a Forwarding Decision by Default - Longest Prefix Match

Routers are key devices in networks responsible for forwarding data packets to their destination. The primary decision a router makes is determining which route to forward a packet. This decision is made based on the destination IP address present in the packet header. By default, routers use the Longest Prefix Match algorithm to choose the most specific route in the routing table. Let's break this down conceptually.

2.1 IP Addressing and Prefix Length

An IP address consists of two parts: the network prefix and the host identifier. The prefix defines the network, and the length of this prefix is crucial when determining which route is the best match. In routing tables, each route is associated with a prefix length, also known as the subnet mask.

For example, in a network entry like 192.168.1.0/24, the prefix length is 24, meaning the first 24 bits represent the network, and the rest specify the host.

2.2 The Longest Prefix Match Algorithm

When a router receives a packet, it looks up the destination IP address in its routing table. Since multiple routes may match the destination, the router applies the Longest Prefix Match rule. This rule selects the route with the longest prefix (most specific match).

Steps involved in the algorithm:

If multiple routes match the destination, the one with the longest prefix length (largest number of matching bits) is selected.

2.2.1 Example of Longest Prefix Match

Let’s say a router has the following entries in its routing table:


192.168.1.0/24  -> Interface 1
192.168.1.128/25 -> Interface 2
192.168.1.64/26  -> Interface 3

Now, a packet arrives with the destination IP address 192.168.1.65. Here's how the router makes its decision:

  • 192.168.1.0/24: Matches the first 24 bits (prefix length 24).
  • 192.168.1.128/25: Does not match, as the first 25 bits do not match the destination IP.
  • 192.168.1.64/26: Matches the first 26 bits (prefix length 26).

Although the first route matches, the longest prefix match is 192.168.1.64/26, which provides a more specific match. Therefore, the router forwards the packet to Interface 3.

2.3 Importance of Longest Prefix Match

The Longest Prefix Match rule is crucial for efficient routing. It ensures that the router always selects the most specific route available, which improves packet forwarding accuracy and efficiency in large networks. Without this rule, packets might follow a less specific route, leading to potential inefficiencies or routing loops.

3. Administrative Distance

In networking, routers often receive routing information from multiple sources such as dynamic routing protocols (e.g., OSPF, EIGRP), static routes, or directly connected routes. When multiple routes to the same destination are learned from different sources, routers need a way to prioritize which route to use. This prioritization is done using a concept known as Administrative Distance (AD).

3.1 Definition of Administrative Distance

Administrative Distance is a value assigned to each route that represents the trustworthiness or reliability of the route source. Lower AD values indicate more trusted sources, while higher values represent less reliable sources. A router will always prefer the route with the lowest AD when there are multiple routes to the same destination.

3.1.1 Key Points
  • Lower AD is preferred: The route with the smallest AD is considered more reliable and will be chosen.
  • Default AD values: Different routing sources have default AD values assigned by vendors (e.g., Cisco). These defaults can be changed by administrators to influence route selection.
  • Static routes: Often have lower AD values, meaning they are preferred over dynamically learned routes unless otherwise configured.

3.2 Default Administrative Distance Values

Each routing protocol or source of a route has a default administrative distance. Here are some common default values:

3.2.1 Example of Administrative Distance in Action

Consider a scenario where a router learns the same destination route 10.10.10.0/24 from two different sources:

  • OSPF advertises the route with an AD of 110.
  • EIGRP advertises the route with an AD of 90.

Since EIGRP has a lower AD, the router will choose the route learned via EIGRP, as it is considered more reliable than the OSPF route.

3.3 Administrative Distance Customization

In some cases, network administrators may need to modify the default administrative distances to influence route selection. For example, if you want a static route to be less preferred than a dynamically learned route, you can increase its AD value.

Steps to customize AD in Cisco routers:


Router(config)# ip route 10.10.10.0 255.255.255.0 192.168.1.1 150

In this case, the AD for the static route to 10.10.10.0/24 is set to 150, making it less preferable than EIGRP or OSPF (default AD of 90 and 110, respectively).

3.4 Impact of Administrative Distance

Understanding and properly configuring administrative distance is crucial for network stability. It ensures that routers select the best path based on the most trusted source, avoiding suboptimal routing or routing loops. Misconfiguring AD values can lead to inefficient routing or the use of unreliable paths.

4. Routing Protocol Metric

In routing, when a router has multiple paths to a destination, it must decide which path to take. While Administrative Distance (AD) determines the trustworthiness of different routing protocols, the Routing Protocol Metric is used to determine the best path within a single routing protocol. The metric is a quantitative value assigned to each route by the routing protocol, representing the cost or efficiency of that route. The lower the metric, the more preferred the route.

4.1 Definition of Metric

A metric is a numerical value that indicates the quality of a path between two routers. Different routing protocols calculate the metric in different ways, based on various factors such as hop count, bandwidth, delay, and reliability.

For example, in some protocols like RIP, the metric is based solely on the number of hops (hop count), while in others like EIGRP, the metric considers multiple factors such as bandwidth and delay.

4.2 Types of Routing Protocol Metrics

Each routing protocol has its own method for calculating the metric:

4.3 Metric Calculation Examples

4.3.1 RIP (Hop Count Example)

RIP calculates the metric as the number of hops between the source and destination routers. For example:


Router A -> Router B -> Router C -> Router D

If a packet travels from Router A to Router D, the hop count is 3, and this will be the metric for the route. The fewer the hops, the more preferred the route.

4.3.2 OSPF (Cost Example)

OSPF uses the bandwidth of the link to calculate the metric. The formula is:

$$Cost = \frac{Reference \, Bandwidth}{Link \, Bandwidth}$$

If the reference bandwidth is set to 100 Mbps and the link bandwidth is 10 Mbps, the cost would be:


Cost = 100 Mbps / 10 Mbps = 10

Routes with lower costs are preferred.

4.3.3 EIGRP (Composite Metric Example)

EIGRP uses the following formula for calculating its metric:

$$Metric = (K1 \cdot Bandwidth) + (K3 \cdot Delay)$$

Where K1 and K3 are weighting factors (usually set to 1), and bandwidth and delay are measured in specific units. EIGRP gives preference to routes with lower composite metrics, making it more flexible than single-factor metrics like RIP’s hop count.

4.4 Metric Comparison and Route Selection

When a routing protocol finds multiple routes to a destination, it compares their metrics and selects the route with the lowest metric. If two routes have the same metric, the protocol may use load balancing to split traffic across multiple routes.

For example, if OSPF has two routes to a destination with costs of 10 and 15, it will choose the route with a cost of 10, as it is considered more efficient.

4.5 Impact of Routing Metrics

Routing metrics directly influence how efficiently data moves across the network. Misconfigured metrics can lead to suboptimal routing, such as traffic taking longer or less reliable paths. Properly understanding and configuring metrics ensures that data follows the most efficient route based on the network’s current state.