Method for IPv6 longest prefix match
View Patent ↗IPv6 longest prefix match lookups are implemented by splitting disjoint forwarding rules from non-disjoint forwarding rules and storing these forwarding rules in separate TCAMs. When an IPv6 address is received, the full IP address is passed to the TCAM containing the disjoint forwarding rules and the first n bits of the IP address are passed to the TCAM containing the non-disjoint forwarding rules. If a hit is received in the TCAM containing the disjoint forwarding rules, a result of the hit is used to implement a forwarding decision and the search in the TCAM containing the non-disjoint forwarding rules is terminated. If no hit is obtained from the disjoint TCAM, the search result of the non-disjoint TCAM is used. If a continue flag is set in the result received from the disjoint TCAM, a sub-trie based lookup is implemented based on the remaining m bits of the IPv6 address.
1. A method for IPv6 Longest Prefix Match, the method comprising the steps of:
receiving, by a network element, a packet including an IPv6 address, the IPv6 address having 128 bits;
passing all 128 bits of the IPv6 address to a first Ternary Content Addressable Memory (TCAM), the first TCAM storing forwarding entries associated with disjoint prefix forwarding rules;
passing a first subset of the bits of the IPv6 address to a second TCAM, the second TCAM storing forwarding entries associated with non-disjoint prefix forwarding rules, the first subset of the bits of the IPv6 address including fewer than all 128 bits of the IPv6 address;
performing a lookup operation in the first TCAM and the second TCAM in parallel.
2. The method of claim 1 , further comprising the step of using a first result of the lookup operation from the first TCAM and stopping the lookup operation in the second TCAM if the first result from the lookup operation from the first TCAM is positive.
3. The method of claim 2 , wherein when the first result is positive, the first result contains a pointer to a next hop forwarding table.
4. The method of claim 2 , further comprising the step of using a second result of the lookup operation from the second TCAM if the first result of the lookup operation from the first TCAM is not positive.
5. The method of claim 4 , wherein the second TCAM includes an entry with all wildcard entries to guarantee a match for the IP address in the second TCAM.
6. The method of claim 4 , wherein when the second result is positive, the second result contains a pointer to a next hop forwarding table.
7. The method of claim 4 , wherein when the second result is positive, the second result contains a continue flag and a pointer to a root of a sub-trie tree to be used to perform a third lookup operation.
8. The method of claim 7 , further comprising the step of performing a third lookup in the sub-trie tree identified by the pointer using a second subset of the bits of the IPv6 address.
9. The method of claim 1 , wherein the disjoint prefix forwarding rules are a set of forwarding rules in which no two forwarding rules of the set commonly apply to any individual IPv6 address.
10. The method of claim 1 , wherein the non-disjoint prefix forwarding rules are a set of forwarding rules in which sub-sets of two forwarding rules commonly apply to IPv6 addresses.
11. The method of claim 1 , wherein the forwarding entries associated with disjoint prefix forwarding rules are not ordered in the first TCAM.
12. A network element for IPv6 Longest Prefix Match, comprising:
an input function, a forwarding function, a memory, and an output function, the forwarding function interacting with the memory to make forwarding decisions in connection with receipt of packets on the input function and forwarding of the packets on the output function;
wherein the memory comprises:
a first Ternary Content Addressable Memory (TCAM) configured to store forwarding entries associated with disjoint prefix forwarding rules and to perform a search on the forwarding entries using all 128 bits of an IPv6 address of a packet;
a second TCAM configured to store forwarding entries associated with non-disjoint prefix forwarding rules and to perform a search on the forwarding entries using a first subset of the bits of the IPv6 address, the first subset of the bits of the IPv6 address including the most significant bits of the IPv6 address and fewer than all 128 bits of the IPv6 address;
wherein the memory is configured to perform an IP search in the first TCAM and second TCAM in parallel.
13. The network element of claim 12 , wherein the memory is configured to terminate the search in the second TCAM if the search in the first TCAM returns a positive result.
14. The network element of claim 13 , wherein the positive result is a pointer to an entry in a next hop forwarding table.
15. The network element of claim 12 , wherein a positive result from the second TCAM includes a value and a continue flag.
16. The network element of claim 15 , wherein when the continue flag is set, the value is a pointer to a root of a sub-trie tree.
17. The network element of claim 16 , wherein the sub-trie tree is maintained in a form of random access memory not implemented as a TCAM.
18. The network element of claim 15 , wherein when the continue flag is not set, the value is a pointer an entry in a next hop forwarding table.