Recursively Partitioned Static IP Router Tables
AssigneeUniversity of Florida Research Foundation, Inc.
InventorsWencheng Lu, Sartaj Kumar Sahni
Life of this patent
Estimating the term…
Abstract
A recursively partitioned static router-table, the data structure incorporating a first-level partition including subtries and an auxiliary trie. A node of the subtrie includes a path Q(N) from the root R of a trie T to a root N of the subtrie, a stride s for a next-level partition, a mask that characterizes a next-level perfect hash function, and a pointer to the hash table for the next-level partition. At least one of the trie T, the first-level partition, the auxiliary trie, and the next-level partition is represented by a base structure selected from the group consisting of MBT and HSST.
Claims9
A computer-readable medium having stored thereon a data structure, the data structure comprising:
- a binary trie T representing a prefix set of all possible destination addresses for routing packets, the T comprising:
- a first-level partition, wherein the first-level partition comprises:
- a subtrie formed by selecting a stride s for the first-level partition, where 0<s≦T.height+1, where T.height is the maximum level l at which there is a descendent of a root R, wherein a node of the subtrie includes:
- a path Q(N), from the root R of T to a root N of the subtrie,
- a stride s for a next-level partition,
- a mask that characterizes a next-level perfect hash function, and
- a pointer to a hash table for the next-level partition;
- an auxiliary trie representing prefixes having a level l less than stride s of the first-level partition, wherein a node of the auxiliary trie includes the root R;
- wherein the number of first-level partitions is |Ds(R)|+1, where Ds(R) represents the level l descendents of root R, where l=s,
- the next-level partition formed by recursively repeating subtrie formation of the first-level partition to each of the |Ds(R)|+1 partitions.
A method for performing a look-up using a data structure comprising a first-level partition of a trie T including an auxiliary partition and a subtrie partition, and a hash table having one or more entry types for keeping track of the first-level partitions of 7′, the method comprising:
- identifying the entry type of a partition from a first bit or first three bits of an entry of the hash table,
- wherein a type 1 entry type represents a partition that is further partitioned into next-level partitions,
- wherein a type 001 entry type represents a leaf partition,
- wherein a type 010 entry type represents a partition represented by a base structure, and
- wherein a type 000 entry type represents an unused hash table entry;
- stripping the first s bits from a destination address d, where s is a stride from a root R of the trie to a root N of the subtrie partition, wherein the first s bits define a key used to index into the hash table;
- and
- if the entry type is the type 000 or if the first s bits do not match a key in the hash table, then
- performing a search of the auxiliary partition, and
- returning the destination address d;
- if the entry type is the type 001, then
- performing a search of the leaf, and
- returning a next hop for the destination address d;
- if the entry type is the type 010, then
- performing a search of the base structure, and
- returning a pointer to the destination address d;
- if the entry type is the type 1, then
- performing a search of the next-level partition by repeating the method for performing a lookup.
Dependencies are inferred from the claim text.