Network Layer Notes

Network Layer: Data Plane

Network Layer Goals

• Understand the principles behind network layer services, focusing on the data plane:
  • Network layer service models.
  • Forwarding versus routing.
  • How a router works.
  • Addressing.
  • Generalized forwarding.
  • Internet architecture.
• Instantiation and implementation in the Internet:
  • IP protocol.
  • NAT, middleboxes.

Data Plane Roadmap

• Network Layer Overview
  • Data plane
  • Control plane
• What’s Inside a Router
  • Input ports, switching, output ports
  • Buffer management, scheduling
• IP: The Internet Protocol
  • Datagram format
  • Addressing
  • Network address translation
  • IPv6
• Generalized Forwarding, SDN
  • Match+action
  • OpenFlow: match+action in action
• Middleboxes

Network Layer Services and Protocols

• Transport segment from sending to receiving host:
  • Sender: encapsulates segments into datagrams, passes to link layer.
  • Receiver: delivers segments to transport layer protocol.
• Network layer protocols in every Internet device: hosts, routers.
• Routers:
  • Examines header fields in all IP datagrams passing through it.
  • Moves datagrams from input ports to output ports to transfer datagrams along the end-to-end path.

Key Network-Layer Functions

• Forwarding: Move packets from a router’s input link to the appropriate router output link.
  • Analogy: getting through a single interchange.
• Routing: Determine the route taken from source to destination by packets.
  • Analogy: process of planning trip
  • Routing algorithms.

Data Plane vs. Control Plane

• Data Plane:
  • Local, per-router function.
  • Determines how a datagram arriving on a router input port is forwarded to a router output port.
• Control Plane:
  • Network-wide logic.
  • Determines how a datagram is routed among routers along the end-to-end path from source host to destination host.
• 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.

Software-Defined Networking (SDN) Control Plane

Remote controller computes and installs forwarding tables in routers.

Network Service Model

• Example services for individual datagrams:
  • Guaranteed delivery.
  • Guaranteed delivery with less than 40 msec delay.
• Example services for a flow of datagrams:
  • In-order datagram delivery.
  • Guaranteed minimum bandwidth to flow.
  • Restrictions on changes in inter-packet spacing.

Internet Service Model

• Internet: Best Effort.
  • Bandwidth: None.
  • Loss: No.
  • Order: No.
  • Timing: No.
  • No guarantees on:
    • Successful datagram delivery to destination.
    • Timing or order of delivery.
    • Bandwidth available to end-to-end flow.
• ATM: Constant Bit Rate, Available Bit Rate.
  • Variable Quality of Service (QoS) Guarantees.
• Intserv: Guaranteed (RFC 1633).
  • Bandwidth: Guaranteed minimum.
  • Loss: Yes.
  • Order: Yes.
  • Timing: No.
• Diffserv: (RFC 2475).
  • Bandwidth: Possible.
  • Loss: Possibly.
  • Order: Possibly.
  • Timing: No.

Reflections on Best-Effort Service

• Simplicity of mechanism has allowed the Internet to be widely deployed and adopted.
• Sufficient provisioning of bandwidth allows performance of real-time applications (e.g., interactive voice, video) to be “good enough” for “most of the time.”
• Replicated, application-layer distributed services (datacenters, content distribution networks) connecting close to clients’ networks allow services to be provided from multiple locations.
• Congestion control of “elastic” services helps.
• It’s hard to argue with the success of the best-effort service model because of the widespread adoption and continuous improvements.

Router Architecture Overview

• High-level view of generic router architecture:
  • Input ports, high-speed switching fabric, Output ports, routing processor.
  • Forwarding data plane (hardware) operates in nanosecond timeframe
  • Routing, management control plane (software) operates in millisecond timeframe.

Router Architecture Analogy

Analogy view of generic router architecture as a roundabout.

Input Port Functions

• Line termination: physical layer, bit-level reception.
• Link layer protocol (receive): e.g., Ethernet.
• Lookup, forwarding, queueing.
• Decentralized switching:
  • Using header field values, lookup output port using forwarding table in input port memory (“match plus action”).
  • Goal: complete input port processing at ‘line speed’.
  • Input port queuing: if datagrams arrive faster than forwarding rate into switch fabric.

Destination-Based Forwarding

Forwarding based only on destination IP address (traditional).

Generalized Forwarding

Forwarding based on any set of header field values.

Longest Prefix Matching

When looking for a forwarding table entry for a given destination address, use the longest address prefix that matches the destination address.

• Often performed using ternary content addressable memories (TCAMs).
  • Content addressable: present address to TCAM, retrieve address in one clock cycle, regardless of table size.
  • Cisco Catalyst: ∼1M routing table entries in TCAM

Switching Fabrics

• Transfer packets from input link to appropriate output link.
• Switching rate: the rate at which packets can be transferred from inputs to outputs.
  • Often measured as a multiple of the input/output line rate.
  • N inputs: switching rate N times line rate desirable. $R * N$ (rate: NR, ideally).

Types of Switching Fabrics

Switching fabrics can be implemented using memory, bus, or interconnection network.

Switching via Memory

• First-generation routers:
  • Traditional computers with switching under direct control of CPU.
  • Packet copied to the system’s memory.
  • Speed limited by memory bandwidth (2 bus crossings per datagram).

Switching via a Bus

• Datagram from input port memory to output port memory via a shared bus.
• Bus contention: switching speed limited by bus bandwidth.
• 32 Gbps bus, Cisco 5600: sufficient speed for access routers.

Switching via Interconnection Network

