Multiplex communications – Network configuration determination
Reexamination Certificate
2002-01-18
2004-01-20
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Network configuration determination
C370S395310, C370S408000
Reexamination Certificate
active
06680916
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to networking. In particular it relates to routing of data packets between source and destination machines in data-packet networks.
BACKGROUND
In data-packet networks such as TCP/IP networks, packetized data is transmitted between source and destination machines along a route which typically includes many intermediate machines. The task of determining a route for a data packet from a source machine to a destination machine is handled by a router. Typically, a router stores a routing table which includes information on which connections lead to particular groups of addresses, priorities for connections to be used, and rules for handling both routine and special cases of traffic.
A routing table can grow to massive size and complexity. There is therefore, a need to store the routing table in an efficient data structure which can be searched relatively quickly.
One such data structure may be a binary tree data structure. Typically a binary tree data structure includes a number of nodes each of which can have at most two children or child nodes. The node at the top of the tree is called the root node. Any node can be considered to be the root of a sub-tree which consists of its children, its children's children, and so on. Each node is used to hold a data item called a key value. A node having no children is called a leaf node.
A special case of a binary tree is the binary search tree, which has a defining characteristic that a node's left child node must have a key value less than its parent and a node's right child node must have a key value greater than or equal to its parent. It will be appreciated that a search algorithm can be designed which takes advantage of this defining characteristic and searches only the left or right sub-tree of the tree depending on the value of the item being searched.
In implementing a binary search tree to store a routing table, the key value of each node in the routing table corresponds to the network address of a network in the routing table.
One problem associated with using a binary search tree data structure to store a routing table is that the left or right sub-trees may become disproportionately long which results in increased search times. Techniques exist to balance a binary tree by making the left and right sub-trees more or less equal in length. However, as discussed below, balancing could result in a problem when the routing table has, for example, routes to a Class B network and a number of Class C networks each of which is a subnet of the Class B network.
The problem occurs if the Class B network address occurs as a left child node of a Class C network address in the binary search tree. For convenience, the Class B network would be referred to as the supernet and the Class C network as the subnet. Thus, in this example, the supernet is a left child node of the subnet (or alternatively, the subnet is a parent of a supernet left child node). In this case, searching the tree for a logical network covered by the supernet and which has a numerically larger address than the subnet-parent node will fail to find the supernet-child node. This is because the value of the logical network is larger than that of the subnet-parent node, as a result of which the search algorithm will only search the right sub-branch of the tree from the subnet-parent node.
In the prior art this problem is avoided by not balancing the binary tree. As discussed above a problem with this approach is that searching the tree would be less efficient. Another solution is to modify the search algorithm to make sure that subnet will be found. However, this results in the search algorithm also becoming less efficient because the defining characteristic of a binary search tree is no longer used.
There is therefore a need for storing a routing table using a balanced binary tree data structure in which the above problem does not occur.
In this specification the term subnet will be used to refer to any logical network which is a subnet of another network which will be referred to as a supernet hereinafter.
SUMMARY OF THE INVENTION
The invention provides a method of storing a routing table having a plurality of routes associated with a plurality of networks, each being identified by a network address. The method includes constructing a binary tree data structure in which a key value of each node in the binary tree data structure corresponds to a network address of a network of the plurality of networks; and rearranging the binary tree data structure so that any node having a key value which is a supernet of a network corresponding to the key value of any other node in the binary tree data structure becomes a parent of such other node.
REFERENCES:
patent: 6018524 (2000-01-01), Turner et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6385649 (2002-05-01), Draves et al.
patent: 6452908 (2002-09-01), Yamada et al.
patent: 6516319 (2003-02-01), Benayoun et al.
International Search Report-PCT/US02/01744, May 17, 2002.
Blakely , Sokoloff, Taylor & Zafman LLP
Tut Systems, Inc.
Yao Kwang Bin
LandOfFree
Method for using a balanced tree as a base for a routing table 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 for using a balanced tree as a base for a routing table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for using a balanced tree as a base for a routing table will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195268