JPH02288439A - Cell switch - Google Patents

Abstract

PURPOSE:To attain improvement in the transfer efficiency of a cell and the effective use of a buffer by giving a cell sending opportunity to prescribed plural cells in sequence of older housing period in each buffer. CONSTITUTION:A cell input means 15 writes the cell from an input communication line 101 sequentially on the buffer 17, and plural cells are read out in sequence of older housing period in the buffer 17 by a phase control means 25, and a request packet is sent to a switch network 11. Next, the packet is sorted by a sorting means 19 based on the output route information of each request packet and priority control information, and the packet with higher priority is arranged at an upper position. The output route information of an output packet neighboring to the sorting means 19 are compared sequentially at a comparison means 21 at the following stage, and when coincidence is obtained between them, a succeeding packet is deleted, and when they are different, they are sent to a routing means 23. Therefore, no disturbance or blocking of a processing for a valid packet by an invalid packet occurs. Thereby, throughput can be im proved, and the effective use of the buffer can be attained.

Description

[Detailed Description of the Invention] [Object of the Invention] (Field of Industrial Application) The present invention is directed to ATMil! ! The present invention relates to cell switches used in exchanges and the like forming communication networks.

(Prior art) In recent years, STM (Syn
The transfer mode is called chronous transfer mode (ATM), which uses the information transmission capability of the communication network when the communication terminal needs it.
nchr.

There is growing interest and expectation in transfer mode (nous transfer mode).

ATM transmits information using fixed-length short packets called cells, and each communication terminal passes the cell to the communication network as needed.In other words, the communication terminal uses the information transmission capacity of the communication network when necessary. This is a transfer mode characterized by the use of

Conventionally, in a cell switch composed of a Batcher Banyan network, 'A Broad-band Pa
cket 5v1tch for Integra
ted Transport” (IEEEJ, ON
SEL, AREAS IN C0MM, VOL,
5AC-5, No. 8. A cell switching method called the 3-phase algorithm shown in J. O. C.T., 1987) is used. In the ATM communication network,
Cells flowing on the input communication path enter the Batcher Banyan network, are switched internally, and are sent out to the output communication path.

The Batcher network sorts cells based on output route information indicating the output light of each cell. Within a batcher network, collisions (blocking) due to two or more cells taking the same route never occur, and cell discards never occur. The following Banyan network is a type of self-routing network, and transfers the cell to the corresponding output channel based on the outgoing route information of the cell. In the Banyan network, collisions do not occur within the network due to the presence of the preceding Batcher network. However, if the output route information of cells simultaneously input to the cell switch from the input communication path is the same, a collision occurs on the output communication path. A three-phase algorithm was devised to avoid this problem. To give an overview of the three-phase algorithm, before a cell is sent from each input channel into the Batcher Banyan network, it checks the outgoing route information of each cell and uses the same outgoing route information. If a cell exists, transmission permission is given to only one of them, and cell transmission is postponed to the other input channels to avoid collisions on the output channels. Therefore, the input section of the cell switch requires a buffer corresponding to each input communication channel. In the input channel where a cell could not be transmitted, the cell is stored in the buffer and a transmission opportunity in the next cycle is waited. Here, the period refers to the period from when the route information of a cell is read from the buffer to when the route information and the corresponding cell are subjected to 3-phase algorithm processing until the next route information is read. . As the name suggests, the three-phase algorithm consists of three phases i, n, and m.

Each phase will be explained below.

Φ Phase I A request packet consisting of incoming route information corresponding to each input communication path and outgoing route information possessed by cells that have flowed on the input communication path is sent to the batcher network. In the batcher network,
Request packets input to the batcher network are sorted by output route information. As a result, request packets with the same output route information are adjacent in the sorting output. Therefore, the output route information of adjacent request packets in the sorting result is compared, and the output route information of the k-th and 11th is different. In this case, the second request packet shall be granted. Further, if the output route information of the k-th request packet matches the output route information of the 11th request packet, the 11th request packet is permitted.

In the sorting result example shown in FIG. 17, the numbers in parentheses indicate incoming route information, and the numbers outside parentheses indicate outgoing route information. In the example shown in FIG. 17, all packets other than request packets having a value of 2 as inbound route information are permitted.

Phase ■ If the request is accepted in phase ■ and the cell that has flowed on the first input communication path is allowed to be sent into the communication network, that information must be returned to the first input communication path. However, this phase is where this is done. Therefore, the second output port and the second input port of the Batcher network are connected, and the input route information of the request packet permitted by Funny's I is input to the Batcher Banyan network. Furthermore, by connecting each output l of the Banyan network to the input l of the Batcher network in advance, cell transmission permission can be transmitted to the input communication channel through which the request packet permitted in phase I was sent. Such changes in the circuit configuration for each phase are performed using multiplexers and demultiplexers. The reason why no collision occurs in phase (3) is because the incoming route information is all different. FIG. 18 shows the circuit configuration in phase (2) and the processing results in phase (2) for the example sorting result shown in FIG. 17. The input route information 1n-0゜1.3 allowed in Phase I was returned to the input port of the Batcher network, sorted within the network, and then input to the Banyan network and transferred to the corresponding output port. It is then returned to the input port of the batcher network.

・Phase ■ The input channel that has received permission for the request packet sends the cell through the Batcher Banyan network to the output channel corresponding to the output route information of that cell.

Input channels that are not allowed store cells in a buffer,
Prepare for the transmission opportunity in the next cycle. FIG. 19 shows the processing results of phase (2) for the example considered above.

The input communication paths I-0, 1, and 3 that have received permission send out cells containing unique data into the communication network.

When cells are switched according to this algorithm, the buffer becomes a general FIFO (FirstIn
First Cut) buffer, one cell stored in each buffer most recently, a total of n cells, becomes transfer target candidates in each transfer process cycle. If there are M cells with the same outgoing route information, that is, if HOL blocking occurs, at least M cycles of switching are required for all of these cells to pass through the Batcher Banyan network. Although the operation is necessary, the input channel that outputs the cell at the Mth time cannot transmit any cells at all in the previous M-1 switchings. This greatly reduces the cell transfer efficiency and prevents efficient use of the buffer, leading to an increase in the buffer capacity, ie, the number of cells to be stored, in order to obtain the required switching performance.

(Problems to be Solved by the Invention) As described above, cell switches that operate using the conventional three-phase algorithm have the problem of being vulnerable to HOL blocking, resulting in poor cell transfer efficiency and ineffective use of buffers. An object of the present invention is to provide a cell switch that solves the above-mentioned problems in the conventional technology, quickly eliminates HOL blocking, has high cell transfer efficiency, and allows effective use of buffers. shall be.

[Structure of the Invention] (Means for Solving the Problems) The cell switch of the present invention, which has been made to achieve the above object, receives input from a plurality of input communication channels and adds incoming route information and outgoing route information. A cell switch that synchronously transfers a plurality of cells to a plurality of output communication paths, the cell switch comprising a plurality of storage means provided for each input communication path to store cells input from each input communication path. , input route information and output route information of a plurality of predetermined cells from each storage means in order from the cell stored first among the plurality of cells stored in each storage means; a selection means for determining transferable cells for each storage means based on route information; and a notification means for notifying each storage means of information specifying the cells determined to be transferable by the selection means. have

(Operation) The selection means gives an opportunity to transmit cells to a predetermined number of cells in order of oldest storage time in each buffer. This allows HOL for the first cell stored in each buffer.
Even when blocking occurs, there is a possibility that the next stored cell will be sent out, improving overall throughput and buffer usage efficiency.

(Example) An embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram of a cell switch 1 according to an embodiment of the present invention. The cell switch 1 has each input communication path 10
Each cell input through 1(0) to 101(n-1) is connected to an output communication path 103(0) to 103(n-1).
1), and n cell storage means 3(0) to 3(n-1) corresponding to each input communication path.
), selection means 5, notification means 7 and transfer means 9.

