×

Methods and apparatus for fairly scheduling queued packets using a ram-based search engine

  • US 6,389,031 B1
  • Filed: 11/04/1998
  • Issued: 05/14/2002
  • Est. Priority Date: 11/05/1997
  • Status: Expired due to Fees
First Claim
Patent Images

1. In a system having a parameter queue for referencing stored information based on their respective parameter values, and having a validity bit associated with each of M parameter values for indicating whether any of the stored information have that parameter value, a method for selecting, from candidate information, an information having an extreme parameter value, the method comprising steps of:

  • a) generating a hierarchy of L levels from the validity bits, the hierarchy generated via sub-steps of, i) grouping the M validity bits into groups of gL−

    1
    bits, ii) logically ORing the gL−

    1
    validity bits in each of the groups, iii) defining bits of a next level by concatenating the OR results thereby generating M/gL−

    1
    bits, iv) storing the bits of the next level in an addressable memory, and v) at each of the remaining levels l, except a highest level l=0, repeatedly A) grouping Ml bits into groups of gl bits, B) logically ORing the gl bits in each of the groups, C) concatenating the OR results thereby generating Ml/gl bits which define bits of a next level, and D) if the next level is not the highest level l≠

    0, storing the bits of the next level in a next addressable memory and if the next level is the highest level l=0, storing the bits of the next level in a storage device; and

    b) searching for an information having an extreme parameter value.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×