| 摘要 |
<p>PROBLEM TO BE SOLVED: To decrease the number of bits needed for one entry of the routing table by storing information on the difference between the IP address of a master node and the IP address of a slave node in a Patricia tree in the routing table and retrieving routing information on the destination IP address that an IP packet has. SOLUTION: A deformed tree is constituted, by converting an 8-bit length Patricia tree into 4-bit length difference information. In the routing table corresponding to the deformed tree, the difference 01** between an entry B and an entry A as its parent node is stored as difference information of a table of, for example, the entry B and the number 2 of effective bits of the difference is stored. Furthermore, the difference 11111111 between the entries A and E cannot be represented with four bits, so that a repeating node F is inserted between the entries A and E. Consequently, the deformed tree obtained by converting the Patricia tree and the routing table can be generated to reduce the memory quantity.</p> |
