US 6,141,738 AGranted

Address translation method and system having a forwarding table data structure

AssigneeNortel Networks Limited

InventorsErnst A. Munter, Gary Michael Depelteau

Life of this patent

Estimating the term…

Loading patent…

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.

Claims13

Dependent claims

A method of creating a forwarding table data structure for access by an application program, said application program being executed by a data processor that creates said data structure in a memory coupled to the data processor, said forwarding table data structure being created from a routing table sorted in ascending order, said routing table including a plurality of route entries where each route entry contains a prefix representing an address, a prefix length (PL) and a resource index, and said method comprising the steps, executed by said data processor, of:

(a) selecting a width W for a first stage table;
(b) creating the first stage table of a size equal to 2.sup.W ;
(c) reading a route entry from the routing table;
(d) computing an offset from the W first bits of the prefix of the route entry read at step (c);
(e) when the prefix length of the route entry is the same as the width W of the first stage table, creating a resource record containing the resource index of the route entry and an action indicator of zero and storing the resource record at the offset of the first stage table;
(f) when the prefix length of the route entry is less than the width W of the first stage table, creating a resource record containing the resource index of the route entry and an action indicator of zero and storing the record at the offset in the first stage table T0 and at 2.sup.W-PL -1 subsequent locations in the first stage table following the offset;
(g) when the prefix length of the route entry is greater than the width W of the first stage table selecting a width V for a second stage table, creating the second stage table of a size equal to 2.sup.V, creating a pointer record including a pointer to the second stage table and an action indicator equal to the width V of the second stage table, and storing the pointer record at the offset in the first stage table;
and
(h) returning to step (c) until each route entry in the routing table has been read once.

6 more elements

A method of creating a forwarding table data structure from a routing table sorted in ascending order, said routing table including a plurality of route entries where each route entry contains a prefix representing an address, a prefix length (PL) and a resource index;

said method comprising the steps of:
(a) selecting a width W (1.ltoreq.W.ltoreq.N) for a first stage table T0, where N is a maximum prefix length;
(b) creating the first stage table T0 of a size equal to 2.sup.W ;
(c) reading a route entry from the routing table;
(d) computing an offset A from the W first bits of the prefix of the route entry read at step (c);
(e) comparing the prefix length PL of the route entry with the width W of the first stage table T0;
(1) creating a resource record when the prefix length PL is equal to the width W, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset A in the first stage table T0;
and returning to step (c) until each route entry in the routing table has been read once;
(2) creating a resource record when the prefix length PL is less than the width W, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset A in the first stage table T0 and at 2.sup.W-PL -1 subsequent locations in the first stage table T0 following the offset A;
and returning to step (c) until each route entry in the routing table has been read once;
(3) selecting a width V for a second stage table Tx when the prefix length PL is greater than the width W and offset A in the first stage table T0 is empty;
creating the second stage table Tx (x=1,2, . . . ) of a size equal to 2.sup.V ;
creating a pointer record including a pointer Ptr to the second stage table Tx and an action indicator AI equal to the width V of the second stage table Tx;
storing the pointer record at the offset A in the first stage table T0;
and computing an offset B from the next V bits of the prefix following the first W bits;
proceeding to second stage processing at step (f);
(4) selecting a width V for a second stage table Tx when the prefix length PL is greater than the width W and offset A in the first stage table T0 contains a resource record;
creating the second stage table Tx (x=1,2, . . . ) of a size equal to 2.sup.V ;
filling the second stage table Tx with the resource record from offset A of the first stage table T0;
creating a pointer record including a pointer Ptr to the second stage table Tx and an action indicator AI equal to the width V of the second stage table Tx;
storing the pointer record at the offset A in the first stage table T0;
and computing an offset B from the next V bits of the prefix following the first W bits;
proceeding to second stage processing at step (f);
and
(5) computing an offset B from the next V bits of the prefix following the first W bits when the prefix length PL is greater than the width W and offset A in the first stage table T0 contains a pointer record;
and proceeding to second stage processing at step (f);
(f) comparing a first modified prefix length PL-W of the route entry with the width V of the second stage table Tx;
(1) creating a resource record when the first modified prefix length PL-W is equal to the width V, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset B in the second stage table Tx;
and returning to step (c) until each route entry in the routing table has been read once;
(2) creating a resource record when the first modified prefix length PL-W is less than the width V, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset B in the second stage table Tx and at 2.sup.V-(PL-W) -1 subsequent locations in the second stage table Tx following the offset B;
and returning to step (c) until each route entry in the routing table has been read once;
(3) selecting a width U for a third stage table Ty when the first modified prefix length PL-W is greater than the width V and offset B in the second stage table Tx is empty;
creating the third stage table Ty (y=x.sub.max +1, x.sub.max +2, . . . ) of a size equal to 2.sup.U ;
computing an offset C from the next U bits of the prefix following the first W+V bits;
creating a pointer record including a pointer Ptr to the third stage table Ty and an action indicator AI equal to the width U of the third stage table Ty;
storing the pointer record at the offset C in the third stage table Ty;
and proceeding to third stage processing at step (g);
(4) selecting a width U for a third stage table Ty when the first modified prefix length PL-W is greater than the width V and offset B in the second stage table Tx contains a resource record;
creating the third stage table Ty (y=x.sub.max +1, x.sub.max +2, . . . ) of a size equal to 2.sup.U ;
filling the third stage table Ty with the resource record from offset B of the second stage table Tx;
computing an offset C from the next U bits of the prefix following the first W+V bits;
creating a pointer record including a pointer Ptr to the third stage table Ty and an action indicator AI equal to the width U of the third stage table Ty;
storing the pointer record at the offset C in the third stage table Ty;
and proceeding to third stage processing at step (g);
and
(5) computing an offset C from the next U bits of the prefix following the first W+V bits when the first modified prefix length PL-W is greater than the width V and offset B in the second stage table Tx contains a pointer record;
and proceeding to third stage processing at step (g);
and
(g) comparing a second modified prefix length PL-W-V of the route entry with the width U of the third stage table Ty;
(1) creating a resource record when the second modified prefix length PL-W-V is equal to the width U, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset C in the third stage table Ty;
and returning to step (c) until each route entry in the routing table has been read once;
and
(2) creating a resource record when the second modified prefix length PL-W-V is less than the width U, said resource record including the resource index RI of the route entry and an action indicator AI of 0;
storing the resource record at the offset C in the third stage table Ty and at 2.sup.U-(PL-W-V) -1 subsequent locations in the third stage table Ty following the offset C;
and returning to step (c) until each route entry in the routing table has been read once.

57 more elements

Dependencies are inferred from the claim text.