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.
- 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.)
- 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.
- 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.
- 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.
- 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