Forwarding information retrieval technique

A method for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, the method comprising the steps of;

• a) providing a plurality of first tables T1_i (i is a positive integer) and a second table T2 in the retrieval table,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages s(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a second-table pointer is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is needed, and wherein a first-table pointer indicating a first table of a stage S(j+1) following a current stage S(j) is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is not needed, and
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j);
• b) dividing the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages s(j);
• c) accessing a first table T1_1 of the stage S(1) to retrieve a first entry E1_1 using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1);
• d) accessing a second entry E2_1 of the second table T2 according to a second-table pointer included in the first entry E1_1;
• e) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, accessing a first table T1_i indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the first table T1_1 as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_1:
• f) when a retrieved first entry E1_k includes a first-table pointer, directly accessing a first table T1_i indicated by a first-table pointer included in the retrieved first entry E1_k without accessing the second table to retrieve a first entry E1_k from the directly accessed first table T1_k using a destination divisional bit string of a stage corresponding to the directly accessed first table T1_i as a retrieval key;
• g) accessing another second entry E2_m of the second table T2 according to a second-table pointer included in the retrieved first entry E1_k;
• h) repeating the steps (e) and (g) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval;
• and
• i) when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, reading a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.

A retrieval apparatus for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, comprising:

• a first storage section for storing a plurality of first tables T1_i (i is a positive integer);
• a second storage section for storing a second table T2;
• a first control section for controlling access to the first storage section;
• and a second control section for controlling access to the second storage section, wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a first entry having an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables includes a second-table pointer,
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j),
• the second control section divides the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j) and sequentially sends the destination divisional bit strings DST(j) to the first control section,
• the first control section accesses a first table T1_1 of the stage S(1) to retrieve a first entry E1_1 using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1), and sends a second-table pointer included in the first entry E1_1 to the second control section,
• the second control section accesses a second entry E2_1 of the second table T2 according to the second-table pointer received from the first control section and, when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, sends a first-table pointer included in the second entry E2_m to the first control section, the first control section accesses a first table T1_i indicated by the first-table pointer received from the second control section, retrieves a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i, and sends a second-table pointer included in the retrieved first entry E1_k to the second control section, and the second control section accesses another second entry E2_m of the second table T2 according to the second-table pointer received from the first control section,
• wherein when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, the first control section repeatedly reads a second-table pointer from a first entry having an offset address matching the destination divisional bit string of a corresponding stage, and sends the read second-table pointer to the second control section and, when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, the second control section reads a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.

A retrieval apparatus for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, comprising:

• a first storage section for storing a plurality of first tables T1_i (i is a positive integer);
• a second storage section for storing a second table T2;
• a first control section for controlling access to the first storage section;
• and
• a second control section for controlling access to the second storage section,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a second-table pointer is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is needed, and wherein a first-table pointer indicating a first table of a stage S(j+i) following a current stage S(j) is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is not needed,
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j),
• the second control section divides the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j) and sequentially sends the destination divisional bit strings DST(j) to the first control section,
• the first accesses a first table T1_1 of the stage S(1) to retrieve a first entry R1 is using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1), and sends a second-table pointer included in the first entry E1_1 to the second control section,
• the second control section accesses a second entry E2_1 of the second table T2 according to the second-table pointer received from the first control section,
• when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, the first control section accesses a first table T1_i indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_1 using a destination divisional bit string of a stage corresponding to the first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i, and sends a second-table pointer included in the retrieved first entry E1_k to the second control section,
• when a retrieved first entry E1_k includes a first-table pointer, the first control section directly accesses a first table T1_i indicated by a first-table pointer included in the retrieved first entry E1_k without accessing the second table to retrieve a first entry E1_k from the directly accessed first table T1_k using a destination divisional bit string of a stage corresponding to the directly accessed first table T1_1 as a retrieval key, and sends a second-table pointer included in the retrieved first entry E1_k to the second control section.
• the second control section accesses another second entry E2_m of the second table T2 according to the second-table pointer received from the first control section,
• wherein when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, the first control section repeatedly reads a second-table pointer from a first entry having an offset address matching the destination divisional bit string of a corresponding stage, and sends the read second-table pointer to the second control section and, when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, the second control section reads a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.

A recording medium storing a retrieval table which is used in a network node to retrieve a hop pointer using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination,

• the retrieval table comprising a plurality of first tables T1_i (i is a positive integer) and a second table T2,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a first entry having an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables includes a second-table pointer and
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j).

A recording medium storing a retrieval table which is used in a network node to retrieve a hop pointer using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination,

• the retrieval table comprising a plurality of first tables T1_i (i is a positive integer) and a second table T2,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a second-table pointer is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is needed, and wherein a first-table pointer indicating a first table of a stage S(j+1) following a current stage S(j) is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is not needed, and
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j).

A recording medium storing a retrieval program to be executed by a computer in a network node to retrieve a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, the retrieval program comprising the steps of:

• a) providing a plurality of first tables T1_i (i is a positive integer) and a second table T2 in the retrieval table,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a first entry having an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables includes a second-table pointer.
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-stable pointer indicates a first table of a stage S(j+1) following a current stage S(j);
• b) dividing the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j);
• c) accessing a first table T1_1 of the stage S(1) to retrieve a first entry E1_1 using a high-order destination divisional bit string DST(L) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1);
• d) accessing a second entry E2_1 of the second table T2 according to a second-table pointer included in the first entry E1_1,
• e) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, accessing a first-table T1_1 indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the;first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i:
• f) accessing another second entry E2_m of the second table T2 according to a second-table pointer included in the retrieved first entry E1_k;
• g) repeating the steps (e) and (f) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval;
• and
• h) when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, reading a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.

A recording medium storing a retrieval program to be executed by a computer in a network node to retrieve a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, the retrieval program comprising the steps of:

• a) providing a plurality of first tables T1_i (i is a positive integer) and a second table T2 in the retrieval table,
• wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a second-table pointer is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is needed, and wherein a first-table pointer indicating a first table of a stage S(j+1) following a current stage S(j) is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is not needed, and
• wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j);
• b) dividing the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j);
• c) accessing a first table T1_1 of the stage S(1) to retrieve a first entry E1_1 using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1);
• d) accessing a second entry E2_1 of the second table T2 according to a second-table pointer included in the first entry E1_1;
• e) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, accessing a first table T1_i indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i;
• f) when a retrieved first entry E1_k includes a first-table pointer, directly accessing a first table T1_i indicated by a first-table pointer included in the retrieved first entry E1_k without accessing the second table to retrieve a first entry E1_k from the directly accessed first table T1_k using a destination divisional bit string of a stage corresponding to the directly accessed first table T1_i as a retrieval key;
• g) accessing another second entry E2_m of the second table T2 according to a second-table pointer included in the retrieved first entry E1_ks;
• h) repeating the steps (e) and (g) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval;
• and
• i) when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, reading a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.

A method for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, the method comprising the steps of:

• a) storing a plurality of first tables and a second table in the retrieval table,
• wherein the first tables are hierarchically arranged according to division of the destination address, an entry of each of the first tables including a second-table pointer indicating a next accessed second entry of the second table, and
• wherein the second table serves as an index table of the first tables, wherein each of entries of the second table includes a hop pointer and a first-table pointer indicating a next accessed first table;
• b) alternately accessing the second table and a selected one of the first tables depending on a first-table pointer included in an accessed entry of the second table while retrieving an entry of an accessed first table using a corresponding divisional portion of the destination address;
• and
• c) reading a hop pointer from a finally accessed entry of the second table as a retrieval result.