BOB

In packet classification problem a best matching rule is found for incoming packet using one of the following rule, first matching rule, most specific rule, or highest priority rule. While packet classification problem on prefix router table with most specific rule was substantially studied, the one with highest priority rule hasn’t. We propose a dynamic data structure BOB for packet classification with highest priority rule that matches the given destination address. BOB can be used for general nonintersecting range router table (including prefix router table). When constraining to prefix router table, further improvements for BOB are presented, BO-BIP for highest priority rule and BOBIPV for most specific rule. As in experiment results, the proposed data structure achieve the good balance between lookup time, update time and memory requirement.