Each cell storage means 3(0) to 3(n-1) temporarily stores cells input via input communication paths 101(0) to 101(n-1), respectively.

The selection means 5 inputs incoming route information and outgoing route information of a plurality of predetermined cells in order from the first cell stored among the plurality of cells stored in each of the storing means, and selects each of the plurality of cells. Cells that can be transferred are determined for each of the storage means based on cell output route information.

The notification means 7 notifies each storage means of information specifying the cells determined by the selection means 5 to be transferable.

The transfer means 9 inputs cells determined to be transferable from each storage means, and transfers them to each output communication path 103(0) to 103.
(n-1).

FIG. 2 is a circuit diagram of the cell switch 1 that performs such processing. The cell switch 1 is broadly divided into cell storage means 3(0) to 3(n-1), a switch network 11, and control devices 13(0) to 13(n-1) for each port.

The selection means 5, notification means 7, and transfer means 9 are all composed of a switch network 11 and control devices 13(0) to 13(n-1) for each port.

Each cell storage means 3 (i) (J-0, 1,...
n-1) is the cell input means 15 (i) and the buffer 17 (
i). The switch network 11 has one sorting means, a comparison means 21, a routing means 23, etc., and each control device 13(i) has a phase control means 25(f
), multiplexer 27 (1), demultiplexer 29
(1), a cell transfer permission buffer 31(1), a cell output means 33(1), and the like.

