COSC 350: Data Communications and Networking - NetData Part 1 Notes

Network Layer: Data Plane

Network Layer Goals

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

Data Plane Roadmap

  • Network layer overview: data plane, control plane.
  • Router internals: input ports, switching, output ports, buffer management, scheduling.
  • IP (Internet Protocol): datagram format, addressing, network address translation, IPv6.
  • Generalized Forwarding and SDN (Software-Defined Networking): Match+action, OpenFlow.
  • 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 exist in every Internet device: hosts, routers.
  • Routers:
    • Examine header fields in all IP datagrams passing through.
    • Move 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 during a trip.
  • Routing: determine the route taken by packets from source to destination.
    • Analogy: planning the entire trip from source to destination.
    • Involves 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.

Control Plane Implementations

Per-router control plane:

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

Software-Defined Networking (SDN):

  • Remote controller computes and installs forwarding tables in routers.

Network Service Models

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

Network-Layer Service Models Compared

FeatureInternet (Best Effort)ATM (CBR)ATM (ABR)Intserv (Guaranteed)Diffserv
BandwidthNoneConstantGuaranteed minYesPossible
LossNoYesNoYesPossibly
OrderNoYesYesYesPossibly
TimingNoYesNoYesNo
QoS GuaranteesNoYesNoneYesNone
  • Internet's “best effort” service model offers no guarantees on:
    • Successful datagram delivery to destination.
    • Timing or order of delivery.
    • Bandwidth available to end-to-end flow.

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.

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

Input Port Functions

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

Destination-Based vs Generalized Forwarding

  • Decentralized switching using header field values from forwarding table in input port memory via "match plus action"
  • Destination-based forwarding: forward based only on destination IP address (traditional).
  • Generalized forwarding: forward based on any set of header field values.

Destination-Based Forwarding

  • Forwarding table maps destination address ranges to link interfaces.
  • Question: What happens if ranges don't divide up so nicely?

Longest Prefix Matching

  • When looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.
  • Example:
    • Destination Address: 11001000 00010111 00011000 10101010
    • Matches:
      • 11001000 00010111 00010******* (Interface 0)
      • 11001000 00010111 00011000******** (Interface 1)
      • 11001000 00010111 00011 (Interface 2)
      • Otherwise (Interface 3)
    • Select Interface 1 due to the most specific match.

Switching Fabrics

  • Transfer packet from input link to appropriate output link.
  • Switching rate: rate at which packets can be transferred from inputs to outputs.
    • Often measured as a multiple of input/output line rate.
    • N inputs implies a desirable switching rate of N times the line rate.

Types of Switching Fabrics

  • Three major types:
    • Memory.
    • Bus.
    • Interconnection network.

Switching via Interconnection Network

  • Crossbar, Clos networks, other interconnection nets initially developed to connect processors in multiprocessor systems
  • NxN switch from 3x3 crossbar multiple stages of smaller switches
  • 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

Switching via Interconnection Network - Scaling

  • Scaling, using multiple switching “planes” in parallel.
  • Cisco CRS router:
    • Basic unit: 8 switching planes.
    • Each plane: 3-stage interconnection network.
    • Up to 100’s Tbps switching capacity.

Output Port Queuing

  • Buffering required when datagrams arrive from 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

Buffer Management

  • Buffer management: policies for when the memory is full
    • 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 arrivals packet departures link (server)

Packet Scheduling

  • Packet scheduling: deciding which packet to send next on link
    • First come, first served (FCFS)
    • Priority
    • Round robin
    • Weighted fair queueing

Packet Scheduling: FCFS

  • FCFS: packets transmitted in order of arrival to output port
  • Also known as: First-in-first-out (FIFO)
  • Real world examples?

Priority Scheduling

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

Round Robin (RR) Scheduling

  • Arriving traffic classified, 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 Queuing (WFQ)

  • Generalized Round Robin.
  • Minimum bandwidth guarantee (per-traffic-class).
  • Each class, i, has weight, w_i, and gets weighted amount of service in each cycle:
    • \frac{wi}{\sumj w_j}