FREE TOOL

Longest prefix match explainer

Paste the output of "show ip route" from a Cisco IOS XE router and enter a destination address. The explainer lists every route in the table that contains the destination, picks the one with the longest prefix, and shows its next hops, with the binary working. The lookup runs in this page, and the page does not send what you paste to a server. No account is required.

Routing table and destination

This explainer runs in your browser and needs JavaScript turned on. The boxes stay locked until the page script loads, so the page cannot send anything you enter. If they stay locked, the script did not load. Turn on JavaScript or reload the page to use the explainer.

Paste the whole "show ip route" output, including the code legend and the "Gateway of last resort" line. From filtered output, such as "show ip route static", the explainer can find the best match among the pasted routes, but it cannot say what the router does with the packet.

The address a packet is sent to, for example 10.1.1.77.

How a router picks a route

A routing table can hold several routes that contain the same destination. The example below holds static routes from a lab router's table. 10.1.1.77 is inside 0.0.0.0/0, 10.0.0.0/8, 10.1.0.0/16 and 10.1.1.0/24. The router uses the route with the longest prefix, here 10.1.1.0/24, because a longer prefix names a smaller block of addresses and so says more about where this destination is. This is the longest prefix match rule.

S*    0.0.0.0/0 [1/0] via 172.16.12.2
      10.0.0.0/8 is variably subnetted, 5 subnets, 4 masks
S        10.0.0.0/8 [1/0] via 172.16.12.2
S        10.1.0.0/16 [1/0] via 172.16.12.6
S        10.1.1.0/24 [1/0] via 172.16.12.2
S        10.1.1.200/32 [1/0] via 172.16.12.6
S        10.2.0.0/16 is directly connected, Null0

Route source, administrative distance and metric do not take part in this choice. They decide which route for a given prefix gets installed in the table in the first place. Once routes are installed, only the prefix length decides between them, so a static /16 loses to an OSPF /24 that also contains the destination.

The example is part of a table and has no gateway line, so if you paste it, the explainer calls each answer the best match in this output. The next section explains why.

To practice, copy the example table and decide on paper which route wins for 10.1.1.200, for 10.1.9.9 and for 10.2.3.4. Then paste the table, run each address, and compare your answer with the table of routes.

What filtered output can and cannot answer

"show ip route static", "show ip route ospf" and "show ip route ... longer-prefixes" print only part of the table. From that output the explainer can show which of the pasted routes contain the destination and which of them is longest. It cannot show what the router does with the packet, because the full table may hold a longer route, or a default route, that the filter left out.

The explainer checks the paste for three signs that it is filtered: a command line with anything after "show ip route", a "Gateway of last resort" line that names a default route the paste does not list, and an "is subnetted" header that counts more subnets than the paste lists under it. When it finds one, it calls a match the best match in this output, and when no pasted route contains the destination, it gives no answer instead of saying the router has no route. A paste with no gateway line gets the same treatment, because it may not be the whole table. On the lab router the fixtures came from, a longer-prefixes view of 10.1.0.0/16 holds no route for 10.7.7.7, but "show ip route 10.7.7.7" on the same router named 10.0.0.0/8 via 172.16.12.2.

How the working shows containment

A route contains a destination when the destination's first bits, as many as the prefix length, equal the route's network. The working keeps that many bits of the destination by ANDing it with the prefix mask and compares the result with the network, for the longest containing routes first. A route that does not contain the destination is listed with the first bit where the destination leaves it.

Equal-cost paths, Null0 and the default route

When the winning route has more than one next hop, IOS prints the extra next hops on the lines below the route, and the router shares traffic across them. The explainer lists every next hop and does not predict which one a packet takes. A route to Null0 discards matching packets. A default route, 0.0.0.0/0, contains every address and so wins only when no longer route contains the destination. On the router the fixtures came from, "show ip route 198.18.0.1" printed "% Network not in table" even though the default route forwards that address; the explainer reports the default route as the match.

What the explainer reads

It reads the IPv4 "show ip route" output captured from IOS XE 17.12.1: the full table and the static, ospf and longer-prefixes variants, with the code legend, the gateway line, the classful "is subnetted" headers and equal-cost next-hop lines. It evaluates routes with the codes C, L, S, S*, O, O IA, O E2. A route line with any other code is read for its prefix only: if that prefix could win, the explainer gives no answer rather than guess. Any line it does not recognize, such as a VRF "Routing Table:" header or the single-route "Routing entry for" output, also stops it from giving an answer, because that line could hold the winning route.

Why this explainer has no share link

The answer depends on the whole table you pasted, and a routing table is device output. This page never writes device output to a link, so the explainer has no share link and never writes the table or the address to the page's URL. Use Copy results to keep a record.

What this explainer does not do

The explainer looks up one destination in the table you paste. It does not follow a next-hop address to find the outgoing interface, and it does not model policy-based routing or VRFs, and it reads the routing table, not the router's forwarding table (CEF). It reads IPv4 tables only, and only the codes listed above. The output it reads was captured from Cisco IOS XE 17.12.1 running as IOL on Cisco Modeling Labs; other releases and platforms can print tables differently. The working shows the 4 longest containing routes, and the table lists every route.

Sources: RFC 1812, section 5.2.4.3, for longest match route lookup; RFC 4632, section 5.1, for discarding traffic to an aggregate with no more specific route; Cisco, Configure Route Selection for Routers, for administrative distance and metric deciding what is installed and the longest prefix match deciding among installed routes.