Browse Prior Art Database

IPv6 routing method Disclosure Number: IPCOM000013967D
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 3 page(s) / 44K

Publishing Venue



IPv6 addresses are 128 bits long (as opposed to 32 bits in IPv4).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 3

IPv6 routing method

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."

Main idea of the invention.

Study of IPv4 routing tables and the small IPv6 tables of today suggests that IPv6 tables will have the following statistics:

1. A large number of routes will be used, perhaps 100K to 1M. This is the whole point of going to IPv6. (Note other emerging technologies and trends such as CIDR and VPNs might make IPv6 unnecessary in some applications. Thus IPv6 architecture provides for "IPv4 compatible IPv6 addresses" and "IPv4-mapped IPv6 addresses.)
2. Perhaps 1% of all IPv6 routes will be 16 bits.
3. Perhaps 10% of all routes will be under 32 bits (clustered at 24, 28, 32 bits)
4. IPv6 addresses are written as eight hexadecimal numbers of four characters each separated by a colon : . Hence A:B:C:D:E:F:G:H would be the form of an IPv6 address where the symbols A, B, ... represent four-character hex numbers, each equivalent to 16 bits. Among routes with >= 32 bits, the number of distinct A components in a routing table is likely to be much smaller than the number of distinct B components. Among routes with >= 48 bits,the number of distinct B components is likely to be somewhat smaller than the number of C components.
5. Other popular IPv6 route lengths will be 35, 48, 64, 126, 128.
6. Many IPv6 addresses (and of the long routes, many routes) will have all zero entries in E, F, G components, especially F and G.
7. In present day IPv4 routing tables, few or no routes of length shorter than 8 bits (first of the conventional four byte representation) occur. Likely few or no IPv6 routes will have fewer than 16 bits. Likely as well, no route has a length greater than 16 and less than 32.

A standard Network Processor lookup mechanism is a 16 bit wide Direct Table (DT) with attached Patricia...