Method and apparatus for constructing and searching IP address
AssigneeAccton Technology Corporation
InventorShou-Yu Pin
Life of this patent
Estimating the term…
Abstract
The present invention discloses an IP address construction and lookup method and apparatus used in routers, which uses a compress technology to reduce memory size occupied by a segment array and a plurality of next hop arrays used in an indirect lookup table method, and also reduce the number of memory accesses from 1 to 4 times. Besides, only one memory access is required if a pipeline scheme is in use. In addition, when the routing table is updating, it is unnecessary to rebuild the forwarding table and capable of finishing newer actions.
Claims8
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.
Dependencies are inferred from the claim text.