Method of address compression for cell-based and packet-based protocols and hardware implementations thereof
US6549536B1 · kind B1 · utility
Assignees
Inventors
Key dates
| Filing date | Jul 30, 1999 |
| Grant date | Apr 15, 2003 |
| Priority date | — |
| Expiry date | Jul 30, 2019 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2012/5652
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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 a…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.