Unit 4: Routing and IP Header - Subjective Questions

A routing algorithm is a procedure used by routers to determine the best path for forwarding packets from a source network to a destination network. The selected routes are stored in a routing or forwarding table.

Major properties of a good routing algorithm:

• Correctness: It should select valid, loop-free routes.
• Optimality: It should choose the best route according to a metric such as hop count, delay, bandwidth, or cost.
• Simplicity: It should require reasonable processing and memory.
• Robustness: It should continue operating despite link or router failures.
• Stability: It should converge to consistent routes without frequent oscillations.
• Fairness: It should not unfairly deny network resources to particular users.
• Scalability: It should work efficiently as the network grows.

Classifications:

1. Static and dynamic routing

   • Static routes are manually configured and do not automatically adapt to failures.
   • Dynamic routes are updated automatically when the topology changes.

2. Adaptive and non-adaptive routing

   • Adaptive algorithms use current topology or traffic information.
   • Non-adaptive algorithms use predetermined routes.

3. Centralized and distributed routing

   • A centralized algorithm uses a central controller with global information.
   • A distributed algorithm allows routers to calculate routes through information exchange.

4. Intra-domain and inter-domain routing

   • Intra-domain routing operates within one autonomous system.
   • Inter-domain routing operates between autonomous systems.

Dijkstra's algorithm finds the minimum-cost path from one source node to every other node in a graph with non-negative link costs.

Procedure:

1. Assign distance 0 to the source and infinity to all other nodes.
2. Select the unvisited node with the smallest tentative distance.
3. Mark it as permanent.
4. Relax each adjacent edge using
   
   where is the current distance to node and is the link cost.
5. Repeat until all nodes become permanent.

Calculation from A:

• Initially: , , , , .
• Select C with cost 2:
  • Cost to B through C is , so update .
  • Cost to D through C is .
  • Cost to E through C is .
• Select B with cost 3:
  • Cost to D through B is , so update .
• Select D with cost 8:
  • Cost to E through D is , so update .
• Select E with cost 10.

Final shortest paths:

The resulting shortest-path tree is formed by the links AC, CB, BD, and DE.

The optimality principle states that if router J lies on the optimal path from router I to router K, then the optimal path from J to K must be part of the same path.

For example, if the best route is

then

must also be the best route from J to K. Otherwise, replacing it with a better route would produce a better route from I to K, contradicting the original assumption.

A sink tree is the collection of optimal routes from all source routers to one destination router, called the sink. Its important characteristics are:

• The destination is the root or sink of the tree.
• Each router has one selected outgoing route toward the destination.
• The tree contains no loops.
• Every router has a path to the destination.
• Different routing metrics may produce different sink trees.

The sink-tree concept is useful because routing algorithms attempt to discover and maintain these loop-free shortest paths. In practice, equal-cost paths may exist, so the complete structure may be a directed acyclic graph rather than a single unique tree.

In distance vector routing, every router maintains a vector containing its estimated distance to each destination. A router periodically sends this vector to its directly connected neighbors.

The Bellman-Ford relation used by router is

where:

• is the estimated distance from to destination .
• is the set of neighbors of .
• is the direct cost from to neighbor .
• is neighbor 's advertised distance to .

Routers initially know only themselves and directly connected neighbors. After repeated exchanges, they converge to the following shortest distances:

• From A: B costs 1, C costs , and D costs .
• From B: A costs 1, C costs 2, and D costs .
• From C: B costs 2, A costs , and D costs 1.
• From D: C costs 1, B costs , and A costs .

Final distance vectors:

Distance vector routing is distributed and simple, but it may converge slowly after a failure.

The count-to-infinity problem occurs when distance vector routers respond slowly to a failed route. After a failure, neighboring routers may incorrectly believe that each other still has a valid path to the destination.

For example, suppose A reaches network X through B. If B's direct route to X fails, A may still advertise a route to X based on its earlier information from B. Router B can then believe that X is reachable through A. The routers repeatedly increase the metric until it reaches a value treated as infinity.

This behavior is often described as good news travels fast, but bad news travels slowly.

Reduction techniques:

• Small infinity value: A protocol defines a limited maximum metric. RIP, for example, uses 16 as infinity.
• Split horizon: A route learned through an interface is not advertised back through that interface.
• Poison reverse: A route is advertised back to its source neighbor with an infinite metric.
• Route poisoning: When a route fails, the router immediately advertises it with an infinite metric.
• Triggered updates: A router sends an update immediately after a significant change instead of waiting for the periodic timer.
• Hold-down timers: Routers temporarily reject suspicious updates about a failed route.

These mechanisms reduce the likelihood and duration of loops, but split horizon and poison reverse do not eliminate every loop involving three or more routers.

