公开(公告)号：US20120023082A1

公开(公告)日：2012-01-26

申请号：US12913717

申请日：2010-10-27

Applicant: Sridhar Kotha ,  Satyanarayana Arvapalli ,  Vikram Bichal ,  Anil Kumar Gajkela ,  Srinivas Reddy Bhima reddy ,  Balaji Tadepalli ,  Venkatesh Nagapudi ,  Satsheel Altekar

Inventor： Sridhar Kotha ,  Satyanarayana Arvapalli ,  Vikram Bichal ,  Anil Kumar Gajkela ,  Srinivas Reddy Bhima reddy ,  Balaji Tadepalli ,  Venkatesh Nagapudi ,  Satsheel Altekar

IPC: G06F17/30

CPC classification number: G06F17/30495 ,  G06F17/30327 ,  G06F17/30625 ,  G06F17/30867

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.

Abstract translation: 使用基于二叉树的搜索算法实现最长前缀匹配（LPM）。 被掩蔽的条目存储在多个二进制搜索引擎中，其中每个二进制搜索引擎存储对应的掩码长度的掩码条目。 搜索值并行应用于每个二进制搜索引擎。 搜索值被掩蔽在每个二进制搜索引擎内，由此产生多个掩码的搜索值，每个具有等于相应二进制搜索引擎的掩码长度的掩码长度。 将每个掩蔽的搜索值与对应的二进制搜索引擎的掩蔽条目进行比较。 从检测匹配的二进制搜索引擎中选择LPM结果，并具有最长的对应掩码长度。 或者，每个二进制搜索引擎存储N个掩码长度的掩蔽条目，并执行N个连续比较以识别LPM。

公开(公告)号：US08880507B2

公开(公告)日：2014-11-04

申请号：US12913717

申请日：2010-10-27

Applicant: Sridhar Kotha ,  Satyanarayana Arvapalli ,  Vikram Bichal ,  Anil Kumar Gajkela ,  Srinivas Reddy Bhima reddy ,  Balajl Tadepalli ,  Venkatesh Nagapudl ,  Satsheel Altekar

Inventor： Sridhar Kotha ,  Satyanarayana Arvapalli ,  Vikram Bichal ,  Anil Kumar Gajkela ,  Srinivas Reddy Bhima reddy ,  Balajl Tadepalli ,  Venkatesh Nagapudl ,  Satsheel Altekar

IPC: G06F17/30

CPC classification number: G06F17/30495 ,  G06F17/30327 ,  G06F17/30625 ,  G06F17/30867

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.

Abstract translation: 使用基于二叉树的搜索算法实现最长前缀匹配（LPM）。 被掩蔽的条目存储在多个二进制搜索引擎中，其中每个二进制搜索引擎存储对应的掩码长度的掩码条目。 搜索值并行应用于每个二进制搜索引擎。 搜索值被掩蔽在每个二进制搜索引擎内，由此产生多个掩码的搜索值，每个具有等于相应二进制搜索引擎的掩码长度的掩码长度。 将每个掩蔽的搜索值与对应的二进制搜索引擎的掩蔽条目进行比较。 从检测匹配的二进制搜索引擎中选择LPM结果，并具有最长的对应掩码长度。 或者，每个二进制搜索引擎存储N个掩码长度的掩蔽条目，并执行N个连续比较以识别LPM。