Patent ID: 6788695
Filing Date: 2004-09-07
Classification: H04L

Abstract:
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.