US 7,444,318 B2 · Prefix partitioning methods for dynamic router tables

Abstract

A method is provided to improve the performance of dynamic router-table designs. Specifically, the invention relates to a method and system for partitioning prefixes at each node of a partitioning tree into 2s+1 partitions using the next s bits of the prefixes. Prefixes that have a length less than s are placed into partition −1, with the remaining prefixes falling into the remaining partitions that correspond to the value of their first s bits. Prefix partitioning may be controlled using either static rule tables or by dynamic rule tables. In one embodiment, binary tree on binary tree (BOB) data structures are applied to a partition of the present invention. In another embodiment, prefix binary tree on binary tree (PBOB) data structures are applied to a partition of the present invention. In a further embodiment, a dynamic longest-matching prefix binary tree on binary tree-table (LMPBOB) is applied to a partition of the present invention.

Claims14

Dependent claims

A method for improving routing operations in dynamic routing tables comprising:

(a) establishing s to be used in a prefix partitioning scheme, wherein s denotes a pre-established value of bits of the prefixes;
(b) partitioning at least one prefix into up to min(n, 2s+1) partitions, where n is the total number of prefixes;
(c) assessing prefixes length with regard to s;
(d) storing the prefix whose length is larger than or equal to s in a partition that corresponds to the value of the prefix's first s bit;
(e) storing prefixes whose length is smaller than s in a first designated partition;
(f) representing the prefixes in each partition using a router table data structure;
and
(g) performing an operation selected from lookup, insert, and delete by using the stored prefixes.

5 more elements

Dependencies are inferred from the claim text.

Prefix partitioning methods for dynamic router tables

Life of this patent

Prefix partitioning methods for dynamic router tables

Life of this patent

Abstract

Claims14