Prefix partitioning methods for dynamic router tables
View Patent ↗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 2 s +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.
1. 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, 2 s +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.
2. The method according to claim 1 , wherein the representative router table structure is a dynamic router-table data structure.
3. The method according to claim 2 , wherein the dynamic router-table data structure is selected from a group consisting of BOB; PBOB; LMPBOB; B-tree data structure; CRBT; ACRBT; PST; HOT; BOT, and one bit TRIE.
4. The method according to claim 1 , wherein the representative router table structure is a static router-table data structure.
5. The method according to claim 4 , wherein the static router-table data structure is selected from a group consisting of a linear array; trie-based data structures; and hash trees organized by prefix length.
6. The method according to claim 1 , further comprising the steps of:
(a) establishing t to be used for further partitioning the prefixes whose length is smaller than s, where t denotes a second pre-established value of bits of the prefixes;
(b) assessing the length of the prefixes stored in the designated partition with regard to t;
(c) partitioning at least one of the prefixes whose length is larger than or equal to t in up to min (n, 2 t +1) partitions, wherein the prefix whose length is smaller than s and larger than or equal to t is placed in a partition based on the value of the prefix's first t bit; and
(d) storing the prefixes whose length is smaller than s and t into a second designated partition.
7. The method according to claim 1 , further comprising the step of indexing nonempty partitions using an array or a hash table.
8. A computer program product recorded on computer readable medium for routing packets comprising: a computer readable medium for receiving packets specifying prefixes and decision rules for the prefixes; a computer readable medium for establishing s bits to be used in a prefix partitioning scheme; a computer readable medium for matching, inserting, or deleting prefixes in a partitioning tree; and a computer readable medium for performing steps of multilevel partitioning, said steps comprising:
(a) establishing s to be used in a prefix partitioning scheme, where s denotes a pre-established value of bits of the prefixes;
(b) partitioning at least one prefix into up to min(n, 2 s +1) partitions, where n is the total number of prefixes;
(c) assessing prefix length with regard to s;
(d) storing prefixes whose length is larger than 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; and
(f) representing the prefixes in each partition using a router table data structure.
9. The computer program according to claim 8 , wherein the dynamic router-table data structure is selected from a group consisting of BOB; PBOB; LMPBOB; B-tree data structure; CRBT; ACRBT; PST; HOT; and BOT.
10. The computer program according to claim 8 , wherein the representative router-table structure is a static router-table data structure.
11. The computer program according to claim 10 , wherein the static router-table data structure is selected from a group consisting of a linear array; trie-based data structures; and hash trees organized by prefix length.
12. The computer program according to claim 8 , wherein the computer readable medium for performing the steps of multilevel partitioning further comprises the steps of:
(a) establishing t to be used for further partitioning the prefixes whose length is smaller than s, where t denotes a second pre-established value of the bits of the prefixes;
(b) assessing the length of the prefixes stored in the designated partition with regard to t;
(c) partitioning at least one of the prefixes whose length is larger than or equal to t in up to min (n, 2 t +1) partitions, wherein the prefix whose length is smaller than s and greater than or equal to t, is placed in a partition based on the value of the prefix's first t bit; and
(d) storing the prefixes whose length is smaller than s and t into additional bits into a second designated partition.
13. A computer system comprising: a memory containing a partitioning routing table constructing program having functions for constructing a routing table with partitions based on the first s bits of a prefix, where s denotes a pre-established value of the bits of the prefix; wherein the prefixes in each partition are represented by a router table data structure; and a processor for executing the partitioning routing table constructing program.
14. The computer system according to claim 13 , wherein the partitioning routing table constructing program further includes functions for constructing partitions based on the first t bits of a prefix, where t denotes a second pre-established value of bits of the prefix.