Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-12-30
2003-07-08
Ngo, Ricky (Department: 2697)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S408000, C370S475000, C709S242000
Reexamination Certificate
active
06590898
ABSTRACT:
FIELD OF INVENTION
The present invention relates generally to the field of transmitting data packets on a wide-area data communication network such as the Internet. More particularly, the present invention relates to routing data packets by using the destination address field of a data packet to retrieve an output port address from a trie data structure.
BACKGROUND OF THE INVENTION
In the data communication network known as the Internet, a device known as a router routes data packets. The router may be connected to (1) a local area network composed of host computers and/or (2) a plurality of other routers. Each data packet originates at a specific computer and may include voice, music, full-motion video or data information. The data packet is then transmitted from one router to another by action of the circuitry of the routers. Eventually, the data packet is transmitted to a router that is directly connected to the computer that is the intended recipient of the data packet.
A central problem in designing a router is maximizing the efficiency of the router in determining the proper output port address for the router to use in transmitting the presented data packet. This process should occur using a minimum of clock cycles, otherwise the presented data packet would have to be stored while awaiting processing. (This storage or buffering would increase the hardware cost of the router.)
In the simplest form of routing, the circuitry of the router would have the capability to determine the appropriate output port address for every possible destination address field of a presented data packet. Although such an approach was viable in the early days of the Internet, it is no longer a useful option given the present size of the Internet. As an alternative, several different techniques have been used such as binary trees, b-trees and hash tables. Most of these techniques do not attempt to associate an output port address with the entire destination address field but with one or more of the most significant bits of the destination address. (The binary number represented by one or more of the most significant bits of the destination address field is commonly referred to in the prior art as a prefix.) More specifically, these techniques use the longest prefix for which there is an associated output port address as the basis for selecting the output port address for transmitting the presented data packet.
As an example of the functioning of one of these techniques, assume that a data packet contains a destination address field that includes the four bit number ‘1011’ as its most significant bits. Four of the possible prefixes of the destination address field of this data packet are ‘1’, ‘10’, ‘101’ or ‘1011’. Further assume that the circuitry of the router has access to a database that contains each output port address associated with each of these prefixes. Although there are several output port addresses associated with this single destination address field, the circuitry of the router transmits the presented data packet in accordance with the output port address that is associated with the prefix that is the longest of the various prefixes. Accordingly, the presented data packet would be transmitted to the router associated with the output port address that is associated with the prefix ‘1011’. If the data base did not contain an output port address associated with the prefix ‘1011’, then the output port address associated with ‘101’ would be used. If the data base did not contain an output port address associated with the prefix ‘101’, then the process continues in similar fashion using the shorter prefixes. If there were no output port addresses associated with any prefix of the destination address field of the presented data packet, then the router may use a default output port address.
The reason that the longest prefix is selected is because the longest prefix contains the most information about the ultimate destination of the data packet, and accordingly the output port address associated with the longest prefix is the best choice in light of the information available.
The goal then in designing algorithms in the field to which the present invention pertains is to develop an algorithm that most efficiently (1) determines the longest prefix from the destination address field for which there is an associated output port address and (2) retrieves that associated port address for use by the circuitry of the router in transmitting the presented data packet.
One common algorithm in the prior art that is designed to satisfy the two above goals uses the data structure commonly known as a “trie” data structure. The trie data structure is a type of tree data structure. The trie data structure has a root node, intermediate level nodes and external leaf nodes. Each node consists a predetermined plurality of words. Each word is composed of a predetermined plurality of bits. The plurality of bits in each word is divided into fields.
In one embodiment in the prior art, each word contains the following fields:
The stop flag field, which indicates to the circuitry of the router if retrieval stops at the node that holds the word or should continue to a higher level node whose address is contained in the forward pointer field, which is discussed below.
The valid flag field, which indicates to the circuitry of the router whether the output port address contained in this word is valid.
The output port address field, which contains, if appropriate, the output port address of the next router to which the presented data packet would be transmitted, in appropriate circumstances by the action of the circuitry of the router.
The children counter field, which indicates to the circuitry of the router the number of words in the node that contain useful information. In this context, useful information is either a word with a valid output port address (that is, the valid flag field is set to ‘1’) or a word with a valid forward pointer field. In the latter case, the stop flag field would be set to ‘0’. The children counter field is contained only in the first word of the relevant node.
The forward pointer field, which contains, if appropriate, the address of the next node of the trie data structure in the memory of the circuitry of the router if the stop bit is not ‘1’.
This trie data structure supports the actions of the circuitry of a router in (1) retrieving an output port address from the trie data structure, (2) inserting an output port address into the trie data structure and (3) deleting an output port address from the trie data structure.
In accordance with a common technology in the prior art, the destination address field of the presented data packet is parsed by the action of the circuitry of the router into several smaller binary numbers of an equal predetermined length. (For purposes of this specification and claims, each of the smaller binary numbers is referred to as a substring.) For example, if the predetermined length was 4 bits, then a 32 bit destination address would be broken into 8 substrings each of 4 bits.
The number of words in each node is equal to 2 raised to the predetermined number of bits in each substring, and each substring is an address to a word in the appropriate node (This number is referred to in this specification and claims as the “dimension” of the node.) The circuitry of the router first processes the word in the root node whose address is the initial substring. If the valid flag field of that word is ‘1’, then the binary number stored in the output port address field of that word is stored in an internal register, so that at any point the last valid output port address is available to the circuitry of the router. If the stop flag field of that word is also ‘1’, then the output port address used in transmitting the presented data packet is the output port address stored in the output port address field of that word. If the stop flag field is ‘0’, then a word of the next higher-level node is processed by the circuitry of the router. The address of that node is stored in the
Ha Yvonne Q.
Klauber & Jackson
New Jersey Institute of Technology
Ngo Ricky
LandOfFree
Method and apparatus for routing data packets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for routing data packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for routing data packets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3017816