[Computer Networking] 11. Network Layer Overview: Forwarding and Routing

Network Layer Overview: Forwarding and Routing

The Network Layer is responsible for delivering packets from the sending host to the receiving host. While the transport layer provides end-to-end logical communication, the network layer is the core layer that determines the actual path between hosts and moves packets along that path.

In this post, we distinguish between the two core functions of the network layer: Forwarding and Routing, and examine the network service model, the differences between virtual circuit and datagram networks, and the internal structure of routers.

1. Distinguishing Forwarding and Routing

1.1 Forwarding

Forwarding is a local action that moves a packet arriving at a router's input port to the appropriate output port. It is performed at the hardware level in nanoseconds and is determined by consulting the forwarding table.

1.2 Routing

Routing is a network-wide action that determines the entire path a packet takes from source to destination. Routing algorithms determine the contents of the forwarding table.

1.3 Understanding Through Analogy

An analogy with a car trip works as follows:

• Routing: Planning the entire route from Seoul to Busan using a navigation system
• Forwarding: Turning left or right at each intersection according to the navigation instructions

Relationship Between Forwarding and Routing
=============================================

[Routing Algorithm] -----> [Forwarding Table]
  (Path Decision)           (Table Lookup)
                               |
                               v
Packet Arrives --> [Input Port] --> [Switching] --> [Output Port] --> Packet Sent
                 (Forwarding: Local Action)

2. Network Service Models

The network layer can offer two main service models to the transport layer.

2.1 Connection-Oriented Service

A path is established before data transfer, and all packets follow the same path. ATM and Frame Relay networks are representative examples.

2.2 Connectionless Service

Each packet is routed independently. The Internet's IP protocol uses this approach.

Service Model Comparison
=========================

Item               | Connection-Oriented (VC) | Connectionless (Datagram)
-------------------+--------------------------+---------------------------
Connection Setup   | Required                 | Not required
Packet Path        | Same path                | Each independent
State Maintenance  | State stored in routers  | No state
Bandwidth Guarantee| Possible                 | Not possible
Representative Tech| ATM, MPLS               | IP (Internet)

3. Virtual Circuit Network

3.1 Concept of Virtual Circuits

A Virtual Circuit (VC) network operates similarly to a telephone network, establishing a path before data transfer. While it does not physically allocate a dedicated circuit, packets logically follow a fixed path.

3.2 Three Phases of VC

1. Setup: Assigns a VC number to all routers along the path and adds entries to forwarding tables.
2. Data Transfer: Packets include the VC number in their header and travel along the established path.
3. Teardown: Removes VC-related state from all routers along the path.

Virtual Circuit Operation Example
===================================

Host A --> [R1] --> [R2] --> [R3] --> Host B

VC Number Translation Table (Router R1):
+------------------+----------+-------------------+----------+
| Input Interface  | Input VC | Output Interface  | Output VC|
+------------------+----------+-------------------+----------+
|        1         |    12    |        3          |    22    |
|        2         |    63    |        4          |    18    |
+------------------+----------+-------------------+----------+

Packet arrives at interface 1 with VC=12
  --> Translated to VC=22 and forwarded via interface 3

3.3 Signaling Protocols

Signaling protocols are used for VC setup and teardown. Q.2931 is used in ATM and LMI protocol in Frame Relay.

4. Datagram Network

4.1 Characteristics of the Datagram Approach

In a datagram network, there is no connection setup phase. Each packet includes the destination address in its header, and routers make independent forwarding decisions based on that address.

4.2 Longest Prefix Matching

The router's forwarding table matches based on the prefix of the destination address. When multiple entries match, the entry with the longest prefix is selected.

Longest Prefix Matching Example
=================================

Forwarding Table:
+-------------------------------+-----------+
| Destination Address Prefix    | Output Link|
+-------------------------------+-----------+
| 11001000 00010111 00010       | Link 0    |
| 11001000 00010111 00011000    | Link 1    |
| 11001000 00010111 00011       | Link 2    |
| Otherwise                     | Link 3    |
+-------------------------------+-----------+

Destination address: 11001000 00010111 00011000 10101010
  --> Link 0: 21-bit prefix match
  --> Link 1: 24-bit prefix match  <-- Selected (longest match)
  --> Link 2: 21-bit prefix match

5. Router Internal Structure

A router consists of four major components.

Router Internal Structure
==========================

        [Routing Processor]
         (Control Plane)
              |
              | Forwarding table distribution
              v
[Input Port] --> [Switching Fabric] --> [Output Port]
[Input Port] --> [Switching Fabric] --> [Output Port]
[Input Port] --> [Switching Fabric] --> [Output Port]
              (Data Plane)

5.1 Input Port

