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:
Aug. 27, 2019
Filed:
Apr. 09, 2018
Cisco Technology, Inc., San Jose, CA (US);
Naader Hasani, San Jose, CA (US);
Shishir Gupta, Santa Clara, CA (US);
David Delano Ward, Somerset, WI (US);
Mohammed Ismael Tatar, Kanata, CA;
Shahin Habibi, Menlo Park, CA (US);
Sreedhar Ravipalli, Cupertino, CA (US);
David Richard Barach, Boxborough, MA (US);
Cisco Technology, Inc., San Jose, CA (US);
Abstract
One embodiment performs longest prefix matching operations in one or more different manners that provides packet processing and/or memory efficiencies in the processing of packets. In one embodiment, a packet switching device determines a set of one or more mask lengths of a particular conforming entry of a multibit trie or other data structure that matches a particular address of a packet via a lookup operation in a mask length data structure. A conforming entry refers to an entry which has less than or equal to a maximum number of different prefix lengths, with this maximum number corresponding to the maximum number of prefix lengths which can be searched in parallel in the address space for a longest matching prefix by the implementing hardware. The packet switching device then performs corresponding hash table lookup operation(s) in parallel in determining an overall longest matching prefix for the particular address.