Unit 4: Routing and IP Header

I. Foundations of Internetwork Routing

Routing is the network-layer process of selecting paths through interconnected networks and forwarding packets toward their destinations. Internet Protocol provides logical addressing and packet formats, while routers use routing algorithms and forwarding tables to move packets between networks.

• Core properties:
  • Layer: Routing and IP operate at the OSI network layer, or the Internet layer of the TCP/IP model.
  • Packet delivery: IP provides connectionless, best-effort delivery; it does not guarantee arrival, ordering, or error recovery.
  • Routing versus forwarding: Routing computes paths and builds routing tables, whereas forwarding sends each packet through the selected outgoing interface.
  • Metric: A numerical value such as hop count, delay, bandwidth cost, or administrative weight represents path quality.
  • Convergence: Routers converge when their routing information becomes mutually consistent after a topology change.
  • Address evolution: IPv4 uses 32-bit addresses; IPv6 uses 128-bit addresses and a simplified fixed-length base header.
  • Address conservation: NAT allows private IPv4 networks to share limited globally routable addresses.

II. Routing Decision Process — Selecting Paths Through a Network

A. Routing Algorithms

A routing algorithm determines the path packets should follow from a source network to a destination network.

• Routing table: Each entry normally contains a destination prefix, next-hop address, outgoing interface, metric, and route source.
• Desired properties: An effective algorithm should provide correctness, simplicity, robustness, stability, fairness, and efficient path selection.
• Static routing: Routes are entered manually and remain unchanged until an administrator modifies them.
  • Advantage: It creates little control traffic and behaves predictably.
  • Limitation: It does not automatically respond to failed links or topology changes.
• Dynamic routing: Routers exchange information and automatically recompute routes when the network changes.
• Centralized versus distributed: A centralized algorithm uses a controller with broad topology knowledge; a distributed algorithm lets routers cooperate using exchanged information.
• Adaptive versus non-adaptive: Adaptive routing reacts to topology or traffic changes, while non-adaptive routing uses predetermined paths.
• Hierarchical routing: Large internetworks are divided into routing domains, reducing table size and update traffic; the Internet uses autonomous systems for this purpose.
• Forwarding rule: Routers generally apply longest-prefix matching, choosing the matching route with the greatest prefix length. For example, 192.0.2.128/25 is preferred over 192.0.2.0/24 for destination 192.0.2.150.
• Limitations: Frequent changes can cause temporary loops, packet loss, route oscillation, and control-message overhead.

III. Minimum-Cost Route Computation — Graph-Based Path Selection

A. Shortest Path Algorithm

A shortest path algorithm models a network as a weighted graph and finds the least-cost route from one node to other nodes.

• Graph model: Routers are vertices, links are edges, and each edge has a non-negative cost representing distance, delay, or another metric.
• Path cost: For path (P), total cost is the sum of its link costs.

C(P) = Σ c(e)

C(P) = total path cost
c(e) = cost assigned to edge e

• Dijkstra’s algorithm: Starting from source s, it repeatedly finalizes the unvisited node with the smallest tentative distance.
  • Set D(s) = 0; set every other distance to infinity.
  • Select the unvisited node u with minimum D(u).
  • Relax each edge from u to neighbor v.
  • Repeat until all reachable nodes are finalized.

if D(u) + c(u,v) < D(v):
    D(v) = D(u) + c(u,v)
    predecessor(v) = u

• Worked example: If A-B = 2, A-C = 5, and B-C = 1, the direct route from A to C costs 5, but A-B-C costs 2 + 1 = 3; therefore, the latter is selected.
• Complexity: With a binary heap and adjacency list, Dijkstra’s algorithm runs in approximately O((V + E) log V).
• Constraint: Standard Dijkstra routing requires non-negative link costs and current topology information.

IV. Neighbor-Based Distributed Routing — Learning Through Local Exchanges

A. Distance Vector Routing

