JP2734863B2 - ATM switch cell order matching method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an ATM switch cell order matching system.

[0002]

2. Description of the Related Art An ATM (Asynchronous Tr) for transmitting, receiving, and exchanging information by dividing information into fixed length cell units.
An answer Mode) switching system is regarded as a promising system for realizing next-generation broadband communication. For practical use, a large-scale ATM switch capable of accommodating thousands to tens of thousands of lines is required. However, a large-scale ATM switch usually requires a plurality of unit switch modules of several tens of lines and a building block type. It is considered to be realized by connecting in multiple stages. FIG. 4 is a block diagram showing an example of a general ATM switch, showing an example of a three-stage connection configuration. 111,
13n are all unit switch modules. Here, there are two types of routing methods for the cells in the switch. One is a fixed routing method. This is a method in which routing is not performed for each cell, but a route is determined for each call when a call is set up, and cells belonging to the same call pass through the same route.

There is also a distributed routing method for selecting a route for each cell. Various methods are available for selecting a path for each cell in the distributed routing method. For example, in the case of a three-stage switch, a method of randomly selecting a path from the first stage to the second stage switch has been proposed. (The route from the second stage to the third stage switch is uniquely determined by the outgoing line.) In this system, unlike the case of the fixed routing system, no block occurs. Control (Sezaki et al., IEICE Transactions BI, Vol. J-72-B-
I, No. 11, 1989, 11).

[0004]

