JPH0787603B2 - Multiple connection method in multi-stage switch network - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a system for performing one-to-many multiple connection used for broadcasting and conference communication in an exchange.

[Conventional technology]

When performing one-to-many multiple connections in an exchange, conventionally,
This has been done by expanding the normal multistage switch network for one-to-one connection. This conventional one-to-many multiple connection system is described in Yoshiaki Tanaka, Kaoru Sezaki, Minoru Akiyama "Multi-to-one connection three-stage switch network", IEICE Transactions, 87/2, Vol.J70.
-B No. 2, pp. 179-185, F. K.
Wang (FKHwang), A. Jaiszcz
yk) “On nonblocking multiconnection network
warks) ”and“ I Triple E Transaction on Communication (IEEE Trans
action on Communication) "COM-34, No. 10, 103
Those described on pages 8 to 1041 are known.

An example of such a conventional technique is shown in FIG.
FIG. 4 shows a three-stage switch network used to make a one-to-many multiple connection according to the prior art. This switch network consists of r n-inputs and m-outputs with a total of N input terminals connected.
The output of the secondary grid switches 400-401 and all primary grids is 1
M r-input and r-output secondary grid switches 410 to 412 connected to the inputs one by one, and the outputs of all secondary grids are connected to the input one by one, and a total of N output terminals are connected. It is composed of r third-order lattice switches 420 to 421 having m inputs and n outputs.
In this 3-stage switch network, if m = 2n-1, then 1: 1
For the connection of, you can connect any empty input terminal to any empty output terminal, which is said to be non-blocking.

Considering that multiple connections are made in the switch network shown in FIG. 4, when multiple connections are made only by a tertiary lattice, a link connecting lattice switches is used more than in the case of one-to-one connection. Therefore, it is possible to perform one-to-many multiple connection while leaving the switch non-blocking for one-to-one connection.

Further, in this switch network, for example, in the case of performing a one-to-two multiple connection for connecting the input A to the outputs B and C, if the multiple connection can be performed by the secondary lattice 411 as shown by the dotted line, it is also 1 For a one-to-one connection, leave it unblocked 1
Many-to-many multiple connections can be made.

The reason will be described below. As shown in FIG. 5, a plurality of virtual primary lattices 502 shown by dotted lines in the switch network of FIG.
~ 503 and secondary grids 513 to 514 are provided to create a virtual primary grid 5
All 2 including the virtual output from 02 to 503
Consider a switch network that can be virtually connected to the inputs of the next grids 510 to 514 and can be connected from all virtual input terminals in a non-blocking manner. Input A to output B, C shown in Fig. 2 2
Comparing the case of multiple connection with the next lattice and the case of 1: 1 connection of input A and output B and virtual terminals input D and output C shown in FIG. , 2nd order, 3
The use state of the input and output of the next switch can be made to be exactly the same in FIG. 4 and FIG. Further, since FIG. 5 shows the one-to-one connection non-block switch network, such one-to-one connection can be surely performed. Therefore, the fourth
In the figure, it can be seen that even when the multiple connection is performed by the secondary lattice, the one-to-many multiple connection can be performed while the switch is in the one-to-one connection non-blocking state.

[Problems to be Solved by the Invention]

However, in the above-described three-stage switch network, if multiple connections are required in the primary lattice, if an attempt is made to make a one-to-one connection equivalent to a one-to-many connection, the actually existing primary One input that is not used by the grid is virtually used. Therefore, it is not possible to make a one-to-many connection in the primary lattice while keeping the network state as a one-to-one connection non-block.

Furthermore, in the prior art, even with respect to the minimum number of multiple connections, one-to-two connections, multiple connections must be performed using a primary lattice, and there is a state in which the state of the network cannot be maintained in a one-to-one connection non-block. This is shown in the schematic diagram of FIG.

As shown in FIG. 6, an input A belonging to the primary lattice 600
Consider connecting to the outputs B, C of the cubic lattice 620, 621.
It is assumed that the other n-1 inputs and outputs of the primary lattice to which the input A belongs and the tertiary lattice to which the outputs B and C belong are already used by another call. Then, in FIG. 6, it can be seen that it is not possible to connect to the outputs B and C using only one secondary grid connected from the primary grid 600 by an empty link without performing multiple connection in the primary grid. . That is, in the secondary lattice 612 in which the output to the tertiary lattice 620 is empty, the output to the tertiary lattice 621 is not empty, and the output to the tertiary lattice 621 is empty 2.
This is because the output to the tertiary lattice 620 is not empty in the secondary lattice 613. In such a case, when the connection request is accepted, the state of the network cannot be maintained in the one-to-one connection non-blocking.

