Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1995-04-13
2002-04-09
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S005000, C711S105000, C711S170000, C711S202000, C711S206000
Reexamination Certificate
active
06370610
ABSTRACT:
The present invention relates to an apparatus which permits input values to be swapped into output values and more particularly to such an apparatus which can be used in a communication system wherein the input values are the headers of data streams received by the system and the output values are the headers of the corresponding data streams transmitted by the communication system. Also, this apparatus can be used for implementing any table look-up function.
BACKGROUND ART
Most communication systems include switches and links and have for a function to transport the data streams received on input links to addressed output links.
The trend today is to use the so-called asynchronous transfer mode for high speed transmission and switching in future communication networks. In this mode, all data are transported in cells and each cell is 53-bytes long. The first five bytes contain a header including a 12-bit VP field (Virtual Path) and a 16-bits VC field (Virtual Channel) which comprise the address indicating the destination of the cell.
At the input of a switching node, the VP/VC fields are replaced by new ones (swapped) and a routing header is attached so that the cell can be routed through the switch. The routing header is then removed and the cell is transmitted on the proper outgoing link.
High speed swapping of the VP/VC fields is a difficult problem, since more then 2
28
=268.10
6
VP/VC combinations are possible and at a transmission rate of 155 Megabits/second, a cell must be processed in less than 2.5 microseconds.
Thus, processing all these combinations is not realistic. Practically a transport node is made of communication adapters attached to physical links on one side and to a switch on the other side. Each adapter must be able to recognize about 2000 VP/VC fields (entries) per physical link and thus if it is attached to 4 physical links it must be able to recognize about 8000 entries.
To perform this function, the communication adapter comprises a table, which is updated by a network manager as a function of the connections which can be established by the adapter.
Consequently, for the purpose of performing the VP/VC swapping function, an 8000-entry table which can be searched and updated within a cell interval has to be implemented in each communication adapter.
One conventional way of implementing such a table consists in providing a content addressable memory. Another way consists in implementing binary search algorithms or hashing techniques.
A first drawback of these implementations is that the search operation takes the major part of the cell processing time. A second drawback results from the fact that a new entry in the table must be made at the right place and thus the table updating is not easy.
Examples of search algorithms are described in the article IEEE Proceedings Vol. 135 No. 1, January 1988.
SUMMARY OF THE INVENTION
An object of the subject invention is to provide an apparatus for swapping input values into output values which performs its swapping function in a very short time less than 2 microseconds, by using low-cost memories.
Another object of the subject invention is to provide such an apparatus wherein the memories can be easily updated to change the input values which can be swapped.
According to the present invention, the swapping function is performed through cascaded look-up tables coupled through a path whose width depends upon the number of entries permitted in the equivalent content addressable memory. Pointers have to be set and updated into the tables so that searching paths are unambiguously marked for all possible entries.
The swapping function is thus performed through a pseudo content addressable memory which provide output values corresponding to a number E of n-bit input values, with E=2
p
−1.
The pseudo content addressable memory is made of a plurality of cascaded random address memories having at least a 2
d
addressing capability, with d higher than p.
A control logic circuit is provided to store into each random access memory p-bits pointers, with each pointer being different from the others and randomly assigned to an input value. In order to find an output value corresponding to an input value, the control logic circuit sequentially address and reads the random access memories, the first memory being addressed with a part including a number n1 of bits of the input value, and each one of the next memories being addressed with the pointer read from the preceding memory concatenated with a part ni of bits of the input value, with ni equal to or lower than n−p. The output value is found as a result of the addressing of the last memory.
REFERENCES:
patent: 4984151 (1991-01-01), Dujari
patent: 5119369 (1992-06-01), Tanabe et al.
patent: 5280475 (1994-01-01), Yanagi et al.
patent: 5303233 (1994-04-01), Sugawara
patent: 5357508 (1994-10-01), Le Boudec et al.
patent: 5473598 (1995-12-01), Takatori et al.
patent: 0182501 (1985-10-01), None
patent: 0500238 (1991-02-01), None
patent: 0 500 238 (1992-06-01), None
“The concept of virtual paths and virtual channels in ATM-net”, Digital Communications, 1990 International Zurich Seminar.*
“Connection management and rerouting in ATM networks”, INFOCOM '94, 1994.*
Computer, vol. 10, No. 5, 5-77 pp. 68-74.
IEEE MICRO vol. 4, No. 2, 4-84 pp. 26-47.
Glaise Rene J.
Kermarec Francois
Lallemand Eric
Pham Tan
Schindler Hans Rudolf
Cockburn Joscelyn G.
Nguyen Than
LandOfFree
Apparatus for swapping input values into corresponding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for swapping input values into corresponding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for swapping input values into corresponding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838583