IPv6 routing method
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jun-19
IPv6 addresses are 128 bits long (as opposed to 32 bits in IPv4). As with IPv4, there is the concept of longest prefix match. Thus a set of routes (each equivalent to a subnet) is a set S of patterns 1 to 128 bits long. This set is called a route table. Associated with each entry in the table is a routing action (that might involve unicast, anycast, multicast issues as defined in RFC 2373, "IP Version 6 Addressing Architecture"). A routing action in general is the assignment of a subnet prefix to a network link. Multiple subnet prefixes may be assigned to the same link. The routing problem for a given 128 bit destination address X is to find the longest route in the set S that matches the leftmost contiguous bits of X exactly. There is a default routing action in the case of no matches at all. The statistics of the route set S can be guessed from small sets that exist today plus an understanding of the statistics of IPv4 route tables. Then, using those statistics, a method for efficiently finding the longest matching prefix can be invented. The present disclosure teaches such a method. The present method is an extension of method disclosed in RAL8-2000-0016, "Hybrid longest prefix match and fixed match searches."