rules in the routing policy database control
the route selection algorithm.
Classic routing algorithms used in the Internet make routing decisions based only on the destination address of packets (and in theory, but not in practice, on the TOS field). The seminal review of classic routing algorithms and their modifications can be found in [3].
In some circumstances we want to route packets differently depending not only on destination addresses, but also on other packet fields: source address, IP protocol, transport protocol ports or even packet payload. This task is called ``policy routing''.
1cm NB.
``policy routing'' 
``routing policy''.
``policy routing'' 
``cunning routing''.
``routing policy'' ``routing tactics'' or ``routing plan''.
To solve this task, the conventional destination based routing table, ordered according to the longest match rule, is replaced with a ``routing policy database'' (or RPDB), which selects routes by executing some set of rules. The rules may have lots of keys of different natures and therefore they have no natural ordering, but one imposed by the administrator. Linux-2.2 RPDB is a linear list of rules ordered by numeric priority value. RPDB explicitly allows matching a few packet fields:
Matching IP protocols and transport ports is also possible,
indirectly, via ipchains, by exploiting their ability
to mark some classes of packets with fwmark. Therefore,
fwmark is also included in the set of keys checked by rules.
Each policy routing rule consists of a selector and an action predicate. The RPDB is scanned in the order of increasing priority. The selector of each rule is applied to {source address, destination address, incoming interface, tos, fwmark} and, if the selector matches the packet, the action is performed. The action predicate may return with success. In this case, it will either give a route or failure indication and the RPDB lookup is terminated. Otherwise, the RPDB program continues on the next rule.
What is the action, semantically? The natural action is to select the
nexthop and the output device. This is what
Cisco IOS [5] does. Let us call it ``match & set''.
The Linux-2.2 approach is more flexible. The action includes
lookups in destination-based routing tables and selecting
a route from these tables according to the classic longest match algorithm.
The ``match & set'' approach is the simplest case of the Linux one. It is realized
when a second level routing table contains a single default route.
Recall that Linux-2.2 supports multiple tables
managed with the ip route command, described in the previous section.
At startup time the kernel configures the default RPDB consisting of three rules:
local (ID 255).
The local table is a special routing table containing
high priority control routes for local and broadcast addresses.
main (ID 254).
The main table is the normal routing table containing all non-policy
routes. This rule may be deleted and/or overridden with other
ones by the administrator.
default (ID 253).
The default table is empty. It is reserved for some
post-processing if no previous default rules selected the packet.
This rule may also be deleted.
Do not confuse routing tables with rules: rules point to routing tables, several rules may refer to one routing table and some routing tables may have no rules pointing to them. If the administrator deletes all the rules referring to a table, the table is not used, but it still exists and will disappear only after all the routes contained in it are deleted.