In link state routing, each router discovers the local network topology and distributes that information to every router in the routing domain. Each router then builds an identical topology database and independently calculates shortest paths.

Operational steps:

1. Neighbor discovery:

   • A router sends hello messages on its interfaces.
   • It identifies directly connected routers and forms adjacencies.

2. Link-cost measurement:

   • The router determines a cost for each link.
   • Cost may be based on bandwidth, delay, administrative configuration, or another metric.

3. Link-state packet generation:

   • A link-state packet contains the originating router's identity, neighbors, link costs, sequence number, and age.

4. Reliable flooding:

   • The packet is sent to all adjacent routers.
   • Each receiving router stores a newer packet and forwards it on other interfaces.
   • Sequence numbers prevent old information from replacing new information.
   • Age fields remove obsolete information.

5. Topology database construction:

   • All routers build a link-state database representing the network graph.

6. Shortest-path calculation:

   • Each router runs Dijkstra's algorithm with itself as the source.
   • The resulting shortest-path tree is used to construct the forwarding table.

Link state routing generally converges rapidly and is used by protocols such as OSPF and IS-IS, although it requires more memory, processing, and flooding control than basic distance vector routing.

Summary:

• Distance vector routing is comparatively simple because routers depend on information supplied by neighbors.
• Link state routing has a higher initial complexity but provides a global view of the topology and normally responds faster to failures.
• Both methods aim to produce a stable forwarding table, but they differ in the information exchanged and the method used to calculate routes.

Hierarchical routing divides a large network into smaller routing regions, areas, or autonomous systems. Routers maintain detailed information about their own region while using summarized information for remote regions.

Need for hierarchical routing:

• A flat routing system requires every router to store routes for all networks.
• Routing tables and topology databases become too large as the network grows.
• Frequent updates consume bandwidth and processing resources.
• Route calculation becomes slower.
• Administrative control is difficult across independently managed networks.

Operation:

• Routers inside an area maintain detailed intra-area routes.
• Border routers connect areas and advertise summarized prefixes.
• An autonomous system groups networks under one administrative authority.
• Intra-domain protocols, such as OSPF, calculate routes within an autonomous system.
• Inter-domain protocols, such as BGP, exchange reachability information between autonomous systems.

Advantages:

• Smaller routing tables
• Reduced update traffic
• Faster route computation
• Better fault isolation
• Easier administration
• Support for route aggregation

A possible disadvantage is that summarization hides detailed topology information, so the chosen inter-area path may not always be the absolute shortest path.

An IPv4 packet begins with a header whose minimum size is 20 bytes and maximum size is 60 bytes.

IPv4 header fields:

• Version, 4 bits: Contains 4 for IPv4.
• Internet Header Length, 4 bits: Gives header size in 32-bit words. Its minimum value is 5.
• Differentiated Services and ECN, 8 bits: Supports traffic classification, quality of service, and congestion notification.
• Total Length, 16 bits: Gives the complete packet length, including header and data. Its maximum value is bytes.
• Identification, 16 bits: Identifies fragments belonging to the same original datagram.
• Flags, 3 bits: Includes the Don't Fragment and More Fragments controls.
• Fragment Offset, 13 bits: Specifies the fragment's data position in units of 8 bytes.
• Time to Live, 8 bits: Limits packet lifetime and prevents indefinite routing loops.
• Protocol, 8 bits: Identifies the upper-layer protocol, such as ICMP, TCP, or UDP.
• Header Checksum, 16 bits: Detects errors in the IPv4 header.
• Source Address, 32 bits: Identifies the sending IPv4 interface.
• Destination Address, 32 bits: Identifies the destination IPv4 interface.
• Options: Carries optional control information.
• Padding: Extends the header to a multiple of 32 bits.

IPv4 fragmentation fields and the variable-length options contribute to processing complexity in routers.

The original payload size is

Each fragment needs a 20-byte IPv4 header. Therefore, the maximum payload allowed by the MTU is

Except for the last fragment, payload sizes must be multiples of 8 because the fragment offset is measured in 8-byte units. Here, 1480 is divisible by 8:

The payload is divided as follows:

• First fragment payload: 1480 bytes
• Second fragment payload: 1480 bytes
• Remaining payload: bytes

Fragment details:

The second offset is

and the third offset is

All fragments carry the same Identification value. An MF value of 1 indicates that more fragments follow, while MF = 0 identifies the last fragment. Reassembly normally occurs only at the destination.

Time to Live:

• TTL is an 8-bit field that prevents a datagram from circulating indefinitely because of a routing loop.
• Every forwarding router decreases TTL by at least 1.
• If TTL becomes 0, the router discards the datagram.
• The router normally sends an ICMP Time Exceeded message to the source.
• The traceroute utility uses this behavior to identify routers along a path.

