Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
1998-04-17
2001-07-24
Luu, Le Hien (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S238000, C709S239000, C709S240000, C709S243000, C709S244000, C370S238000, C370S351000
Reexamination Certificate
active
06266706
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method and system of IP (internet protocol) routing lookups in a routing table, comprising entries of arbitrary length prefixes with associated next-hop information in a next-hop table, to determine where IP datagrams are to be forwarded.
DESCRIPTION OF THE PRIOR ART
The Internet is an interconnected set of networks, wherein each of the constituent networks retains its identity, and special mechanisms are needed for communication across multiple networks. The constituent networks are referred to as subnetworks.
Each subnetwork in the Internet supports communication among the devices connected to that subnetwork. Further, subnetworks are connected by devices referred to as interworking units (IWUs).
A particular IWU is a router, which is used to connect two networks that may or may not be similar. The router employs an internet protocol (IP) present in each router and each host of the network.
IP provides a connectionless or datagram service between stations.
Routing is generally accomplished by maintaining a routing table in each station and router that indicates, for each possible destination network, the next router to which the IP datagram should be sent.
IP routers do a routing lookup in a routing table to determine where IP datagrams are to be forwarded. The result of the operation is the next-hop on the path towards the destination. An entry in a routing table is conceptually an arbitrary length prefix with associated next-hop information. Routing lookups must find the routing entry with the longest matching prefix.
Since IP routing lookups have been inherently slow and complex, operations with prior art solutions have led to a proliferation of techniques to avoid using them. Various link layer switching technologies below IP, IP layer bypass methods (disclosed by the Proceedings of the Conference on Computer Communications (IEEE Infocom), San Francisco, Calif., March 1996; Proceedings of Gigabit Network Workshop, Boston, April 1995; and Proceedings of ACM SIGCOMM '95, p. 49-58, Cambridge, Mass., August 1995), and the development of alternative network layers based on virtual circuit technologies such as asynchronous transfer mode (ATM), are to some degree results of a wish to avoid IP routing lookups.
The use of switching link layers and flow or tag switching architectures below the IP level adds complexity and redundancy to the network.
Most current IP router designs use caching techniques wherein the routing entries of the most recently used destination addresses are kept in a cache. The technique relies on there being enough locality in the traffic so that the cache hit rate is sufficiently high and the cost of a routing lookup is amortized over several packets. These caching methods have worked well in the past. However, as the current rapid growth of the Internet increases the required size of address caches, hardware caches may become uneconomical.
Traditional implementations of routing tables use a version of Patricia trees (disclosed by the Journal of the ACM, 15(4): 514-534, October 1968), a data structure invented almost thirty years ago, with modifications for longest prefix matching.
A straightforward implementation of Patricia trees for routing lookup purposes, for example in the NetBSD 1.2 implementation, uses 24 bytes for leaves and internal nodes. With 40,000 entries, the tree structure alone is almost 2 megabytes, and in a perfectly balanced tree 15 or 16 nodes must be traversed to find a routing entry.
In some cases, due to the longest matching prefix rule, additional nodes need to be traversed to find the proper routing information as it is not guaranteed that the initial search will find the proper leaf. There are optimizations that can reduce the size of a Patricia tree and improve lookup speeds. Nevertheless, the data structure is large and too many expensive memory references are needed to search it. Current Internet routing tables are too large to fit into on-chip caches and off-chip memory references to DRAMs are too slow to support required routing speeds.
An early work on improving IP routing performance by avoiding full routing lookups (disclosed by the proceedings of the Conference on Computer Communication (IEEE Infocom), New Orleans, La., March 1988) found that a small destination address cache can improve routing lookup performance by at least 65 percent. Less than 10 slots were needed to get a hit rate over 90 percent. Such small destination address caches are not sufficient with the large traffic intensities and the number of hosts in today's Internet.
ATM (asynchronous transfer mode) avoids doing routing lookups by having a signaling protocol that passes addresses to the network during connection setup. Forwarding state, accessed by a virtual circuit identifier (VCI), is installed in switches along the path of the connection during setup. ATM cells contain the VCI which can then be used as a direct index into a table with forwarding state or as the key to a hash function. The routing decision is simpler for ATM. However, when packet sizes are larger than 48 bytes, more ATM routing decisions need to be made.
Tag switching and flow switching (disclosed by the Proceedings of the Conference on Computer Communications (IEEE Infocom), San Francisco, Calif., March 1996) are two IP bypass methods that are meant to be operated over ATM. The general idea is to let IP control link-level ATM hardware that performs actual data forwarding. Special purpose protocols (disclosed by Request for Comments RFC 1953, Internet Engineering Task Force, May 1996) are needed between routers to agree on what ATM virtual circuit identifiers to use and which packet should use which VCI.
Another approach with the same goal of avoiding IP processing is taken in the IP/ATM architecture (disclosed by the Proceedings of Gigabit Network Workshop, Boston, April 1995; and the Proceedings of ACM SIGCOMM '95, p. 49-58 Cambridge, Mass., August 1995), where an ATM backplane connects a number of line cards and routing cards. IP processing elements located in the routing cards process IP headers. When a packet stream arrives, only the first IP header is examined and the later packets are routed the same way as the first one The main purpose of these shortcuts seems to be to amortize the cost of IP processing over many packets.
IP router designs can use special-purpose hardware to do IP processing, as in the IBM router (disclosed by the Journal of High Speed Networks, 1(4): 281-288, 1993). This can be an inflexible solution. Any changes in the IP format or protocol could invalidate such designs. The flexibility of software and the rapid performance increase of general purpose processors makes such solutions preferable. Another hardware approach is to use CAMs to do routing lookups (disclosed by the Proceedings of the Conference on Computer Communications (IEEE Infocom), volume 3, p. 1382-1391, San Francisco, 1993). This is a fast but expensive solution.
BBN is currently building a pair of multi-gigabit routers that use general purpose processors as forwarding engines. Little information has been published so far. The idea, however, seems to be to use Alpha processors as forwarding engines and to do all IP processing in software. The Publication Gigabit networking, Addison-Wesley, Reading, Mass., 1993, shows that it is possible to do IP processing in no more than 200 instructions, assuming a hit in a route cache. The secondary cache of the Alpha is used as a large LRU (least recently used) cache of destination addresses. The scheme presumes locality in traffic patterns. With low locality, the cache hit rate could become too low and performance would suffer.
SUMMARY OF THE INVENTION
It is therefore an objective of the present invention to provide an improved IP routing lookup method and system for performing full routing lookups for each IP packet up to gigabit speeds, which method and system overcome the above mentioned disadvantages.
A further objective is to increase routing lookup speeds with a
Brodnik Andrej
Carlsson Svante
Degermark Mikael
Pink Stephen
Effnet Group AB
James Ray & Associates
Luu Le Hien
LandOfFree
Fast routing lookup system using complete prefix tree, bit... 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 routing lookup system using complete prefix tree, bit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast routing lookup system using complete prefix tree, bit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2551407