Patent ID: 6141738
Filing Date: 2000-10-31
Classification: H04L,H04Q,Y10S

Abstract:
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.