Patent ID: 7509300
Filing Date: 2009-03-24
Classification: H04L,Y10S

Abstract:
1. A computer-implemented method for improving, in dynamic routing tables of a dynamic router, processes for matching a highest-priority range with a destination address in O(log 2 n) time and inserting or deleting rules in O(log n) time, the method comprising: applying a top level balanced binary search tree (PTST) with at least one node comprising a lower level range search tree (RST) to a nonintersecting highest priority rule table comprising at least one nonintersecting range and corresponding priority, wherein the PTST comprises at most 2n nodes, with each of the PTST nodes associated with a point value, wherein the PTST and the RST are stored in a memory of the dynamic router; applying a range allocation rule to allocate to each PTST node a subset of the nonintersecting ranges and corresponding priorities; applying an RST to organize the subset of nonintersecting ranges and corresponding priorities allocated to each PTST node; and maintaining balanced PTST, the PTST having up to n empty nodes, wherein matching a highest-priority range with a destination address is performed in O(log