Connected: An Internet Encyclopedia
11.1. Routing table lookup

Up: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1583
Up: 11. The Routing Table Structure
Prev: 11. The Routing Table Structure
Next: 11.2. Sample routing table, without areas

11.1. Routing table lookup

11.1. Routing table lookup

When an IP data packet is received, an OSPF router finds the routing table entry that best matches the packet's destination. This routing table entry then provides the outgoing interface and next hop router to use in forwarding the packet. This section describes the process of finding the best matching routing table entry. The process consists of a number of steps, wherein the collection of routing table entries is progressively pruned. In the end, the single routing table entry remaining is the called best match.

Note that the steps described below may fail to produce a best match routing table entry (i.e., all existing routing table entries are pruned for some reason or another). In this case, the packet's IP destination is considered unreachable. Instead of being forwarded, the packet should be dropped and an ICMP destination unreachable message should be returned to the packet's source.

  1. Select the complete set of "matching" routing table entries from the routing table. Each routing table entry describes a (set of) path(s) to a range of IP addresses. If the data packet's IP destination falls into an entry's range of IP addresses, the routing table entry is called a match. (It is quite likely that multiple entries will match the data packet. For example, a default route will match all packets.)

  2. Suppose that the packet's IP destination falls into one of the router's configured area address ranges (see Section 3.5), and that the particular area address range is active. This means that there are one or more reachable (by intra- area paths) networks contained in the area address range. The packet's IP destination is then required to belong to one of these constituent networks. For this reason, only matching routing table entries with path-type of intra-area are considered (all others are pruned). If no such matching entries exist, the destination is unreachable (see above). Otherwise, skip to step 4.

  3. Reduce the set of matching entries to those having the most preferential path-type (see Section 11). OSPF has a four level hierarchy of paths. Intra-area paths are the most preferred, followed in order by inter-area, type 1 external and type 2 external paths.

  4. Select the remaining routing table entry that provides the longest (most specific) match. Another way of saying this is to choose the remaining entry that specifies the narrowest range of IP addresses.[10] For example, the entry for the address/mask pair of (128.185.1.0, 0xffffff00) is more specific than an entry for the pair (128.185.0.0, 0xffff0000). The default route is the least specific match, since it matches all destinations.

  5. At this point, there may still be multiple routing table entries remaining. Each routing entry will specify the same range of IP addresses, but a different IP Type of Service. Select the routing table entry whose TOS value matches the TOS found in the packet header. If there is no routing table entry for this TOS, select the routing table entry for TOS 0. In other words, packets requesting TOS X are routed along the TOS 0 path if a TOS X path does not exist.


Next: 11.2. Sample routing table, without areas

Connected: An Internet Encyclopedia
11.1. Routing table lookup