Patent ID: 6618760
Filing Date: 2003-09-09
Classification: H04L

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