JPH0748892B2 - Amida-shaped sorting switch - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an exchange switch that connects a plurality of input terminals and a plurality of output terminals without internal congestion (blocking).

[Conventional technology]

As a mitami-shaped switch, n (where n is an arbitrary integer) input terminals and n output terminals are connected in a one-to-one manner to transmit signals in one direction, A total of _n C ₂ switch elements (a combination of 2 out of n switches) are arranged across any two adjacent links to provide n input terminals and n output terminals. The inventors of the present invention have already proposed a structure in which the spaces can be connected without causing internal congestion (blocking), and a patent application is pending as Japanese Patent Application No. 61-30546.

As a remark, the commonly known Amida lottery proceeds according to the rule that the traveling direction always changes when it hits an intersection, but in the case of an Amida-shaped switch as well, if it starts from an input terminal and hits a path (switch element), The connection route is formed under the rule that the direction must be changed.

In such a proposed switch, it is necessary to have information on whether each switch element is currently in the ON or OFF state in order to perform the desired switching.This information and the input terminal number and the output terminal number are required. Which switch element is turned on based on
Or I was deciding whether to turn it off. In other words, it is necessary to have information for all the ON / OFF states of each switch element (2 _n C _{2 power} ), and the larger n becomes, the more information is required and the switching algorithm becomes complicated. There was a drawback to do.

Moreover, with this switch, in order to connect without internal congestion (blocking) by the above switching algorithm, the connection path between the preset input terminal and output terminal is changed even if the input and output connection relationships do not change. In some cases, it is necessary, and if the terminal is in use, the connection route changes during communication.

A switching example of this conventional switch will be described with reference to FIG.

FIG. 14 shows n = 4 composed of _n C ₂ switch elements.
In the configuration example of the switch proposed in Japanese Patent Application No. Sho 61-30546, 101, 102, 103, 104 are input terminals, 111, 112, 113, 114 are output terminals, 121, 122, 123, 124 are links, 131, 132, 133, 134, 135, 1
36 is a switch element (also referred to as a path), and this switch element can take two states of ON and OFF as shown in FIG.

That is, as shown in FIG. 15 (a), when it is in the OFF state, the input terminals 141 and 142 are connected to the output terminals 151 and 152.
Fig. 15 (b) when connected to and kept in the ON state.
As shown in, the input terminals 141 and 142 are crossed and connected to the output terminals 152 and 151, respectively.

FIG. 14 shows the state when all the paths 131 to 136 are ON. Input terminal name is a, b, c, d, output terminal name is 1,2,3,4,
Assign input terminal names that pass through each path. In the state of Fig. 14, regardless of whether each terminal is used or not, the input terminal and the output terminal are a-4,
It is connected to b-3, c-2, d-1.

Suppose now that you want to connect the terminal of a to the output terminal 1 (terminal d,
1 is assumed to be unused). In this case, the state after switching corresponds to switching the connection destinations of a and d. Therefore, turn on the path 133 with the terminal names a and d.
When switching from to OFF, terminal a is connected to terminal 1.

Next, consider the state of FIG. 16 in which only the path 133 is OFF. Assuming that terminals a-1 and c-2 are in use, and now trying to connect terminal b to terminal 4, this switching will result in path 13
This can be achieved by turning 3 from OFF to ON and turning paths 131 and 134 from ON to OFF. The state after this switching is shown in FIG.

However, in this switching, the connection route of a-1 is changed, and moreover, switching is complicated as compared with the example shown in FIG. 14 described above. In any case, switching depends on the ON / OFF status of the path at that time, and which path is ON / O depending on which terminal is connected to which terminal in each status.
A huge amount of information on whether to FF is required.

In addition, as an amido-type switch capable of preventing blocking without changing the preset connection path, an amida-type non-blocking switch composed of (2 ⁿ −n−1) switch elements is used. After all, the present inventors have already proposed and have applied for a patent as Japanese Patent Application No. 61-80201.

However, the switching control of such a proposed switch is
Similar to the above-mentioned switch, information on all ON / OFF states of all switch elements is required, and since the number of elements is much larger than that of the above-mentioned switch, the switching algorithm becomes more complicated. .

Therefore, it is important to provide a simple switching algorithm when using the amidida switch.

[Problems to be solved by the invention]

Therefore, the present invention is to solve the problem to configure an amida-type switch that can be switched by a simple algorithm,
It is an object of the present invention to provide an amido-shaped sorting switch that enables this.

[Means for solving problems]

The present invention is configured such that the Amid-shaped switch filed as Japanese Patent Application No. 61-30546 can actually be switched only by the output terminal number by utilizing the fact that it has a sorting function.

