FAST PREFIX-BASED NETWORK ROUTE FILTERING

In general, the invention is directed to techniques for improving the performance of route filtering methods. More specifically, an interval tree data structure is assembled from one or more address prefix outbound route filter (ORF) entries by partitioning, according to the characteristics of the ORF entries, a two-dimensional space defined by the address prefix and prefix length domains into non-overlapping intervals. Each node in the interval tree represents a non-overlapping interval in the address prefix dimension. In addition, each node includes a distinct tree structure having nodes that maintain information about the ORF entries that map onto the represented interval for various non-overlapping intervals in the prefix length domain. By traversing the two tiers of trees, a network device can quickly determine the appropriate action to apply to a route.