US 6,549,536 B1Granted

Method of address compression for cell-based and packet-based protocols and hardware implementations thereof

AssigneesItaltel S.p.A., Siemens Mobile Communications S.p.A.

InventorsMarco Pavesi, Riccardo Gemelli

Life of this patent

Estimating the term…

Loading patent…

Abstract

It is disclosed an algorithm able to compress a defined set of addresses S, the set of addresses to be compressed, belonging to the set U, the whole addressing space; for each of these addresses the algorithm must identify one and only one address belonging to C, the set of compressed address (i.e. perform a transformation S→C). The algorithm may be implemented using some low-cost random access memories (RAM) and some control logic. A performance comparison shows that is possible to perform the address compression using one order of magnitude less memory respect to the state-of-the-art techniques. Basically, the method of the invention combines the splitting of the incoming address space (U) into a plurality of sub-spaces, a tree search algorithm for clustering a defined set (S) of identifiers contained in the sub-spaces into which the incoming addresses space (U) has been split and a sequential search performed within the right cluster in order to identify the compressed address belonging to space C. The patent covers the algorithm, a preferred embodiment and some extended embodiments, that give extra gain. Thanks to the invention is thus possible to implement silicon devices able to compress one order of magnitude more managed channels with respect to the state-of-the-art techniques, without area changes. Conversely, it is possible to implement the address compression function with one order magnitude less memory resources with respect to the state-of-the-art techniques.

Claims12

Dependent claims

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 Ncpr<N, characterized in that the method comprises the steps of:

a) 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.

1 more element

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 different points or domains of said address space (U) belonging to a certain number (Nclasses) of subsets (S1, S2, Sj, SNclasses) of identifiers to be compressed to a number of strings, being said number equal to the said number of subsets (Nclasses), these strings constituting different compressed address spaces (C1, C2, Cj, CNclasses), characterized in that the method comprises the steps of:

a) 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 subsets (S1, S2, Sj, SNclasses) of N-bit identifiers contained in said subspaces by the use of a plurality of routing tables (RTij), the tables being organized in a tree, a page of the firsttable (RT11) 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, used to point a page of the following tables of the cascade (RT12) if the same subset S1 has to be clustered or to point to at least two different tables (RT21, and RT22, . . . ), downstream of a branching of said tree, if different subsets must be clustered to different compressed address spaces, for selecting, by means of a predefined slice of the incoming N-bit identifier (INCVECT), at least two different pointer data suitable to point to a next stage of Routing Table of said tree (RTij), and so forth until all bits of the incoming N-bit identifier (INCVECT), have been utilized, outputting from the last pointed routing tables (RTnj) a plurality of final pointer data (CLID1, CLID2, CLIDj, CLIDNclasses) identifying as many clusters in different sequential search tables (SST1, SST2, SSTj, SSTNclasses) each organized in pages composed by a number of rows equal to said predefined number (SSLLj), each page corresponding to a cluster, and each sequential search table corresponding to points or domains or subsets Sj belonging to said address space (U), each cluster being smaller of or equal to said predefined number of rows (SSLL1, SSLL2, SSLLj, SSLLNclasses) and storing only points belonging to the said subset of N-bit identifiers (S1, S2, Sj, SNclasses) which map to the corresponding said (C1, C2, Cj, CNclasses) subsets of compressed addresses.
c) performing, on the clusters belonging to each sequential search table (SST1, SST2, SSTj, SSTNclasses) pointed by said final pointer data (CLID1, CLID2, CLIDj, CLIDNclasses) a sequential search by means of different address generators, one for each sequential search table, verifying the match of the data stored in said sequential search tables (OUTVECTj) with said incoming N-bit identifier (INCVECT), identifying said compressed addresses subsets (C1, C2, Cj, CNclasses) of compressed addresses.

A data processing structure for performing 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 2N size, by mapping in a predictable time span 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 Ncpr<N, the structure receiving an incoming N-bit identifier (INCVECT) belonging to said address space (U) containing unique address information upon verifying a match of the destination information contained in the N-bit incoming identifier (INCVECT) with an outcoming N-bit vector (OUTVECT) among a plurality of 2Ncpr elements, each one in direct relationship with a compressed address, characterized that it comprises

a) a direct addressing table (DAT) to which a first predefined slice of said incoming N-bit identifier (INCVECT) is inputted, pointing a row of said table for outputting a first pointer datum;
b) a cascade of routing tables (RT1, . . . , RTn), the first of which is coupled in cascade to said direct addressing table (DAT), each organized in selectable pages that are pointed by the pointer datum of the preceding table in the cascade, the first table of the cascade (RT1) having a page pointed by said first pointer datum outputted by said direct addressing table (DAT), and a row of the thus pointed page of all routing tables of the cascade being pointed by respective slices of said incoming N-bit identifier (INCVECT), which is inputted to each routing table;
c) at least a sequential search table (SST) organized in a plurality if pages, or clusters, pointed by the datum outputted by the last table (RTn) of said cascade of routing tables;
d) validation means (=) verifying the coincidence of the destination information contained in said incoming N-bit identifiers (INCVECT) with the information contained in the sequentially searched rows (OUTVECT) of the pointed page of said sequential search table (SST) or plurality of tables.

1 more element

A data processing structure for performing 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, by mapping in a predictable time span different points or domains of said address space (U) belonging to Nclasses subsets (S1, S2, Sj, SNclasses) of identifiers to be compressed to M string of at least Ncpr bits, constituting different compressed address spaces (C1, C2, Cj, CNclasses), the structure receiving an incoming N-bit identifier (INCVECT) belonging to said address space (U) containing unique address information upon verifying a match of the destination information contained in the N-bit incoming identifier (INCVECT) with Nclasses of N-bit vectors (OUTVECTj) among a plurality of elements, each one in direct relationship with a compressed address, characterized that it comprises

a) a direct addressing table (DAT) to which a first predefined slice of said incoming N-bit identifier (INCVECT) is inputted, pointing a row of said table for outputting a first pointer datum;
b) a tree of routing tables (RT11, . . . , RTij, . . . , RTnNclasses), the first of which is coupled in cascade to said direct addressing table,(DAT), each routing table being organized in selectable pages that are pointed by pointer data outputted by preceding tables in the tree-like cascade, the first table of the tree-like cascade (RT11) having a page pointed by said first pointer datum outputted by said direct addressing table (DAT), and pointing to a chain of routing tables or branching to at least two chains, a row of the thus pointed page of all routing tables of the tree-like cascade being pointed by respective slices of said incoming N-bit identifier (INCVECT), which is inputted to each routing table, the last routing table (RTnj) of each branch in said tree-like cascade generating a final pointer datum (CLID1, CLID2, CLIDj, CLIDNclasses);
c) at least Nclasses of sequential search tables (SSTj), each table being organized in a plurality of pages, or clusters, pointed by the datum outputted by the last table (CLIDj) of said tree-like cascade of routing tables;
d) validation means (=) verifying the coincidence of the destination information contained in said incoming N-bit identifier (INCVECT) with the data (OUTVECTj) contained in the pages, belonging to said sequential search table (SSTj), pointed by final pointer data (CLID1, CLID2, CLIDj, CLIDNclasses) generated by said last routing table (RTnj) of each branch in said tree-like cascade.

1 more element

Dependencies are inferred from the claim text.