UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the complexity theory of switching networks Lin, Geng 1993

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

On the Complexity Theory of Switching NetworksbyGENG LINB.Sc., Beijing University, China, 1985M.Sc., Beijing University, China, 1988A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIES(DEPARTMENT OF COMPUTER SCIENCE)We accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIADecember 1992© Geng Lin, 1992In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature) Department of Co m p ukte The University of British ColumbiaVancouver, CanadaDate ^DC-L^rf:2^, I (-14 ZDE-6 (2/88)AbstractFast and efficient communications are essential to the success of large-scale multiprocessorparallel 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 con-struction 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 anycommunication path) and the degree (the largest fan-out of a switch); (b) the complexity ofthe 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 ofnon-blocking networks, and the design of the parallel routing algorithms. "Weakly optimal" heremeans 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 smallestpossible values. We also consider routing algorithms for networks with probabilistic traffic. Wepresent an optimal routing algorithm for series-parallel networks (which includes a broad rangeof 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. Weiiprove lower bounds for the size and depth of fault-tolerant non-blocking networks, rearrangeablenetworks and superconcentrators. And we explicitly construct such networks with optimal sizesand depths. We also consider fault-tolerant planar switching networks, which become attractivebecause of the rapid advances in VLSI technology. We prove lower bounds for the degrees ofvertices of fault-tolerant planar rearrangeable networks and superconcentrators. We constructsuch fault-tolerant planar networks with optimal sizes and degrees.iiiContentsAbstract^ iiContents ivList of Figures^ viAcknowledgement viii1 Introduction 11.1 Communications and Switching Networks ^ 11.1.1^Complexity Aspects of Switching Networks ^ 31.2 Circuit Switching and Packet Switching 41.2.1^Circuit Switching ^ 41.2.2^Packet Switching 51.3 A Historical Overview 61.4 Thesis outline ^ 122 Routing in Non-blocking Networks 142.1 Non-blocking Networks^ 142.2 The Networks ^ 192.3 A Randomized Parallel Algorithm ^ 212.4 The Data-structure for the Deterministic Parallel Algorithm ^ 232.5 A Deterministic Parallel Algorithm 263 Routing in Networks with Probabilistic Traffic 343.1 Probabilistic Model and Previous Work ^ 343.2 The Networks ^ 363.3 Main Result and the General Strategy 393.4 The Almost-Series Case ^ 403.5 The General Case 443.5.1^Routing Algorithms of the "Restricted Class" ^ 463.5.2^Routing Algorithms without Restriction 50iv4 Fault-Tolerant Switching Networks 524.1 The Switch Failure Model ^ 524.2 The Networks ^ 534.3 Fault-Tolerance 554.4 Main Result and the Overall Strategy ^ 574.5 The Lower Bounds ^ 584.6 The Upper Bounds 635 Fault-Tolerant Planar Switching Networks 725.1 Planar Networks ^ 725.2 A Lower Bound on the Degree ^ 755.3 A Fault-Tolerant Planar Rearrangeable Network ^ 765.4 A Fault-Tolerant Superconcentrator 806 Related Graph Theory and Combinatorics Results 876.1 Edge-Disjoint Paths in a Tree ^ 876.2 Vertex-Disjoint Paths in a Planar Graph ^ 1027 Bibliography 103vList of Figures1.1 An N x M crossbar ^  21.2 A Bend network with 16 inputs and 16 outputs ^  31.3 An interconnection network in a parallel computer  92.1 A Bend network with 8 inputs and 8 outputs (edges are direct from left to right) 192.2 Non-blocking network N+ with 4 inputs and 4 outputs (edges are directed fromleft to right) ^  203.1 A d x d crossbar  363.2 A network built from 2 x 2 crossbars and its acyclic directed graph representation 383.3 A series-parallel network with d = 2, k = 3 and 1 = 5 ^  383.4 Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 5 ^ 413.5 Channel graph in a series-parallel network with d = 2, k = 4 and 1 = 6  454.1 A bad leaf ^  604.2 An internal node collects at most 6 dollars ^  604.3 Each path collects at most 4 dollars from unlucky leaves ^ 614.4 A (4, 8)-directed grid ^  644.5 Network N  665.1 The planar (c, 5)-rearrangeable n-network N ^  775.2 The planar (E, 5)-n-superconcentrator M  826.1 T of the xo, x 1 , x2, x3 and x4 kind ^  896.2 Tree T1 for r(3, 3) ^  916.3 Tree Ti÷ i for r(3,3)  916.4 Tree T1 for r(3, 2k + 1)  936.5 Tree Ti+i for r(3,2k+ 1) ^  936.6 Tree Ti for r(3, 2k)  956.7 Tree Ti+i for r(3, 2k)  956.8 Tree T1 with h = 2k + 1 and odd d ^  966.9 Tree Ti..F1 with h = 2k + 1 and odd d  976.10 Tree T1 with h = 2k + 1 and even d  976.11 Tree Ti.fi with h = 2k + 1 and even d ^  98vi6.12 Tree T1 with h = 2k and odd d ^  986.13 Tree Ti+i with h = 2k and odd d  996.14 Tree Ti. with h = 2k and even d  996.15 Tree Ti+1 with h = 2k and even d^  100viiAcknowledgementsI am greatly indebted to my supervisor, Nick Pippenger. His deep insight and inexhaustiblemathematics tools are the constant impetus of this thesis. He not only supervised the productionof my thesis, he also taught me ways of doing research in Computer Science. He has done morethan usual one could ask of a supervisor. He made time to listen to me and discuss his ideaswith me whenever I asked for it — no matter how tight his schedule is; he taught me how topresent the results — from writing papers to giving seminars. His influence on me is far beyondmy 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 everyaspect 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 meto improve results in Theorem 6.1 of Chapter 6.I would like to thank other members of my supervisory committee, Richard Anstee, JackSnoeyink, and especially David Kirkpatrick, not only because they provided useful commentsand suggestions concerning my thesis, but also for the numerous discussions that have leadedme 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 bothresearch results and the presentation of this thesis. For example, discussions with Bruce resultedin upper bounds in Chapter 4.Many other people have contributed to the development of this thesis. Thanks go to AditiDhagat, Feng Gao, Michelangelo Grigni, Prabhakar Raghavan, Paul Seymour and Alan Wagner.Financial support was provided by the University and the Department through GraduateFellowships, Scholarships and Assistantships, and I acknowledge them for this regard. I thankall members of the department — staff, faculty and fellow students — who made the departmenta 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 areessential to the completion of this thesis. Finally, I can not express in words my love to my wifeYing. Without her endless love and support, none of these would have been possible.viiiChapter 1Introduction1.1 Communications and Switching NetworksFast and efficient communications are essential to the success of large-scale multiprocessor par-allel systems, distributed processing systems, and telecommunication systems. In massive mul-tiprocessor parallel computers, simultaneous communications among processors or between pro-cessors and memory modules are fundamental to achieve large-scale parallelism. In distributedprocessing systems, vast numbers of messages are exchanged across the systems to coordinatethe physically distributed processing components. In telecommunication systems, large amountsof voice, data and video are communicated simultaneously between subscribers. In each case,the essence of the communication problem is to provide efficient communications between twosets 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 one1CHAPTER 1. INTRODUCTION^ 2link to another (carries signals from one link to another). An input communicates with (sendssignals 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 (seeFigure 1.1). In a crossbar, each input or output is connected by a link, and each crosspoint isN inputsFigure 1.1: An N x M crossbara single-pole single-throw switch. Each pair of an input and an output can communicate viatheir "private" switch, regardless of the status of other switches. The difficulty with crossbarnetworks is the cost (measured by the number of switches). An N x M crossbar contains NMswitches. Therefore a crossbar in a parallel computer connecting 2 10 processing units with 2 10memory modules will require 220 switches. This scheme is also inflexible to the addition of newinputs 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 ofstages, and connected by links. For example, a switching network (due to Bene§ [B64]) withCHAPTER 1. INTRODUCTION^ 32 log2 N — 2 stages and 4N(log 2 N —1) (single-pole single-throw) switches provides simultaneousone-to-one communications between N inputs and N outputs (see Figure 1.2). This scheme hasa recursive construction, which makes it easy to accommodate more inputs and outputs (thatis to say, a network with a larger number of inputs and outputs can be constructed from a setof similarly structured networks as components, with each having a smaller number of inputsand outputs).--t a 2x2 crossbar ^ a linkFigure 1.2: A Bend network with 16 inputs and 16 outputs1.1.1 Complexity Aspects of Switching NetworksSwitching networks provide fast and efficient communications at reasonable cost in large-scalesystems. The theory for the construction of switching networks concerns (a) the complexityof the networks, as measured by the size (number of switches), the depth (largest number ofswitches on any communication path) and the degree (the largest fan-out of a switch) — theseCHAPTER 1. INTRODUCTION^ 4complexity measures reflect the cost, communication delay and wiring complexity of the net-works; (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 ultimatelydetermines the performance of the switching; and (c) the fault-tolerance of the networks.1.2 Circuit Switching and Packet SwitchingThere are two fundamental ways which a switching network may accomplish the simultaneoustransmission of messages. They are usually referred to as "circuit switching" and "packet switch-ing". 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 communi-cation requests. Messages move through these paths without interference with each other. Thesepaths may be dissolved later after the communication requests are satisfied, and their constituentcomponents 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 forwardedto avoid interference, or they may be discarded and later resent in the case that interferenceoccurs. Because of this store-and-forward nature, in packet switched networks, each switch isassociated with a queue (also known as a buffer) to temporarily store the passing messages.1.2.1 Circuit SwitchingCircuit switching is efficient in the case where the time scale of establishing the communicationpaths is considerably shorter than that of the transmission along the paths. Since a circuitCHAPTER 1. INTRODUCTION^ 5switched 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'sreal-time telecommunication systems are universally of the circuit switched type, although thereis great interest in the possibility of transmitting voice in real-time in packet form. In telecom-munication systems, large amounts of data, voice, and video are transmitted over dedicatedpaths. (See Briley [B83], Keiser and Strange [KS85], Schwartz [S87] and McDonald [M90] for adetailed coverage on telecommunication systems.) Besides telecommunication systems, circuitswitching is also used in some parallel architectures.The circuit switching technology can be implemented in the time division multiplexing or thespace 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 areaccomplished 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 aphysical link at different time slots during their transmission. Messages do not interfere witheach other, because their transmitting paths (circuits) are disjoint at any given time slot. SeeChapter 11 of Keiser and Strange and Chapter 5 of McDonald for a full explanation. For thetheoretical study in this thesis, however, there is not much difference. We shall only considerspace division.1.2.2 Packet SwitchingPacket switching has received considerable attention in the past. Many parallel computers usepacket switching to support interprocessor communications. (See Section 1.3 for more details.)CHAPTER 1. INTRODUCTION^ 6It is also widely used in computer communication networks. The Local Area Network (LAN) isan example. (See Bertsekas and Gallager [BG87], Stallings [St85] and Tanenbaum [T89] for adetailed study of computer communication networks.)1.3 A Historical OverviewSwitching networks have been studied for a long time, well before the occurrence of modernelectronic digital computers. They date back to the late 19th century, when the telephone wasinvented. Early works studied telephone switching problems concerning steams of calls arrivingwith 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 threedistinct communities: the telephone switching community, the parallel computer architecturecommunity and the Boolean circuit complexity community.The impulse from the telephone switching community came after the introduction of the firstcrossbar-type electromechanical switch in 1938. Shannon [S50] showed fundamental results intelephone switching concerning the size of some telephone networks. Clos [C53] introduced thenon-blocking network, and presented the first multistage construction for non-blocking networksfrom simple crossbars (i.e., crossbars with a fixed number of inputs and outputs). In a non-blocking network, a communication request to establish a path from an input to an output mayarrive at any time, and must be satisfied without disturbing previously existing communicationpaths in the network. On the other hand, if the network can satisfy the request by rearrangingthe existing paths (still maintaining the communication for these existing pairs, but throughCHAPTER 1. INTRODUCTION^ 7new paths), then the network is called a rearrangeable network. From automatic telephony'sperspective, a rearrangeable network and a non-blocking network can simultaneously carry anumber of calls equal to the number of inputs or outputs originated in any sequence, with orwithout the rearrangement of the existing paths. If the simultaneous connection capacity of anetwork for an arbitrary sequence of calls is less than the number of inputs or outputs, then thenetwork is called blocking network.To determine the blocking probability in such a blocking network is inherently complex. Theprobability of a link occupied at a given time depends not only on other links in the path, butalso 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 linkis independent of others, and analyzed the blocking probabilities of some multistage blockingnetworks with simple constructions.To construct non-blocking networks (including rearrangeable networks) with small size anddepth and to build blocking networks with simple topology and small blocking probability arethe main goals in telephone switching community. Later works on non-blocking networks andrearrangeable networks were given by Bend [B64], Cantor [C71], Pippenger [P73], Bassalygoand Pinsker [BP74], Pippenger and Yao [PY82], Feldman, Friedman and Pippenger [FFP88],Arora, Leighton and Maggs [ALM90], Lin and Pippenger [LP91]. While all these works focusedon 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^ 8mance, Ikeno [159] used the approximation model of Lee and Le Gall, and determined the limit-ing 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 conjec-tured that spider-web networks have a smaller blocking probability. Takagi [T68] described aclass of networks called rhyming networks, which include series-parallel networks and spider-webnetworks. He showed that among rhyming networks, the spider-web networks have the smallestblocking probabilities. He did not, however, determine the blocking probabilities of the spider-web networks (or its limit) in the general case. Pippenger [P92] succeeded in determining theperformance of switching networks under Lee's probabilistic traffic model. Pippenger has twocontributions. First, he showed that the limiting value of the blocking probability conjecturedby 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 samecrossbars arranged in the same number of stages, but for which the interconnection patternmay be arbitrary. Other significant results include Koverninskif [K75], Pippenger [P75], Chungand Hwang [CH77] and [CH80], and Pippenger [P91]. The papers [K75] and [P75] indepen-dently 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. Mooreand Shannon [MS56] described networks that are resilient to random-switch failures.Another contribution to the development of switching networks comes from the parallelSwitching NetworkCHAPTER I. INTRODUCTIONcomputer architecture community. In multiprocessor parallel computers, data values and con-trol signals are communicated among multiple processors and memory modules via switchingnetworks (also known as interconnection networks). Figure 1.3 schematically illustrates theinterconnection network among processors and/or memory modules.Figure 1.3: An interconnection network in a parallel computerA tremendous amount of effort has been devoted to the design of switching networks to sup-port 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]), banyannetworks (see Goke and Lipovski [GL73]), the butterfly (see Crowther et al [CGG+85]), and themultibutterfly (see Upfal [U89] and Leighton and Maggs [LM89]) have been presented. Theseswitching networks are employed in various parallel computers. For instance, the ConnectionMachine CM-2, the Intel iPSC, and the FPS T-Series use hypercube-type interconnection net-CHAPTER 1. INTRODUCTION^ 10works; the IBM GF-11 uses a three-stage shuffle-exchange-type interconnection network; andthe BBN Butterfly uses a butterfly-type interconnection network. Routing algorithms in inter-connection networks have also been studied. For interconnection networks of parallel computers,the routing algorithms mostly focus on how to packet-route an arbitrary permutation betweenN inputs and N outputs of the network. Valiant [V82] presented a randomized algorithm, whichwith a high probability routes any permutation of N packets in O(log N) steps in an N-nodehypercube 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 ofthe queues decreased from O(log N) (Aleliunas and Upfal) to 0(1) (Pippenger and Ranade) andthe 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 variantsof the butterfly, such as the omega network and banyan networks. Upfal [U89], and Leightonand Maggs [LM89] presented deterministic algorithms to packet-route any permutation on amultibutterfly 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 boundsfor Boolean circuits. The research on the superconcentratoris an example. In an n-superconcen-trator, 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 configurationcontaining k vertex-disjoint paths joining X to Y. The superconcentrator was first introducedby Aho, Hoperoft and Ullman [AHU74], with the hope of establishing a nonlinear lower boundCHAPTER 1. INTRODUCTION^ 11for the Boolean circuit complexity of multiplication. Valiant [V75] showed an 0(n) size and0((log n)2 ) depth upper bound — this dashed the hope of establishing a nonlinear lower boundfor multiplication via superconcentrators. Pippenger [P77] improved Valiant's result, showinga construction with 0(n) size (with a smaller constant) and O(log n) depth. Other importantresults include Pippenger [P82B], and Dolev, Dwork, Pippenger and Wigderson [DDPW83].(These results concern superconcentrators with limited depths.) Despite the failure for theiroriginal purpose, superconcentrators turned out to be central in a number of communicationnetworks. For instance, superconcentrators provide support for the Task Queue Scheme [C88]in parallel computing. Another example is the expander. Expanders are essential in establishingthe upper bounds for the complexities of some Boolean circuits and algorithms. See the sortingnetworks of Ajtai, Komi& and Szemeredi [AKS83a] and [AKS83b], and routing algorithms ofLeighton 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. Shortlythereafter, 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, Gabberand Gall [GG81] gave an explicit construction with an explicit constant in the linear bound ofthe 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 sizeand depth.CHAPTER 1. INTRODUCTION^ 121.4 Thesis outlineThis thesis focuses on the complexity theory for the construction of switching networks, withprimary emphasis on (a) the complexity of the networks, as measured by the size (number ofswitches), 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 2presents a first simultaneous "weakly optimal" solutions for the explicit construction of non-blocking networks, and the design of the parallel routing algorithms. "Weakly optimal" heremeans 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 smallestpossible values. Chapter 3 considers routing algorithms for blocking networks with probabilistictraffic. We present an optimal routing algorithm for series-parallel networks (which includes abroad range of useful interconnection networks for parallel architectures, e.g., butterflies andBene§ networks). The algorithm has an asymptotically minimum expected time complexityamong all routing algorithms.Chapters 4 and 5 discuss fault-tolerant switching networks under a random switch failuremodel. In Chapter 4, we prove lower bounds for the size and depth of fault-tolerant non-blocking networks, rearrangeable networks and superconcentrators. And we explicitly constructsuch networks with optimal sizes and depths. In Chapter 5, we consider fault-tolerant planarCHAPTER 1. INTRODUCTION^ 13switching networks, which are attractive because of the rapid advances in VLSI technology. Weprove lower bounds for the degree (of vertices) of fault-tolerant planar rearrangeable networksand superconcentrators. And we construct such fault-tolerant planar networks with optimalsizes and degrees.Chapter 6 presents some graph theory and combinatorics results obtained in the courseof this research. We consider the problem of how many pairs of leaves can be connected byedge-disjoint paths with a certain length in a given tree. We discuss the ratio of the maximumnumber of such paths to the number of leaves. We describe this value as a function of theminimum degree d of internal nodes and the maximum length 1 of the paths. We show lowerbounds and upper bounds of this value. In particular, we determine this value in the specialcase 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 aplanar graph, we give necessary and sufficient conditions for the existence of k vertex-disjointpaths 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 2Routing in Non-blocking Networks2.1 Non-blocking NetworksNon-blocking networks were introduced by Clos [C53] in 1953, although related work datedback to Shannon [S50] in 1950. Non-blocking networks have many applications in communica-tions. Typical examples are telephone switching networks and communication networks amongprocessors or between processors and memory devices.Definition 2.1 Let G be an acyclic directed graph G with a set of n distinguished vertices calledinputs and a set of n other distinguished vertices called outputs. G is a non-blocking n-networkif, given any set of vertex-disjoint direct paths from inputs to outputs, and given any input andany output not involved in these established paths, a new path that is vertex-disjoint from theestablished paths can be found from the requesting input to the requesting output.The interpretation of non-blocking networks in the context of automatic telephony andcircuit-switching networking is evident. Let us agree that vertices represent the connectingelements, 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 simultaneous14CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 15paths of communication at any time, without ever disturbing existing communication paths inthe 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 inputto an output). These measures reflect the cost and communication delay of the network. Anextensive literature exists concerning the design of non-blocking networks, minimizing the sizeand 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-networkwith depth k must have size at least 51(n 1 + 1/k) (k(n 1 + 1 /k) to be exact). Concerning constructionof the networks, Clos [C53] discovered non-blocking n-networks with 0(n 1 + 1/i) size and 2j — 1depth. 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 withO(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 presentedresults on wide-sense non-blocking networks. See Pippenger [P82] for an introductory accountand [FFP88] for more recent references.In this chapter we shall combine this concern for depth and size with concern for the timetaken by an algorithm that finds the routes guaranteed by the non-blocking property, and forthe space taken by the data-structure used by the algorithm. Unlike the case of depth and sizeCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 16alone, not much progress has been made in this setting. An exception is that Arora, Leightonand Maggs [ALM90] found an on-line O(log n) steps parallel path selection algorithm for non-blocking networks of size 0(n log n) and depth O(log n). Their proposal, however, assumes thatthe number of processors is proportional to the size of the network, irrespective of the numberof transactions being processed. Our approach, in contrast, uses only one processor for eachtransaction, even if this number is as small as one. (Simply counting processors is not entirelyfair: 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 networkof [ALM90] is based on a randomized construction, whereas the network of this chapter has asimple explicit construction. Neither of these results subsumes the other.)In this chapter, we explicitly construct a scheme in which non-blocking networks with ninputs and n outputs have size O(n(log n) 2 ) and depth O(log n). And we present on-line parallelalgorithms to control them. The algorithms use time and space within one or more factors oflog n of the smallest possible values that any control algorithm (on-line or off-line, parallelor serial) may use. More precisely, we present an on-line deterministic algorithm that usesO((log n) 5 ) steps to process any number of transactions in parallel (with one processor pertransaction), maintaining a data structure that use 0(n(log n) 2 ) words, and we present anon-line randomized algorithm that uses 0((log n) 2 ) expected steps to process any number oftransactions in parallel (with one processor per transaction), again maintaining a data structurethat use 0(n(log n) 2 ) words. (The meanings of "step", "word" and "transaction" will beexplained in next paragraph).CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 17Consider a non-blocking network with n = 2" inputs and n = 2" outputs. Any routingalgorithm that controls the network must be able to find out the state of the network. An obviousapproach 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 changethe set of busy vertices. While this approach is successful in restricted circumstances, our mostsatisfactory results take a more general approach in which the data-structure is separated fromthe network. This allows the data-structure to contain redundant information about traffic inlarge parts of the network, and to maintain this information incrementally, without having torecompute it from scratch for each transaction. In fact, we consider the routing algorithm andits 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 processedbefore its successors are known, and each transaction affects and is affected by only a smallportion of the data-structure, rather than as an "off-line system", for which time requirementswould always exceed space requirements. Furthermore, for a batch of t transactions, whichare to be processed in parallel, only t processors are allowed to be used. In other words, ourapproach assumes each transaction "brings its own processor", a setting convenient in situationswhere routing is but one part of a larger process, and the number of processes simultaneouslyengaged 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. WeCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 18reckon "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 thatcontrols the network must use Si(1) steps to process a batch of transactions, and the data-structure for it must have St(n) words (or their equivalent), since this much space is needed torepresent one of n! bijections between inputs and outputs.Our results provide the first simultaneous "weakly optimal" solutions for the explicit con-struction of non-blocking networks, the design of algorithms and data-structures. "Weaklyoptimal" is in the sense that all measures of complexity (size and depth of the network, time forthe algorithm, space for the data-structure and number of processor-time product) are withinone or more factors of log n of their smallest possible values. Our solutions are practical in thesense that the construction of the networks is simple and the algorithms (both the randomizedand the deterministic one) and their data-structures are easy to implement. Our main result inthis chapter is summarized in the following theorem.Theorem 2.1 There is an explicit construction for a non-blocking network of n inputs and noutputs with size 0(n(log n) 2 ) and depth 0(log n), and a deterministic on-line parallel algorithmthat 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 al-gorithms and data-structures apply. We present the randomized algorithm in Section 2.3. Insection 2.4, we describe the data-structure of the deterministic algorithm. In Section 2.5, weCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 19use the derandomization technique from Luby [L88} to eliminate the randomization and presentthe deterministic parallel algorithm.2.2 The NetworksSuppose that we wish to construct a non-blocking network with n = 2" inputs and n outputs.Set -y = Llog2 (4v)J, so that 21+ 1 > 4v > 21 . Construct a Rene§ network with m = 2 11+1 inputsand m outputs (see Elena (l364]). (Roughly speaking, a Rene§ network with m inputs and moutputs consists of two back-to-back butterflies with m inputs and m outputs. See Figure 2.1for example.):10.k^#1.1 2Mra DanatrAdOMA. X :-.. LWACOUSEPRIM' WAraff^VW' ael■AlLw wralVAlhFigure 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 stage2(7 -I- v), with the inputs in stage 0 and the outputs in stage 2(7 -I- v). Each stage contains21'+" vertices, and all edges are from stage i to stage i 1 (i = 0, • • •, 2(7 + v)). Now reducethe number of inputs and outputs in this network to n by retaining only every 2/-th inputand output and discard vertices and edges that can not be reached from these n inputs and noutputs. This is done so that routes originating at two distinct retained inputs can meet onlyat or after the (y -I- 1)-st stage, and similarly for retained outputs.CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 20Let N+ denote the resulting network (see Figure 2.2). This network is non-blocking asshown in [P82].Figure 2.2: Non-blocking network N+ with 4 inputs and 4 outputs (edges are directed from leftto right)Given a set of vertex-disjoint direct paths from inputs to outputs, say a vertex in N+ is idle ifit is not involved in these paths, and busy otherwise; say a vertex 6 has access to another vertex6 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 stageregardless 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. Thusgiven any idle input and idle output, a route from the input to the output that is disjoint fromthe established routes always exists regardless the status of other inputs and outputs. Thisnetwork has size 0(v2" 1. ) = 0(v22") = O(n(log n) 2 ) and depth 0(7 + v) = O(log n). Thisnetwork is essentially equivalent to the one described by Cantor [C71].CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 212.3 A Randomized Parallel AlgorithmIn this section, we describe a randomized parallel algorithm which processes a batch of trans-actions in parallel with O((log n) 2 ) expected steps by dynamically changing a data-structure ofO(n(log n) 2 ) words. Our deterministic parallel algorithm is obtained by eliminating randomnessfrom this algorithm.The data-structure for our randomized algorithm is very simple. It keeps only the up-to-datebusy/idle status for each vertex of the network. We describe the data-structure in terms of adirected graph G that is isomorphic to N+. For each vertex of the network N+, we create a nodein G. Two nodes in G are adjacent if and only if their correspondents in N+ are adjacent. Witheach node C in G, we associate a number G((), which is 0 or 1 according as its correspondingvertex in N+ is idle or busy. (The reason that we distinguish G from N+ is that we want touse G to refer to the data-structure and N+ to the network). It is clear that the data-structureuses 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 amirror image of the subnetwork of stage 0 to stage 7 + v. We refer the former to "the right-handhalf 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 pathstarting from e forms a tree Ti. Similarly, for each output y of N+, there is a tree Tn . It is clearthat all Te's and Tn 's are complete binary trees having depth -y + v with 2 -r+" leaves. We callthe common topological structure of these trees T.CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 22Suppose that a batch of t transactions (requests to establish or abolish a route) are to beprocessed by t processors (each transaction "brings its own processor"). We need not worryabout interference between requests that establish routes and requests that abolish routes bythe simple device of splitting each batch into two batches, one comprising only requests toestablish and the other comprising only requests to abolish. As we will see, the algorithmspresented in this chapter to process requests to establish are well suited to process requests toabolish, thus we shall only consider requests to establish here.We now proceed to describe our randomized algorithm. Suppose that when a processorattempts to establish a route from input e to output 77, it pushes two pebbles in T4 and T,7respectively 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 21'+'possible paths P at random, and then determines whether or not the two subroutes (in N andN' respectively) corresponding to the subpaths in 7'4 and T,, are both idle (this includes checkingwhether 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 thatfail to choose an idle path, do the same procedure again, and so forth, until all requests aresatisfied. 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 thecorresponding paths in T4 and T,i respectively (7' and T,7 are embedded in G). It changes thevalue 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 ) wordsCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 23and for any t in the range 1 < t < n, processes t transactions in parallel using t processors in0((log n)2 ) expected steps.Proof. Consider an arbitrary processor, which chooses one of the 21'+' possible paths at random.The probability that the corresponding subroute in N is busy is at most 1/4, since every idleinput in N has access to at least (2141 - v)211-1 of its 214 ' outputs (vertices in the middle stageof N+) regardless the status of other inputs, and 4v < 2141 . Similarly, the probability that thesubroute in N' is busy is at most 1/4 too. Thus the probability that both subparts of the routeare idle is at least 1/2. Therefore, with randomly chosen paths, at least half of the requests areexpected to be satisfied. At most t2 -1 requests are expected not to be satisfied after i-th roundof choosing. Thus the expectation of such i when t2 -i = 1 is at most log 2 t = O(log n). Onthe other hand, determining whether or not paths are idle (including no other processors in thesame batch having seized a vertex in the path) and updating the data-structure to reflect theaddition of new routes are performed with O(log n) parallel operations, since each route is oflength 2(7 + v) +1 = O(log n) and G is of bounded degree (the maximum degree is 4). Thus theparallel randomized algorithm establishes (and/or abolishes) t transactions using t processorsin 0((log t)(log n)) = 0((log n) 2 ) expected steps. A2.4 The Data-structure for the Deterministic Parallel Algo-rithmIn this section, we extend our simple data-structure for the randomized algorithm to supportan efficient deterministic parallel algorithm. Roughly speaking, we maintain some redundantinformation about the distribution of established routes, so that we can save some computationCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 24by 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 definethe distance dist(711,7/2) of two outputs 7b and 772 .It is observed that, for each input e there are 2" other inputs e' with dist(e,e) = d, forany 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 + 6for any 1 < 6 < v — d. That is to say, if the distance of two inputs is d, then they share thesame group of inputs whose distance is d -I- 6 to them. It will be much clearer if we describethe distance relationship among inputs in terms of a binary tree IND. IND is a complete binarytree of depth v with 2' leaves. Let the leaves correspond to the inputs of N+ in the followingway. Two leaves are siblings if and only if their distance is 1; two nodes r 1 and r2 at depth 1are siblings if and only if the distance between leaves in the subtree rooted at r1 and that inthe subtree rooted at r2 is v — 1 +1 (the distance is unique, as observed above). Similarly, thedistance relationship among outputs is described in terms of a complete binary tree OUTD. Itis observed that two inputs (outputs, resp.) have distance d if and only if their lowest commonancestor in IND (OUTD, resp.) is at depth v — d.In order to obtain an efficient deterministic parallel algorithm, we need to keep some re-dundant information about the distribution of established routes. The information in the datastructure, on the other hand, can not be too redundant, since our algorithm dynamically up-CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 25dates 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 themwill block each other is determined within the first 7 d 1 stages in N+. Thus for each inpute, we confine the route distribution information for inputs with distance d to the first 7 d 1stages; for inputs with distance d to e, however, we keep their route distribution information asa whole instead of individually. Therefore, for each input e, we keep v complete binary trees, ofdepth 7 d and having 27+d leaves for 1 < d < v, with each representing the route informationof 2d-1 other inputs (inputs with distance d to E). Associated with each node C in such a treeis a number, counting the number of routes that start from one of the 2d-1 inputs, say e', andpass 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 largeamount of overlapping). Similar properties hold for outputs.Our data-structure for deterministic algorithms is precisely described as follows. In additionto the data-structure G of the randomized algorithm, we keep some redundant information aboutthe distribution of established routes. For each node r at depth v - h (with v - 1 > h> 0) inIND, we keep a complete binary tree TR, (TR stands for "traffic"), which is of depth 7 h with27+h+ 1 - 1 nodes. Recalling the common structure T of Ti's and T,7 's, we see TR., is a subtreeof T truncated at depth 7 + h. For each node in TR,, there is a corresponding node Ct in eachtree T. Associate with each node in TR, a number TR,('), which is the sum of G(C) (the0/1 value indicating CC is idle or busy) over every input e which is a leaf in the subtree rootedat r in IND. Similarly, for each node at depth v - h (with v - 1 > h > 0) in OUTD, make aCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 26complete binary tree Tito, which is of depth 7 + h with 214h+ 1 - 1 node. Associated with eachnode ( is the value TR,3((), which is the sum of G((, 7 ) over every output n which is a leaf in thesubtree rooted at /3 in OUTD (61 is the corresponding node of ( in T,,).Let us consider the space requirements of the data structure. Graph G has less than2(v + 1)2ry÷u nodes, and there is a number (0 or 1) associated with each node. There are2 . 2"-h nodes r and /3 at depth v - h in trees IND and OUTD. For each r or /3, there is a treeof r+h+1 -1 nodes, and associated with each node is a number (in the range [0,2' - 1]). Thusthere are less thanu-i.2(v + 1)2ry+u +^(2 • 2v-h )(2 • 2 .y+h _ 1) < 6(v + 1)214v = 0(,22p) = O(n(logn)2 )h=0numbers 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 AlgorithmThe elimination of randomization from the randomized parallel algorithm of Section 2.3 isaccomplished 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 numberof bits from a smaller number. In the second stage we show how to deterministically computethis smaller number of bits.CHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 27In the randomized parallel algorithm, each processor makes a random choice uniformly dis-tributed over 214" possibilities; we may therefore regard it as making y + v successive indepen-dent random binary choices, corresponding to the y + v successive moves involved in pushinga pebble from the root to a leaf in T (T is the common structure of trees Tt and T,1). Wemay 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 assumptionthat all routes were independently chosen, but actually only relied on the routes being pairwiseindependent. Thus the analysis will remain valid if the binary choices in each phase are notcompletely independent, but are pairwise independent. These t pairwise independent bits canbe computed deterministically from a set of v = log2 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 thet requests (input indices are in their binary representations). Let X be a row of v completelyindependent random elements of GF(2), and let Y be the product XM (a row of t elements ofGF(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 fromthe 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 treesTe's and Tn 's. As before, established routes will be replaced by pebbles at the leaves, and eachprocessor 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^ 28For simplicity of notation, we label the two corresponding pebbles e and 77 as well. Given adisposition 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 pebble6 is at a node cr„ at depth 7c in T and the path from the root of T to cr„ is oo, cri, • • • ,a„, whereao is the root of T, the congestion of 6 is the sum of a contribution of 1/2 14d- '` for every pebble6' in the subtree rooted at cr„ and with d = dist(6,6')> lc- 7, plus for each node at depth 7 + ion the path from the root of T to c (i.e., node ai,+i), i = 1, • • • , K - -y - 1, a contribution of 1for every pebble 6" in the subtree rooted at (7.7+i and with dist(6,61') = i. (Quantity 1/214"indicates the possibility of 6 being blocked by 6' in later stages; quantity 1 indicates that 6 isblocked by 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 2d-1 and of distance d to 6, for1 < d < v. Of the inputs in the group of distance d to 6, their lowest common ancestor in INDis at depth v - d + 1 (recall that inputs correspond to leaves in IND). Let these ancestors ber1 , • • • , i-  y (ri corresponds the group of inputs with distance i to 6). The congestion of 6 equalthe sum of TR,d (crpc )/21-1-d- '5 over every d, , - 7 < d < ii, plus the sum of T/ird (cf-r+d) overevery d, 1 < d < , - 7 -1. We say that the congestion of a request is the sum of the congestionsof its two pebbles, and that the congestion of a batch of requests is the sum of the congestionsof 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), theCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 29congestion of a pebble is less than or equal to EL,'1_, 1 (1/21'+d)•2d-1 = v/27+ 1 < 1/4, correspondingto contributions of 1/ 21-14 for each of the other pebbles at leaves or at the root. Secondly, ifa pebble is moved from a node a to one of its two children (chosen at random with equalprobability), the expected congestion of each pebble is unaffected; indeed, each contributionto the congestion is either unaffected or undergoes a "double-or-nothing" transformation withequal probabilities. Finally, when all pebbles are pushed to leaves (K = y + v) , the congestionof 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 thebatch of requests. It follows from these observations that on the average, at least one-half ofrequests 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 itstwo pebbles down one level in their trees during each phase. If all of the binary choices involved inthese pushes were completely independent, the expected congestion would be unaffected. Sincethe congestion is defined as a sum of pairwise contributions, its expectation is unchanged ifcompletely independent binary choices are replaced by pairwise independent binary choices. Solet t pairwise independent choices be deterministically computed from v completely independentchoices, as described above. Since the expectation over all I/ choices is unaffected, it follows thatthere is a particular way of making the first choice for which the expectation (over the remainingv — 1 choices) does not increase. After the first choice has been made in this way, there is aparticular way of making the second choice for which the expectation (over the remaining v — 2choices) does not increase. Proceeding in this way, we arrive at particular ways of making all yCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 30choices, 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 precedingparagraph can in fact themselves be deterministically computed in a simple way. For if we assignparticular values to some of the v choices, the expected congestion over the remaining choicescan be computed as follows. Assigning particular values to some of the choices commits someof the t pebbles to move from the node a at which they began the phase to one of their twochildren, 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 Mcontains a 1 have been assigned particular values; otherwise, its fate is uncompromised). Thus anadvantageous value for a choice can be found by tentatively assigning one value, recomputing thecongestions, and rescinding the tentative assignment in favor of its alternative if the congestionincreases.By now we have finished the description of our deterministic parallel algorithm. The fol-lowing lemmas formalize the preceding arguments. Readers who are satisfied with the abovearguments 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 vectorZ = (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, andyin+1(z) A if not all entries of 1 in Mc appear in M(zin .,+1, • • • , Z772 •,+1)M otherwisewhere M is the vector containing the first 1 entries of Mc. Let P(Z,e) be the correspondingCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 31position of pebble e (the node 6 resides at) in T, after m + 1 consecutive moves in accordancewith 1"?(Z), • • • ,Yr+ 1 (Z) (0 correponds to the move to the left child, 1 to the move to the rightchild and A to no move). Denote the congestion of 6 at node P(Z, e) by conMZ). Given avector 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, wherex is an element of GF(2).Lemma 2.1 For any input pebble 6, conMO) < 1/4.Proof. It is straightforward. ALemma 2.2 For any input pebble 6, any Z = (z1,• • • ,z,,,,÷1) over GF(2), 0 < m < 7 + v — 1and 1 < 1 < v, and a random variable x uniformly distributed over GF(2), the expectationE[conge(Zx)] = conMZ).Proof. Let x be a random variable uniformly distributed over GF(2). For any input pebblee, we consider two cases, P(Zx, 6) 0 P(Z, f) and P(Zx,6) = P(Z,e) (whether 6 moves onelevel down or not because of x). When P(Zx,e) 0 P(Z, s), first consider a pebble 6' such thatP(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 Kin T. If d> K-7, P(Z, e'') must not be the same node as P(Z, 6) and the expected contributionof e' to conMZx) equals the contribution of 6' to conMZ), because the contribution undergoesa "double-or-nothing" transformation with equal probabilities; if d = K - 7, the contribution of6' 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 + iCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 32from the root of T to P(Z , E) with dist(e, e") = i, i = I,. • • , lc - - 7 —1. The contribution of e" toconMZx) equals that to conMZ) (remains to be 1) regardless which child e moves to. WhenP(Zx,e) = P(Z,e), it is clear that the contribution of any other pebble E' to congaZx) is thesame as that to conMZ). Thus in either case, E[conMZx)] = conMZ). ALemma 2.3 For any input pebble e, if VI = v(7 + v), conMZ) is an integer greater than orequal 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 routesin parallel in O((log n) 5 ) steps with one processor per transaction, maintaining a data structureof 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 areat least one half of the requests being satisfied, which implies flog 2 tl = O(log n) "rounds" ofpushing 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 congestionof the batch of requests is computed, this is done with O(log n) steps, as the congestion of apebble is computed in O(log n) steps by one processor (the sum of TR,d (a,c )/2/+d-" over everyCHAPTER 2. ROUTING IN NON-BLOCKING NETWORKS^ 33d, K — 7 < d < v, plus the sum of TRra (a7+d) over every d, 1 < d < i - 7 — 1), and after thecongestion 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 ofa 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 fromthe fact that to any one of these numbers, at most 0(t) = 0(n) processors may want to updateit simultaneously (with each one adding 1 or subtracting 1). 0Chapter 3Routing in Networks withProbabilistic Traffic3.1 Probabilistic Model and Previous WorkIn the preceding chapter, we discussed routing algorithms for non-blocking networks. Non-blocking networks guarantee a dynamic linkage between any pair of an idle input and an idleoutput 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 complexwiring topology. Very often then, switching networks are constructed with simple topologiesand limited "blocking probabilities".In this chapter, we consider a family of switching networks, known as "series-parallel net-works". The basic building blocks of these networks are d x d crossbars. These networks havesimple topologies and exhibit a reasonable probability of connection for inputs and outputs. Toanalyze the performance of these switching networks, one assumes the network is in a "randomstate" (i.e., the network is operating under probabilistic traffic), and measures the extent ofconnection of inputs and outputs by the "linking probability". (The meaning of "random state"34CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^35and "linking probability" will be explained in the next paragraph.)A literature exists concerning the analysis of the performance of switching networks underprobabilistic traffic assumptions. Lee [L55] in 1955 proposed a simple approximation modelto characterize the probabilistic traffic (see also Le Gall [L56]). In this model, each link of thenetwork is assumed to be idle with some probability q (called the "vacancy probability") or busywith the complementary probability p = 1 — q (called "occupancy probability"), independentlyof all other links. A random state of a network in this model is an assignment of busy or idlestatus to its links in accordance with the above described probability distribution. The linkingprobability for a given pair of idle input v and output w is the probability that there is a pathfrom v to w containing idle links only. For the networks we consider in this chapter and for mostnetworks used in practice, this probability is the same for each pair of idle input and output, andthus refers to the linking probability of the network as well. The complementary probability (ofthe 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 withprobabilistic traffic. Unlike the situation for the linking probability, there is virtually no non-trivial progress in analyzing efficient routing algorithms for these networks. We shall adopt Lee'sprobabilistic model, and we assume that the status of a link (busy or idle) remains unknownuntil it is detected by a "test" operation. We reckon the time by the number of such testoperations. We measure the cost of a routing algorithm by its expected time, assuming theCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^36network 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 routingalgorithms for series-parallel networks. (More precisely, we shall show that it has an expectedtime within a multiplicative constant lip of the optimal.)3.2 The NetworksWe 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 d2 "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, whereOutlets0 0 00 0Inlets 0 0 OutletsInlets 0000 0A d x d crossbar^Another representationFigure 3.1: A d x d crossbark < 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. Theparameter k is called the "scale" of the network, and 1 is called the "depth" of the network. For1 < j < 1-1, the outlets of the crossbars in the j-th stage are connected in a one-to-one fashionto the inlets of the crossbars in the (j + 1)-st stage by means of dk links.CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^37We 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 classescalled "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 stageform the j-th rank). An edge from a vertex in the j-th rank to some vertex in the (j + 1)-st rankexists if there is a switch (in some crossbar in the j-th stage) providing a path from the formerto the latter. In this way, a d x d crossbar is regarded as a directed complete bipartite graphwith 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 networkof the type considered here. (See Figure 3.2.) Hereafter in this chapter, we shall use such anacyclic 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 eachrank with binary strings of length k over the alphabet {0,1, • • • , d — 1). The positions in eachstring 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-thCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^38  1324234A network built from 2 by 2 crossbars^Its acyclic directed graph representationFigure 3.2: A network built from 2 x 2 crossbars and its acyclic directed graph representationrank and the (j 1)-st rank is of type i, for 1 < i < k, if an edge from vertex x in rank j tovertex 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 anddepth I is constructed according to the rhyme scheme r 1 • • ri E { 1 , • • • , kV if its interconnectionpattern 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 accordingto the rhyme scheme 12 • • • k(/ — k)(/ — k — 1) • • .1 (see Figure 3.3).000001010011100101110111000001010011100101110111• .^1.1" /elISSEMPIABOIC1ev 01111.11111111111114aXeltrA Pl■ ■WevA11111411101.■MIRSTAILFigure 3.3: A series-parallel network with d = 2, k = 3 and 1 = 5CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^39In a network with an input v and an output w, the channel graph from v to w is the acyclicgraph comprising those vertices and edges lying on paths from v to w. A network is balancedif any two channel graphs are isomorphic. It is clear that the linking probability in a balancednetwork is the same for any pair of idle input and idle output. It is obvious that a series-parallelnetwork is a balanced network. (In fact, any network constructed according to a rhyme schemeis a balanced network.) Therefore, for the purpose of analyzing routing algorithms for thesenetworks, we may restrict our attention only to the channel graph instead of the whole network.3.3 Main Result and the General StrategyWe shall show that the routing algorithm for series-parallel networks, Depth-First Search Rout-ing, is asymptotically optimal: the expected time of the algorithm is within a multiplicativefactor 1/p of the optimal. Our general strategy is that (1) we transform any optimal routingalgorithm 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) isproved by associating the "appearance" of the channel graph at any step of the execution of analgorithm in the "restricted form" with a "potential". (An "appearance" reflects the knowledgethat 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 algorithmis able to terminate), decreases by a fixed constant c (in expectation) for each step of the algo-rithm Depth-First Search Routing B, and decreases by at most c (in expectation) for any stepof any routing algorithm in the restricted form. It follows that the optimal expected time forCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^40algorithms 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 ofother considerations. Furthermore, in this special case, our result is somewhat stronger: weshow that a "depth-first search" type routing algorithm (Depth-First Search Routing A on page31) is optimal, i.e., it has the smallest expected time among all routing algorithms.3.4 The Almost-Series CaseAs stated at the end of Section 3.2, routing in a series-parallel network is the same as routing ina channel graph. Given an idle input v and an idle output w, let C(v, w) be the channel graphfrom v to tv. A routing algorithm will find a path from v to to containing idle vertices only (inshort, 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 andoutput to is a set of d chains of length 1 (containing 1 edges) from v to w, disjoint except at theends (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 anddepth k + 1, a routing algorithm consists of a combination of tests on vertices of the channelgraph (detecting the busy/idle status of the vertices) nested in a control structure. We mayCHAPTER 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 = 5view a routing algorithm as a decision tree, in which each internal node is a test, and the twobranches correspond to the situations where the vertex is found busy or idle. The test results ofthe nodes on a path from the root to a leaf in the decision tree include either a busy cut or anidle path of the channel graph. Suppose that a test of a vertex 9 on a chain C of C(v, w). Theresult of this test is that (a) 9 is found busy (with probability p), so that there is no need toexamine any other vertices on chain C, and therefore we may imagine that chain C disappearsand the number of chains in C(v, w) decreases by one; or (b) 9 is found idle (with probabilityq = 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 thelinks). Each appearance is characterized by a set of r (r < d) chains from v to w disjoint excepttheir ends (v and w). Let 1 < 11 < 12 < • • • < I,. be the lengths of these chains (that is, thenumbers of edges contained). The appearance of the channel graph C(v, w) is described by thevector (1 1 ,12 , • • • ,1,.). Initially, the channel graph is in appearance (12 12 . 22 where there aredd chains each containing 1 edges (in this case, the routing algorithm "knows" nothing aboutC(v, w) but the probability distribution of the busy/idle status of the links). The algorithmCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^42terminates when C(v, w) is in some appearance (1 1 ,12 , • • • , 1,.) where 1 1 = 1 (in this case, therouting algorithm finds an idle path) or r = 0 (in this case, the routing algorithm finds a busycut). As explained in the preceding paragraph, a test on a vertex on j-th chain (the chain withlength 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 ofgenerality we may assume^< /j).Given 1 < 1 1 < 12 < • • • <^we define the potential function on appearance (4,12, • • • , 1r)to be^1 - q12-1^(1 - q 11 -1 )(1 - q12 -1 )^(1 - q11-1 )(1 - q12-1 ) • • • (1 - ql* -1 )F(11,12, • • • , 1r ) = 1^ — q 1 - q^ 1 - qLemma 3.1 For each appearance (1 1 ,12 , • • • ,1r ) (1 < 11 < 12 < I r and r < d) of the channelgraph C(v,w) at which a routing algorithm terminates, we haveF(11,12, • • • , 1r) = O.Proof. It is straightforward. Note that in this case 1 1 = 1 or r = 0. ALemma 3.2 Given an appearance (1 1 ,12,- • • , Ir) (2 < 1 1 < 12 < 1r and r < d) of the channelgraph C(v, w), if a routing algorithm examines a vertex on the shortest chain (the chain withlength li), 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 thenew appearance is (4 - 1,12 , • • • , 1,.). Therefore the expectation of the potential function on theCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^43new appearance is=pF(I2,• • • ,1r) A- qF(11 - 1,12,• - • ,1r), 1,412-1^(1-q12-1)...(1_gir-1) \Pk^1^+ • • • +^ fq 1-q^I0. _ qii -2^o_qii-2)(1_112-1)+0_0. -2 )(1 _ 9 :2 -1 ) ... (1 -vr-1 ))+^1-qqk^1-q^4-^1-q= 1-q 11-1^i^(1_,7 j11-1)(i_qi2-1 ., (i_qii-1)(i_qt2-1)...0_qtr-i)11-q^.1-^1-q^+ +^1-q= F(11,12, • • • ,1r) - 1.^ALemma 3.3 Given an appearance (li,12,• • • ,1r)^< 11 < 12 < Ir and r < d) of the channelgraph C(v,w), if a routing algorithm examines a vertex on the j-th chain (the chain with lengthli) and 11 < 13 , then the expectation of the potential function on the new appearance is strictlygreater than F(11 ,12 ,• • • ,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, • • •,/,) (withprobability q). Thus the expectation of the potential function on the new appearance ispF(11,• • • ,li-1, 1J+1,• • • ,10-1- qF(11 , • • • ,1;1-q111^(1-q11-1)...(-q5-1-1)- 1, • • • ,1,)1-q 1-q(1 - q11 -1 ) • • •(1 _k(1-q1.7-1)...0_qtr-s)1-q+1-q 1)F(11,12,• • '^1r) - ( 1 - qii -1 ) • • • (1 - q13-1 )> F(11,12, • • • , 1r) - 1.^ALemma 3.1, 3.2 and 3.3 together show that for any appearance (11,12, • • • , 1r), the potentialF(I1 ,12 , • • • ,/r) is a lower bound for the expected number of tests that any routing algorithmuses before it terminates. In particular,1 Yn1-1^(1 — q1-1)2^(1- g1_1)d^(1 471-1) ( 1 _ qb-s)d=  1 - q^1 -  1^ +1 - q^ =(1 - q)ql -1dis a lower bound for the expected time of any routing algorithm. Furthermore, Lemma 3.1, 3.2CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^44and 3.3 show that the following algorithm (Depth-First-Search Routing A) is an optimal routingalgorithm.Depth-First-Search Routing ARepeat the following until C(v, w) is empty or contains a chain of length oneChoose a chain C with the shortest length in C(v, w)Examine a vertex u (other than v or w) in chain CIf the vertex is busythen delete chain C from C(v, w)else delete vertex u and merge the two edges incident to uProposition 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- q1-1)-(1-q1-1)d(1-q)q1-1^•3.5 The General CaseFor a series-parallel network with scale k and depth 1 (k < 1 < 2k - 1), the rhyme scheme is12 • • • k(1 - k)(1 - k - 1) • • .1. Given such a series-parallel network N, and given an input vand an output w, consider two distinct paths r and ir' from v to w. Let L denotes the longestcommon 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 atrank a - 1. Then r and ir' must differ at rank a, and the labels of their vertices in the a-th rankCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^45must 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 all1 — k -I- 1 < j < k, position a must be in the range 1 < a < 1 — k (otherwise z- and ir' willnot coincide at w). Since in the rhyme scheme, the interconnection pattern of type j' appearsexactly twice, for all 1 < j' < 1— k, paths z- and z-' must coincide at (1— a)-th rank and will notseparate 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 length2k — 1 from 2" leaves of Tv to 2" leaves of Tw in an identity fashion (see Figure 3.5). Callthis 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 ofthe two comprising trees the "ends" of the folio. Throughout the remainder of this chapter, weshall 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 = 6As 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 mayCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^46discard a portion of the channel graph (if 97 is found busy) or we may delete 97 and merge thein-edge(s) of 97 to the out-edge(s) of 97. And then we may define some "potential function" oneach "appearance" to measure its "closeness" to the "final appearance". Unfortunately, thisapproach is unsuccessful because an arbitrary "appearance" of the channel graph generated bya routing algorithm is too complex to be characterized by a set of simple parameters, so as to beused as the domain of a "potential function". (One may recall that in the almost-series case, theappearance is characterized by the lengths of a set of chains). However, we are able to show thatthere is a "restricted class" of routing algorithms, such that the "appearances" of the channelgraph 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 "restrictedclass" is within a constant factor (i.e., 1/p) of that of the optimal routing algorithm (withoutany "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 twoends of some b-folio as a pair (that is, examines one end and if it is idle, examines the otherend). 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 isempty). 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 setCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^47of d disjoint (1 - 1)-folios. It is natural to characterize a "appearance" of the channel graphgenerated by an algorithm in 7Z by a set of disjoint folios. Let 0 < 1 1 < • • • < I, be the depths ofthese 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)-dfolios. A routing algorithm in 7Z terminates when the channel graph is in some appearance(11 ,12 ,• • • ,1,.) where 4 = 0 (in this case, the routing algorithm finds an idle path) or r = 0 (inthis 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 - q2 , and (b) appearance(4, • • • , - 1,•••• (if 1.; > 2k -/) or appearance (4, • • • ,lj -1, • • •,1,.) (if < 2k-1)dwith 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 beH(4, l2, • • • ,1r ) = G( 11) + C(4)G(12) C(4)C(12)G(13) + • • • + C(i1) • • • C(1r_ i )G(4),whereG(x) ={1 + q + q2 G (x 1)1 i (c4-11)d if x > 2k - I1+ q -I- q2G(x - 1)^if x < 2k - 1and1 - q2 q2 (C (x - 1))d if x > 2k - 1C(x) =1_ q2 q2^(x^1) if x < 2k - 1,with G(0) = 0 and C(0) = 0.CHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^48Lemma 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 haveH(111121 • • • lr ) = 0.Proof. The idea is the same as in Lemma 3.1. Note that in this case 1 1 = 0 or r = 0. ALemma 3.5 Given an appearance (1 1 ,12 , • • • ,1r ) (1 < 11 < 12 < 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 theexpectation 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 and1 < 2k - 1. We shall only show the case 1 1 > 2k - 1 (the case / 1 < 2k - 1 is similar). In thiscase, with probability 1 - q2 , the new appearance is (1 2 , • • •, 1r ), and with probability q2 , thenew appearance is (11 - 1, • • • , / 1 - 1,12 , • • •,1„). Thus the expectation of the potential functiondon the new appearance is(1- q2) I1(12, • • • ,1,.)-F q2 H(11 - 1,• • • ,11 - 1,12,• • • ,1r)d= (1 — q2 )[G(12)-F • • • 4- C(12)• • •C(1r-i)G(101-1-q2 [G(li - 1)-F • • + (C(11 - 1)) d-1 G(11 - 1) + (C(11)) dG(12)-F • • • + (C(11)) d • • •C(1r_i)G(1r )]= q2 [G(li - 1) + • • • + (C(11 - 1))d-1G(11 - 1)]+[( 1 - q2) q2 (C(11 - 1))1[G(12)-1- • • • + C(12) • • • C(1 r_i)G(1r )]= G( 11) - 1 - q+ C(10G(12)+ • • • + C(l 1 ) • • •C(1r_ i )G(Ir )= H(11,12, • • • ,1 r) - 1 - q. ALemma 3.6 Given an appearance (11,12, • • • ,1r)^< 11 < 12 < 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 expectationof 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^49Proof. Similar to the proofs of Lemma 3.4 and Lemma 3.5. AFrom Lemma 3.4, 3.5 and 3.6, we conclude that^ 1 is a lower bounddfor the expected number of tests of any routing algorithm in 7Z. It also shows that the followingalgorithm (Depth-First-Search Routing B) is an optimal routing algorithm in 7Z with an expectedtimedDepth-First-Search Routing BRepeat the following until C(v, w) is empty or the depth of a folio becomes zeroChoose an h-folio F with the smallest depth h in C(v, w)Examine the two ends of FIf one of the ends is busythen delete folio F from C(v, w)else if h > 2k — 1then remove the two ends andbreak folio F into d (h — 1)-folioselse remove the two ends and decrease the depth of folio F by oneProposition 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 timeHCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^503.5.2 Routing Algorithms without RestrictionGiven a set S of disjoint folios, in which each vertex is busy with probability p and idle withprobability 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 theminimum T(a) over all routing algorithms a, and Optn(S) be the minimum T(a) over allrouting algorithms a E R.Proposition 3.3 We haveOptiz(S) < Opt(S)PProof. Let w be an optimal routing algorithm for S. We shall show that there is a routingalgorithm 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 simulatesthis step by doing the following:Repeat the following until either x is examined or a busy vertex is foundExamine the ends of F in turnIf both ends are idlethen if h > 2k —Ithen remove the two ends and break F into d (h — 1)-folioselse remove the two ends and reduce F to an (h — 1)-folioProceed recursivelyCHAPTER 3. ROUTING IN NETWORKS WITH PROBABILISTIC TRAFFIC^51 The algorithm a uses at most an expected number 1 + q + q2 + • • • < 1/p tests for the one testby co, and at the end, a "knows more than" w does (either it has examined x, or it has verifiedthat the status of x is irrelevant). Therefore a simulates w (it returns a busy cut of S when wdoes, and returns a idle path when co does) with at most a 1/p factor increase in the expectedtime. AFrom Proposition 3.2 and 3.3, we conclude thatTheorem 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 4Fault-Tolerant Switching Networks4.1 The Switch Failure ModelIn this chapter, we consider fault-tolerant switching networks under a random switch-failuremodel. In this model, each electrical switch in the network is independently in one of thethree states: (1) open failure (the switch is permanently off and fails to be on) with probability0 < El < 1/2, (2) closed failure (the switch is permanently on and fails to be off) with probability0 < 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 theprobability 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 inthe context of relay circuits computing Boolean functions. The model retains its relevance, sinceopen and closed failures represent the two dominant failure-modes both for metallic-contactswitches (still frequently used, especially for video switching) and MOSFET's (Metal-Oxide-Semiconductor Field-Effect Transistors, a common switching element in VLSI circuits).52CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 534.2 The NetworksThe networks we consider in this chapter are non-blocking networks, rearrangeable networks andsuperconcentrators. These networks are designed to achieve specific worst-case performance withrespect to the communication task (though we shall be interested in average-case performancewith respect to failures). Non-blocking networks were introduced by Clos [C53] in 1953 to epito-mize the activity of telephone communication. Bene'S [B64] in 1964 described the rearrangeablenetwork. Rearrangeable networks are useful architectures for parallel machines. Aho, Hoperoftand Ullman [AHU74] in 1974 posed the problem of superconcentrators. Although their hopewas to use them to establish a nonlinear lower bound for the Boolean circuit complexity ofmultiplication, superconcentrators turned out to be central in a number of communication net-works. 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. Terminalsof the network (wires that connect the network to the outside world) are represented by distin-guished vertices called inputs and outputs. Links are represented by vertices other than inputsand outputs, and switches (single-pole single throw, connecting two links) by edges between thetwo corresponding vertices. The three states of each switch in the random switch failure modelare therefore interpreted as (1) the edge ceases to exist (open failure), (2) two vertices of theedge 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^ 54Definition 2.1 Let G be an acyclic directed graph G with a set of n distinguished vertices calledinputs and a set of n other distinguished vertices called outputs. G is a non-blocking n-networkif, given any set of vertex-disjoint direct paths from inputs to outputs, and given any input andany output not involved in these established paths, a new path that is vertex-disjoint from theestablished 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 calledinputs and a set of n other distinguished vertices called outputs. G is a rearrangeable n-networkif, given any one-to-one correspondence between the inputs and the outputs, there exists a set ofn 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 calledinputs and a set of n other distinguished vertices called outputs. G is a n-superconcentratorif, for every r < n, every set of r inputs, and every set of r outputs, there exists a set of rvertex-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 rearrangeablen-network is an n-superconcentrator. From the worst-case performance point of view, thesenetworks all exhibit some type of "non-blocking" property under different assumptions. Non-blocking networks guarantee a dynamic linkage between any pair of idle input and outputregardless the current traffic pattern in the networks. Rearrangeable networks provide an idlepath for a requesting pair (of an idle input and an idle output) by rearranging the connectionpaths for the existing pairs. Superconcentrators assume all inputs (outputs) are equivalent, andCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 55satisfy the communication requirement by providing a flow of disjoint paths (from inputs tooutputs).As before, the measures of complexity applied to such networks are size (the number ofedges), 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. Theexistence of 0(n log n) size and O (log n) depth non-blocking n-networks was proved by Bassalygoand 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] improvedValiant'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 rearrangeablen-networks. See Pippenger [P90] for a detailed survey on the improvements of lower and upperbounds on non-blocking networks, rearrangeable networks and superconcentrators.4.3 Fault-ToleranceGiven 0 < c < 1/2, consider a network N subject to the random switch failure model. Let theevent space ft be the set of all graphs obtained from N. The probability measure on each graphis assigned in accordance to the number of failed edges. More precisely, if a graph G E SI has kfailed edges, the probability that the random instance of N equals G is (2c)k (1 - 2c)"-k , where nis the number of edges in N. Given 0 < 45 < 1, we say N is an (e,b)-non-blocking n-network if theprobability that the random instance of N contains a non-blocking n-network consisting of edgesCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 56of normal state is greater than 1 — 6. Similarly we define an (c, 6)-n-rearrangeable network andan (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 withan 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-superconcen-trator. For this purpose, the exact values of 0 < c < 1/2 and 0 < b < 1 do not matter. To seethis, 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 calledinput and output, in which each edge is randomly and independently subject to closed and openfailures with probabilities of c, respectively; and in which the probabilities that the input andthe output contract into one vertex and that there is no path from the input to the output areboth less than E'.Proposition 4.1 (Moore and Shannon) Let 0 < c < 1/2 and 0 < < E. There is anexplicit construction of an (c,e)-1-network with cc (log2 (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 thesize and depth, we suppose that 0 < E l < E2 < 1/2, and that 4I) is an (E l , 0-n-superconcentratorCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 57with size L and depth D, for some 6 < 1. By Proposition 4.1 there is an (c 2 ,c1 )-1-network AP ofsize a and depth b (a and b are depending only on c2). The result of substituting this network Pfor 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 isa polynomial in c and the constant term of this polynomial vanishes (since the network doesnot fail unless some switch fails). If we replace c by di /62 , every term in this polynomialdecreases to at most 61 /62 times its previous value, and the value of the polynomial decreasesto less than Si . Thus 4, is also an (cbi /6'2 , 451 )-n-superconcentrator. Again, substitute each edgein 41 by an (c, c6. 1 /62 )-1-network and the resulting network is an (c,6 1 )-n-superconcentratorwith 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 StrategyIn this chapter we show that the size and depth of (c, 5)-n-superconcentrators, (c,6)-rearrangeablen-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 boundsfor 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. Thesuccess of this strategy is ascribed to an observation we made earlier, that for any 0 < c < 1/2CHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 58and 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 ordepth) for an (c, S)-n-superconcentrator is a lower bound of all three, and an upper bound foran (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)-non-blocking n-network. A few observations on our upper bound are in order. First, the upperbound 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-tolerantnetwork merely by discarding faulty components and their immediate neighbors, so no difficultcomputations 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 computationsare involved.4.5 The Lower BoundsThe strategy of the lower bound proof is as follows. We associate with each input a neighborhoodcontaining all vertices within a logarithmic distance of the input. We show that for a large setof inputs, these neighborhoods are disjoint (otherwise two inputs would be shorted by dosedfailures with high probability). This gives the lower bound for depth. We then partition thevertices in the neighborhoods of these inputs into zones according to their distance from theinput. We show that for a large number of inputs, each of these zones must have logarithmicCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 59size (otherwise some input would be isolated by open failures with high probability). Summingover the zones of each neighborhood and the neighborhoods of the inputs gives the lower boundfor size.Given a graph G, we say the distance from vertex e l to vertex e2, diSt(ei,e2), is the numberof edges in the shortest path (not necessarily directed) from el to 6 ; the distance from a vertexe 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, containsat 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 exactly3. For if not, we may replace each internal node with degree d > 3 by a "tree" comprisingd — 2 new nodes with degree 3. If we find a set of edge-disjoint paths of length at most 3 in theresulting tree, these will correspond to edge-disjoint paths of no greater length in the originalgraph. 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 otherleaf with distance at most 3 from L. We shall show that there are at most 61/7 bad leaves. If Lis 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" atmost 6 dollars, from which it follow that there are at most 6(1— 2)/7 < 61/7 bad leaves. If someinternal node V collects more than 6 dollars from bad leaves at distance at most 3, then morethan 1 of these bad leaves must be adjacent to one of the 6 or fewer nodes at distance 2 fromCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 60^ :Leaf 0 : Internal nodeFigure 4.1: A bad leafV. But no more than 1 bad leaf can be adjacent to an internal node (see Figure 4.2). Thus atFigure 4.2: An internal node collects at most 6 dollarsleast 1/7 leaves are "good" (that is, not bad). Suppose that there are m good leaves. Let G bea maximal set of edge-disjoint paths, each joining 2 good leaves and each having length at most3. 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 leafwithin distance 3 of L, since L is good, and only a path in G could prevent L from being joinedto 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 leaveswith distance at most 2 from P (see Figure 4.3). It follows that there are at most 4 unluckyleaves for each path in G. Since there are exactly 2 lucky leaves for each path in C, and m > 1/7good leaves (lucky and unlucky), this implies that there are at most m/6 > 1/42 paths in C. ACHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 61BS : Lucky leaf^^ : Unlucky leafFigure 4.3: Each path collects at most 4 dollars from unlucky leavesRemark: The bound "1/42" in Lemma 4.1 can be improved to "1/4", but this requires a moreelaborate 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, containsat 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/,2inputs of 4) have distance (ignoring the direction of each edge) at least (1/8)log2 n from eachother 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 forestby (1) starting with the empty forest, (2) considering each such input in turn, and (3) addingto the forest the longest initial segment of ir(v) that is edge-disjoint from the forest generatedthus far. Thus the resulting forest F has at least n/2 leaves, and each "stretch" (sequence ofconsecutive vertices of degree 2) has length at most j. Let G be the forest obtained from F byreplacing each stretch, together with the edges incident with its vertices, by a single edge. InCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 62G every internal node is of degree at least 3, so we may apply Corollary 4.1 to obtain at leastn/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/84edge-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 inputsof 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 weset 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. ATheorem 4.1 Let 40 be a (1/4, 112)-n-superconcentrator. For all sufficiently large n, 4. has sizeat least (1/256)n(log2 n) 2 and depth at least (1/16) log2 n.Proof Say an input is "good" if it has distance at least (1/8) log2 n from each other input. ByLemma 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 goodinput v, let B(v) denote the set of all edges at distance at most (1/16) log 2 n from v. For anypair v and w of good inputs, the sets B(v) and B(w) must be disjoint, since otherwise thedistance between v and w would be less than (1/8) log2 n. Thus it will suffice to show that, foreach good input v the set B(v) contains at least (1/128)(log 2 n) 2 edges for all sufficiently largen. If an input vo has all n outputs adjacent to some edges in B(vo ), then it is certainly true thatIB(v0 )1 > (1/128)(log2 n)2 , since the number of edges in B(vo ) cannot be less than the numberof outputs adjacent to these edges, and n > (1/128)(log2 n)2 for all sufficiently large n. Thus weCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 63may assume that for each good input v, there is an output w(v) that is not adjacent to an edgein B(v). Consider an arbitrary good input v. Set i . [(1/16) log2 nJ > (1/32) log2 n. PartitionB(v) into subsets Bi(v), • • • , Bi(v), where Bh(v) comprise those edges at distance h from v. LetB*(v) denote the set Bh(v) with the minimum number of edges. It will suffice to show that eachset B*(v) contains at least (1/4) log 2 n edges. Let b be the cardinality of the set B*(v) with theminimum number of edges. It will suffice to show that b > (1/4) log2 n for all sufficiently largen. 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 ofB*(v) are all in the open state, all paths from v to w(v) are broken, and the resulting network iscertainly not an n-superconcentrator. This can happen with probability at most 1/2. Thus wehave 1- (1- (1/4)b)n/2 < 1/2. As before, this implies that b > (1/2) log2 (n/21n 2) > (1/4) log2 nfor all sufficiently large n. A4.6 The Upper BoundsIn 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 constructionfor non-blocking networks, but scale the construction up by a logarithmic factor, and terminatethe recursion with subnetworks of logarithmic size (rather than constant size). We then usenetworks (called "directed grids" in this chapter) of logarithmic by logarithmic size based onthe "hammock" of Moore and Shannon [MS56] to interface the inputs and outputs to theCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 64terminal subnetworks.The basic building blocks of the construction are (c, c' ,t)- expanding graphs and (1, w)- directedgrids. A (c, c', t)-expanding graph is a bipartite directed graph with two distinguished sets of tvertices called inlets and outlets respectively, where every set of c inlets is joined by edges toat least c' outlets (that is, for every set C of c inlets, there exist a set C' of c' outlets, suchthat 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 respectto n) are quite standard. See Bassalygo and Pinsker [BP74] for the probabilistic version, andGabber and Galil [GG81] for an explicit construction. (It needs mention that the first explicitconstruction was presented by Margulis [M73] and the current best explicit construction is dueto Lubotzky, Phillips and Sarnak [LPS88].) An (1, w)-directed grid is a directed graph with wstages and 1 vertices in each stage. A vertex in the j-th stage and the i-th row is denoted by abinary tuple (i, j), 1 < i < 1 and 1 < j < w. An edge from vertex (i, j) to vertex (i', j') existsif 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 gridCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 65Suppose that we wish to construct an (c, 0-non-blocking n-network with n = 4". Set7 = flog4 (4001, so that 160v > 4' 1 > 40v. We first construct a non-blocking 4'1-1-networkthrough the recursive construction illustrated in Pippenger [P82] (Section 9). This network is adirected graph with 2(v + 7) + 1 stages, with 4 141 inputs on stage 0 and 4'4'1 outputs on stage2(v + 7). Each other stage contains 64 . 4' 41 vertices. Edges only exist between some verticesin adjacent stages. The subgraph induced by inputs and vertices in stage 1 consists of 4 11+1-1disjoint 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) consistsof 4P+.7-i disjoint (32 • 4i, 32(1 + .?=-P) 4i, 64 • 4i)-expanding graphs, with each vertex on stagei having 20 out-edges and vertex on stage i + 1 20 having in-edges. The subnetwork from stagev + 7 to stage 2(v + 7) is a mirror image of that from stage 0 to stage v + 7. Network N' isa mirror image of network N if N' is obtained from N by (1) exchanging the inputs with theoutputs 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 andedges incident with them, and let M be the remaining graph. The first stage of M consists of4" disjoint sets vertices, each being the inlets of a (32 • 41 ,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.. Joinedto each vertex in the first stage of ol)i (i = 1, • • .,4") is an edge from an input vertex. CombineM with 4. 1 , • • • , 44g, and the associated inputs by (1) letting the 4" (32 . 41 ,33.07 . 47 ,64 . 41 )-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^ 66and (2) in each such corresponding pair, identifying the inlets of the expanding graph with thevertices in the last stage of the directed grids in any one-to-one fashion. Similarly, construct 4"(v, 64 • 41')-directed grids T i , • • • , We; join an output by edges to every vertex in the last stageof each Ili (j = 1, • • • , 4"); combine Ti , • • • , Te and the associated outputs with M (and theabove combined 4, 1 , • • • , 41) 4 1, and the associated inputs) by identifying vertices of the first stageof 41 1 , • • • , T2v with vertices in the last stage of M. Call the resulting network Al. (See Figure4.5.)Figure 4.5: Network HNetwork H has 2(v -I- v) + 1 = 4v + 1 stages. The 4" inputs and 4" outputs are on stage 0and stage 4v respectively. Each other stage contains 64 • 4"+"Y vertices. The subnetwork fromstage 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 subnetworkfrom stage 2v to stage 4v (called .Arn.) is a mirror image of that from stage 0 to stage 2v (calledCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 67ArE). In particular, the right-hand half of M, called M iz , is a mirror image of Mr, the left-handhalf of M. Network N has 2816ve+1 edges, because there are 2560v4P+ 1 edges in M, at most256(v — 1)4Y+1 edges in 4i and 414, for all 1 < i < 4', and 128 •4P+1 edges adjacent to inputsand outputs.Let 7/ be a vertex of N which is not an input or an output, say a vertex ri of N is faulty, ifan edge <r, n> or <77, > is in open failure or closed failure state. Given a set of vertex-disjointdirect paths from inputs to outputs in N, for an input, an output, or a vertex which is notfaulty, say it is idle if it is not involved in these paths, busy otherwise. Say an (idle) vertex elhas access to another (idle) vertex 6 if there is a path of idle vertices from Ei to 6 . It is clearthat if ei has access to 6 and 6 has access to 6, then el has access to 6 . A network N is amajority-access network if, given any set of directed paths from inputs to outputs, every idleinput 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 least32 . 41 -I- 1 vertices in the last stage of (i.e., strictly more than half) is at least 1— c i v(264c)" ,where c1 = 1/(1 — 132c).Proof. The basic idea is illustrated in [KKL+] and [R89]. Let us begin by estimating theprobability that e does not have access to any vertex at the last stage of 4)e. There is no busyvertex in 4), since e is idle and N is a directed and staged graph. By Menger's Theorem (seee.g., Chapter 5 of [CL86]), there is a "(vertex) cut set" of 4)e (i.e., vertices such that the removalof which and their adjacent edges will separate and the vertices at the last stage) consistingCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 68of faulty vertices only. Consider a cut set C of 1 vertices. It must be 1 > 64 • 4-Y, since 017,t hasthis many rows. The probability of every vertex in C being faulty is at most (44c) 1 , since eachvertex in (N (other than e, which is not in any cut set we consider) is adjacent to at most 22edges (2 in-edges and 20 out-edges). For any given 1, the number of such cut sets C is at mostv3 1 , since there are v vertices at the first row of (Pt to start C, and at most 3 ways (each alongan edge) to continue at each step. Thus the probability that e does not have access to anyvertex at the last stage of 41)t is at mostE 1131(440/ = ci v(132064-4 -Y.l>64.47Consider an arbitrary set S of 32.4ry vertices in the last stage of 40t. The probability that e does( 64 • 41not have access to any vertex in S is at most CW032064.4' . There are at most 32.4  7264.47 such S. This implies that the probability of E having access to at least 32 . 47 + 1 verticesin the last stage of 4 is at least 1 — c iv(264c)', since 64 .^> v. ALemma 4.4 In a (32 . 40 , 33.07 . 4P, 64 . 40)-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), theprobability that it has more than 0.07 . LIP outlets faulty is at most e -0 .05•ImProof. There are 2560.40 edges incident with outlets of the (32.4', 33.07.4 0 , 64 .4P)-expandinggraph (each vertex has 20 in-edges and 20 out-edges). For each such edge, let x j be the randomvariable 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.4AJ1 ^x3.Pr[T > 0.07 • 4"1 = Pr[eT > 0.67.41 < E[eT]/eo.o7•4ACHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 69by Markov's inequality. As xi's are independent,E[eT] =^E[exi] < (1 + 2e02560.4 , < e5120ee•40i= 1since (1 + x)Y < el'. And 5120e€ < 0.02 when e = 10 -6 . Thus the probability that there aremore than 0.07 • 2" outlets faulty is at most 0.02.414-0.074P = e -0.05-11 . ALemma 4.5 The probability that there exists a (32 • 4", 33.07 • 4", 64 • 4 19-expanding graph inMc 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 thenumber of outlets. There are 4 11+1-14 (32 .4", 33.07.41 , 64 • 419-expanding graphs between stagev+ p - 7 and stage p - y +1 of Mc, for all y < p < v+ 7 -1. By Lemma 4.4, the probabilitythat there is an expanding graph with no more than 0.07 • 4" faulty outlets is at mostv+-y-1e--0.05.414 < E 4ve -0.054 -1 < vee -2v ,th=7^ IA=7since 41' > 40v. ALemma 4.6 With probability at least 1-civ(264c)"-v(2/e) 2u, 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 inMr has at most 0.07 • 4" outlets faulty, and each idle input has access to at least 32 • 4 7 + 1vertices in the last stage of (N. It is clear by Lemma 4.3 and Lemma 4.5 that the probability ofthe assumption failing is at most 1 - civ(264c)" - v(2/e) 2v. 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 directedpaths starting from the two inputs may share a vertex at or after the (d+ v)-th stage but cannotCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 70share any vertex before the (d + v)-th stage. It is observed that, for each input e, there are4d — 4d-1 = ,.• .4 4d-1 other inputs e' with relat(4',e)= d, for any d with 1 < d < v. Now supposethat e is an arbitrary idle input, let the subnetwork No of .Al . be (k, and Nk be the subnetworkinduced by vertices that can only be reached by e and 4 k —1 other inputs ei with relat(e,4.1) < k.It is clear that Nk has 4k inputs and 64 . V+k outputs. We shall prove by induction on k thate has access to at least 32 • 414k + 1 outputs of Nk, thus in particular has access to strictlymore than half of the outputs of NN =Pi,. The base case No is obviously true because of ourassumption. Consider Nk+i. The outputs of Nk are linked to the outputs of Nk+i via four(32 .4"-k , 33.07.41+k , 64 . 414k )-expanding graphs (with the inlets being the outputs of Nk andthe outlets being four disjoint subsets of the outputs of Nk +1 ). By the induction hypothesis, ehas access to at least 32.41+k + 1 outputs of Nk. These 32.414k + 1 vertices are joined by edgesto at least 4.33.07.41+k outputs of Nk+i (via the four (32.4 1'+k, 33.07.41+k , 64 .41+k)-expandinggraphs). By our assumption, there are at most 0.07 • 4 1"44+ 1 outputs of Nk-Fi are faulty. Andthere are at most 411-1 - 1 outputs of Nk.4-1 are busy, because each busy output is one-to-onecorresponding (via a directed path) to a busy input of Nk÷i, and there are at most 4 k}1 -1 suchinputs. Thus, e has access to at least 4 . 33.07. 4/+ k — 0.07 • 41"4+1 — 4k+1 +1 > 32 • 47+k+1 +1outputs of Nk+1. This completes our induction. 0Corollary 4.2 With probability at least 1 — c i v(264c)" — v(21e)2Y , the mirror image of Ni isa majority-access network.We observe that if Arc and the mirror image of Ariz are both majority-access networks andthe inputs and outputs of N. are distinct (no two input(s) and output(s) contracting to a singleCHAPTER 4. FAULT-TOLERANT SWITCHING NETWORKS^ 71vertex), then N contains a non-blocking 4"-network of no-failure edges.Lemma 4.7 With probability at most c2v2 (1600 2' , where c2 = 415/(1 - 40e), there exist twoinput(s) and output(s) that contract to a single vertex.Proof. The correctness of the lemma follows four observations. Firstly, any simple path joiningtwo input(s) and output(s) must contain at least 2v edges. Secondly, for any 1 > 2v, thereare at most (64 • 4 1)2 (40)1-2 such paths of length 1, since the degree of inputs and outputs is64 • 41 , and that of the other vertices is at most 40. Note (64 • 412(40)1-2 < 4141,2(41 ,u since41 < 160v. Thirdly, the probability that a path of length 1 gets "shorted" (all edges on the pathare in closed failure state) is less than El. And lastly, there are at most (2 • 4')2 such input oroutput pairs. ATheorem 4.2 Network .Ar is a (10 -6 , 0-non-blocking n-network with at most 410n(log4 n)2edges and 5 log4 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 47 < 160v. The probabilitythat N fails to contain an non-blocking n-network of no-failure edges is less than 2(civ(264c)" -v(2/e)2") + c2v2 (160c)2", by Lemma 4.6, Corollary 4.2, and Lemma 4.7. This value can bearbitrarily small when n = 4" is sufficiently large, given c = 10'. LChapter 5Fault-Tolerant Planar SwitchingNetworks5.1 Planar NetworksThe 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". Pla-nar communication networks (consisting of links and switching elements) provide simultaneouscommunication between various combinations of transmitters and receivers. Today's fabricationtechnologies, such as MOS technology, fabricate these links and switches as transistors in VLSIcircuits. Our interest in this chapter is in fault-tolerant planar networks that accomplish thesimultaneous communication by means of disjoint paths of links and switches from transmittersto receivers.We shall consider the constructions of fault-tolerant planar rearrangeable networks and fault-tolerant planar superconcentrators. A "planar rearrangeable n-network" is a rearrangeable n-72CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^73 network that can be embedded into a plane. And a "planar n-superconcentrator" is an n-superconcentrator that can be embedded into a plane. Similarly, one can define a "planarnon-blocking n-network".There are simple constructions for planar rearrangeable n-networks and planar n-supercon-centrators with polynomial sizes (see next paragraph for details). This is in contrast with thegloomy situation of planar non-blocking n-networks where even the existence of planar non-blocking n-networks for arbitrary n is an open problem.The measures of complexity applied to planar communication networks are the size (thenumber of edges), and the degree (the maximum degree of vertices), since they affect the numberof processing and memory units integrated onto a VLSI chip. An extensive literature existsconcerning the design of planar communication networks. Cutler and Shiloach [CS78] showed agrid construction for planar rearrangeable n-networks with 0(n3 ) edges and a constant degreefor each vertex. Aggarwal et al [AKL+85] proved an S1(n 3 ) size lower bound for any gridconstruction, showing that Cutler-Shiloach construction is asymptotically optimal. Aggarwalet al [AKL+91] further extended their result to multi-layer grid construction, showing thatthe 11(n3 ) lower bound still holds when a constant fraction of the connection paths remain inthe same layer. Klawe and Leighton [KL90] on the other hand, extended the S2(n 3 ) size lowerbound 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 planarn-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 andCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^74planar n-superconcentrators, minimizing size and degree. We shall consider the random switch-failure 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-networksin ft is greater than 1 — 5, where ft is the set of all graphs obtained from N under the randomswitch-failure model; N is a planar (c,(5)-n-supereoncentrator if the probability measure on allplanar n-superconcentrators in S2 is greater than 1 — b.Results of Moore and Shannon EMS561 are useful to build fault-tolerant networks. A con-sequence of Proposition 4.1 is that there is a planar (c, b)-rearrangeable n-network of sizeO(n3 (log n) 2 ), with each vertex having degree 0(log n). To see this, we replace each edgein the Cutler-Shiloach planar rearrangeable n-network by an (c, c')-1-network, where c' = 6 ITand T = 0(n3 ) is the size of the Cutler-Shiloach network. Similarly there is a planar (c, 5)-n-superconcentrator of size O(n2 (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) verticeseach having degree 12(log n). And for any 0 < E < 1/2 and 0 < 5 < 1, we explicitly constructplanar (c, 5)-rearrangeable n-networks with 0(n3 ) edges and 0(log n) degree, having 0(n) ver-tices with degree greater than 4; and we explicitly construct planar (c, 5)-n-superconcentratorswith 0(n2 ) edges and 0(log n) degree, having 0(n) vertices with degree greater than 6. In bothconstructions, the sizes are asymptotically optimal, since 12(n 3 ) and S1(n2 ) edges are neededrespectively, 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^75bility we can find a planar rearrangeable network or a planar superconcentrator contained in thefault-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 performedby an application of a standard network flow algorithm, so again no difficult computations areinvolved.5.2 A Lower Bound on the DegreeIn 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, atleast (ln 2)n inputs of 4 have degree at least (1 /2) log2 n.Proof. We observe that in 01), less than six inputs are adjacent to other inputs. Otherwise theremust exist at least three edges such that two ends of each edge are inputs. Note that if one ofthe 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 withprobability 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 otherinputs, for all sufficiently large n. For each remote input v, let B(v) denote the set of edgesthat are adjacent to v. For any pair v and w of remote inputs, the sets B(v) and B(w) must bedisjoint. 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 theresulting network is certainly not an n-superconcentrator. This can happen with probability atCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^76most 1/2. Let b be the cardinality of the set B(v) with the minimum number of edges. Thuswe have 1- (1- ( 1 /4 )b)(h12)n < 1/2. If we have b < (1/2) log2 n we obtain a contradiction usingthe inequality (1 - xr < e-zY. ACorollary 5.1 Given 0 < c < 1/2 and 0 < 6 < 1, any planar (6,6)-n-superconcentrator mustcontain 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-networkmust contain 11(n) vertices with degree St(log n).5.3 A Fault-Tolerant Planar Rearrangeable NetworkIn this section, we assume c = 10 -4 , and we construct planar (10 -4 , 0-rearrangeable n-networksfor arbitrarily small S. The networks contain 0(n3 ) 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 isessentially due to Cutler and Shiloach [CS78]Lemma 5.2 (Cutler and Shiloach) Given a (2n2 + n) x (2n + 1) grid G, n inputs and noutputs 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 shrinkthe first v of every v + 2n vertices to one vertex. Let the first n of the 2n "shrunk" vertices beCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^77inputs and the rest n be outputs. A vertex is adjacent to an input (output) if it was a neighborof one of the v vertices from which the input (output) is obtained. Call this network Al. (SeeFigure 5.1.)Figure 5.1: The planar (e,45)-rearrangeable n-network NSay a vertex is faulty, if one of its adjacent edges is in open or closed failure state; otherwisesay the vertex is intact. Say a path is intact, if every vertex in the path is intact; say a pathcontaining an input or an output is working, if every vertex in the path is intact except theinput 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 fromthe 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 itCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^78 is faulty; and with the complementary probability it is intact. If there are less than r vertex-disjoint 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, theprobability that it contains less than r intact vertices is at mostE ( /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 thereare at most t places (at the top boundary) to start the cut set and at most 3 ways to continueat each step. Thus the probability that the grid contains less than r vertex-disjoint intact pathsis at mostE t31(32c)1/2 < d i t(2880, .1>2rALemma 5.4 In a s x t grid, shrink the s vertices at the left hand side boundary to one vertexand name it "source". The probability that there is no working path from source to the oppositeside 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 2neven layers contains vertices of the remaining 2n of every v + 2n rows. Each input or output isexclusively contained in one of the 2n odd layers. Each odd layer is a v x (4n + 1) grid, exceptCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^79that the v vertices in the middle vertical line shrink to an input or an output. Applying Lemma5.4 (setting s = v and t = 2n + 1), we have that with probability at least 1— 4d 2n(2n + 1)(24c)',every odd layer has a working path from left side boundary to right side boundary (thus throughthe input or the output in this layer). Each even layer is a 2n x (4n + 1) grid. Applying Lemma5.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 rightside boundary.Imagine vertically partitioning N into three sections. The left section consists of verticesin the left hand side of the inputs and outputs. The middle section consists of 2n inputsand outputs. The rest constitutes the right section. The left section and the right section are2n x (4n 2 +2nv) grids. Applying Lemma 5.3 (setting r = n and t = 4n2 +2nv), we have that withprobability at least 1 — d i (4n2 + 2nv)(288e)n, the left section contains n vertex-disjoint intactpaths 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 thebottom 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 thatany 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 aplanar 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 planarCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^80(10 -4 , (5)-rearrangeable n-network with at most 33n3 edges and 2 log2 n degree, having 2n verticeswith degree greater than 4.Proof. Network A is planar, contains at most 2(4n 2 + 2n log 2 n)(4n + 1) < 33n3 edges for allsufficiently 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 notcontain a planar rearrangeable n-network subnetwork frame (H) is at most4d2 n(2n + 1)(24E)" + 2di n(4n -I- 1)(288c)n + 2d1 (4 n2 + 2rw)(288c)n.This value can be arbitrarily small when n = 2 1' is sufficiently large, given E = 10 -4 . ACorollary 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(n3 ) edges and 0(log n) degree, having 0(n) vertices withdegree greater than 4.5.4 A Fault-Tolerant SuperconcentratorIn this section, we assume that c = 10 -5 , and we construct planar (10 -5 ,5)-n-superconcentratorsfor 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 planarn-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 nedges and n outputs to the n vertices on the bottom boundary of the grid via n edges in anyCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^81 one-to-one correspondence. The resulting graph is a planar n-superconcentrator.Proof. It is straightforward. ALet n = 2". The construction of the planar (c,b)-n-superconcentrator is described in termsof stages. The n inputs make up stage 0. Stage 1 comprises 2n disjoint sets of v vertices calledgroup(j), for 1 < j < 2n. Input i (1 < i < n) is adjacent to the v vertices of group(2i — 1) viav edges. Join the 2nv vertices in stage 1 on a path, i.e., a chain of 2nv — 1 edges, with verticesin 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 verticesin stage 2). Recursively say a vertex is a descendant of group(i) if the two vertices adjacent toit in the previous stage are in group(i) or descendants of group(i). Join the 2n(v — 1) verticesin stage 2 by a chain of 2n(v — 1) — 1 edges, with descendants of group(i) appearing on top ofthat of group(i + 1). In similar ways, construct stage 3, and so on. The number of vertices ineach stage decreases by 2n as one more stage is constructed. Stop the construction after stagev. 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 thebottom boundary of the grid, associate a (v+ 1)-stage subnetwork described above, but replacethe 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 withunspecified 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 withOCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^82Figure 5.2: The planar (c, 6)-n-superconcentrator Mspecified sources.Lemma 5.6 Given a planar graph G, let vo ,v1 ,• • •, vn be a set of vertices occurring anti-clockwise 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, 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 themmay originate at the same vi).Proof. Necessity of the condition is obvious. Before we prove the sufficiency, we need somedefinitions. Given a set of paths {L 1 , • • •, Lp } on the exterior face of G, vertex-disjoint exceptat their ends, we define a full anti-symmetric order relation lies-above among them. We sayLi lies-above Li+1 , for i = 1, • • • ,p — 1, if Upperboundary, L 1 , • • • , Lp form an anti-clockwiseorder, where Upperboundary is the segment between v 1 and vo of the boundary of the exteriorCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^83face that contains no vi, i = 2, • • • , n. Given two simple paths A and B on the exterior faceof G, let cap(A, B) be a new path by starting from A's initial vertex and, between each twoconsecutive intersecting vertices of A and B, choosing the segment that lies above. Similarlywe define cup(A, B) except we choose the segment that lies below (that is, the segment thatdoes not lie above). To prove sufficiency of the condition, we do induction on n. The case whenn = 1 is trivially true. Assuming the proposition is true when n = k, we consider the casen = k + 1. By the condition, there are k + 1 paths Ri, i = 1, • • • , k + 1, from {vi , v2 , • • -, vic+1 }to vo vertex-disjoint except at their ends, and for every interval {vi, • • • , vj+,}, there are rpaths of Ri originated from the interval (some of them may originate at a same vi). Withoutloss of generality, we assume that Ri lies above Ri+i . By induction hypothesis, we have kpaths Pi: vi ---> vo for i = 1, • • • , k, vertex-disjoint except at vo , and k paths Qi: vi ---* vo fori = 2, • • •, k + 1, vertex-disjoint except at vo . Without loss of generality, we assume all Pi's,Q i's and Ri's are simple. Let T1 = cap(Pi , R1 ), 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 , andT1 , • • • , Tk+i are vertex-disjoint except at vo . This completes the induction. LApplying 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 < nand 1 < r < n — i + 1, there are r working paths from a subset of the r inputs to the rightside boundary of the grid, vertex-disjoint except initial vertices, then there are n vertex-disjointworking paths from the n inputs to the right side boundary of the grid.CHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^84Corollary 5.4 shows that to ensure the existence of n vertex-disjoint working paths from ninputs to the right side boundary of the grid, besides the distinctness of n inputs (that is, notwo inputs contract to one vertex, due to a shorted path linking the two inputs), one needs toexamine 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 rconsecutive 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 withmessage flow with unspecified sources) is sufficient. (The success of this method in dealingwith message flows with specified sources is ascribed to the planarity of the network. In thenon-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 andthe 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 rworking paths in M 1 from a subset of r consecutive inputs to the right side boundary of thegrid, 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 benoted are (1) each vertex in M 1 is adjacent to at most 6 edges, (2) any cut set separating inputsi, 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 isCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^85 at most 2n + v. ALemma 5.8 With probability at most 4d4n2v2 (6c)", where d4 = 1/(1 - 6c), there exist twoinput(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 v2 61-2 < v26 1 such paths of length 1, since the degree of inputsand outputs is v, and that of the other vertices is at most 6. ATheorem 5.2 For any arbitrarily mall 6, when n is sufficiently large, M is a planar (10 -5 ,6)n-superconcentrator with at most 9n2 edges and log2 n degree, having at most 2n vertices withdegree greater than 6.Proof. Network M is planar, contains at most 2(2n(3v 2/2))+8n 2 < 9n2 edges for all sufficientlylarge n. Network M has a maximum degree log 2 n, and only 2n vertices in M (inputs andoutputs) have degree greater than 6. By Lemma 5.8, the probability that 2n inputs and outputsremain distinct is at least 1 - 4d4n 2v2 (6c)v. By Lemma 5.7, the probability that there exist nvertex-disjoint working paths from the n inputs to the right side boundary of the grid is at least1 - d3n2 (2n + v)(432c) 42 , since we have at most n2 conditions to examine; a similar propertyholds 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 -4d4n2v2 (6c)", networkM is a planar n-superconcentrator. The value2d3n 2 (2n + v)(432c) 42 + 4d4n2v2(6c)vCHAPTER 5. FAULT-TOLERANT PLANAR SWITCHING NETWORKS^86can be arbitrarily small when n = 2" is sufficiently large, given e = 10 -5 . 0Corollary 5.5 Given 0 < e < 1/2 and 0 < b' < 1, there is an explicit construction for aplanar (c,6)-n-superconcentrator with 0(n 2 ) edges and O(log n) degree, having 0(n) verticeswith degree greater than 6.Chapter 6Related Graph Theory andCombinatorics ResultsIn this chapter, we summarize some graph theory and combinatorics results obtained along thecourse 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 TreeLemma 4.1 of Chapter 4 shows that given a tree with 1 leaves, in which each internal nodehas degree at least 3, there exist 1/42 edge-disjoint paths each containing at most 3 edges andhaving 2 leaves as its ends. Define II(/, d) to be the set of trees with 1 leaves and degree at leastd for each internal node. Given T E 11(1, d), let T(h) be the maximum number of edge-disjointpaths in T, such that each path contains at most h edges and has 2 leaves as its ends. Definep(1, d, h) = inIn---TE11(1,d){T(h )}. Let r(d, h) =^P(11'h)Lemma 6.1 The limit r(d, h) exists.87CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^88Proof. 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. Thatis, Tn and Tm satisfy Tn (h) = p(n, d, h) and Tm (h) = p(m, d, h), where Ti(h) is the maximumnumber of edge-disjoint paths in T.; with each path joining 2 leaves and having length at mosth. Let 6 and E2 be two arbitrary leaves in Tn and Tm, and v1 and v2 be the parents of 6 ande2, respectively. Delete 6 and e2, and join v1 and v2 by an edge. The resulting graph is a treein II(n m — 2,d). Call it Tn+m_2. Clearlyp(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 Tni.m_2 that joins two leaves, one inTn and one in Tm , is at most one (the path must contain edge (v 1 , v2 )). Thus the observationfollows from p(1 + 2, d, h) < p(1, d, h) + 1, for all 1 > 1. Let ai = p(i, d, h) + 2. We havean-Fm < an + am ,for all n > 1 and m > 1. By Fekete's Lemma (see [PS72], p. 23 and p. 198, problem 98), (tilleither converges or diverges to —oo, as 1^oo. That is, p(1,d,h)11= (ai — 2)/1 either convergesor diverges to —oo, as 1 oo. But the second case is impossible, since p(1, d, h) > 0. AIt is clear that r(d, h) is a function monotone increasing with respect to either parameter, dor h. To determine the value of r(d, h) in the general case is an interesting open problem. Wepresent 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^89Lemma 6.2 Given a tree T of I leaves, in which each internal node has degree at least 3, thereexist 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 exactly3. The case I < 5 is trivial. We assume 1 > 5. The number of internal nodes is I — 2. Say aninternal node is a type-i internal node (and for abbreviation type-i node), 0 < i < 2, if there arei 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 ro +r1 -Fr2 = 1-2 and r1 -1-2r2 = 1.This implies that r 2 = ro + 2. For each type-1 leaf e, denote by TT the subtree consisting of allvertices having distance at most 3 from e. Let xo , x i , x2 , x3 and x4 be the number of Ta's thatcontain no leaf, one leaf, two non-sibling leaves, two sibling leaves and three leaves among thefour vertices that have distance 3 from e, respectively. For the simplicity of notation, we referto the corresponding leaf E as an "x0 , x i , x2 , x3 or x4 leaf" and to the corresponding subtree TT"of the xo , x i , x2 , x3 or x4 kind." (See Figure 6.1.) We observe that in each of the xi + x 2 + x4o : Leaf^o : Internal nodeFigure 6.1: TT of the xo, x 1 , x2, x3 and x4 kindsubtrees TT of the x i , x2 or x4 kind, there is a path of 3 edges having e and another xi, x2CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^90or x4 leaf ik as its ends. Note there are at most 2 other x 1 , x 2 or x4 leaves (in or adjacentto having distance 3 from e or ye. Thus there are at least (x 1 + x2 + x4)/4 vertex-disjointpaths in T, each containing 3 edges and having 2 leaves as its ends. On the other hand, the 2r 2leaves adjacent to r 2 type-2 nodes form r2 vertex-disjoint paths in T, each containing 2 edgesand having 2 leaves as its ends. And these r2 paths of 2 edges are vertex-disoint from the above(x 1 + x 2 + x4 )/4 paths of 3 edges. Therefore, the number of vertex-disjoint paths in T, suchthat each path joins 2 leaves and contains at most 3 edges is at least (x 1 + x2 + x4 )/4 + r2 .Note that in each of the subtrees TT of the x3 kind, there exists a type-2 node and, this type-2node can be contained in only one Te of the x3 kind (see II of the x3 kind in Figure 6.1). Thusx3 < r2 . Next we shall show that xo < r2 . To see this, we (1) arbitrarily choose a type-2 node7 (the existence of y is guaranteed by r 2 > ro + 2 > 2), and, (2) suspend the tree T from 7 asa root. Call the new rooted tree Troot. Note that in Troot 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 atype-0 node 77, and this e is the only sibling of 77 (see Te of the x o kind in Figure 6.1). Thusxo < ro < r2 . Therefore the number of vertex-disjoint paths in T, each joining 2 leaves andcontaining at most 3 edges is(xi + x2 + x4)/4 + rz= (xi + x2 + x4 + 4r2)/4> (x0 + x1 + X2 + X3 + X4 + 2r2)/4= (r1 + 2r2 )/4= 1/4.This completes our proof. ACHAPTER 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 andFigure 6.3. Let ti be the number of leaves in Ti and ai the number of leaves in Ai. ThusFigure 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 andki if h is odd1r(3,h) <3h-56h-4 if h is evenCHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^92ci be the maximum number of edge-disjoint paths in Ti and Ai, respectively, each containing atmost 3 edges and having 2 leaves as its ends. It is obvious that ci < bi < + 1, and c1 = 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. Thusany path in Ai+i containing at most 3 edges and having 2 leaves as its ends must be confinedin one of the 2 subtree Ai's. From the recursionsai+i = 2ai + 2andCi+i = 2Ciand 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,Proof. In the case of odd h, let us assume h = 2k + 1. We recursively construct a sequence oftrees T1, T2, • • •. See Figure 6.4 and Figure 6.5. Let ti be the number of leaves in Ti and ai thenumber 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 inTi 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^94As before, we have ci < bi < ci +1, and we have c 1 = 2k. It is clear that ci+1 = 2ci + 2k — 2 forall i > 1. From the recursions= 2ai + 4k — 2andci+1 = 2ci + 2k — 2and the boundary values a l = 4k + 2 and c 1 = 2k, we haveai = k2 i+ 2 — (4k — 2)andci = k2 i+ 1 — 2` — (2k — 2).Therefore^r(3, h) = r(3, 2k + 1) < lim b•^2k — 1^h — 2^t i^ai^4k^2h — 2 .In the case of even h where h = 2k, the sequence of trees T1 , T2, • • • we construct is illustratedin 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 — 4andci+1 = 3ci + 2k — 3.And the new boundary values are a l = 4k and Cl = 2k — 1. Solving these recursions, we haveai = 2k3 2 — 2 3i-1 — (2k — 2) and ci = k3i 5.3'222k-3  Thereforer(3, h) = r(3, 2k) < tlimo ci^6k — 5 — 3h — 5a i 12k — 4 6h- 4CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^95Figure 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^96Similar techniques can be applied to construct trees with arbitrary internal degree, thusyielding 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)kd(d-1)(d-21k—d 2d(d-1)(d-2)k-2dfd-1)1c/-2)k—(d2 —d-1) 2d(d-1)(d-2)k-2(d2 —2d-1)d(d-1)(d-2)k—(d2 —d-1)2d(d-1)(d-2)k-2d(d-2)r(d,h) <if h = 2k + 1 and d is oddif h = 2k + 1 and d is evenif h = 2k and d is oddif h = 2k and d is evenProof. We shall only present the recursive constructions for the trees for the upper bound. Forthe case of h = 2k +1 and odd d, see Figure 6.8 and 6.9. For the case of h = 2k +1 and evend, see Figure 6.10 and 6.11. For the case of h = 2k and odd d, see Figure 6.12 and 6.13. Forthe 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 dCHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^97Figure 6.9: Tree T1 4. 1 with h = 2k + 1 and odd dFigure 6.10: Tree T1 with h = 2k +1 and even dCHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^98Figure 6.11: Tree Ti+1 with h = 2k + 1 and even dEiAiFigure 6.12: Tree T1 with h = 2k and odd dCHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^99Ai+1Figure 6.13: Tree Ti+1 with h = 2k and odd dTAiFigure 6.14: Tree T1 with h = 2k and even dCHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^100Figure 6.15: Tree Ti+1 with h = 2k and even d6.As mentioned earlier, r(d, h) is monotone increasing with respect to either parameter d orh. Therefore, for any fixed h > 2, limd„, r(d, h) exists, since 1/2 is an upper bound for anyr(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,d—+lim r(d, h) = 1/2.ooThis 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 numberof internal nodes in T, that there exists at least 1==1 1 edge-disjoint paths in T, each joining 22d-4leaves and containing 2 edges. Let r be the number of internal nodes in T. The base case wherer = 1 (that is, a "star" — one internal node and 1 leaves) is trivial: there are L//2 .1 > (1 — 1)/2edge-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 degreesover 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, otherwisecondition (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. Removethese x leaves and treat e as a leaf. The resulting graph is a tree T' E II(/ — x + 1, d) withd-4)(1--x +1)r — 1 internal nodes. By induction, there exist at least ( ^edge-disjoint paths, each2d-4containing 2 edges and having 2 leaves of T' as its ends. These paths are edge-disjoint fromthe previous (x — 1)/d paths (paths pairing leaves adjacent to e), and all leaves of T' but e areleaves of T. Therefore, there are at least(x — 1)/2 + (d — 4)(1 — x +1) 1> d — 42d — 412d — 4edge-disjoint paths in T, each joining 2 leaves and containing 2 edges. AIntuition tells us that a result analogous to Theorem 6.2 with respect to h may exist. Weare not, however, able to prove or disprove the correctness of our intuition.CHAPTER 6. RELATED GRAPH THEORY AND COMBINATORICS RESULTS^1026.2 Vertex-Disjoint Paths in a Planar GraphIn Chapter 5, Lemma 5.6 statesLemma 5.6 Given a planar graph G, let vo , v1 , • • •, vn be a set of vertices occurring anti-clockwise around the boundary of the exterior face of G. There are n paths vi .- vo inG (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 themmay originate at the same vj).In a similar way, we are able to proveTheorem 6.3 Given a planar graph G, let v1 , • • • , vn , un , • • • , u 1 be a set of 2n vertices oc-curring anti-clockwise around the boundary of the exterior face of G. There are n vertex-disjoint 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 ,• • • ,vi+,- 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 andspecified destinations.Bibliography[A82]^R. Aleliunas, "Randomized Parallel Communication", ACM Symp. on Principlesof Distributed Computing, 1 (1982) 60-72.[AHU74]^A. V. Aho, J. E. Hoperoft and J. D. Ullman, The Design and Analysis of ComputerAlgorithms (Addison-Wesley, Reading, MA, 1974).[AKL+85] A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial and A. Wigderson, "Multi-layerGrid 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 LowerBound 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", Combi-natorica 3 (1983) 1-19.[AKS83b] M. Ajtai, J. Komi& and E. Szemeredi, "An O(nlogn) Sorting Network", ACMSymp. 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 aNonblocking 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., EnglewoodCliffs, 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.103BIBLIOGRAPHY^ 104[BMR91]^B. Bhargava, E. Mafia and J. Riedl, "Communication in the RAID DistributedDatabase System", Computer Networks and ISDN Systems, 21 (1991) 81-92.[BP74]^L. A. Bassalygo and M. S. Pinsker, "Complexity of Optimum Non-blocking Switch-ing Network without Reconnections. Problems of Info. Transmission, 9 (1974) 64-66.[BRS+90] P. Banerjee, J. T. Rahmeh, C. Stunkel, V. S. Nair, K. Roy, V. Balasubramanianand J. A. Abraham, "Algorithm-Based Fault Tolerance on a Hypercube Multipro-cessor", IEEE Trans. Comput., Vol. 39, No. 9 (Sept. 1990) 1132-1145.[BW89]^A. E. Barbour and A. S. Wojcik, "A General, Constructive Approach to Fault-tolerant 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) 406-424.[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 Managementof 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 Net-works", Bell Sys. Tech. J., 56 (1977) 1431-1446.[CH80]^F. R. K. Chung and F. K. Hwang, "The Connection Patterns of Two CompleteBinary Trees", SIAM J. Discr. Math., 1 (1980) 322-335.[CGG+85] W. Crowther, J. Goodhue, R. Gurwitz, R. Rettberg and R. Thomas, "The Butter-fly 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) 253-278.[CS90]^M. Chen and K. G. Shih, "Adaptive Fault-Tolerant Routing in Hypercube Multi-computers", 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, Gener-alizers and Generalized Connectors with Limited Depth", ACM Symp. on Theoryof 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 Infor-matica, June 1990. '[En18]^T. Engset, "Die Wahrscheinlichkeitsrechnung zur Bestimmung der Wahleranzahlin Automatischen Fernsprechamtern", Electroteck. Z., 31 (1918) 304-305.[Er18]^A. K. Erlang, "Solution of Some Problems in the Theory of Probabilities of Signif-icance 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 Superconcentra-tors", J. Computer and System Sciences, 22 (1981), 407-420.[GG84]^J. Greene and A. E. Gamal, "Configuration of VLSI Arrays in the Presence ofDefects", J. ACM, Vol. 31, No. 4 (Oct. 1984), 694-717.[GL73]^L. R. Goke and G. J. Lipovski, "Banyan Networks for Partitioning MultiprocessorSystems", 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 andArtificial Intelligence (McGraw-Hill Publishing Inc., 1989).[11J88]^R. W. Hockney and C. R. Jesshope, Parrallel Computers 2: Architecture, Pro-gramming 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 Circuitsby 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 Digi-tal Services in a Worldwide Intelligent Network", Computer Networks and ISDNSystems, 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 Computingwith Faulty Arrays of Processors", IEEE Symp. on Foundations of Computer Sci-ence, 31 (1990) 285-296.BIBLIOGRAPHY^ 106[KL90]^M. Klawe and F. T. Leighton, "A Tight Lower Bound on the Size of Planar Per-mutation 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 Nos-trand Reinhold Company Inc., New York, NY, 1985).[L55] C. Y. Lee, "Analysis of Switching Networks", Bell Sys. Tech. J., 34 (1955) 1287-1315.[L56] P. Le Gall, "Etude du Blocage Dans les Systems de Commutation TelephoniquesAutomatique 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", IEEETrans. Comput. 24 (1975) 1145-1155.[L86]^M. Luby, "A Simple Parallel Algorithm for the Maximal Independent Set Prob-lem", SIAM J. Computing, 15 (1986) 1036-1053.[L88]^M. Luby, "Removing Randomness in Parallel Computation without a ProcessorPenalty", IEEE Symp. on Foundations of Computer Science, 29 (1988) 162-173.[L90]^T. Lengauer, "VLSI Theory", Handbook of Theoretical Computer Science, Chapter16, Edited by J. van Leeuwen (Elsevier Science Publishers B. V., 1990).[L92]^G. Lin, "Fault Tolerant Planar Communication Networks", ACM Symp. on Theoryof 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 Yangand R. Zak, "The Network Architecture of the Connection Machine CM-5", ACMSymp. 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 forRouting Around Faults on Multibutterflies", IEEE Symp. on Foundation of Com-puter Science, 30 (1989) 384-389.[LMT89]^T. Leighton, F. Makedon and I. Tollis, "A 2n — 2 Steps Algorithm for Routing inan n x n Array with Constant-Size Queues", ACM Symp. on Parallel Algorithmsand Architectures, 1 (1989) 328-335.[LP91]^G. Lin and N. Pippenger, "Parallel Algorithms for Routing in Non-blocking Net-works", 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 Routingin Permutation Networks", IEEE Trans. on Computers, 30 (1981) 93-100.[LT79]^R. Lipton and R. Tarjan, "Applications of a Planar Separator Theorem", SIAMJ. 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" (PartI 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 FaultTolerance", 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.[1382A]^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 ComputerScience, Chapter 15, Edited by J. van Leeuwen (Elsevier Science Publishers B.V., 1990).[P91] N. Pippenger, "The Blocking Probability of Spider-Web Networks", RandomStructures 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. Tele-traffic Congr. (1973) 318/1-4.[PL92]^N. Pippenger and G. Lin, "Fault-Tolerant Circuit-Switching Networks", ACMSymp. on Parallel Algorithms and Architectures, 4 (1992) 229-235, also acceptedfor 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 Foundationsof Computer Science, 28 (1987) 185-194.[R89]^P. Raghavan, "Robust Algorithms for Packet Routing in a Mesh", ACM Symp. onParallel Algorithms and Architectures, 1 (1989) 344-350.[RS86]^N. Robertson and P. D. Seymour, "Graph Minors VI. Disjoint Paths Across aDisc", J. of Combinatorial Theory, Series B 41 (1986) 115-138.[RSV90]^U. Ramachandran, M. Solomon and M. K. Vernon, "Hardware Support for Inter-process 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 DistributedParallel Machine, I", IEEE Symp. on Computer Architectures, 4 (1977) 105-177.[Si85]^H. J. Siegel, Interconnection Networks for Large-Scale Parallel Processing: Theoryand Case Studies (D. C. Heath and Company, Lexington, MA/Toronto, Canada,1985).[SP63]^J. Squire and S. Palais, "Programming and Design Considerations of a HighlyParallel Computer", AFIPS Conference Proc., 23 (1963) 395-400.[St85]^W. Stallings, Data and Computer Communications (Macmillan Publishing Com-pany, 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 Com-plexity of Evaluating Game Trees", IEEE Symp. on Foundations of ComputerScience, 27 (1986) 29-38.BIBLIOGRAPHY^ 109[T68]^K. Takagi, "Design of Multi-Stage Link Systems by Means of Optimal ChannelGraphs", 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 Lay-out", Networks, Vol. 12 (1982) 187-316.[U82]^E. Upfal, "Efficient Schemes for Parallel Communication", ACM Symp. on Prin-ciples of Distributed Computing, 1 (1982) 55-59.[U89]^E. Upfal, "An O(logN) Deterministic Packet Routing Scheme", ACM Symp. onTheory of Computing, 21 (1989) 241-250.[V75]^L. G. Valiant, "On Nonlinear Lower Bounds in Computational Complexity", ACMSymp. 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 Cut-through Switching Network", Computer Networks and ISDN Systems, 21 (1990)41-51.

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items