Packet Routing
Brett Lee
====================================================================


How does the OS determine where to route the packet?

Check each entry in the routing table, starting with the local subnets
then going to the gateways.

Begin:  

I.  Pull the destination IP from the IP header.

II. Check the local subnets in the routing table

  a. For the first subnet, get the network bits as indicated by the 
     subnet mask.  

****
* Here's where implemenation variations *may* occur.
* Need to consult text (Stevens) to verify (cause I'm only guessing).
*
* Option 1
  b. Perform an exclusive bitwise OR (XOR) between the masked amount of
        subnet bits in the attached subnet and the same amount of bits in
        the destination IP.
     If the XOR resutls in all ZEROs, check the ARP cache and, if
        necessary, ARP for the MAC address of the host, and if successful,
        deliver the packet to that MAC.
     Example:
       subnet IP = 192.168.0.2/24
       destination IP = 192.168.0.3
       192.168.0.2/24 ^ 192.168.0.3 =
       11000000.10101000.00000000 ^ 11000000.10101000.00000000 =
       00000000.00000000.00000000 ( ZEROs ! )
     If not, continue to next attached subnet
*
* Option 2
  b. Perform a bitwise AND between the masked amount of subnet bits in the
        attached subnet and the same amount of bits in the destination IP.
        the same number of bits in the destination IP, perform an
     If the result equals "either" operand, check the ARP cache and, if
        necessary, ARP for the MAC address of the host, and if successful,
        deliver the packet to that MAC.
     Example:
       subnet IP = 192.168.0.2/24
       destination IP = 192.168.0.3
       192.168.0.2/24 & 192.168.0.3 =
       11000000.10101000.00000000 ^ 11000000.10101000.00000000 =
       11000000.10101000.00000000 ( MATCH ! )
     If not, continue to next attached subnet
 *
 * Option 3
  d. Review Stevens book.  There is probably a better way.
****

If none of the attached subnets match, check the gateways.  This is more
  complex, as multiple routes may exist to the same subnet, possibly with
  different hop counts / distance vectors.  Of course there could also
  be a multipath daemon running, too.  At any rate, if a suitable route is
  found, the MAC address of the gateway is found and the packet is sent
  happly (we hope) along its way.  As with checking the attached subnets,
  the netmask of the destination in the routing table is used to determine
  the number of bits in the destination to check.  This allows for
  CIDR and supernetting multiple similarly prefixed subnets together
  into one route.
If no gateways match (or exist), the packet is sent to the default route.
If the default route is unreachable, an ICMP "Destination Unreachable" 
  message is sent back to the source IP address.
If no default route exists, the network may be misconfigured and an ICMP
  message with a different unreachable code is sent back to the source IP.
Of course, we only briefly touch on ICMP, which could provide some
  other helpful information on delivering the darn packet.