New results in the design and analysis of nonblocking switching networks.

摘要

Switching networks are the core component of modern switching devices for voice and data communications. The evolution of switching networks dates back to the early days of telephony. Advances in communication technologies, such as broadband communications and optical transmissions, as well as the explosion of demand on switching capacity have made switching network design an ever-more challenging task. Switching speed is the bottleneck at the core of the Internet and communication-intensive data centers. Consequently, characterizing the complexity of switching networks and constructing cost-effective switching networks under modern requirements are important problems both theoretically and practically.;In switching network theory, the first important class of questions needed to be addressed is of the type: "how complex is it to design a switching network satisfying such and such requirements?" In order to answer this type of questions, we first need to formulate a complexity model for the switching networks in the desired switching environment. This class of questions has been studied extensively in the classical environment of telephone (or circuit) switching for the past 60 years. Results and techniques obtained for circuit switching have proved to be very useful, with deep connections to other areas of Mathematics and Theoretical Computer Science. Under the newer switching environments such as broadband switching and optical switching, much less is known, however. This dissertation partly fills the gap by addressing two important complexity problems in broadband switching and optical switching. Briefly, we resolve a 20-year old open question regarding the optimal complexity of a multirate distributor, which is the complexity model representing rearrangable multicast switching network under the broadband environment. We also provide several complexity models for optical switching networks and show how to construct optical switching networks of optimal sizes.;The second class of questions in switching network studies is to design practical switching networks using commodity switching elements. This type of questions certainly has also been studied extensively in circuit switching. Many good constructions are known, such as the Clos network, Cantor network, Benes network, and so on, which have been widely used in practice. This dissertation continues the tradition by introducing combinatorial optimization techniques for analyzing the class of multi-log networks. Our maxflow-mincut and linear programming based techniques prove to be simpler and more effective than known ones in analyzing multi-log networks. New constraints such as crosstalk and fanout in optical switching can be incorporated into the combinatorial problem formulation and handled effectively by our techniques.