Concentrators in large-scale packet switching

Concentrators provide a cost-effective solution for enhancing performance of existing switching systems by absorbing the traffic fluctuation and burstiness. This thesis treats three topics on the design and application of self-route concentrators.; First, when the method of statistical line grouping is applied to a multistage interconnection network of 2 x 2 switches, every interconnection line is replaced by a bundle of n lines and every 2 x 2 switch is dilated into a 2 n x 2n switch. The 2n x 2 n switch needs not be nonblocking but needs to possess the following characteristic under a certain self-route control: Divide the 2n outputs evenly into Group-0 and Group-1; then, as many 0-bound packets as possible should be routed to Group-0 and as many 1-bound packets as possible should be routed to Group-1. A 2n-to-n concentrator constructed in the form of a partial sorting network meets this description. This technique of statistical line grouping is especially effective in the physical construction of switches from a generic component of the chip size when the underlying multistage interconnection network is of the divide-and-conquer type. Analysis and simulation show that switching fabrics constructed in this extremely economical manner trim the packet loss to negligible rates.; A 2n-to-n concentrator constructed in the form of a partial sorting network is of particular practical interest when n is a reasonably large power of 2. The second topic of study is on the optimal construction of such concentrators in terms of layout complexity under the 2-layer Manhattan layout model. Two specific issues are pursued in great detail. One is the fine-tuned construction of a 32-to-16 concentrator in order to best all known constructions under all conceivable useful criteria. Another issue is concerned with 2n-to-n partial sorting networks that do not yield concentrators but practically serve for the purpose in the statistical sense. We also propose a new scheme for building a large concentrator.; The design of a self-route concentrator does not have to be in the form of a partial sorting network. The third topic of study is on an alternative construction of concentrators specifically for single-bit controlled input signals. The approach is from the interconnection of 2 x 2 switches that are under mixed in-band and out-of-band control. The out-of-band control is administered in a self-route fashion across each stage of 2 x 2 switches in the multistage interconnection. The physical complexity of the concentrators so constructed is very low, although the administering of out-of-band incurs a substantial overhead in switching. The overall comparison with all previous arts verifies the cost-effectiveness of this construction for concentrators that are not too large.