Protocol:

• The Protocol field identifies the next-layer protocol carried in the payload.
• Common values include ICMP = 1, TCP = 6, and UDP = 17.
• The destination host uses it to deliver the payload to the correct protocol handler.

Header Checksum:

• It checks only the IPv4 header, not the payload.
• The sender sets the checksum field to zero, adds the 16-bit header words using one's-complement arithmetic, and stores the one's complement of the sum.
• A receiver repeats the calculation to detect header corruption.

Because a router changes TTL, it must also update or recompute the header checksum before forwarding the packet. IPv6 removes the header checksum to reduce per-hop processing.

The IPv6 base header has a fixed size of 40 bytes, which simplifies processing compared with the variable-length IPv4 header.

IPv6 base-header fields:

• Version, 4 bits: Contains the value 6.
• Traffic Class, 8 bits: Supports differentiated service and congestion notification.
• Flow Label, 20 bits: Identifies packets belonging to the same flow so that they may receive consistent handling.
• Payload Length, 16 bits: Gives the number of bytes after the 40-byte base header, including extension headers.
• Next Header, 8 bits: Identifies the next extension header or upper-layer protocol such as TCP, UDP, or ICMPv6.
• Hop Limit, 8 bits: Performs the function of IPv4 TTL. Each router decreases it, and the packet is discarded when it reaches zero.
• Source Address, 128 bits: Identifies the sending IPv6 interface.
• Destination Address, 128 bits: Identifies the destination interface or, in some routing cases, an intermediate destination.

IPv6 moves optional information into extension headers. It also removes the base-header checksum and router fragmentation fields, allowing routers to forward packets more efficiently.

IPv6 efficiency improvements:

• A fixed header size allows predictable parsing.
• The removal of the header checksum avoids checksum updates at every hop.
• Routers do not fragment packets.
• Optional information does not enlarge the base header unnecessarily.
• The Next Header chain provides flexible protocol extension.
• The Flow Label can assist special handling of packet flows.

Although the IPv6 base header is larger because of 128-bit addresses, its simpler structure reduces router processing complexity.

IPv6 extension headers carry optional network-layer information outside the fixed 40-byte base header. The Next Header field connects the IPv6 header, extension headers, and upper-layer protocol as a chain.

Important extension headers:

• Hop-by-Hop Options: Contains information that may need examination by every node along the path. When present, it appears immediately after the base header.
• Routing Header: Specifies routing-related information or a list of intermediate nodes.
• Fragment Header: Carries fragmentation information. Only the source creates IPv6 fragments.
• Destination Options: Contains options examined only by the destination or by destinations named in a routing header.
• Authentication Header: Provides data-origin authentication and integrity protection in IPsec.
• Encapsulating Security Payload: Provides confidentiality and can also provide integrity and authentication.

A commonly recommended logical order is:

1. IPv6 base header
2. Hop-by-Hop Options
3. Destination Options for intermediate destinations
4. Routing Header
5. Fragment Header
6. Authentication Header
7. Encapsulating Security Payload
8. Destination Options for the final destination
9. Upper-layer header

Extension headers make IPv6 flexible while keeping the base header simple. Intermediate routers normally process only the fields required for forwarding, although the exact treatment of some options depends on their definitions.

An IPv6 address contains 128 bits and is written as eight groups of four hexadecimal digits separated by colons. Each group represents 16 bits.

Compression rules:

• Leading zeros in a group may be omitted. For example, 0042 becomes 42.
• One consecutive sequence of all-zero groups may be replaced by ::.
• :: can appear only once in an address because otherwise the number of omitted groups would be ambiguous.
• When more than one zero sequence has the same length, standard canonical notation normally compresses the leftmost sequence.

Expansion:

The address 2001:db8::8a2e:370:7334 contains five explicitly written groups. Therefore, :: represents three groups of zeros.

Its expanded form is:

2001:0db8:0000:0000:8a2e:0370:7334

This expression has only seven groups, so the correct count must be checked carefully: before :: there are two groups and after it there are three groups. Thus :: represents three groups, producing eight groups:

2001:0db8:0000:0000:0000:8a2e:0370:7334

Compression:

2001:0db8:0000:0000:0000:ff00:0042:8329

becomes:

2001:db8::ff00:42:8329

The prefix length is written using CIDR notation, such as 2001:db8:1::/64.

IPv6 supports unicast, multicast, and anycast addressing. It does not use broadcast addressing.

1. Unicast: A packet is delivered to one interface.

