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:
Apr. 21, 2009
Filed:
Apr. 30, 2003
Sartaj Kumar Sahni, Gainesville, FL (US);
Haibin LU, Gainesville, FL (US);
Sartaj Kumar Sahni, Gainesville, FL (US);
Haibin Lu, Gainesville, FL (US);
University of Florida Research Foundation, Inc., Gainesville, FL (US);
Abstract
An improved system and method is provided for packet routing in dynamic router tables. Specifically, the invention provides a method, computer system, and computer readable media for using Priority Search Trees (PSTs) to match, insert, and delete rules in dynamic routing tables in O(log n) time. In a first embodiment, for a dynamic router table consisting of n pairs of tuples, each tuple comprising an address prefix and next-hop information, the invention provides a system and method, using a PST, for inserting a new tuple, deleting an existing tuple, and searching for the tuple with the longest matching prefix for destination address, wherein each operation is performed in O(log n) time. In a second embodiment, for a dynamic router table consisting of n pairs of tuples, each tuple comprising a range of destination addresses and next-hop information, the invention provides a system and method, using a PST and a set of red-black priority search tree (RBPST), for inserting a new tuple, deleting an existing tuple, and searching for the tuple with the most specific matching range, wherein each operation is performed in O(log n) time. The invention can be implemented in numerous ways to improve dynamic router table performance, including as a system, a device, a method, or a computer readable medium.