Content

1. Overview
2. Routing & Forwarding
3. Internet Protocol
   1. IP Header
   2. IP Fragmentation
      1. Avoid Fragmentation - Path MTU Discovery
4. IPv4 Addressing
   1. Format
5. Classless InterDomain Routing (CIDR)
   1. Longest Prefix Match
6. Classful Addressing
7. Special Addresses

Overview

Support host-to-host communication.

• Challenges
  • Efficiency: finding the best route in a large-scale network
  • Heterogeneity: different addressing schemes, packet sizes, service models, network types, ...

Routing & Forwarding

• Routing function
  • Determines the best path routing packets from source to destination
  • Collaboration of routers
  • Determines the forwarding table of each router
• Forwarding/Switching function
  • Forwards packets from input port to output port by dynamically connecting input & output
  • Determines the output port based on packet header & forwarding table
• Principles
  • Each packet routed independently
    • May take different routes and arrive out-of-order
  • Routers have no connection state about end-to-end connections flowing through the network
  • Receivers should:
    • Reorder packets
    • Handle packet losses

Internet Protocol

• Best effort, connectionless packet delivery
• Responsibility
  • Forwarding
    • Addressing schemes
    • Path selections
  • Datagram management
    • Datagram format
      • Header + data
      • 20 B fixed header + variable length (max 40 B) optional
    • Fragmentation & reassembly
  • Error control
    • ICMP

IP Header

IP Fragmentation

Physical links have maximum transfer unit (MTU), so have to fragment datagrams into smaller ones.
Identified, ordered, & reassembled at final destination (identifier, flag, offset) before passing to upper layer.

Make data length multiple of 8 B.

Avoid Fragmentation - Path MTU Discovery

• Don't fragment (DF) bit
  • Any device along the path with MTU < DF will drop the packet and send back internet control message protocol (ICMP) message, which includes the MTU of the link

IPv4 Addressing

• 32-bit identifier
  • Uniquely identify an interface of a router/host
• Interface
  • Router: multiple ports, only active ports is assigned IP addresses associated with that network
  • Host: multi-homed

Format

|subnet bits|host bits|/subnet mask

• Subnet
  • All interfaces under the same IP network have the same subnet
  • All interfaces in the same subnet can physically reach each other using link layer info (MAC address) without intervening router
• Subnet mask (network prefix)
  • Left most bits indicating the subnet address of that IP address
  • ...00...0 & ...11...1 is reserved for subnet address & broadcast address
• Host
  • Locate individual interfaces in the subnet
  • Assigned locally by network admin
• The combination is globally unique except for private networks

Classless InterDomain Routing (CIDR)

|network|subnet|host|

An organization is assigned a block of contiguous addresses, which can be further divided into smaller subnets visible to the organization only.

External routers only need a single entry in their forwarding tables to reach all destinations within the organization.

• Variable-sized block
  • Can aggregate a few small contiguous subnets into 1 single prefix -> reduces size of forwarding table
  • Forwarding table needs to be scanned to find longest prefix match
• Change to classless addressing scheme makes the need to change in routing table organization & searching

Longest Prefix Match

• Forwarding table scanned entry-by-entry
  • Address of incoming packet AND with subnet mask of entry
  • Compared with network address of entry
  • If multiple entries are matched, choose the one with longest prefix (more specific)

Classful Addressing

• Class A
  • |0|network(7)|host(24)|
  • 126 networks, 16 million hosts each
• Class B
  • |01|network(14)|host(16)|
  • 16384 networks, 65 thousands hosts each
• Class C
  • |011|network(21)|host(8)|
  • 2 million networks, 254 hosts each
• Class D
  • |0111|multicast addresses(28)|
• Class E
  • |1111|...|

Special Addresses

• 0.0.0.0: this host
• Subnet all 0s, host non-zero: a host in this network
• 255.255.255.255: broadcast on this subnet
• Subnet non-zero, host all 0s: broadcast on that network
• 01111111 (127): loopback
• Private networks
  • 10.0.0.0/8
  • 172.16.0.0/8
  • 192.168.0.0/16