The probability of the above occurrence is r
Consider a case where one-to-many connection is made from one secondary lattice to all the tertiary lattices. In this case, in the above-described single-link connection switch network in which there is only one output going from each secondary lattice to a certain tertiary lattice, since there is only one output to each tertiary lattice, there is no output. A secondary grid that is not used is needed. The probability Ps of finding this quadratic lattice is Ps = (1/2) ^rm , assuming that the probability of using the output terminal of the quadratic lattice is 1/2, if a very simple estimation is performed (m is Number of secondary lattices). In this network, it can be said that there is a high possibility that the connection cannot be made even if the network state is set to non-blocking even in the one-to-two connection.

The above explanation was made for the three-stage switch, but 2i-1
The same applies to switches of (i = natural number of 2 or more) stages.

As mentioned above, 2i, which is non-blocking with one-to-one connection
In order to prevent the subsequent 1-to-1 connection request from being affected in the -1 stage multi-stage switch network, there is a problem that the 1-to-multi connection request must be rejected at a high probability.

An object of the present invention is to provide a multiple connection method in a multi-stage connection network that solves such a problem and greatly increases the possibility of making a one-to-many connection while keeping the one-to-one connection non-blocking. To provide.

[Means for Solving the Problems]

The present invention relates to a multiple connection method in a multi-stage switch network in which lattice switches are connected in 2i-1 stages (i is a natural number of 2 or more), and links connecting each stage are n-fold (n is a natural number of 2 or more) multiple links. Connection, connection of input and output is one-to-one,
Also, when performing one-to-many multiple connection, branch connection is performed from the stage closer to the output with a lattice switch, and the j-th stage (i ≦ j ≦ 2i
1) multi-branching connection is performed so that at least one link among the n-fold multiple links from the lattice switch belonging to (1) to each j + 1-th lattice switch can be left unused without being used. When it is not possible to leave at least one link open for all n-fold links from the j-th stage to the j + 1-th stage by selecting the lattice switch at the stage and setting multiple connection paths, Multi-branch connection is performed so that the number of all n links to the lattice switch at the stage is all in use j
It is characterized in that the lattice switch at the stage is selected to set a multiple connection path.

According to the present invention, in the one-to-many new connection and the request for increasing the number of connected outputs, there is a vacancy in the output link of the lattice switch from the i-th stage to the 2i−1-th stage, and the i-th stage to the 2i−1-th stage. If multiple desired outputs can be connected to one input only by the multiple branch connection in the stage lattice switch, the connection request is accepted, and the multiple connection is performed in the lattice switches from the i-th stage to the 2i-1th stage. It is preferable to reject a connection request in which there is no required output link space and a multi-branch connection is required by the lattice switches in the first to (i-1) th stages.

Further, according to the present invention, it is preferable to limit the number of multiple connections to a predetermined number and receive.

Further according to the invention it is preferred that the multi-stage switch network is non-blocking for one-to-one connections.

[Action]

The present invention increases the possibility of making a one-to-many connection as follows.

In the case of a multi-link connection switch network in which there are a plurality of outputs going from each secondary lattice to a certain tertiary lattice, it suffices if the outputs to all the tertiary lattices are free. The probability Pm of finding such a secondary lattice in a double-link connection switch network is defined by the following two outputs from a certain secondary lattice to a target tertiary lattice.
Since only one vacant line is required, Pm = (3/4) ^r (m / 2), which is (1/2) (3/2) ^r times larger than the case of a single link. Further, in the case of the multi-link connection switch network, it is possible to control the route connection so that the route from a certain secondary lattice to each tertiary lattice is not closed as much as possible. For example,
In the case of a double link, it is possible to control the route between the input and output so that only one of the double links is used. By performing such control,
The difference between the probabilities Ps and Pm described above becomes even larger.

Further, by limiting the number of multiple connections to a certain small number k (k is a number smaller than r), the probability Pm of connection with a secondary lattice or a tertiary lattice is (3/4) ^k (m / 2) It can be made larger than the above.

〔Example〕

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

