×

Fast IP route lookup with configurable processor and compressed routing table

  • US 6,888,838 B1
  • Filed: 02/09/2001
  • Issued: 05/03/2005
  • Est. Priority Date: 11/16/2000
  • Status: Active Grant
First Claim
Patent Images

1. A computer-readable storage medium configured to store a data structure comprising:

  • a first lookup table having at least one entry, each of the at least one entry having a bitmap portion and an information storage portion; and

    a second lookup table having at least one entry, each entry in the at least one entry storing next hop and prefix length information;

    wherein;

    the at least one entry in the first lookup table is indexable by a first portion of an IP destination address, and bits within the bitmap of the at least one entry are indexable by a second portion of the IP destination address;

    the information storage portion of the at least one entry stores next hop and prefix information when the total number of ones in the bitmap of the at least one entry is one of a given set of values;

    the information storage portion of the at least one entry stores information pointing to an entry in the second lookup table when the total number of ones in the bitmap of the at least one entry is not one of the given set of values;

    the first set of values includes one and two;

    the information storage portion of the at least one entry stores one set of next hop and prefix length information when the total number of ones in the bitmap of the at least one entry is one;

    the information storage portion of the at least one entry stores two sets of next hop and prefix length information when the total number of ones in the bitmap of the at least one entry is two; and

    the information storage portion of the at least one entry stores information pointing to an entry in the second lookup table when the total number of ones in the bitmap of the at least one entry is more than two.

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