JP2756604B2 - Self-routing switch network - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Field] The present invention mainly relates to a distributed ATM (Async) configured by connecting multiple stages of banyan networks based on 2 × 2 unit switches.
(Hronous Transfer Mode) This relates to a method for preserving cell order in a switch network.

That is, according to the present invention, arrival time information is added to a cell input in the self-routing switch network, the arrival time information added to this cell is compared in the routing network, and the cell with the earliest arrival time is preferentially output. Thus, the time order of the cells can be stored with a small number of additional circuits.

[Conventional technology]

FIG. 3 shows the configuration of a conventional distributed ATM switch using a Banyan network based on a 2 × 2 unit switch circuit.
In this example, a 2 × 2 unit switch circuit will be described, but an n × n unit switch circuit is generally satisfied.

The inventors of the present invention have previously disclosed the distributed ATM switch using the banyan network with a bypass link shown in FIG. 3 as Japanese Patent Application No. 1-28123.

The distributed ATM switch shown in FIG. 3 is a switch network using a banyan network with a bypass link.
101, 102, 103, 104 indicate input ports, and reference numerals 105, 10
6, 107 and 108 are output ports, and input ports 101 to 104
An output port number is assigned to the header of the input cell 110 input to the banyan network, and the input port is input to the banyan network, and the path is switched to output to the output port of the output port number assigned to the cell header in the banyan network. You.

Reference numeral 10 denotes 2 × 2 which constitutes a distributed network in the banyan network.
Reference numeral 11 denotes a 2 × 2 unit switch circuit which constitutes a routing network. This distributed network is for equalizing the link load in the switch network, and the routing network has a function of sending out to the corresponding output port according to the output port number assigned to each cell. In this switch network, a 2 × 2 unit switch circuit of a distributed network denoted by reference numeral 10 and a 2 × 2 unit switch circuit of a routing network denoted by reference numeral 11
A 2 × 2 unit switch element is configured with the two-unit switch circuit.

FIG. 4 shows the configuration of the 2 × 2 unit switch element.

The 2 × 2 unit switch circuit 10 of the distribution network includes an input link 20
1 is connected, a bypass determination circuit 20 that determines whether two input cells can be bypassed, and a distribution unit switch 21 that distributes the output of the bypass determination circuit 20 and outputs the output to the output link 202. Is provided.

The bypass output of the bypass determination circuit 20 is a bypass link.
2 × 2 unit switch circuit 11 of the routing network via 205
Are input to the buffers 25 and 27. 2 × 2 of routing network
Input link 20 is connected to buffers 26 and 28 of unit switch circuit 11.
Cell is input from 3.

The output of the buffers 25 and 26 is selected by the buffer selection circuit 23 from the cells input to the bypass link 205 and the input link 203. The buffer selection circuit 24 also selects one of the cells to which the bypass link 205 and the input link 203 are input. This buffer selection circuit
Outputs of 23 and 24 are input to a routing unit switch 22. The routing unit switch 22 is a switch that identifies an output port number of an input cell and outputs it to a corresponding path.

The conventional switch network shown in FIG. 3 is of a distributed type in which the unit switch circuits operate independently. It is easy to increase the scale by adding unit switch elements. It has a feature that it operates stably without generating an internal block for various input traffic.

However, this conventional switch has a disadvantage that the time order of cells is not preserved due to the operation of the distributed network.

For example, in FIG. 3, it is assumed that cells directed to the same output port are continuously input to a certain input port. The two cells belong to the same line and need to be output in input order.

However, due to the operation of the distributed network, these two cells are
It is output through different paths in the illustrated switch network. For example, the data is output through different paths such as the path 111 and the path 112 in FIG. This indicates that cells switched from the first input port to the eighth output port go through different paths inside the switch network.

Generally delay time in a path 111 and path 112 are different, one of the two cells that are continuously inputted, the cell and the delay time d ₁ of the first cell is larger than the delay time d ₂ of the next cell 2 cell hours or more Order is reversed.

As a solution to this drawback, the order of cells is assigned to each line, the order is monitored at the output port, and if the order is reversed, the cells are stored in a buffer and the order is monitored, and the order is reversed. In such a case, a method of storing cells in a buffer and correcting the order has been proposed.

However, since it is necessary to monitor and correct the order of one input and one output, it is difficult to achieve this at a high transmission rate on the order of Gd / s, and the processing circuit for that purpose becomes complicated and large-scale. was there.

SUMMARY OF THE INVENTION An object of the present invention is to solve the above-mentioned drawbacks and to provide a switch configuration that can preserve the time order of cells while utilizing the features of a conventional switch network having a distributed configuration.

[Means for solving the problem]

