Unit4 - Subjective Questions

An IPv4 datagram consists of a header part and a text (data) part. The header has a nominal 20-byte fixed part and a variable-length options part.

Key fields include:

• Version: A 4-bit field indicating the IP version (value is 4 for IPv4).
• Header Length (IHL): A 4-bit field specifying the datagram header length in 32-bit words.
• Type of Service (ToS): Allows the host to specify the treatment the datagram should receive from the network (e.g., delay, throughput, reliability).
• Total Length: A 16-bit field indicating the total length of the IP datagram in bytes (maximum 65,535 bytes).
• Time to Live (TTL): An 8-bit field used to prevent packets from looping endlessly in the network. It is decremented by each router, and if it reaches zero, the packet is discarded.
• Protocol: Indicates the higher-level protocol (e.g., TCP = 6, UDP = 17) to which the payload should be delivered.

Fragmentation is the process of breaking a single IP datagram into smaller fragments to fit within the Maximum Transmission Unit (MTU) of the underlying physical network.

Three key IPv4 header fields manage this process:

• Identification (16 bits): Uniquely identifies fragments of an original IP datagram. All fragments of the same datagram carry the same identification number.
• Flags (3 bits): Contains control flags. The 'Don't Fragment' (DF) bit prevents fragmentation (dropping the packet if it exceeds MTU). The 'More Fragments' (MF) bit is set to 1 for all fragments except the last one.
• Fragmentation Offset (13 bits): Indicates where in the original datagram this fragment belongs. It specifies the offset in units of 8 bytes.

The Header Checksum in IPv4 is a 16-bit field used for error-checking the header to ensure it has not been corrupted in transit.

Calculation Mechanism:

