×

Compilation of access control lists

  • US 7,646,771 B2
  • Filed: 09/28/2005
  • Issued: 01/12/2010
  • Est. Priority Date: 08/17/2005
  • Status: Active Grant
First Claim
Patent Images

1. A method of organizing classification tables for use in a packet classification algorithm in which incoming packets are matched with rules contained in access control data base, said method comprising the steps of:

  • (A) constructing, by one or more processors of a network device, a set of top-level equivalence tables, each of which contains bit vectors identifying the rules specifying a value or values in a field in the packet headers, each table entry containing a unique bit vector and a equivalence ID specifying the bit vector;

    (B) constructing, by the one or more processors, a set of second-level of equivalence tables whose entries are indexed by a pair of equivalence ID'"'"'s in a pair of top-leveled tables, each entry in the second level containing(1) a bit vector resulting from the intersection of the bit vectors in the corresponding top-level equivalence ID'"'"'s, and(2) an equivalence ID specifying the bit vector;

    (C) constructing, by the one or more processors, a third-level set of equivalence tables whose entries are indexed by pairs of equivalence ID'"'"'s in pairs of second-level tables, each entry in a third-level table containing(1) a bit vector resulting from the intersection of the bit vectors corresponding to the second-level equivalence ID'"'"'s, and(2) an equivalence ID specifying the bit vector;

    (D) constructing, by the one or more processors, each of said third-level tables as a set of fragments, constructing a pointer array derived from the equivalence ID'"'"'s in a second-level table, the contents of the pointer array pointing to the respective third-level table fragments, and the equivalence ID'"'"'s of another of the second-level tables indicating depths of the entries in the table fragments;

    (E) recording a time when at least some tables of the set of top-level equivalence tables, second-level of equivalence tables or third-level equivalence tables were last rebuilt in order to classify a new type of packet;

    (F) accessing a minimum rebuild interval; and

    (C) timing a new rebuilding of the at least some tables to occur only after the minimum rebuild interval has elapsed since the last rebuild.

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