Method and system for performing longest prefix matching for network address lookup using bloom filters

  • US 7,602,785 B2
  • Filed: 02/09/2005
  • Issued: 10/13/2009
  • Est. Priority Date: 02/09/2004
  • Status: Active Grant
First Claim
Patent Images

1. A method of performing a network address lookup, comprising:

  • grouping forwarding prefixes from a routing table by prefix length;

    associating each of a plurality of Bloom filters with a unique prefix length;

    programming each of said plurality of Bloom filters with said prefixes corresponding to said associated unique prefix length;

    performing membership probes to said Bloom filters by using predetermined prefixes of a network address; and

    utilizing a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths;

    wherein said direct lookup array comprises;

    storing prefixes of not more than a predetermined number for a predetermined length, in a binary trie;

    performing Controlled Prefix Expansion (CPE) in a CPE trie for a stride length equal to said predetermined number;

    writing a next hop associated with each leaf at a level of said CPE trie corresponding to said predetermined number to an array slot addressed by bits that label a path from a root of said CPE trie to said leaf; and

    searching said array using bits of said network address of said predetermined number to index into said array.

View all claims

    Thank you for your feedback