19: IP and Routing Tables

Lecture Overview

  • University: University of Nottingham

  • Lecturers: Rebecca Tickle, Dr. Steven Bagley

  • Course: COMP1055

  • Lecture Topic: IP (Internet Protocol) and Routing Tables

Lecture Content Overview

  • Understanding the Application Layer, Transport Layer, Internet Layer, Network Interface Layer, and Physical Layer (Layers 1-5).

Return to IP

  • Focused on:

    • IP packets and fragmentation

    • More on routing and constructing routing tables

    • TCP (Transmission Control Protocol)

IPv4 Packet Structure

  • An IPv4 packet consists of several important fields:

    • Version: Indicates the IP version (IPv4).

    • IHL (Internet Header Length): Length of the header.

    • DSCP (Differentiated Services Code Point): Used for QoS (Quality of Service).

    • Total Length: Entire size of the packet including the header and data.

    • Identification: Unique value for each packet used for reassembly.

    • Flags: Control flags such as fragmentation control.

    • Fragmentation Offset: Indicates the position of a fragment within the original packet.

    • Time to Live (TTL): Limits the packet's lifetime to prevent looping.

    • Protocol: Indicates the protocol used in the payload (e.g., TCP, UDP).

    • Header Checksum: Error-checking mechanism for the header.

    • Source Address: Origin of the packet.

    • Destination Address: Intended recipient of the packet.

    • Options: Additional controls, may include padding.

    • Data: The actual payload which is variable in length.

Fragmentation

  • Definition: Fragmentation refers to the process of breaking down IP packets into smaller chunks to be transmitted over heterogenous networks that may have different maximum transmission unit (MTU) sizes.

  • Key Points:

    • IP packets must fit within the MTU of the network they are being sent through.

    • If moving from a network with a larger MTU to one with a smaller MTU, fragmentation is necessary.

    • Fragmented packets are reconstructed at the destination using the Identification field and Fragmentation Offset.

Example of Fragmentation

  • Two networks with different MTU sizes:

    • Network 1: MTU of 4500 bytes

    • Network 2: MTU of 1500 bytes

  • Process:

    • Packets sent from Network 1 must be fragmented to fit into the 1500 bytes of Network 2.

“Don’t Fragment” Flag

  • Defined as a single bit in the Flags field:

    • 0: Packet can be fragmented.

    • 1: Do not fragment the packet.

    • If the DF flag is set to 1 and the packet exceeds the network’s MTU, the packet is dropped and an ICMP (Internet Control Message Protocol) message is sent back to the source.

Path MTU Discovery

  • A method of determining the largest packet size (MTU) that can be sent without fragmentation.

  • Implementation:

    • If a router receives a packet that exceeds its MTU, it drops the packet and sends an ICMP message back, containing the router's MTU.

    • The source then adjusts its MTU accordingly and retransmits the data.

Routing Table Overview

  • Routing tables are used to map destination addresses to the next hop address.

    • Every machine maintains its own routing table, which can vary based on network connections.

Example Routing Table

  • For networks where various machines share the same next hop:

Destination  Next Hop  
1.B          LOCAL     
1.C          LOCAL     
1.D          LOCAL     
2.B          1.B       
2.E          1.B       
2.F          1.B

  • Shared next hops reduce the size of routing tables as it maps several destinations to a single next hop.

Hierarchical Addressing

  • Definition: A method of addressing where multiple machines that connect to the same next hop can share routing information to improve efficiency.

    • Next hop information is generalized, avoiding the need to specify all addresses.

  • Routing tables only need to contain network prefixes instead of specifying detailed routing for each individual machine.

Example of Hierarchical Routing

  • Simplification using prefixes in routing tables:

Destination  Next Hop  
1.*          LOCAL     
2.*          1.B

Default Routes

  • Default routes in routing tables reduce the complexity by allowing matching of unspecified destinations.

  • Default routes are used unless a more specific route exists, leading to simpler routing table construction.

Properties of a Routing Table

  • Source Independence: Routing is based on packet destination, regardless of source.

  • Hierarchical: Only the network level is necessary, not individual machines.

  • Universal Routing: A next hop is specified for every destination.

  • Optimal Routes: Shortest paths are preferred for efficiency.

  • Default Route: Acts as a catch-all for unmatched destinations.

Constructing a Routing Table

  • Static Routing: Built manually during router initialization, inflexible and cannot adapt to network changes.

  • Dynamic Routing: Developed by routers through communication with each other, allowing real-time updates and adaptability.

Algorithms for Dynamic Routing

  • Dijkstra’s Algorithm: A popular algorithm to determine the shortest path in graph structures of networks:

    • Works by exploring all nodes and evaluating paths.

    • It involves initializing distances from the source to other nodes and iteratively updating these distances based on known paths.

Example of Dijkstra’s Algorithm Initialization

  • Set of nodes: {A, B, C, D, E}

  • Distance table initialization from a source node:

  v          D[v]        R[v]  
  A          1           A     
  B          10          B     
  C          2           A     
  D          2           D     
  E          Inf.

  • The algorithm incrementally discovers and optimizes paths until no nodes are left in the set.

Conclusion

  • The lectures summarize the intricate relationships between IP, routing tables, fragmentation, and hierarchical routing, encapsulating the dynamic aspects of networking and addressing. Understanding these concepts is crucial for designing resilient and optimized networking systems.