The present invention relates to a switch used in the Broadband Integrated Services Digital Network(hereinafter referred to as BISDN) adopting Asynchronous Transfer Mode(hereinafter referred to as ATM) and, in particular, relates to an output buffer type ATM switch dividing output lines into several output groups so that output lines in a same group share a common buffer, thus having multiple paths between input lines and output lines.
ATM switches have been rigorously developed during the past several years and currently proposed ATM switches have four types: common buffer type, common medium type, space division type, and complete connection type. The common buffer type switch has one buffer commonly used by all the input/output lines and thus requires that the speed of a processor controlling the buffers should be increased in proportion to the number of input/output lines. Hence, the number of input/output lines in a switch is limited by the speed of the processor.
The common medium type switch also has the same limitation resulting from having only one medium to be shared. Therefore, common buffer type and common medium type are used in small-capacity switches rather than in large-capacity switches due to a problem, of speed-up. On the other hand, space division type and complete connection type switches have the advantage of having no speed-up problem even in large-capacity switches.
FIG. 1 shows the structure of an 8.times.8 Banyan network(hereinafter, for example, N.times.N network means a network with N input lines and N output lines) which is a traditional space division type switch. In an 8.times.8 Banyan network, twelve basic Switching Elements(hereinafter referred to as SE) are arrayed in three stages. Hence, in a N.times.N Banyan network with N input lines, log.sub.2 N.times.(N/2) SEs are arrayed in log.sub.2 N Stages.
A SE with two input/output ports checks one bit among output port addresses included in a cell inputted through each input port and sends the cell to the lower-end or upper-end output port when the checked bit has value 1 or 1 respectively.
The aforementioned space division type switch is easy to operate, and due to the distributed processing, eliminates the processing speed problems arising from high-speed processing inside the switch. It is also easy to diagram the inter-connection structure between one stage and another stage of the SEs. Since space division type switch due to a blocking of the switch, is not limited by the number of input/output lines increasing in a large-capacity switch, it has been rigorously developed as a basic structural model for the BISDN switch.
The aforementioned switch, however, has a problem of low efficiency due to the cell collision phenomenon arising in the inner part or output lines of the switch.
Suppose output line addresses are 101 and 100, respectively for two cells inputted through two input lines(1, 4). Since the two cells have the same most significant bit of output line addresses impressed by two input ports of the SE 116, they are sent to the same output port(0), resulting in an inner cell collision. Therefore, only one cell is successfully sent to the output line and the remaining cell is either lost or sent to the other output line through output port(l), resulting in a cell loss.
Suppose output line addresses have the same value of 011 for two cells inputted through two input lines (0, 7). Then, the two cells are respectively inputted through two input ports (0, 1) of SE 120 in the stage-2, resulting in an output line cell collision. Since the least significant bits of two cells have the same value of 1, only one cell is outputted to the output line(3) through the desired output port(l) of the SE, and the other cell is lost. Considering 10.sup.-6 cell loss, which is one factor of the Quality of Service (QOS), the space division type switch should not have the problem of cell collision to be eligible for the BISDN.
FIG. 2 shows the structure of a traditional Batcher-Banyan switch which solves the problem of a cell collision. A Batcher-sorting network (hereinafter referred to as BSN) 201 and a Banyan network 202 are serially arrayed in this structure. This switch arrays input line cells in the order of output line address from the top(the lowest address) to the bottom (the highest address). Cells with-the same output line addresses are adjacently outputted and idle cells are outputted through the lower output line of BSN 201. Each cell outputted through the BSN is sent to the desired output line of the switch through the Banyan network 202.
The aforementioned Batcher-Banyan switch eliminates inner cell collisions by firstly executing sorting through the BSN, and secondly routing through the Banyan network. But cells with the same output line address still have the problem of an output line cell collision.
Considering the fact that, under the BISDN environment, diverse output line addresses of the cells causes a higher cell loss rate by an output line cell collision rather than by an inner cell collision, the Batcher-Banyan switch still has the shortcoming of high cell loss rate.
FIG. 3A and 3B show the structure of a Knockout switch which is a traditional complete connection type. A Knockout switch generally has a bus type structure, as shown in FIG. 3A, and a packet filter 301 is connected to each bus, as shown in FIG. 3B. A cell is inputted to the output buffer 303 through said packet filter 301 and the concentrator 302. N input cells are concentrated as L output cells through the knockout tournament at the concentrator 302 and sent to the output buffer 303, as shown in FIG. 3C.
Since said complete connection type switch has a unique path between an input line and an output line, all input cells are simultaneously sent to their desired output lines. Hence, the complete connection type switch has an ideal structure where there is no cell loss. But, the number of all cross points of the switch is increased to N.sup.2 when the number of input lines is N. This fact causes the complexity of hardware in a large capacity switch. Thus, the complete connection type switch is limited to small capacity uses.