The input port performs three functions:

1. Physical Layer Function: Converts incoming physical signals to bits
2. Link Layer Function: Processes frame headers and performs decapsulation
3. Forwarding Function: Consults the forwarding table to determine the output port

Input Port Processing
======================

Physical Signal --> [Line Termination] --> [Link Layer Processing] --> [Forwarding Table Lookup]
                                                                             |
                                                                             v
                                                                      [To Switching Fabric]

5.2 Switching Fabric

The switching fabric physically moves packets from input ports to output ports. There are three approaches:

Memory-based Switching: Used in early routers, the CPU copies packets to memory and then forwards them to the output port. Speed is limited by memory bandwidth.

Bus-based Switching: Packets move directly from input port to output port through a shared bus. Speed is limited by bus bandwidth.

Crossbar Switching: A grid structure connecting N inputs to N outputs. It allows simultaneous transmission between different port pairs, making it the fastest.

Three Types of Switching Fabric
=================================

1. Memory-based         2. Bus-based           3. Crossbar

[Input] -> [Memory]     [Input] --+             [Input]-+-+-+
            |           [Input] --+--> [Bus]    [Input]-+-+-+
            v           [Input] --+             [Input]-+-+-+
         [Output]       [Output] <-+                    | | |
                        [Output] <-+            [Output][Output][Output]
                        [Output] <-+

5.3 Output Port

The output port stores packets received from the switching fabric in a buffer, performs link layer and physical layer processing, and transmits them on the output link.

5.4 Queuing and Packet Loss

Queuing can occur at both input and output ports.

Output Port Queuing: When packets from multiple input ports arrive at the same output port simultaneously, they must wait in the buffer. Packets are dropped when the buffer is full.

Input Port Queuing: Occurs when the switching fabric cannot process all input packets simultaneously. This can cause the HOL (Head-of-Line) blocking problem.

HOL Blocking Problem
=====================

Input Port 1 Queue: [Packet A -> Output 1] [Packet B -> Output 2]
Input Port 2 Queue: [Packet C -> Output 1] [Packet D -> Output 3]

Both Packet A and C are destined for Output Port 1
  --> Packet C must wait
  --> Packet D has Output Port 3 available but
      is behind Packet C, so it also waits (HOL Blocking)

6. Control Plane and Data Plane

6.1 Traditional Approach

Traditionally, routing algorithms run independently on each router, exchanging information with neighboring routers to build forwarding tables.

6.2 SDN (Software-Defined Networking)

In SDN, a remote controller computes forwarding tables and distributes them to each router. Routers only perform forwarding, while routing decisions are made centrally.

Traditional Approach vs SDN
=============================

Traditional:                    SDN:

[R1]---[R2]---[R3]             [Remote Controller]
 |      |      |                /     |     \
Each router independently      [R1]  [R2]  [R3]
runs routing algorithms        Controller centrally
                               computes/distributes
                               forwarding tables

7. Buffer Sizing

Router buffer size significantly impacts network performance.

According to the traditional rule of thumb, when the link capacity is C and the average round-trip time is RTT, the buffer size is set as follows:

Buffer Size = RTT x C

Example:
  RTT = 250ms, C = 10 Gbps
  Buffer Size = 0.25 x 10 x 10^9 = 2.5 Gbit

Revised formula from recent research:
  Buffer Size = (RTT x C) / sqrt(N)
  N = number of TCP flows

This revised formula shows that a large number of TCP flows provide statistical multiplexing effects, allowing smaller buffers to suffice.

8. Packet Scheduling

When multiple packets are waiting at an output port, a scheduling method is needed to decide which packet to transmit first.

8.1 FIFO (First-In First-Out)

The simplest approach, transmitting packets in arrival order.

8.2 Priority Queuing

Packets are classified into priority classes, and higher-priority packets are transmitted first.

8.3 Round Robin and WFQ

Round Robin: Cycles through each class, transmitting one packet at a time.

WFQ (Weighted Fair Queuing): A weighted version of round robin that assigns weights to each class to fairly distribute bandwidth.

Packet Scheduling Comparison
==============================

FIFO:       [1][2][3][4] --> Transmitted in order

Priority:   High: [A][C]  --> A, C transmitted first
            Low:  [B][D]  --> Then B, D

WFQ:        Class 1 (w=2): [A][C]  --> 2x bandwidth
            Class 2 (w=1): [B]     --> 1x bandwidth

9. Summary

A summary of the key concepts of the network layer:

In the next post, we will examine the datagram format and addressing system of IP (Internet Protocol), the core protocol of the Internet.

References

• James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 4
• RFC 791 - Internet Protocol
• Andrew S. Tanenbaum, "Computer Networks", 5th Edition