Address translation method and system having a forwarding table data structure
First Claim
1. A memory for storing data for access by an application program being executed on an address translation system, comprising:
- a data structure stored in said memory, said data structure including information resident in a database used by said application program and including;
a plurality of blocks, each of the plurality of blocks includes a contiguous set of data records;
each data record includes a pointer and an action indicator;
if the action indicator is equal to a prescribed value the pointer represents an address of a translation target in the data structure; and
if the action indicator is not equal to the prescribed value the pointer represents an address of a selected one of the plurality of blocks in the data structure.
10 Assignments
0 Petitions
Accused Products
Abstract
A forwarding table data structure and a memory optimization process that involves variable multi-stage lookups. The data structure for an address translation system includes, a plurality of blocks, each of the plurality of blocks includes a contiguous set of data records; each data record includes a pointer and an action indicator; if the action indicator is equal to a prescribed value the pointer represents an address of a translation target in the data structure; and if the action indicator is not equal to the prescribed value the pointer represents an address of a selected one of the plurality of blocks in the data structure. The data structure is built based on the input data set (e.g. IP routing table) to be memory optimized. The number of stages can be flexibly determined based on memory restrictions, input data set etc. Since the data structure is essentially “customized” optimal routing speeds can be obtained.
-
Citations
30 Claims
-
1. A memory for storing data for access by an application program being executed on an address translation system, comprising:
-
a data structure stored in said memory, said data structure including information resident in a database used by said application program and including;
a plurality of blocks, each of the plurality of blocks includes a contiguous set of data records;
each data record includes a pointer and an action indicator;
if the action indicator is equal to a prescribed value the pointer represents an address of a translation target in the data structure; and
if the action indicator is not equal to the prescribed value the pointer represents an address of a selected one of the plurality of blocks in the data structure. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. An address translation system executing an application program and containing a routing table used by said application program, said address translation system comprising:
-
CPU means for processing said application program; and
memory means for holding a data structure for access by said application program, said data structure being composed of information resident in said routing table used by said application program and including;
a plurality of objects, each of the plurality of objects includes a set of data records;
each data record includes a pointer and an action indicator;
if the action indicator is equal to a prescribed value the pointer represents an address of a translation target in the data structure; and
if the action indicator is not equal to the prescribed value the pointer represents an address of a selected one of the plurality of objects in the data structure. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method of translating an X-bit address to a resource index selected from a plurality of resource indices where 2X exceeds the number of resource indices comprising the steps of:
-
(a) using a first bit offset value A representing A most significant bits of the X-bit address as a first offset into a first lookup table containing 2A entries where each entry includes a pointer and an action indicator;
said pointer represents (i) an address to one of a plurality of second lookup tables when the action indicator is greater than a prescribed value indicating that an address to a second level table is required and (ii) one of the plurality of resource indices when the action indicator is equal to the prescribed value indicating that the X-bit address has been translated;
(b) using the action indicator to determine a second bit offset value B representing B bits following the A most significant bits of the X-bit address; and
(c) using the second bit offset B to select the next B bits following the A most significant bits of the X-bit address as a second offset to a selected second lookup table, the selected second table containing 2B entries. - View Dependent Claims (29, 30)
-
Specification