In this embodiment, the sorting means 19 is constituted by a Batcher network, and the routing means 23 is constituted by a combination of an inverse Banyan network and a Banyan network, which are self-routing multistage networks.

The operation of the cell switch 1 having such a configuration will be described below.

The cell input means 15(1) takes in cells flowing on the input communication path 101(i) and sequentially writes them into the buffer 17(1). This operation is performed independently of the switching operation described below.

The cell switch 1 of the present invention performs periodic operation in which each period consists of three phases as shown below. That is, in phase (2), the phase control means 25 (I) in each control device 13 (1) first reads out the oldest cell existing in the buffer 17 (t) at that time, and stores the valid bit, output route information, A request packet consisting of priority control information, ingress route information, and buffer information is sent to the switch network 11. As soon as the sending is finished,
Similar processing is performed on the next oldest cell stored in the buffer 17(i) after the cell described above, and a corresponding request packet is sent to the switch network 11. As described above, request packets for 3 cells are sent to the switch network 11 in order from the cell stored in the buffer 17(i) earliest.
sent to. At this time, the request packets are sent out synchronously between each phase control means 25 (i). This corresponds to processes (1) to (2) in FIG. FIG. 3 shows the structure of the request packet. Buffer information means that the cell corresponding to the request packet is in the buffer 17(1).
This is information indicating how old the data has been stored.

In addition, priority control information is used to select an allowable request packet from among multiple request packets with the same outgoing route information, in which case the smallest value of priority control information is selected. Those that have are selected. This priority control information is assumed to be changed every time one request packet is sent out, as shown in an example in FIG. This reduces the possibility that a port that has been granted transmission permission twice in the same cycle will receive transmission permission twice. Furthermore, the valid bit indicates whether the request packet is significant or meaningless. In other words, if there are no cells in the buffer, a corresponding request packet cannot be created, so by setting this valid bit to 1,
Indicates that the request packet is invalid.

Multiplexer 27 (I) and demultiplexer 29 (t
) both switch the signal flow corresponding to the phase change. Here, the multiplexer 27(i) switches the output signal to the switch network 11, and the demultiplexer 29(I) switches the destination of the signal input from the switch network 11. That is, in phase I, the multiplexer 27(i) is connected to the phase control means 25(1).
A request packet is input to the switch network 11, and the request packet is output to the switch network 11. FIG. 7 shows an example of a total of 4×8 request packets input to the switch network 11 in one cycle. That is,
The number of input ports is 8, and 4 from each storage means in each cycle.
This is a case where the outgoing route information and incoming route information of the cells -0 are input to the selection means 5. The eight request packets located at the right end in FIG. 7 and indicated by the symbol A are: Each buffer 17 (0
) to 17(7), corresponds to the entire request packet corresponding to the cell with the oldest storage time, and is hereinafter indicated as B, C, and D in order of oldest storage time. Further, when the valid bit or empty cell indication is 1, the data has no meaning. That is, each process in the switch network 11 does not consider such data at all. Therefore, in FIG. 7 and the like, such data portions are displayed as "?".

The 4×8 request packets denoted by A are phase I.
are input to the switch network 11 at the same time.

The eight request packets indicated by A in FIG. 7 that are simultaneously input to the switch network 11 in Phase I are sorted by the sorting means 19 according to the outgoing route information and priority control information that each request packet has (FIG. Processing in ■
). FIG. 8 shows an example of this sorting result. In FIG. 8, A.

The eight request packets at the right end indicated by are the sorting results for the eight request packets indicated by A in FIG. For request packets with the same output route information, sorting is performed such that the smaller the value of the priority control information, that is, the higher the priority, the higher the priority in the output result. Furthermore, packets whose valid bit value is 1, that is, invalid packets, are arranged at the bottom.

