Prefix Trees

A prefix tree is a nonsequential collection of permit and deny conditions that apply to IP addresses. Like a prefix list, the prefix tree specifies a base IP address and a length, the number of bits applied to the base to determine the network prefix. The tested address is matched against the prefix. The prefix tree also enables route summarization.

However, the prefix tree does not match addresses one by one in sequence against the listed conditions. The router performs a binary search against the tree structure of the entries. If the tested address is less than a particular entry, it branches one way to another test pair; if it is greater than the entry, it branches the other way to another mutually exclusive test pair. The router stops testing conditions when it finds the best match. If no conditions match, the router rejects the address. An empty prefix tree results in an automatic permit of the tested address.

The prefix tree provides a faster search method and matches the test address more closely than either the access list or the prefix list.

Use the ip prefix-tree command to define an IP prefix tree. Use the prefix-tree keyword with the match ip address or match ip next-hop commands to add a clause to a route map. Use the match-set summary prefix-tree command to specify the prefix tree that summarizes routes for a particular route map.

Using a Prefix Tree

The following example creates a prefix tree that permits routes with a prefix length of 24 or larger in the 10.10.2.0/24 network:

clear ip prefix-tree

• Use to clear all hit counts in the prefix trees or the specified entry from the specified prefix tree. (The router increments the hit count by 1 each time an entry matches.)
• Example

  host1#clear ip prefix-tree xyz

• There is no no version.
• See clear ip prefix-tree.

ip prefix-tree

• Use to create a prefix tree for best route filtering; specifies a tree entry—a deny or permit clause for a network address.
• The prefix tree name can be up to 32 characters long.
• Example

  host1(config)#ip prefix-tree boston42 permit 10.10.2.0/24

• Use the no version to remove the specified prefix tree or the specified tree entry.
• See ip prefix-tree.

match ip address

• Use with the prefix-tree keyword to match routes that have a destination network number address that is permitted by the prefix tree.
• Example

  host1(config-route-map)#match ip address prefix-tree xyz

• Use the no version to delete the match clause from a route map or a specified value from the match clause.
• See match ip address.

match ip next-hop

• Use with the prefix-tree keyword to match routes that have a next-hop router address passed by the specified prefix tree.
• Example

  host1(config-route-map)#match ip next-hop prefix-tree xyz

• Use the no version to delete the match clause from a route map or a specified value from the match clause.
• See match ip next-hop.

match-set summary prefix-tree

• Use to specify the prefix tree that summarizes routes for a particular route map.
• Use the ip prefix-tree command to set the conditions of the prefix tree, including which routes to summarize and how many bits of the network address to preserve.
• Example

  host1(config-route-map)#match-set summary prefix-tree dog3

• Use the no version to disable use of the prefix tree by the route map.
• See match-set summary prefix-tree.