Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
2000-01-13
2003-06-17
Powell, Mark R. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S238000
Reexamination Certificate
active
06581106
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to routing in networks, more particularly to a method and apparatus for facilitating fast routing at a network node. The routing (forwarding) stage it deals with is called “address lookup in routing (forwarding) tables.” Given information designating which destination address has to be forwarded to which output port at a node, the stage organizes the information such that the on line search for this information (when a message/packet arrives at the node) is efficient in time and space consumed. The invention concerns with setting, performing and maintaining this stage. The invention is suitable (and is tuned to) the prevalent setting of Internet routing where addresses are called IP addresses. The invention is related to fast methods for solving the above problem within a standard processor architecture and with a small number of memory accesses. Due to fast routing, the invention is related to the issue of increased network bandwidth.
BACKGROUND OF THE INVENTION
Computer networks are expected to exhibit very high performance in delivering data because of the explosive growth of Internet nodes (from 100,000 hosts in 1989 to over 60 millions as of 1999). The network bandwidth, which measures the number of bits that can be transmitted in a certain period of time, is thus continuously improved by adding new links and/or by improving the performance of the existing ones.
Routers are at the heart of the networks in that they forward packets from input interfaces to output interfaces on the ground of the packets' destination Internet address, which we simply call IP address. They choose which output interface corresponds to a given packet by performing an IP address lookup at their routing table. As routers have to deal with an ever increasing number of links whose performance constantly improves, the address lookup is now becoming one of the major bottlenecks in high performance forwarding engines.
The IP address lookup problem was just considered a simple table lookup problem at the beginning of Internet. Now, it is unconceivable to store all existing IP addresses explicitly because, in this case, routing tables would contain millions of entries. In the early 1990s people realized that the amount of routing information would grow enormously, and introduced a simple use of prefixes to reduce space (see Fuller, V., Li, T., Yu, J., and Varadhan, K. “Classless inter-domain routing (CIDR): an address assignment and aggregation strategy” RFC 1519, 1993,). Specifically, IP protocols use hierarchical addressing, so that a network contains several subnets which in turn contain several host computers. Suppose that all subnets of the network with IP address 128.96.*.* have the same routing information apart from the subnet whose IP address is 128.96.34.*. We can succinctly describe this situation by just two entries (128.96 and 128.96.34) instead of many entries for all possible IP addresses of the network. However, the use of prefixes introduces a new dimension in the IP address lookup problem: For each packet, more than one table entry can match the packet's IP address. In this case, the applied rule consists of choosing the longest prefix match, where each prefix is a binary string that has a variable length from 8 to 32 in IPv4 (see Postel, J. “Internet protocol”, RFC 791, 1981,). For example, let us consider Table 1 where &egr; denotes the empty sequence corresponding to the default output interface, and assume that the IP address of the packet to be forwarded is 159.213.37.2, that is, 10011111 11010101 00100101 00000010 in binary. Then, the longest prefix match is obtained with the fourth entry of the table and the packet is forwarded to output interface D. Instead, a packet whose IP address is 159.213.65.15, that is, 10011111 11010101 01000001 00001111 is forwarded to output interface C.
Looking for the longest matching prefix in IP routing tables represents a challenging problem since lookups must be answered very quickly. In order to get a bandwidth of, say, 10 gigabits per second with an average packet length equal to 2,000, a router should forward 5 millions of packets per second. It means that each forwarding has to be performed in approximately 200 nanoseconds and, consequently, each lookup must be realized much faster.
DESCRIPTION OF RELATED ART
Several approaches have been proposed in the last few years in order to solve the IP address lookup problem. Hardware solutions, though very efficient, are expensive and some of them may become outdated quite quickly (See U.S. patent application Ser. No. 034,444, 1995 by McAuley, A., Tsuchiya, P., and Wilson, D. “Fast multilevel hierarchical routing table using content-addressable memory” as well as Newman, P., Minshall, G., Lyon, T., and Huston, L. “IP switching and gigabit routers” in IEEE Communications Magazine (January 1997)). Modern routers will use software or hardware and software combination. Next we will review the known software solutions.
A traditional implementation of routing tables (see Stevens, W., and Wright, C. “TCP/IP Illustrated, Volume 2 The Implementation” Addison-Wesley Publishing Company, Reading, Mass., 1995) use a version of Patricia tries, a very well-known data structure (Morrison, D. “PATRICIA—Practical Algorithm To Retrieve Information Coded In Alfanumeric” in Journal of ACM 15,4 (October 1968), 514-534). In this case, it is possible to show that, for tables with n elements, the average number of examined bits is 1.44 log n (log n is logarithm to the base 2 of the number n). Thus, for n=32000, this value is bigger than 21. When compared to millions of address lookup requests served in one second, 21 table accesses are too many. Another variation of Patricia tries has been proposed in order to examine k bit each time (in Pei, T.-B. and Zukowski, C. “Putting routing tables into silicon” in IEEE Network, 1992, pages 42-50). However, this variation deals with either the exact matching problem or with the longest prefix matching problem restricted to prefixes whose lengths are multiples of k.
A more recent approach (by Nilsson, S., and Karlsson, G. “Fast address look-up for internet routers” in ALEX (February 1998), Università di Trento, pp. 9-18) was inspired by the three-level data structure of Degermark, M. at al. (“Small forwarding tables for fast routing lookups”, in ACM Computer Communication Review 27, 4 (October 1997), 3-14). which uses a scheme to compress multi-bit trie nodes using a bitmap, and is based on the compression of the routing tables by means of level compressed tries, which are a powerful and space efficient representation of binary tries. This approach seems to be very efficient from a memory size point of view but it requires many bit operations which, on the current technology, are time consuming.
Another approach is based on binary search on hash tables organized by prefix lengths (in Waldvogel, M. et al. “Scalable high speed IP routing lookups”, in ACM Computer Communication Review 27, 4 (October 1997), 25-36). This technique is more memory consuming than the previous one but, according to the experimental evaluation presented by the authors, it seems to be very efficient from the time point of view.
A completely different way of using binary search is described in Lampson at al. (in “IP lookups using multi-way and multicolumn search” ACM INFOCOM Conference, (April 1998)). It is based on multi-way search on the number of possible prefixes rather than the number of possible prefix lengths and exploits the locality inherent in processor caches.
The most recent software solution to the IP address lookup problem is the one based on controlled prefix expansion (by Srinivasan, V., and Varghese, G. in “Fast address lookups using controlled prefix expansion” in ACM SIGMETRICS Conference (September 1998) and available full version to appear in ACM TOCS). This approach, together with optimization techniques such as dynamic programming, can be used to improve the speed of most IP lookup algorithms. When applied to trie search, it resu
Crescenzi Pierluigi
Dardini Leandro
Grossi Roberto
Yung Marcel Mordechay
Powell Mark R.
Schweitzer Cornman Gross & Bondell LLP
Thompson Marc D.
LandOfFree
Fast address lookup in routing tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast address lookup in routing tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast address lookup in routing tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096415