Patent ID: 6888838
Filing Date: 2005-05-03
Classification: H04L

Abstract:
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.