Multiplex communications – Network configuration determination
Reexamination Certificate
1997-08-29
2003-04-22
Martin-Wallace, Valencia (Department: 3713)
Multiplex communications
Network configuration determination
C370S351000
Reexamination Certificate
active
06553002
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to data communications systems, and more particularly to an apparatus and method for routing data packets through a communications system.
In most networks, data at one location cannot be directly sent to another location without passing through multiple network nodes. For example, a telephone or data communications system may not provide a direct connection between a source node in California and a destination node in Sweden. Instead, a path that may pass through a number of data routers must be determined to establish a connection between the two locations. A routing table may store information at each router about the next routers in the path, correlating a destination number or address with the next router in the path. At each intermediate node location on the path, the routing table is examined to determine the next node on the path. And in each case only the next node in the path is generally stored, since the alternative of storing the entire sequence of nodes for each of the multiple possible paths through the network for all nodes in the network would require a large amount of memory. Using these routing tables located at each node in the network, data may be routed from a source to a destination by hopping between various nodes. Routing at nodes in a computer network is accomplished by routers.
The time spent examining each routing table at each node translates into delays, for example, in establishing a connection between one caller and another, or in transferring data from one computer to another computer. Since each router in a data path must search its own routing table to determine the next location in the path, this delay is multiplied by the number of routers along the path of the data. On systems as complex as the Internet, where approximately 100,000 networks connect 10 million computers, and where a data packet may be sent through dozens of routers, the time spent examining routing tables can cause considerable delays. In addition, on a network like the Internet, which is expected to grow and support 500,000 networks and 50 million computers within a few years, the delays associated with the route table look-ups are likely to increase dramatically.
These route table look-up delays and an attempt to do less than a full route table look-up can cause significant problems. Each router in a network may have a predetermined amount of memory available to store data packets (e.g., a queue) while the route table look-up process occurs since the route table look-up may not occur as fast as data packets are entering the router. A very slow route table look-up process may cause the memory to overflow because there are too many data packets waiting for the route table look-up process. This queue memory overflow may cause data packets to be lost or discarded which requires those data packets to be resent.
Some conventional routers use software-implemented search engines to determine the next location in a path. The routers use a microprocessor to receive data packets from remote locations, to process the data packet header, to search the routing tables for the next location along the path, and to perform other functions. These microprocessors may execute specific search algorithms intended to perform the search faster than other methods. Although, these software implemented search algorithms decrease route table search times, these software implemented algorithms are still too slow to handle the anticipated growth of the Internet. In addition, the microprocessor may be tied up while performing the route table search and thus cannot perform other tasks while this search is taking place.
Other conventional routers use a cache memory to store only a portion of a full routing table in an effort to decrease the time needed to search through the routing table. These systems generally require less memory to store a routing table, and because there is less information in the abbreviated routing table to process, it potentially takes less time to examine these cache-based routing tables. However, these cache-based systems have proven inefficient because there are so many different data paths on a network, such as the Internet, that entries in the routing table corresponding to the desired path are found in the cache only a fraction of the time. In addition, infrequently-used entries are rarely found in the abbreviated routing table, since conventional methods used to maintain these cache-based routing tables remove infrequently used paths in favor of entries for paths that are more often or more recently used. When an entry is not found in the cache, it must be fetched from memory, adding to the delays in determining a next location in the path.
For the above reasons, there is need to quickly determine next addresses in a path using a full routing table which avoids the above problems with conventional systems, and it is to this end that the present invention is directed.
SUMMARY OF THE INVENTION
The invention provides an apparatus and method for rapidly routing data packets through a communications network and for rapidly traversing a routing table in a router to determine a next router in a path of a data packet as it moves towards a destination computer. The routing table may be stored as a binary tree in a router's memory. The nodes of the binary tree may correspond to bits in the destination address, and the leaves may correspond to the physical address of a next router on the path. The next router in a path is determined by traversing the binary tree and reading a router address stored in a leaf node. In one aspect of the present invention the system and method use a particular unique data structure for the nodes and leaves in the binary tree so that only a single memory cycle is required to traverse each node. This may be accomplished by storing, in each node, a decision bit for its child, i.e., path to the next node in the binary tree, which determines whether the right branch or the left branch is taken from the child.
In another aspect of the invention, the apparatus used to traverse the routing table uses a dedicated hardware search engine to perform the search. By using a dedicated hardware search engine, the apparatus allows the main microprocessor in the router to perform other tasks while the hardware search engine is performing the route table search.
In accordance with the invention, a master microprocessor is used to control a hardware search engine that it used to traverse a routing table stored as a search tree, also known as a search trie, to produce the address of a router in path to which a data packet is to be sent. The search tree or trie may be a compressed special radix tree or a Patricia tree. The master microprocessor communicates data about the radix tree to the hardware search engine and can then go about performing other tasks while the hardware search engine traverses the radix tree in the background. The hardware search engine traverses each node in the radix tree in one memory cycle because of a unique data structure used to store each node of the radix tree. The decision bit for each node is stored in its parent node, so that when a node is traversed, the decision of which child node to branch to next has already been determined, and thus only one memory cycle is needed to traverse each node. The leaves of the radix tree store information about a next router that the data packet may be sent to. When a leaf is reached, the physical address of the next router may be determined and the data packet sent to the next router on its way to a destination address.
REFERENCES:
patent: 4933846 (1990-06-01), Humphrey et al.
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5463777 (1995-10-01), Bialkowski et al.
patent: 5546390 (1996-08-01), Stone
patent: 5598410 (1997-01-01), Stone
patent: 5787430 (1998-07-01), Doeringer et al.
Bremer Clark
Gunderson Marlon
Severns Christine E.
Ascend Communications, Inc.
Martin-Wallace Valencia
Nguyen Kim T.
LandOfFree
Apparatus and method for routing data packets through a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for routing data packets through a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for routing data packets through a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3055914