1. The checksum field is initially set to zero.
2. The entire header is treated as a sequence of 16-bit words.
3. These 16-bit words are added together using 1's complement arithmetic.
4. The 1's complement of the final sum is taken and placed in the Checksum field.
5. When a router receives the packet, it performs the same sum including the checksum field. If the header is error-free, the result will be all 1s (or zero in 1's complement). Note: It only covers the header, not the data payload.

The IPv6 base header has a fixed size of 40 bytes, streamlining router processing compared to IPv4.

IPv6 Header Fields:

• Version (4 bits): Set to 6.
• Traffic Class (8 bits): Similar to IPv4 ToS, used for QoS.
• Flow Label (20 bits): Identifies a specific sequence of packets requiring special handling.
• Payload Length (16 bits): Length of the IPv6 payload (excluding the base header).
• Next Header (8 bits): Identifies the type of header immediately following the IPv6 header (similar to Protocol in IPv4).
• Hop Limit (8 bits): Decremented by each node that forwards the packet; packet is discarded if it reaches zero (replaces IPv4 TTL).
• Source & Destination Addresses (128 bits each): The IPv6 addresses.

Differences/Simplicity: IPv6 removes the Header Length, Checksum, and Fragmentation fields from the base header. Fragmentation is handled by extension headers, and checksums are left to upper layers, significantly speeding up packet processing.

In IPv6, optional network-layer information is placed in Extension Headers, which are placed between the base IPv6 header and the upper-layer payload. This design keeps the base header simple and fixed in size (40 bytes).

• Mechanism: The Next Header field in the base header points to the first extension header. If multiple extension headers exist, each contains a Next Header field pointing to the subsequent one, forming a daisy chain, ending with the upper-layer protocol (like TCP/UDP).
• Common Extension Headers:
  • Hop-by-Hop Options: Must be processed by every router on the path.
  • Routing: Specifies a list of routers the packet must visit.
  • Fragment: Used when a source needs to fragment a packet (unlike IPv4, routers do not fragment IPv6 packets).
  • Encapsulating Security Payload (ESP): Provides encryption and authentication.

IPv6 utilizes 128-bit addresses, categorized into three primary types:

1. Unicast: An identifier for a single interface. A packet sent to a unicast address is delivered specifically to the interface identified by that address. (e.g., Global Unicast, Link-Local).
2. Anycast: An identifier for a set of interfaces (typically belonging to different nodes). A packet sent to an anycast address is delivered to the closest interface in that set, based on routing protocol metrics.
3. Multicast: An identifier for a set of interfaces. A packet sent to a multicast address is delivered to all interfaces identified by that address. IPv6 does not implement broadcast addresses; multicast serves this purpose.

Here is a comparison between IPv4 and IPv6:

• Address Space: IPv4 uses 32-bit addresses (approx. 4.3 billion). IPv6 uses 128-bit addresses (virtually inexhaustible).
• Header Size: IPv4 has a variable header (20-60 bytes). IPv6 has a fixed 40-byte base header.
• Fragmentation: In IPv4, routers and sending hosts can fragment packets. In IPv6, only the sending host can fragment packets using Extension Headers.
• Checksum: IPv4 includes a header checksum. IPv6 eliminates the header checksum for faster processing.
• IPsec: Optional in IPv4, but natively supported and integrated into IPv6.
• Configuration: IPv4 uses DHCP or manual configuration. IPv6 supports Stateless Address Autoconfiguration (SLAAC) in addition to DHCPv6.

Network Address Translation (NAT) is a technique used to map private IP addresses to a public IP address before packets are routed onto the public Internet, primarily to conserve IPv4 addresses.

Working Principle:

• A local network uses private IP addresses (e.g., 192.168.x.x) which are not routable on the Internet.
• When a device sends a packet to the Internet, the NAT router intercepts it.
• The router replaces the private Source IP address with its own public WAN IP address and assigns a unique source port number.
• It records this mapping in a NAT Translation Table.
• When the reply returns from the Internet, the router checks the destination port, looks up the NAT table, and translates the public IP and port back to the original private IP and port, forwarding the packet to the correct local device.

Different types of NAT address various networking needs:

• Static NAT: Maps a single unregistered (private) IP address to a single registered (public) IP address on a one-to-one basis. Useful for web servers inside a local network that need to be accessible from the outside.
• Dynamic NAT: Maps a private IP address to a public IP address from a pool of available public IPs. The translation is first-come, first-served until the pool is exhausted.
• Port Address Translation (PAT) / NAT Overload: Maps multiple private IP addresses to a single public IP address by utilizing different source port numbers. This is the most common form of NAT used in home routers, allowing many internal devices to share one public IP.

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. In the Network Layer, routers receive incoming packets, inspect their destination IP addresses, and use routing tables to determine the best outgoing interface.

Key Goals of a Routing Algorithm:

• Correctness and Simplicity: The algorithm should route packets to the correct destination without excessive computational overhead.
• Robustness: It must perform correctly in the face of hardware failures, topology changes, and high traffic loads.
• Stability: The algorithm should converge on a solution quickly and not bounce between different routes continuously.
• Fairness and Optimality: It should optimize a specific metric (like delay, hop count, or bandwidth) while ensuring no single node is unfairly starved of network resources.

Unicast Routing Protocols dictate how routers communicate to share network topology information and calculate the best path to a single destination (one-to-one communication).

They are categorized based on their scope of operation (Autonomous Systems - AS):

1. Intra-domain Routing (Interior Gateway Protocols - IGP): Used for routing within a single Autonomous System (e.g., a corporate network or university campus).
   • Examples: RIP (Routing Information Protocol) based on Distance Vector, and OSPF (Open Shortest Path First) based on Link State.
2. Inter-domain Routing (Exterior Gateway Protocols - EGP): Used for routing between different Autonomous Systems.
   • Example: BGP (Border Gateway Protocol) based on Path Vector routing. BGP is the protocol that runs the global Internet.

Dijkstra's Algorithm is a link-state routing algorithm used to find the shortest path from a single source node to all other nodes in a graph with non-negative edge weights.

Algorithm Steps:

1. Initialization: Set the distance to the source node to $0$ (). Set the distance to all other nodes to . Create a set containing all nodes.
2. Selection: Find the node in with the smallest tentative distance.
3. Update: For each neighbor of that is still in , calculate the potential new distance: .
4. Relaxation: If , update and set the predecessor of to .
5. Finalize: Remove from .
6. Repeat: Repeat steps 2-5 until is empty.
   The result is a shortest-path tree from the source node to all reachable nodes.

In Distance Vector (DV) Routing, each router maintains a table (vector) giving the best known distance to each destination and which link to use to get there.

Principles:

• Knowledge of whole network: Each router shares its knowledge of the entire network with its neighbors.
• Routing to neighbors only: Information is sent only to directly connected neighbors.
• Periodic updates: Routers exchange this information periodically (e.g., every 30 seconds).
• Algorithm: It utilizes the Bellman-Ford equation. When router receives a distance vector from neighbor , it calculates the cost to each destination via . If the new cost () is less than the current known cost, updates its routing table.

Protocol: The Routing Information Protocol (RIP) is the most common protocol utilizing Distance Vector routing.

The Count-to-Infinity problem is a routing loop issue in Distance Vector networks that occurs when a link breaks. Routers slowly, step-by-step, increment the cost to a disconnected network towards infinity, bouncing incorrect information back and forth because they don't know the global topology.

Mitigation Techniques:

• Define Infinity: Set a maximum hop count (e.g., 16 in RIP). Once the metric reaches 16, the destination is considered unreachable, stopping the loop.
• Split Horizon: A router never sends routing information back in the direction from which it was received. If A routes to C via B, A will not tell B that it has a route to C.
• Poison Reverse: A variation of Split Horizon where A tells B that its route to C has a cost of infinity, ensuring B never tries to use A to reach C.
• Triggered Updates: Send updates immediately when a topology change occurs, rather than waiting for the periodic timer.

In Link State (LS) Routing, every router possesses complete information about the network topology.

Working Concept:

1. Discovery: Each router discovers its neighbors and the cost (delay/bandwidth) of reaching them.
2. LSA Creation: Each router creates a Link State Packet (LSP) containing its identity, its neighbors, and the link costs.
3. Flooding: LSPs are flooded to all routers in the network (not just neighbors).
4. Dijkstra's Algorithm: Once a router has all LSPs, it builds a complete topological map of the network and runs Dijkstra's shortest path algorithm to compute the best routes to all destinations.

Differences from Distance Vector (DV):

• LS sends information about its neighbors to the whole network. DV sends information about the whole network to its neighbors.
• LS uses Dijkstra's algorithm; DV uses Bellman-Ford.
• LS converges much faster and is immune to the count-to-infinity problem, but requires more memory and CPU power.

Flooding is the mechanism used in Link State Routing to distribute Link State Packets (LSPs) to every router in the routing domain. When a router receives an LSP on one interface, it forwards a copy out of all other interfaces.

Preventing Infinite Loops:
If left unchecked, flooding would cause LSPs to circulate endlessly. This is prevented by:

• Sequence Numbers: Each LSP includes a sequence number. When a router creates a new LSP, it increments the sequence number. If a router receives an LSP with a sequence number it has already seen (or a lower one), it discards it.
• Age Field / Time-to-Live (TTL): Each LSP has an age field that decreases over time or per hop. When the age reaches zero, the LSP is discarded.
• Acknowledgments: Routers acknowledge the receipt of LSPs to ensure reliable delivery without requiring endless retransmissions.

OSPF is a widely used interior gateway protocol based on Link State routing.

Advantages:

• Fast Convergence: OSPF reacts quickly to topology changes because updates are flooded immediately.
• Loop-Free: Since every router has a complete topology map and runs Dijkstra's algorithm, routing loops are completely avoided.
• Hierarchical Design: OSPF supports splitting a large network into smaller 'Areas', reducing the size of the routing table and limiting the scope of LSA flooding.
• Metric: Uses cost (usually derived from bandwidth), allowing for better path selection than simple hop-count.

Disadvantages:

• Resource Intensive: Requires more memory (to store the topology database) and CPU processing power (to run Dijkstra's algorithm) than Distance Vector protocols.
• Complexity: Configuration and troubleshooting are significantly more complex than RIP.

Stateless Address Autoconfiguration (SLAAC) allows a device to obtain an IPv6 address without the need for a DHCP server.

Mechanism:

1. Link-Local Address Generation: The host generates a link-local address by combining the prefix fe80::/10 with its interface identifier (often derived from the MAC address using EUI-64).
2. Duplicate Address Detection (DAD): The host sends a Neighbor Solicitation message to ensure no other device on the link is using this address.
3. Router Solicitation (RS): The host sends a multicast RS message to discover local routers.
4. Router Advertisement (RA): Local routers respond with an RA message containing the network prefix (e.g., a /64 global prefix) and default gateway information.
5. Global Address Generation: The host combines the received network prefix with its interface identifier to configure its globally routable IPv6 address.

The Bellman-Ford algorithm computes shortest paths from a single source vertex to all other vertices in a weighted digraph.

Utilization in Distance Vector Routing:
In routing, the equation is expressed as:

Where:

• is the least cost from node to .
• is the link cost from to its direct neighbor .
• is neighbor 's estimated least cost to .

Each router maintains its own distance vector and receives vectors from its neighbors. Upon receiving an update from neighbor , router applies the Bellman-Ford equation. If routing via provides a shorter path to destination than the currently known path, router updates its routing table with the new lowest cost and sets as the next hop.

Here is a comparison of the two primary intra-domain routing algorithms:

• Message Complexity:
  • Distance Vector (DV): Messages are exchanged only between adjacent neighbors. However, they contain the entire routing table. Traffic is relatively low but increases with network size.
  • Link State (LS): LSPs are flooded to the entire network. Messages are small (only neighbor info) but high in number due to flooding. Higher message complexity during topology changes.
• Convergence Speed:
  • DV: Slow convergence. Susceptible to routing loops and the count-to-infinity problem, requiring time-consuming mitigation.
  • LS: Fast convergence. Updates are flooded immediately, and routers independently calculate paths quickly without loops.
• Robustness:
  • DV: If a router advertises an incorrect path cost, this error propagates through the network, potentially causing widespread routing anomalies.
  • LS: More robust. An incorrect LSP only affects the links of the router that generated it. Each node computes its own table based on raw topology data, localizing errors.