US 8,798,066 B2 · Method for IPv6 longest prefix match

Abstract

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.

Claims18

Dependent claims

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.

1 more element

Dependencies are inferred from the claim text.

Method for IPv6 longest prefix match

Life of this patent

Method for IPv6 longest prefix match

Life of this patent

Abstract

Claims18