The following comparing means 21 sequentially compares the output route information of the adjacent first and tx-1st output packets in the output of the sorting means 19, and if the two are equal, rejects the third packet, and if they are not equal, rejects the third packet. The sixth packet is sent to the routing means 23 (processes 1 to 2 in FIG. 4). The eight request packets indicated by the symbol ^'' in FIG. 9 illustrate the results of this comparison with respect to the eight request packets indicated by the symbol ° in FIG.

In FIG. 8, it is assumed that the top request packet is always sent to the routing means 23.

Further, a request packet is discarded by setting the value of the valid bit in the request packet to 1. That is, in each process, a request packet whose valid bit has a value of 1 is treated as invalid, and such an invalid request packet does not interfere with or block the processing of valid request packets.

The routing means 23 transfers the eight input request packets to the corresponding output ports based on the output route information they have (process @l in FIG. 4). The eight packets indicated by the symbol A°" on the far right of FIG. The input route information and buffer information of these packets are stored in the cell transfer permission buffer in the control device corresponding to the output route information.

For example, the input route information and buffer information of the second packet from the top among the eight packets indicated by the symbol A°'' in FIG. 31 (1) (processes 0 to ■ in FIG. 4).

Subsequently, the above processing is performed for each of eight request packets indicated by symbols B and C1D in FIG. Note that the processing for B, C, and D at this time is performed continuously. In other words, when the input of A to the sorting means 19 is completed,
Input of B starts immediately, and so on.
, D are input, and the sorting means 19 performs the corresponding processing.

The input route information and buffer information of each request packet output from the routing means 23 are such that if the request packet is valid and the cell transfer permission buffer in the control device corresponding to the output route information is empty, stored in this buffer.

Transfer permission is granted for 2 and 1 packet, respectively, of the 8 request packets denoted by B and C in FIG. 7, which are respectively denoted by B in FIG. These correspond to two and one packets shown as shaded out of the eight packets shown as ``'' and C''.

FIG. 11 shows the data thus set in each cell transfer permission buffer 31(0) to 31(n-1) in Phase I.

In phase ■, each transfer permission buffer 31 (0
) to 31(n-1), that is, a permission packet consisting of a valid bit, input route information, and buffer information is input to the switch network 11 (processes 0 to 0 in FIG. 5).

The structure of each permission packet is shown in FIG. This input of the permission packet to the switch network 11 is performed by the phase control means 2.
Multiplexer 2 with 5(0) to 25(n-1)
This is done through control of 7(0) to 27(n-1). Signal 203(1) in FIG. 2 represents this control signal. Here, in the same manner as in Phase I, based on the incoming route information and buffer information, the permission packet that has passed through the sorting means 19, the comparing means 21, and the routing means 23 is sent to the control device 13 (1) that sent the corresponding request packet. returned to
This becomes a cell transfer permission signal 201(1) to the phase control means 25(1) in the control device 13(1).

Processing (2) in FIG. 5 corresponds to the processing by the sorting means 19 in phase (2), and an example of the processing result is shown in FIG.

That is, in the sorting means 19, the eight permission packets are arranged in order according to their incoming route information values. Further, among the permission packets having the same incoming route information, the one with the smaller buffer information value, that is, the one with the older storage time in the buffer, is arranged in the higher order. Processing in Figure 5 ■
. . . O corresponds to the processing by the comparison means 21 in phase (2), and an example of the processing results is shown in FIG.

In other words, in the example we are considering, there are two permission packets with the same ingress route information value of 4, but generally the highest ranked among these permission packets is selected, and the one lower than the others is selected. For the request packets arranged in , invalidation processing is performed by setting the value of the valid bit to 1. Therefore, among a plurality of grant packets having the same incoming route information value, the one corresponding to the cell stored in the buffer corresponding to the incoming route information value earliest is selected.

Processing O in FIG. 5 corresponds to the processing in the routing means 23 in phase (2), and FIG. 15 shows an example of the processing result.

That is, in phase (2), the routing means 23
transfers the permission packet to the corresponding input port according to the input route information value of the valid one among the eight input permission packets.

In this way, in phase (2), valid permission packets in each transfer permission buffer are transferred to the corresponding input port, at most one for each ingress route, based on the value of the ingress route information contained in the permission packet. .