FIG. 1 is a block diagram showing an example of a multistage switch network for implementing the present invention. This multistage switch network has r n-input and m-output primary grid switches 110 to 112 to which a total of N input terminals are connected, and two outputs of all primary grids are connected to two inputs each. M / 2 2r input, 2r output secondary grid switches 120 to 122 and all 2 secondary grid outputs are connected to the input, and a total of N output terminals are connected to the r output grids. It is provided with m-input and n-output third-order lattice switches 130 to 132.

In this switch network, if m = 2n−2, an arbitrary empty input terminal can be connected to an arbitrary empty output terminal for one-to-one connection. So here, N = 12, n
= 4, m = 6, r = 3.

In such a case, in the multistage switch network of FIG. 1, a virtual primary lattice and a secondary lattice are provided as in the conventional example shown in FIG. 5, and the output of one virtual primary lattice is provided. Consider a switch network that is connected to the inputs of all secondary lattices including virtual ones, and the connections from virtual terminals are also non-blocking for one-to-one connections. Then, for the same reason as described in the conventional example, the double link switch network of FIG. 1 is not connected to the one-to-one connection only when the multiple connection is performed by the secondary lattice and the tertiary lattice. It is possible to set the route while keeping the block.

Next, when one-to-many multiple connections are made in such a multi-stage switch network, the multi-stage switch network sets a route according to the flowchart of FIG. For example, in the one-to-one connection non-blocking switch network shown in FIG.
And output terminals B and C are connected in a 1: 2 multiplex. In this network, the route between input and output has already been set, and the secondary lattice 12
Three outputs of 0 are evenly vacant, two outputs of the secondary lattice 121 are vacant, three outputs of the secondary lattice 122 are vacant, and two outputs to the tertiary lattice 132 are vacant. Suppose it is free.
First, since the outputs B and C belong to different cubic lattices (step S21), it is not possible to set the route by multiple connection in the cubic lattice. Next, in consideration of making multiple connections with the secondary lattice, the route is set from the secondary lattice to the tertiary lattices 130 and 132 (step S2). The secondary grid 121 cannot be routed because both outputs to the tertiary grid 132 are already blocked.
In the secondary lattice 121, the path to two of the tertiary lattices 130 and 132 is closed. On the other hand, in the secondary lattice 122, only the path to the tertiary lattice 130 is closed (step S3). Therefore, the route is set using the secondary lattice 122 having the lowest number of tertiary lattices that cannot be connected (step S4). That is, multiple connection is performed in the secondary lattice 122.

On the other hand, if some of the outputs to be connected in step S1 belong to the same cubic lattice, multiple connection is performed in this cubic lattice (step S5). Then, if the route setting is not completed in step S5 (step S6), the process of step S2 is performed.

In the case of multiple connection in a double link switch network having two links for connecting the output of a certain primary lattice to the input of a secondary lattice as described above, 2
When multiple connections are made using the next- and third-order lattices, one-to-many multiple connections can be performed while leaving the switch network as a non-block.

Next, details of the route setting will be described with reference to FIG. As shown in FIG. 3, the output of the cubic lattice in use is n / 2−1.
If the number is equal to or less than this, the number of cubic lattices that cannot be connected from the secondary lattice is set to 0. That is, for this n / 2th input terminal A and output terminal B, a double link is n
Since there is -1 bundle, it is always possible to set the route so that only one of the double links is used depending on the non-blocking condition of the three-stage switch network. The subsequent n / 2 outputs are routed using the n / 2-1 bundle of double links with both links free. In this case, in the worst case relative to the other connections, all outputs could be routed using both of the double links. Then n / 4 bundles of 2
The heavy links will be closed. To summarize the above, even in the worst case, even if all outputs are connected, when viewed from a certain second-order lattice, outputs to 3 / 4r third-order lattices are open.

Considering this worst multiple connection, it is necessary to consider a case where multiple connections are made to all r third-order switches, one at a time for a total of r outputs. As described above, if control is performed so as not to close both links between the secondary lattice and the tertiary lattice, the probability that an output from a certain secondary lattice to a certain third lattice will be 3 / 4 or more. Also, since there are m / 2 secondary lattices, the probability that a route can be set using only secondary and tertiary lattices is (3/4) ^r (m / 2) or more. Therefore, compared with the case of a single link, the probability is (1/2) (3/2) ^r times, which is very large.

