Patent ID: 7990893

Claim:
A network device comprising: a route filter configured to store data defining an interval tree comprising a plurality of first-tier nodes arranged in a tree data structure, wherein each of the first-tier nodes of the interval tree matches a non-overlapping interval of address values along an address dimension, wherein each of the first-tier nodes comprises one or more second-tier nodes, and wherein each of the second-tier nodes specifies a route filter action and matches a non-overlapping interval of length values along a length dimension; and a control unit configured to: apply the route filter to a route; traverse the plurality of first-tier nodes of the interval tree to determine, for an address of the route, a first-tier node that matches an interval of address values that includes the address of the route; traverse the one or more second-tier nodes of the matching first-tier node to determine, for a length of the route, a second-tier node that matches an interval of length values that includes the length of the route; and perform a route filter action specified by the matching second-tier node on the route.