Longest prefix match using binary search tree

US8880507B2 · kind B2 · utility

Assignee

• Brocade Communications Systems LLC · US

Inventors

• Sridhar Kotha · Fremont, US
• Satyanarayana Arvapalli · Darsi, IN
• Vikram Bichal · Savanuru, IN
• Anil Kumar Gajkela · Nalgonda, IN
• Srinivas Reddy Bhima reddy · Darsi, IN
• Balajl Tadepalli · Bengaluru, IN
• Venkatesh Nagapudl · Milpitas, US
• Satsheel B. Altekar · San Jose, US

Key dates

• Filing date: Oct 27, 2010
• Grant date: Nov 4, 2014
• Expiry date: May 31, 2031

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/9535
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Longest Prefix Match (LPM) is implemented using a binary tree based search algorithm. Masked entries are stored in a plurality of binary search engines, wherein each of the binary search engines stores masked entries of a corresponding mask length. A search value is applied to each of the binary search engines in parallel. The search value is masked within each of the binary search engines, thereby creating a plurality of masked search values, each having a masked length equal to the mask length of the corresponding binary search engine. Each of the masked search values is compared with the masked entries of the corresponding binary search engine. An LPM result is selected from the binary search engine that detects a match, and has the longest corresponding mask length. Alternately, each binary search engine stores masked entries of N mask lengths, and N consecutive comparisons are performed to identify the LPM.