Here, sorting means sorting a list of a certain entry in order according to a numerical value, and the sorting technology is said to be one of the most studied technologies in computers.

As a sorting switch, a switch by Batcher is well known. This is a method of connecting a link between the elements in a switch configured by combining a plurality of 2 × 2 switching elements which is the basis of sorting. No special restrictions are set. On the other hand, the switch form targeted by the present invention is a switch belonging to a set of forms in which the links between the 2 × 2 switch elements are not crossed with each other. That is, it is a feature of the present invention that a switch belonging to such a set (which is called an "amidami switch") has a sorting function.

[Action]

Unlike the conventional Amid-shaped switch, the Amid-shaped sorting switch according to the present invention does not need to know the states of all switch elements, and moreover, the switching control function is distributed to each element to perform self-routing. The control function is not required or the load can be significantly reduced.

〔Example〕

 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 the present invention, that is, an example in which a sorting switch according to the present invention is configured by using the switch shown in FIG.

In FIG. 1, 201, 202, 203, and 204 are output address adding devices for editing an input signal by adding an output address corresponding to the terminal number of the connection destination to a predetermined information format and transmitting the signal in synchronization with a clock. ,twenty one
3,214,215,216 are switching elements, 221,222,223,224 are circuits for delaying the switching time T of the switching elements, 23
Reference numeral 1 is a clock supply control circuit for inputting to each device of 201 to 224 in a cycle of time T.

The switch elements 211 to 216 compare the magnitude of the output addresses of the two signals input to the element, and turn ON or OF depending on the result.
Has a function (sorting function) to control either of F. FIG. 2 shows an example of this. When the sizes of the output addresses i, j are compared, if i <j, then as shown in FIG.
If i> j, it is switched ON as shown in FIG. 2 (b). In this example, sorting is performed in ascending order, but all may be sorted in reverse.

As an example, consider an example in which signals at the output addresses, respectively, are input to the input terminals a, b, c, d in FIG. For example, since the address signal is input to the switch of 211 from the link of 121 and the address signal is input from the link of 122, the switch is controlled to ON when sorting in ascending order. In this way, it can be seen that switching is performed as shown in FIG. However, FIG. 3 is expressed only by switching elements for the sake of clarity.

By the way, it can be proved that an amida-type switch consisting of _n C ₂ paths can be sorted as follows.

First, for simplification of the proof, suppose that _n C ₂ paths are arranged as follows. _{Since n} C ₂ = _n-1 C ₂ + (n-1), a switch having n terminals can be constructed by adding (n-1) paths to a switch having (n-1) terminals. Therefore, the number of terminals n
Can be defined by giving a method of adding (n-1) paths to a switch having (n-1) terminals.

First, when n = 2, there is only one way of arranging ₂ C ₂ = 1 paths in FIG. Next, assuming that a switch having the number of terminals n is configured, a switch having the number of terminals (n + 1) is configured as shown in FIG. Next, a switch having the number of terminals (n + 2) is constructed as shown in FIG. 6 by using the switch shown in FIG. In general, the case of n can be constructed by alternately repeating the methods of FIGS. 5 and 6 based on the configuration of FIG.

At this time, FIGS. 5 and 6 may be reversed. That is, in the case of configuring a switch of n = 3 based on FIG.
Applying the figure results in FIG. 7, and applying FIG.
It becomes a figure. When configuring n = 4, FIG. 6 is applied when using FIG. 7, and FIG. 5 is applied when using FIG. The respective configurations are shown in FIGS. 9 and 10. It may be configured according to this rule.

Therefore, the sorting proof is performed by using the mitami-shaped switch configured in this way. First, when n = 2, it is obvious that sorting can be performed because only one switching element is used.

Next, in FIG. 5, it is assumed that a switch having n terminals can be sorted. That is, for example, its output b ₁ , b ₂ ,
…, B _n becomes b ₁ <b ₂ <... <b _n . These and terminal a _{n + 1}
If n paths are input to the portion 902 where the paths are arranged in stages, it is easy to confirm that the output is properly sorted. Since it holds for n = 2, it can be seen that it holds for n in general by the principle of induction. FIG. 11 shows an example in which the switch of the present invention is configured using this form.

In this way, when signals having different addresses are simultaneously input to the n terminals, it is possible to connect to a desired connection terminal without fail by sorting with each switch element. At this time, the delay element is adjusted so that two signals are simultaneously input to each switch element.
The maximum switching time required for the input signal to be output is _n C ₂ × T at maximum (depending on the path layout).

