Object:

route entries in the kernel routing tables keep information about paths to other networked nodes.

Each route entry has a key consisting of a prefix (i.e. a pair containing a network address and the length of its mask) and, optionally, the TOS value. An IP packet matches the route if the highest bits of its destination address are equal to the route prefix at least up to the prefix length and if the TOS of the route is zero or equal to the TOS of the packet.

If several routes match the packet, the following pruning rules are used to select the best one (see [3]):

1. The longest matching prefix is selected. All shorter ones are dropped.

2. If the TOS of some route with the longest prefix is equal to the TOS of the packet, the routes with different TOS are dropped.

   If no exact TOS match was found and routes with TOS=0 exist, the rest of routes are pruned.

   Otherwise, the route lookup fails.

3. If several routes remain after the previous steps, then the routes with the best preference values are selected.

4. If we still have several routes, then the first of them is selected.

   1cm NB. Note the ambiguity of the last step. Unfortunately, Linux historically allows such a bizarre situation. The sense of the word ``first'' depends on the order of route additions and it is practically impossible to maintain a bundle of such routes in this order.

   For simplicity we will limit ourselves to the case where such a situation is impossible and routes are uniquely identified by the triplet {prefix, tos, preference}. Actually, it is impossible to create non-unique routes with ip commands described in this section.

   One useful exception to this rule is the default route on non-forwarding hosts. It is ``officially'' allowed to have several fallback routes when several routers are present on directly connected networks. In this case, Linux-2.2 makes ``dead gateway detection'' [4] controlled by neighbour unreachability detection and by advice from transport protocols to select a working router, so the order of the routes is not essential. However, in this case, fiddling with default routes manually is not recommended. Use the Router Discovery protocol (see Appendix D, p.) instead. Actually, Linux-2.2 IPv6 does not give user level applications any access to default routes.

Certainly, the steps above are not performed exactly in this sequence. Instead, the routing table in the kernel is kept in some data structure to achieve the final result with minimal cost. However, not depending on a particular routing algorithm implemented in the kernel, we can summarize the statements above as: a route is identified by the triplet {prefix, tos, preference}. This key lets us locate the route in the routing table.