×

High speed routing using compressed tree process

  • US 6,067,574 A
  • Filed: 05/18/1998
  • Issued: 05/23/2000
  • Est. Priority Date: 05/18/1998
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for searching a routing table for routes corresponding to an input string derived from an internet protocol prefix, comprising:

  • a) fetching a compressed tree of pages in memory corresponding to internet protocol address prefixes according to a code which identifies whether a node (i) represents a valid prefix;

    (ii) has descendent nodes; and

    (iii) is a descendent node corresponding to a 1 or to a zero in a predetermined bit position of the prefix;

    b) decompressing the fetched page to construct the original prefix tree; and

    c) searching the decompressed tree to identify the longest prefix matching said string.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×