JP2546526B2 - Exchange system - Google Patents

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION The present invention relates to threshold-based load balancing in ATM switches with parallel switchplane related applications.

[0002]

2. Description of the Related Art With the development of high-speed VLSI circuits and optical transmission, broadband ISDN (B-ISD)
It is becoming possible to realize a broadband communication system such as N). With regard to multiplexing and switching, Asynchronous Transfer Mode (ATM) is becoming the basic technology for supporting a wide range of B-ISDN services. ATM exchanges using fixed length cells (short packets) and asynchronous multiplexing are very suitable for the transfer of digital information signals of all kinds. The cell length is 53 octets (424 bits).

ATM switches are ATM (ATM Output Buf
fer Modular) switch element. The ATOM switch element is an output buffer architecture. The ATOM switch element includes a time division multiplexed bus and one first-in first-out (FI
FO) buffer is used. This switch architecture is called an output buffer architecture because it has a buffer function on the outgoing line side.

Regarding the ATOM switch element, 1989
IEEE Communication Society "IEEE" held June 11-14, 2014
H. Su recorded in Minutes pp.99-103 of "International Communication Conference"
zuki, H. Nagano, T. Suzuki, T. Takeuchi and S.
Iwasaki co-authored paper Output buffer Switch Archite
cture for Asynchronous Transfer Mode ".

It is expected that ultra high-speed systems required in the future will need to use a switch architecture that employs a large number of ATOM switch elements of this kind in parallel and that corresponds to a transmission rate of gigabit per second level. Many distributors in such a system,
It also requires multiple switch planes and multiple resequencers.

However, load imbalance is likely to occur in such systems with multiple parallel switch planes. That is, the output buffer often has to store a large number of cells and the output buffer often has to store a small number of cells. This results in a large number of cell losses. Therefore, in order to keep the cell loss low when the traffic peaks on a specific switch plane, the output buffer capacity must be increased considerably, which is a capacity that is rarely needed. To improve system performance, it is desirable to provide a device for load balancing to minimize the total buffer capacity that the switch must have.

It is an object of the present invention to realize a more even load distribution to all switch planes of a switch in order to keep the total cell loss number below an allowable level.

[0008]

To this end, the present invention relates to a switching system using a number of parallel switch planes, each of which comprises an ATOM switch element with an output buffer architecture or its equivalent. It is a thing. With a large number of distributors,
Periodically assign input signals to the switch plane. Multiple resequencers are required to allow the exchange signals to be collected from the output buffer and transmitted to their destination.

Each of the output buffers of the switch plane has a number of cells currently stored in the buffer exceeding a specified threshold which is a large fraction of the buffer capacity, or
It is considered to be in one of two states, a light load state and a heavy load state, depending on whether it falls below the lower limit. Each distributor in the system has a load matrix whose elements take one of two values, 0 and 1, to tell the state of a particular output buffer in the system. It is desirable that the value 0 represents a light load state and the value 1 represents a heavy load state. The matrix elements are set by the switch plane and read by the distributor.

The bit representing the state of each output buffer is fed back to the load matrix of each distributor. Advantageously, this feedback is provided only when the state of the output buffer changes.

When the output buffer becomes heavily loaded, the distributor acts to change the path of new cells from a switch plane having such a heavily loaded output buffer to a switch plane having a lightly loaded output buffer. This load balancing is conveniently implemented as follows. Each distributor has two finite buffers. Conveniently, each size is one cell. One of the two buffers is used for receiving new cells and the other is used for load balancing. Whether new cells are sent to the switch plane or stored in another buffer for load balancing purposes is determined by the appropriate algorithm implemented by the appropriate circuitry.

In many cases, cells that have been held for some time for load balancing purposes are sent to the light load output buffer switch plane that corresponds to the desired destination. The number of cell losses in the switch is thus reduced by this load balancing scheme.

[0013]

FIG. 1 shows an ATO of the type used in the present invention.
The basic structure of the M switch element 10 is shown. This switch element has N input lines 11 and N output lines 16. The speed of each input line and output line is V bits / second. In the operation of switch elements, it is assumed that time is divided into equal time intervals called time slots. Exactly one cell is transmitted from one input line to the ATOM switch element during one time slot. Since one cell can be transmitted to each switch element using N input lines during one time slot, the switch element can receive a maximum of N cells during one time slot.

In typical operation, some input lines remain idle throughout the timeslot. That is, no cells are transmitted from those input lines to the switch element during that time slot. Therefore, the total number of cells that the switch element receives from all the input lines in one time slot is 0 to N.

Each cell is routed to the output line by the exchange according to the destination information in the cell. For this purpose, each input cell is first sent to a series-to-parallel converter 12 for converting the serial pulse train of each cell into a parallel pulse train for the time-division bus 13. When the time division bus has L parallel lines, the speed is NV / L. This allows N cells to be transmitted over the bus in one time slot. The time division bus sends the pulse via the address filter 17 to the output buffer corresponding to the destination information in the cell. Since there may be a plurality of cells destined to the same output line in one time slot, it is often the case that the pulse cannot be immediately transmitted. In that case, the pulses are first stored in the output buffer 14, which is generally a FIFO storage device. Upon leaving the output buffer, the pulses are reconverted into a serial pulse train for transmission by a parallel to series converter 15 connected to separate output lines 16.

In the ultra high speed network, the input line 11 and the output buffer 1
It is necessary to perform the cell transfer between 4 and 4 at a very high speed. By using a serial to parallel conversion scheme, the required bus speed is basically reduced by the degree of parallelism. However, this imposes a limit on the input linear velocity that can be achieved with this type of switch, since the degree of parallelism that can be used in practice is limited by the length of each cell. In order to overcome this limitation, an ATM consisting of a number of ATOM switch planes, a distributor for distributing cells to those switch planes and a resequencer for collecting the exchanged cells for further transmission to a designated destination. A switch architecture was devised.

FIG. 2 shows the overall basic structure of the ATM switch 20. This structure is based on the paper Parallel ATOM Switch included in the proceedings pp.250-254 of the IEEE Communication Society / IEEE International Communication Conference (June 1992, Chicago, Illinois).
Architecture for High Speed ATM Networks "for details. This ATM switch is composed of S ATOM switch planes operating in parallel.

The exchange 20 basically comprises N input lines 21 through which the train of cells to be transferred by this exchange is supplied. Each input line 21 is connected to a separate distributor 22. Further, S parallel ATOM switch planes 23 are provided. Each of these is composed of the ATOM switch element shown in FIG. Each distributor 22
On the other hand, the cell is demultiplexed on each switch plane 23. Next, the cells are transferred to the output buffers 26 provided in the respective switch planes independent of each other and corresponding to the respective destinations. The resequencer 24 outputs from the output buffer 26 to the output line 2 for the purpose of maintaining the cell sequence.
Control cell transfer to cell 5.

In this type of exchange, it is convenient to consider that each distributor operates in cycles of the length of S time units. Number the cycles 1, 2, 3 ... If cycle k starts at time x, then the distributor corresponding to input j (1 ≦ j ≦ N) is time x + i−1 (1 ≦ i ≦ S) and (input j
Cell will be sent to switch plane i). Switch plane i does not receive cells from the distributor at any other time during cycle k. The cells are distributed as soon as they arrive at the input. Thus, cells are distributed by each distributor on an FCFS (first-come-first-served basis) regardless of destination. The switch plane is scheduled to receive cells in a circular round robin fashion. Whether the switch plane actually receives cells in a round robin manner depends on the supply status of the cells to be distributed. If there is a new cell in any time slot, the switch plane will receive the cell in a round-robin fashion. However, in reality, there may be no new cell depending on the time slot. For this reason, the switch plane does not strictly receive cells in a round-robin fashion. So we say that the switch plane receives cells in a quasi-round robin (QRR) manner. Therefore, different output buffers corresponding to arbitrary output lines do not have to accommodate data at the same speed, and the output buffers cause a difference in load.

The output buffers of the switch plane receive cells at a time interval of length S time units (assuming there are cells to receive). The cell arrival process at the switch plane output buffer can be described as follows. Arrivals occur in the order of 1, 2, 3 ... Numbered cycles. The length of each cycle is S
It is a time unit. If cycle k starts at time x, the cell arrives at the output buffer of switch plane i at time x + i-1. The number of cells arriving at output buffer j of switch plane i during cycle k is A
It is displayed as _kij (0 ≦ A _kij ≦ N). The set of cells arriving at output buffer j of switch plane i during cycle k is denoted by C _kij . Cell in C _kij and C
The cells in _{k, i + 1, j} arrive at their respective buffers at intervals of one time unit.

FIG. 3 shows a normal cell distribution operation in each distributor. The distributor demultiplexes cells into each switch plane at a rate N / S in each of the S time slots. The distributor cyclically changes the switch plane to which the incoming cell should be sent in each time slot in a repeating cycle. As is clear from the figure, in the first cycle, the cells are switch planes 1, 2 and S-1.
To the switch plane S, but not to the switch plane S at all. This is because there were no cells received by the distributor in that time slot. In the second cycle, no cells were sent to the first switch plane during the first time slot, and in the third cycle, cells were sent to each of the three switch planes shown. Within each switch plane, serial-to-parallel conversion, switching to the appropriate buffer, parallel-to-serial conversion to bring the pulse back into cell format, and then cell collection by a resequencer for transmission. .

In an ATM switch, the cells in the cell train sent out on the output line must be in the same sequence as when they arrived on the input line. Because of the large number of switch planes, individual cells can follow different paths within the switch, and different cells can also have different buffers to settle in, thus the sequence of cells can be out of order. In order to ensure that the cells in the row sent out on the output line are in the same sequence as they arrived on the input line, a resequencing operation must be incorporated. In order to maintain the integrity of the cell sequence by the resequencer, time stamps are added to the cells such that the value increases with each time slot. The various values shown in FIG. 3 are time stamps that would be suitable for the example shown.

In order to maintain the integrity of the cell sequence, the cell read is controlled by the resequencer. Cell resequencing ensures that the output line corresponding to the desired destination receives the cells in the correct sequence. Various resequencing formats have been proposed in the aforementioned paper which describes this type of switching system in more detail. In the preferred resequencing operation we propose, the resequencing concatenates the cells with the smallest timestamp value among the cells stored in the head of the buffer.

FIGS. 4A and 4B show the resequencing operation. FIG. 4A shows the states of the output buffers of the four specific switch planes # 1, 2, S-1, and S. Time stamps of cells existing on the output side of each buffer corresponding to the same output line. Indicates the value. As shown in the figure, the output buffer of the switch plane # 1 contains two cells with the time stamp 1. These two cells will be sent out first. Next, the cell with time stamp 2 in switch plane # 2 will be sent out as it is the minimum time stamp value. In FIG. 4B, these correspond to the cells shown on output line 31 as 1,1,2. Next to these, three cells having the time stamp value S shown in the switch plane #S are sent.

In the above-mentioned prior art described above, FIG. 2 and FIG.
The distributor shown in does not support load balancing. The present invention includes an improved distributor for assisting load balancing, which will be described below with reference to FIGS. 5, 6, 7 and 8. In particular, the distributors of FIGS. 2 and 3 would be replaced by the distributors described with reference to FIGS. 5, 7 and 8 to build an ATM switch that supports load balancing.

For the purpose of load balancing, each buffer corresponding to the output line has a light load state and a heavy load state.
It can be considered to be in one of two states. The number of cells in the buffer is the threshold value T
Below, or when it is equal to T, it is called a light load. Also,
When the number of cells in the buffer exceeds the threshold value T, it is called heavy load. Generally, T is 80% of the buffer capacity and 9
It will be between 0%.

FIG. 5 shows components included in each distributor for supporting load balancing. The interaction between the components will be described with reference to FIGS. 7 and 8. As shown in FIG. 5, the distributor 30 has seven components. That is, the load matrix 40, 1 cell
Buffer NC (41), 1-cell buffer OC (4
2), counter 43, decision circuit 49, logic circuit LC1
(47) and the logic circuit LC2 (48).

Each distributor has a load matrix 40 of a total of S × N bits corresponding to S rows and N columns.
Is provided. The matrix element L _ij is the switch plane i
Tells the status of the output buffer corresponding to line j in. This matrix element L _ij takes one of two values 0 and 1. If possible, the value 0 indicates a light load state and the value 1 indicates a heavy load state. The matrix elements are modified (or written) by the switching elements and used (or read) by the distributor.

The bit indicating the state of the buffer is fed back to each distributor by the switch element. This bit is called the buffer status signal. The buffer status signal is generated only when the status of the output buffer changes. The method used to generate this signal is described in FIG.

Each distributor has two finite buffers. The size of each finite buffer is conveniently one cell. One buffer 41 (NC) is for new incoming cells. This buffer NC is directly connected to the input line and receives cells from the input line during non-idle slots. Another buffer 42 (OC) is for storing cells that arrived during the preceding slot and whose distribution to the switch elements was deferred for load balancing purposes. There is a counter 43, which indicates the number i of the switch plane that will receive the cell in the slot of interest. This counter counts from 0 to S-1 and its count value is incremented by 1 for each slot. When the count value reaches S-1, it is reset to 0 in the next slot. When the counter indicates a value of i-1, switch plane i will receive cells as long as the distributor decides to send cells to the switch plane during that slot.

The decision circuit 49 includes buffers NC and OC.
Determine what to do with the cells in. How this decision is made is described next. Let us take as an example the decision to send the cells in the buffer NC to the switch plane and keep the cells in the buffer OC as they are. This decision may be made when the output buffers corresponding to cells in the NC are lightly loaded and the output buffers corresponding to cells in the OC are heavily loaded in the scheduled switch plane. In this case, the cells in the OC arrive at the distributor before the cells in the NC. However, since these cells are routed to different output lines, it does not matter if they leave the distributor with the sequence disturbed. The sequence must be preserved by the switch only for cells arriving via the same input line and destined for the same output line.

LC2 (48) provides the circuitry necessary to route cells within the NC or OC to the switch plane. The LC1 (47) provides a circuit necessary for transferring a cell in the NC to the OC or a cell in the NC to the switch plane through the logic circuit LC2.

FIG. 6 shows a simple circuit 50 that can be used to generate the buffer status signal. Obviously, other formats can be used. The counter 51 stores the current count value of the cells in the output buffer 55. The comparator 52 compares the threshold value T with the count value indicated by the counter 51. The output of the comparator 52 is 1 if the value of the counter is larger than T, and 0 otherwise. This buffer status signal is sent to the load matrix 40 in the distributor to modify the corresponding load matrix element. This circuit is built into the switch plane. One such circuit would be provided for each output buffer in the switch plane. A decision circuit 49 for making the aforementioned cell distribution decision is also required.

The decision circuit 49 uses four input signals to make a cell distribution decision. Two of the signals indicate whether the NC has a cell or not, and the OC has a cell or not. The remaining two signals, represented by lmn and lmo, indicate the state of the output buffers in the switch plane corresponding to the cells contained in the buffers NC and OC. It is sufficient that the decision circuit is a circuit that serves as a lookup table for performing the search function shown in Table 1. Various circuits can be used for this simple function. In particular, 4-bit microprocessors can be easily programmed to perform such functions.

FIG. 7 illustrates one of the possible modes of generation of the two signals lmn and lmo used by the decision circuit. The signal lmn indicates the item or state of the load matrix corresponding to the new cell in the buffer NC. The signal lmo indicates the item or state of the load matrix corresponding to the storage cell in the buffer OC. To generate these signals, the counter 43, which indicates the number i of the switch plane that will receive the cell in the slot of interest, selects the load matrix row and the buffer OC.
The destination field of the cell in selects the load matrix column. The load matrix item thus selected produces the signal lmn. For simplicity, logic circuits LC1 and LC2 have been omitted from FIG.

Table 1 shows all possible decision circuit input signal combinations. For a given value of the four input signals, the decision circuit triggers a number of possible actions. These actions are the three output signals d of the decision circuit.
It is encoded by c1, dc2 and dc3. These signals are sent to the logic circuits LC1 and LC2.
These two circuits ensure that the intended action is performed. Table 1 shows the actions corresponding to the given input signals and the values of the decision circuit output signals dc1, dc2 and dc3.

[0037]

[Table 1]

In the sixth column of Table 1, the signal lmn is disregarded even though there is a cell in the NC. Since lmo is 0 and the cell in OC arrives at the distributor before the cell in NC, O is set regardless of the value of lmn.
I decided to send the cells in C to the switch plane.

In the second column of Table 1, OC is empty. Therefore, the actions in the second and seventh columns are equivalent. Therefore, in these columns, the same value was assigned to the three output signals.

FIG. 8 shows a circuit arrangement for cell transfer between the components in the distributor 30. Logic circuit L
C1 is controlled by the signals dc1, dc2 and dc3 generated by the decision circuit 49. LC1 has one input,
There are two outputs. The input of LC1 is sent from the buffer NC. One output of LC1 is the input to LC2,
The other output is the input to the buffer OC. (Dc
1 = 0, dc2 = 1, dc3 = 0) or (dc1 =
0, dc2 = 0, dc3 = 1), the input of LC1 is combined with the output sent to the buffer OC and the cells in NC are transferred to OC. (Dc1 = 1, dc2 = 0, d
When c3 = 0), the input of LC1 is combined with the output sent to LC2 and the cells in NC are transferred to the switch plane via LC2. dc1, dc2 and dc3
In all other combinations of, the input of LC1 remains separated from the two outputs.

The function of the logic circuit LC2 is to transfer cells from the buffer NC or OC to the switch plane. Its output is S and is sent to S switch planes. Cells are sent to only one of the S switch planes. The switch plane which is the destination of the cell is determined by the counter 43. The value of the counter is L
Directly sent to C2. LC2 has three signals dc1 and dc
2, controlled by dc3. In LC2, the input is 2
One. One input comes from LC1. This input carries the cells in the buffer NC. The other input comes from the buffer OC. (Dc1 = 1, dc2 = 0, d
When c3 = 0), the input from LC1 is combined with the output to the switch plane and the cells in NC are transferred to the switch plane. (Dc1 = 1, dc2 = 1, dc3
= 0) or (dc1 = 0, dc2 = 0, dc3 = 1)
Then the input from the OC is combined with the output to the switch plane and the cells in the OC are transferred to the switch plane. With various other combinations of dc1, dc2, and dc3, the two inputs of LC2 remain disconnected from the S outputs.

It goes without saying that the particular embodiments described above are merely illustrative of the general principles of the invention. Obviously, various modifications thereto can be made without departing from the spirit and scope of the present invention.

[Brief description of drawings]

FIG. 1 shows the basic structure of an ATOM switch plane.

FIG. 2 shows the basic structure of an exchange using a number of parallel ATOM switch planes.

FIG. 3 shows a cell distribution operation for an ATOM switch plane.

FIG. 4 shows a resequencing operation.

FIG. 5 shows the components of the controller at the distributor in the system.

6 shows a part of a control device in an output buffer used together with the control device in the distributor shown in FIG.

FIG. 7 is an explanatory diagram regarding generation of two control signals in the distributor.

FIG. 8 shows cell transfers from one buffer in the distributor to another buffer and from the distributor to the switch plane.

[Explanation of symbols]

 10 ATOM switch element 12, 15 converter 13 time division bus 14 output buffer 16 output line 17 address filter

Claims (3)

(57) [Claims] 1. A plurality of inputs provided with a cell string of signal information.
A line and a cell string of the supplied signal information are transmitted.
In a switching system including a plurality of output lines, a plurality of output lines are provided, one for each of the output lines.
A plurality of switch planes having output buffer means, and provided to the input lines provided for each of the input lines.
Cyclically distribute cells to different switch planes
A plurality of distributing means associated with the output lines, which are provided for each of the output lines.
A sequence for collecting cells from a plurality of said output buffer means
All the cans means, the load information to monitor the load in each output buffer means
Hands to give feedback to the above mentioned means of distribution
And the distributing means is adapted to receive a cell when the cell is supplied.
A first buffer means for temporarily storing the cell and a second buffer means.
Comprising a Ffa means, the output buffer receives the load information, is supplied cell has a light load state
When the destination is a switch plane with
The cells stored in the buffer means are circularly switched
Output buffer that is distributed to the switch plane and the supplied cells are under heavy load
When the destination is a switch plane with
The cell stored in the buffer means is stored in the second buffer.
It is stored in a column, the supplied cell is processed next, and later processed.
When the output buffer means is in a light load state, or
When a cell destined for another heavily loaded output buffer is supplied
The cells stored in the second buffer are
A switching system characterized by distribution on the switch plane to be replaced. 2. Each of the switch planes has an input series section.
A parallel-to-parallel converter for converting
Time-sharing bus hand for flowing parallel cells for the purpose of starting
And the parallel to direct conversion of the parallel cells into serial cells.
And a converter to a column.
On-board exchange system. 3. The first and second buffer means are respectively provided.
A single cell buffer means.
The exchange system according to 1.