As can be seen from FIG. 4, there are a plurality of routes between a specific input and output. However, in fixed routing, only one of the routes is used. May occur. The block means that the call cannot be accommodated due to the blockage of the link in the switch even though the input / output line has a free capacity to accommodate the call. On the other hand, in the distributed routing method in which a route is selected for each cell, since cells belonging to the same call pass through different routes, the order of the cells in the switch is reversed in the switch due to a difference in buffer waiting time for each route in the switch. A new problem arises. As a matching method for reversing the order of the cells, a time stamp adding method has been proposed. (For example, the document “Study of control method in large-scale ATM switch” (Hayashi et al., IEICE Technical Report SSE89-173, 1989)
Such. This adds a timestamp to each cell at the entrance of the switch, indicating the input time of each input cell,
At the exit of the switch, cells are temporarily stored in a buffer, aligned in the order of time stamps, and output to an outgoing line. In this time stamp method, the order relation between cells arriving in the buffer can be known by comparing the time stamp values, but this alone is not sufficient. It must be ensured that no cell is older than the cell with the oldest timestamp value currently stored in the buffer and has not yet arrived in the buffer due to delays in the switch. For this purpose, a method has been proposed in which each cell has a fixed delay from the arrival of the buffer until the transmission. If this fixed delay is set to be equal to or greater than the maximum value of the passage delay in the switch, the order is not reversed, but the delay of the cell increases by that amount, which is not preferable. Although the maximum value of the passage delay in the switch depends on the buffer capacity and the link speed on each path in the switch, it is generally considered to be about several tens μsec to 100 μsec.

Another point to consider is the broadcast function of the switch. Generally, each unit switch module has a broadcast function of duplicating a cell input from an input terminal of the unit switch module and simultaneously outputting the copied cells to a plurality of output terminals of the unit switch module.

[0006]

According to the cell order matching method of the ATM switch of the present invention , one or more input cells are used in an ATM switching system for exchanging information in fixed-length cell units.
Includes broadcast means that duplicates and outputs simultaneously to the upper output terminal
Multiple unit switch modules are connected in multiple stages.
In ATM switches, to the inlet portion of the ATM switch, a time stamp adding means for adding to each cell to generate a time stamp indicating an input time of each input cell, the number of cells marked with the same timestamp the same time stamp counting means for counting, the same timestamp
The number of cells marked with the
Notifying means for notifying an output unit of the switch, wherein at the entrance of each unit switch module constituting the ATM switch, a front switch of the cell described in the input cell is provided. the replication number of cells up stage switch
Have a replication number number rewriting means for rewriting the number obtained by multiplying the replication number in the unit switch module switch stage as a new replication number of each cell, the output of the ATM switch, once a cell has passed through the ATM switch No. to save
1 buffer, a second buffer for sequentially accumulating the number of cells with the same time stamp notified by the notifying means for each time stamp value, and a second buffer.
One value of the time stamp extracted from the
Timestamp added to the cells stored in the first buffer
The value of the time stamp is compared with the value of the stamp.
Comparing means for permitting output of Le, the comparing means outputs
Reduce the number of duplicates written in each permitted cell
The same time stamp retrieved from the second buffer
When the number becomes 0 after subtracting and updating from the number with
The same value of the next time stamp from the second buffer
Characterized by chromatic and control means <br/> retrieve the number of cells marked with timestamps.

[0007] The control means is adapted to perform a predetermined time
When the time has elapsed, the same
Time stamp to force the number of cells
It is characterized in that it further includes an image means .

[0008]

According to the present invention, the number of cells having the same time stamp which have been input to the switch and which have not yet been output is always known. Even if a cell is duplicated inside the switch by the broadcast function, whether or not all cells having the above time stamp value including the duplicated cell have been transmitted from the buffer by updating the number of duplicates by each unit switch module You can know. Therefore, it is possible to output each cell in order without waiting for the maximum passage delay time in the switch. This greatly reduces the cell delay. For example, when the maximum delay of the switch passing is set to t and the average delay is set to t / 2, and the fixed delay in the case not according to the present invention is set to t, the worst case is 2t and the average is 3t /.
However, according to the present invention, only a delay of t and an average of t / 2 are added according to the present invention.

[0009]

Next, an embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of a cell order matching method for an ATM switch according to the present invention. In FIG. 1, 1 is a switch unit, 21 to 2n are time stamp addition circuits, 3 is a time stamp generation control circuit, 4 is a bus for notifying the same time stamp information, and 51 to 5n are buffers and comparison circuits, respectively. , A time stamp recording / updating circuit, 711-71n, 72
Reference numerals 1, to 72n, to, 7m1, to 7mn are copy number updating circuits in each unit switch module.

The time stamp adding circuits 21 to 2n add the time stamp at the time of input to a part of the header of the cell input from each input line and input it to the switch. The time stamp generation control circuit 3 distributes the synchronizing signal to each of the time stamp adding circuits 21 to 2n for each time slot of one cell time width, and the time stamp adding circuits 21 to 2n The time stamp value is updated by incrementing the counter. Each time stamp adding circuit 21,.
n notifies the time stamp generation control circuit 3 of the presence / absence of a cell that has entered this time slot for each time slot. The time stamp generation control circuit 3 obtains the number of cells input to the switch in this time slot from the signals from the time stamp adding circuits 21 to 2n, and outputs the number of cells together with the time stamp value corresponding to this time slot to the switch exit. The time stamp recording / updating circuit 6 is notified via the notification bus 4. Time stamp record
The update circuit 6 stores the received time stamp value and the number of cells as a pair in the memory.

Next, the operation of the copy number updating circuit at the entrance of each unit switch module will be described.
FIG. 3 is an explanatory diagram showing a format of a cell in the switch. In FIG. 3, a is a header part, and b is an information part.
The inside of the header section a is further divided into three areas. c is a routing unit including routing information, d is a time stamp unit in which a time stamp value is written, and e is a copy number unit in which the number of copies is written.

At the entrance of the switch, all "1" s are written in the copy number part e. Therefore, all the copy number portions of the cells input to the first-stage unit switch module are “1”. Next, when the first-stage unit switch module broadcasts the input cell to the i output terminals, the copy number updating circuit at the entrance of the first-stage unit switch module sets the copy number part to i (1 × i). And then input to the unit switch module. In the unit switch modules in the second and subsequent stages, a plurality of parts are similarly updated.

Next, the operation at the switch outlet will be described. FIG. 2 is a block diagram showing an example of a detailed configuration of the selection circuit and the time stamp recording / updating circuit of the switch exit section in FIG. In FIG. 2, the selection circuit 5
Represents a cell distributor 501, a buffer 502, and a comparison circuit 5
03, and a cell concentrator 504. The time stamp recording / updating circuit 6
, The same time stamp number storage buffer 62, the buffer 63, and the control unit 64. Although only one is shown here, the number of the selection circuits 5 is equal to the number of output lines as shown in FIG. 1, and each of them is disposed between the switch output unit and the output line.

The same time stamp information is stored in the buffers 61 and 62, respectively, with the time stamp value and the number information notified from the time stamp generation control circuit 3 at the switch entrance via the bus 4. The buffers 61 and 62 are FIFO buffers, and are read out in the order of input by a control signal supplied from the control unit 64. That is, the time stamp values are sequentially input to the buffer 63, and the number is sequentially input to the counter in the control unit 64. Buffer 63
Is set in the memory in the comparison circuit 503. The time stamp value set in the buffer 63 is further transferred to a comparison circuit 503 in each selection circuit and stored in an internal memory. The cells passing through the switch unit 1 are transferred to the buffer 50 via the cell distributor 501.
2 is stored once. Each time a new time stamp value is set in the memory in the selection circuit 5 and each time a cell is input,
The time stamp value and the number of copies of all cells stored in the buffer 502 are sent to the comparison circuit 503, and the sent time stamp value is compared with the time stamp value set in the comparison circuit 503. As a result of the comparison, a transmission permission signal is sent from the comparison circuit 503 to the buffer 502 for the matched cell, and the corresponding cell is output to the output line via the cell concentrator 504. Comparison circuit 503
Sends a transmission permission signal to the buffer 502 if they match, and simultaneously transmits to the control unit 64 the number of copies corresponding to the matched cells. The control unit 64 decrements the number of identical timestamps set in the internal counter by the number obtained by dividing 1 by the number of duplicate cells notified from the comparison circuit 503 (that is, 1 / the number of duplicates). When the counter value becomes 0, the control unit 64
Sends a control signal to the buffers 61, 62 and 63, the next time stamp value is read into the buffer 63 in synchronization with the control signal, and the number of the time stamp value is newly set in a counter in the control unit 64.

Although omitted in the description so far, cells may actually be lost in the switch unit.
It is necessary to reset the counter due to timeout. That is, the control unit 64 has a timer for each time stamp value, and forcibly sets the number of time stamps corresponding to this time stamp value to 0 after the maximum passage time in the switch has elapsed. Thus, even if a cell is lost in the switch, subsequent cells can be transmitted.

By repeating the operation described above,
Cells are transmitted in the order of input to the switch without reversing the order.

[0017]

As described above, according to the present invention, it is possible to replace an ATM switch with no delay in the switch and no block in the switch. Further, the present invention has an effect that the broadcast function of the switch can be supported.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of an ATM switch cell order matching system according to the present invention.

FIG. 2 is a block diagram showing an example of a detailed configuration of a selection circuit and a time stamp recording / updating circuit of a switch exit unit in FIG. 1;

FIG. 3 is an explanatory diagram showing a format of a cell in a switch.

FIG. 4 is a block diagram illustrating an example of a general ATM switch.

[Explanation of symbols]

Reference Signs List 1 switch section 3 time stamp generation control circuit 4 bus 6 time stamp recording / updating circuit 21,..., 2n time stamp adding circuit 51,..., 5n selection circuit 61 time stamp storage buffer 62 identical time stamp number storage buffer 63, 502 buffer 64 control unit 111, to 11n, 121, to 12n, 131, to 13
n unit switch module 501 cell distributor 503 comparison circuit 504 cell concentrator 711-71n, 721-72n, 7m1, -7m
n Number of copies update circuit

Continuation of the front page (56) References JP-A-3-82243 (JP, A) JP-A-3-255748 (JP, A) JP-A-5-252156 (JP, A) JP-A-5-252187 (JP) , A) IEICE Transactions, VOL. J 72-BI, NO. 9 (1989-9-25), Hitoshi Ohara, Configuration of Self-Routing Switch with Other Buffers that Can Preserve Cell Order, PP. 698-709 IEICE Technical Report, SS E91-111 (1991-11-22), Toshiya Aramaki et al., Characteristic evaluation of cell-distributed ATM switch, p. 25-29

