Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-08-23
2004-09-07
Ha, Yvonne Quy (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S351000, C370S389000, C370S392000
Reexamination Certificate
active
06788695
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to an IP (Internet Protocol) routing system and, in particular, to a high-speed IP routing system utilizing a binary tree comprising a plurality of nodes. This invention also relates to an IP routing method executed by the above-mentioned system.
When an IP packet is transferred, an IP routing (or IP route look-up) operation is traditionally carried out on a software basis.
Referring to
FIG. 1
, description will be made of a binary tree for use in a conventional software-based IP routing technique.
When the binary tree is created from a routing table, a destination network address in each route entry is recognized simply as a bit sequence. For example, the binary tree illustrated in
FIG. 1
is used in FreeBSD to search a route corresponding to CIDR (Classless Inter-Domain Routing).
Every node (hereinafter may be referred to as a parent node) forming the binary tree is branched to at most two nodes (hereinafter may be referred to as child nodes).
The nodes contained in the binary tree are classified into route nodes having route information and repeater nodes having no route information and used exclusively for branching.
The number of the repeater nodes never exceeds the number of the route nodes. Therefore, the total number of the nodes required to form the binary tree is up to about twice the number of route entries.
In case where a plurality of matches are found, a route node with a shorter mask is located at a branch point between a root node and a leaf node while all other route nodes are leaf nodes.
Each node is assigned with a check bit number. The check bit number represents a bit position of a check bit for judgment about which one of the child nodes is to be selected as a branch for each node.
In a search algorithm (Forward Search) used in the software-based IP routing technique, selection of a child node is repeated until a lowermost node is reached as a reached node. Then, comparison is carried out between an object IP address to be subjected to routing and an IP address of the reached node. Upon coincidence, i.e., if a match is found, route information possessed by the reached node is adopted. Upon incoincidence, i.e., if a match is not found, routing or route look-up proceeds to another node linked upward from the reached node to perform a similar operation.
In the example illustrated in
FIG. 1
, the object IP address is “85.05.17.11”. In this event, the routing starts from a root node A, proceeds through nodes B, C, D, and E, and reaches a leaf node F at the bottom. Because of incoincidence between the object IP address and the IP address of the leaf node F, the routing proceeds to the node E. Eventually, the route information possessed by the node E is adopted.
Following the recent spread of the internetworking, an IP packet transfer apparatus equipped in a backbone network is required to have an ability of carrying out a routing operation at an extremely high speed on a high-speed interface such as OC (Optical Carrier level)12/OC48.
Under the circumstances, the above-mentioned software-based IP routing technique using the Forward Search algorithm is disadvantageous in that high-speed routing is inhibited by useless transfer between the nodes (in the illustrated example, from the node E to the node F and then from the node F to the node E).
The binary tree looked up in the above-mentioned software-based IP routing technique includes the repeater nodes having no route information. Possibly, one repeater node is added every time when one route entry is added.
Therefore, the number of nodes contained in the binary tree is increased so that the operation becomes complicated and time-consuming.
SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide a high-speed IP routing system and a high-speed IP routing method capable of reducing the number of nodes included in a binary tree and carrying out a routing operation at a high speed.
According to this invention, a high-speed IP routing system for searching a best route for an object IP address by the use of a binary tree comprises a volatile memory storing the binary tree exclusively comprising a plurality of route nodes each of which has route information, a next node selection circuit for successively selecting, with respect to the object IP address, every next nodes as selected nodes starting from a root node of the binary tree stored in the volatile memory, and an adopted route determining circuit for comparing the route information of each of the selected nodes selected by the next node selection circuit and the object IP address to determine an adopted route IP address to be adopted as a next route.
In the above-mentioned system, the binary tree does not include any repeater node having no route information, unlike the binary tree used in the conventional software-based IP routing technique. Therefore, the number of nodes can be reduced to a half at minimum. It is therefore possible to increase the number of route entries or to implement the system by the use of a small-capacity RAM.
Preferably, each node in the binary tree stored in the volatile memory has, as the route information, identification of a node type, an IP address of the node, a mask length, and an adopted route IP address. The node type is either a comparison branch node or a bit branch node. Each of the comparison branch node and the bit branch node satisfies a condition that a parent node has a mask length not longer than that of a child node. The comparison branch node satisfies a condition that a bit sequence of the parent node is coincident with a masked bit sequence obtained by masking a bit sequence of one of left and right child nodes with a mask of the parent node. The bit branch node satisfies a condition that a bit sequence of the parent node is coincident with a masked bit sequence obtained by masking a bit sequence of one of left and right child nodes with the mask of the parent node and that a k-th bit from a most significant bit as a first bit has “0” and “1” in one and the other of the left and the right child nodes, respectively, where k is equal to the mask length plus one.
In the above-mentioned system, each node of the binary tree is classified into the comparison branch node and the bit branch node so that the number of nodes can be reduced up to a half.
Preferably, if the selected node selected by the next node selection circuit is the comparison branch node, comparison is made between a masked result obtained by masking the object IP address with a mask of the mask length of the selected node and the IP address of the selected node to judge coincidence or incoincidence. The selected node is branched to one and the other of the left and the right child nodes upon coincidence and upon incoincidence, respectively, to continue searching or routing. If the selected node selected by the next node selection circuit is the bit branch node, comparison is made between a masked result obtained by masking the object IP address with a mask of the mask length of the selected node and the IP address of the selected node. Upon coincidence, the selected node is branched to one and the other of the left and the right child nodes when a k-th bit has “0” and “1”, respectively, where k is equal to the mask length plus one.
With the above-mentioned system, a search algorithm is improved, taking into account the use of simultaneous processing of next node selection and address comparison, to eliminate useless transfer between the nodes caused by the Forward Search used in the conventional software-based routing technique.
Preferably, the above-mentioned adopted route determining circuit produces, if coincidence is detected in the above-mentioned comparison, the adopted route IP address of the selected node as a next route. If the comparison branch node or the bit branch node does not have the left or the right child node to be a branch node upon selection by the next node selection circuit or if incoincidence is detected in the comparison for the bit branch node, search
Ha Yvonne Quy
NEC Corporation
LandOfFree
System and method capable of carrying out high-speed IP... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method capable of carrying out high-speed IP..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method capable of carrying out high-speed IP... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3230331