Crosspoint and buffer complexity, density properties, and efficient design of concentrators for packet switching networks
A. Yavuz Oruç, E. Gunduzhan · 1998
The new and attractive B-ISDN services such as video on demand, digital high-definition TV, and high quality videoconferencing, will be possible by the availability of affordable switches working in high-speed networks. In this dissertation we investigate cost efficient designs of some important packet switching fabrics, namely concentrators and superconcentrators. We introduce a new model for concentrators and superconcentrators with input, output, or intermediate buffers, and working in packet switching environments. This model is more general than the existing circuit switching models for these fabrics. Using this model we find lower and upper bounds on the crosspoint complexity of buffered sparse crossbar and multistage concentrators, and buffered superconcentrators. We also design a buffered sparse crossbar concentrator which attains the lower bound, and hence is optimum in crosspoint complexity. We also investigate the density of sparse crossbar concentrators among all bipartite graphs. We establish that this density tends to 0 when the total buffer space ratio is less than 1/2, and it tends to 1 when this ratio is greater than 1/2.