Patent ID: 7085235

Claim:
An IP address construction method used in routers, which records prefixes and next hops corresponding to a routing table by using first-level to fourth-level forwarding tables, comprising the following steps: generating a segment array and a plurality of next hop arrays; dividing said segment array into a plurality of first groups; recording a next hop in a next hop/map column of said first-level forwarding table and recording a null in a pointer column of said first-level forwarding table if all bits of said first group are identical; otherwise, recording a compression bit map in said next hop/map column of said first-level forwarding table and recording an address of said second-level forwarding table in said pointer column of said first-level forwarding table; sequentially and unrepeatedly recording next hops of said segment array in said next hop/pointer column of said second-level forwarding table and recording a null in a longest offset column of said second-level forwarding table if a bit number of said prefix is less than 16; otherwise, recording a pointer in said next hop/pointer column of said second-level forwarding table and recording a longest offset in said longest offset column of said second-level forwarding table; recording next hops in said third-level forwarding table if a longest offset of said first group is greater than 4; otherwise, dividing said next hop array into a plurality of second groups; recording a next hop in said next hop/map column of said third-level forwarding table and recording a null in a pointer column of said third-level forwarding table if all bits of said IP address in said second group are identical; otherwise, recording a compression bit map in said next hop/map column of said third-level forwarding table and recording an address of said fourth-level forwarding table in a pointer column of said third-level forwarding table; and recording a next hop by using said fourth-level forwarding table.