Patent ID: 7523218

Claim:
A method for matching, inserting, or deleting rules in dynamic routing tables in O(log n) time comprising applying at least one priority search tree to represent at least one dynamic routing table; mapping in 2-dimensional space a set of ranges R wherein each range represents a rule to provide at least one point set, transforming the map so that every point set on the map is unique; and representing the transformed map as a first priority search tree (PST1), wherein the point set comprises points x and y, and wherein the transformation of the point set is performed according to the following formulas: (x,y)∈P.transform1(x,y)=(x′,y′)=(2 W x−y+2 W −1,y), and transform1(P)={transform1(x,y)|(x,y)∈P}; wherein P is the point set and W is the number of bits in the destination.