Patent ID: 6792423
Filing Date: 2004-09-14
Classification: G06F,H04L,Y10S

Abstract:
A method for finding a matching prefix for an input binary data string from among a plurality of prefixes having varying lengths, said method comprising:generating a first lookup table for said plurality of prefixes having a length greater than or equal to n1 bits by utilizing a first hash function; generating a second lookup table for said plurality of prefixes having a length less than n1 bits by utilizing a second hash function, wherein said second hash function is different from said first hash function; applying said first hash function to a prefix of said input binary data string to yield an m1 bit index; determining whether or not said first lookup table includes a match by utilizing said m1 bit index; in response to a determination that said first lookup table does not include a match, applying said second hash function to said prefix of said input binary data string to yield an m2 bit index; and determining whether or not said second lookup table includes a match by utilizing said m2 bit index.