Address retrieval apparatus

1. An address retrieval apparatus including:

a divided bit string generating unit for dividing an original bit string into a plurality of divided bit strings, each of which has one of plural different hierarchical levels, said original bit string providing a route information which defines a route to a final destination for data transmission through a communication network;

a transfer destination distribution information storage unit for storing a transfer destination distribution information which indicates a distributed transfer destination for data transmission in accordance with said route information;

a retrieval table including a hierarchical tree structure which comprises said divided bit strings and plural retrieval table nodes, wherein each of said plural retrieval table nodes further includes at least one of a next retrieval table node designation information indicating a next retrieval table node based on corresponding one of said divided bit strings and a transfer destination distribution information storage location designation information designating a location at which said transfer destination distribution information is stored in said transfer destination distribution information storage unit;

a hierarchy definition unit for shifting up by one level a hierarchy level of said retrieval table node to execute a retrieval process with reference to said retrieval table node until said hierarchy definition unit retrieves said transfer destination distribution information storage location designation information from said retrieval table node, and said hierarchy definition unit defining one hierarchy level upon retrieval of said transfer destination distribution information storage location designation information; and

a transfer destination distribution information acquiring unit for acquiring said transfer destination distribution information from said retrieval table node based on said transfer destination distribution information storage location designation information retrieved by said hierarchy definition unit from said retrieval table node with said defined hierarchy level.

2. The address retrieval apparatus as claimed in claim 1 , wherein said divided bit string generating unit divides said original bit string from a head to a tail of said original bit string in accordance with a predetermined bit length rule for each of said plural different hierarchical levels, and fetches said divided bit strings in a sequence from said head to said tail, so that said divided bit strings in said sequence from said head to said tail respectively correspond to said plural different hierarchical levels in a sequence of a bottom level to a top level.

3. The address retrieval apparatus as claimed in claim 2 , wherein said hierarchy definition unit executes said retrieval process in said sequence of said bottom level to said top level of said plural different hierarchical levels by use of said divided bit strings in said sequence from said head to said tail.

4. The address retrieval apparatus as claimed in claim 1 , wherein said hierarchy definition unit shifts up by one level said hierarchy level, during said next retrieval table node designation information is read out of a retrieval table node with a first hierarchical level.

5. The address retrieval apparatus as claimed in claim 1 , wherein only said retrieval table node necessary for storing said next retrieval table node designation information includes a storage area for storing said next retrieval table node designation information, and said retrieval table node unnecessary for storing said next retrieval table node designation information is free of said storage area.

6. The address retrieval apparatus as claimed in claim 1 , wherein each of said retrieval table nodes at all of said hierarchical levels includes an additional information which indicates a presence or an absence of said retrieval table node having a next hierarchical level which is higher by one level than its hierarchical level of said each retrieval table node.

7. The address retrieval apparatus as claimed in claim 1 , wherein said transfer destination distribution information storage location designation information includes an area storing said transfer destination distribution information in said transfer destination distribution information storage unit, and an address which designates a storage location of said transfer destination distribution information in said area.

8. The address retrieval apparatus as claimed in claim 7 , wherein the number of addresses possessed by said area is equal to the square of a bit number of corresponding one of said divided bit strings.

9. The address retrieval apparatus as claimed in claim 1 , wherein said divided bit strings have a uniform bit number.

10. The address retrieval apparatus as claimed in claim 1 , wherein

said divided bit string generating unit further comprises a plurality of divided bit string generating sub-units which correspond to said plural different hierarchical levels,

said hierarchy definition unit further comprises a plurality of hierarchy definition sub-units which correspond to said plural different hierarchical levels,

said retrieval table further comprises a plurality of retrieval sub-tables which correspond to said plural different hierarchical levels, and

said divided bit string generating sub-units, said hierarchy definition sub-units and said retrieval sub-tables make plural sets which correspond to said plural different hierarchical levels, so that said plural sets perform parallel processings for said plural different hierarchical levels.

11. The address retrieval apparatus as claimed in claim 1 , wherein said transfer destination distribution information acquiring unit includes an off-set pointer calculation unit for calculating an off-set point, which designates a storage location of a bit string in one of nodes of said transfer destination distribution information storage unit, based on a retrieval result supplied from said hierarchy definition unit.