×

Longest prefix match (LPM) algorithm implementation for a network processor

  • US 6,947,931 B1
  • Filed: 04/06/2000
  • Issued: 09/20/2005
  • Est. Priority Date: 04/06/2000
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for determining a longest prefix match for a variable length search key by a computer processing device, comprising:

  • reading an input key as a search string;

    using the N most significant bits of the input key as an address to index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

    determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

    reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree and comparing the prefix represented by the next branch with the input key to find a distinguishing bit position;

    reading a leaf pattern when the leaf of a corresponding search tree is reached and comparing the leaf pattern with the input key to determine if the leaf pattern matches the input key; and

    returning the longest prefix match found for the input key to a requesting application.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×