Distance vector routing lets each router advertise its estimated distance to destinations to directly connected neighbors.

• Information maintained: Router x stores a distance estimate Dₓ(y) and next hop for each destination y.
• Bellman-Ford relation: A router selects the neighbor producing the lowest combined link and advertised cost.

Dₓ(y) = minᵥ { c(x,v) + Dᵥ(y) }

Dₓ(y) = x's estimated cost to destination y
c(x,v) = link cost from x to neighbor v
Dᵥ(y) = neighbor v's advertised distance to y

• Operation: Routers exchange vectors periodically or after changes, update lower-cost entries, and continue until estimates stabilize.
• Example protocol: RIP uses hop count as its metric; 15 hops is the largest usable distance, and 16 represents an unreachable destination.
• Count-to-infinity problem: After a failure, neighboring routers may incorrectly advertise routes through one another, increasing the metric step by step.
• Loop controls:
  • Split horizon: A route is not advertised back through the interface from which it was learned.
  • Poison reverse: That route is advertised back with an infinite metric.
  • Triggered updates: Significant changes are advertised immediately instead of waiting for the periodic timer.
• Strengths: The method is distributed, requires no complete topology map, and is relatively simple.
• Limitations: Convergence can be slow, loops may occur temporarily, and periodic full-table updates consume bandwidth.

V. Topology-Aware Routing — Independent Calculation from Shared State

A. Link State Routing

Link state routing makes every router learn the network topology and independently calculate shortest paths.

• Neighbor discovery: A router identifies directly connected routers, often through hello messages.
• Link measurement: It assigns a cost to each active interface or adjacency.
• Link-state advertisement: The router describes its neighbors, link costs, sequence number, and age in a link-state packet or advertisement.
• Flooding: Advertisements are reliably distributed throughout the routing area so routers obtain matching link-state databases.
• Route calculation: Each router treats itself as the root and runs Dijkstra’s algorithm to construct a shortest-path tree.
• Example protocol: OSPF is a link-state interior gateway protocol that supports cost-based routing, areas, authentication options, and classless prefixes.
• Freshness controls: Sequence numbers distinguish newer information, while aging removes obsolete records.
• Advantages: Link failures are generally propagated quickly, convergence is faster than traditional distance vector routing, and complete topology knowledge supports accurate decisions.
• Costs: Routers require more memory and processing, while flooding and database synchronization create control overhead.
• Operational risk: Inconsistent databases during convergence can temporarily produce incorrect forwarding decisions.

VI. IPv4 Datagram Structure — Variable-Length Network-Layer Header

A. IPv4 Header

The IPv4 header carries the addressing and control information needed to deliver a datagram across IPv4 networks.

• Header size: The header is normally 20 bytes and may reach 60 bytes when options are present.
• Version and IHL: Version is 4; the 4-bit Internet Header Length gives the header size in 32-bit words. Thus, IHL = 5 means 5 × 4 = 20 bytes.
• DSCP and ECN: These fields support traffic classification and explicit congestion notification.
• Total Length: This 16-bit value includes header and payload, allowing a maximum IPv4 datagram size of 65,535 bytes.
• Fragmentation fields: Identification, Flags, and Fragment Offset allow fragments to be associated and reassembled at the destination.
  • DF: “Don’t Fragment” prevents fragmentation.
  • MF: “More Fragments” indicates that another fragment follows.
• TTL: Time To Live is decreased by each router; the packet is discarded at zero, preventing indefinite circulation.
• Protocol: This identifies the encapsulated payload, such as ICMP 1, TCP 6, or UDP 17.
• Header checksum: Routers recalculate this error-detection value because TTL changes at every hop.
• Addresses: The 32-bit Source Address and Destination Address identify the sender and intended receiver.
• Options and padding: Optional controls extend the header; padding restores a 32-bit boundary.
• Limitation: The small address space and router-handled fragmentation contributed to IPv6 development.