Further, consider a case where there is a demand for further connecting the output terminals D and E to the input terminal A after the connection between the input terminal A and the output terminals B and C is completed in FIG. in this case,
By connecting multiple output terminals D with a cubic lattice 130,
Since it can be connected to the input terminal A, the path is actually set. On the other hand, since the output terminal E has no connection between the input terminal A and the cubic lattice 131, the cubic lattice cannot be used for multiple connection. Furthermore, even if an attempt is made to make multiple connections with a secondary lattice, the secondary lattice 12
The outputs from the 2nd to 3rd order lattice 131 cannot be multiplexed because both of them are already in use. If multiple connections are made from the primary switch, the connection can be made, but there is a possibility that the one-to-one connection set later cannot be made. Therefore, the connection request of the output terminal E is rejected.

In this way, of the new connection request and the additional connection request of the output terminal, the one that can be multiple-connected in the second and third stages sets the route, and rejects the connection request that requires the multiple-connection in the first stage. As a result, the switch network can be kept non-blocking in response to a one-to-one connection request. Also, reduce the number of cubic lattices that cannot be connected from the secondary lattice by 1
By performing pair-to-one and one-to-many route setting, it is possible to increase the possibility that the one-to-many connection can be routed using only the multiple connection of the secondary lattice and the tertiary lattice.

Further, when accepting a one-to-many connection reservation, by limiting the number of multiple connections to a certain small number k (r> k), the route can be obtained using only the secondary and tertiary lattices described above. The probability of setting is even higher (3/4) ^k (m / 2) or more.

In the above description, the case where the switch network is non-blocking for one-to-one connection has been described. However, even if the switch network is not non-blocking for one-to-one connection, by using the route setting method of the present invention, A one-to-many connection can be performed without causing a deterioration in the block rate for the one-to-one connection.

Moreover, although the above description has described the three-stage switch network,
The same can be applied to a 2i-1 stage switch network.

〔The invention's effect〕

As described above, according to the present invention, in a switch network that is non-blocking for one-to-one connection, the following one-to-one connection is kept non-blocking, and the number of one-to-many is larger than that of the conventional method. This has the effect of greatly increasing the possibility of connection. Further, even if the switch network is not non-blocking for the one-to-one connection, there is an effect that the one-to-many connection can be performed without deteriorating the block rate for the one-to-one connection.

[Brief description of drawings]

FIG. 1 is a block diagram showing an example of a multi-stage switch network for carrying out the present invention, FIG. 2 is a flow chart for performing route setting in the switch network shown in FIG. 1, and FIG. FIG. 4 is a schematic diagram showing a route setting method according to the invention, FIG. 4 is a block diagram showing an example of a configuration of a switch network according to the conventional technique, and FIG. 5 is a schematic diagram showing a route setting method in the switch network according to the conventional technique. FIG. 6 is a schematic diagram when a route cannot be set in the switch network according to the conventional technique. 110〜112,120〜122,130〜132 …… Lattice switch

Claims (4)

[Claims] 1. In a multiple connection system in a multi-stage switch network in which lattice switches are connected in 2i-1 stages (i is a natural number of 2 or more), links connecting each stage are multiplexed n times (n is a natural number of 2 or more). Link connection, one-to-one connection between input and output,
Also, when performing one-to-many multiple connection, branch connection is performed from the stage closer to the output with a lattice switch, and the j-th stage (i ≦ j ≦ 2i
1) multi-branching connection is performed so that at least one link among the n-fold multiple links from the lattice switch belonging to (1) to each j + 1-th lattice switch can be left unused without being used. When it is not possible to leave at least one link open for all n-fold links from the j-th stage to the j + 1-th stage by selecting the lattice switch at the stage and setting multiple connection paths, Multi-branch connection is performed so that the number of all n links to the lattice switch at the stage is all in use j
A multiple connection method in a multi-stage switch network characterized by selecting a lattice switch at the stage and setting a multiple connection route. 2. A one-to-many new connection and an increase request for the number of connection outputs, there is a vacancy in the output link of the lattice switch from the i-th stage to the 2i-1th stage, and the i-th stage to the 2i-1th stage. Multiple desired outputs can be output only by multiple branch connection in the lattice switch
Accepts a connection request if it can connect to one input, and
There is no vacant output link required for multiple connections in the lattice switches from the 2nd to 1st stages from the 1st stage to the i-stage.
2. The multiple connection method in a multi-stage switch network according to claim 1, wherein a connection request that requires multiple branch connection in the first stage lattice switch is rejected. 3. The multiple connection system in a multistage switch network according to claim 1, wherein the number of multiple connections is limited to a predetermined number and accepted. 4. The multiple connection system in a multistage switch network according to claim 1, 2 or 3, wherein the multistage switch network is non-blocking for one-to-one connection.