Open Collections

On the complexity theory of switching networks

University of British Columbia

Fast and efficient communications are essential to the success of large-scale multiprocessor parallel processing systems, distributed processing systems, and telecommunication systems. Switching networks are constructed to support simultaneous communications (of data, voice, image and video) in these systems. This thesis focuses on the complexity theory for the construction of switching networks, with primary emphasis on (a) the complexity of the networks, as measured by the size (number of switches), the depth (largest number of switches on any communication path) and the degree (the largest fan-out of a switch); (b) the complexity of the routing algorithms of the networks, as measured by the time and space; and (c) the fault-tolerance of the networks. We present the first simultaneous "weakly optimal" solutions for the explicit construction of non-blocking networks, and the design of the parallel routing algorithms. "Weakly optimal" here means that all measures of complexity (size and depth of the network, time for the algorithm, and space for the data-structure) are within one or more logarithmic factors of their smallest possible values. We also consider routing algorithms for networks with probabilistic traffic. We present an optimal routing algorithm for series-parallel networks (which includes a broad range of useful connection networks for parallel architectures, e.g., butterflies and Bend networks).The algorithm has an asymptotically minimum expected time among all routing algorithms. We consider fault-tolerant switching networks under a random switch-failure model. We prove lower bounds for the size and depth of fault-tolerant non-blocking networks, rearrangeable networks and superconcentrators. And we explicitly construct such networks with optimal sizes and depths. We also consider fault-tolerant planar switching networks, which become attractive because of the rapid advances in VLSI technology. We prove lower bounds for the degrees of vertices of fault-tolerant planar rearrangeable networks and superconcentrators. We construct such fault-tolerant planar networks with optimal sizes and degrees.

Thesis/Dissertation

application/pdf

2008-09-05

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/1662

Computer Science

University of British Columbia

UBCV

DSpace