On the Complexity Theory of Switching Networks by GENG LIN B.Sc., Beijing University, China, 1985 M.Sc., Beijing University, China, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA December 1992 © Geng Lin, 1992 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) Department of Co m p ukte The University of British Columbia Vancouver, Canada Date ^DC-L^rf:2^, DE-6 (2/88) I (-14 Z 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 faulttolerance 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 ii 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. iii Contents Abstract^ ii Contents^ iv List of Figures^ vi Acknowledgement^ 1 2 Introduction 1 1.1 Communications and Switching Networks ^ 1.1.1^Complexity Aspects of Switching Networks ^ 1.2 Circuit Switching and Packet Switching ^ 1.2.1^Circuit Switching ^ 1.2.2^Packet Switching ^ 1.3 A Historical Overview ^ 1.4 Thesis outline ^ 1 3 4 4 5 6 12 Routing in Non-blocking Networks 14 2.1 2.2 2.3 2.4 2.5 3 viii Non-blocking Networks ^ The Networks ^ A Randomized Parallel Algorithm ^ The Data-structure for the Deterministic Parallel Algorithm ^ A Deterministic Parallel Algorithm ^ Routing in Networks with Probabilistic Traffic 3.1 3.2 3.3 3.4 3.5 Probabilistic Model and Previous Work ^ The Networks ^ Main Result and the General Strategy ^ The Almost-Series Case ^ The General Case ^ 3.5.1^Routing Algorithms of the "Restricted Class" ^ 3.5.2^Routing Algorithms without Restriction ^ iv 14 19 21 23 26 34 34 36 39 40 44 46 50 4 Fault-Tolerant Switching Networks 4.1 The Switch Failure Model ^ 4.2 The Networks ^ 4.3 Fault-Tolerance ^ 4.4 Main Result and the Overall Strategy ^ 4.5 The Lower Bounds ^ 4.6 The Upper Bounds ^ 52 52 53 55 57 58 63 5 Fault-Tolerant Planar Switching Networks 5.1 Planar Networks ^ 5.2 A Lower Bound on the Degree ^ 5.3 A Fault-Tolerant Planar Rearrangeable Network ^ 5.4 A Fault-Tolerant Superconcentrator ^ 72 72 75 76 80 6 Related Graph Theory and Combinatorics Results 6.1 Edge-Disjoint Paths in a Tree ^ 6.2 Vertex-Disjoint Paths in a Planar Graph ^ 87 87 102 7 Bibliography 103 v List of Figures 1.1 An N x M crossbar ^ 1.2 A Bend network with 16 inputs and 16 outputs ^ 1.3 An interconnection network in a parallel computer ^ 2 3 9 2.1 A Bend network with 8 inputs and 8 outputs (edges are direct from left to right) 19 2.2 Non-blocking network N+ with 4 inputs and 4 outputs (edges are directed from left to right) ^ 20 3.1 A d x d crossbar ^ 36 3.2 A network built from 2 x 2 crossbars and its acyclic directed graph representation 38 3.3 A series-parallel network with d = 2, k = 3 and 1 = 5 ^ 38 3.4 Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 5 ^ 41 3.5 Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 6 ^ 45 4.1 A bad leaf ^ 4.2 An internal node collects at most 6 dollars ^ 4.3 Each path collects at most 4 dollars from unlucky leaves ^ 4.4 A (4, 8)-directed grid ^ 4.5 Network N ^ 60 60 61 64 66 5.1 The planar (c, 5)-rearrangeable n-network N ^ 5.2 The planar (E, 5)-n-superconcentrator M ^ 77 82 6.1 T of the xo, x 1 , x2, x 3 and x 4 kind ^ 6.2 Tree T1 for r(3, 3) ^ 6.3 Tree Ti ÷ i for r(3,3) ^ 6.4 Tree T1 for r(3, 2k + 1) ^ 6.5 Tree Ti+i for r(3,2k+ 1) ^ 6.6 Tree Ti for r(3, 2k) ^ 6.7 Tree Ti +i for r(3, 2k) ^ 6.8 Tree T1 with h = 2k + 1 and odd d ^ 6.9 Tree Ti..F1 with h = 2k + 1 and odd d ^ 6.10 Tree T1 with h = 2k + 1 and even d ^ 6.11 Tree Ti.fi with h = 2k + 1 and even d ^ 89 91 91 93 93 95 95 96 97 97 98 vi 6.12 Tree T1 with h = 2k and odd d ^ 6.13 Tree Ti+i with h = 2k and odd d ^ 6.14 Tree Ti. with h = 2k and even d ^ 6.15 Tree Ti +1 with h = 2k and even d ^ vii 98 99 99 100 Acknowledgements I am greatly indebted to my supervisor, Nick Pippenger. His deep insight and inexhaustible mathematics tools are the constant impetus of this thesis. He not only supervised the production of my thesis, he also taught me ways of doing research in Computer Science. He has done more than usual one could ask of a supervisor. He made time to listen to me and discuss his ideas with me whenever I asked for it — no matter how tight his schedule is; he taught me how to present the results — from writing papers to giving seminars. His influence on me is far beyond my thesis. I am very fortunate and proud of being his student. I can not thank him enough. I owe special thanks to Maria Klawe. She has been paying significant attention to every aspect of my professional development. Of course, as a member of my supervisory committee, she is attributed for many technical improvements of this thesis. For instance, she helped me to improve results in Theorem 6.1 of Chapter 6. I would like to thank other members of my supervisory committee, Richard Anstee, Jack Snoeyink, and especially David Kirkpatrick, not only because they provided useful comments and suggestions concerning my thesis, but also for the numerous discussions that have leaded me to a deeper understanding of Combinatorics and the Theory of Computation in general. I would also like to thank Bruce Maggs for productive discussions and suggestions, on both research results and the presentation of this thesis. For example, discussions with Bruce resulted in upper bounds in Chapter 4. Many other people have contributed to the development of this thesis. Thanks go to Aditi Dhagat, Feng Gao, Michelangelo Grigni, Prabhakar Raghavan, Paul Seymour and Alan Wagner. Financial support was provided by the University and the Department through Graduate Fellowships, Scholarships and Assistantships, and I acknowledge them for this regard. I thank all members of the department — staff, faculty and fellow students — who made the department a great place to work and study, and my past years at UBC very enjoyable. I am grateful to my parents and brother, whose constant encouragement and support are essential to the completion of this thesis. Finally, I can not express in words my love to my wife Ying. Without her endless love and support, none of these would have been possible. viii Chapter 1 Introduction 1.1 Communications and Switching Networks Fast and efficient communications are essential to the success of large-scale multiprocessor parallel systems, distributed processing systems, and telecommunication systems. In massive multiprocessor parallel computers, simultaneous communications among processors or between processors and memory modules are fundamental to achieve large-scale parallelism. In distributed processing systems, vast numbers of messages are exchanged across the systems to coordinate the physically distributed processing components. In telecommunication systems, large amounts of voice, data and video are communicated simultaneously between subscribers. In each case, the essence of the communication problem is to provide efficient communications between two sets of devices, one called inputs and the other called outputs. The communication between inputs and outputs is accomplished by switching networks, which consist of a collection of linking elements (links) and a collection of switching elements (switches). A link is capable of transmitting digital or analog signals. A switch has two states, on and off When a switch is in the "on" state, it establishes a communication path from one 1 CHAPTER 1. INTRODUCTION ^ 2 link to another (carries signals from one link to another). An input communicates with (sends signals to) an output via such paths of links and switches. Conceivably one can fully connect N inputs with M outputs by an N x M crossbar (see Figure 1.1). In a crossbar, each input or output is connected by a link, and each crosspoint is N inputs Figure 1.1: An N x M crossbar a single-pole single-throw switch. Each pair of an input and an output can communicate via their "private" switch, regardless of the status of other switches. The difficulty with crossbar networks is the cost (measured by the number of switches). An N x M crossbar contains NM switches. Therefore a crossbar in a parallel computer connecting 2 10 processing units with 2 10 memory modules will require 2 20 switches. This scheme is also inflexible to the addition of new inputs and outputs. A practical connection scheme is the multistage switching network. In such a network, switching components with a fixed number of inputs and outputs are placed in a number of stages, and connected by links. For example, a switching network (due to Bene§ [B64]) with CHAPTER 1. INTRODUCTION^ 3 2 log 2 N — 2 stages and 4N(log 2 N —1) (single-pole single-throw) switches provides simultaneous one-to-one communications between N inputs and N outputs (see Figure 1.2). This scheme has a recursive construction, which makes it easy to accommodate more inputs and outputs (that is to say, a network with a larger number of inputs and outputs can be constructed from a set of similarly structured networks as components, with each having a smaller number of inputs and outputs). --t a 2x2 crossbar ^ a link Figure 1.2: A Bend network with 16 inputs and 16 outputs 1.1.1 Complexity Aspects of Switching Networks Switching networks provide fast and efficient communications at reasonable cost in large-scale systems. The theory for the construction of switching networks concerns (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) — these CHAPTER 1. INTRODUCTION^ 4 complexity measures reflect the cost, communication delay and wiring complexity of the networks; (b) the complexity of the routing algorithms of the networks, such as the time and space — after all, it is the routing algorithm that establishes the communication paths and ultimately determines the performance of the switching; and (c) the fault-tolerance of the networks. 1.2 Circuit Switching and Packet Switching There are two fundamental ways which a switching network may accomplish the simultaneous transmission of messages. They are usually referred to as "circuit switching" and "packet switching". In circuit switching, simultaneous disjoint end-to-end circuits (transmission "routes" or "paths" of links and switches from inputs to outputs) are established to accommodate communication requests. Messages move through these paths without interference with each other. These paths may be dissolved later after the communication requests are satisfied, and their constituent components used to establish other paths. In packet switching, messages are partitioned into "packets". Packets are carried through the switching network in a "store-and-forward" fashion, that is, they may be stored temporarily at some intermediate destination and later forwarded to avoid interference, or they may be discarded and later resent in the case that interference occurs. Because of this store-and-forward nature, in packet switched networks, each switch is associated with a queue (also known as a buffer) to temporarily store the passing messages. 1.2.1 Circuit Switching Circuit switching is efficient in the case where the time scale of establishing the communication paths is considerably shorter than that of the transmission along the paths. Since a circuit CHAPTER 1. INTRODUCTION^ 5 switched network uses dedicated transmitting paths and does not temporarily store messages, it has better performance as regards the communication delay time. For this reason, today's real-time telecommunication systems are universally of the circuit switched type, although there is great interest in the possibility of transmitting voice in real-time in packet form. In telecommunication systems, large amounts of data, voice, and video are transmitted over dedicated paths. (See Briley [B83], Keiser and Strange [KS85], Schwartz [S87] and McDonald [M90] for a detailed coverage on telecommunication systems.) Besides telecommunication systems, circuit switching is also used in some parallel architectures. The circuit switching technology can be implemented in the time division multiplexing or the space division multiplexing form, or some combinations of the two. In space division multiplex- ing, the end-to-end circuits (transmission paths of links and switches) for different messages are accomplished by physically disjoint paths of links and switches. In time division multiplexing, a unit of time is divided into a fixed number of time slots. Different messages may possess a physical link at different time slots during their transmission. Messages do not interfere with each other, because their transmitting paths (circuits) are disjoint at any given time slot. See Chapter 11 of Keiser and Strange and Chapter 5 of McDonald for a full explanation. For the theoretical study in this thesis, however, there is not much difference. We shall only consider space division. 1.2.2 Packet Switching Packet switching has received considerable attention in the past. Many parallel computers use packet switching to support interprocessor communications. (See Section 1.3 for more details.) CHAPTER 1. INTRODUCTION ^ 6 It is also widely used in computer communication networks. The Local Area Network (LAN) is an example. (See Bertsekas and Gallager [BG87], Stallings [St85] and Tanenbaum [T89] for a detailed study of computer communication networks.) 1.3 A Historical Overview Switching networks have been studied for a long time, well before the occurrence of modern electronic digital computers. They date back to the late 19th century, when the telephone was invented. Early works studied telephone switching problems concerning steams of calls arriving with certain probabilistic distributions. See Engset [En18] and Erlang [Er18], for example. The development of the modern theory of switching networks was fueled by efforts from three distinct communities: the telephone switching community, the parallel computer architecture community and the Boolean circuit complexity community. The impulse from the telephone switching community came after the introduction of the first crossbar-type electromechanical switch in 1938. Shannon [S50] showed fundamental results in telephone switching concerning the size of some telephone networks. Clos [C53] introduced the non-blocking network, and presented the first multistage construction for non-blocking networks from simple crossbars (i.e., crossbars with a fixed number of inputs and outputs). In a nonblocking network, a communication request to establish a path from an input to an output may arrive at any time, and must be satisfied without disturbing previously existing communication paths in the network. On the other hand, if the network can satisfy the request by rearranging the existing paths (still maintaining the communication for these existing pairs, but through CHAPTER 1. INTRODUCTION^ 7 new paths), then the network is called a rearrangeable network. From automatic telephony's perspective, a rearrangeable network and a non-blocking network can simultaneously carry a number of calls equal to the number of inputs or outputs originated in any sequence, with or without the rearrangement of the existing paths. If the simultaneous connection capacity of a network for an arbitrary sequence of calls is less than the number of inputs or outputs, then the network is called blocking network. To determine the blocking probability in such a blocking network is inherently complex. The probability of a link occupied at a given time depends not only on other links in the path, but also on many other factors, such as the network operating policy. Lee [L55] and Le Gall [L56] used a simple approximation model, assuming the occupancy probability of each individual link is independent of others, and analyzed the blocking probabilities of some multistage blocking networks with simple constructions. To construct non-blocking networks (including rearrangeable networks) with small size and depth and to build blocking networks with simple topology and small blocking probability are the main goals in telephone switching community. Later works on non-blocking networks and rearrangeable networks were given by Bend [B64], Cantor [C71], Pippenger [P73], Bassalygo and Pinsker [BP74], Pippenger and Yao [PY82], Feldman, Friedman and Pippenger [FFP88], Arora, Leighton and Maggs [ALM90], Lin and Pippenger [LP91]. While all these works focused on the construction of the networks, making the size and depth smaller, the recent ones (Arora, Leighton and Maggs, and Lin and Pippenger) paid attention to routing algorithms as well. In designing multistage networks with simple configurations and analyzing their perfor- CHAPTER 1. INTRODUCTION^ 8 mance, Ikeno [159] used the approximation model of Lee and Le Gall, and determined the limiting value of the blocking probability for a family of networks known as series-parallel networks. Ikeno also introduced another family of networks known as spider-web networks, and conjectured that spider-web networks have a smaller blocking probability. Takagi [T68] described a class of networks called rhyming networks, which include series-parallel networks and spider-web networks. He showed that among rhyming networks, the spider-web networks have the smallest blocking probabilities. He did not, however, determine the blocking probabilities of the spiderweb networks (or its limit) in the general case. Pippenger [P92] succeeded in determining the performance of switching networks under Lee's probabilistic traffic model. Pippenger has two contributions. First, he showed that the limiting value of the blocking probability conjectured by Ikeno [159] is actually achieved by spider-web networks, thus settling Ikeno's conjecture. Second, he proved that this limiting value is optimal among all networks containing the same crossbars arranged in the same number of stages, but for which the interconnection pattern may be arbitrary. Other significant results include Koverninskif [K75], Pippenger [P75], Chung and Hwang [CH77] and [CH80], and Pippenger [P91]. The papers [K75] and [P75] independently proposed similar approximation models which are more precise (and not surprisingly, more complex) than Lee's model. Pippenger [P91] showed an analogous result to that in [P92] under these models. Switching networks constructed from unreliable switches have also been discussed. Moore and Shannon [MS56] described networks that are resilient to random-switch failures. Another contribution to the development of switching networks comes from the parallel CHAPTER I. INTRODUCTION computer architecture community. In multiprocessor parallel computers, data values and control signals are communicated among multiple processors and memory modules via switching networks (also known as interconnection networks). Figure 1.3 schematically illustrates the interconnection network among processors and/or memory modules. Switching Network Figure 1.3: An interconnection network in a parallel computer A tremendous amount of effort has been devoted to the design of switching networks to support efficient interprocessor communications. Networks such as the omega network (see Lawrie [I,75]), the hypercube (see Squire and Palais [SP63], and Sullivan and Bashkow [SB77]), banyan networks (see Goke and Lipovski [GL73]), the butterfly (see Crowther et al [CGG+85]), and the multibutterfly (see Upfal [U89] and Leighton and Maggs [LM89]) have been presented. These switching networks are employed in various parallel computers. For instance, the Connection Machine CM-2, the Intel iPSC, and the FPS T-Series use hypercube-type interconnection net- CHAPTER 1. INTRODUCTION^ 10 works; the IBM GF-11 uses a three-stage shuffle-exchange-type interconnection network; and the BBN Butterfly uses a butterfly-type interconnection network. Routing algorithms in interconnection networks have also been studied. For interconnection networks of parallel computers, the routing algorithms mostly focus on how to packet-route an arbitrary permutation between N inputs and N outputs of the network. Valiant [V82] presented a randomized algorithm, which with a high probability routes any permutation of N packets in O(log N) steps in an N-node hypercube with queues of size O(log N) at each node. Aleliunas [A82], Upfal [U82], Pippenger [P84], and Ranade [R871 presented randomized algorithms that route (with high probabilities) any permutation on a butterfly of N inputs and N outputs in O(log N) steps, with the size of the queues decreased from O(log N) (Aleliunas and Upfal) to 0(1) (Pippenger and Ranade) and the random bits used reduced from 0(N log N) (Aleliunas, Upfal and Pippenger) to 0((log N) 2 ) (Ranade). The routing algorithms for butterflies are also applicable to a broad range of variants of the butterfly, such as the omega network and banyan networks. Upfal [U89], and Leighton and Maggs [LM89] presented deterministic algorithms to packet-route any permutation on a multibutterfly of N inputs and N output, in O(log N) steps using queues of size 0(1). The third motivation for studying switching networks is to obtain lower and upper bounds for Boolean circuits. The research on the superconcentratoris an example. In an n-superconcentrator, there are n vertices called inputs and n other vertices called outputs. For every 1 < k < n, every set X of k inputs and every set Y of k outputs, there exists a configuration containing k vertex-disjoint paths joining X to Y. The superconcentrator was first introduced by Aho, Hoperoft and Ullman [AHU74], with the hope of establishing a nonlinear lower bound CHAPTER 1. INTRODUCTION^ 11 for the Boolean circuit complexity of multiplication. Valiant [V75] showed an 0(n) size and 0((log n) 2 ) depth upper bound — this dashed the hope of establishing a nonlinear lower bound for multiplication via superconcentrators. Pippenger [P77] improved Valiant's result, showing a construction with 0(n) size (with a smaller constant) and O(log n) depth. Other important results include Pippenger [P82B], and Dolev, Dwork, Pippenger and Wigderson [DDPW83]. (These results concern superconcentrators with limited depths.) Despite the failure for their original purpose, superconcentrators turned out to be central in a number of communication networks. For instance, superconcentrators provide support for the Task Queue Scheme [C88] in parallel computing. Another example is the expander. Expanders are essential in establishing the upper bounds for the complexities of some Boolean circuits and algorithms. See the sorting networks of Ajtai, Komi& and Szemeredi [AKS83a] and [AKS83b], and routing algorithms of Leighton and Maggs [LM89], and Arora, Leighton and Maggs [ALM90] for example. Pinsker [Pins73] proved the existence of linear size expanders by using a probabilistic argument. Shortly thereafter, Margulis [M73] showed an explicit construction for expanders. In his construction, however, the constant in the linear bound is shown by an existence proof. Finally, Gabber and Gall [GG81] gave an explicit construction with an explicit constant in the linear bound of the size. Later important results include Lubotzky, Phillips and Sarnak [LPS88] and Margulis [M88]. These results all contribute to the construction of non-blocking networks with small size and depth. CHAPTER 1. INTRODUCTION^ 12 1.4 Thesis outline 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. In Chapters 2 and 3 we consider routing algorithms for switching networks. Chapter 2 presents a first simultaneous "weakly optimal" solutions for the explicit construction of nonblocking 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. Chapter 3 considers routing algorithms for blocking networks with probabilistic traffic. We present an optimal routing algorithm for series-parallel networks (which includes a broad range of useful interconnection networks for parallel architectures, e.g., butterflies and Bene§ networks). The algorithm has an asymptotically minimum expected time complexity among all routing algorithms. Chapters 4 and 5 discuss fault-tolerant switching networks under a random switch failure model. In Chapter 4, we prove lower bounds for the size and depth of fault-tolerant nonblocking networks, rearrangeable networks and superconcentrators. And we explicitly construct such networks with optimal sizes and depths. In Chapter 5, we consider fault-tolerant planar CHAPTER 1. INTRODUCTION^ 13 switching networks, which are attractive because of the rapid advances in VLSI technology. We prove lower bounds for the degree (of vertices) of fault-tolerant planar rearrangeable networks and superconcentrators. And we construct such fault-tolerant planar networks with optimal sizes and degrees. Chapter 6 presents some graph theory and combinatorics results obtained in the course of this research. We consider the problem of how many pairs of leaves can be connected by edge-disjoint paths with a certain length in a given tree. We discuss the ratio of the maximum number of such paths to the number of leaves. We describe this value as a function of the minimum degree d of internal nodes and the maximum length 1 of the paths. We show lower bounds and upper bounds of this value. In particular, we determine this value in the special case where d = 3 and 1 = 3. We also present a result on vertex-disjoint paths in planar graphs. Given a set of ordered vertices v 1 , • • • , vk, uk, • • • , u 1 on the boundary of the exterior face of a planar graph, we give necessary and sufficient conditions for the existence of k vertex-disjoint paths vi uk (for i = 1, • • -,k). Results described in Chapter 2, 4 and 5 have been presented earlier in [LP91], [PL92] and [L92], respectively. Chapter 2 Routing in Non-blocking Networks 2.1 Non-blocking Networks Non-blocking networks were introduced by Clos [C53] in 1953, although related work dated back to Shannon [S50] in 1950. Non-blocking networks have many applications in communications. Typical examples are telephone switching networks and communication networks among processors or between processors and memory devices. Definition 2.1 Let G be an acyclic directed graph G with a set of n distinguished vertices called inputs and a set of n other distinguished vertices called outputs. G is a non-blocking n-network if, given any set of vertex-disjoint direct paths from inputs to outputs, and given any input and any output not involved in these established paths, a new path that is vertex-disjoint from the established paths can be found from the requesting input to the requesting output. The interpretation of non-blocking networks in the context of automatic telephony and circuit-switching networking is evident. Let us agree that vertices represent the connecting elements, i.e., "links", and edges between pairs of vertices represent the switching elements, i.e., "switches", between the pairs. Non-blocking networks can provide any number of simultaneous 14 CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 15 paths of communication at any time, without ever disturbing existing communication paths in the network. The most frequently applied measures of complexity for non-blocking networks are the "size" (the number of edges) and the "depth" (the largest number of edges on any path from an input to an output). These measures reflect the cost and communication delay of the network. An extensive literature exists concerning the design of non-blocking networks, minimizing the size and depth (or some combination of them) as functions of the number of inputs and outputs. Shannon [S50] showed that any non-blocking n-network must have size at least S2(n log n). Pippenger and Yao [PY82] improved the lower bound, showing that any non-blocking n-network with depth k must have size at least 51(n 1 + 1 /k) (k(n 1 + 1 /k) to be exact). Concerning construction of the networks, Clos [C53] discovered non-blocking n-networks with 0(n 1 + 1 /i) size and 2j — 1 depth. Cantor [C71] constructed non-blocking n-networks with 0(n(log n) 2 ) size and 0(log n) depth. Bassalygo and Pinsker [BP74] showed the existence of non-blocking n-networks with O(n log n) size and O(log n) depth. This result later yielded an explicit construction of non- blocking n-networks with O(n log n) size and 0(log n) depth through the work of Margulis [M75] and Gabber and Galli [GG81]. Feldman, Friedman and Pippenger [FFP88] recently presented results on wide-sense non-blocking networks. See Pippenger [P82] for an introductory account and [FFP88] for more recent references. In this chapter we shall combine this concern for depth and size with concern for the time taken by an algorithm that finds the routes guaranteed by the non-blocking property, and for the space taken by the data-structure used by the algorithm. Unlike the case of depth and size CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 16 alone, not much progress has been made in this setting. An exception is that Arora, Leighton and Maggs [ALM90] found an on-line O(log n) steps parallel path selection algorithm for nonblocking networks of size 0(n log n) and depth O(log n). Their proposal, however, assumes that the number of processors is proportional to the size of the network, irrespective of the number of transactions being processed. Our approach, in contrast, uses only one processor for each transaction, even if this number is as small as one. (Simply counting processors is not entirely fair: the processors in [ALM90] are finite-state automata located at the switches of the network, whereas the processors in this chapter are more complicated. On the other hand, the network of [ALM90] is based on a randomized construction, whereas the network of this chapter has a simple explicit construction. Neither of these results subsumes the other.) In this chapter, we explicitly construct a scheme in which non-blocking networks with n inputs and n outputs have size O(n(log n) 2 ) and depth O(log n). And we present on-line parallel algorithms to control them. The algorithms use time and space within one or more factors of log n of the smallest possible values that any control algorithm (on-line or off-line, parallel or serial) may use. More precisely, we present an on-line deterministic algorithm that uses O((log n) 5 ) steps to process any number of transactions in parallel (with one processor per transaction), maintaining a data structure that use 0(n(log n) 2 ) words, and we present an on-line randomized algorithm that uses 0((log n) 2 ) expected steps to process any number of transactions in parallel (with one processor per transaction), again maintaining a data structure that use 0(n(log n) 2 ) words. (The meanings of "step", "word" and "transaction" will be explained in next paragraph). CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 17 Consider a non-blocking network with n = 2" inputs and n = 2" outputs. Any routing algorithm that controls the network must be able to find out the state of the network. An obvious approach would be to let the network itself perform this function, and to let the algorithm make "queries" to the network to find out which vertices are busy, as well as "updates" to change the set of busy vertices. While this approach is successful in restricted circumstances, our most satisfactory results take a more general approach in which the data-structure is separated from the network. This allows the data-structure to contain redundant information about traffic in large parts of the network, and to maintain this information incrementally, without having to recompute it from scratch for each transaction. In fact, we consider the routing algorithm and its data-structure together as an "on-line transaction processing system", in which each "batch" of transactions (requests to establish a route and requests to abolish a route) must be processed before its successors are known, and each transaction affects and is affected by only a small portion of the data-structure, rather than as an "off-line system", for which time requirements would always exceed space requirements. Furthermore, for a batch of t transactions, which are to be processed in parallel, only t processors are allowed to be used. In other words, our approach assumes each transaction "brings its own processor", a setting convenient in situations where routing is but one part of a larger process, and the number of processes simultaneously engaged in routing is not easily predictable. The model of computation that we shall use is the "Parallel Access Computer" or "PRAC", introduced by Lev, Pippenger and Valiant [LPV81]. We shall assume that inputs and outputs are represented as binary words of length v and a "processor" is able to perform arithmetic and logical operations on such words of length v. We CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 18 reckon "time" in such operations, and "space" in such words. If a non-blocking network has n inputs and an equal number of outputs, any algorithm that controls the network must use Si(1) steps to process a batch of transactions, and the datastructure for it must have St(n) words (or their equivalent), since this much space is needed to represent one of n! bijections between inputs and outputs. Our results provide the first simultaneous "weakly optimal" solutions for the explicit construction of non-blocking networks, the design of algorithms and data-structures. "Weakly optimal" is in the sense that all measures of complexity (size and depth of the network, time for the algorithm, space for the data-structure and number of processor-time product) are within one or more factors of log n of their smallest possible values. Our solutions are practical in the sense that the construction of the networks is simple and the algorithms (both the randomized and the deterministic one) and their data-structures are easy to implement. Our main result in this chapter is summarized in the following theorem. Theorem 2.1 There is an explicit construction for a non-blocking network of n inputs and n outputs with size 0(n(log n) 2 ) and depth 0(log n), and a deterministic on-line parallel algorithm that maintains a data-structure using O(n(log n) 2 ) words and will, for any t in the range 1 < t < n, process t transactions using t processors in 0((log n) 5 ) steps. In next section we describe the family of non-blocking networks to which the parallel algorithms and data-structures apply. We present the randomized algorithm in Section 2.3. In section 2.4, we describe the data-structure of the deterministic algorithm. In Section 2.5, we CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 19 use the derandomization technique from Luby [L88} to eliminate the randomization and present the deterministic parallel algorithm. 2.2 The Networks Suppose that we wish to construct a non-blocking network with n = 2" inputs and n outputs. Set -y = Llog 2 (4v)J, so that 2 1 + 1 > 4v > 21 . Construct a Rene§ network with m = 2 11 +1 inputs and m outputs (see Elena (l364]). (Roughly speaking, a Rene§ network with m inputs and m outputs consists of two back-to-back butterflies with m inputs and m outputs. See Figure 2.1 for example.) :10.k^#1.1 2 Mra Danat rAdOM A. X : -.. LWACOUSEPRIM ' WAraff^VW' a el■AlLw^wralVAlh Figure 2.1: A Bene§ network with 8 inputs and 8 outputs (edges are direct from left to right) In the Bene§ network, the vertices are in 2(7 + -I- 1 stages numbered from stage 0 to stage 2(7 -I- v), with the inputs in stage 0 and the outputs in stage 2(7 -I- v). Each stage contains 2 1'+" vertices, and all edges are from stage i to stage i 1 (i = 0, • • •, 2(7 + v)). Now reduce the number of inputs and outputs in this network to n by retaining only every 2/-th input and output and discard vertices and edges that can not be reached from these n inputs and n outputs. This is done so that routes originating at two distinct retained inputs can meet only at or after the (y -I- 1)-st stage, and similarly for retained outputs. CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 20 Let N+ denote the resulting network (see Figure 2.2). This network is non-blocking as shown in [P82]. Figure 2.2: Non-blocking network N+ with 4 inputs and 4 outputs (edges are directed from left to right) Given a set of vertex-disjoint direct paths from inputs to outputs, say a vertex in N+ is idle if it is not involved in these paths, and busy otherwise; say a vertex 6 6 has access to another vertex if there is a path of idle vertices from i to 4.2. Given any idle input of N+, Pippenger [P82] showed that it has access to at least (21+1 - v)2v -1 of the 2"-Y vertices of the (y + v)-th stage regardless the status (idle or busy) of other inputs. A similar property holds for any idle output. Notice that (r+ 1 - 02' 1 is strictly more than half (to be exact, three quarters) of 2 -Y+Y. Thus given any idle input and idle output, a route from the input to the output that is disjoint from the established routes always exists regardless the status of other inputs and outputs. This network has size 0(v2" 1. ) = 0(v 2 2") = O(n(log n) 2 ) and depth 0(7 + v) = O(log n). This network is essentially equivalent to the one described by Cantor [C71]. CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 21 2.3 A Randomized Parallel Algorithm In this section, we describe a randomized parallel algorithm which processes a batch of transactions in parallel with O((log n) 2 ) expected steps by dynamically changing a data-structure of O(n(log n) 2 ) words. Our deterministic parallel algorithm is obtained by eliminating randomness from this algorithm. The data-structure for our randomized algorithm is very simple. It keeps only the up-to-date busy/idle status for each vertex of the network. We describe the data-structure in terms of a directed graph G that is isomorphic to N+. For each vertex of the network N+, we create a node in G. Two nodes in G are adjacent if and only if their correspondents in N+ are adjacent. With each node C in G, we associate a number G((), which is 0 or 1 according as its corresponding vertex in N+ is idle or busy. (The reason that we distinguish G from N+ is that we want to use G to refer to the data-structure and N+ to the network). It is clear that the data-structure uses 0(n(log n) 2 ) words. Notice that N+ has 2(7 + v) stages. The subnetwork of stage 7 + v to stage 2(7 -I- v) is a mirror image of the subnetwork of stage 0 to stage 7 + v. We refer the former to "the right-hand half of N+" called N' and the latter to "the left-hand half of N+" called N. We observe that, for each input e of N+, confined to N, the subgraph of vertices that may appear in some path starting from e forms a tree Ti. Similarly, for each output y of N+, there is a tree Tn . It is clear that all Te's and Tn 's are complete binary trees having depth -y + v with 2 -r+" leaves. We call the common topological structure of these trees T. CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 22 Suppose that a batch of t transactions (requests to establish or abolish a route) are to be processed by t processors (each transaction "brings its own processor"). We need not worry about interference between requests that establish routes and requests that abolish routes by the simple device of splitting each batch into two batches, one comprising only requests to establish and the other comprising only requests to abolish. As we will see, the algorithms presented in this chapter to process requests to establish are well suited to process requests to abolish, thus we shall only consider requests to establish here. We now proceed to describe our randomized algorithm. Suppose that when a processor attempts to establish a route from input e to output 77, it pushes two pebbles in T4 and T,7 respectively from their roots to a common leaf a along a path P. In the randomized algorithm, each processor independently chooses one of the 2 14 '1 possible leaves a, i.e., one of the 2 1'+' possible paths P at random, and then determines whether or not the two subroutes (in N and N' respectively) corresponding to the subpaths in 7'4 and T,, are both idle (this includes checking whether or not any other processor in the same batch has seized a vertex in the subroutes). If both are idle, the route is established and the data-structure is updated. For those that fail to choose an idle path, do the same procedure again, and so forth, until all requests are satisfied. In order to update the data-structure to reflect the addition of new routes to the state, the processor that establishes the route sends two bubbles back from a to e and ri along the corresponding paths in T4 and T,i respectively (7' and T,7 are embedded in G). It changes the value G(C) (from 0) to 1 for each node C that the bubbles encounter. Proposition 2.1 The randomized algorithm maintains a data-structure of O(n(log n) 2 ) words CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 23 and for any t in the range 1 < t < n, processes t transactions in parallel using t processors in 0((log n) 2 ) expected steps. Proof. Consider an arbitrary processor, which chooses one of the 2 1'+' possible paths at random. The probability that the corresponding subroute in N is busy is at most 1/4, since every idle input in N has access to at least (2 141 - v)2 11-1 of its 2 14 ' outputs (vertices in the middle stage of N+) regardless the status of other inputs, and 4v < 2 141 . Similarly, the probability that the subroute in N' is busy is at most 1/4 too. Thus the probability that both subparts of the route are idle is at least 1/2. Therefore, with randomly chosen paths, at least half of the requests are expected to be satisfied. At most t2 -1 requests are expected not to be satisfied after i-th round of choosing. Thus the expectation of such i when t2 -i = 1 is at most log 2 t = O(log n). On the other hand, determining whether or not paths are idle (including no other processors in the same batch having seized a vertex in the path) and updating the data-structure to reflect the addition of new routes are performed with O(log n) parallel operations, since each route is of length 2(7 + v) +1 = O(log n) and G is of bounded degree (the maximum degree is 4). Thus the parallel randomized algorithm establishes (and/or abolishes) t transactions using t processors in 0((log t)(log n)) = 0((log n) 2 ) expected steps. A 2.4 The Data-structure for the Deterministic Parallel Algorithm In this section, we extend our simple data-structure for the randomized algorithm to support an efficient deterministic parallel algorithm. Roughly speaking, we maintain some redundant information about the distribution of established routes, so that we can save some computation CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 24 by retrieving the redundant information. For each pair of inputs e i and e2, we say their distance, dist(ei,.2) = dist(e2,6), is d (1 < d < v) if the routes starting from the two inputs may share a vertex at or after the (d + 7)-th stage but cannot share any vertex before the (d + -y)-th stage. Similarly, we define the distance dist(711,7/2) of two outputs 7b and 77 2 . It is observed that, for each input e there are 2" other inputs e' with dist(e,e) = d, for any d with 1 < d < v. A similar result holds for each output. Furthermore, for any inputs e, e' and e", if dist(e,e') = d, then dist(e, E") = d + 6 (6 > 0) if and only if dist(e',e") = d + 6 for any 1 < 6 < v — d. That is to say, if the distance of two inputs is d, then they share the same group of inputs whose distance is d -I- 6 to them. It will be much clearer if we describe the distance relationship among inputs in terms of a binary tree IND. IND is a complete binary tree of depth v with 2' leaves. Let the leaves correspond to the inputs of N+ in the following way. Two leaves are siblings if and only if their distance is 1; two nodes r 1 and r2 at depth 1 are siblings if and only if the distance between leaves in the subtree rooted at r1 and that in the subtree rooted at r 2 is v — 1 +1 (the distance is unique, as observed above). Similarly, the distance relationship among outputs is described in terms of a complete binary tree OUTD. It is observed that two inputs (outputs, resp.) have distance d if and only if their lowest common ancestor in IND (OUTD, resp.) is at depth v — d. In order to obtain an efficient deterministic parallel algorithm, we need to keep some redundant information about the distribution of established routes. The information in the data structure, on the other hand, can not be too redundant, since our algorithm dynamically up- CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 25 dates the data structure to reflect the addition of new routes (and the subtraction of old ones). For any two inputs with distance d, the fate of whether or not the routes starting from them will block each other is determined within the first 7 d 1 stages in N+. Thus for each input e, we confine the route distribution information for inputs with distance d to the first 7 d 1 stages; for inputs with distance d to e, however, we keep their route distribution information as a whole instead of individually. Therefore, for each input e, we keep v complete binary trees, of depth 7 d and having 2 7 +d leaves for 1 < d < v, with each representing the route information of 2 d-1 other inputs (inputs with distance d to E). Associated with each node C in such a tree is a number, counting the number of routes that start from one of the 2d -1 inputs, say e', and pass through the corresponding node of C in Ti '. Thus for each input e, there are v such trees; each input is involved in v such trees and there are 2'41 -1 such trees in total (due to the large amount of overlapping). Similar properties hold for outputs. Our data-structure for deterministic algorithms is precisely described as follows. In addition to the data-structure G of the randomized algorithm, we keep some redundant information about the distribution of established routes. For each node r at depth v - h (with v - 1 > h> 0) in IND, we keep a complete binary tree TR, (TR stands for "traffic"), which is of depth 7 h with 2 7 +h+ 1 - 1 nodes. Recalling the common structure T of Ti's and T,7 's, we see TR., is a subtree of T truncated at depth 7 + h. For each node in TR,, there is a corresponding node Ct in each tree T. Associate with each node in TR, a number TR,('), which is the sum of G(C) (the 0/1 value indicating CC is idle or busy) over every input e which is a leaf in the subtree rooted at r in IND. Similarly, for each node at depth v - h (with v - 1 > h > 0) in OUTD, make a CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 26 complete binary tree Tito, which is of depth 7 + h with 2 14 h+ 1 - 1 node. Associated with each node ( is the value TR,3((), which is the sum of G((, 7 ) over every output n which is a leaf in the subtree rooted at /3 in OUTD (6 1 is the corresponding node of ( in T,,). Let us consider the space requirements of the data structure. Graph G has less than 2(v + 1)2ry÷u nodes, and there is a number (0 or 1) associated with each node. There are 2 . 2" - h nodes r and /3 at depth v - h in trees IND and OUTD. For each r or /3, there is a tree of r+h+1 -1 nodes, and associated with each node is a number (in the range [0,2' - 1]). Thus there are less than u-i. 2(v + 1)2ry+ u +^(2 • 2 v-h )(2 • 2 .y +h _ 1) < 6(v + 1)214v = 0(,22p) = O(n(logn) 2 ) h=0 numbers to be stored. Proposition 2.2 The space requirement of the data-structure for the deterministic parallel al- gorithm is O(n(log n) 2 ) words. 2.5 A Deterministic Parallel Algorithm The elimination of randomization from the randomized parallel algorithm of Section 2.3 is accomplished in two stages. In the first stage we greatly reduce the number of random bits (independent coin flips) used by the algorithm, by deterministically computing a large number of bits from a smaller number. In the second stage we show how to deterministically compute this smaller number of bits. CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 27 In the randomized parallel algorithm, each processor makes a random choice uniformly distributed over 2 14 " possibilities; we may therefore regard it as making y + v successive independent random binary choices, corresponding to the y + v successive moves involved in pushing a pebble from the root to a leaf in T (T is the common structure of trees Tt and T,1 ). We may therefore imagine all of the choices of all the processors as being made in 7 + v successive "phases", with each of the t processors making its first choice in the first phase, and so forth. We next observe that the analysis of the randomized algorithm was based on the assumption that all routes were independently chosen, but actually only relied on the routes being pairwise independent. Thus the analysis will remain valid if the binary choices in each phase are not completely independent, but are pairwise independent. These t pairwise independent bits can be computed deterministically from a set of v = log 2 n completely independent random bits, using the following well-known scheme. Let M be avxt matrix over GF(2) in which each column is a distinct input index of the t requests (input indices are in their binary representations). Let X be a row of v completely independent random elements of GF(2), and let Y be the product XM (a row of t elements of GF(2)). Then the elements of Y are uniformly distributed over GF(2) and pairwise independent (see Luby [L86]). We may thus deterministically compute t pairwise independent bits in Y from the v = log 2 n completely independent random bits in X. Let us now return to the picture of pebbles being pushed from the root to a leaf in the trees Te's and Tn 's. As before, established routes will be replaced by pebbles at the leaves, and each processor is responsible for pushing two pebbles, one in a tree TT and the other in a tree Tn. CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 28 For simplicity of notation, we label the two corresponding pebbles e and 77 as well. Given a disposition of pebbles in these trees, associate with each pebble a quantity called "congestion", defined in the following way. Imagine all pebbles being pushed in T (the common structure of Ti's and Tn 's). If the pebble 6 is at a node cr„ at depth 7c in T and the path from the root of T to cr„ is oo, cri, • • • ,a„, where ao is the root of T, the congestion of 6 is the sum of a contribution of 1/2 14d- '` for every pebble 6' in the subtree rooted at cr„ and with d = dist(6,6')> lc- 7, plus for each node at depth 7 + i on the path from the root of T to c (i.e., node ai,+ i), i = 1, • • • , K for every pebble -y - 1, a contribution of 1 6" in the subtree rooted at (7.7+ i and with dist(6,61') = i. (Quantity 1/2 14 " indicates the possibility of blocked by - 6 being blocked by 6' in later stages; quantity 1 indicates that 6 is E".) This quantity is easy to compute. Consider the 2'1 - 1 inputs other than 6. Based on their distances to 6, they fall into v groups with size 2 d-1 and of distance d to 1 < d < v. Of the inputs in the group of distance d to 6, for 6, their lowest common ancestor in IND is at depth v - d + 1 (recall that inputs correspond to leaves in IND). Let these ancestors be r1 , • • • , i y (ri corresponds the group of inputs with distance i to - the sum of TR,d (crpc )/2 1-1-d- '5 over every d, every d, 1 < d < , - , - 6). The congestion of 6 equal 7 < d < ii, plus the sum of T/i rd (cf-r+ d) over 7 -1. We say that the congestion of a request is the sum of the congestions of its two pebbles, and that the congestion of a batch of requests is the sum of the congestions of the requests in the batch. The success of the randomized algorithm may now be ascribed to three simple observations. Firstly, when all the pebbles of the requests in the batch are at the root of T (n = 0), the CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 29 congestion of a pebble is less than or equal to EL,'1 _, 1 (1/21'+ d )•2 d-1 = v/27 + 1 < 1/4, corresponding to contributions of 1/ 2 1-14 for each of the other pebbles at leaves or at the root. Secondly, if a pebble is moved from a node a to one of its two children (chosen at random with equal probability), the expected congestion of each pebble is unaffected; indeed, each contribution to the congestion is either unaffected or undergoes a "double-or-nothing" transformation with equal probabilities. Finally, when all pebbles are pushed to leaves (K = y + v) , the congestion of a pebble is an integer greater than or equal to 1 if it is blocked, and is 0 if it is not blocked. Therefore, the number of pebbles being blocked is less than or equal to the congestion of the batch of requests. It follows from these observations that on the average, at least one-half of requests finish with both pebbles not being blocked, and are successful. Let us now combine this picture with the notion of phases, so that each processor pushes its two pebbles down one level in their trees during each phase. If all of the binary choices involved in these pushes were completely independent, the expected congestion would be unaffected. Since the congestion is defined as a sum of pairwise contributions, its expectation is unchanged if completely independent binary choices are replaced by pairwise independent binary choices. So let t pairwise independent choices be deterministically computed from v completely independent choices, as described above. Since the expectation over all I/ choices is unaffected, it follows that there is a particular way of making the first choice for which the expectation (over the remaining v — 1 choices) does not increase. After the first choice has been made in this way, there is a particular way of making the second choice for which the expectation (over the remaining v — 2 choices) does not increase. Proceeding in this way, we arrive at particular ways of making all y CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 30 choices, from which we may deterministically compute the t pushes of pebbles. It remains to observe that the "particular ways" whose existence was argued in the preceding paragraph can in fact themselves be deterministically computed in a simple way. For if we assign particular values to some of the v choices, the expected congestion over the remaining choices can be computed as follows. Assigning particular values to some of the choices commits some of the t pebbles to move from the node a at which they began the phase to one of their two children, while leaving the other pebbles equally likely to move to either of their two children (the fate of a particular pebble is sealed when all of the entries of X for which its column of M contains a 1 have been assigned particular values; otherwise, its fate is uncompromised). Thus an advantageous value for a choice can be found by tentatively assigning one value, recomputing the congestions, and rescinding the tentative assignment in favor of its alternative if the congestion increases. By now we have finished the description of our deterministic parallel algorithm. The following lemmas formalize the preceding arguments. Readers who are satisfied with the above arguments may skip over these lemmas to Proposition 2.3. Recall that the pebble being pushed from input e is labelled e as well. Given a vector Z = (zi, • • • , zn,., + i) over GF(2), 0 < m < y + v — 1 and 1 < 1 < v, let 171(Z) be the product (zi., 4. 1 , • , zj.,, + ,)/Iii for j = 1, • • • , m, where M is the binary index of input e, and yin+1(z A if not all entries of 1 in Mc appear in M ) (zin ., + 1, • • • , Z772 •, + 1)M otherwise where M is the vector containing the first 1 entries of Mc. Let P(Z,e) be the corresponding CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 31 position of pebble e (the node 6 resides at) in T, after m + 1 consecutive moves in accordance with 1"?(Z), • • • ,Yr+ 1 (Z) (0 correponds to the move to the left child, 1 to the move to the right child and A to no move). Denote the congestion of 6 at node P(Z, e) by conMZ). Given a vector Z, let IZI be the "size" of Z, i.e., the number of arguments in Z. In particular, if IZI = 0, we mark Z by 0. Given Z = (z1, • • • ,z,,) over GF(2), we denote Z = (z1,- • • ,z,,x) by Zx, where x is an element of GF(2). Lemma 2.1 For any input pebble 6, conMO) < 1/4. Proof. It is straightforward. A Lemma 2.2 For any input pebble 6, any Z = (z1,• • • ,z,,,,÷1) over GF(2), 0 < m < 7 + v — 1 and 1 < 1 < v, and a random variable x uniformly distributed over GF(2), the expectation E[conge(Zx)] = conMZ). Proof. Let x be a random variable uniformly distributed over GF(2). For any input pebble e, we consider two cases, P(Zx, 6) 0 P(Z, f) and P(Zx,6) = P(Z,e) (whether 6 moves one level down or not because of x). When P(Zx,e) 0 P(Z, s), first consider a pebble 6' such that P(Z,e) is in the subtree rooted at P(Z, E) and d = dist(e,e)> K-7, where P(Z, e) is at level K in T. If d> K-7, P(Z, e'') must not be the same node as P(Z, 6) and the expected contribution of e' to conMZx) equals the contribution of 6' to conMZ), because the contribution undergoes a "double-or-nothing" transformation with equal probabilities; if d = K - 7, the contribution of 6' to congjZx) equals that to conge(Z) (remains to be 1) regardless which child 6 moves to. Next consider a pebble 6" such that P(Z, 6") is in a subtree rooted at the node at depth 7 + i CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ 32 from the root of T to P(Z , E) with dist(e, e") = i, i = I,. • • , lc - - 7 —1. The contribution of e" to conMZx) equals that to conMZ) (remains to be 1) regardless which child e moves to. When P(Zx,e) = P(Z,e), it is clear that the contribution of any other pebble E' to congaZx) is the same as that to conMZ). Thus in either case, E[conMZx)] = conMZ). A Lemma 2.3 For any input pebble e, if VI = v(7 + v), conMZ) is an integer greater than or equal to 1 if e is blocked, is 0 if e is not blocked. Proof. It is straightforward. Note when VI = v(7 + v), every input pebble is on a leaf. Similar properties hold for output pebbles. Proposition 2.3 The deterministic algorithm establishes and/or abolishes any number of routes in parallel in O((log n) 5 ) steps with one processor per transaction, maintaining a data structure of O(n(log n) 2 ) words. Proof. The space complexity has been dealt with in Proposition 2.2. For the time complexity, we observe the following facts. Firstly, each time pebbles being pushed to leaves, there are at least one half of the requests being satisfied, which implies flog 2 tl = O(log n) "rounds" of pushing are sufficient to satisfy all the requests. Secondly, within each "round" of pushing, 7 + v = O(log n) "phases" are sufficient to push a pebble from its root to a leaf. Thirdly, in each "phase", v = O(log n) bits in X are deterministically computed, and after each bit is computed, the data-structure is updated. Finally, in order to determine the value of one bit, the congestion of the batch of requests is computed, this is done with O(log n) steps, as the congestion of a pebble is computed in O(log n) steps by one processor (the sum of TR,d (a,c )/2/+d " over every - CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS ^ d, K — 7 < d < v, plus the sum of TR ra (a7+ d) over every d, 1 < d < i - 33 7 — 1), and after the congestion of each pebble is known, the congestion of a batch of requests is computed in O (log n) steps by t processors in parallel; and the update of the data structure after the determination of a bit (committing some of the t pebbles to move to one of their two children) needs 0((log n) 2 ) steps, of which one O(log n) factor comes from the fact that 0(v) = O(log n) numbers in TR,d 's, 1 < d < v, are to be updated (at most two numbers in each TR,d ), and the other comes from the fact that to any one of these numbers, at most 0(t) = 0(n) processors may want to update it simultaneously (with each one adding 1 or subtracting 1). 0 Chapter 3 Routing in Networks with Probabilistic Traffic 3.1 Probabilistic Model and Previous Work In the preceding chapter, we discussed routing algorithms for non-blocking networks. Nonblocking networks guarantee a dynamic linkage between any pair of an idle input and an idle output regardless the current traffic pattern in the networks. In some applications, however, non-blocking networks are impractical due to various reasons, such as high cost and complex wiring topology. Very often then, switching networks are constructed with simple topologies and limited "blocking probabilities". In this chapter, we consider a family of switching networks, known as "series-parallel networks". The basic building blocks of these networks are d x d crossbars. These networks have simple topologies and exhibit a reasonable probability of connection for inputs and outputs. To analyze the performance of these switching networks, one assumes the network is in a "random state" (i.e., the network is operating under probabilistic traffic), and measures the extent of connection of inputs and outputs by the "linking probability". (The meaning of "random state" 34 CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^35 and "linking probability" will be explained in the next paragraph.) A literature exists concerning the analysis of the performance of switching networks under probabilistic traffic assumptions. Lee [L55] in 1955 proposed a simple approximation model to characterize the probabilistic traffic (see also Le Gall [L56]). In this model, each link of the network is assumed to be idle with some probability q (called the "vacancy probability") or busy with the complementary probability p = 1 — q (called "occupancy probability"), independently of all other links. A random state of a network in this model is an assignment of busy or idle status to its links in accordance with the above described probability distribution. The linking probability for a given pair of idle input v and output w is the probability that there is a path from v to w containing idle links only. For the networks we consider in this chapter and for most networks used in practice, this probability is the same for each pair of idle input and output, and thus refers to the linking probability of the network as well. The complementary probability (of the linking probability) is called the blocking probability. Using Lee's probabilistic model, Ikeno [159] in 1959 determined the limiting value of the linking probability for series-parallel networks. Other approximation models proposed include Koverninskif [K75} and Pippenger [P75]. In this chapter, we consider efficient routing algorithms for series-parallel networks with probabilistic traffic. Unlike the situation for the linking probability, there is virtually no nontrivial progress in analyzing efficient routing algorithms for these networks. We shall adopt Lee's probabilistic model, and we assume that the status of a link (busy or idle) remains unknown until it is detected by a "test" operation. We reckon the time by the number of such test operations. We measure the cost of a routing algorithm by its expected time, assuming the CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^36 network is in a random state. We shall present a "depth-first search" type routing algorithm (Depth-First Search Routing) for series-parallel networks. And we shall prove it is asymptotically optimal among all routing algorithms for series-parallel networks. (More precisely, we shall show that it has an expected time within a multiplicative constant lip of the optimal.) 3.2 The Networks We consider switching networks that are constructed from d x d "crossbars" by simple structures. A d x d crossbar has 2d terminals, d called "inlets" and d called "outlets", and d 2 "switches", one for establishing a path between each of the inlets and each of the outlets (see Figure 3.1). The networks we consider have 1 > 3 "stages", each containing dk -1 d x d crossbars, where Outlets 0 0 0 Inlets Inlets 0 0 0 A d x d crossbar ^ 0 0 0 0 0 0 Outlets Another representation Figure 3.1: A d x d crossbar k < 1 < 2k —1. The dk inlets of the crossbars in the first stage are the "inputs" of the network, and the dk outlets of the crossbars in the last stage are the "outputs" of the network. The parameter k is called the "scale" of the network, and 1 is called the "depth" of the network. For 1 < j < 1-1, the outlets of the crossbars in the j-th stage are connected in a one-to-one fashion to the inlets of the crossbars in the (j + 1)-st stage by means of dk links. CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^37 We may represent such a network as an acyclic directed graph in the following way. Inputs, outputs and links are the vertices of the graph. The vertices are partitioned into 1 + 1 classes called "ranks" according to the stages they are associated with (the inputs form the 0-th rank, the outputs forms the d-th rank, and the links connecting the j-th stage to the (j + 1)-st stage form the j-th rank). An edge from a vertex in the j-th rank to some vertex in the (j + 1)-st rank exists if there is a switch (in some crossbar in the j-th stage) providing a path from the former to the latter. In this way, a d x d crossbar is regarded as a directed complete bipartite graph with two disjoint sets of vertices (d inlets and d outlets, respectively) and d 2 edges (switches). The networks we consider are acyclic directed graphs with the following properties. (1) Every vertex that is not an input has in-degree d. (2) Every vertex that is not an output has out-degree d. (3) The existence of edges (v, u), (v', u), and (v, u') implies the existence of the edge (v', u'). (4) Every path from an input to an output has length 1 (that is, contains 1 edges). Conversely, any acyclic directed graph with these four properties can be regarded as a network of the type considered here. (See Figure 3.2.) Hereafter in this chapter, we shall use such an acyclic directed graph to represent a switching network. In a network of scale k and depth 1 (1 + 1 ranks of vertices), we label the vertices in each rank with binary strings of length k over the alphabet {0,1, • • • , d — 1). The positions in each string will be referred to as the 1-st (leftmost) through the k-th (rightmost). Given a network of scale k and depth 1, we say the interconnection pattern between the j-th CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^38 1 2 3 3 2 4 4 A network built from 2 by 2 crossbars^Its acyclic directed graph representation Figure 3.2: A network built from 2 x 2 crossbars and its acyclic directed graph representation rank and the (j 1)-st rank is of type i, for 1 < i < k, if an edge from vertex x in rank j to vertex y in rank j+ 1 exists if and only if the labels of x and y differ at most in the i-th position. A rhyme scheme is a string of length 1 over the alphabet {1, . • • , k}. A network of scale k and depth I is constructed according to the rhyme scheme r 1 • • ri E{1,•••, kV if its interconnection pattern between rank j — 1 and rank j is of type ri, for all 1 < j < 1. The series-parallel network with scale k and depth 1 is the network constructed according to the rhyme scheme 12 • • • k(/ — k)(/ — k — 1) • • .1 (see Figure 3.3). 000 001 010 011 100 101 110 111 000 • .^1.1" / lISSEMPIABOIC1 v 01111.11111111111114 aXeltrA Pl■ ■WevA 11111 1■MIRSTAIL 411101. e e 001 010 011 100 101 110 111 Figure 3.3: A series-parallel network with d = 2, k = 3 and 1 = 5 CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^39 In a network with an input v and an output w, the channel graph from v to w is the acyclic graph comprising those vertices and edges lying on paths from v to w. A network is balanced if any two channel graphs are isomorphic. It is clear that the linking probability in a balanced network is the same for any pair of idle input and idle output. It is obvious that a series-parallel network is a balanced network. (In fact, any network constructed according to a rhyme scheme is a balanced network.) Therefore, for the purpose of analyzing routing algorithms for these networks, we may restrict our attention only to the channel graph instead of the whole network. 3.3 Main Result and the General Strategy We shall show that the routing algorithm for series-parallel networks, Depth-First Search Routing, is asymptotically optimal: the expected time of the algorithm is within a multiplicative factor 1/p of the optimal. Our general strategy is that (1) we transform any optimal routing algorithm into a "restricted form" with at most a 1/p factor increase in the expected time, and (2) we show that in this restricted form, Depth-First Search Routing B is optimal. Step (1) is achieved by recursively rearranging the components of an optimal algorithm. Step (2) is proved by associating the "appearance" of the channel graph at any step of the execution of an algorithm in the "restricted form" with a "potential". (An "appearance" reflects the knowledge that the routing algorithm has about the busy/idle status of the links in the channel graph.) The potential equals 0 for any "final appearance" (the appearance to which a routing algorithm is able to terminate), decreases by a fixed constant c (in expectation) for each step of the algorithm Depth-First Search Routing B, and decreases by at most c (in expectation) for any step of any routing algorithm in the restricted form. It follows that the optimal expected time for CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^40 algorithms in the restricted form is the expected time for Depth-First Search Routing B. We shall initially consider the series-parallel network with 1 = k+1 (the "almost-series" case), since in this special case, step (2) of our general strategy will itself yield the result we desire, thus allowing us to understand the motivation of the "potential" without the complication of other considerations. Furthermore, in this special case, our result is somewhat stronger: we show that a "depth-first search" type routing algorithm (Depth-First Search Routing A on page 31) is optimal, i.e., it has the smallest expected time among all routing algorithms. 3.4 The Almost-Series Case As stated at the end of Section 3.2, routing in a series-parallel network is the same as routing in a channel graph. Given an idle input v and an idle output w, let C(v, w) be the channel graph from v to tv. A routing algorithm will find a path from v to to containing idle vertices only (in short, an idle path), if there is such an idle path, or else a cut that contains busy vertices only (in short, a busy cut) in the channel graph C(v, w). (Note that with the "linking probability" there is an idle path, and with the "blocking probability" there is a busy cut.) In the almost-series case where 1 = k 1, the channel graph C(v, w) for any input v and output to is a set of d chains of length 1 (containing 1 edges) from v to w, disjoint except at the ends (v and w) (see Figure 3.4). Given an idle input v and an idle output w in a series-parallel network N with scale k and depth k + 1, a routing algorithm consists of a combination of tests on vertices of the channel graph (detecting the busy/idle status of the vertices) nested in a control structure. We may CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^41 Figure 3.4: Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 5 view a routing algorithm as a decision tree, in which each internal node is a test, and the two branches correspond to the situations where the vertex is found busy or idle. The test results of the nodes on a path from the root to a leaf in the decision tree include either a busy cut or an idle path of the channel graph. Suppose that a test of a vertex 9 on a chain C of C(v, w). The result of this test is that (a) 9 is found busy (with probability p), so that there is no need to examine any other vertices on chain C, and therefore we may imagine that chain C disappears and the number of chains in C(v, w) decreases by one; or (b) 9 is found idle (with probability q=1 — p), so that the number of vertices in chain C to be examined later decreases by one, and therefore we may imagine that the length of chain C decreases by one. When a routing algorithm runs, the channel graph C(v, w) goes through a sequence of "appearances" (indicating how well the routing algorithm "knows" the busy/idle status of the links). Each appearance is characterized by a set of r (r < their ends (v and w). Let 1 < 11 < 12 < • • • < d) chains from v to w disjoint except I,. be the lengths of these chains (that is, the numbers of edges contained). The appearance of the channel graph C(v, w) is described by the vector (1 1 ,1 2 , • • • ,1,.). Initially, the channel graph is in appearance d chains each containing (12 12 . 22 where there are d 1 edges (in this case, the routing algorithm "knows" nothing about C(v, w) but the probability distribution of the busy/idle status of the links). The algorithm ^1 CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^42 terminates when C(v, w) is in some appearance (1 1 ,1 2 , • • • , 1,.) where 1 1 = 1 (in this case, the routing algorithm finds an idle path) or r = 0 (in this case, the routing algorithm finds a busy cut). As explained in the preceding paragraph, a test on a vertex on j-th chain (the chain with length li) will yield two possible new appearances: (a) appearance (1 1 , • • • , 1j- 1 , 1j +1 , • • • , /,.) with probability p, and (b) appearance (l 1 , • • • - 1, • • • , I,.) with probability q (without loss of generality we may assume ^< /j). Given 1 < 1 1 < 12 < • • • <^we define the potential function on appearance (4,12, • • • , 1r) to be q 12-1^(1 - q 1 1 -1 )(1 - q 1 2 -1 )^(1 - q 11-1 )(1 - q 12-1 ) • • • (1 - ql* -1 ) F(11,12, • • • , 1r ) = ^ 1 — q^1 - q^ 1-q Lemma 3.1 For each appearance (1 1 ,1 2 , • • • ,1 r ) (1 < 11 < 12 < I r and r < d) of the channel graph C(v,w) at which a routing algorithm terminates, we have F(11,12, • • • , 1r) = O. Proof. It is straightforward. Note that in this case 1 1 = 1 or r = 0. A Lemma 3.2 Given an appearance (1 1 ,12,- • • , I r ) (2 < 1 1 < 1 2 < 1r and r < d) of the channel graph C(v, w), if a routing algorithm examines a vertex on the shortest chain (the chain with length l i ), then the expectation of the potential function on the new appearance is F(I1,12, • • • ,1 r )1. Proof. With probability p the new appearance is (12, • •• 1,.), and with probability q = 1- p the new appearance is (4 - 1,1 2 , • • • , 1,.). Therefore the expectation of the potential function on the CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^43 new appearance is = = = pF(I2,• • • ,1r) A- qF(11 - 1,12,• - • ,1r) , 1,412-1^(1-q12-1)...(1_gir-1) \ • • • +^ q^ Pk^1^+ 1-q^If 0. _ q i i -2^o_qii-2)(1_112-1) qk^1-q^4-^1-q 11-1)(i_ q i2-1 ., 1- q 11-1^i^(1_,7^ j + 1-q^.1-^1-q^ F(11,12, • • • ,1 r ) - 1.^A + 0_0. -2 )(1 _ 9 : 2 -1 ) ... (1 -vr-1 )) +^ 1-q (i_qii-1)(i_qt2-1)...0_qtr-i) 1 +^1-q Lemma 3.3 Given an appearance (li,12,• • • ,1r)^< 11 < 12 < Ir and r < d) of the channel graph C(v,w), if a routing algorithm examines a vertex on the j-th chain (the chain with length li) and 11 < 13 , then the expectation of the potential function on the new appearance is strictly greater than F(1 1 ,1 2 ,• • • ,I,.)- 1. Proof. Without loss of generality, we assume that 1j_ 1 < /j. Thus the two new appearances are ••^• • • , 1r) (with probability p), and (b) appearance (4, • • •,/i - 1, • • •,/,) (with probability q). Thus the expectation of the potential function on the new appearance is pF(11,• • • ,li-1, 1J+1,• • • ,10-1- qF(1 1 , • • • ,1; 1-q111^(1-q11-1)...(-q5-1-1) 1-q^ 1-q (1 - q 1 1 -1 ) • • •(1 _ k F(11,12,• • ' ^1 r) - ( 1 > F(11,12, •••, 1r) - q ii -1 ) • + 1-q • • (1 - q 13-1 - 1, • • • ,1,) (1-q1.7-1)...0_qtr-s) 1-q 1) ) 1.^A Lemma 3.1, 3.2 and 3.3 together show that for any appearance (11,12, • • • , 1r), the potential F(I 1 ,1 2 , • • • ,/ r ) is a lower bound for the expected number of tests that any routing algorithm uses before it terminates. In particular, ^1 d = 1 n1-1^(1 — Y 1q - q 1_1)d (1 47 1-1) ( 1 _ q b-s)d (1- g ^^ = ^ 1-q (1 - q)ql -1 q1-1)2^ 1^ + is a lower bound for the expected time of any routing algorithm. Furthermore, Lemma 3.1, 3.2 CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^44 and 3.3 show that the following algorithm (Depth-First-Search Routing A) is an optimal routing algorithm. Depth First Search Routing A - - Repeat the following until C(v, w) is empty or contains a chain of length one Choose a chain C with the shortest length in C(v, w) Examine a vertex u (other than v or w) in chain C If the vertex is busy then delete chain C from C(v, w) else delete vertex u and merge the two edges incident to u Proposition 3.1 Given a series-parallel network with scale k and depth 1 = k 1, the Depth- First Search Routing A is the optimal routing algorithm, with an expected time (1- q 1-1)-(1q 1-1)d (1-q)q 1-1^• 3.5 The General Case For a series-parallel network with scale k and depth 1 (k < 1 < 2k - 1), the rhyme scheme is 12 • • • k(1 - k)(1 - k - 1) • • .1. Given such a series-parallel network N, and given an input v and an output w, consider two distinct paths r and ir' from v to w. Let L denotes the longest common initial segment of r and ir'. Since r and ir' both originate at v, L contains at least v. Since r and r' are distinct, L does not continue as far as w. Suppose the last vertex of L is at rank a - 1. Then r and ir' must differ at rank a, and the labels of their vertices in the a-th rank CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^45 must differ in the a-th position (if 1 < a < k) or in the (1 — a)-th position (if k + 1 < a < 1). Since in the rhyme scheme, the interconnection pattern of type j appears only once, for all 1 — k -I- 1 < j < k, position a must be in the range 1 < a < 1 — k (otherwise z- and ir' will not coincide at w). Since in the rhyme scheme, the interconnection pattern of type j' appears exactly twice, for all 1 < j' < 1— k, paths z- and z-' must coincide at (1— a)-th rank and will not separate again. Therefore, the channel graph C(v, w) comprises two complete d-ary trees T t, and Tw of height / — k with v and w as their roots, connected by 2" disjoint chains of length 2k — 1 from 2" leaves of Tv to 2" leaves of Tw in an identity fashion (see Figure 3.5). Call this structure a 1-folio. (It is in fact characterized by three parameters: the branching factor d, the "parallel depth" 1— k, and the "series depth" 2k — 1. In our manipulation of this structure, however, d and k will remain unchanged.) Call 1 the "depth" of the folio and the two roots of the two comprising trees the "ends" of the folio. Throughout the remainder of this chapter, we shall assume / is even. (The case of odd 1 is similar.) Figure 3.5: Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 6 As in the almost-series case, when a routing algorithm runs, the channel graph C(v, w) goes through a sequence of "appearances": after a test on some vertex 77 is done, we may CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^46 discard a portion of the channel graph (if 97 is found busy) or we may delete 97 and merge the in-edge(s) of 97 to the out-edge(s) of 97. And then we may define some "potential function" on each "appearance" to measure its "closeness" to the "final appearance". Unfortunately, this approach is unsuccessful because an arbitrary "appearance" of the channel graph generated by a routing algorithm is too complex to be characterized by a set of simple parameters, so as to be used as the domain of a "potential function". (One may recall that in the almost-series case, the appearance is characterized by the lengths of a set of chains). However, we are able to show that there is a "restricted class" of routing algorithms, such that the "appearances" of the channel graph generated by these "restricted" algorithms are simple enough to allow the definition of a "potential function", and the expected time of the optimal routing algorithm in this "restricted class" is within a constant factor (i.e., 1/p) of that of the optimal routing algorithm (without any "restriction"). 3.5.1 Routing Algorithms of the "Restricted Class" A routing algorithm of the "restricted class" (denoted by TO is described as a sequence of "moves". At each move, where a set of disjoint folios are given, it always examines the two ends of some b-folio as a pair (that is, examines one end and if it is idle, examines the other end). If one of the two ends is busy, the algorithm discards this b-folio; if both ends are idle, the algorithm breaks this b-folio into d disjoint (b — 1)-folios (if b > 2k —1, that is, the "parallel" part is not empty), or reduces it to a (b — 1)-folio (if b < 2k — 1, that is, the "parallel" part is empty). It is clear that the expected number of tests in a move is 1 + q. Given an idle input v and an idle output w, recall that the channel graph C(v, w) is a set CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^47 of d disjoint (1 - 1)-folios. It is natural to characterize a "appearance" of the channel graph generated by an algorithm in 7Z by a set of disjoint folios. Let 0 < 1 1 < • • • < I, be the depths of these folios, the appearance of the channel graph C(v, w) is the vector (4,12, • • -,1r ). Initially, the channel graph is in appearance (122L-- 1::L,1-2 )-1 where there are d disjoint (1 - 1)- d folios. A routing algorithm in 7Z terminates when the channel graph is in some appearance (1 1 ,1 2 ,• • • ,1,.) where 4 = 0 (in this case, the routing algorithm finds an idle path) or r = 0 (in this case, the routing algorithm finds a busy cut). A move of an algorithm in 7Z at appearance (4,12, • • • , I,.) (operating on the two ends of some 1 .;-folio) will yield two possible new appearances: (a) appearance (4, • • • ,1j-1,1i44, • • • ,1r ) with probability p qp = 1 - q 2 , and (b) appearance (4, • • • , - 1,•••• (if 1.; > 2k -/) or appearance (4, • • • ,lj -1, • • •,1,.) (if < 2k-1) d with probability q 2 (without loss of generality we may assume /j_1 < Given 0 < 4 < 12 < • • • < 1,., define the potential function on the appearance (4,12, • to be H(4, l2, • • • ,1r ) = G( 1 1) + C(4)G(12) C(4)C(12)G(13) + • • • + C(i1) • • • C(1 r _ i )G(4), where {1 + q + q2 G ( x 1)1 i (c4-11 G(x) = )d if x > 2k - I 1+ q -I- q 2 G(x - 1)^if x < 2k - 1 and C(x) = with G(0) = 0 and C(0) = 0. 1 - q2 q 2 (C (x - 1))d if x > 2k 1_ q 2 q 2^( x^1) - 1 if x < 2k - 1, CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^48 Lemma 3.4 For each appearance (11,12,• • •,1 r ) (0 < 11 < 12 < 1,.) of the channel graph C(v,w) at which a routing algorithm in 7Z terminates, we have H( 1111 21 • • • lr ) = 0. Proof. The idea is the same as in Lemma 3.1. Note that in this case 1 1 = 0 or r = 0. A Lemma 3.5 Given an appearance (1 1 ,12 , • • • ,1 r ) (1 < 1 1 < 1 2 < 1,.) of the channel graph C(v,w), if a routing algorithm in 7Z examines the two ends of the 1 1 folio at the current move, then the expectation of the potential function on the new appearance is H(11,12, • • • ,1,.)- 1 - q. Proof. The idea is the same as in Lemma 3.2. Note that we have two cases: 1 1 > 2k - 1 and 1 < 2k - 1. We shall only show the case 1 1 > 2k - 1 (the case / 1 < 2k - 1 is similar). In this case, with probability 1 - q 2 , the new appearance is (1 2 , • • •, 1 r ), and with probability q 2 , the new appearance is (11 - 1, • • • , / 1 - 1,12 , • • •,1„). Thus the expectation of the potential function on the new appearance is d (1- q 2) I1(12, • • • ,1,.)-F q 2 H(11 - 1,• • • ,11 - 1,12,• • • ,1r) d = (1 — q 2 )[G(12)-F • • • 4- C(12)• • •C(1r-i)G(101-1q 2 [G(li - 1)-F • • + (C(11 - 1)) d-1 G(11 - 1) + (C(11)) d G(12)-F • • • + (C(11)) d • • •C(1 r _i)G(1 r )] = q 2 [G(li - 1) + • • • + (C(11 - 1)) d-1 G(1 1 - 1)]+ [( 1 - q 2 ) q 2 (C(1 1 - 1))1[G(12)-1- • • • + C(12) • • • C(1 r _i)G(1 r )] = G( 1 1) - 1 - q+ C(10G(12)+ • • • + C(l 1 ) • • •C(1 r _ i )G(I r ) = H(11,12, • • • ,1 r ) - 1 - q. A Lemma 3.6 Given an appearance (11,12, • • • ,1r)^< 1 1 < 1 2 < 1r ) of the channel graph C(v,w), if a routing algorithm in TZ examines the two ends of some l i -folio (11 < li), then the expectation of the potential function on the new appearance is strictly greater than H(1 1 , 12, • • • ,1,.)- 1 - q. CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^49 Proof. Similar to the proofs of Lemma 3.4 and Lemma 3.5. A From Lemma 3.4, 3.5 and 3.6, we conclude that ^ 1 is a lower bound d for the expected number of tests of any routing algorithm in 7Z. It also shows that the following algorithm (Depth-First-Search Routing B) is an optimal routing algorithm in 7Z with an expected time d Depth-First-Search Routing B Repeat the following until C(v, w) is empty or the depth of a folio becomes zero Choose an h-folio F with the smallest depth h in C(v, w) Examine the two ends of F If one of the ends is busy then delete folio F from C(v, w) else if h > 2k — 1 then remove the two ends and break folio F into d (h — 1)-folios else remove the two ends and decrease the depth of folio F by one Proposition 3.2 Given a series-parallel network with scale k and depth 1, where k < 1 < 2k —1, the Depth-First Search Routing B is the optimal routing algorithm in R, with an expected time H CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^50 3.5.2 Routing Algorithms without Restriction Given a set S of disjoint folios, in which each vertex is busy with probability p and idle with probability q, a routing algorithm for S returns a busy cut of S with the "blocking probability," or an idle path of S with the "linking probability." Given a routing algorithm a for S, let T(a) be its expected time. Let Opt(S) be the minimum T(a) over all routing algorithms a, and Optn(S) be the minimum T(a) over all routing algorithms a E R. Proposition 3.3 We have Optiz(S) < Opt(S) P Proof. Let w be an optimal routing algorithm for S. We shall show that there is a routing algorithm a E TZ, which "simulates" co with at most a 1/p factor increase in the expected time. Suppose that at some step, w examines vertex x in an h-folio F of S. Algorithm a simulates this step by doing the following: Repeat the following until either x is examined or a busy vertex is found Examine the ends of F in turn If both ends are idle then if h > 2k —I then remove the two ends and break F into d (h — 1)-folios else remove the two ends and reduce F to an (h — 1)-folio Proceed recursively CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC ^51 The algorithm a uses at most an expected number 1 + q + q 2 + • • • < 1/p tests for the one test by co, and at the end, a "knows more than" w does (either it has examined x, or it has verified that the status of x is irrelevant). Therefore a simulates w (it returns a busy cut of S when w does, and returns a idle path when co does) with at most a 1/p factor increase in the expected time. A From Proposition 3.2 and 3.3, we conclude that Theorem 3.1 Given a series-parallel network with scale k and depth 1, k < 1 < 2k — 1, the ex- pected time of Depth-First Search Routing B is within a multiplicative factor 1 I p of the optimal. Chapter 4 Fault-Tolerant Switching Networks 4.1 The Switch Failure Model In this chapter, we consider fault-tolerant switching networks under a random switch-failure model. In this model, each electrical switch in the network is independently in one of the three states: (1) open failure (the switch is permanently off and fails to be on) with probability 0 < E l < 1/2, (2) closed failure (the switch is permanently on and fails to be off) with probability 0 < c2 < 1/2, and (3) normal state (the switch functions correctly) with probability 1 — e l — e2 . For the simplicity of notation, we assume that e l = E2 = e. The measure of fault tolerance is the probability of the network fulfilling the communication task in the presence of switch failures. This model is essentially equivalent to that of Moore and Shannon [MS56], who introduced it in the context of relay circuits computing Boolean functions. The model retains its relevance, since open and closed failures represent the two dominant failure-modes both for metallic-contact switches (still frequently used, especially for video switching) and MOSFET's (Metal-OxideSemiconductor Field-Effect Transistors, a common switching element in VLSI circuits). 52 CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 53 4.2 The Networks The networks we consider in this chapter are non-blocking networks, rearrangeable networks and superconcentrators. These networks are designed to achieve specific worst-case performance with respect to the communication task (though we shall be interested in average-case performance with respect to failures). Non-blocking networks were introduced by Clos [C53] in 1953 to epitomize the activity of telephone communication. Bene'S [B64] in 1964 described the rearrangeable network. Rearrangeable networks are useful architectures for parallel machines. Aho, Hoperoft and Ullman [AHU74] in 1974 posed the problem of superconcentrators. Although their hope was to use them to establish a nonlinear lower bound for the Boolean circuit complexity of multiplication, superconcentrators turned out to be central in a number of communication networks. For example, superconcentrators provide support for the Task Queue Scheme (see [C88]) in parallel computing. As before, we describe a switching network in terms of an acyclic directed graph. Terminals of the network (wires that connect the network to the outside world) are represented by distinguished vertices called inputs and outputs. Links are represented by vertices other than inputs and outputs, and switches (single-pole single throw, connecting two links) by edges between the two corresponding vertices. The three states of each switch in the random switch failure model are therefore interpreted as (1) the edge ceases to exist (open failure), (2) two vertices of the edge contract to one (closed failure), and (3) the edge is unaffected (normal state). A non-blocking n-network is defined in Definition 2.1. CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 54 Definition 2.1 Let G be an acyclic directed graph G with a set of n distinguished vertices called inputs and a set of n other distinguished vertices called outputs. G is a non-blocking n-network if, given any set of vertex-disjoint direct paths from inputs to outputs, and given any input and any output not involved in these established paths, a new path that is vertex-disjoint from the established paths can be found from the requesting input to the requesting output. Definition 4.1 Let G be an acyclic directed graph with a set of n distinguished vertices called inputs and a set of n other distinguished vertices called outputs. G is a rearrangeable n-network if, given any one-to-one correspondence between the inputs and the outputs, there exists a set of n vertex-disjoint paths joining each input to its corresponding output. Definition 4.2 Let G be an acyclic directed graph with a set of n distinguished vertices called inputs and a set of n other distinguished vertices called outputs. G is a n-superconcentrator if, for every r < n, every set of r inputs, and every set of r outputs, there exists a set of r vertex-disjoint paths from the given inputs to the given outputs. It is obvious that a non-blocking n-network is a rearrangeable n-network and a rearrangeable n-network is an n-superconcentrator. From the worst-case performance point of view, these networks all exhibit some type of "non-blocking" property under different assumptions. Nonblocking networks guarantee a dynamic linkage between any pair of idle input and output regardless the current traffic pattern in the networks. Rearrangeable networks provide an idle path for a requesting pair (of an idle input and an idle output) by rearranging the connection paths for the existing pairs. Superconcentrators assume all inputs (outputs) are equivalent, and CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 55 satisfy the communication requirement by providing a flow of disjoint paths (from inputs to outputs). As before, the measures of complexity applied to such networks are size (the number of edges), and depth (the largest number of edges on any path from an input to an output). Shannon [S50] showed an fi(n log n) size lower bound of rearrangeable n-networks. Bend [B64] presented an 0(n log n) size and O(log n) depth construction for rearrangeble n-networks. The existence of 0(n log n) size and O (log n) depth non-blocking n-networks was proved by Bassalygo and Pinsker [BP74]. For n-superconcentrators, an 11(n) size lower bound is obvious and Valiant [V75] showed an 0(n) size and 0((log n) 2 ) depth upper bound. Pippenger [P77] improved Valiant's result, showing a construction with 0(n) size (with a smaller constant) and O(log n) depth. Pippenger and Yao [PY82] presented a trade-of between size and depth for rearrangeable n-networks. See Pippenger [P90] for a detailed survey on the improvements of lower and upper bounds on non-blocking networks, rearrangeable networks and superconcentrators. 4.3 Fault-Tolerance Given 0 < c < 1/2, consider a network N subject to the random switch failure model. Let the event space ft be the set of all graphs obtained from N. The probability measure on each graph is assigned in accordance to the number of failed edges. More precisely, if a graph G E SI has k failed edges, the probability that the random instance of N equals G is (2c) k (1 - 2c)" -k , where n is the number of edges in N. Given 0 < 45 < 1, we say N is an (e,b)-non-blocking n-network if the probability that the random instance of N contains a non-blocking n-network consisting of edges CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 56 of normal state is greater than 1 — 6. Similarly we define an (c, 6)-n-rearrangeable network and an (c, 6)-n-superconcentrator. We observe that an (c, 0-non-blocking n-network is an (c,6)- rearrangeable n-network and an (c, 0-rearrangeable n-network is an (c, 0-n-superconcentrator. It is clear that by choosing an arbitrarily small 5, an (e, 5)-non-blocking n-network or an (c, 6)rearrangeable n-network or an (c, 5)-n-superconcentrator can fulfill its communication task with an arbitrarily high probability. The goal of this chapter is to analyze the asymptotic behaviors of the size and depth of the (c, 0-non-blocking n-network, the (c,0-rearrangeable n-network, and the (c, S)-n-superconcentrator. For this purpose, the exact values of 0 < c < 1/2 and 0 < b < 1 do not matter. To see this, we shall first need a result of Moore and Shannon [MS56]. Define an (c, E')-1-network to be a directed graph with two distinguished vertices called input and output, in which each edge is randomly and independently subject to closed and open failures with probabilities of c, respectively; and in which the probabilities that the input and the output contract into one vertex and that there is no path from the input to the output are both less than E'. Proposition 4.1 (Moore and Shannon) Let 0 < c < 1/2 and 0 < < E. There is an explicit construction of an (c,e)-1-network with c c (log 2 (1/0 2 edges and d,log 2 (11e) depth, where c, and d, are constants depending only on c. To observe the fact that the exact value of c does not affect the asymptotic behaviors of the size and depth, we suppose that 0 < E l < E2 < 1/2, and that 4I) is an (E l , 0-n-superconcentrator CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 57 with size L and depth D, for some 6 < 1. By Proposition 4.1 there is an (c 2 ,c1 )-1-network AP of size a and depth b (a and b are depending only on c2). The result of substituting this network P for each edge in 4) is an (€2 , 0-n-superconcentrator with size at most aL and depth at most bD. Similar arguments apply to (c,0-rearrangeable n-networks and (c, 5)-non-blocking n-networks. To see the invariance with respect to the value of 5, we suppose that 0 < Si < 6 < 1, and that 4) is an (c,62)-n-superconcentrator, for some c < 1/2. The failure probability of 4P is a polynomial in c and the constant term of this polynomial vanishes (since the network does not fail unless some switch fails). If we replace c by di /6 2 , every term in this polynomial decreases to at most 6 1 /62 times its previous value, and the value of the polynomial decreases to less than S i . Thus 4, is also an (cbi /6'2 , 45 1 )-n-superconcentrator. Again, substitute each edge in 41 by an (c, c6 1 /6 2 )-1-network and the resulting network is an (c,6 1 )-n-superconcentrator . with the size and depth being affected by only a constant factor. Similar arguments apply to (c,0-rearrangeable n-networks and (c, 5)-non-blocking n-networks. 4.4 Main Result and the Overall Strategy In this chapter we show that the size and depth of (c, 5)-n-superconcentrators, (c,6)-rearrangeable n-networks, and (c, 5)-non-blocking n-networks are O(n(log n) 2 ) and O(log n). The overall strategy is that we shall prove the S2(n(log n) 2 ) and 11(log n) lower bounds for size and depth of an (1/4, 1/2)-n-superconcentrator, and we shall construct (10 -6 , 6)-non- blocking n-networks with O(n(log n) 2 ) size and O(log n) depth for an arbitrarily small 6. The success of this strategy is ascribed to an observation we made earlier, that for any 0 < c < 1/2 CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 58 and 0 < S < 1, an (c, 0-non-blocking n-network is an (c,5)-rearrangeable n-network and an (c, 5)-rearrangeable n-network is an (c, 5)-n-superconcentrator. Thus a lower bound (on size or depth) for an (c, S)-n-superconcentrator is a lower bound of all three, and an upper bound for an (E, 0-non-blocking n-network is an upper bound of all three. The lower bounds are proved in Section 4.5. In section 4.6 we construct the (c, 5)-nonblocking n-network. A few observations on our upper bound are in order. First, the upper bound is based on an explicit construction and is not merely an existence proof. Second, with a high probability we can find a non-blocking network contained in the fault-tolerant network merely by discarding faulty components and their immediate neighbors, so no difficult computations are hidden here. Third, because the contained network is "strictly" non-blocking (see Feldman, Friedman and Pippenger [FFP88] for details), routing can be performed by a "greedy" application of a standard path-finding algorithm, so again no difficult computations are involved. 4.5 The Lower Bounds The strategy of the lower bound proof is as follows. We associate with each input a neighborhood containing all vertices within a logarithmic distance of the input. We show that for a large set of inputs, these neighborhoods are disjoint (otherwise two inputs would be shorted by dosed failures with high probability). This gives the lower bound for depth. We then partition the vertices in the neighborhoods of these inputs into zones according to their distance from the input. We show that for a large number of inputs, each of these zones must have logarithmic CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 59 size (otherwise some input would be isolated by open failures with high probability). Summing over the zones of each neighborhood and the neighborhoods of the inputs gives the lower bound for size. Given a graph G, we say the distance from vertex e l to vertex of edges in the shortest path (not necessarily directed) from e2, diSt(ei,e2), is the number el to 6 ; the distance from a vertex e to an edge e =<v, p>, dist(e, e), is minIdist(e , p), dist(, v)} + 1. Lemma 4.1 A tree with 1 leaves, in which every internal node has degree at least 3, contains at least 1/42 edge-disjoint paths, each joining 2 leaves, and each having length at most 3. Proof. We begin by observing that we may assume that each internal node has degree exactly 3. For if not, we may replace each internal node with degree d > 3 by a "tree" comprising d — 2 new nodes with degree 3. If we find a set of edge-disjoint paths of length at most 3 in the resulting tree, these will correspond to edge-disjoint paths of no greater length in the original graph. Suppose then that T is a tree with 1 leaves in which each internal node has degree 3. Clearly there must be 1— 2 internal nodes. Let us say that a leaf L is "bad" if there is no other leaf with distance at most 3 from L. We shall show that there are at most 61/7 bad leaves. If L is bad, there are 7 internal nodes with distance at most 3 from L (see Figure 4.1). Let L "pay" 1 dollar to each of those nodes. We claim that each of the 1 — 2 internal nodes "collects" at most 6 dollars, from which it follow that there are at most 6(1— 2)/7 < 61/7 bad leaves. If some internal node V collects more than 6 dollars from bad leaves at distance at most 3, then more than 1 of these bad leaves must be adjacent to one of the 6 or fewer nodes at distance 2 from CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 60 ^ :Leaf 0 : Internal node Figure 4.1: A bad leaf V. But no more than 1 bad leaf can be adjacent to an internal node (see Figure 4.2). Thus at Figure 4.2: An internal node collects at most 6 dollars least 1/7 leaves are "good" (that is, not bad). Suppose that there are m good leaves. Let G be a maximal set of edge-disjoint paths, each joining 2 good leaves and each having length at most 3. Say that a good leaf is "lucky" if it is the endpoint of a path in G, and that it is "unlucky" otherwise. If L is unlucky, there must be a path P in G within distance 2 of L. (There is a leaf within distance 3 of L, since L is good, and only a path in G could prevent L from being joined to such a leaf in the maximal set C.) Let each unlucky leaf "pay" 1 dollar to some such path P. Each path P "collects" at most 4 dollars from unlucky leaves, since there are at most 4 leaves with distance at most 2 from P (see Figure 4.3). It follows that there are at most 4 unlucky leaves for each path in G. Since there are exactly 2 lucky leaves for each path in C, and m > 1/7 good leaves (lucky and unlucky), this implies that there are at most m/6 > 1/42 paths in C. A CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 61 BS : Lucky leaf^^ : Unlucky leaf Figure 4.3: Each path collects at most 4 dollars from unlucky leaves Remark: The bound "1/42" in Lemma 4.1 can be improved to "1/4", but this requires a more elaborate analysis which will be presented in Chapter 6. Corollary 4.1 A forest F of l leaves, in which every internal node has degree at least 3, contains at least 1/42 edge-disjoint paths, each joining 2 leaves, and each having length at most 3. Lemma 4.2 Let 4 be a (114,112)-n-superconcentrator. For all sufficiently large n, at least n/,2 inputs of 4) have distance (ignoring the direction of each edge) at least (1/8)log2 n from each other input. Proof. Suppose that each of n/2 inputs v has a path ir(v) of length at most j to some other input. We shall obtain a contradiction if j = (1/8)log2 n and n is sufficiently large. Define a forest by (1) starting with the empty forest, (2) considering each such input in turn, and (3) adding to the forest the longest initial segment of ir(v) that is edge-disjoint from the forest generated thus far. Thus the resulting forest F has at least n/2 leaves, and each "stretch" (sequence of consecutive vertices of degree 2) has length at most j. Let G be the forest obtained from F by replacing each stretch, together with the edges incident with its vertices, by a single edge. In 62 CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ G every internal node is of degree at least 3, so we may apply Corollary 4.1 to obtain at least n/84 edge-disjoint paths, each having length at most 3 and each joining one leaf to another. Replacing each edge of these paths by the corresponding stretch, we obtain in F at least n/84 edge-disjoint paths, each having length at most 3j and each joining one input of 4) to another. Note that if each of the 3j edges on one of the n/84 paths is in the closed failure state, two inputs of 40 will contract to a single vertex, and the result will certainly not be an n-superconcentrator. Since this can happen with probability less than 1/2, we have 1 - (1 - (1/4) 3i )n/84 < 1/2. If we set j = (1/6) log2 (n/(841n 2)), we obtain a contradiction using the inequality (1 - x)Y < e xv. - Thus if we set j = (1/8) log2 n, we obtain a contradiction for all sufficiently large n. A Theorem 4.1 Let 40 be a (1/4, 112)-n-superconcentrator. For all sufficiently large n, 4. has size at least (1/256)n(log 2 n) 2 and depth at least (1/16) log 2 n. Proof Say an input is "good" if it has distance at least (1/8) log 2 n from each other input. By Lemma 4.2, there are at least n/2 good inputs. (Note that the existence of 2 good inputs implies, by the triangle inequality of the distance, that the depth is at least (1/16) log 2 n.) For each good input v, let B(v) denote the set of all edges at distance at most (1/16) log 2 n from v. For any pair v and w of good inputs, the sets B(v) and B(w) must be disjoint, since otherwise the distance between v and w would be less than (1/8) log 2 n. Thus it will suffice to show that, for each good input v the set B(v) contains at least (1/128)(log 2 n) 2 edges for all sufficiently large n. If an input vo has all n outputs adjacent to some edges in B(v o ), then it is certainly true that IB(v0 )1 > (1/128)(log 2 n) 2 , since the number of edges in B(v o ) cannot be less than the number of outputs adjacent to these edges, and n > (1/128)(log 2 n) 2 for all sufficiently large n. Thus we CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 63 may assume that for each good input v, there is an output w(v) that is not adjacent to an edge in B(v). Consider an arbitrary good input v. Set i . [(1/16) log 2 nJ > (1/32) log2 n. Partition B(v) into subsets Bi(v), • • • , Bi(v), where Bh(v) comprise those edges at distance h from v. Let B*(v) denote the set Bh(v) with the minimum number of edges. It will suffice to show that each set B*(v) contains at least (1/4) log 2 n edges. Let b be the cardinality of the set B*(v) with the minimum number of edges. It will suffice to show that b > (1/4) log 2 n for all sufficiently large n. Consider an arbitrary good input v. Any path from v to w(v) must contain an edge in B*(v), since the distance from v can increase at most 1 at each successive edge of a path. If edges of B*(v) are all in the open state, all paths from v to w(v) are broken, and the resulting network is certainly not an n-superconcentrator. This can happen with probability at most 1/2. Thus we have 1- (1- (1/4)b)n/ 2 < 1/2. As before, this implies that b > (1/2) log2 (n/21n 2) > (1/4) log 2 n for all sufficiently large n. A 4.6 The Upper Bounds In this section we shall explicitly construct (10 -6 ,0-non-blocking n-net works with O(n(log n) 2 ) edges and O(log n) depth for arbitrarily small b. The strategy of the upper bound proof is as follows. We use a standard recursive construction for non-blocking networks, but scale the construction up by a logarithmic factor, and terminate the recursion with subnetworks of logarithmic size (rather than constant size). We then use networks (called "directed grids" in this chapter) of logarithmic by logarithmic size based on the "hammock" of Moore and Shannon [MS56] to interface the inputs and outputs to the CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 64 terminal subnetworks. The basic building blocks of the construction are (c, c' ,t)- expanding graphs and (1, w)- directed grids. A (c, c', t)-expanding graph is a bipartite directed graph with two distinguished sets of t vertices called inlets and outlets respectively, where every set of c inlets is joined by edges to at least c' outlets (that is, for every set C of c inlets, there exist a set C' of c' outlets, such that for every outlet (' in C' there is an inlet C in C and an edge ((, (')). The constructions of (an, bn, n)-expanding graphs (where 0 < a < b <1 are constants) with linear sizes (with respect to n) are quite standard. See Bassalygo and Pinsker [BP74] for the probabilistic version, and Gabber and Galil [GG81] for an explicit construction. (It needs mention that the first explicit construction was presented by Margulis [M73] and the current best explicit construction is due to Lubotzky, Phillips and Sarnak [LPS88].) An (1, w)-directed grid is a directed graph with w stages and 1 vertices in each stage. A vertex in the j-th stage and the i-th row is denoted by a binary tuple (i, j), 1 < i < 1 and 1 < j < w. An edge from vertex (i, j) to vertex (i', j') exists if i' = i and j' = j + 1 or i' = i + 1 and j' = j -I- 1. (See Figure 4.4.) Figure 4.4: A (4, 8)-directed grid CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 65 Suppose that we wish to construct an (c, 0-non-blocking n-network with n = 4". Set 7 = flog 4 (4001, so that 160v > 4' 1 > 40v. We first construct a non-blocking 4' 1-1 -network through the recursive construction illustrated in Pippenger [P82] (Section 9). This network is a directed graph with 2(v + 7) + 1 stages, with 4 141 inputs on stage 0 and 4' 4'1 outputs on stage 2(v + 7). Each other stage contains 64 . 4' 41 vertices. Edges only exist between some vertices in adjacent stages. The subgraph induced by inputs and vertices in stage 1 consists of 4 11 +1-1 disjoint bipartite graphs, each having 4 inputs on one side and 256 vertices on the other side. Similar property holds for the subgraph induced by outputs and vertices in the adjacent stage. The subgraph induced by vertices in stage i and stage i + 1 (for all 1 < i < v + 7 - 1) consists of 4P+ .7-i disjoint (32 • 4i, 32(1 + .?=-P) 4i, 64 • 4i)-expanding graphs, with each vertex on stage i having 20 out-edges and vertex on stage i + 1 20 having in-edges. The subnetwork from stage v + 7 to stage 2(v + 7) is a mirror image of that from stage 0 to stage v + 7. Network N' is a mirror image of network N if N' is obtained from N by (1) exchanging the inputs with the outputs and (2) reversing the direction of every edge. In this non-blocking 4 11 + 1 -network, we then remove vertices in the first and last 7 stages and edges incident with them, and let M be the remaining graph. The first stage of M consists of 4" disjoint sets vertices, each being the inlets of a (32 • 4 1 ,33.07 • 4'1 ,64 . 41-expanding graph (note that 32(1 + 1:--A > 33.07). Construct 4" (v, 64 . 41-directed grids (1)1, • • • , 404.. Joined to each vertex in the first stage of ol)i (i = 1, • • .,4") is an edge from an input vertex. Combine M with 4. 1 , • • • , 44g and the associated inputs by (1) letting the 4" (32 . 4 1 ,33.07 . 4 7 ,64 . 4 1 ), expanding graphs in the first stage of M correspond to (P i , • • • , De in any one-to-one fashion, ( CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 66 and (2) in each such corresponding pair, identifying the inlets of the expanding graph with the vertices in the last stage of the directed grids in any one-to-one fashion. Similarly, construct 4" (v, 64 • 4 1')-directed grids T i , • • • , We; join an output by edges to every vertex in the last stage of each Ili (j = 1, • • • , 4"); combine Ti , • • • , Te and the associated outputs with M (and the above combined 4, 1 , • • • , 41) 4 1, and the associated inputs) by identifying vertices of the first stage of 41 1 , • • • , T2v with vertices in the last stage of M. Call the resulting network Al. (See Figure 4.5.) Figure 4.5: Network H Network H has 2(v -I- v) + 1 = 4v + 1 stages. The 4" inputs and 4" outputs are on stage 0 and stage 4v respectively. Each other stage contains 64 • 4"+"Y vertices. The subnetwork from stage 1 to stage v and that from stage 3v to stage 4v — 1 consist of 4b 1 , • • • , 4■4v and Ti, • • • , T4v, respectively. The subnetwork from stage v to stage 3v is M. Each input has out-degree 64 • 4 7 ; a vertex in 41)i has in-degree 2 and out-degree 2, except vertices on its first stages (in-degree 1) and last stages (out-degree 20); a vertex in the left-hand half of M (stage v to stage 2v of H) has in-degree 20 and out-degree 20, except vertices on stage v (in-degree 2). The subnetwork from stage 2v to stage 4v (called .Arn.) is a mirror image of that from stage 0 to stage 2v (called CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 67 ArE). In particular, the right-hand half of M, called M iz , is a mirror image of Mr, the left-hand half of M. Network N has 2816ve+ 1 edges, because there are 2560v4P+ 1 edges in M, at most 256(v — 1)4Y+ 1 edges in 4i and 414, for all 1 < i < 4', and 128 •4P+ 1 edges adjacent to inputs and outputs. Let 7/ be a vertex of N which is not an input or an output, say a vertex ri of an edge <r, N is faulty, if n > or <77, > is in open failure or closed failure state. Given a set of vertex-disjoint direct paths from inputs to outputs in N, for an input, an output, or a vertex which is not faulty, say it is idle if it is not involved in these paths, busy otherwise. Say an (idle) vertex has access to another (idle) vertex that if e i has access to 6 and 6 6 if there is a path of idle vertices from Ei to has access to 6, then el has access to 6. e l 6 . It is clear A network N is a majority-access network if, given any set of directed paths from inputs to outputs, every idle input has access to a majority (strictly more than half) of the outputs. Lemma 4.3 Let e be an idle input of network N. The probability that f has access to at least 32 . 4 1 -I- 1 vertices in the last stage of (i.e., strictly more than half) is at least 1— c i v(264c)" , where c 1 = 1/(1 — 132c). Proof. The basic idea is illustrated in [KKL+] and [R89]. Let us begin by estimating the probability that e does not have access to any vertex at the last stage of 4)e. There is no busy vertex in 4), since e is idle and N is a directed and staged graph. By Menger's Theorem (see e.g., Chapter 5 of [CL86]), there is a "(vertex) cut set" of 4)e (i.e., vertices such that the removal of which and their adjacent edges will separate and the vertices at the last stage) consisting CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 68 of faulty vertices only. Consider a cut set C of 1 vertices. It must be 1 > 64 • 4 -Y, since 017, t has this many rows. The probability of every vertex in C being faulty is at most (44c) 1 , since each vertex in (N (other than e, which is not in any cut set we consider) is adjacent to at most 22 edges (2 in-edges and 20 out-edges). For any given 1, the number of such cut sets C is at most v3 1 , since there are v vertices at the first row of (Pt to start C, and at most 3 ways (each along an edge) to continue at each step. Thus the probability that e does not have access to any vertex at the last stage of 41)t is at most E 1131(440/ = c i v(132064-4 Y. - l>64.4 7 Consider an arbitrary set S of 32.4ry vertices in the last stage of 40t. The probability that e does not have access to any vertex in S is at most CW0320 64.4' . There are at most ( 64 • 41 32.4 7 264.47 such S. This implies that the probability of E having access to at least 32 . 4 7 + 1 vertices in the last stage of 4 is at least 1 — c i v(264c)', since 64 .^> v. A Lemma 4.4 In a (32 . 4 0 , 33.07 . 4P, 64 . 4 0 )-expanding graph in Mc, for any 7 p^+7 —1 (the expanding graph is in the subgraph from stage p v — 7 to stage p v — y +1 of N), the probability that it has more than 0.07 . LIP outlets faulty is at most e -0 . 05 •I m Proof. There are 2560.4 0 edges incident with outlets of the (32.4', 33.07.4 0 , 64 .4P)-expanding graph (each vertex has 20 in-edges and 20 out-edges). For each such edge, let x j be the random variable such that xj = 0 if the edge is in normal state, xi = 0 otherwise, for all 1 < j < 2560.4P. It is clear that Pr[x = 1] < 2e and Pr[x • = 0] > 1 — 2c. Let T = E25 60.4A ^x3. J1 Pr[T > 0.07 • 4"1 = Pr[eT > 0.67.41 < E[eT]/eo.o7•4A CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 69 by Markov's inequality. As xi's are independent, E[e T ] =^E[exi] < (1 + 2e 02560.4 , < e 5120ee•4 0 i= 1 since (1 + x)Y < el'. And 5120e€ < 0.02 when e = 10 -6 . Thus the probability that there are more than 0.07 • 2" outlets faulty is at most 0.02.414-0.074P = e -0.05-1 1 . A Lemma 4.5 The probability that there exists a (32 • 4", 33.07 • 4", 64 • 4 19-expanding graph in Mc with more than 0.07 • 4" faulty outlets, for some y < p < v 7 - 1, is less than v(2 le) 2 '. Proof. It is simply a problem of counting the number of expanding graphs with respect to the number of outlets. There are 4 11 +1-14 (32 .4", 33.07.4 1 , 64 • 4 19-expanding graphs between stage v+ p - 7 and stage p - y +1 of Mc, for all y < p < v+ 7 -1. By Lemma 4.4, the probability that there is an expanding graph with no more than 0.07 • 4" faulty outlets is at most v+-y-1 e--0.05.414 < th=7^ E 4v e -0.054 -1 < vee -2v , IA=7 since 41' > 40v. A Lemma 4.6 With probability at least 1-civ(264c)"-v(2/e) 2 u, H is a majority-access network. Proof. We may assume in this proof that each (32 • 4", 33.07 • 4 1 , 64 • 4")-expanding graph in Mr has at most 0.07 • 4" outlets faulty, and each idle input has access to at least 32 • 4 7 + 1 vertices in the last stage of (N. It is clear by Lemma 4.3 and Lemma 4.5 that the probability of the assumption failing is at most 1 - civ(264c)" - v(2/e) 2 v. For each pair of inputs el and 6, we say their relativity, relat(6,e2) = relat(6,6), is d (1 < d < v) if and only if the directed paths starting from the two inputs may share a vertex at or after the (d+ v)-th stage but cannot CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS ^ 70 share any vertex before the (d + v)-th stage. It is observed that, for each input e, there are 4d — 4d-1 = ,.•4. 4 d-1 other inputs e' with relat(4',e)= d, for any d with 1 < d < v. Now suppose that e is an arbitrary idle input, let the subnetwork No of .Al . be (k, and Nk be the subnetwork induced by vertices that can only be reached by e and 4 k —1 other inputs e i with relat(e,4.1 ) < k. It is clear that Nk has 4 k inputs and 64 . V +k outputs. We shall prove by induction on k that e has access to at least 32 • 414 k + 1 outputs of Nk, thus in particular has access to strictly more than half of the outputs of NN =Pi,. The base case No is obviously true because of our assumption. Consider Nk+i. The outputs of Nk are linked to the outputs of Nk+i via four (32 .4" -k , 33.07.4 1 + k , 64 . 4 14 k )-expanding graphs (with the inlets being the outputs of Nk and the outlets being four disjoint subsets of the outputs of Nk +1 ). By the induction hypothesis, e has access to at least 32.4 1 +k + 1 outputs of Nk. These 32.414 k + 1 vertices are joined by edges to at least 4.33.07.4 1 + k outputs of Nk+i (via the four (32.4 1'+k, 33.07.4 1 + k , 64 .41 + k )-expanding graphs). By our assumption, there are at most 0.07 • 4 1"44 + 1 outputs of Nk-Fi are faulty. And there are at most 411-1 - 1 outputs of Nk.4-1 are busy, because each busy output is one-to-one corresponding (via a directed path) to a busy input of Nk÷i, and there are at most 4 k}1 -1 such inputs. Thus, e has access to at least 4 . 33.07. 4/+ k — 0.07 • 41"4+1 — 4 k+1 +1 > 32 • 4 7+k+1 +1 outputs of Nk+1. This completes our induction. 0 Corollary 4.2 With probability at least 1 — c i v(264c)" — v(21e) 2 Y , the mirror image of Ni is a majority-access network. We observe that if Arc and the mirror image of Ariz are both majority-access networks and the inputs and outputs of N are distinct (no two input(s) and output(s) contracting to a single . CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 71 vertex), then N contains a non-blocking 4"-network of no-failure edges. Lemma 4.7 With probability at most c 2 v 2 (1600 2 ' , where c 2 = 4 15 /(1 - 40e), there exist two input(s) and output(s) that contract to a single vertex. Proof. The correctness of the lemma follows four observations. Firstly, any simple path joining two input(s) and output(s) must contain at least 2v edges. Secondly, for any 1 > 2v, there are at most (64 • 4 1) 2 (40) 1-2 such paths of length 1, since the degree of inputs and outputs is 1since , 64 • 4 1 , and that of the other vertices is at most 40. Note (64 • 412(40)1-2 < 4 14 1,2( 4 u 41 < 160v. Thirdly, the probability that a path of length 1 gets "shorted" (all edges on the path are in closed failure state) is less than El. And lastly, there are at most (2 • 4') 2 such input or output pairs. A Theorem 4.2 Network .Ar is a (10 -6 , 0-non-blocking n-network with at most 4 10 n(log 4 n) 2 edges and 5 log 4 n depth for arbitrarily small S, when n is sufficiently large. Proof. We have seen that network Ai contains at most 28161,4 11+ 1 edges and has 4v + 1 depth, where n = 4" and 7 = Flo& 3411. Work out the constant using 4 7 < 160v. The probability that N fails to contain an non-blocking n-network of no-failure edges is less than 2(civ(264c)" v(2/e) 2 ") + c2v 2 (160c) 2 ", by Lemma 4.6, Corollary 4.2, and Lemma 4.7. This value can be arbitrarily small when n = 4" is sufficiently large, given c = 10'. L Chapter 5 Fault-Tolerant Planar Switching Networks 5.1 Planar Networks The rapid advances of VLSI technology have made massive parallel computer systems practical. Consequently, research on planar networks on VLSI chips becomes attractive (see [AKL+ 85], [AKL+91], [C578], [TK82] and [KL90]). Suppose that in a VLSI circuit, there are units (eg. processing and memory units) called "transmitters" and other units called "receivers". Planar communication networks (consisting of links and switching elements) provide simultaneous communication between various combinations of transmitters and receivers. Today's fabrication technologies, such as MOS technology, fabricate these links and switches as transistors in VLSI circuits. Our interest in this chapter is in fault-tolerant planar networks that accomplish the simultaneous communication by means of disjoint paths of links and switches from transmitters to receivers. We shall consider the constructions of fault-tolerant planar rearrangeable networks and faulttolerant planar superconcentrators. A "planar rearrangeable n-network" is a rearrangeable n72 CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^73 network that can be embedded into a plane. And a "planar n-superconcentrator" is an nsuperconcentrator that can be embedded into a plane. Similarly, one can define a "planar non-blocking n-network". There are simple constructions for planar rearrangeable n-networks and planar n-superconcentrators with polynomial sizes (see next paragraph for details). This is in contrast with the gloomy situation of planar non-blocking n-networks where even the existence of planar nonblocking n-networks for arbitrary n is an open problem. The measures of complexity applied to planar communication networks are the size (the number of edges), and the degree (the maximum degree of vertices), since they affect the number of processing and memory units integrated onto a VLSI chip. An extensive literature exists concerning the design of planar communication networks. Cutler and Shiloach [CS78] showed a grid construction for planar rearrangeable n-networks with 0(n 3 ) edges and a constant degree for each vertex. Aggarwal et al [AKL+85] proved an S1(n 3 ) size lower bound for any grid construction, showing that Cutler-Shiloach construction is asymptotically optimal. Aggarwal et al [AKL+91] further extended their result to multi-layer grid construction, showing that the 11(n 3 ) lower bound still holds when a constant fraction of the connection paths remain in the same layer. Klawe and Leighton [KL90] on the other hand, extended the S2(n 3 ) size lower bound to arbitrary planar rearrangeable n-networks. Lipton and Tarjan [LT79] proved an II(n 2 ) size lower bound for any planar n-superconcentrator. And an n x n grid is obviously a planar n-superconcentrator with 0(n 2 ) edges and a constant degree for each vertex. Our goal in this chapter is to construct fault-tolerant planar rearrangeable n-networks and CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^74 planar n-superconcentrators, minimizing size and degree. We shall consider the random switchfailure model of Chapter 4. As before, given 0 < S < 1, we say a network N is a planar (c, b)-rearrangeable n-network if the probability measure on all planar rearrangeable n-networks in ft is greater than 1 — 5, where ft is the set of all graphs obtained from N under the random switch-failure model; N is a planar (c,(5)-n-supereoncentrator if the probability measure on all planar n-superconcentrators in S2 is greater than 1 — b. Results of Moore and Shannon EMS561 are useful to build fault-tolerant networks. A consequence of Proposition 4.1 is that there is a planar (c, b)-rearrangeable n-network of size O(n 3 (log n) 2 ), with each vertex having degree 0(log n). To see this, we replace each edge in the Cutler-Shiloach planar rearrangeable n-network by an (c, c')-1-network, where c' = 6 IT and T = 0(n 3 ) is the size of the Cutler-Shiloach network. Similarly there is a planar (c, 5)-nsuperconcentrator of size O(n 2 (log n) 2 ), with each vertex having degree O(log n). In this chapter, we prove that given 0 < c < 1/2 and 0 < S < 1, any planar (c,b)rearrangeable n-network and any planar (c, S)-n-superconcentrator must contain 12(n) vertices each having degree 12(log n). And for any 0 < E < 1/2 and 0 < 5 < 1, we explicitly construct planar (c, 5)-rearrangeable n-networks with 0(n 3 ) edges and 0(log n) degree, having 0(n) vertices with degree greater than 4; and we explicitly construct planar (c, 5)-n-superconcentrators with 0(n 2 ) edges and 0(log n) degree, having 0(n) vertices with degree greater than 6. In both constructions, the sizes are asymptotically optimal, since 12(n 3 ) and S1(n 2 ) edges are needed respectively, even if there are no edge failures. As in Chapter 4, we shall make a few remarks on our constructions. First, with high proba- CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^75 bility we can find a planar rearrangeable network or a planar superconcentrator contained in the fault-tolerant network merely by discarding faulty components and their immediate neighbors, so no difficult computations are hidden here. Second, routing in these networks can be performed by an application of a standard network flow algorithm, so again no difficult computations are involved. 5.2 A Lower Bound on the Degree In this section we may suppose, without loss of generality, that c = 1/4 and 6 = 1/2. Lemma 5.1 Let (D be a planar (1/4, 1/2)-n-superconcentrator. For all sufficiently large n, at least (ln 2)n inputs of 4 have degree at least (1 /2) log 2 n. Proof. We observe that in 01), less than six inputs are adjacent to other inputs. Otherwise there must exist at least three edges such that two ends of each edge are inputs. Note that if one of the three edges is in the closed failure state, two inputs of (I) will contract to a single vertex, and the result will certainly not a planar n-superconcentrator. Since this can happen with probability 1 — (3/4) 3 > 1/2, it contradicts the fact that 4:k is a (1/4, 1/2)-n-superconcentrator. Thus we may assume that at least (ln 2)n inputs are "remote", that is, not adjacent to any other inputs, for all sufficiently large n. For each remote input v, let B(v) denote the set of edges that are adjacent to v. For any pair v and w of remote inputs, the sets B(v) and B(w) must be disjoint. Thus it will suffice to show that for each remote input v the set B(v) contains at least (1/2) log2 n edges. Note that if all edges of B(v) are open, all paths out of v are broken, and the resulting network is certainly not an n-superconcentrator. This can happen with probability at CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^76 most 1/2. Let b be the cardinality of the set B(v) with the minimum number of edges. Thus we have 1- (1- ( 1 / 4 )b)(h12)n < 1/2. If we have b < (1/2) log 2 n we obtain a contradiction using the inequality (1 - xr < e zY. A - Corollary 5.1 Given 0 < c < 1/2 and 0 < 6 < 1, any planar (6,6)-n-superconcentrator must contain 11(n) vertices with degree 11(log n). Corollary 5.2 Given 0 < c < 1/2 and 0 < 6 < 1, any planar (c,6)-rearrangeable n-network must contain 11(n) vertices with degree St(log n). 5.3 A Fault-Tolerant Planar Rearrangeable Network In this section, we assume c = 10 -4 , and we construct planar (10 -4 , 0-rearrangeable n-networks for arbitrarily small S. The networks contain 0(n 3 ) edges and have degree O(log n), with 0(n) vertices having degree greater than 4. Let us first review a result on planar rearrangeable n-networks of reliable edges. It is essentially due to Cutler and Shiloach [CS78] Lemma 5.2 (Cutler and Shiloach) Given a (2n 2 + n) x (2n + 1) grid G, n inputs and n outputs are placed on the middle vertical line at intervals of length n beginning at the top line, with inputs being placed first. G is then a planar rearrangeable n-network. Suppose that we wish to construct a planar (10 -4 ,5)-rearrangeable n-network with n = 2". We first construct a (4n 2 + 2vn) x (4n + 1) grid. Then along the middle vertical line, we shrink the first v of every v + 2n vertices to one vertex. Let the first n of the 2n "shrunk" vertices be CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^77 inputs and the rest n be outputs. A vertex is adjacent to an input (output) if it was a neighbor of one of the v vertices from which the input (output) is obtained. Call this network Al. (See Figure 5.1.) Figure 5.1: The planar (e,45)-rearrangeable n-network N Say a vertex is faulty, if one of its adjacent edges is in open or closed failure state; otherwise say the vertex is intact. Say a path is intact, if every vertex in the path is intact; say a path containing an input or an output is working, if every vertex in the path is intact except the input or output. Obviously every edge in a working path is in normal state. Lemma 5.3 In a 2r x t grid, the probability that there are r vertex-disjoint intact paths from the left hand boundary to the right hand boundary is at least 1 — d i t(288E)'' , where d i. = 1/(1 — (2880 1 / 2 ). Proof. The idea is the same as in Lemma 4.3. For each vertex, with probability at most 8E it CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^78 is faulty; and with the complementary probability it is intact. If there are less than r vertexdisjoint intact paths from the left boundary to the right boundary, then by Menger's Theorem (see e.g., Chapter 5 of [CL86]), there is a (vertex) cut set that contains less than r intact vertices. Note that any cut set must contain at least 2r vertices. Given a cut set of 1 > 2r vertices, the probability that it contains less than r intact vertices is at most E ( / w ) (80 1 '(1 — 8c)" < 2 1 (8c) 1 ' < (32c) 1 / 2 . For any given 1 > 2r, the number of cut sets that contain 1 vertices is at most t3 1 , since there are at most t places (at the top boundary) to start the cut set and at most 3 ways to continue at each step. Thus the probability that the grid contains less than r vertex-disjoint intact paths is at most E t31(32c)1/2 < d i t(2880 . , 1>2r A Lemma 5.4 In a s x t grid, shrink the s vertices at the left hand side boundary to one vertex and name it "source". The probability that there is no working path from source to the opposite side boundary is at most d2t(24e) 8 , where d2 = 1/(1 — 24c). Proof. The proof of Lemma 4.3 applies. To show the fault tolerance of network N, imagine horizontally partitioning N into 4n layers. Each of the 2n odd layers contains vertices of the first v of every v + 2n rows; each of the 2n even layers contains vertices of the remaining 2n of every v + 2n rows. Each input or output is exclusively contained in one of the 2n odd layers. Each odd layer is a v x (4n + 1) grid, except CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^79 that the v vertices in the middle vertical line shrink to an input or an output. Applying Lemma 5.4 (setting s = v and t = 2n + 1), we have that with probability at least 1— 4d 2 n(2n + 1)(24c)', every odd layer has a working path from left side boundary to right side boundary (thus through the input or the output in this layer). Each even layer is a 2n x (4n + 1) grid. Applying Lemma 5.3 (setting r = n and t = 4n+1), we have that with probability at least 1— 2d i n(4n+1)(288c)n, every even layer contains n vertex-disjoint intact paths from the left side boundary to the right side boundary. Imagine vertically partitioning N into three sections. The left section consists of vertices in the left hand side of the inputs and outputs. The middle section consists of 2n inputs and outputs. The rest constitutes the right section. The left section and the right section are 2n x (4n 2 +2nv) grids. Applying Lemma 5.3 (setting r = n and t = 4n 2 +2nv), we have that with probability at least 1 — d i (4n 2 + 2nv)(288e)n, the left section contains n vertex-disjoint intact paths running from the top boundary to the bottom boundary; and with the same probability, the right section contains n vertex-disjoint intact paths running from the top boundary to the bottom boundary. Call these working paths and vertex-disjoint intact paths in the (horizontal) layers and (vertical) sections tracks. Let the subnetwork induced by these tracks be frame(N). Note that any two tracks of two adjacent layers are vertex-disjoint, since one of the two tracks is intact. Similarly, any two tracks of two different sections are vertex-disjoint. Therefore, frame(N) is a planar rearrangeable n-network as shown in Lemma 5.2. Theorem 5.1 For any arbitrarily small b, when n is sufficiently large, network N is a planar CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^80 (10 -4 , (5)-rearrangeable n-network with at most 33n 3 edges and 2 log 2 n degree, having 2n vertices with degree greater than 4. Proof. Network A is planar, contains at most 2(4n 2 + 2n log 2 n)(4n + 1) < 33n 3 edges for all sufficiently large n. Network H has a maximum degree 2 log 2 n, and only 2n vertices in H (inputs and outputs) have degree greater than 4. The probability that network H does not contain a planar rearrangeable n-network subnetwork frame (H) is at most 4d2 n(2n + 1)(24E)" + 2d i n(4n -I- 1)(288c)n + 2d 1 (4 n 2 + 2rw)(288c)n. This value can be arbitrarily small when n = 2 1' is sufficiently large, given E = 10 -4 . A Corollary 5.3 Given 0 < c < 1/2 and 0 <45 <1, there is an explicit construction for a planar (c,6)-rearrangeable n-network with 0(n 3 ) edges and 0(log n) degree, having 0(n) vertices with degree greater than 4. 5.4 A Fault-Tolerant Superconcentrator In this section, we assume that c = 10 -5 , and we construct planar (10 -5 ,5)-n-superconcentrators for arbitrarily small 6. The networks contain 0(n 2 ) edges and have degree 0(log n), with 0(n) vertices having degree greater than 6. Similarly to the situation of rearrangeable networks, let us first review a result on planar n-superconcentrators of reliable edges. Lemma 5.5 Join n inputs to the n vertices on the left hand boundary of an n x n grid via n edges and n outputs to the n vertices on the bottom boundary of the grid via n edges in any CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^81 one-to-one correspondence. The resulting graph is a planar n-superconcentrator. Proof. It is straightforward. A Let n = 2". The construction of the planar (c,b)-n-superconcentrator is described in terms of stages. The n inputs make up stage 0. Stage 1 comprises 2n disjoint sets of v vertices called group(j), for 1 < j < 2n. Input i (1 < i < n) is adjacent to the v vertices of group(2i — 1) via v edges. Join the 2nv vertices in stage 1 on a path, i.e., a chain of 2nv — 1 edges, with vertices in group(i) appearing on top of that in group(i -I- 1). For any two adjacent vertices in stage 1, if they are in the same set group(i), they have edges leading to a common vertex in stage 2. Thus stage 2 contains 2nv — 2n = 2n(v — 1) vertices (each set group(i) leads to v — 1 vertices in stage 2). Recursively say a vertex is a descendant of group(i) if the two vertices adjacent to it in the previous stage are in group(i) or descendants of group(i). Join the 2n(v — 1) vertices in stage 2 by a chain of 2n(v — 1) — 1 edges, with descendants of group(i) appearing on top of that of group(i + 1). In similar ways, construct stage 3, and so on. The number of vertices in each stage decreases by 2n as one more stage is constructed. Stop the construction after stage v. Stage v contains 2n vertices with the number of descendants of each group(i) shrinking to 1. Taking the 2n vertices of stage v as the left hand boundary, construct a 2n x 2n grid. With the bottom boundary of the grid, associate a (v+ 1)-stage subnetwork described above, but replace the n inputs by n outputs. Call this network M. (See Figure 5.2.) The technique presented in Lemma 5.3 is successful in dealing with message flows with unspecified sources. In order to analyze the fault tolerance of M, we shall need new techniques (presented in Lemma 5.6, Corollary 5.4 and Lemma 5.7) to cope with message flows with CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^82 O Figure 5.2: The planar (c, 6)-n-superconcentrator M specified sources. Lemma 5.6 Given a planar graph G, let vo ,v 1 ,• • •, v n be a set of vertices occurring anticlockwise around the boundary of the exterior face of G. There are n paths vi —+ vo in G (for i = 1, • • • ,n) that are vertex-disjoint except at vo if for every interval {vi, vi +i , • • • , (1 < i < n and 1 < r < n — i 1), there are r paths from {vi, vi+i, • • •,vi-Fr—i} to vo , vertexdisjoint except for their ends (i.e, the starting vertices and ending vertices). Note: These r paths do not necessarily originate at distinct vertices (i.e., two or more of them may originate at the same vi). Proof. Necessity of the condition is obvious. Before we prove the sufficiency, we need some definitions. Given a set of paths {L 1 , • • •, L p } on the exterior face of G, vertex-disjoint except at their ends, we define a full anti-symmetric order relation lies-above among them. We say Li lies-above Li +1 , for i = 1, • • • ,p — 1, if Upperboundary, L 1 , • • • , L p form an anti-clockwise order, where Upperboundary is the segment between v 1 and vo of the boundary of the exterior CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^83 face that contains no vi, i = 2, • • • , n. Given two simple paths A and B on the exterior face of G, let cap(A, B) be a new path by starting from A's initial vertex and, between each two consecutive intersecting vertices of A and B, choosing the segment that lies above. Similarly we define cup(A, B) except we choose the segment that lies below (that is, the segment that does not lie above). To prove sufficiency of the condition, we do induction on n. The case when n = 1 is trivially true. Assuming the proposition is true when n = k, we consider the case n = k + 1. By the condition, there are k + 1 paths Ri, i = 1, • • • , k + 1, from {v i , v2 , • • -, vic+1 } to vo vertex-disjoint except at their ends, and for every interval {vi, • • • , vj + ,}, there are r paths of Ri originated from the interval (some of them may originate at a same vi). Without loss of generality, we assume that Ri lies above Ri +i . By induction hypothesis, we have k paths Pi : vi ---> vo for i = 1, • • • , k, vertex-disjoint except at v o , and k paths Qi: vi ---* vo for i = 2, • • •, k + 1, vertex-disjoint except at v o . Without loss of generality, we assume all Pi's, Q i's and Ri's are simple. Let T1 = cap(Pi , R 1 ), Ti = cap(cup(Pi, Q i), Ri) for i = 2, • • • , k, and Tk+1 = CaP(Q k+i, Rk+i)• Thus Ti (i = 1, • • • ,k + 1) is a simple path from vi to vo , and T1 , • • • , Tk+i are vertex-disjoint except at v o . This completes the induction. L Applying Lemma 5.6 to network M immediately suggests Corollary 5.4. Corollary 5.4 If given any r consecutive inputs i, i+1, • • •, i+r-1 of M, for any 1 < i < n and 1 < r < n — i + 1, there are r working paths from a subset of the r inputs to the right side boundary of the grid, vertex-disjoint except initial vertices, then there are n vertex-disjoint working paths from the n inputs to the right side boundary of the grid. CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^84 Corollary 5.4 shows that to ensure the existence of n vertex-disjoint working paths from n inputs to the right side boundary of the grid, besides the distinctness of n inputs (that is, no two inputs contract to one vertex, due to a shorted path linking the two inputs), one needs to examine the truths of at most n + (n — 1) + • • • -I- 1 = n(n + 1)/2 < n 2 "conditions". By a "condition", we mean an assertion of the form "there are r working paths from a subset of r consecutive inputs to the right side boundary of the grid, vertex-disjoint except initial vertices". To determine the truth of a condition, the technique presented in Lemma 5.3 (dealing with message flow with unspecified sources) is sufficient. (The success of this method in dealing with message flows with specified sources is ascribed to the planarity of the network. In the non-planar general case, up to 2n conditions, i.e., any set of r inputs, have to be considered.) . Let M 1 be the subnetwork consisting of the (v +1)-stage subnetwork with the n inputs and the 2n x 2n grid. The following lemma estimates the probability of a condition being true. Lemma 5.7 Given r consecutive inputs i, i+1, • • •, i+r-1, the probability that there exist r working paths in M 1 from a subset of r consecutive inputs to the right side boundary of the grid, vertex-disjoint except initial vertices, is at least 1 — d3 (2n + v)(432e) 42 , where d3 = 1/(1 — (4320) 112 . Proof. Virtually the same arguments as of Lemma 5.3 apply. Special things that need to be noted are (1) each vertex in M 1 is adjacent to at most 6 edges, (2) any cut set separating inputs i, i + 1, • • • , i + r — 1 and the right hand boundary contains at least / > min{v + 2r — 1, 2n} vertices, (3) 1 — (r — 1) > 1/2 > v, and (4) the number of places for each cut set to start at is CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^85 at most 2n + v. A Lemma 5.8 With probability at most 4d4n 2 v 2 (6c)", where d4 = 1/(1 - 6c), there exist two input(s) and output(s) that contract to a single vertex. Proof. It is the same as the proof of Lemma 4.7. Special things that need to be noted are (1) any simple path that links two input(s) and output(s) must contain at least v edges, and (2) for any 1 > v, there are at most v 2 6 1-2 < v 2 6 1 such paths of length 1, since the degree of inputs and outputs is v, and that of the other vertices is at most 6. A Theorem 5.2 For any arbitrarily mall 6, when n is sufficiently large, M is a planar (10 -5 ,6) n-superconcentrator with at most 9n 2 edges and log 2 n degree, having at most 2n vertices with degree greater than 6. Proof. Network M is planar, contains at most 2(2n(3v 2 /2))+8n 2 < 9n 2 edges for all sufficiently large n. Network M has a maximum degree log 2 n, and only 2n vertices in M (inputs and outputs) have degree greater than 6. By Lemma 5.8, the probability that 2n inputs and outputs remain distinct is at least 1 - 4d4n 2 v 2 (6c)v. By Lemma 5.7, the probability that there exist n vertex-disjoint working paths from the n inputs to the right side boundary of the grid is at least 1 - d3n 2 (2n + v)(432c) 42 , since we have at most n 2 conditions to examine; a similar property holds for the vertex-disjoint working paths from the n outputs to the top boundary of the grid. Thus by Lemma 5.5, with probability at least 1- 2d3n 2 (2n + v)(432c) 42 -4d4n 2 v 2 (6c)", network M is a planar n-superconcentrator. The value 2d3n 2 (2n + v)(432c) 42 + 4d4n2v2(6c)v CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS ^86 can be arbitrarily small when n = 2" is sufficiently large, given e = 10 -5 . 0 Corollary 5.5 Given 0 < e < 1/2 and 0 < b' < 1, there is an explicit construction for a planar (c,6)-n-superconcentrator with 0(n 2 ) edges and O(log n) degree, having 0(n) vertices with degree greater than 6. Chapter 6 Related Graph Theory and Combinatorics Results In this chapter, we summarize some graph theory and combinatorics results obtained along the course of this research. These results, beyond the immediate applications in switching networks, have their own significance in graph theory and combinatorics. 6.1 Edge-Disjoint Paths in a Tree Lemma 4.1 of Chapter 4 shows that given a tree with 1 leaves, in which each internal node has degree at least 3, there exist 1/42 edge-disjoint paths each containing at most 3 edges and having 2 leaves as its ends. Define II(/, d) to be the set of trees with 1 leaves and degree at least d for each internal node. Given T E 11(1, d), let T(h) be the maximum number of edge-disjoint paths in T, such that each path contains at most h edges and has 2 leaves as its ends. Define p(1, d, h) = in In---TE11(1,d){T(h )}. Let r(d, h) =^P(11'h) Lemma 6.1 The limit r(d, h) exists. 87 CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^88 Proof. We observe that p(n rn, d, h) < p(n, d, h) p(m, d, h) + 2, for all n > 1 and m > 1. To see this, let Tn and Tim, be two "minimum" trees in 11(n, d) and II(m, d), respectively. That is, Tn and Tm satisfy Tn (h) = p(n, d, h) and Tm (h) = p(m, d, h), where Ti(h) is the maximum number of edge-disjoint paths in T.; with each path joining 2 leaves and having length at most h. Let 6 and E2 be two arbitrary leaves in Tn and Tm, and v1 and v2 be the parents of 6 and e2, respectively. Delete 6 and e2, and join v 1 and v 2 by an edge. The resulting graph is a tree in II(n m — 2,d). Call it Tn+m_2. Clearly p(n m — 2, d, h) < Tn+m _ 2 (h) < Tn (h)-1- Tm (h)-1- 1 = p(n,d,h)-1- p(m,d,h)-F 1, since the number of paths in a set of edge-disjoint paths in Tn i. m _2 that joins two leaves, one in Tn and one in Tm , is at most one (the path must contain edge (v 1 , v 2 )). Thus the observation follows from p(1 + 2, d, h) < p(1, d, h) + 1, for all 1 > 1. Let ai = p(i, d, h) + 2. We have an-Fm < a n + a m , for all n > 1 and m > 1. By Fekete's Lemma (see [PS72], p. 23 and p. 198, problem 98), (till either converges or diverges to —oo, as 1^oo. That is, p(1,d,h)11= (ai — 2)/1 either converges or diverges to —oo, as 1 oo. But the second case is impossible, since p(1, d, h) > 0. A It is clear that r(d, h) is a function monotone increasing with respect to either parameter, d or h. To determine the value of r(d, h) in the general case is an interesting open problem. We present here some partial results. Theorem 6.1 r(3,3)= 1/4. Theorem 6.1 is concluded from the following two Lemmas. CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^89 Lemma 6.2 Given a tree T of I leaves, in which each internal node has degree at least 3, there exist 114 edge-disjoint paths, each joining 2 leaves and containing at most 3 edges. Proof. As in the proof of Lemma 4.1, we may assume that each internal node has degree exactly 3. The case I < 5 is trivial. We assume 1 > 5. The number of internal nodes is I — 2. Say an internal node is a type-i internal node (and for abbreviation type-i node), 0 < i < 2, if there are i leaves among its 3 neighbors. A leaf is a type-i leaf if it is adjacent to a type-i node, 1 < i < 2. Let ri be the number of type-i nodes in T, 0 < i < 2. We have r o +r 1 -Fr 2 = 1-2 and r 1 -1-2r 2 = 1. This implies that r 2 = r o + 2. For each type-1 leaf e, denote by TT the subtree consisting of all vertices having distance at most 3 from e. Let x o , x i , x 2 , x 3 and x 4 be the number of Ta's that contain no leaf, one leaf, two non-sibling leaves, two sibling leaves and three leaves among the four vertices that have distance 3 from e, respectively. For the simplicity of notation, we refer to the corresponding leaf E as an "x 0 , x i , x 2 , x 3 or x 4 leaf" and to the corresponding subtree TT "of the x o , x i , x 2 , x 3 or x 4 kind." (See Figure 6.1.) We observe that in each of the xi + x 2 + x 4 o : Leaf^o : Internal node Figure 6.1: TT of the xo, x 1 , x2, x3 and x4 kind subtrees TT of the x i , x 2 or x 4 kind, there is a path of 3 edges having e and another xi, x2 CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^90 or x 4 leaf ik as its ends. Note there are at most 2 other x 1 , x 2 or x 4 leaves (in or adjacent to having distance 3 from e or ye. Thus there are at least (x 1 + x2 + x4)/4 vertex-disjoint paths in T, each containing 3 edges and having 2 leaves as its ends. On the other hand, the 2r 2 leaves adjacent to r 2 type-2 nodes form r2 vertex-disjoint paths in T, each containing 2 edges and having 2 leaves as its ends. And these r 2 paths of 2 edges are vertex-disoint from the above (x 1 + x 2 + x 4 )/4 paths of 3 edges. Therefore, the number of vertex-disjoint paths in T, such that each path joins 2 leaves and contains at most 3 edges is at least (x 1 + x 2 + x 4 )/4 + r 2 . Note that in each of the subtrees TT of the x 3 kind, there exists a type-2 node and, this type-2 node can be contained in only one Te of the x 3 kind (see II of the x3 kind in Figure 6.1). Thus x 3 < r 2 . Next we shall show that x o < r 2 . To see this, we (1) arbitrarily choose a type-2 node 7 (the existence of y is guaranteed by r 2 > r o + 2 > 2), and, (2) suspend the tree T from 7 as a root. Call the new rooted tree Troot. Note that in Tro ot vertices (internal nodes and leaves) are leveled in accordance with their distance from -y. In Troot, the sibling of each x o leaf e is a type-0 node 77, and this e is the only sibling of 77 (see Te of the x o kind in Figure 6.1). Thus x o < r o < r 2 . Therefore the number of vertex-disjoint paths in T, each joining 2 leaves and containing at most 3 edges is (xi + x2 + x4)/4 + rz = (xi + x2 + x4 + 4r2)/4 > (x0 + x1 + X2 + X3 + X4 + = (r 1 + 2r 2 )/4 = 1/4. This completes our proof. A 2r2)/4 CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^91 Corollary 6.1 r(3,3) > 1/4. Lemma 6.3 r(3, 3) < 1/4. Proof. We recursively construct a sequence of trees T 1 , T2, • • as illustrated in Figure 6.2 and Figure 6.3. Let ti be the number of leaves in Ti and ai the number of leaves in Ai. Thus Figure 6.2: Tree T1 for r(3,3) A;+; Figure 6.3: Tree T1 +1 for r(3, 3) ti = ai +1, for i = 1, 2, • • It is clear that ai +i = 2ai + 2, for all i > 1, and a l = 6. Let bi and CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^92 ci be the maximum number of edge-disjoint paths in Ti and Ai, respectively, each containing at most 3 edges and having 2 leaves as its ends. It is obvious that ci < bi < + 1, and c 1 = 2. We observe that ci +i = 2ci for all i > 1. To see this, consider any 2 leaves e l and e2 of Ai +1 . If S1 and e2 are not in the same subtree Ai, then the distance from e l to 6 is at least 4. Thus any path in Ai +i containing at most 3 edges and having 2 leaves as its ends must be confined in one of the 2 subtree Ai's. From the recursions ai+i = 2ai + 2 and Ci+i = 2Ci and the boundary values al = 6 and Cl = 2, we conclude that ai = 2 1 + 2 — 2 and ci = 2i. Therefore r(3,3) < limi_,,„, i = limi, a = 1/4. ZS, The proof technique of Lemma 6.3 can be extended to obtain the following result. Proposition 6.1 For any h > 3, 1 r(3,h) < ki if h is odd 3h-5 6h-4 if h is even Proof. In the case of odd h, let us assume h = 2k + 1. We recursively construct a sequence of trees T1, T2, • • •. See Figure 6.4 and Figure 6.5. Let ti be the number of leaves in Ti and ai the number of leaves in Ai. We have ti = ai +1, for i = 1, 2, • • It is clear that ai + i = 2ai + 4k — 2, for all i > 1, and a l = 4k + 2. Let bi and ci be the maximum number of edge-disjoint paths in Ti and Ai, respectively, each containing at most 2k + 1 edges and having 2 leaves as its ends. CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^93 Figure 6.4: Tree T1 for r(3, 2k + 1) Figure 6.5: Tree T1 + 1 for r(3, 2k + 1) ^ CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^94 As before, we have ci < bi < ci +1, and we have c 1 = 2k. It is clear that ci +1 = 2ci + 2k — 2 for all i > 1. From the recursions = 2ai + 4k — 2 and ci+1 = 2ci + 2k — 2 and the boundary values a l = 4k + 2 and c 1 = 2k, we have ai = k2 i + 2 — (4k — 2) and ci = k2 i + 1 — 2` — (2k — 2). Therefore ^t r(3, h) = r(3, 2k + 1) < 2k — 1^h — 2 lim b•^ i^ai^4k^2h — 2 . In the case of even h where h = 2k, the sequence of trees T1 , T2, • • • we construct is illustrated in Figure 6.6 and Figure 6.7. Let ti, ai, bi and ci have the same meanings as in the odd h case. The new recursions we have now are = 3ai + 4k — 4 and ci +1 = 3ci + 2k — 3. And the new boundary values are a l = 4k and Cl = 2k — 1. Solving these recursions, we have ai = 2k3 2 — 2 3i -1 — (2k — 2) and ci = k3 i r(3, h) = r(3, 2k) 5.3'222k-3 Therefore ci^6k — 5 — 3h — 5 < tlimo o a i 12k — 4 6h- 4 CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^95 Figure 6.6: Tree T1 for r(3, 2k) Figure 6.7: Tree Ti+i for r(3,2k) CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^96 Similar techniques can be applied to construct trees with arbitrary internal degree, thus yielding a general upper bound of r(d, h) for any d and h. Corollary 6.2 For any d > 3 and h > 3, (d-1)(4-2)k —1 2(d-1)(d-2)k if h = 2k + 1 and d is odd d(d-1)(d-21k—d 2d(d-1)(d-2)k-2 if h = 2k + 1 and d is even dfd-1)1c/-2)k—(d 2 —d-1) 2d(d-1)(d-2)k-2(d 2 —2d-1) if h = 2k and d is odd d(d-1)(d-2)k—(d 2 —d-1) 2d(d-1)(d-2)k-2d(d-2) if h = 2k and d is even r(d,h) < Proof. We shall only present the recursive constructions for the trees for the upper bound. For the case of h = 2k +1 and odd d, see Figure 6.8 and 6.9. For the case of h = 2k +1 and even d, see Figure 6.10 and 6.11. For the case of h = 2k and odd d, see Figure 6.12 and 6.13. For the case of h = 2k and even d, see Figure 6.14 and 6.15. Figure 6.8: Tree T1 with h = 2k +1 and odd d CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^97 Figure 6.9: Tree T1 4. 1 with h = 2k + 1 and odd d Figure 6.10: Tree T1 with h = 2k +1 and even d CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^98 Figure 6.11: Tree Ti+1 with h = 2k + 1 and even d Ei Ai Figure 6.12: Tree T1 with h = 2k and odd d CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^99 Ai+1 Figure 6.13: Tree Ti+1 with h = 2k and odd d T Ai Figure 6.14: Tree T1 with h = 2k and even d CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^100 Figure 6.15: Tree Ti + 1 with h = 2k and even d 6. As mentioned earlier, r(d, h) is monotone increasing with respect to either parameter d or h. Therefore, for any fixed h > 2, limd„, r(d, h) exists, since 1/2 is an upper bound for any r(d, h). Similarly, limh_, c, r(d, h) exists for any d > 2. We are able to determine limd_,,, r(d, h) for any h. Theorem 6.2 For any fixed h > 2, lim r(d, h) = 1/2. d—+ oo This result is an immediate conclusion of the following proposition. Proposition 6.2 For any d > 4, r(d, 2) > L-44. CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^101 Proof. Suppose T is an arbitrary tree in II(1, d), we shall show by induction on the number of internal nodes in T, that there exists at least 1 ==1 1 2d-4 edge-disjoint paths in T, each joining 2 leaves and containing 2 edges. Let r be the number of internal nodes in T. The base case where r = 1 (that is, a "star" — one internal node and 1 leaves) is trivial: there are L//2 .1 > (1 — 1)/2 edge-disjoint paths, each joining 2 leaves and containing 2 edges; and (1-1)/2 > (d-4)1/(2d-4), since 1 > d. For r > 1, we have 1+ rd < 2(1 + r — 1), since 1+ rd is at most the sum of degrees over all vertices in T and 1 + r — 1 is the number of edges in T. Therefore, (d — 2)r < / — 2.^ (6.1) Thus there exist at least one internal nodes E which is adjacent to at least d —1 leaves, otherwise condition (6.1) would be violated. The x (x > d — 1) leaves adjacent to e can form Lx/2 .1 > (x — 1)/2 edge-disjoint paths, each containing 2 edges and having 2 leaves as its ends. Remove these x leaves and treat e as a leaf. The resulting graph is a tree T' E II(/ — x + 1, d) with r — 1 internal nodes. By induction, there exist at least ( d-4)(1--x +1) 2d-4 ^edge-disjoint paths, each containing 2 edges and having 2 leaves of T' as its ends. These paths are edge-disjoint from the previous (x — 1)/d paths (paths pairing leaves adjacent to e), and all leaves of T' but e are leaves of T. Therefore, there are at least (x — 1)/2 + (d — 4)(1 — x +1) 1> d — 4 1 2d — 4 2d — 4 edge-disjoint paths in T, each joining 2 leaves and containing 2 edges. A Intuition tells us that a result analogous to Theorem 6.2 with respect to h may exist. We are not, however, able to prove or disprove the correctness of our intuition. CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS ^102 6.2 Vertex-Disjoint Paths in a Planar Graph In Chapter 5, Lemma 5.6 states Lemma 5.6 Given a planar graph G, let vo , v 1 , • • •, vn be a set of vertices occurring anticlockwise around the boundary of the exterior face of G. There are n paths vi .- vo in G (for i = 1,- • • ,n), such that they are vertex-disjoint except at v o if for every interval {N, vi+i , • • • , Vii. r _i } (1 < i < n and 1 < r < n-i+1), there are r paths from {vi, vi +i , • • • , vi + ,._ 1 } to vo , vertex-disjoint except for their ends (i.e., the starting vertices and ending vertices). Note: These r paths do not necessarily originate at distinct vertices (i.e., two or more of them may originate at the same vj). In a similar way, we are able to prove Theorem 6.3 Given a planar graph G, let v1 , • • • , vn , u n , • • • , u 1 be a set of 2n vertices occurring anti-clockwise around the boundary of the exterior face of G. There are n vertexdisjoint paths vi --* ui in G (for i = 1, • • • ,n) if for every interval {vi, 14-1-1,• • • ,vi-Fr--i} and {ui,ui-I-1, • • • ,uil-r-i} (1 < i < n and 1 < r < n - i + 1), there are r paths from {vi,vi +1 ,• • • ,v i+ ,- 1 } to fui,ai+1,• • • ,uil-r-il, vertex-disjoint except for their ends. Theorem 6.3 is useful to deal with message flows in planar graphs with specified sources and specified destinations. Bibliography [A82]^R. Aleliunas, "Randomized Parallel Communication", ACM Symp. on Principles of Distributed Computing, 1 (1982) 60-72. [AHU74]^A. V. Aho, J. E. Hoperoft and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). [AKL+85] A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial and A. Wigderson, "Multi-layer Grid Embeddings", IEEE Symp. on Foundations of Computer Science, 26 (1985) 186-196. [AKL+91] A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial and A. Wigderson, "A Lower Bound on the Area of Permutation Layouts", Algorithmica, Vol. 6, No. 2 (1991) 241-255. [AKS83a] M. Ajtai, J. Komi& and E. Szemeredi, "Sorting in clog n Parallel Steps", Combinatorica 3 (1983) 1-19. [AKS83b] M. Ajtai, J. Komi& and E. Szemeredi, "An O(nlogn) Sorting Network", ACM Symp. on Theory of Computing 15 (1883) 1-9. [AKS91]^A. Aggarwal, M. Klawe and P. Shor, "Multilayer Grid Embeddings for VLSI", Algorithmica, Vol. 6, No. 1 (1991) 129-151. [ALM90]^S. Arora, T. Leighton and B. Maggs, "On-Line Algorithms for Path Selection in a Nonblocking Network", ACM Symp. on Theory of Computing, 22 (1990) 149-158. [B64]^V. E. Bend, "Optimal Rearrangeable Multistage Connecting Networks", Bell Sys. Tech. J., 43 (1964) 1641-1656. [BG87]^D. Bertsekas and R. Gallager, Data Networks, (Prentice-Hall, Inc., Englewood Cliffs, NJ 1987). [BLM+92] G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith and M. Zagha, "A Comparison of Sorting Algorithms for the Connection Machine CM-2", ACM Symp. on Parallel Algorithms and Architectures, 3 (1991) 3-16. 103 BIBLIOGRAPHY^ 104 [BMR91]^B. Bhargava, E. Mafia and J. Riedl, "Communication in the RAID Distributed Database System", Computer Networks and ISDN Systems, 21 (1991) 81-92. [BP74]^L. A. Bassalygo and M. S. Pinsker, "Complexity of Optimum Non-blocking Switching Network without Reconnections. Problems of Info. Transmission, 9 (1974) 6466. [BRS+90] P. Banerjee, J. T. Rahmeh, C. Stunkel, V. S. Nair, K. Roy, V. Balasubramanian and J. A. Abraham, "Algorithm-Based Fault Tolerance on a Hypercube Multiprocessor", IEEE Trans. Comput., Vol. 39, No. 9 (Sept. 1990) 1132-1145. [BW89]^A. E. Barbour and A. S. Wojcik, "A General, Constructive Approach to Faulttolerant Design Using Redundancy", IEEE Trans. Comput., Vol. 38, No. 1 (Jan. 1989) 15-29. [C53]^C. Clos, "A Study of Non-blocking Networks", Bell Sys. Tech. J., 32 (1953) 406424. [C71]^D. G. Cantor, "On Non-blocking Switching Networks", Networks, 1 (1971) 367-377. [C88]^M. I. Cole, "Algorithmic Skeletons: A Structured Approach to the Management of Parallel Computation", Ph. D. Thesis, Computer Science, Univ. of Edinburgh, Oct. 1988. [CH77]^F. R. K. Chung and F. K. Hwang, "On Blocking Probabilities for Switching Networks", Bell Sys. Tech. J., 56 (1977) 1431-1446. [CH80]^F. R. K. Chung and F. K. Hwang, "The Connection Patterns of Two Complete Binary Trees", SIAM J. Discr. Math., 1 (1980) 322-335. [CGG+85] W. Crowther, J. Goodhue, R. Gurwitz, R. Rettberg and R. Thomas, "The Butterfly Parallel Processor", Newsletter, Computer Architecture Technical Committee, IEEE Computer Society (Sept./Dec. 1985) 18-45. [CL86]^G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition (Wadsworth, Inc., Belmont, CA, 1986). [CS78]^M. Culter and Y. Shiloach, "Permutation Layout", Networks, Vol. 8 (1978) 253278. [CS90]^M. Chen and K. G. Shih, "Adaptive Fault-Tolerant Routing in Hypercube Multicomputers", IEEE Trans. Comput., Vol. 39, No. 12 (Dec. 1990) 1406-1416. [DES74]^De Bruijn, N. G., P. Erdiis and J. Spencer, "Solution 350", Nieuw Arch. Wisk., 22 (1974) 94-109. BIBLIOGRAPHY^ 105 [DDPW83] D. Dolev, C. Dwork, N. Pippenger and A. Wigderson, "Superconcentrators, Generalizers and Generalized Connectors with Limited Depth", ACM Symp. on Theory of Computing, 15 (1983) 42-51. [DSS90]^G. Ding, A. Schrijver and P.D. Seymour, " Disjoint Paths in a Planar Graph — A General Theorem", Tech. Report BS-R9012, Centrum voor Wiskunde en Informatica, June 1990. ' [En18]^T. Engset, "Die Wahrscheinlichkeitsrechnung zur Bestimmung der Wahleranzahl in Automatischen Fernsprechamtern", Electroteck. Z., 31 (1918) 304-305. [Er18]^A. K. Erlang, "Solution of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges", Post Office Elect. Eng. J., 10 (1918) 189-197. [FFP88]^P. Feldman, J. Friedman and N. Pippenger, "Wide-Sense Non-Blocking Networks", SIAM J. Discr. Math., 1 (1988) 158-173. [GG81]^0. Gabber and Z. Galil, "Explicit Constructions of Linear-Sized Superconcentrators", J. Computer and System Sciences, 22 (1981), 407-420. [GG84]^J. Greene and A. E. Gamal, "Configuration of VLSI Arrays in the Presence of Defects", J. ACM, Vol. 31, No. 4 (Oct. 1984), 694-717. [GL73]^L. R. Goke and G. J. Lipovski, "Banyan Networks for Partitioning Multiprocessor Systems", IEEE Symp. on Computer Architectures, 1 (1973) 8-21. [1163]^T. E. Harris, The Theory of Branching Processes (Springer-Verlag, Berlin, 1963). [HD89]^K. Hwang and D. DeGroot (editors), Parrallel Processing for Supercomputers and Artificial Intelligence (McGraw-Hill Publishing Inc., 1989). [11J88]^R. W. Hockney and C. R. Jesshope, Parrallel Computers 2: Architecture, Programming and Algorithms (IOP Publishing Ltd., Bristol, England, 1988). [159]^N. Ikeno, "A Limit on Crosspoint Number", IRS Trans. on Info. Theory (Spec. Suppl.), 5 (1959) 187-196. [K75]^I. V. Koverninskir, "Estimation of the Blocking Probability for Switching Circuits by Means of Probability Graphs", Problems of Info. Transmission, 11 (1975)63-71. [KKA90]^A. N. Kashper, S. S. Katz and G. R. Ash, "Robust Design for Switched Digital Services in a Worldwide Intelligent Network", Computer Networks and ISDN Systems, 20 (1990) 81-88. [KKL+90] C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Malenkovic, P. Raghavan, S. Rao, C. Thomborson and A. Tsantilas, "Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors", IEEE Symp. on Foundations of Computer Science, 31 (1990) 285-296. BIBLIOGRAPHY^ 106 [KL90]^M. Klawe and F. T. Leighton, "A Tight Lower Bound on the Size of Planar Permutation Networks", International Symp. SIGAL '90, in Lecture Notes in Comp. Sci. 450, 281-287; see also SIAM J. Discr. Math., 5 (1992) 558-563. [KS85]^B.E. Keiser and E. Stange, Digital Telephony and Network Integration (Van Nostrand Reinhold Company Inc., New York, NY, 1985). [L55] C. Y. Lee, "Analysis of Switching Networks", Bell Sys. Tech. J., 34 (1955) 12871315. [L56] P. Le Gall, "Etude du Blocage Dans les Systems de Commutation Telephoniques Automatique Utilisant des Commtateurs Electroniques du Type Crossbar", Ann. Telecomm. 11, 159-171, 180-194, 197 (1956). [L75]^D. H. Lawrie, "Access and Alignment of Data in an Array Processors", IEEE Trans. Comput. 24 (1975) 1145-1155. [L86]^M. Luby, "A Simple Parallel Algorithm for the Maximal Independent Set Problem", SIAM J. Computing, 15 (1986) 1036-1053. [L88]^M. Luby, "Removing Randomness in Parallel Computation without a Processor Penalty", IEEE Symp. on Foundations of Computer Science, 29 (1988) 162-173. [L90]^T. Lengauer, "VLSI Theory", Handbook of Theoretical Computer Science, Chapter 16, Edited by J. van Leeuwen (Elsevier Science Publishers B. V., 1990). [L92]^G. Lin, "Fault Tolerant Planar Communication Networks", ACM Symp. on Theory of Computing, 24 (1992) 133-139. [LAD+92] C. Leiserson, Z. S. Abuhamdeh, D. Douglas, C. R. Feynmann, M. Ganmukhi, J. Hill, W.D. Hillis, B. Kuszmaul, M. St. Pierre, D. Wells, M. Wong, S-W Yang and R. Zak, "The Network Architecture of the Connection Machine CM-5", ACM Symp. on Parallel Algorithms and Architectures, 4 (1992) 272-285. [LL82]^F. T. Leighton and C. E. Leiserson, "Wafer-Scale Integration of Systolic Arrays", IEEE Symp. on Foundations of Computer Science, 23 (1982) 297-311. [LM89]^T. Leighton and B. Maggs, "Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies", IEEE Symp. on Foundation of Computer Science, 30 (1989) 384-389. [LMT89]^T. Leighton, F. Makedon and I. Tollis, "A 2n — 2 Steps Algorithm for Routing in an n x n Array with Constant-Size Queues", ACM Symp. on Parallel Algorithms and Architectures, 1 (1989) 328-335. [LP91]^G. Lin and N. Pippenger, "Parallel Algorithms for Routing in Non-blocking Networks", ACM Symp. on Parallel Algorithms and Architectures, 3 (1991) 272-277, also accepted for publication by the journal Mathematical Systems Theory. BIBLIOGRAPHY^ 107 [LPS88]^A. Lubotzky, R. Phillips and P. Sarnak, "Ramanujan Graphs", Combinatorica, 8 (1988) 261-277. [LPV81]^G. Lev, N. Pippenger and L. G. Valiant, "A Fast Parallel Algorithm for Routing in Permutation Networks", IEEE Trans. on Computers, 30 (1981) 93-100. [LT79]^R. Lipton and R. Tarjan, "Applications of a Planar Separator Theorem", SIAM J. Appl. Math., 36 (1979) 177-189. [M75]^G. A. Margulis, "Explicit Constructions of Concentrators" (English Translation), Problems of Info. Transmission, 9 (1975) 325-332. [M90]^Fundamentals of Digital Switching, Second Edition, Edited by J. C. McDonald (Plenum Press, New York, NY 1990). [MS56]^E. Moore and E. Shannon, "Reliable Circuits Using Less Reliable Relays" (Part I and Part II), J. Franklin Inst., Vol. 262, No. 3 (Sept. 1956) 191-208 and No. 4 (Oct. 1956) 281-297. [NG90]^W. Najjar and J. L. Gaudiot, "Network Resilience: A Measure of Network Fault Tolerance", IEEE Trans. Comput., Vol. 39, No. 2 (Feb. 1990) 174-181. [P73]^N. Pippenger, "The Complexity Theory of Switching Networks", Ph. D. Thesis, Electrical Engineering, MIT, August 1973. [P75]^N. Pippenger, "On Crossbar Switching Networks", IEEE Trans. Commun. 23 (1975) 646-659. [P77]^N. Pippenger, "Superconcentrators", SIAM J. Computing, Vol. 6, No. 2, (1977) 298-304. [13 82A]^N. Pippenger, "Telephone Switching Networks", A MS Proc. Symp. Appl. Math., 26 (1982) 101-133. [P8213]^N. Pippenger, "Superconcentrators of Depth Two", J. Comput. System Sci., 24 (1982) 82-90. [P90] N. Pippenger, "Communication Networks", Handbook of Theoretical Computer Science, Chapter 15, Edited by J. van Leeuwen (Elsevier Science Publishers B. V., 1990). [P91] N. Pippenger, "The Blocking Probability of Spider-Web Networks", Random Structures and Algorithms, Vol. 2, No. 2 (1991) 121-149. [P92}^N. Pippenger, "The Asymptotic Optimality of Spider-Web Networks", Discr. Appl. Math., Vol. 37/38 (1992) 437-450. BIBLIOGRAPHY^ 108 [P173]^M. S. Pinsker, "On the Complexity of a Concentrator", Proc. 7th Internat. Teletraffic Congr. (1973) 318/1-4. [PL92]^N. Pippenger and G. Lin, "Fault-Tolerant Circuit-Switching Networks", ACM Symp. on Parallel Algorithms and Architectures, 4 (1992) 229-235, also accepted for publication by SIAM Journal on Discrete Mathematics. [PS72]^G. POlya and G. Szegii, Problems and Theorems in Analysis I (Springer-Verlag, Berlin, 1972). [PY82]^N. Pippenger and A. C. Yao, "Rearrangeable Networks with Limited Depth", SIAM J. Alg. Disc. Meth., Vol. 3, No. 4 (1982) 411-417. [R87]^A. G. Ranade, "How to Emulate Shared Memory", IEEE Symp. on Foundations of Computer Science, 28 (1987) 185-194. [R89]^P. Raghavan, "Robust Algorithms for Packet Routing in a Mesh", ACM Symp. on Parallel Algorithms and Architectures, 1 (1989) 344-350. [RS86]^N. Robertson and P. D. Seymour, "Graph Minors VI. Disjoint Paths Across a Disc", J. of Combinatorial Theory, Series B 41 (1986) 115-138. [RSV90]^U. Ramachandran, M. Solomon and M. K. Vernon, "Hardware Support for Interprocess Communication", IEEE Trans. Parallel and Distributed Systems, Vol. 1, No. 3 (July 1990) 318-329. [S50]^C. E. Shannon, "Memory Requirements in a Telephone Exchange", Bell Sys. Tech. J., 29 (1950) 343-349. [SB 77]^H. Sullivan and T. R. Bashkow, "A Large Scale, Homogeneous, Fully Distributed Parallel Machine, I", IEEE Symp. on Computer Architectures, 4 (1977) 105-177. [Si85]^H. J. Siegel, Interconnection Networks for Large-Scale Parallel Processing: Theory and Case Studies (D. C. Heath and Company, Lexington, MA/Toronto, Canada, 1985). [SP63]^J. Squire and S. Palais, "Programming and Design Considerations of a Highly Parallel Computer", AFIPS Conference Proc., 23 (1963) 395-400. [St85]^W. Stallings, Data and Computer Communications (Macmillan Publishing Company, New York, NY, 1985). [S87]^M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis (Addsion-Wesley Publishing Company, Reading, MA, 1987). [SW86]^M. Saks and A. Wigderson, "Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees", IEEE Symp. on Foundations of Computer Science, 27 (1986) 29-38. BIBLIOGRAPHY^ 109 [T68]^K. Takagi, "Design of Multi-Stage Link Systems by Means of Optimal Channel Graphs", Electr. and Comm. in Japan, 51-A (1968) 37-46. [T83]^M. Tarsi, "Optimal Search on Some Game Trees", J. ACM, 30 (1983) 389-396. [T89]^A. S. Tanenbaum, Computer Networks (Prentice-Hall, Inc., Englewood Cliffs, NJ, 1989). [TK82]^S. Tsukiyama and E. S. Kuh, "Double-Row Planar Routing and Permutation Layout", Networks, Vol. 12 (1982) 187-316. [U82]^E. Upfal, "Efficient Schemes for Parallel Communication", ACM Symp. on Principles of Distributed Computing, 1 (1982) 55-59. [U89]^E. Upfal, "An O(logN) Deterministic Packet Routing Scheme", ACM Symp. on Theory of Computing, 21 (1989) 241-250. [V75]^L. G. Valiant, "On Nonlinear Lower Bounds in Computational Complexity", ACM Symp. on Theory of Computing, 7 (1975) 45-53. [V82]^L. G. Valiant, "A Scheme for Fast Parallel Communication", SIAM J. Computing, 11 (1982) 350-361. [YU90]^Y. S. Youn and C. K. Un, "Performance Analysis of an Integrated Voice/Data Cutthrough Switching Network", Computer Networks and ISDN Systems, 21 (1990) 41-51.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the complexity theory of switching networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the complexity theory of switching networks Lin, Geng 1993
pdf
Page Metadata
Item Metadata
Title | On the complexity theory of switching networks |
Creator |
Lin, Geng |
Date Issued | 1993 |
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. |
Extent | 4568090 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-09-05 |
Provider | Vancouver : University of British Columbia Library |
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. |
DOI | 10.14288/1.0051348 |
URI | http://hdl.handle.net/2429/1662 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1993_spring_phd_lin_geng.pdf [ 4.36MB ]
- Metadata
- JSON: 831-1.0051348.json
- JSON-LD: 831-1.0051348-ld.json
- RDF/XML (Pretty): 831-1.0051348-rdf.xml
- RDF/JSON: 831-1.0051348-rdf.json
- Turtle: 831-1.0051348-turtle.txt
- N-Triples: 831-1.0051348-rdf-ntriples.txt
- Original Record: 831-1.0051348-source.json
- Full Text
- 831-1.0051348-fulltext.txt
- Citation
- 831-1.0051348.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051348/manifest