Notes on the Complexity of Switching Networks
Network theory and applicationsPublished 1 January 2001
Hung Q. Ngo, Ding‐Zhu Du
Citations20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
There are various complexity measures for switching networks and communication networks in general, which include the number of switching components, the delay time of signal propagating through the network, the complexity of path selection algorithms, and the difficulty of physically designing the network.
Abstract
There are various complexity measures for switching networks and communication networks in general. These measures include, but not limited to, the number of switching components, the delay time of signal propagating through the network, the complexity of path selection algorithms, and the complexity of physically designing the network. This chapter surveys the study of the first measure, and partially the second measure. It is conceivable that the number of switching components, or the "size" of a network, affects directly the third and fourth measures.
Keywords
Computer ScienceMathematics
Matrix Analysis
22,234 Citations1985Roger A. Horn, Charles R. Johnson
Cambridge University Press eBooksMatrix Analysis
10,056 Citations1985Roger A. Horn, Charles R. Johnson
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Distance-Regular Graphs
2,112 Citations1989Andries E. Brouwer, Arjeh M. Cohen +1 more
Bell System Technical JournalA Study of Non-Blocking Switching Networks
1,721 Citations1953Charles Clos
COMBINATORICAEigenvalues and expanders
1,170 Citations1986Noga Alon
It is shown that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first.
COMBINATORICARamanujan graphs
1,003 Citations1988Alexander Lubotzky, Ralph S. Phillips +1 more
The girth ofX is asymptotically ≧4/3 logk−1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.
Journal of Combinatorial Theory Series Bλ1, Isoperimetric inequalities for graphs, and superconcentrators
866 Citations1985Noga Alon, Vitali Milman
Kluwer international series in engineering and computer scienceSwitching and Traffic Theory for Integrated Broadband Networks
515 Citations1990Joseph Y. Hui
This chapter discusses switching theory, application of Sorting for Self-Routing and Non-Blocking Switches, and Queueing for Multi-Stage Packet Networks.
COMBINATORICASorting inc logn parallel steps
513 Citations1983Miklós Ajtai, János Komlós +1 more
A sorting network withcn logn comparisons where in thei-th step of the algorithm the contents of registersRj, andRk, wherej, k are absolute constants then change their contents or not according to the result of the comparison.
Journal of the ACMA Permutation Network
444 Citations1968Abraham Waksman
The construction of a switching network capable of n-permutation of its input terminals to its output terminals is described and an algorithm is given for the setting of the binary cells in the network according to any specified permutation.
Journal of Combinatorial Theory Series BExistence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q
310 Citations1994Moshe Morgenstern
For any prime power q, explicit constructions for many infinite linear families of q + 1 regular Ramanujan graphs are given as Cayley graphs of PGL2 or PSL2 over finite fields, with respect to very simple generators.
SIAM Journal on Algebraic and Discrete MethodsExplicit Concentrators from Generalized <i>N</i>-Gons
251 Citations1984R. Michael Tanner
Random Structures and AlgorithmsRandom Cayley graphs and expanders
247 Citations1994Noga Alon, Yuval Roichman
It is shown that for every group G of order n, and for a set S of c(δ) log n random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph X(G, S) is at most (1 - δ).
SIAM Journal on Discrete MathematicsBounds for Dispersers, Extractors, and Depth-Two Superconcentrators
223 Citations2000Jaikumar Radhakrishnan, Amnon Ta‐Shma
The method of Kovari, Sos, and Turan can be extended to give tight lower bounds for extractors, in terms of both the number of truly random bits needed to extract one additional bit and the unavoidable entropy loss in the system.
On the second eigenvalue of random regular graphs
222 Citations1989Joel Friedman, J. Kahn +1 more
The following is an extended abstract for two papers, one written by Kahn and Szemeredi, the other written by Friedman, which have been combined at the request of the STOC committee.
Journal of the ACMParallel permutation and sorting algorithms and a new generalized connection network
198 Citations1982David Nassimi, Sartaj Sahni
O(k log n) algorithms are obtained to permute and sort n data items on cube and perfect shuffle computers with n/sup 1+1/k/ processing elements, 1>k>log n, which lead directly to a generalized-connection-network construction having o(klog n) delay and o(kn/Sup 1-kn/ sup 1-1-k/log- n) contact pairs.
COMBINATORICAEigenvalues, geometric expanders, sorting in rounds, and ramsey theory
131 Citations1986Noga Alon
It is shown that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges.
Theory of Computing SystemsSpace bounds for a game on graphs
127 Citations1976Wolfgang J. Paul, Robert E. Tarjan +1 more
It is shown that for each graph withn vertices and maximum in-degreed, there is a pebbling strategy which requires at mostc(d) n/logn pebbles, and this bound is tight to within a constant factor.
Journal of Computer and System SciencesGraph-theoretic properties in computational complexity
123 Citations1976Leslie G. Valiant
The extent to which a set of related graph-theoretic properties can be used to accont for the superlinear complexity of computational problems is explored and certain limited lower bounds can be proved by means of such properties.
Series on applied mathematicsThe Mathematical Theory of Nonblocking Switching Networks
116 Citations1998Frank K. Hwang
NetworksGeneralized multi‐stage connection networks
113 Citations1972Gerald M. Masson, B. W. Jordan
Multi-stage connection networks in which each input terminal can be connected to any number of output terminals are developed and it is shown that such networks have fewer cross-points than the product of input and output terminals for a sufficiently large number of inputand output terminals.
Journal of the ACMEigenvalues and expansion of regular graphs
112 Citations1995Nabil Kahalé
Improved results on random walks on expanders and selection networks of smaller size than was previously known are obtained and shown to be the best bound one can obtain using the second eigenvalue method.
COMBINATORICAExpanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
103 Citations1999Avi Wigderson, David Zuckerman
Cambridge University Press eBooksCayley graphs: eigenvalues, expanders and random walks
100 Citations1995Alexander Lubotzky
SIAM Journal on Discrete MathematicsWide-Sense Nonblocking Networks
96 Citations1988Paul Feldman, Joel Friedman +1 more
This paper presents a new method for constructing wide-sense nonblocking generalized connectors with n inputs and outputs and size O, and with depth k and size $O ( n 1 + 1/k) and $O 1 - 1/ k.
NetworksOn non‐blocking switching networks
96 Citations1971David G. Cantor
It is shown that σ(a, a) ⩽ C ae2√log a·log 2.2 shows the minimal number of switches necessary to connect a inputs to b outputs using a non-blocking network.
Bell System Technical JournalMemory Requirements in a Telephone Exchange
87 Citations1950Claude E. Shannon
Comparison of any proposed design with the minimum requirements obtained from the relations gives a measure of the efficiency in memory utilization of the design.
Bell System Technical JournalOn Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
82 Citations1979Fan Chung
Improve bounds for the number of edges (which can be viewed as approximations of the cost) in some networks by combinatorial analysis by studying various communication networks.
COMBINATORICAExpanders obtained from affine transformations
80 Citations1987Shuji Jimbo, Akira Maruoka
COMBINATORICACommunication in bounded depth circuits
78 Citations1994P. Pudl�k
It is shown that rigidity of matrices can be used to prove lower bounds on depth 2 circuits and communication graphs and a general nonlinear bound on a certain type of circuits is proved.
Journal of the ACMShifting Graphs and Their Applications
77 Citations1976Nicholas Pippenger, Leslie G. Valiant
Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied and bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity of shifting, merging, and matching problems.
Information Processing LettersThe complexity of testing whether a graph is a superconcentrator
71 Citations1981Manuel Blum, Richard M. Karp +3 more
A very surprising result due to Valiant is the existence of superconcentrators with n inputs and O(n) edges.
On non-linear lower bounds in computational complexity
68 Citations1975Leslie G. Valiant
It is shown that the graph of any algorithm for any one of a number of arithmetic problems (e.g. polynomial multiplication, discrete Fourier transforms, matrix multiplication) must have properties closely related to concentration networks.
Journal of AlgorithmsBetter expanders and superconcentrators
64 Citations1987Noga Alon, Zvi Galil +1 more
Better expanders are constructed than those previously known and used to construct explicitly n-superconcentrators with ≈ 122.74n edges; much less than the previous most economical construction.
Journal of Computer and System SciencesOn rearrangeable and non-blocking switching networks
52 Citations1978Nicholas Pippenger
Switching networks of the type used in telephone exchanges are studied, with emphasis on a particular class of networks possessing great structural symmetry, and it is shown that there are non-blocking networks with roughly 90N log 3 N contacts.
SIAM Journal on Algebraic and Discrete MethodsRearrangeable Networks with Limited Depth
51 Citations1982Nicholas Pippenger, Andrew Chi-Chih Yao
This work is interested in the minimum possible number of switches in rearrangeable networks in which the depth is at most k and the length of the longest path from an input to an output is at least k.
COMBINATORICARecursive construction for 3-regular expanders
48 Citations1994Miklós Ajtai
An algorithm which inn3 (logn)3 time constructs a 3-regular expander graph onn vertices by substituting a pair of edges of the graph by a new Pair of edges so that the total number of cycles of lengths decreases.
Journal of Computer and System SciencesSuperconcentrators of depth 2
31 Citations1982Nicholas Pippenger
It is shown that every n-superconcentrator of depth 2 has size μ(n log n); and that there exist n- superconcentrators on which the pebble game can be played in space S and time O(( n log n)2S), for a wide range of values of S.
Journal of Computer and System SciencesSelf -Routing Superconcentrators
25 Citations1996Nicholas Pippenger
SIAM Journal on Algebraic and Discrete MethodsExpanders and Diffusers
25 Citations1986Marshall W. Buck
Journal of Computer and System SciencesSuperconcentrators of depths 2 and 3; odd levels help (rarely)
25 Citations1994Noga Alon, Pavel Pudlák
COMBINATORICANatural bounded concentrators
24 Citations1995Moshe Morgenstern
The first known direct construction for linear families of bounded concentrators is given and the results are simple natural bounded concentrations.
SIAM Journal on Algebraic and Discrete MethodsSome Graph-Colouring Theorems with Applications to Generalized Connection Networks
23 Citations1985David Kirkpatrick, Maria Klawe +1 more
This work gives a simple explicit construction for generalized n-connectors with 2k - 1 stages and O ( n 1 + 1 / k) edges, which is asymptotically the best explicit construction known for generalized connectors.
SIAM Journal on ComputingGeneralized Connectors
21 Citations1978Nicholas Pippenger
This paper deals with an idealized version of the problem of designing a network capable of providing any such pattern of simultaneous connections, and shows that d(n)=c(n)+O(n), * Received by the editors May 13, 1977.
Journal of Combinatorial Theory Series AExpansion Properties of Cayley Graphs of the Alternating Groups
19 Citations1997Yuval Roichman
The proof of the last result combines spectral and representation theory techniques with direct combinatorial arguments.
Symposium on the Theory of ComputingSuperconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
18 Citations1983Danny Dolev, Cynthia Dwork +2 more
Theoretical Computer ScienceA geometric construction of a superconcentrator of depth 2
16 Citations1984Roy Meshulam
An N-superconcentrator of depth 2, with 3 N32+O(N1712) edges, is constructed by essentially duplicating the lines vs. points incidence graph of a projective plane by the following theorem.
COMBINATORICAA lower bound on strictly non-blocking networks
14 Citations1988Joel Friedman
It is proved that a strictly non-blockingn-connector of depthk must haveω(n1+1/(k−1) edges.
SIAM Journal on Algebraic and Discrete MethodsA New Lower Bound for the Number of Switches in Rearrangeable Networks
13 Citations1980Nicholas Pippenger
For the commonest model of rearrangeable networks with n inputs and n outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches.
Theoretical Computer ScienceSize bounds for superconcentrators
12 Citations1983G. Lev, Leslie G. Valiant
It is proved that any N-superconcentrator of indegree two has at least 4N - o(N) nodes, and a lower bound of 3N log2 N edges is given that improves on the best bounds previously known for values of N up to several thousand.
NetworksA two‐stage network with dual partial concentrators
9 Citations1993F. K. Hwang, G. W. Richards
This study extends this study to a network with two partial concentrators: one on the input side and the other on the output side, and shows that a particular construction that meets the rearrangeability conditions actually yields a broadcast network.
The IMA volumes in mathematics and its applicationsConstructing Error-Correcting Codes from Expander Graphs
9 Citations1999Daniel A. Spielman
A derivation of asymptotically good error-correcting codes from expander graphs is surveyed, which can be encoded as well as decoded in linear time.
Discrete Applied MathematicsThe capacity of the subarray partial concentrators
5 Citations1992F. K. Hwang, Gaylord W. Richards
This paper uses the cyclic property of the construction given by Richards and Hwang to prove c≥M2+2M−2, the best result possible for M=3 since it coincides with an upper bound previously proved.
Discrete Applied MathematicsAn improved upper bound for the subarray partial concentrators
2 Citations1992Xiao Hu, F. K. Hwang
This paper disproves an upper bound of the capacity of the subarray partial concentrator given by Du, Hwang and Richards and proves to be the best by Richards and Hwang.