Claims (2)

(57) [Claims] 1. AT for exchanging information in fixed-length cell units
The input cells of one or more output terminals of the M switching system
Unit switch that includes a broadcast
ATM consisting of multiple modules connected in multiple stages
In the switch, the entrance portion of the ATM switch, counting the time stamp adding means for adding to each cell to generate a time stamp indicating an input time of each input cell, the number of cells marked with the same timestamp same The time stamp counting means and the number of cells having the same time stamp
And a notifying means for notifying an output of said switch with stamp value, the entrance portion of each unit switch modules constituting the ATM switch, prior to the cells being written to the cell input switch
Have a replication number number rewriting means for rewriting the number obtained by multiplying the replication number in the unit switch module of the switch stage in the replication number of cells to Chi-stage as a new replication number of each cell, the output of the ATM switch A first buffer for temporarily storing cells that have passed through the ATM switch, and the number of cells with the same time stamp notified from the notifying unit are sequentially stored for each time stamp value .
A second buffer that, one time stamp retrieved from the second buffer
Value and the value added to the cell stored in the first buffer.
Timestamp value and compare the
Comparing means for permitting output of the cell values match, double the comparison means is written in each cell to allow output
Retrieve one part of the number from the second buffer
Subtract and update from the number with the same time stamp
When the number becomes 0, the next time is output from the second buffer.
The number of cells with the same time stamp as the stamp value
Control means for extracting a number
Cell order matching method for M switch. 2. The control device according to claim 1, wherein the control unit determines that a predetermined time has elapsed.
Then, the same time stamp notified from the notifying means is output.
Timer means for forcibly setting the number of cells with a lamp to 0
2. The ATM switch cell order matching method according to claim 1 , further comprising: