JPH04100346A - Multi-stage connection cell transfer circuit - Google Patents

Abstract

PURPOSE:To exchange cells subject to concatenation multiplex by providing a cell queue corresponding to a number of a 3rd switch group to each switch of a 1st switch group applying exchange connection of an input cell. CONSTITUTION:Four F switches 102, four S switches 103 and four T switches 104 applying exchange connection to an input cell are formed to be 3-stage configuration to be expanded to 16X16 switches. A cell transmission arbitration circuit 101 arbitrates a cell transmission number requested from each of the F switches so as not to cause internal conflict and gives a transmission enable signal to each of the F switches. Then a queue of the F switches 102 is managed for each number of the T switches. Thus, large scale cell switches of 3-stage configuration is built up and cells subject to concatenation multiplex are exchanged.

Description

DETAILED DESCRIPTION OF THE INVENTION Industrial Field of Application The present invention 1 relates to ATM cell transfer technology used in broadband 15DN etc., and relates to a cell transfer circuit in which cell switches are connected in multiple stages.Prior art Fig. 23 is an example of the overall diagram of the JiATM switching system communication path system & 2301 is the line interface circuit jL 2
302 is a unit ATM switch, and a line interface circuit LIFii ATM switch is provided for each line.
O/E change a E10 conversion S/P change a P/S conversion
Cell mass sales Header conversion A part that performs traffic monitoring and control, etc. ATM unit ATM switch (SW) f table AT
This is the part that replaces M cells, and the scale can be expanded with a 3-stage configuration.If the unit switch is 32x32,
As shown in Figure 23, 1024X1024 due to the 3-stage configuration
Even if each unit ATM switch 2302+L has a built-in memory buffer so that it can wait for cells going to the same output link, each line interface circuit LIF2301ζ can be expanded to the size of STM.
With the configuration shown in Figure 23, it is possible to input and exchange up to 1024 +LSTM-1 speed signals (155, 52 Mbit/s). By using the speed of C1155, it is possible to transmit high-speed, large-capacity digital signals such as high-speed data and television signals. Therefore, when transmitting a high-definition signal, an STM-4 signal is used to concatenately multiplex four LISTM-1 signals. Since the processing capacity is only 1,000,000,000,000,000,000,000,000,000,000,000,000 (
It must be taken into consideration that four STM-1 signals are concatenated and multiplexed (~ The input/output signal speed of the exchange system in Figure 23 is STM-1
speed (] 55.52 Mbit/s),
Although it is not possible to directly interface with the STM-4 signal, it is necessary to decompose the STM-4 signal (or STM-1 code) before exchanging it. Cancellation signals (S as shown in Figure 24 (b))
44 STM-1 signals separated into 4 signals equivalent to TM-1
Even if the eulogies are exchanged to the same destination and arrive at the same timing (L), if they are output at the same timing as in Figure 24(b), if they are concatenated and multiplexed, the result will be as shown in Figure 24(a).
The STM-4 signal can be restored, and the STM-4 speed signal can be exchanged. Problems to be Solved by the Invention (Problems for Claim 1.2) For example, the first cell switch 4 and the second cell switch Cell switch 4 - 3rd cell switch A complete line group switch with 4 switches configured in 3 stages.For any combination of 16 incoming lines and 16 outgoing lines, there is always a switch combination that does not cause collision. In the case of cell transfer, the outgoing address of a cell input from one incoming line changes every cell unit time. Unless the transit route is rearranged in each cell unit time, internal collisions will occur. When it comes to large-scale switches, it is extremely difficult to rearrange cells every unit time (a) In order to avoid internal collisions, one cell is forced to wait in the buffer of the second cell switch. When one force of concatenation multiplexed cells (
The possibility of cell order reversal occurs when delays occur.Second
Figure 4 (a) shows the cell flow equivalent to STM-4 where cells are transferred in the order of 01 to CIO. Figure 24 (b) shows the ST
The transmission format converted to four cell streams equivalent to M-1 is shown below. Now, if cell C6 among the input cells of 2401 is delayed, the output of 2402 will be 4.
In order to solve the problem of claim 1.2 (!1F problem for claim 3), the signal after concatenation multiplexing will cause cell reversal as shown in Fig. 24(d). It is necessary to detect in advance the cell that causes the collision, and then determine the cell sending order after determining the route that does not cause a conflict.In order to avoid internal collisions, one cell is made to wait at the first cell switch. The throughput of the entire switch decreases just by doing so. Conventionally, there is no route determination method that does not cause internal collisions and increases the throughput. (Issue for claims 4 and 5) I'm looking for a route within the main line network that won't cause this to happen, but I don't have enough throughput yet.
It is necessary to have a standby line network to reduce internal collisions. However, in the past, there was no routing algorithm that effectively utilizes such a backup line network (issues for claims 6 and 7). An algorithm is required to constantly monitor the queue status of the switch and reduce the cell waiting time by preferentially transferring cells from queues with longer waiting times. It is necessary to determine the number of cells.However, conventionally there is no such determination circuit. It is an object of the present invention to provide a multi-stage connection cell transfer circuit and a cell transmission request circuit which solve the above problems. (1) A first cell switch group (hereinafter referred to as aF switch) which exchanges and connects input cells, and a second cell switch (side ratio S) which inputs and exchanges and connects output cells of the F switch group. In a cell transfer circuit, input cells are exchange-connected in a cell transfer circuit composed of a group of switches (referred to as switches) and a third group of switches (referred to as T-switches) which input and exchange-connect the output cells of the S switch group. Each switch in the F switch group has a cell queue corresponding to the number in the T switch group. (2) When multiple cells read from one queue of the F switch are transmitted at the same transmission time, the cell transfer order is For the next cell, select the output line that goes through the switch with the lower number of the S switch (3) Display the unused route between the S switch and the T switch and the reallocation request signal displayed by the unused line display circuit. (4) A fourth switch (hereinafter referred to as &F' switch) to set a detour route for the first cell switch. A fifth switch group (referred to as the 5th cell switch) for setting a detour for the second cell switch is installed. and S
F
Setting a new cell transfer route between the switch S' and the T switch (5) Randomly perform the lil stop operation.

(6) A counting circuit that counts the number of cells in the buffer for each destination, an addition circuit that calculates the total number of cells in the buffer, a division circuit that divides each counted value by the added value, and a total number of sending requests for each destination. It also includes a conversion circuit that divides the ratio of the number of cells, and an addition circuit and a comparison circuit that control the sum of the outputs of each conversion circuit to be the total number of transmission requests. (7) Calculate the number of cells in the buffer for each destination. A counting circuit that counts, a shift circuit that outputs a value obtained by bit-shifting the output of each counting circuit, an addition circuit that adds the numbers output by the shift circuit across all destinations, and a comparison that controls the shift amount of the shift circuit. The present invention is capable of exchanging concatenated multiplexed cells by using a cell queue management method and associating the S switch number with the cell transfer order. By setting more transfer routes that can be transferred at a given time, the throughput of the switch can be increased. By performing g stops randomly, it is also possible to avoid situations where a specific cell transfer route becomes congested (6). (7) Using the above configuration, calculate the ratio of the number of cells in the buffer for each destination to the total number of cells in the buffer. Divide the total number of transmission requests by the calculated ratio and calculate the number of requests for each buffer. Example An embodiment of the invention relating to claims 1 and 2 will be explained with reference to Fig. 2. The switch shown in Fig. 1 has 16 4x4 unit switches.
Even if it is expanded to X16 switch, it will be as shown in Figure 114
Four F switches 102 (i=1 to 4), four S switches 103 (j=1 to 4), and four T switches 104 (k=1 to 4) are configured in three stages to form a 16×16 switch. Expand to. 101 is a cell sending arbitration circuit;
The number of cells requested by each F-switch is arbitrated to avoid internal collisions, and transmission permission is given to each F-switch. Cells for which transmission permission is not granted are forced to wait at the F-switch. In this case, internal collisions occur. Since there is no waiting time at the S switch, there is no waiting time at the S switch.If the cells being transmitted in the order of (1) and (2) on the transmission line are input from the input port X shown in Figure 1, then the cell transfer line Dea.

When passing through the route b, the cell (1) passes through a, and the cell (2) passes through b. Immediately, the S switch with j = 1 passes through the cell (1). The S switch with Lj = 2 passes through ( 2) Cells pass through Figure 2 shows a block diagram of the F switch. 2
51 to 254 are incoming lines, and the 53-octet cell is horizontally converted so that the inside of the switch can read and write cells in one clock. 4261 to 264 are outgoing lines.
Input cells from the incoming line are accumulated in queue buffers 201 to 204 in one clock cycle.The queue buffer 201 receives cells that go to 1, and the queue buffer 202 receives cells that go to 2. The queue buffer of 203 is input with the cell going to =3, and the queue buffer of 204 is input with the cell going to =4.
Although the F switch queue is managed for each T switch number, the timing circuit 203 is a cell cycle counter.
Even though the timing of writing incoming cells to the queue and the timing of reading them from the queue are controlled, 210 is a register for temporarily storing cells read from the queue, and cells can be read and written in one clock.221-2
24 is an output circuit which, when a load signal is input from the memory control circuit 240, takes in the output of the register 210 in one clock.

The fetched cells are vertically and horizontally converted and output at 53 clocks.The timing circuit 230 gives timing signals to each lock.
At each j number, the value of the cell's queue number (k number) is determined by the cell arbitration circuit.
It is also sent through the cell transmission permission signal 250.
The memory control circuit determines cells to be sent out for each number and notifies the body sending arbitration circuit through the cell sending request signal line 260. An embodiment of the invention related to claim 3.4 is shown in FIG.

This is an example of expanding a 4X4 switch to a 16X16 switch. 301 is a 4x4 unit switch that exchanges 155 Mbit/s input cells, and even though 4 units constitute an F switch group, 303 is an S switch,
Even though 304 constitutes a T switch, 302 is an F switch, and 304 is an S switch.

A switch 306 is a cell transmission arbitration circuit that determines a transfer route to prevent internal cell collisions. Although the transfer route determination operation will be explained in detail later, FIG. 4 shows a network configuration diagram using a main line network and a protection line network. Using this diagram, explain that it is necessary to have a backup line only between FS.A 4T switch has four incoming and outgoing lines. Also, the maximum processing capacity of T-switch is 4x (155M
itb/s). Therefore, by creating a backup line between the S switch and the T switch, 4X (155Mb i
Even if more cells than t/p) are input, it cannot be processed ~ The reason why the throughput decreases: The route between the LSTs cannot be used effectively, and a collision occurs in the S switch.
This is because there are still vacant routes between STs. In this example, the routes between STs are used more effectively by adding a backup line network between the 4 FS in addition to the 1-tomo main line network. Now, if there is a request to use the thick line part on the main network, (l.

Using the route j)=(1,2), we get (J.

A cell collision occurs at k)-(2,1). Even in this state, the route (j, k) = (3, 1) is not used, and if there is only a main network, this cell transfer time
(j, k) - (3, 1) is not used (t In this example, we use the backup route of (j, k') = (3,]), and (j, k) = (3, 1). ) routes are effectively utilized.

So, let's explain the cell transmission arbitration circuit 306 shown in Figure 3.Before explaining the specific circuit, we will specifically explain the collision route detection method and the unused line reallocation algorithm. Next, we will explain the unused line reallocation operation when the line is not used. Next, we will explain the unused line reallocation operation using a backup line. Figure 5 shows the cell transmission request table. Figure 6 shows the reallocation request. Show table.

FIG. 7 shows an unused line management table. Figure 7 shows the main line usage management table. Therefore, the unused line reassignment algorithm will be explained using Figures 5 to 7. The numbers i, j, and k are
Even though they correspond to the switch numbers shown in the figure, the numbers in the frame of the table represent the number of cell transmission requests. = 1) indicates that the requested number of cells is 2 cells.At this time, the J number shown in box 8 in Figure 5 is used as the route given to the cell transferred from the F switch to the T switch. For example, in the diagonal line (i,
Even if j, k) - (+, 1. If you do this, there will be no internal conflict, and S
There is no delay at the switch (L%), but if this continues, the throughput will be low.

In this effort, we perform the following unused line reallocation algorithm.

(1> The number of cell transmission requests is determined by each F switch.

(2) Even if the number of cell transmission requests is registered in the cell arbitration circuit from each F switch (Fig. 5) (3) A main line reallocation request table (Fig. 6) is created from the cell transmission request table. Even if the number of cell transmission requests going from the corresponding F switch numbered 1 to the T switch numbered 1 is two or more cells, and this means that an internal collision will occur if this continues, (4) From the cell transmission request table Create an unused line management table (Figure 7). This figure is
This indicates that the route between the numbered F switch and the numbered T switch is unused.

(5) The arbitration circuit creates a main line usage management table (FIG. 8) from the cell transmission request table. Even if the route between the corresponding F switch numbered 1 and the S switch numbered J indicates that the F switch is used by the cell k goes to (6) the arbitration circuit (from k=1 to Start arbitration & search for unused line between S switch and T switch (k = 1) (Example: (j, k) = (2, 1)) (7) Next k =
Search for the F switch number requesting unused line reassignment to 1 & (i =]) (8) Wire (j, k) = (2゜]) to the F switch of (i = 1) Assign temporarily.

(9) F switch i of 6 (i=1) that was able to check whether the inter-FS route temporarily allocated from the main line usage management table (Fig. 8) can be used: (i.

If permission is given to use the main line j, k) = (1, 2, 1), but at the same time, (k = 1) is registered in the main line usage management table (in this example, it is 1) (i, j) = (L2) has already been allocated and will not be re-allocated l-'Yo) (10
) Return to (6) and continue the arbitration work until k=4.

(11) After the mediation work is completed (Uri main line use table (
Permission to use the main line will be granted to the F switch group based on Figure 8).

Example of reassigned route; For i=2, (i, j, k) = (2, 3, 2) For i=4, (b Jr k) - (4, 3, 4) Main line FIG. 9 shows the cell transmission request table after performing the unused line reallocation operation, FIG. 10 shows the reallocation request table, and FIG. 11 shows the unused line management table. Comparing FIG. 5 with FIG. 9, it can be seen that in this embodiment, two cells are newly transferable (after reallocating unused lines using the main line network, Raku: Use the backup line network to reallocate unused lines and search for usable ST-to-ST routes.

FIG. 12 shows the backup line management table. The unused line reallocation operation using the backup line is as follows. (2) Even if the reallocation request table looks like the one shown in Figure 10 (3) Even if the unused line management table looks like the one shown in Figure 11 (4) The new ＼ Reserve line usage management table looks like the one shown in Figure 12 (5) Start arbitration from k=1 Search for unused line between S switch and T switch (k=i) (Example: (j',
k) = (2, 1)) (6) Search for the F switch number requesting unused line reallocation to k = 1% (i = 1) (7) (i
'=1) F° switch (j', k)=(2,1
), it was possible to check whether the temporarily allocated inter-FS route could be used from the main line usage management table (8).
' = 1) F switch (i', jk) = (1,
2. Grant permission to use the main line in 1) and at the same time register (k = 1) in the main line usage management table (9) Return to (5) and perform all arbitration work until k = 4.

(10) After the mediation work is completed, the main line use table No. 1
An example of a route that was reassigned even though the F switch group was granted permission to use the main line based on Figure 2: For i = 2, (i', j', k) = (1, 2, 1) for i = 4. For (i', j', k) = (2, 4, 2) Route 4Q determined by the unused line reallocation algorithm explained above. The force explained as starting mediation from =1 (bias in mediation (towards cells going to k = 1) =
The order of arbitration for 6k is randomized to eliminate unused lines (easier to allocate than cells going to cell 4).Next, we will explain the guarantee of cell order. When expanding to a switch, if the arbitration order is set to 10 m (mod 33), unused lines can be allocated randomly. However, m is an integer that is coprime to 32 (for example, 3, 5, 7...) Cells sent from the F switch and the F° switch to the T switch with the same number use the S switch with the smaller j number for cells that are earlier in the cell order. is being transferred and the Lj number (1~) is being transferred.
It is defined that the route passing through the S switch is faster in transfer time.For T switch input, cells coming from the S switch with the smaller j number are processed first.This order is the same when using a backup line. Deam Example 1ij=3, andj
When o = 2, the cells of the jo = 2 route are processed first. Figure 13 (a) This is the format for transmitting the cell transmission request number arbitration circuit determined by the ζiF switch. number of requests per destination (k), and
The total number of transmission requests in one frame of each F switch is 4 cells or less. Figure 13 (b) shows the transmission format when reporting the arbitration result to each F switch. For example, 1 = 1
One friend with the signal to the frame synchronization signal (i, j)
= (1, 1) The destination number of the cell that is allowed to use the main line (i, j) = (1, 2) The destination number of the cell that is allowed to use the main line... After that, the number (i'
, j) = (1', 2) The cell arbitration circuit 306 shown in the embodiment shown in FIG. Although the specific operation of the circuit will be explained, Figure 14 shows the block configuration of the cell transmission arbitration circuit. In the figure, 140
1 is the same area where the number of cell transmission requests is registered 1402 is unused line allocation time i 1403 is allocation line registration time 1i 1404, 1
405 is an OR gate m 1406 is a timing circuit a A specific circuit of the request number registration circuit 1401 is shown in FIG.

15th FI! J(a) is the same as in FIG. FIG. 15(b) shows four counters 1510, 1520, 15 that record the number of cell transmission requests issued from the F switch with i=1.
15 (C ) is a specific circuit of the register 1510, and 151
1 is a callan with a load terminal. 1512 and 1513 are logical sum circuits. If the content of the counter 1511 is 0'', the output 1514 (unused line display signal) of the logical sum 1512 becomes "H" (j, k ) = Indicates that (1, 1) is an unused line.The contents of the counter 1511 are ``
If it is 2″ or more, the a force of logical sum 1513 is 1515
(Reallocation request signal) becomes °H'', (i, k) =
Indicates that there is a cell at (1, 1) that transmits a cell. When the unused line is reallocated to the cell (i, k) = (1, 1), the counter 1511 decrements by "1" and the unused line allocation circuit 402 shown in FIG. A specific circuit is shown in FIG. Although FIG. 16(a) is the same as FIG. 5, FIG. 16(b) L (i.

This is the circuit that allocates the unused line of k) = (2, 1) to the cell going from 1 = 1 to = 1. 1611 is the circuit that allocates the unused line of k) = (2, 1) to the cell going from 1 = 1 to = 1. % 1612 is the input line of the unused line display signal of (j, k) = (2, 1), which is "H".4 This signal is the 15th line.
This corresponds to the 1514 signal in the figure. 1630, 1640
, 1650 is an AND circuit. 1621 is the input line for the reallocation request signal from i=3 to =1 1622 is the input line for i=4
Input 11.1623 of the reallocation request signal from l=1 to 1 is the input line of the reallocation request signal from l=1 to 1.
In this example, even if only the reallocation request signal of i=1 is "H", 1651 is the double registration prevention signal of (i, j) = (1, 2), and when this signal is "H", the logical product is The output 1652 of 1650 becomes "H", and (i, j) = (1, 2
) is permitted (reassignment), this permission signal is the first
input to the EN terminal of the counter 1510 shown in Figure 5.
When the counter value is decremented, it is also registered in the (bj) = (1, 2) register of the assigned line registration circuit (in this example, the (i, j) = (1, 2) line has already been used). The double registration signal is “L”,
1652 remains 'L'.)Next, the unused line allocation timing will be explained with reference to Figure 17.Cell transmission requests from each F switch are sent in numerical order at 4 clocks.k= The number of cell transmission requests of 4 is registered.
Starting from the next clock when the main line usage management table is created, sequentially (1-Jlk) = (1, I, I), (2, 2, 1
), (3°3.1), and (4,4,1). Therefore, if the mediation of the shaded area is completed as shown in Figure 17, the mediation of the shaded area will be performed at the next clock, but the time required for the entire mediation will be 7 clocks. Arbitration is performed in one clock (the pairs of i, j> are always different, so if we have 11 arbitration circuits for each (i, j), we can perform arbitration at high speed through pipeline processing. Lastly, the allocation line registration circuit 1403 shown in FIG. 14 will be explained in conjunction with FIG.
゜2.4-5) is the same as Figure 18(b) is 1=2
The assignment for is the line registration circuit.(++j)=(2
, 3) is shown in Figure 18(c).
We will explain how to register (i, j, k) = (1, 2, 1) using the registration circuit shown in Figure 19 (c).
Reset R8/FF1801 at the first clock that performs arbitration operation. Set L4 counter 1802 to "2." The numbers in the table shown in Figure 18(d) indicate the number of J, and the reassignment Accordingly, (i, j)=(2,3
) are indicated with diagonal lines. Comparing Figure 17 and Figure 18 (d), we find that
(l.

j, k) = (2, 3, 2) The timing at which the assignment is made is the "4th" timing.The initial value of the counter is set to 2''.The value of the counter at the time of assignment is Even though 2+4=2 (mod 5), if (i, j) = (1゜2) is assigned and R8-FF is set at the same time and the counter is held, the k number "2" will be registered in the counter 1802. This number is sent to F switch 12.
(i, j, k) = (2, 3, 2) The R5-FF output 1803c sends cells using the route. Even though the unused line allocation is fed back to the circuit as a double registration prevention signal, the main line is The unused line reallocation circuit 1401 and the unused line allocation circuit 14 in FIG.
02 uses the exact same circuit. Assignment line registration circuit 1403
Even if there is a backup line usage management table that is different from the main line usage management table, is the reallocation of backup lines the same as reallocation using the main line network? An embodiment of the invention related to item 6 will be described. A configuration diagram of a cell transmission request circuit in this embodiment is shown in FIG. 19. Figure 20 is an example of a conversion table used in the conversion circuit in Figure 19.This is a circuit that selects 4 cells from the cells stored in multiple buffers and requests the cells to be sent. If the total number of cells in is less than 4,
In Fig. 19, 1901 requests all transmissions.
is the number of cells counted in the queue j
l 1902 is the division time j & 1903 is the conversion time jL 1904 which converts the input numerical value using the conversion table
is a selection circuit 19051 that selects and outputs the smaller input from two inputs.A division circuit 1902 and a conversion circuit 190.
3 and a selection circuit 1904.
Ma? , = 1910 and 1920 are addition times gl that calculate the sum of input numerical values 1921 is a comparison circuit and a cell number counting circuit 1901 il Counts the number of cells accumulated in the corresponding queue a In other words, Matsu Number of cells that have arrived Addition circuit 1910i that adds up and subtracts the number of sent cells Four cell number counting circuits 1901
Then, the output value 1912 of the corresponding cell number counting circuit and the output value 1911 of the adder circuit 1910 are input.
Then, the division circuit (table 1912 of the output value of the cell number counting circuit is added to the addition circuit 19) and the addition value 1911 of 0
Divide by and output the result sumo conversion circuit 1903 L
The calculation result of the division circuit is input, and the input value is converted and output using the conversion table shown in Fig. 20. Also, the comparison circuit 19
The output value of the conversion circuit is increased or decreased according to the instructions of the output signal of the comparison circuit 1921.
When the receiver receives a positive signal, it adds 1 to the output value.
When a negative signal is received, 1 is subtracted from the output value. However, the minimum value of the output value of the conversion circuit 1903 is O, and the output value 1912 of the corresponding cell number counting circuit and the - conversion circuit] 903 output is input.Then, the smaller value of both inputs is selected and output.If the output value of the adder circuit 1910 is 4 or less,
Selection circuit 1904 g:! , an adder circuit 19201 that selects the output value 1912 of the cell number counting circuit, an adder circuit that inputs the output values of the four selection circuits 1904, a comparator circuit 19211L that outputs the addition result, and an output of the adder circuit 1920. The added value is compared with 4, and if the added value exceeds 4, a negative signal is output, and if the added value is less than 4, a positive signal is output.It is possible to output a negative signal and a positive signal to each conversion circuit independently. If the added value exceeds 4, output a number of negative signals equal to the number exceeding 4 to a random destination (conversion circuit).If the added value is less than 4 (
By this control, adder circuit 1 outputs a number of plus signals equal to the number missing from Table 4 to a random destination.
If the added value of 920 is 4, that is, if the number of cells requested to be sent out from the board is 4, then the added value becomes 4 ('L) A signal (Valid) indicating that the numerical value output from the selection circuit 1904 is valid.
However, if the output of the adder circuit 1910 is 4 or less, if the total number of accumulated cells is less than 4, the signal (minus signal plus signal) will not be output. Assuming the maximum number of cells is 4, it is possible to request the sending of a number of cells approximately proportional to the number of cells in the queue. As a method of increasing or decreasing the output value of the circuit 1903, the conversion circuit output is directly increased or decreased by using a positive signal (or a negative signal).In contrast, the following method is used to increase or decrease the conversion circuit output. L The operation of the sending request circuit is the same, and the output of the comparison circuit 1921 is a positive signal and a negative signal (Table 6) Instead of being output to a random destination, the signal strength is negative when it exceeds 4 (when it is less than 4) When the plus signal and the minus signal are output, the plus signal and the minus signal are connected to each circuit block 1905. For example, when a positive signal is input, the threshold value is decreased and a large value is output. With this control,
The output of adder circuit 1920 becomes 4.

An embodiment of the invention relating to claim 7 of the present invention will be described with reference to FIG. 21. A configuration diagram showing the configuration of a cell sending request circuit in an embodiment of the invention relating to claim 7 of the present invention.
Figure 21 is an explanatory diagram of the operation of the shift circuit in Figure 21. In Figure 21, 2101 indicates the number of cells accumulated in the queue. 2102 indicates the number of cells in the queue. Addition 1i to calculate the sum of numbers
2111 is a comparison circuit and a mucell number counting circuit 2101ζ
yo Count the number of cells accumulated in the corresponding queue.
Shift circuit 21024 that adds the number of cells that have arrived and subtracts the number of cells that have been sent out. A function that outputs a value that is bit-shifted from the output value of the cell number counting circuit, and a function that subtracts 1 from the bit-shifted value. and has. Figure 22 is an explanatory diagram showing the operation of α bit shift when the human input value is 4 bits.As shown in Figure 22, the shift circuit output (Q
3~QO)It As the number of shifts increases,
The shift circuit input values (D3 to Do) are shifted. Shifted n times output (value obtained by dividing the power value by 2 to the power of (4-n) For example, let's explain the case where the input value is 6 (-[0, 1, 1, 0]).The output of one shift is 0 (=[0,
0, 0, 0]), and the two-shift output is 1 (=[0,
0, 0, 1]), and the output of 3 shifts is 3 (=
[0, 0, 1, 1).

In this example, when a negative signal is received from the comparator circuit 2111, the output of the shift circuit becomes 2 (=3-1).The output values of the adder circuit 21101 and the four shift circuits 2102 are input. Sum Added value is output to comparison circuit 2111 Sum comparison circuit 2111 +1
Compare the added value output from the adder circuit 2110 with 4. If the added value is smaller than 4, shift the signal to 4.
The shift signal is output to two shift circuits 2102 until the added value becomes 4 or more.However, the shift signal can only be sent a maximum of 4 times.When the added value exceeds 4:
Dai: It works as follows: Calculate numbers over 4,
A program that randomly outputs negative signals for that number of signals.
The shift circuit 2102 that receives the minus signal performs a minus 1 operation, so that the added value of the shift circuit output becomes 4. When the output value of one shift circuit exceeds 4, it outputs a negative signal so that the output value of 1 becomes 4 and the output values of the other three shift circuits become 0.

A module that outputs a signal (Valid in Figure 21) indicating that the value indicated by each sending request number is valid when the added value is 4 and when the added number becomes 4 due to a negative signal. In addition, even if the shift circuit operates up to 4 times, if the added value is less than 4, the L signal will be output. According to the present invention, it is possible to request the transmission of a number of cells approximately proportional to the number of cells in the queue. Nation multiplexed cells can be exchanged.1.
Unused line reassignment algorithm makes it possible to configure cell transfer circuits with high throughput.

[Brief explanation of the drawing]

Figure 1 shows the configuration of an embodiment of the invention according to claim 1 @2
The figure is a block diagram of an embodiment of the invention according to claim 2. Figure 3 is an explanation of a backup line network. Figures 4 to 12 are illustrations of an unused line reallocation algorithm according to the present invention. Figure 13 is an F switch. To show the transmission format between the arbitration circuit and the
4 is a configuration diagram of an embodiment of the invention according to claims 3, 4, and 5. FIGS. 15 to 18 are detailed configurations of each part of FIG. 14, and FIG. 19 is a cell sending request circuit according to the invention according to claim 6. Configuration @ Figure 20 shows an example of a conversion table used in the conversion circuit in Figure 19 @ Figure 21 is a configuration diagram of the cell sending request circuit in claim 7 Figure 22 is the operation of the shift circuit in Figure 21 The explanation is as follows: Fig. 23 is an explanatory diagram of the entire conventional ATM switching system communication path system & Fig. 24 is an explanatory diagram of the exchange of concatenation multiplexed signals.
...S switch, 104, 305...T switch,
302...F' switch, 304...S' switch, 201-204...Queue 240 corresponding to T switch number...Memory control circuit (management circuit for output line and queue number), 1401 ... Cell sending request registration circuit 1512 ... Unused line surface water outlet [1512 Reallocation request [1k 1403 ... Allocation leading edge 11k10
1, 306...Cell arbitration time i 1901...Cell number counting circuit 1902...Division time 1i1903...Conversion same section 1904...Selection time jl1905...Circuit block 1910...Addition Time j3 1920...Addition time 1i@, 1921...Comparison time 1i1 210
1...Cell number counting circuit 2102...Shift time li
d 2110...Addition time 13 2111...Comparison time i 2301...Line interface opening 2
302...Unit ATM switch. Name of agent: Patent attorney Shigetaka Awano and 1 other person1” (F
irst) switch S (Secondl switch + T (Thirdl switch Figure 3 240: Memory control circuit Figure 2 = 1 to = 2 to = 3 to = 4 to = 1 to = 2 to = 3 to = 4 to = 1 = 2 = 3 = 4 = 1 = 2 = 3 = 4 Figure 10 = 1 = 2 = 3 = 4 Figure 7 (Reassignment) k = 1 = 2 =3 to =4 Fig. 11 Fig. 12 Fig. 13 F; Frame synchronization pattern (a) Fig. 15 (b) (d) Numbers in the frame of Fig. 17 indicate the order of arbitration timing Fig. 20 Input values Shift circuit input (MSB) l D. (LSB) Shift circuit output (MSB) (LSB) Shift 1 Shift 2 Shift 3 Shift 4
sν1tch 2301+ 2302+ Line interface circuit unit ATM switch Figure 24

Claims (1)

[Scope of Claims] 2. Scope of Claims (1) A first cell switch group that exchanges and connects input cells, and a second cell that inputs and exchanges and connects output cells of the first cell switch group. In a cell transfer circuit composed of a switch group and a third cell switch group that inputs and exchanges the output cells of the second cell switch group, each switch of the first cell switch group A multi-stage connection cell transfer circuit comprising a cell queue corresponding to a number of the existing third cell switch group. (2) a first cell switch group that exchanges and connects input cells; a second cell switch group that inputs and exchanges the output cells of the first cell switch group; In a cell transfer circuit composed of a third cell switch group that inputs and exchanges output cells, the second cell switch group is given a number, and one queue of the first cell switch is assigned a number. When transmitting a plurality of cells read out at the same transmission time, the cell whose transfer order is earlier in the plurality of cells is equipped with a circuit for selecting an output line to be routed through a switch with a lower number of the second cell switch. A multistage connection cell transfer circuit characterized by: (3) a first cell switch group that exchanges and connects input cells; a second cell switch group that inputs and exchanges the output cells of the first cell switch group; In a cell transfer circuit composed of a third cell switch group that inputs and exchanges output cells, the number of cell transmission requests to be transferred from the first cell switch group to the third cell switch is determined. a circuit for registering the number of cell transmission requests to be registered; and an unused line display circuit for displaying an unused route between the second cell switch and the third cell switch using the number registered in the circuit for registering the number of cell transmission requests; , using the registered number of the cell transmission request number registration circuit, the first cell switch number and the third cell switch number for which two or more cells are to be transferred from the first cell switch to the third cell switch. a reassignment request circuit that displays the combination;
The unused route between the second cell switch and the third cell switch displayed by the unused line display circuit and the reallocation request signal are combined to connect the first cell switch and the second cell switch. an unused line reassignment circuit that sets a new cell transfer route between the first cell switch and the second cell switch that has already been assigned;
1. A multi-stage connection cell transfer circuit comprising a cell arbitration circuit comprising an allocation line registration circuit for managing routes between cell switches. (4) a first cell switch group that exchanges and connects input cells; a second cell switch group that inputs and exchanges the output cells of the first cell switch group; In a cell transfer circuit comprising a third cell switch group that inputs and exchanges output cells, a fourth cell switch group for setting a detour for the first cell switch;
register a switch group, a fifth switch group for setting a detour to the second cell switch, and the number of cell transmission requests to be transferred from the first cell switch group to the third cell switch. an unused line display circuit that displays an unused route between the second cell switch and the third cell switch using the number registered in the cell transmission request number registration circuit; A combination of a first cell switch number and a third cell switch for which two or more cells are to be transferred from the first cell switch to the third cell switch is determined using the number registered in the cell transmission request number registration circuit. A fourth cell switch is generated by combining the reallocation request circuit to display, the unused route between the second cell switch and the third cell switch displayed by the unused line display circuit, and the reallocation request signal. and an unused line reallocation circuit that sets a new cell transfer route between the fifth cell switch and the third cell switch, and an unused line reallocation circuit that sets a new cell transfer route between the fourth cell switch and the fifth cell switch that have already been allocated. A multi-stage connection cell transfer circuit comprising a cell arbitration circuit comprising an allocation line registration circuit for managing routes. (5) The arbitration operation order of the unused line reassignment circuit is to allocate unused lines for each number in the order of adding an integer that is coprime to N, taking the total number of third cell switches N (N is an integer) as a side. Paragraph 1 of the patent claim is characterized in that the process is performed randomly;
The multistage connection cell transfer circuit according to item 2, 3, or 4. (6) A circuit that counts the number of cells in a buffer for each destination, an addition circuit that adds the number of cells in a buffer for each destination across all destinations, and a circuit that counts the number of cells in a buffer for each destination. It is comprised of a division circuit for each destination that divides by the addition result, and a conversion circuit that has a conversion table that converts the division result so that the sum of the table output values becomes a predetermined number (M), and is less than or equal to a predetermined number (M), a request to send all cells in the buffer is output, and a predetermined number (M)
A cell transmission request circuit characterized in that, when the cell transmission request number exceeds , the value indicated by the conversion circuit proportional to the division result is set as the transmission request number. (7) A counting circuit that counts the number of cells in a buffer for each destination for each destination; a shift circuit for each destination that receives input from the most significant bit of each counting circuit output and outputs a bit-shifted value; and a shift circuit for each destination that outputs a bit-shifted value. It consists of an addition circuit that adds the numbers output by the circuit to all destinations and outputs an added value (LL), and a comparison circuit that compares the added value (LL) with a predetermined number (M). All destination-specific shift circuits simultaneously shift bits until the value (LL) exceeds a predetermined number (M), and if the added value (LL) exceeds the predetermined number (M), the addition result (LL) The output value of each shift circuit is randomly subtracted until M becomes equal to a predetermined number (M), and the output value of the shift circuit at that time is set as the number of requests to be sent. Even if the bits are shifted to the same value as the output of each counting circuit, the added value will not be the same. A cell sending request circuit characterized in that when (LL) does not reach a predetermined number (M), the output of each counting circuit is set as the sending request number.