{"id":{"repo_id":"ubc","oai_identifier":"oai:circle.library.ubc.ca:2429/1662"},"canonical_url":"https://search.dev.ndltd.org/etd/ubc/oai:circle.library.ubc.ca:2429/1662","repository":{"repo_id":"ubc","name":"University of British Columbia","base_url":"http://circle.library.ubc.ca/oai/request"},"display":{"title":"On the complexity theory of switching networks","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Lin, Geng"],"institution":"University of British Columbia","degree_name":"Doctor of Philosophy - PhD","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1993,"date_issued":"1993","date_published":"1993","updated_at":"2026-07-24T05:07:28Z","subjects":[],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2429/1662","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lin, Geng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1993"]},{"key":"dc:publisher","label":"Institution","values":["University of British Columbia"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy - PhD"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of British Columbia"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2429/1662","http://circle.library.ubc.ca/bitstream/2429/1662/1/ubc_1993_spring_phd_lin_geng.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["4568090","application/pdf"]},{"key":"dc:title","label":"Title","values":["On the complexity theory of switching networks"]}]}],"canonical_facts":{"dc:creator":["Lin, Geng"],"dc:date":["1993"],"dc:description":["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."],"dc:format":["4568090","application/pdf"],"dc:identifier":["http://hdl.handle.net/2429/1662","http://circle.library.ubc.ca/bitstream/2429/1662/1/ubc_1993_spring_phd_lin_geng.pdf"],"dc:language":["eng"],"dc:publisher":["University of British Columbia"],"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."],"dc:title":["On the complexity theory of switching networks"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy - PhD"],"thesis:institution_name":["University of British Columbia"]},"updated_at":"2026-07-24T05:07:28Z"}