On the complexity theory of switching networks

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.

Name thesis:degree_name

Doctor of Philosophy - PhD

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of British Columbia

Year dc:date

1993

Author dc:creator

• Lin, Geng

Statement dc:rights

• 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.

Language dc:language

eng

Handle dc:identifier

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

OAI identifier oai:identifier

oai:circle.library.ubc.ca:2429/1662