Network Layer: Data Plane Notes

Network Layer: Data Plane

Introduction

• This lecture focuses on the data plane aspects of the network layer.

• The slides are freely available for use and modification, with attribution requested.

• The content is copyrighted by J.F Kurose and K.W. Ross.

Goals

• Understand the principles behind network layer services, focusing on the data plane.

• Service models, forwarding vs. routing, router operation, addressing, generalized forwarding, and Internet architecture.

• Instantiation and implementation in the Internet, including IP protocol, NAT (Network Address Translation), and middleboxes.

Roadmap

• Network layer overview: data plane and control plane.

• Generalized Forwarding and Software-Defined Networking (SDN).

• Router internals: input ports, switching, output ports, buffer management, and scheduling.

• IP: the Internet Protocol, including datagram format, addressing, network address translation, and IPv6.

Network-Layer Services and Protocols

• The network layer provides services to transport layer segments from sending to receiving hosts.

  • Sender: Encapsulates segments into datagrams and passes them to the link layer.

  • Receiver: Delivers segments to the transport layer protocol.

• Network layer protocols exist in every Internet device, including hosts and routers.

• Routers examine header fields in IP datagrams and move datagrams from input to output ports.

• Illustrations of network configurations are provided, showcasing the network layer's role in various environments like mobile networks, enterprise networks, national or global ISPs, and data center networks.

Key Network-Layer Functions

• Forwarding: Moving packets from a router’s input link to the appropriate output link.

  • Analogy: Getting through a single interchange during a trip.

• Routing: Determining the route taken by packets from source to destination.

  • Analogy: Planning the entire trip from source to destination.

  • Routing algorithms determine the path.

Data Plane vs. Control Plane

• Data Plane: Local, per-router function that determines how a datagram arriving on an input port is forwarded to an output port.

• Control Plane: Network-wide logic that determines how a datagram is routed among routers along the end-to-end path.

• Two control-plane approaches:

  • Traditional routing algorithms implemented in routers.

  • Software-Defined Networking (SDN) implemented in remote servers.

Per-Router Control Plane

• Individual routing algorithm components in each router interact in the control plane.

• Each router makes decisions based on the routing algorithm.

Software-Defined Networking (SDN)

• Remote controller computes and installs forwarding tables in routers.

• Centralized control for routing decisions.

Network-Layer Service Model

• Comparison of service models:

  • Internet: Best effort.

  • ATM: Constant Bit Rate, Available Bit Rate.

  • Intserv: Guaranteed (RFC 1633).

  • Diffserv: (RFC 2475).

• Quality of Service (QoS) Guarantees:

  • Varying guarantees on bandwidth, loss, order, and timing.

  • Internet offers no guarantees on successful datagram delivery, timing, order, or bandwidth.

Reflections on Best-Effort Service

• Simplicity has allowed widespread deployment and adoption of the Internet.

• Sufficient bandwidth provisioning allows real-time applications to perform adequately.

• Replicated, application-layer distributed services (datacenters, content distribution networks) improve service delivery.

• Congestion control of “elastic” services helps in maintaining network stability.

Router Architecture Overview

• High-level view of a generic router architecture:

  • Input ports, high-speed switching fabric, output ports, and routing processor.

  • Data plane operates in nanoseconds (hardware).

  • Control plane operates in milliseconds (software).

Input Port Functions

• Line termination (physical layer bit-level reception).

• Link layer protocol processing (e.g., Ethernet).

• Lookup and forwarding: using header field values to determine output port using forwarding table.

  • Decentralized switching: match plus action.

  • Goal: complete input port processing at line speed.

• Input port queuing: if datagrams arrive faster than the forwarding rate into the switch fabric.

Destination-Based Forwarding

• Forwarding based only on the destination IP address (traditional).

• Generalized forwarding: forward based on any set of header field values.

Forwarding Table Example

• Example of a forwarding table with destination address ranges and corresponding link interfaces.

• Question raised about handling ranges that don't divide up neatly.

Longest Prefix Matching

• Use the longest address prefix that matches the destination address when looking for a forwarding table entry.

• Example provided to illustrate the concept.

Ternary Content Addressable Memories (TCAMs)

• Longest prefix matching is often performed using TCAMs.

• Content addressable: retrieve address in one clock cycle regardless of table size.

Switching Fabrics

• Transfer packets from input link to the appropriate output link.

• Switching rate: rate at which packets can be transferred from inputs to outputs.

  • Measured as a multiple of the input/output line rate.

  • $N$ inputs: Switching rate $N$ times line rate desirable (rate: $NR$, ideally).

Types of Switching Fabrics

• Three major types: bus, memory, and interconnection network.

Input Port Queueing

• If the switch fabric is slower than the combined input ports, queueing may occur at input queues.

  • Queueing delay and loss due to input buffer overflow.

• Head-of-the-Line (HOL) blocking: queued datagram at the front of the queue prevents others from moving forward.

Output Port Queueing

• Buffering is required when datagrams arrive from the fabric faster than the link transmission rate.

• Drop policy: which datagrams to drop if no free buffers?

• Scheduling discipline chooses among queued datagrams for transmission.

Buffer Management

• Policies:

  • Tail drop: drop arriving packet.

  • Priority: drop/remove on priority basis.

• Marking: which packets to mark to signal congestion (ECN, RED).

Packet Scheduling

• Deciding which packet to send next on the link.

• Scheduling algorithms:

  • First Come, First Served (FCFS).

  • Priority.

  • Round Robin.

  • Weighted Fair Queueing.

First-Come-First-Served (FCFS)

• Packets are transmitted in the order of arrival to the output port.

• Also known as First-In-First-Out (FIFO).

Priority Scheduling

• Arriving traffic is classified and queued by class.

• Header fields can be used for classification.

• Send packets from the highest priority queue that has buffered packets.

• FCFS within a priority class.

Round Robin (RR) Scheduling

• Arriving traffic is classified and queued by class.

• The server cyclically scans class queues and sends one complete packet from each class in turn.

Weighted Fair Queuing (WFQ)

• Generalized Round Robin.

• Minimum bandwidth guarantee per traffic class.

• Each class $i$ has weight $w<em>i$ and gets a weighted amount of service in each cycle: $\frac{w</em>i}{\sum<em>j w</em>j}$.