Multi-resolution tree for longest match address lookups

Details Multi-resolution tree for longest match address lookups Multi-resolution tree for longest match address lookups

1997-10-30

2003-05-13

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000

Reexamination Certificate

active

06563823

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to forwarding devices in general. More particularly, the present invention relates to a method and apparatus for performing longest match address lookups for routing a packet or cell of information in a network.
BACKGROUND OF INVENTION
The popularity of communications networks such as the Internet and World Wide Web (WWW) is growing at a phenomenal rate. Part of the reason for this growth is the rich amount of content available through these networks, as well as the ability to provide interactive communications services. For example, it is currently possible to place a telephone call using the Internet rather than the Public Switched Telephone Network (PSTN). Moreover, it is possible to engage in multi-media communications over the Internet, such as video conferencing, telecontrol, distributed computer applications, multimedia conferencing, remote visualization, high definition television (HDTV) and even virtual reality.
The increase in usage of the Internet increases the basic unit of transfer used by the Internet, namely data packets. The Internet is already required to process hundreds of thousands of packets per second, with indications that it must process millions of packets per second to maintain pace with user demand. In response to this demand, communications technologies have been developed which significantly improve the number of packets which can be moved through the network.
A problem still persists, however, with a class of network devices which are integral to combining disparate networks together. These network devices are collectively referred to as forwarding devices, examples of which include packet switches, routers and bridges. The basic function of a forwarding device is exactly as it sounds, that is, the forwarding device takes a data packet, looks up forwarding information needed to route the packet to its destination, and forwards the packet to another network device using the forwarding information.
A forwarding device accomplishes this basic routing or directing function by utilizing a routing table. A routing table comprises destination addresses and forwarding information used by the forwarding device to direct a packet to its next or ultimate destination. In recent years, the sheer number of destination addresses required for the routing table have caused forwarding devices to become saturated in terms of processing power and memory allocation. Lookup algorithms designed to compare a destination address retrieved from a packet with the ever-growing number of destination address stored in the routing table are far too slow and inefficient to meet current forwarding device throughput requirements.
In an attempt to reduce the number of destination addresses required for a routing table, a new Internet addressing scheme was developed which is referred to as Classless Interdomain Routing (CIDR). CIDR aggregates or groups IP addresses together in hierarchical levels, similar to the hierarchical addressing scheme used to route a telephone call to a specific call recipient using a telephone number. Take for example the telephone number 412-555-1212. The area code (i.e., 412) indicates the general area of the call recipient, while the next three digits (e.g., 555) further narrows down the location to a more specific local, while the last four digits (i.e., 1212) identifies the precise location of the called party. CIDR groups IP addresses together in a similar hierarchical pattern, with the leftmost bits of an IP address giving the location of a particular network, while the location of a network device or host becomes increasingly specific as the address reads to the rightmost bit. For example, a typical Internet address under the IP version 4 (IPv4) addressing scheme might be 1.1.1.2 in decimal form, which is represented in binary form as a sequence of 32 binary bits, i.e., 00000001.00000001.00000001.00000010. CIDR is a method of identifying those address bits which are meaningful for routing a packet to its next destination. Since the Internet is comprised of a plurality of forwarding devices, it is sometimes unnecessary to have a complete destination address for each packet in the routing table. Rather, an abbreviated address could be used which merely represents forwarding information to the next forwarding device. This is referred to as “hop-by-hop forwarding.” Thus, instead of using 00000001.00000001.00000001.00000010 to index forwarding information for a packet, CIDR assigns a prefix for each address, the prefix comprising an IP address and some indication of the leftmost contiguous significant bits within this address. For example, the CIDR prefix 1.1.1.2/16 would mean that only the first 16 bits of the address 1.1.1.2 are significant for routing purposes. The result is fewer destination addresses are required for each Internet forwarding device's routing table.
Although CIDR reduced the number of destination addresses stored in a routing table, CIDR also complicated the lookup algorithms required to lookup forwarding information stored in the table. Under CIDR, routing to all destinations is always performed on a longest match basis. It may occur that a routing table may have different length prefixes of the same network which match the destination address of a packet. When a forwarding device must decide between two different length prefixes of the same network, it will always follow the longer mask. By way of analogy, if a switch in the PSTN had a choice to route a call using just the area code, or the area code and next three digits, the switch would use the area code plus three digits to route the call since it is more precise. As an example for a forwarding device, assume that a forwarding device has the following two CIDR prefixes in its routing table: (1) 198.32.1.0/24 via path 1 and (2) 198.32.0.0/16 via path 2. When trying to deliver traffic to host 198.32.1.1., the forwarding device tries to match the destination with the longest prefix and in this case would deliver the traffic via path 1. Thus, the longest match rule imposed by CIDR requires that for each destination address embedded within a packet, the lookup algorithm must search the entire routing table for the longest prefix.
The CIDR longest match rule can be better understood with reference to FIG.
1
.
FIG. 1
is a diagram for a logical representation of the longest match rule. A data packet is received by a forwarding device with an IP address of 124.13.7.5. The forwarding device uses a lookup algorithm to search for matching prefixes within a routing table 16. Routing table 16 contains prefixes with varying levels of granularity, with the meaningless bits represented by the letter “X”. The search first uncovers the matching prefix 124.X.X.X (referred to as match preference three). Since the longest match rule requires that the entire routing table be searched for the longest prefix that matches the destination address, the forwarding device must continue searching routing table 16. The continued search uncovers a second match preference of 124.13.X.X. Since the address 124.13.7.5 more closely resembles 124.13.X.X, this match preference is more desirable the match preference three since it more specifically identifies a route for the packet. Finally, the search uncovers a first match preference of 124.13.7.X. Since this prefix is the closest match to the address 124.13.7.5 in routing table 16, the forwarding device will use the forwarding information associated with this prefix to route the packet to its next destination.
Different lookup solutions such as the hash, radix tree, Patricia tree and cached variations thereof, have been developed to perform longest match lookups required by CIDR. The conventional lookup solutions, however, are unsatisfactory for a number of reasons. For example, all of the conventional solutions suffer under the fact that the number of steps necessary for a longest match lookup can grow large in certain cases. This leads to more frequent memory accesses, which slow down the lookup proces

Affiliated with

Also associated with

Rating

Multi-resolution tree for longest match address lookups does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-resolution tree for longest match address lookups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-resolution tree for longest match address lookups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3091072