The present invention relates to a means for assigning an output port number of an output destination to an input cell, a distributed network for distributing an incoming cell to a random path and equalizing a load of a link in a switch network, and a distributed network for the distributed network. And a routing network for sending an incoming cell to a corresponding output port with reference to an output port number of a cell output destination, wherein the unit switch of the distributed network and the unit switch of the routing network are one unit. The two unit switches of the unit switch module are housed in a switch module and constitute a distribution network and a routing network, respectively, connected to the unit switches of the other unit switch modules. A cell to be input to a switch can be changed to a unit switch of a routing network without inputting to a unit switch of a distributed network. A bypass unit that outputs the input cell when the bypass tag added to the input cell matches the bypass collation pattern set in the own unit switch module, and the input cell is matched. In a self-routing switch network comprising means for inputting to a unit switch of a distributed network in the case of a mismatch, a unit switch for adding arrival time information to an input cell is provided, and the unit switch constituting the distributed network comprises: Means for adding a predetermined value to the arrival time information added to the cell,
The unit switch circuit constituting the routing network includes means for reading the arrival time information added to the cell, comparing the arrival time information of the cell, and transmitting the earlier arrival time information to the output preferentially. Features.

[Action]

The input cell receives arrival time information in addition to a destination output port number by a time stamp adding circuit, and inputs the information to the switch network.

First, in the distribution network of the switch network, the routes are distributed by the unit switch circuits so that the load on the switch network becomes uniform.

The unit switch circuit constituting the routing network identifies the arrival time information added to the cell arriving at the input link, and preferentially sends out the earlier arrival time of the cell to the desired output link.

By controlling in this way, the order of arrival of cells in the switch network can be preserved, so that switching can be performed in a distributed manner while preserving the time order of cells.

When a predetermined value, for example, “1” is added to the arrival time information given to the cell when distributing the route by the unit switch of the distribution network, the routing network is bypassed at the previous stage of the switch network. The cell transmission waiting time can be reduced to reduce the average transit delay time of the cell.

〔Example〕

 Hereinafter, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a diagram showing the configuration of a self-routing switch network according to one embodiment of the present invention. This switch network has a switch network configuration using a banyan network with an 8-input / 8-output bypass link. In this embodiment, a switch network of 2 × 2 unit switch circuits will be described, but an n × n unit switch circuit is generally satisfied.

Each input of the input ports 301, 302, 303, 304
Time stamp addition circuit 31, 32, 33, 34, 35, 36, 37,
The banyan net 39 is input via 38. The time stamp adding circuits 31 to 38 are circuits for adding arrival times to input cells. The counters are incremented in real time according to the cell cycle, and the count value is added as the arrival time.

Banyan network 39 is a switch network with a bypass link.
The internal topology and function are the same as those of the conventional banyan network shown in FIG.

The output of the banyan network 39 is connected to output ports 305, 306, 30
7, output to 307.

FIG. 2 shows the internal configuration of the 2 × 2 unit switch element constituting the banyan network 39.

The configuration of the 2 × 2 unit switch element shown in FIG. 2 is different from the conventional 2 × 2 unit switch element shown in FIG. A timestamp adding circuit 42 for adding "1" to the timestamp indicating the arrival time added by "1" is provided. The switching of the routing network compares the timestamp of the cell and determines the smaller cell. Time stamp comparison circuits 43, 44,
There is a characteristic where 45 is provided.

That is, the feature of the present embodiment is that a time stamp adding circuit 31 to 38 is provided as a means for adding arrival time information to a cell input to a switch network, and a unit switch circuit constituting a routing network includes Time stamp comparing circuits 43, 44, and 45 are provided as means for reading the added arrival time information, comparing the arrival time information of the cells, and sending out the one with the earlier arrival time preferentially to the output. The unit switch circuit comprises a time stamp addition circuit 42 for adding "1" as a means for adding a predetermined value to the arrival time information added to the cell.

 Next, the operation of the switch network of this embodiment will be described.

The cells input to the input ports 301 to 304 are provided with an output port number and the time stamp adding circuits 31 to 304.
After the arrival times are given at 38, they are input to the banyan net 39.

In the banyan network 39, the bypassable cells are input to the routing network buffers 46 and 48 via the bypass link 205. The cells that cannot be bypassed are added with "1" by the time stamp adding circuit 42, and then are distributed.
According to 21, load distribution is performed by randomly allocating routes.

All cells that have not been bypassed until the last stage of the banyan network 39 can be bypassed at the last stage and sent to the routing network. For this reason, the time order of the cells is not reversed in the buffers 46 and 48 of the last-stage routing network switch.

In the routing network, cells are taken out of the buffers 46 to 48 by the time stamp comparing circuits 43, 44, and 45. The signal is input to the unit 22 and output to a desired output path according to the output port number assigned to the cell by the unit switch 22 for routing. Therefore, the time order of cells input to each stage of the banyan network 39 is preserved.

In the same manner, the same processing is performed in each stage of the routing network, so that the chronological order of the cells is preserved in the entire Banyan network 39.

