Network routing table using content addressable memory

Details Network routing table using content addressable memory Network routing table using content addressable memory

1997-07-09

2001-01-30

Olms, Douglas W. (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S422000, C710S108000

Reexamination Certificate

active

06181698

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to routing tables, and to devices and methods for network routing, such as internet protocol (IP) routing. In particular, it relates to methods for quickly finding routing information in a routing table from a destination address.
BACKGROUND ART
In networking, the objective of routing is to quickly find from a given destination address a route and the related information about the route. This information is typically stored in a routing table. For example, in IP routing, a route is either:
an indirect route, in which case the next hop is another router. A routing table entry contains the next router's IP address and the related route information (such as the network interface to which it is connected);
a direct route, in which case the next hop is the destination host. A routing table entry contains the network interface to which the destination host is connected.
An IP address consists of 32 bits, plus an optional IP prefix. This prefix specifies the number of leading bits of the IP address which are considered the network portion, with the remaining bits being considered the host portion. The network portion is often referred to as the IP network address. The host portion could be referred to as the IP host address. The whole IP address, however, is sometimes called the IP host address to emphasize that it indicates the host address. For example, using standard Internet dotted decimal notation, 172.16.10.20/24 would indicate a network address of 172.16.10.0, while the full IP host address is 172.16.10.20.
IP routing is based on either the destination IP network address or the destination IP host address (i.e. the whole IP address). Routes specified with IP network addresses are called network routes. Routes specified with IP host addresses are called host routes. IP routers must handle both types of routes.
Routers use a table (or tables) called the routing table to find routes. The routing table consists of routing table entries. Each routing table entry typically contains information related to a destination, such as a next router's IP address for the destination, the destination network or host IP address, the IP prefix for the destination, and the network interface to be used for sending a datagram to the next router. [A datagram is a packet of information including an IP address header.] In case a routing table entry contains a direct route, the next router's IP address is 0.0.0.0 to indicate that it is a direct route.
The destination IP address in each IP datagram is used as the search key when routers look up a route. The problem is that each IP datagram is sent with its destination IP host address but not with its IP prefix information. Consequently, routers have to find which part of the IP host address consists of the IP network address in the case of a network route. Since network routes are much more common than host routes, this is a serious problem since it slows down the router and limits network speed.
There are two popular routing table implementations in the prior art.
The first uses hash tables. This approach is used in 4.2BSD UNIX, 4.3BSD UNIX, and some commercial routers.
Two routing tables and one special routing entry are used in this implementation. The first table, which we will refer to as rt_host, is used for host routes. The second table, which we will refer to as rt_net, is used for network routes. A special routing entry is used for the default route. When a datagram is being decoded, the router first tries to look up a route in the rt_host table for host routes. Then, if it cannot find a route in the rt_host table, it tries to look up a route in the rt_net table. Finally, it uses the default route (assuming the default route exists) if it cannot find any routes in either the rt_host or the rt_net tables.
These tables are implemented as hash tables. Routers use the destination IP host address in the incoming IP datagram as a hash key to determine the starting pointer of a linked list in the hash table. A linear search is then performed over a linked list to determine if the IP host address matches any entry in the linked list. If so, this entry (which contains the host route) is returned. In the case of the rt_net hash table, the linked list is pre-sorted by IP prefix in descending order so that the longest match of the network portion is selected.
This implementation is very slow because it is basically a linear search after calculating the starting pointer in the hash table. In addition, this route lookup cannot be done in deterministic time. That is, a router employing this method of look-up cannot always find a route within a fixed minimum amount of time. Consequently, networks using such routers cannot provide guaranteed or reliable performance and may experience unpredictable data flow problems.
Another popular implementation is the radix tree routing table. It is also known as the Patricia tree routing table. This is used in 4.4BSD UNIX, and some commercial routers. Some routers implement this by a hardware implementation.
This method takes the destination IP host address, and compares it one bit at a time going down in a binary tree of network and host IP addresses with back tracking. This tree can be sorted depending on the network and host IP addresses in the binary tree to optimize the search.
A radix tree search can minimize the number of bits to be tested to distinguish among a set of bit strings, but it cannot search for a route in deterministic time. It can also be slow if back tracking occurs.
In U.S. Pat. No. 5,386,413, all possible values to be compared with the incoming address are split into banks. Each bank uses a single mask in conjunction with the incoming address to select at most one associated output value in the bank. If more than one bank selects an output value, the value used is determined by the static priority of the banks. This method has the disadvantage of being inflexible and non-optimal. It also requires a separate bank for each set of different mask values. This arrangement can be inefficient and can waste valuable chip real estate since it is not known a priori how large each bank will need to be for a given router. Each router must therefore be built with large banks, most of which will be empty. If a bank fills up, the router fails to perform properly.
U.S. Pat. No. 5,521,910 discloses a breath first recursive search in parallel. It searches in parallel for the best path of multiple possible paths to the destination based on a relative ranking of the paths. This method, however, does not have mask values for the addresses and cannot select the most specific address among all possible addresses.
U.S. Pat. No. 5,490,258 uses a content addressable memory (CAM), which is also called an associative memory, for routing. But it uses CAM only for compressing the destination address, and the routing table itself is comprised of ordinary memory. Consequently, while the CAM helps compress information, it does not provide improved router look-up speed.
Some CAMs allow each entry to have different mask values. But none of them also return the mask value as well as the address for the entry found.
The paper “Fast Routing Table Lookup Using CAMs” by Anthony J. McAuley & Paul Francis,
Proc. IEEE INFOCOM,
1993, discloses a routing method that requires different CAM banks for each mask value unless all entries are always kept sorted in order of largest to smallest mask. The burden of sorting addresses every time they change is an obvious disadvantage, and can degrade router performance. The use of different CAM banks also has the disadvantages already mentioned above.
OBJECTS AND ADVANTAGES OF THE INVENTION
Accordingly, several objects and advantages of the present invention are:
to provide a routing table enabling deterministic look-up time.
to provide a routing table enabling fast, parallel route look-up.
to provide a simply structured routing table which makes efficient use of memory.
to provide a routing table which is capable of selecting

Affiliated with

Also associated with

Rating

Network routing table using content addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Network routing table using content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network routing table using content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2533354