• Global unicast: Publicly routable addresses, generally from 2000::/3.
• Link-local: Addresses from fe80::/10. They are automatically available on a link and are not forwarded by routers.
• Unique local: Addresses from fc00::/7, commonly using fd00::/8 for locally assigned prefixes. They are intended for private communication and are not normally routed on the public Internet.
• Loopback: ::1/128, used by a host to refer to itself.
• Unspecified: ::/128, used when a source address has not yet been assigned.

2. Multicast: A packet is delivered to all interfaces that have joined a multicast group. Multicast addresses begin with ff00::/8. Their scope field identifies whether the group is interface-local, link-local, organization-local, global, or another defined scope.

Examples include:

• ff02::1: all nodes on the local link
• ff02::2: all routers on the local link

3. Anycast: The same unicast-format address is assigned to multiple interfaces, usually on different nodes. Routing delivers the packet to the nearest member according to the routing metric.

IPv6 replaces IPv4 broadcast functions with multicast, reducing unnecessary processing by nodes not interested in the traffic.

The organization has a /48 prefix and wants to create /64 subnets. The number of bits available for subnetting is

Therefore, the number of /64 subnets is

Address structure:

• First 48 bits: global routing prefix assigned to the organization
• Next 16 bits: subnet identifier
• Last 64 bits: interface identifier

A conceptual structure is:

Example /64 subnet prefixes:

• 2001:db8:1200:1::/64
• 2001:db8:1200:2::/64
• 2001:db8:1200:abcd::/64

The subnet identifier ranges from hexadecimal 0000 through ffff. Each /64 subnet theoretically contains

interface addresses.

The /64 boundary is standard for most IPv6 LANs and is important for mechanisms such as Stateless Address Autoconfiguration. The large interface-identifier space is designed for address-management efficiency and uniqueness, not for placing active devices on one LAN.

Network Address Translation, or NAT, is a mechanism in which a router or firewall modifies IP address information as packets move between address domains, commonly between a private network and the public Internet.

Suppose an internal host 192.168.1.10 communicates with public server 203.0.113.20, and the NAT router uses public address 198.51.100.5.

Outgoing packet:

1. The host sends a packet with source 192.168.1.10 and destination 203.0.113.20.
2. The NAT router replaces the private source address with 198.51.100.5.
3. It records the translation in a NAT table.
4. Because the IPv4 header has changed, the router updates the IPv4 header checksum.
5. The translated packet is forwarded to the Internet.

Incoming reply:

1. The reply arrives with source 203.0.113.20 and destination 198.51.100.5.
2. The NAT router consults its translation table.
3. It replaces the destination address with 192.168.1.10.
4. It updates the necessary checksums.
5. It forwards the packet to the internal host.

Basic NAT may provide a one-to-one mapping between private and public addresses. In practice, many networks use port translation so that several internal devices can share one public IPv4 address.

Static NAT:

• Creates a permanent one-to-one mapping between a private and a public address.
• Useful when an internal server must be consistently reachable from outside.
• Requires one public address for each mapping.

Dynamic NAT:

• Maps private addresses to addresses selected from a public address pool.
• The mapping is created when communication begins and may later expire.
• The number of simultaneous translated hosts is limited by the pool size.

Port Address Translation:

• Also called PAT, NAT overload, or many-to-one NAT.
• Maps many private address-and-port pairs to one public address using different translated port numbers.

For example:

When replies arrive, the destination port identifies the correct translation-table entry. PAT then restores the corresponding private destination address and port.

Because TCP and UDP checksums include a pseudo-header containing IP addresses and also cover port fields, NAT must update transport checksums when it changes these values. PAT conserves public IPv4 addresses and is the most common form of NAT in homes and small organizations.

Advantages of NAT:

• Conserves globally unique IPv4 addresses.
• Allows many private hosts to share one or a small number of public addresses.
• Permits organizations to use private address ranges internally.
• Reduces the need to renumber internal devices when changing Internet service providers.
• Hides internal addressing details from ordinary external traffic.
• Can enforce a policy in which unsolicited inbound connections require explicit mappings.

Limitations:

• Breaks the end-to-end addressing model because source or destination addresses are modified in transit.
• Requires translation state, especially for PAT.
• State may be lost when a NAT device restarts or traffic follows an asymmetric path.
• Inbound connections require port forwarding, static mappings, or NAT-traversal techniques.
• Protocols that carry IP addresses or ports inside application data may fail unless an application-level gateway modifies the payload.
• Checksum recalculation and state tracking add processing overhead.
• NAT can complicate peer-to-peer communication, VoIP, online gaming, IPsec, and network troubleshooting.
• NAT is not equivalent to a complete firewall and should not be treated as a substitute for security policy.

Traversal techniques include STUN, TURN, ICE, port forwarding, and NAT-aware application gateways. IPv6 greatly expands the address space and reduces the need for address-conservation NAT, although firewalls and other security controls remain necessary.