VII. IPv6 Packet Structure — Simplified Fixed Base Header

A. IPv6 Header

The IPv6 base header is a fixed 40-byte structure designed for efficient forwarding and extensibility.

• Version: The 4-bit value is 6.
• Traffic Class: This 8-bit field supports differentiated handling and congestion notification.
• Flow Label: This 20-bit value identifies packets belonging to a flow that may require consistent or special handling.
• Payload Length: A 16-bit value gives the number of bytes after the base header, including extension headers.
• Next Header: This identifies either an IPv6 extension header or an upper-layer protocol such as TCP or UDP.
• Hop Limit: Each router decrements this 8-bit field; the packet is discarded when it reaches zero.
• Addresses: Source and Destination Address fields are each 128 bits.
• Extension headers: Optional functions such as routing, fragmentation, and destination options are placed after the base header.
• IPv4 comparison: IPv6 removes the base-header checksum, options field, and router fragmentation fields, reducing per-hop processing.
• Fragmentation rule: IPv6 routers do not fragment packets; a source uses Path MTU Discovery and may add a Fragment extension header.
• Limitation: IPv6 is not directly interoperable with IPv4, so dual-stack operation, tunneling, or translation may be required during migration.

VIII. IPv6 Address Representation — 128-Bit Hierarchical Identification

A. IPv6 Addressing

IPv6 addressing provides a vastly larger address space and supports hierarchical allocation, automatic configuration, and scoped communication.

• Notation: An address is written as eight groups of four hexadecimal digits, for example 2001:0db8:0000:0000:0000:0000:0000:0042.
• Compression: Leading zeros in a group may be omitted, and one consecutive zero sequence may be replaced once by ::; the example becomes 2001:db8::42.
• Prefix length: CIDR notation such as 2001:db8:1234::/48 states that the first 48 bits identify the network prefix.
• Address types:
  • Unicast: Identifies one interface; global unicast commonly falls within 2000::/3.
  • Link-local: fe80::/10 is used on the local link and is not routed globally.
  • Multicast: ff00::/8 identifies a group of interfaces.
  • Anycast: The same unicast address is assigned to multiple interfaces, and routing delivers packets to a nearby instance.
• No broadcast: IPv6 replaces broadcast communication with multicast.
• Special addresses: :: is unspecified, while ::1 is the loopback address.
• Configuration: Hosts may use Stateless Address Autoconfiguration, DHCPv6, or manual assignment.
• Subnet convention: A /64 prefix is standard for most IPv6 LAN subnets, leaving 64 bits for the interface identifier.

IX. Address Translation — Connecting Private IPv4 Networks to Public Networks

A. Network Address Translation (NAT)

NAT modifies IPv4 address information at a network boundary so private hosts can communicate through public addresses.

• Private ranges: Common non-public prefixes are 10.0.0.0/8, 172.16.0.0/12, and 192.168.0.0/16.
• Static NAT: One private address is permanently mapped to one public address, often for an internally hosted service.
• Dynamic NAT: Private addresses are temporarily mapped to available addresses from a public pool.
• PAT or NAPT: Many private hosts share one public address by using distinct TCP or UDP port numbers.
• Translation entry: A mapping may convert 192.168.1.10:52000 to 203.0.113.5:40001; return traffic matching the public tuple is translated back.
• Checksum handling: Because addresses or ports change, NAT must update affected IP and transport-layer checksums.
• Benefits: NAT conserves public IPv4 addresses and hides internal addressing details from ordinary external traffic.
• Limitations: It weakens end-to-end connectivity, complicates inbound sessions, and can interfere with protocols that embed addresses in payloads.
• Inbound access: Port forwarding creates a fixed public address-and-port mapping to an internal service.
• Traversal: Applications may use techniques such as STUN, TURN, or ICE when peer-to-peer communication must cross NAT devices.
• Security distinction: NAT changes addressing but is not a complete security mechanism; access control still requires firewall policy.