Network Layer Functions and Protocols

Chapter 4: Network Layer

• Computer Networking: A Top-Down Approach (6th edition) by Jim Kurose and Keith Ross, Addison-Wesley, March 2012
• Chapter Goals: Understand principles behind network layer services, including network layer service models, forwarding versus routing, how a router works, routing (path selection), broadcast, multicast, instantiation, and implementation in the Internet.

Chapter 4: Outline

• 4.1 Introduction

• 4.2 Virtual Circuit and Datagram Networks

• 4.3 What's Inside a Router

• 4.4 IP: Internet Protocol

  • Datagram format
  • IPv4 addressing
  • ICMP
  • IPv6

• 4.5 Routing Algorithms

  • Link state
  • Distance vector
  • Hierarchical routing

• 4.6 Routing in the Internet:

  • RIP
  • OSPF
  • BGP

• 4.7 Broadcast and Multicast Routing

Network Layer

• Transport Segment: Transports segments from sending to receiving host.
• Encapsulation: Encapsulates segments into datagrams on sending side.
• Delivery: Delivers segments to transport layer on receiving side.
• Protocols: Network layer protocols operate in every host and router.
• Header Fields: Routers examine header fields in all IP datagrams passing through.

Two Key Network Layer Functions

• Forwarding: Moves packets from a router's input to the appropriate output port.
• Routing: Determines the route taken by packets from source to destination.
• Routing Algorithms: Used to determine routes.

Interplay Between Routing and Forwarding

• Routing Algorithm: Determines the end-to-end path through the network.
• Local Forwarding/Table: Determines the local forwarding at the router.

Connection Setup

• Network layer connection services: Between two hosts (or potentially intervening routers in Virtual Circuits).
• Transport Layer connection services: Between two processes.

Network Service Models

• 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

Virtual Circuits

• Analogy: Source-to-destination path behaves like a telephone circuit for performance and actions along that path.
• Call Setup: Call setup/teardown for each call before data flows.
• VC Identifier: Each packet carries a VC identifier (not destination host address).
• State Maintenance: Every router maintains state for each passing connection on the source-destination path.
• Resource Allocation: Link and router resources (bandwidth, buffers) may be allocated to VC (predictable service).

VC Implementation

• VC path: Constitutes the path from source to destination.
• VC numbers: Assigned one number for each link along the path (entries in forwarding tables).
• Packet carrying VC number: Packet belonging to VC carries VC number (rather than dest address).
• VC number changes: VC number can be changed on each link.
• New VC number from forwarding tables: New VC number comes from forwarding tables.

VC Forwarding Table

• Incoming interface: Interface the packet arrives on.
• Incoming VC#: The VC number of the incoming packet.
• Outgoing interface: Interface the packet leaves on.
• Outgoing VC#: The VC number of the outgoing packet.

Virtual Circuits: Signaling Protocols

• Used in: ATM, frame-relay, X.25.
• Not Used in: Today's Internet.

Datagram Networks

• No call setup: No call setup at network layer.
• No state: No network-level concept of "connection."
• Destination address: Packets are forwarded using destination host address.

Datagram Forwarding Table

• Dest Address: Destination address or range of addresses.
• Output link: Corresponding output link for the destination.

Longest Prefix Matching

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

Datagram or VC Network: Why?

• Internet (datagram): Data exchange among computers; "elastic" service, no strict timing; many link types; different characteristics; "smart" end systems (can adapt, perform control, error recovery).
• ATM (VC): Evolved from telephony (human conversation); strict timing, reliability requirements; need for guaranteed service; "dumb" end systems (telephones); complexity inside network.

Router Architecture Overview

• Routing algorithms/protocol : Run routing protocol (RIP, OSPF, BGP).
• Forwarding datagrams: Forward datagrams from incoming to outgoing links.

Input Port Functions

• Line termination: Bit-level reception.
• Link Layer (receive): Link layer protocol receive.
• Lookup/forwarding: Lookup forwarding, and queueing.
• Switch fabric: Switch fabric acts as a connection point.
• Decentralized switching: Given a datagram, look up output port using forwarding table.

Switching Fabrics

• Packet transfer: Transfer packets from input buffer to appropriate output buffer.
• Switching rate: Rate at which packets can transfer from inputs to outputs.
• Types: Memory switching, bus switching, crossbar switching.

Switching via Memory