• Crossbar, Clos networks, other interconnection nets initially developed to connect processors in multiprocessor.
• Multistage switch: nxn switch from 3x3 crossbar multiple stages of smaller switches
• Exploiting parallelism:
  • Fragment datagram into fixed-length cells on entry.
  • Switch cells through the fabric, reassemble datagram at exit.
• Scaling, using multiple switching “planes” in parallel. Speedup, scaleup via parallelism achieved with 8 switching planes. Each plane is a 3 stage interconnection network. Yielding 100's of Tbps switching capacity.
• Cisco CRS router:
  • Basic unit: 8 switching planes.
  • Each plane: 3-stage interconnection network.
  • Up to 100’s Tbps switching capacity.

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: a queued datagram at the front of the queue prevents others in the queue 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.
• Datagrams can be lost due to congestion, lack of buffers.
• Priority scheduling – who gets best performance, network neutrality?

How Much Buffering?

• RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity C
  • e.g., C = 10 Gbps link: 2.5 Gbit buffer
• Too much buffering can increase delays (particularly in home routers).
  • Long RTTs: poor performance for real-time apps, sluggish TCP response.
  • Recall delay-based congestion control: “keep bottleneck link just full enough (busy) but no fuller.”
• More recent recommendation: with N flows, buffering equal to $\frac{RTT * C}{\sqrt{N}}$.

Buffer Management

• Drop: which packet to add, drop when buffers are full
  • Tail drop: drop arriving packet.
  • Priority: drop/remove on priority basis.
• Marking: which packets to mark to signal congestion (ECN, RED).

Packet Scheduling: FCFS

• Deciding which packet to send next on link.
• First Come, First Served (FCFS):
  • Packets transmitted in order of arrival to output port.
  • Also known as First-In-First-Out (FIFO).

Priority Scheduling

• Arriving traffic is classified and queued by class.
• Any header fields can be used for classification.
• Send packet from the highest priority queue that has buffered packets.
  • FCFS within priority class.

Round Robin (RR) Scheduling

• Arriving traffic is classified and queued by class.
• Any header fields can be used for classification.
• Server cyclically, repeatedly scans class queues, sending one complete packet from each class (if available) in turn.

Weighted Fair Queueing (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}$

Sidebar: Network Neutrality

• Technical: how an ISP should share/allocate its resources.
• Packet scheduling, buffer management are the mechanisms.
• Social, economic principles:
  • Protecting free speech.
  • Encouraging innovation, competition.
• Enforced legal rules and policies.
• Different countries have different “takes” on network neutrality.

2015 US FCC Order on Protecting and Promoting an Open Internet: three “clear, bright line” rules:

• No blocking: Shall not block lawful content, applications, services, or non-harmful devices, subject to reasonable network management.
• No throttling: Shall not impair or degrade lawful Internet traffic on the basis of Internet content, application, or service, or use of a non-harmful device, subject to reasonable network management.
• No paid prioritization: Shall not engage in paid prioritization.

ISP: Telecommunications or Information Service?

• US Telecommunication Act of 1934 and 1996:
  • Title II: imposes “common carrier duties” on telecommunications services: reasonable rates, non-discrimination and requires regulation.
  • Title I: applies to information services:
    • No common carrier duties (not regulated).
    • But grants FCC authority “… as may be necessary in the execution of its functions”.
• Is an ISP a “telecommunications service” or an “information service” provider?
  • The answer really matters from a regulatory standpoint!

Internet Host, Router Network Layer Functions

• IP protocol:
  • Datagram format
  • Addressing
  • Packet handling conventions
• ICMP protocol:
  • Error reporting
  • Router “signaling”
• Path-selection algorithms: implemented in:
  • Routing protocols (OSPF, BGP)
  • SDN controller

IP Datagram Format

• Version ver
• Header length length
• Type of service
• Flags flgs
• Fragment offset offset
• Time to live TTL
• Upper layer
• Header checksum
• Source IP address
• Destination IP address
• Options (if any)
• Payload data (variable length, typically a TCP or UDP segment)
• Type of service:
  • Diffserv (0:5)
  • ECN (6:7)
• Fragmentation/reassembly. Remaining max hops (decremented at each router).
• Header checksum
• Maximum length: 64K bytes, Typically: 1500 bytes or less
• 32-bit Source IP address
• 32-bit Destination IP address
• e.g., timestamp, record route taken. = 40 bytes + app layer overhead for TCP+IP overhead
  • 20 bytes of TCP
  • 20 bytes of IP

IP Addressing: Introduction

• IP address: 32-bit identifier associated with each host or router interface.
• Interface: connection between host/router and physical link.
  • Routers typically have multiple interfaces.
  • Hosts typically have one or two interfaces (e.g., wired Ethernet, wireless 802.11).

Subnets

• What’s a subnet?
  • Device interfaces that can physically reach each other without passing through an intervening router.
• network consisting of 3 subnets
• IP addresses have structure:
  • Subnet part: devices in same subnet have common high-order bits.
  • Host part: remaining low-order bits.
• Recipe for defining subnets:
  • Detach each interface from its host or router, creating “islands” of isolated networks.
  • Each isolated network is called a subnet.
  • Subnet mask: /24 (high-order 24 bits: subnet part of IP address).

IP Addressing: CIDR

• CIDR: Classless InterDomain Routing (pronounced “cider”).
• Subnet portion of address of arbitrary length.
• Address format: a.b.c.d/x, where x is # bits in subnet portion of address.

IP Addresses: How to Get One?

• How does a host get an IP address within its network (host part of address)?
• How does a network get an IP address for itself (network part of address)?
• How does a host get an IP address?
  • Hard-coded by sysadmin in config file (e.g., /etc/rc.config in UNIX).
  • DHCP: Dynamic Host Configuration Protocol: dynamically get address from the server.