Method for optimizing a network prefix-list search
View Patent ↗A packet network device includes a route processor that operates to maintain one or more forwarding tables and it includes one or more line cards that operate to process information received by the packet network device from the network and to forward the information to its correct destination. The route processor also operates to identify which incoming prefixes can be used to update the forwarding tables or to identify prefixes stored in the packet network device that can be redistributed from one network protocol to another network protocol running on the route processor. A table management function running on the route processor operates to identify the best match between an incoming prefix and information included in policy statement associated with both an ordered prefix-list and a radix tree structure.
1. A method for updating a forwarding table in a packet network device, comprising:
defining a first plurality of routing policies for inclusion into a first sequentially numbered list of routing policies;
defining a second plurality of routing policies for inclusion into an ordered prefix list that includes a second sequentially numbered list of routing policies, at least some of the second plurality of routing policies including a non-contiguous IP prefix mask;
building a radix tree structure with information included in the first sequentially numbered list of routing policies;
using IP prefix information included in an IP prefix to search the radix tree structure to identify a lowest sequence number routing policy in the radix tree structure that best matches the IP prefix information;
using the IP prefix information in the IP prefix to search the ordered prefix list to identify a lowest sequence number routing policy in the ordered prefix list that best matches the IP prefix information;
comparing the lowest sequence number routing policy in the ordered prefix list with the lowest sequence number routing policy in the radix tree structure to identify a routing policy with the overall lowest sequence number; and
updating the forwarding table with the IP prefix information if the routing policy with the overall lowest sequence number includes an instruction to permit the IP prefix.
2. The method of claim 1 , wherein a route is discovered by a network protocol.
3. The method of claim 1 , wherein each of the first plurality of routing policies are comprised of contiguous sub-net mask information.
4. The method of claim 1 , wherein each of the second plurality of routing policies are comprised of non-contiguous mask information.
5. The method of claim 1 , wherein the first sequentially number list of routing policies is an IP prefix-list.
6. The method of claim 1 , wherein the ordered prefix list is an IP prefix-list.
7. The method of claim 1 , wherein the first plurality of routing policies is comprised of a permit/deny portion and a IP prefix pair portion.
8. The method of claim 7 , wherein the first plurality of routing policies includes an IP prefix range portion.
9. The method of claim 1 , wherein the radix tree structure is comprised of nodes that include IP prefix-pair information and sub-nodes that include a sequence number and a permit/deny portion.
10. The method of claim 9 , wherein the sub-nodes in the radix tree structure including a prefix range.
11. The method of claim 9 , wherein searching the radix tree structure to identify a lowest sequence number routing policy in the radix tree structure that best matches the IP prefix information includes:
searching the radix tree structure until a best match between the IP prefix information and a routing policy in the radix tree is identified; and
starting at the identified routing policy, backtracking up the radix tree structure to identify the lowest sequence number routing policy in the radix tree structure that best matches the IP prefix information.
12. A packet network device, comprising:
one or more line cards each of which are comprised of one or more input/output ports, a packet processor and a line card memory, the line card memory including at least one forwarding table with information that the packet processor uses to forward packets received by the line card; and
a control module comprised of a route processor and a control module memory, the route processor operating to maintain the at least one forwarding table on the one or more line cards and the control module memory used to store a radix tree structure that includes first sequentially numbered list of routing policies and an ordered prefix list that includes a second sequentially numbered list of routing policies, at least some of the second sequentially numbered list of routing policies including a non-contiguous mask information; wherein the route processor operates to:
use IP prefix information in an IP prefix to search the radix tree structure to identify a lowest sequence number routing policy in the radix tree structure that best matches the IP prefix information;
uses the IP prefix information in the IP prefix to search the ordered prefix list to identify a lowest sequence number routing policy in the ordered prefix list that best matches the IP prefix information;
compare the lowest sequence number routing policy in the ordered prefix list with the lowest sequence number routing policy in the radix tree structure to identify a routing policy with the overall lowest sequence number; and
update the at least one forwarding table with the IP prefix information if the routing policy with the overall lowest sequence number includes an instruction to permit the IP prefix.
13. The packet network device of claim 12 , wherein each of the routing policies in the first sequentially numbered list of routing policies includes contiguous sub-net mask information.
14. The packet network device of claim 12 , wherein each of the routing policies in the second sequentially numbered list of routing policies includes non-contiguous mask information.
15. The packet network device of claim 12 , wherein the first sequentially numbered list of routing policies is an IP prefix-list.
16. The packet network device of claim 12 , wherein the second sequentially numbered list of routing policies is an IP prefix-list.
17. The packet network device of claim 12 , wherein the radix tree structure is comprised of nodes that include IP prefix-pair information and sub-nodes that include a sequence number and a permit/deny portion and prefix range information.
18. The packet network device of claim 12 , wherein the route processor operates to search the radix tree structure until a best match between the IP prefix information and a routing policy in the radix tree structure is identified, and,
starting at the identified routing policy statement, performs a backtrack operation on the radix tree structure to identify the lowest sequence number routing policy in the radix tree structure that best matches the IP prefix information.