The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 28, 2008
Filed:
Nov. 21, 2003
Sartaj Kumar Sahni, Gainesville, FL (US);
Haibin LU, Columbia, MO (US);
Sartaj Kumar Sahni, Gainesville, FL (US);
Haibin Lu, Columbia, MO (US);
University of Florida Research Foundation, Inc., Gainesville, FL (US);
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 2+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.