Address translation method and system having a forwarding table data structure

• US 6,243,720 B1
• Filed: 07/14/2000
• Issued: 06/05/2001
• Est. Priority Date: 07/08/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Depelteau, Gary Michael, Munter, Ernst A.
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US09/616,880
• Time in Patent Office: 326 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 711/100-173, 711/200-221
• US Class Current: 707/741
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/255 Maintenance or indexing of mapping tables
• CPC Class Codes: H04Q 2213/1305 Software aspects
• CPC Class Codes: H04Q 2213/13097 Numbering, addressing
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99957 Garbage collection

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.

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.

2. The memory of claim 1, wherein the action indicator is an integer value.

3. The memory of claim 2, wherein the prescribed value is zero.

4. The memory of claim 3, wherein the integer value represents a size of the selected one of the plurality blocks when the action indicator is not equal to zero.

5. The memory of claim 4, wherein the size of the selected one of the plurality of blocks is equal to 2 to the power of the integer value.

6. The memory of claim 2, wherein the integer value is a logarithm to the base of 2 of a size of the selected one of the plurality of blocks when the action indicator is not equal to zero.

7. The memory of claim 1, wherein the plurality of blocks are arranged in a hierarchical structure.

8. The memory of claim 7, wherein the hierarchical structure is a tree.

9. The memory of claim 8, wherein each of the plurality of blocks is assigned a level in the tree, a selected one of the plurality of blocks being designated as a root block and being assigned a lowest level in the tree.

10. The memory of claim 9, wherein the pointer in the data record points to one of the plurality of blocks at a higher level than a current level when the action indicator is not equal to the prescribed value.

11. The memory of claim 5, wherein the database includes a source record including a prefix representing an address, a prefix length and a resource index representing the address of the translation target.

12. The memory of claim 11, wherein the address is an internet protocol address.

13. The memory of claim 12, wherein the resource index is a port destination.

14. The memory of claim 12, wherein the integer value represents a number of bits to be extracted from the prefix to form an offset value, wherein the offset value is used to address one of the data records in one of the plurality of blocks given by the pointer of the data record stored at the offset value.

15. The memory of claim 14, wherein each data record further includes a skip offset field, wherein said skip offset field is added to the integer value when extracting the offset value from the prefix.

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.

17. The memory of claim 16, wherein the action indicator is an integer value.

18. The memory of claim 17, wherein the prescribed value is zero.

19. The memory of claim 18, wherein the integer value represents a size of the selected one of the plurality objects when the action indicator is not equal to zero.

20. The memory of claim 19, wherein the size of the selected one of the plurality of objects is equal to 2 to the power of the integer value.

21. The memory of claim 17, wherein the integer value is a logarithm to the base of 2 of a size of the selected one of the plurality of objects when the action indicator is not equal to zero.

22. The memory of claim 16, wherein the plurality of objects are arranged in a tree structure.

23. The memory of claim 22, wherein each of the plurality of objects is assigned a level in the tree, a selected one of the plurality of objects being designated as a root object and being assigned a lowest level in the tree.

24. The memory of claim 23 wherein the pointer in the data record points to one of the plurality of objects at a higher level than a current level when the action indicator is not equal to the prescribed value.

25. The memory of claim 20, wherein the database includes a source record including a prefix representing an address, a prefix length and a resource index representing the address of the translation target.

26. The memory of claim 25, wherein the integer value represents a number of bits to be considered from the prefix to form an offset value, wherein the offset value is used to address one of the data records in one of the plurality of objects given by the pointer of the data record stored at the offset value.

27. The memory of claim 26, wherein each data record further includes a skip offset field, wherein said skip offset field is added to the integer value when considering the offset value from the prefix.

28. A method of translating an X-bit address to a resource index selected from a plurality of resource indices where 2^X 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 2^A 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 2^B entries.

29. The method of claim 28, wherein the action indicator is an integer value.

30. The method of claim 29, wherein the prescribed value is zero.