Efficient address-based rule resolution in a network employing a bit-mapped index

A network device packet processing method comprising:

• storing, in computer readable memory accessible by at least one computing processor, information about a range of addresses, the stored information structured as:
• a first dataset comprising first data structures, each first data structure including a respective address in the range of addresses and a corresponding instruction parameter, the first data structures sorted in the first dataset by address;
• a second dataset comprising second data structures, each second data structure including at least one intermediary value corresponding to a respective address prefix, the at least one intermediary value representing information for use in identifying a respective instruction parameter for an address beginning with the respective address prefix;
• and
• a set of Boolean values, each Boolean value corresponding to a respective address prefix and indicating whether the second dataset includes a second data structure for the respective address prefix;
• identifying, by the at least one computing processor, a first address and a first address prefix for a first data packet;
• identifying, by the at least one computing processor, one or more intermediary values corresponding to the first address prefix using the set of Boolean values;
• identifying, by the at least one computing processor, an instruction parameter using the one or more identified intermediary values;
• and
• processing, by the at least one computing processor, the first data packet using the identified instruction parameter,
• wherein at least one second data structure in the second data set includes:
• a first intermediary value that is a count of first data structures in the first dataset that each include an address beginning with the corresponding address prefix;
• and
• a second intermediary value that is an index into the first dataset for a first data structure that includes an address with the corresponding address prefix.

Tangible non-transitory computer readable media storing instructions which, when executed by one or more computing processors, cause the one or more computing processors to:

• access computer readable memory storing information regarding a range of addresses, the stored information structured as:
• a first dataset comprising first data structures, each first data structure including a respective address in the range of addresses and a corresponding instruction parameter, wherein the first data structures are organized in the first dataset ordered by address;
• a second dataset comprising second data structures, each second data structure including at least one intermediary value corresponding to a respective address prefix, the at least one intermediary value representing information for use in identifying a respective instruction parameter for an address beginning with the respective address prefix;
• and
• a set of Boolean values, each Boolean value corresponding to a respective address prefix and indicating whether the second dataset includes a second data structure for the respective address prefix;
• identify a first address and a first address prefix for a first data packet;
• identify one or more intermediary values corresponding to the first address prefix using the set of Boolean values;
• identify an instruction parameter using the one or more identified intermediary values;
• and
• process the first data packet using the identified instruction parameter,
• wherein at least one second data structure in the second data set includes:
• a first intermediary value that is a count of first data structures in the first dataset that each include an address beginning with the corresponding address prefix;
• and
• a second intermediary value that is an index into the first dataset for a first data structure that includes an address with the corresponding address prefix.