Here, the reason for using the time stamp addition circuit 42 will be described.

The value of the arrival time of the cell arriving later on the switch network is large, and the value of the arrival time of the cell arriving earlier is small. The cells bypassed in the front stage of the banyan network 39 have a short delay time, and the cells bypassed in the subsequent stage have a long delay time and are input to the routing network. For this reason, cells arriving later are bypassed at the front stage of Banyan net 39,
If the cell that arrives first is bypassed at the subsequent stage of the banyan network 39 and is input to the routing network, the cell bypassed at the front stage has a low priority, and the waiting time until it is removed from the buffer becomes longer. As a result, there is a disadvantage that the average transit delay time of the cell becomes longer.

To solve this, the time stamp adding circuit 42
Then, if the value of the arrival time of the cell bypassed in the subsequent stage is increased by adding “1”, the waiting time of the cell bypassed in the front stage is shortened and the average transit delay time of the cell is shortened. it can.

Even when the arrival times are added by the time stamp adding circuit 42, the time order of the cells can be preserved.

〔The invention's effect〕

As described above, in the switch network of the present invention, the time order of cells does not reverse the cell order stored in the switch network. For this reason, the present invention requires only a few circuits, namely, a time stamp adding circuit and a time stamp comparing circuit, to be added to a conventional switch, and these circuits add a counter output to a header of an input cell, It can be composed of a comparator circuit. The time stamp addition circuit is also "1".
Can be configured by an adder that adds

A time stamp adding circuit may be added corresponding to an input port. A time stamp adding circuit is provided for each 2 × 2 unit switch circuit of the distributed network, and a time stamp comparing circuit is provided for each of the routing networks. 2x
What is necessary is just to arrange in a 2 unit switch circuit.

As described above, in the present invention, self-routing is possible in a multistage connection form, and the original merit of a distributed self-routing switch network constituted by a uniform combination of switch elements is ensured by distributed control with a few additional circuits. The advantage is that the time order of the cells can be preserved.

The present invention requires a small additional circuit for preserving the cell order, can be configured economically, can be easily added for a distributed configuration, and has a uniform circuit configuration. Suitable for LSI.

There are advantages.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a self-routing switch network according to an embodiment of the present invention. FIG. 2 is a diagram showing a configuration of a unit switch element according to the embodiment of the present invention. FIG. 3 is a configuration diagram of a conventional self-routing switch network. FIG. 4 is a diagram showing a configuration of a unit switch element of a conventional banyan network with a bypass link. 10: 2 × 2 unit switch circuit of distributed network, 11: 2 × 2 unit switch circuit of routing network, 20: bypass determination circuit, 21: unit switch for distribution, 22: unit switch for routing, 23 , 24 ... Buffer selection circuit, 25-28,
46 to 49 buffer, 31 to 38 time stamp addition circuit, 39 banyan net, 40 unit switch element, 42 time stamp addition circuit, 43 to 45 time stamp comparison circuit, 101 to 104, 301-304 ... input ports, 105-108, 305-308 ... output ports, 110 ... input cells, 201, 203 ... input links, 202, 204 ... output links, 205 ... bypass links.

Continuation of the front page (56) References JP-A-2-206939 (JP, A) JP-A-2-195758 (JP, A) Transactions of the Institute of Electronics, Information and Communication Engineers, Vol, J 72-BI No. 9 (1989-9-25) pp. 698-709 IEICE Transactions, Vol., J 72-BI No. 11 (1989-11-25) pp. 1055-1061 Proceedings of the IEICE Spring Conference (3rd volume), B-436 (1989-3-15), p. 3-142

Claims (1)

(57) [Claims] 1. A means for assigning an output port number of an output destination to an input cell, a distribution network for distributing an incoming cell to a random path and equalizing a load of a link in a switch network, and A routing network connected to a network and transmitting an incoming cell to a corresponding output port by referring to an output port number of a cell output destination, wherein a unit switch of the distributed network and a unit switch of the routing network are one. The two unit switches of the unit switch module are housed in the unit switch module,
A distributed network and a routing network connected to the unit switches of the other unit switch modules are formed, and the unit switch module is configured to route cells input to the unit switches of the distributed network without inputting the cells to the unit switches of the distributed network. A bypass unit for inputting to the unit switch of the network, wherein the bypass unit compares the bypass tag added to the input cell with the bypass matching pattern set in the own unit switch module and matches the input cell if the match is found. Means for inputting to a unit switch of a routing network, and means for inputting to a unit switch of a decentralized network if they do not match, in a self-routing switch network, means for adding arrival time information to input cells, comprising the distributed network The unit switch that determines the arrival time information added to the cell Means for adding a value, wherein the unit switch circuit constituting the routing network reads the arrival time information added to the cell, compares the arrival time information of the cell, and preferentially outputs the one with the earlier arrival time. A self-routing switch network comprising transmission means.