• First-generation routers: Traditional computers with switching under direct control of CPU.
• Packet Copying: Packet copied to system memory.
• Speed limitation: Limited by memory bandwidth.

Switching via Bus

• Datagram Transfer: Datagram is transferred from input port memory to output port memory via a shared bus.
• Bus contention: Switching speed limited by the bus bandwidth.
• Cisco 5600 example: 32 Gbps bus in Cisco 5600 is sufficient for access/enterprise routers.

Switching via Interconnection Network

• Bus/Bandwidth Limitation issues: Overcome bus bandwidth limitations with banyan networks, crossbar, other interconnection networks.
• Advanced design: Fragmenting datagram into fixed-length cells, switching cells through fabrics (e.g., Cisco 12000).

Output Ports

• Buffering: Buffering is required from fabric faster rate.

• Scheduling: Priority scheduling.

Output Port Queuing

• Arrival rate: Buffering when arrival rate via switch exceeds output line speed.
• Loss and delay: Queueing (delay) and loss due to the output port buffer overflow.

How Much Buffering?

• RFC 3439: Average buffering is equal to typical RTT(say 250msec).
• Capacity (C): Times link capacity C (e.g., 10 Gbps link: ~2.5 Gbit buffer).
• Recommendation for many flows: With N flows, buffering equal to RTT.C / N

Input Port Queuing

• Fabric slower: Fabric slower than input ports combined which can lead to queueing at input queues.
• Delay/Loss: Queueing delay and loss due to input buffer overflow.
• HOL blocking: Head-of-the-line blocking.

ICMP

• Internet Control Message Protocol: Used for error reporting from hosts and routers.

IPv6: Motivation

• Address space: 32-bit address space is shrinking.
• Header format: Header format improvement for faster processing and QoS.

IPv6 Datagram Format

• Priority and flow labels: Identifies priority and flow, respectively.
• Fixed-length header: Fixed-length 40 byte header.
• No fragmentation: No fragmentation (to avoid issues at lower levels/routers).

Other Changes from IPv4

• Checksum removal: Processing time reduced through checksum removal.
• Options: Options outside of the header, indicated by "Next Header" field in order to save space.
• ICMPv6: Extensions to ICMP.
• Message Types: New/Additional message types are added.

Transition from IPv4 to IPv6

• Tunneling: IPv6 datagram carried as payload in an IPv4 datagram for transit between IPv4 and IPv6 routers.

IP Addressing

• Introduction: IP addresses are identifiers for hosts and routers on an internet.
• Interface: An interface is a connection between a host/router and a physical link.
• Host/routers: Routers typically have multiple interfaces; Hosts typically has one or two interfaces (Wired/Wireless).

Subnets

• IP address: High-order bits in subnet and low-order bits in host part.

• What's a Subnet: A subnet is a set of interfaces with the same subnet part of the IP address.

• Recipe: To determine subnets, detach each interface from its host and create islands of isolated networks.

IP Addressing: CIDR

• Classless Inter-Domain Routing: Allows assigning arbitrary-length subnet portions of an IP address.
• Format: Format is a.b.c.d/x where x is the number of bits in subnet portion of address.

IP Addresses: How to Get One?

• Hard-coded: Hard-coded by system administrator.
• DHCP: Dynamic Host Configuration Protocol: Dynamically obtain IP address from the server.

DHCP: Dynamic Host Configuration Protocol

• Goal: Allows hosts to dynamically obtain IP addresses from a network server.
• Lease renewal: Renew IP leases automatically.
• Address reuse: Allows reuse of addresses when a device is no longer connected on the network.

DHCP Client-Server Scenario

• Client's Request: Arriving DHCP client needing an address from the network.

DHCP: More than IP addresses

• More Data: Provides more data beyond the IP address: first-hop router, DNS server, subnet mask.

NAT: Network Address Translation

• Motivation: Local networks use one IP address to the outside world; range of addresses not needed; can change addresses without notifying outside world; can change ISPs.

• Implementation: NAT router must translate addresses when packets are sent out or received by the router.

NAT Traversal Problem

• External visibility: NATted devices are only visible externally through a single address.
• Solution 1: Statically configure NAT to forward incoming connection requests at a given port to the server.

IPv6: Adoption

• Estimates: US National Institutes of Standards estimate (2013) about ~3% of industry IP routers and ~11% of US government routers use IPv6.
• Deployment and usage: Long periods for deployment and widespread usage.