The phase ■ that follows phase ■ is the Funnies above ■
This is a series of processes for actually outputting each cell for which transfer permission has been obtained to the output communication channel. Processing O to O in Figure 6
constitutes phase ■.

Each phase control means 25(i) has a transfer permission signal 201(
1), the corresponding cell is read from the buffer 17(1) and a cell transfer packet consisting of the output route information and the cell is sent out (processes O and 0 in FIG. 6). 16th
The figure shows the structure of a cell transfer packet. The cell transfer packet passes through the switch network 11 and is transferred to the output light according to the output route information, and then passes through the cell output means 33 (1) in each control device 13 (1) to the output communication path 103 (1). Output. Then, in preparation for the start of the next cycle, each transfer permission buffer 31(1) is emptied (processes 0 to 0 in FIG. 6).Here, if the cell transfer rate of the cell switch 1 is If the transmission speed is faster than the transmission speed of cell output means 3
It is necessary to provide a buffer in 3(I) for accumulating output cells.

As described above, the switching operation is repeated in one cycle from the sending of the request packet to the arrival of the cell at the cell output means 33(1).

Note that this is the handling of request packets when there are no cells in the buffer 17 (1) or packets that are discarded by processing within the switch network, but in this case, the packet is not significant so that the switch network performs a predetermined operation. It is necessary to add this information and send it within the network. For example, process (2) in FIG. 4 corresponds to this process. Therefore, each packet has an information bit indicating whether the packet is significant or not. Moreover, non-significant packets do not hinder the progress of meaningful packets within the switch network.

By the way, regarding the configuration of each buffer 17(1), if the buffer overflows, it is possible to make HOL blocking more efficient by discarding the oldest existing cell instead of discarding the newest cell. It is possible to reduce the

[Effects of the Invention] As explained above, according to the cell switch of the present invention,
Since more cells accumulated in the buffer of the input section are given an opportunity to be transmitted in each cycle than in the case of the prior art, the throughput of the cell switch can be improved and the buffer can be used effectively.

[Brief explanation of the drawing]

FIGS. 1 and 2 are block diagrams showing the configuration of a cell switch according to an embodiment of the present invention, FIGS. 3, 12, and 1.
6 is a block diagram of the request packet, grant packet, and cell transfer packet used in the cell switches shown in FIGS. 1 and 2, respectively. Flowcharts for processing performed in the cell switch, FIGS. 7, 8, 9, and 10
11, 13, 14, and 15 are diagrams showing examples of each processing result in FIGS. 4, 5, and 6, and FIG. 17, FIG. 18, and FIG. FIG. 19 is an explanatory diagram of the conventional three-phase algorithm. 1... Cell switch 3 (0), 3 (1), ..., 3(n
-1)...Cell storage means 5...Selection means 7...Notification means 9...
Transfer means 11... switch network 13 (0),
13 (1),..., 13(n-1)...Control device 15(0)...Cell input means 17(0)...Buffer 19...Sorting means 21...Comparing means 23・
... Routing means 25 (0) ... Phase control means 27 (0) ... Multiplexer 29 (0) ... Demultiplexer 31 (0) ... Cell transfer permission buffer 33 (0
)...Cell output means

Claims (2)

[Claims] (1) A cell switch that synchronously transfers a plurality of cells inputted from a plurality of input communication paths and to which ingress route information and egress route information are added to a plurality of output communication channels, each input communication a plurality of storage means provided for each input communication channel for storing cells inputted from the storage means; a selection means for inputting incoming route information and outgoing route information of the cells from the respective storage means and determining transferable cells for each of the storage means based on the outgoing route information of each cell; and the selecting means 1. A cell switch comprising: notification means for notifying each storage means of information specifying a cell determined to be transferable. (2) The selection means has N input ports and N output ports, and sorts N bit strings input simultaneously from the input ports and each expressing output route information according to the value of the output route information. and a sorting means for outputting to N output ports, inputting N bit strings from the sorting means, comparing output path information values of each bit string, and determining output path information values of the plurality of bit strings as a result of the comparison. If it is determined that the bit strings match, one bit string is selected with a predetermined priority from among the plurality of bit strings, the cell corresponding to this bit string is determined as a transferable cell, and the output route information of a certain bit string is Claim 1 further comprising comparing means for determining a cell corresponding to this bit string as a transferable cell if the value is determined to be different from the output route information value of any other bit string.
Cell switch as described.