JP2734864B2 - 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]

A cell order matching method for an ATM switch according to the present invention is a method for replicating input cells in an ATM switching system for exchanging information in fixed-length cell units.
Broadcast means for simultaneously outputting to one or more output terminals
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 the output unit of the switch, and at the entrance of each unit switch module constituting the ATM switch , the input cell is connected to the switch stage of the switch stage.
Sui replication cell number of replicating unit switch module
In correspondence with pitch stage have a replication number of additional means for filling in, the output of the previous <br/> Symbol ATM switch, a first buffer for storing temporarily the cell passed through the ATM switch, the notification Hand
A second buffer that sequentially accumulates the number of cells with the same time stamp notified from the stage for each time stamp value.
Buffer and the time extracted from the second buffer.
One value of the stamp and the cell stored in the first buffer.
Time stamp value added to the
Comparing means for permitting output of cells having the same stamp value; and a description of each cell permitted for output by the comparing means.
Of the total number of copies obtained by multiplying the number of copies
The same number obtained from the second buffer
Subtract and update from the number with
At which time the next timestamp from the second buffer
Extract the number of cells with the same time stamp as the value
Characterized by chromatic and to control means.

[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
1, to 72n, to, 7m1, to 7mn are copy number adding 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 adding 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 e1 to e
m is a copy number part for writing the number of copies in each stage. Here, m is the same as the number of switch stages.

At the entrance of the switch, the copy number part e
"1" is written in all of 1 to em. Therefore the first
All the copy number portions of the cells input to the unit switch module of the stage are “1”. Next, when the first-stage unit switch module broadcasts the input cell to the i output terminals, the copy number adding circuit at the entrance of the first-stage unit switch module changes the copy number unit e1 to “ i ”. Input to the unit switch module. Similarly, in the second and subsequent unit switch modules, the copy number parts e2 to e
m is 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.

As the same time stamp information, the time stamp value notified from the time stamp generation control circuit 3 at the switch entrance via the bus 4 and its number information are stored in the buffers 61 and 62, respectively. 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 6
The time stamp value input to No. 3 is set in a memory in the comparison circuit 503. The time stamp value set in the buffer 63 is further compared with the comparison circuit 503 in each selection circuit.
And stored in the internal memory. Switch part 1
Are passed through the cell distributor 501 to the buffer 5.
02 once. Each time a new timestamp value is set in the memory in the selection circuit 5 and every time a cell is input, the timestamp values of all cells stored in the buffer 502 and the value of the copy number part are sent to the comparison circuit 503. The transmitted 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. Comparator circuit 503 sends a transmission permission signal to all control unit 64 the value of the duplication number portion corresponding to the matched cell at the same time as will be returned to the buffer 502 if they match. Control unit 64
Replication number portion e1 notified from the comparison circuit, the total duplication number calculated by multiplying the value of ～Em, the number of identical time stamp is set to the internal counter, one of the total duplication number min Decrement. The calculation of the total number of duplicates may be performed on the comparison circuit side and only the result may be notified to the control unit. When the counter value in the control unit 64 becomes 0, the control unit 64
2 and 63, and the next time stamp value is read into the buffer 63 in synchronization with the control signal,
Further, the number 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 Copy number addition 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-252186 (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
Duplicate the input cell of the M switching system and copy one or more
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
Notifying means for notifying the output unit of the switch together with the value of the stamp. At the entrance of each unit switch module constituting the ATM switch , the input cell is connected to the unit switch module of the switch stage.
Corresponding of replication cell number and switching stage to replicate in Joules
A first buffer for temporarily storing cells that have passed through the ATM switch at an output unit of the ATM switch; and the same time notified by the notifying unit. Accumulates the number of stamped cells sequentially for each timestamp 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
Multiplied by the number of copies of the number of cells
The same time-count obtained from the second buffer
Subtract and update from the number with tamping and the number becomes 0
Then the next timestamp value from the second buffer is
A system to extract the number of cells with the same time stamp
Cell sequence integrity scheme of the ATM switch; and a control means. 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: