Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Patent
1996-08-23
2000-02-08
Hsu, Alpus H.
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
341 62, 341102, 711202, H04L 1256, H03M 712, H03M 720
Patent
active
060234660
DESCRIPTION:
BRIEF SUMMARY
Given a mapping from a subset of n-bit wide words, which may be keywords, addresses, identifiers, etc., to a set of k-bit wide words (k<n), the invention relates to a method and apparatus for rapidly looking up the k-bit word corresponding to a given n-bit word. More specifically, it relates to the building, use, and maintenance of an n-bit to k-bit translating or mapping device, in particular for use in an application involving the rapid transfer of digital data, such as high speed parallel processing or telecommunications. More specifically, it concerns an n-to-k-bit mapping apparatus and method using a random access memory in which digital data are stored in an order specified by a search key.
BACKGROUND OF THE INVENTION
In computing and telecommunications, often a situation is encountered in which from the 2.sup.n possible words with n bits, representing for example instructions, memory locations, node or hosts addresses, only a significantly smaller subset is actually supported or used at a particular place or time. For the purpose of describing the current invention, this smaller number of words is denoted by 2.sup.k, with k being an integer smaller than n. In order to avoid unnecessary expenditures and unused resources, this situation can be solved by a translation of the n-bit words into k-bit words to be used in a local or temporary application. In terms relevant to the related technical field, this translation is known as `lookup` or `mapping` function. A description of the header conversion within a ATM-type switching system, as given below, may serve as an example for this general concept.
The ATM switching technique is currently under development by all major telecommunications equipment manufacturers. ATM is an acronym made up from asynchronous transfer mode. This switching technology allows the exchange of digital data coming from customer premises, e.g. connections from homes or offices, from local area networks (LANs), or from other switches, routers, or gateways. Data transmitted in ATM are divided into standard-size packets, called cells. Each cell has to be provided with a header containing information concerning addressee and receiving node or user. According to currently valid standards, the bit string identifying the receiver of an ATM cell is 28 bits wide and divided into a virtual path identifier field (VPI) and a virtual channel identifier field (VCI). Out of these 2.sup.28 possible addresses, a state-of-the-art ATM switch may support approximately 10,000 at a time, which lets k assume a value of 13 or 14. Thus, the switch allows the conversion of 2.sup.k incoming VPI/VCIs into new VPI/VCIs to enable, for example, the next `hop` of the respective data packets towards their final destination address.
This header conversion is performed by means of a lookup table, in which the incoming VPI/VCI is identified and translated into the VPI/VCI which is paired to it. Comparing the number of supported VPI/VCI values (2.sup.k) with the number of possible VPI/VCIs (2.sup.n, n=28). it is immediately obvious that a simple lookup table which pairs n-bit words is ineffective as the overwhelming number of entries has no counterpart.
This problem is solved by an (intermediate) translation of those n-bit addresses supported by the switch into k-bit words and performing the (final) conversion back to an n-bit word in a second lookup step in a table which has only 2.sup.k entries. As this second lockup step can easily be implemented, the prior art is focused on the problem of mapping or translating the supported n-bit words into k-bit words.
For the n-to-k-bit translation, typically content addressable memories (CAMs) are used. An example for this technique is given in European patent application EP-A-0 500 238, in which the n-bit VPI/VCI is extracted from the header of an incoming ATM cell and fed into a CAM. The k-bit output word of the CAM is used to address a conventional random access memory (RAM), which holds the new VPI/VCI to be attached to the outgoing ATM cell. A similar approach is p
REFERENCES:
patent: 5261090 (1993-11-01), Lien
patent: 5271010 (1993-12-01), Miyake et al.
patent: 5696925 (1997-12-01), Koh
patent: 5696930 (1997-12-01), Garetz et al.
patent: 5699539 (1997-12-01), Garber et al.
patent: 5737564 (1998-04-01), Shah
patent: 5895500 (1999-04-01), Thompson et al.
IBM Technical Disclosure Bulletin, vol. 35, No. 5, Oct. 1992, New York US pp. 396-397 "Use of an Associative Memory Scheme for Large RAM/ROM Simulation Models".
Luijten Ronald P.
Schindler Hans R.
Cockburn Joscelyn G.
Hsu Alpus H.
International Business Machines - Corporation
Qureshi Afsar M.
LandOfFree
Bit mapping apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bit mapping apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit mapping apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1686212