System and method capable of carrying out high-speed IP routing by the use of a binary tree comprising a reduced number of nodes
AssigneeNEC Corporation
InventorShinya Nagasawa
Life of this patent
Estimating the term…
Abstract
A high-speed IP routing system (1) for searching a best route for an object IP address by the use of a binary tree comprises a volatile memory (15) storing the binary tree exclusively comprising a plurality of route nodes each of which has route information, a next node selection circuit (2) 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 (15), and an adopted route determining circuit (4) for comparing the route information of each of the selected nodes selected by the next node selection circuit (2) and the object IP address to determine an adopted route IP address to be adopted as a next route.
Claims5
A high-speed IP routing system for searching a best route for an object IP address by the use of a binary tree, said system comprising:
- a volatile memory storing said binary tree comprising a plurality of route nodes each of which has route information, said route nodes comprising comparison branch nodes and bit branch nodes;
- a next node selection circuit for successively selecting, with respect to said object IP address, every next one of the route nodes as selected nodes starting from a root node of said binary tree stored in said volatile memory;
- an adopted route determining circuit for comparing said route information of each of said selected nodes and said object IP address to determine an adopted route IP address to be adopted as a next route;
- wherein said route information comprises identification of a node type, an IP address of the node, a mask length, and an adopted route IP address;
- said node type including the comparison branch node and the bit branch node;
- each said comparison branch node and said bit branch node satisfying a condition that a parent node has a mask length not longer than that of a child node;
- each said comparison branch node satisfying a condition that a bit sequence of said 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 said parent node;
- and
- each said bit branch node satisfying a condition that a bit sequence of said 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 said 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 said left and said right child nodes, respectively, where k is equal to the mask length plus one.
A high-speed IP routing method of searching a best route for an object IP address by the use of a binary tree, said method comprising the steps of:
- making a volatile memory store said binary tree comprising a plurality of route nodes each of which has route information, said route nodes comprising comparison branch nodes and bit branch nodes;
- successively selecting, with respect to said object IP address, every next one of the route nodes as selected nodes starting from a root node of said binary tree stored in said volatile memory;
- comparing said route information of each of said selected nodes selected in said selecting step and said object IP address to determine an adopted route IP address to be adopted as a next route,
- wherein said route information comprises identification of a node type, an IP address of the node, a mask length, and an adopted route IP address;
- said node type including the comparison branch node and the bit branch node;
- each said comparison branch node and said bit branch node satisfying a condition that a parent node has a mask length not longer than that of a child node;
- each said comparison branch node satisfying a condition that a bit sequence of said 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 said parent node;
- and
- each said bit branch node satisfying a condition that a bit sequence of said 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 said 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 said left and said right child nodes, respectively, where k is equal to the mask length plus one.
Dependencies are inferred from the claim text.