Exploring Route Selection on a PC: A Research Hypothesis

Verbal Kint

• 3 min read
Exploring Route Selection on a PC: A Research Hypothesis
Introduction:

Recently, I became intrigued by the low-level mechanisms that govern route selection on a PC. I hypothesised that the host machine calculates a bitwise AND operation between its IP address and subnet mask to determine the network address. Similarly, when forwarding a packet, I suspected the PC performs the same AND operation with the destination IP address. If the results of both operations (i.e., the network addresses) match, the host would initiate an ARP request to obtain the destination’s MAC address and forward the packet accordingly. Otherwise, it would default to using the MAC address of its default gateway.

With this hypothesis in mind, I set out to research and either validate or disprove this theory.

The general consensus seems to be that a PC will AND both its IP and The destination IP against the subnet mask, then compare the result. However i found another compelling process that a PC might use. The XOR & AND

Technical Analysis

AND Operation:

The AND operation takes two bits and returns 1 only if both bits are 1. If either bit is 0, it returns 0. Here’s how it functions on a pair of bits:

  • 0 AND 0 = 0
  • 1 AND 0 = 0
  • 0 AND 1 = 0
  • 1 AND 1 = 1

XOR:

The XOR operation takes two bits and returns 1 if the bits are different, and 0 if they are the same. Here's how it operates on a pair of bits:

  • 0 XOR 0 = 0
  • 1 XOR 0 = 1
  • 0 XOR 1 = 1
  • 1 XOR 1 = 0

The XOR is used to compare the bits of the source IP and destination IP. If bits are the same = 0. If bits are different = 1.

A host determines whether or not a destination host is in the same network by running an XOR operation between its own address and the destination address. The host will then run an AND operation on the result of the XOR operation and its own subnet mask.

If the result of the AND operation is all zeros, then the destination host is in the same network, in which case the host will forward the packet directly to the destination.

Below are examples:

Example 1: Both hosts are in the same network

Source: 192.168.1.10
Destination: 192.168.1.99
Subnet Mask: 255.255.255.0

Stage 1: XOR Operation (of source and destination)

Source: 192.168.1.10:       1100 0000.1010 1000.0000 0001.0000 1010 
Destination: 192.168.1.99 : 1100 0000.1010 1000.0000 0001.0110 0011
XOR result:                 0000 0000.0000 0000.0000 0000.0110 1001

Stage 2: AND Operation (of XOR result and subnet mask)

Subnet Mask: /24   11111111. 11111111. 11111111. 00000000
XOR Result:        00000000. 00000000. 00000000. 01101001
AND Result:        00000000. 00000000. 00000000. 00000000

The result of the AND is all zeros, which means the destination host is in the same network, in which case the host will forward the packet directly to the destination.

Example 2: Hosts are in different networks

Source: 192.168.1.10/24
Destination: 192.168.2.50/24
Subnet Mask: 255.255.255.0

Stage 1: XOR Operation (of source and destination)

Source: 192.168.1.10:     1100 0000.1010 1000.0000 0001.0000 1010
Destination: 192.168.2.50 1100 0000.1010 1000.0000 0010.0011 0010
XOR result:               0000 0000.0000 0000.0000 0011.0011 1000

Stage 2:AND Operation (of XOR result and subnet mask)

Subnet Mask (/24): 1111 1111.1111 1111.1111 1111.0000 0000  
XOR Result:        0000 0000.0000 0000.0000 0011.0011 1000  
AND Result:        0000 0000.0000 0000.0000 0011.0000 0000

Ostensibly, XOR outputs which bits are the same between host and destination. The AND operation with the subnet mask then shows which bits SHOULD be the same for the destination to be in the same network. As you can see, the initial XOR operation is a nifty little trick, because it essentially performs 2 simultaneous checks.

Ultimately, my hypothesis about the AND operations is probably how modern PC's do it, but i think the XOR & AND is still an elegant approach