Patent ID: 6549536
Filing Date: 2003-04-15
Classification: H04L

Abstract:
A method of address compression for a data stream structured in packets or cells, each including a destination identifier consisting of a string of N bits (INCVECT) constituting an address space (U) of size 2N, consisting in an algorithm, executable in a predictable time span, mapping 2Ncpr points of said address space (U) belonging to a subset (S) of identifiers to be compressed to a unique string of Ncpr bits, constituting a compressed address space (C) of size 2Ncpr where Ncpra) splitting said address space (U) of incoming N-bit identifiers into a plurality of subspaces by the use of a direct addressing table (DAT), a row of which is pointed by a first predefined slice of the incoming N-bit identifier (INCVECT) for outputting a first pointer datum; b) clustering said subset (S) of N-bit identifiers contained in said subspaces by the use of a plurality of routing tables (RTi), the tables being coupled in a cascade, a page of the first table (RTI) being pointed by said first pointer datum and the row of the pointed page being selected by a predefined second slice of the incoming N-bit identifier (INCVECT), for outputting a second pointer datum, a page of each of the following tables of the cascade being pointed by the pointer datum output by the preceding table and the row of the pointed page being selected by a respective predefined slice of the incoming N-bit identifier (INCVECT), for outputting from the last routing table (RTn) a final pointer datum, thus identifying a series of clusters located in at least a sequential search table (SST), each cluster smaller or equal to a predefined number (SSLL) and storing only points of said subsets that belong to the said subset (S); c) performing, on a cluster of said first subset (S), having a size equivalent to said predefined number (SSLL) as defined in, step b), a sequential search in at least a table (SST), said table being organized in pages, each page corresponding to a cluster, composed by a number of rows equal to said predefined number (SSLL), within a given packet or cell time slot, by pointing, with the pointer datum outputted by the last one of said routing tables (RTi) in cascade, a page on which said sequential search is performed; d) said pointer datum outputted by the last routing table, concatenated with the row index datum of the selected page of said sequential search table (SST) or plurality of tables, verifying the match with incoming N-bit identifier (INCVECT) constituting said compressed address of Ncpr bits.