routing destinations

There are 3 classes of destinations:

  1. locally hosted IPs - IPs bound to any network device including loopback devices
  2. locally connected computers (directly reachable IPs) - reachable on the directly connected link layer medium
  3. everywhere else - reachable through a router (gateway) which is reachable on a directly connected link layer medium

policy based routing

  • classic routing algorithms make routing decisions based only on the destination address
  • since v2.2, linux supports policy routing, i.e. packets are routed depending not only on the destination address, but also other packet fields like source address, tos, etc.
  • routes are selected based on a set of rules configured in the routing policy database (RPDB)
  • each rule has a selector and an action predicate
  • there used to be a routing cache, but it was removed in v3.6 due to non-deterministic performance
  • route selection algorithm pseudo-code:
    for rule in rpdb:
        # rpdbLookupKey could be one of:
        # - sourceAddress
        # - destAddress
        # - incomingInterface
        # - tos
        # - fwmark
        if packet.rpdbLookupKey in rule:
            routeTable = rule.lookupTable
            # in the simplest case the destination address would be
            # looked up in the routing table using longest prefix match
            if packet.routeLookupKey in routeTable:
                route = routeTable[packet.routeLookupKey]
    
  • list the RPDB
    $ ip rule show
    0:	from all lookup local 
    32766:	from all lookup main 
    32767:	from all lookup default 
    
  • The above is the default RPDB consisting of 3 rules:
    1. priority 0 (highest)
      • selector: match anything
      • action: lookup routing table local, which is a special table containing routes for local and broadcast addresses
    2. priority 32766
      • selector: match anything
      • action: lookup routing table main, which is where all normal routes are inserted
    3. priority 32767
      • selector: match anything
      • action: lookup routing table default

routing tables

Apart from the local (id 255), main (id 254) and default (id 253) tables, the kernel supports tables identified by a number in the range 1 to 232-1. There are different route types: unicast, broadcast, local, nat, etc.

local routing table

  • 3 entries are added to the local table for each interface that is brought up:
    1. route type local for the IP assigned to this interface
    2. route type broadcast for the network IP
    3. route type broadcast for the broadcast IP
  • e.g.
    $ ip route show dev enp2s0 table local
    broadcast 192.168.1.0 proto kernel scope link src 192.168.1.117 
    local 192.168.1.117 proto kernel scope host src 192.168.1.117 
    broadcast 192.168.1.255 proto kernel scope link src 192.168.1.117 
    

references