However, it is not necessary to have the next signal input until all the previously input signals are output, and the signals can be input one after another at intervals of time T. This is shown in FIG. That is, if signals arrive at each incoming line at intervals of time T, they can be input to the switch without waiting, and delayed by a delay time mT determined by the configuration of the switch and output to each output line one after another.

By the way, in this structure, signals input to the respective input terminals at the same time are output to the respective output terminals at the same time. If each output line is independent and the time required for switching does not have to be the same for all output lines, omit the delay circuit between each output terminal and the closest switch element as shown in Fig. 13. You can

〔The invention's effect〕

As described above, according to the present invention, in an Amit type switch, it is possible to perform switching very simply by using only the output address, and since it is self-routing, the switching control function is distributed and the speed is increased. be able to.

Further, the switch of the embodiment of the present invention may cause blocking when a fixed route is used after switching at the time of call setup. However, if switching is performed in the information unit in the cycle T as in the present invention, blocking does not occur.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is an explanatory diagram showing possible states of the switch element shown in FIG. 1, and FIG. 3 is switching by sorting. FIG. 4 is an explanatory diagram showing an example of arrangement of switch elements, FIGS. 5 and 6 are explanatory diagrams showing one method of path arrangement, and FIG. FIG. 8 is an explanatory diagram showing a case where the configuration is performed by the method shown in FIG. 8, FIG. 8 is an explanatory diagram showing a case where the switch form is configured by the method shown in FIG. 6, and FIGS. 9 and 10 are path layout diagrams, respectively.
FIG. 11 is a block diagram showing another embodiment of the present invention, FIG. 12 is an explanatory view showing a situation in which signals are continuously input to the embodiment shown in FIG. 11, and FIG. FIG. 14 is a block diagram showing still another embodiment of the present invention, FIG. 14 is an explanatory view showing the configuration of a conventional fold switch, and FIG. 15 is an explanatory view showing possible states of a conventional switch element, FIG. 16, FIG. FIG. 17 is an explanatory diagram showing a switching method of the Amid type switch. Description of symbols 201,202,203,204 ... A device that adds an output address corresponding to the terminal number of the connection destination to an input signal, edits it into a predetermined information format, and sends the signal in synchronization with a clock, 211,212,213,214,215,216 ... Switch element, 22
1,222,223,224 ... Circuit for delaying switching time T of switch element, 231 ... Clock supply control circuit, 241,2
42,243,244,245,246,247,248,249,250,251,252 ... Delay circuit.

Claims (1)

[Claims] 1. An exchange switch having n input terminals and n output terminals and capable of setting a connection path from an arbitrary input terminal to an arbitrary output terminal (where n is an integer of 2 or more). )
Between the n input terminals and the n output terminals, which are connected in a one-to-one manner to transmit signals, and between the two adjacent transmission paths. 1 between the two input terminals that are arranged and are aligned with 1,2 and the two output terminals that are aligned with a and b
-a, 2-b connection state A and 1-b, 2-a connection state B two connection states are switched by switching control 2x2 unit switch element, and the above n n When the transmission line numbers and the input terminal numbers from 1 to n are sequentially assigned to the transmission lines and the n input terminals connected to them in a one-to-one manner, the unit switch element in the connection state B is The input terminal number i (1
The signals input from the input terminals of ≦ i ≦ n pass in the ascending order of the transmission line number, and the input terminal number j (however,
(1 ≦ j ≦ n, j ≠ i) When a signal input from an input terminal of (1 ≦ j ≦ n, j ≠ i) passes in the descending direction of the transmission path number, (i, j) is arranged at the location (i, j) of the unit switch element. In the exchange switch, a total of n × (n−1) / 2 pieces are arranged so that all the combinations of numbers in () are different, and output terminal numbers 1 to n are sequentially assigned to the n output terminals. In this case, for a signal input from an arbitrary input terminal of the n input terminals, an arbitrary output terminal number of the n output terminals to be the output destination and 1
Means for assigning output addresses, which correspond to the pair 1 and are assigned in ascending order like the output terminal number, are provided for the n input terminals, and in each of the unit switch elements, the input terminal 1 of the unit switch element is provided. The output control signals A1 and A2, which are given to the two signals input from the input terminals 2 and 2, respectively, are compared in magnitude, and if A1 <A2, the connection state A is set, and if A1> A2, the connection state B is set. Or switching control means for setting the connection state B in the case of A1 <A2 and the connection state A in the case of A1> A2, each of the unit switch elements is provided with either one of the means. A mida type sorting switch characterized by this.