Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-30
2001-07-17
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S399000, C370S409000
Reexamination Certificate
active
06262985
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the fields of computer science and telecommunications and, more specifically, to means and methods of translating identification strings from one format into another.
BACKGROUND OF THE INVENTION
Many computing applications manipulate identification strings that reference various entities such as data structures, external objects and processes. Such identification strings, which are hereinafter referred to as identifiers, tend to be large so that they can be distinguished from a great number of other identifiers. Identifiers also tend to be large in order for the schemes that organize them to be more flexible and more able to accommodate future additions of new identifers.
One common type of manipulation effected by such computing applications involves translating identifiers from a bulkier less manageable format to a smaller more manageable format that can be manipulated more easily. Such translations are performed to reduce the needless processing and memory demands that are made of a localized set of components, when the identifiers they are handling include fields that they do not need to access.
One example of a computing application that requires such translations arises in the field of telecommunications engineering, and more specifically in the operation of an Asynchronous Transfer Mode (ATM) switch. In an ATM network, the external connection identifier (ECI) of a cell, which can be processed by all nodes of the network, can comprise a Virtual Path Identifier (VPI), and a Virtual Channel Identifier (VCI). These identifiers, when considered in combination, can occupy binary words that are typically at least 28 bits long, and thus can assume billions of possible values. Usually however, it is not feasible or necessary for a switch to support such a large number of connections at one time primarily because of the vast amounts of context memory and processing resources required for each connection. As a result, a smaller number of connections is supported instead.
Accordingly, it is desirable to implement a system in ATM networks for translating a set of ECIs that can be manipulated by any of the switches into smaller more easily manageable internal connection identifiers (ICIs) that will only have to be manipulated by a single switch. At the same time, it is also desirable that the set of ECIs selected for translation comprise any subset of the full range of possible ECIs. That is, assuming the full range of ECIs comprises M ECIs, it is desirable that a switch capable of translating N ECIs into ICIs, be able to set each of its N ECIs to any one of the M possible ECIs.
Whether the target application is the above-described ATM network, or any other application wherein large bulky identifiers need to be converted into smaller, more manageable internal identifiers, present systems that translate identifiers have shortcomings.
Systems designed around direct one-stage look-up tables, wherein each table-entry is addressed by a large, external identifier and contains a smaller internal identifier, are economically impractical. This is because under such an approach, the size of the look-up tables must be set to equal the number of ECIs comprising the full range of external identifiers. For example, if an individual ATM switch can serve 100,000 connections, and the full range of ECIs extends from 0 to 1,000,000, the size of the look-up table would have to be 1,000,000 entries rather than 100,000 entries. Such large look-up tables are costly and wasteful.
Systems designed around constrained one-stage look-up tables cannot translate the full range of possible external identifiers, and thus are also undesirable.
Systems that use hashing functions to access look-up tables are complex, and may require expensive hardware to implement. Moreover, the time required to complete each translation may not be deterministic.
Systems designed around Content Addressable Memory (CAMs), wherein each entry is addressed by an internal identifier and contains an external identifier, are expensive. Furthermore, at present, a reasonably priced CAM does not have sufficient capacity to hold the number of internal identifiers required by many applications.
An improved system is thus desired for translating identifiers from a bulkier less manageable external format that can be manipulated by a broader range of components comprising a computing application, to a smaller more manageable internal format that can be more efficiently manipulated by a narrower range of those same components.
The desired system should also be able to translate any of the full range of external identifiers.
Another object of such a system is to achieve the translations using a simple and robust design that requires a minimal amount of memory and computation.
It is also desirable that the translation system exhibit fast and deterministic response-times.
SUMMARY OF THE INVENTION
These and other objects are achieved using a system designed around a two stage look-up method. More specifically, the objects are achieved by a method of translating any of a full range of external identifiers into a smaller internal identifier, the method making use of a final look-up table (LUT) that has an internal identifier in each of its entries, that is divided into a plurality of pages, and that allows access to a given entry upon receiving a base-address that specifies the page of the entry and an offset-address that specifies the position of the entry within the page, said method comprising the steps of: dividing an inputted external identifier into a plurality of fields; inputting the contents of a subset of the plurality of fields, the subset being associated with the internal identifiers inside a specific page of the final LUT, as a given address into an initial look-up table (LUT) that has in each of its entries a base-address of a page of the final LUT, to obtain the base-address of the specific page; adding the base-address of the specific page obtained from the inputting step to an offset-address, which is obtained from the contents of the field or fields of the external identifier not sent into the initial LUT, to obtain a resulting sum, and using the resulting sum as an address into the final LUT; and reading the entry of the final LUT referenced by the resulting sum to obtain the smaller internal identifier.
Another aspect of this invention is centred around a method of translating any of a full range of external identifiers into a smaller internal identifier, said method comprising the steps of: dividing an inputted external identifier into a plurality of fields; inputting the contents of a subset of the plurality of fields as an address into an initial look-up table (LUT), the initial LUT having in each of its entries a base-value; and adding the base-value obtained from the inputting step to an offset-value which is obtained from the contents of the field or fields of the external identifier not sent into the initial LUT, to obtain the internal identifier.
In yet another aspect of this invention, the aforementioned objects are achieved by an apparatus for translating any of a full range of external identifiers, each of which is defined by a plurality of fields, into a smaller internal identifier, comprising: a final look-up table (LUT) which is divided into a plurality of pages, each page having one entry or many entries and each entry containing an internal identifier, which receives an address input that comprises a base-address specifying a specific page and an offset-address specifying a specific entry within the specific page, and which yields an output that includes the internal identifier stored inside the specific entry; an initial look-up table (LUT) which has a plurality of entries, each entry containing a respective base-address of a page of the final LUT, which receives an address input comprising a subset of the fields of the external identifier, said address input being associated with the internal identifiers inside a specific page of the final LUT, and which yields an outp
Bahgat Osama
Depelteau Gary
Huang Tony
Hung Paul Fong-Yan
McLaughlin James
Ngo Ricky
Nortel Networks Limited
Tran Phuc
LandOfFree
Method and apparatus for full range translation of large... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for full range translation of large..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for full range translation of large... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2517326