Longest prefix match scheme

US8880494B2 · kind B2 · utility

Assignee

• Brocade Communications Systems LLC · US

Inventors

• Jian Liu · Huizhou, CN
• Philip Lynn Leichty · Rochester, US
• How Tung Lim · San Jose, US
• John Michael Terry · San Jose, US
• Mahesh Maddury · Santa Clara, US
• Wing Cheung · Fremont, US
• Kung-Ling Ko · Union City, US

Key dates

• Filing date: Oct 28, 2011
• Grant date: Nov 4, 2014
• Expiry date: Oct 28, 2031

Classification

• Technology area (CPC H): Electricity
• CPC primary: H04L45/748
• WIPO field: Digital communication
• WIPO sector: Electrical engineering

Abstract

A LPM search engine includes a plurality of exact match (EXM) engines and a moderately sized TCAM. Each EXM engine uses a prefix bitmap scheme that allows the EXM engine to cover multiple consecutive prefix lengths. Thus, instead of covering one prefix length L per EXM engine, the prefix bitmap scheme enables each EXM engine to cover entries having prefix lengths of L, L+1, L+2 and L+3, for example. As a result, fewer EXM engines are potentially underutilized, which effectively reduces quantization loss. Each EXM engine provides a search result with a determined fixed latency when using the prefix bitmap scheme. The results of multiple EXM engines and the moderately sized TCAM are combined to provide a single search result, representative of the longest prefix match. In one embodiment, the LPM search engine supports 32-bit IPv4 (or 128-bit IPv6) search keys, each having associated 15-bit level 3 VPN identification values.