iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/3-540-68530-8_22
On Nonblocking Properties of the Beneš Network | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Nonblocking Properties of the Beneš Network

  • Conference paper
  • First Online:
Algorithms — ESA’ 98 (ESA 1998)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1461))

Included in the following conference series:

  • 1056 Accesses

Abstract

A network is called nonblocking if every unused input can be connected by a path through unused edges to any unused output, regardless of which inputs and outputs have been already connected. The Beneš network of dimension n is shown to be strictly nonblocking if only a suitable chosen fraction of 1/n of inputs and outputs is used. This has several consequences. First, there is a very simple strict sense nonblocking network with N = 2n inputs and outputs, namely a (n + log n + 1)-dimensional Beneš network. Its depth is O(log N), it has O(N log2 N) edges and it is not constructed of expanders. Secondly it leads to a (3 log N)-competitive randomized algorithm for a (log N)-dimensional Beneš network and a O(log2 N)-competitive randomized algorithm for a (log N)-dimensional hypercube, for routing permanent calls.

This research has been supported by the Grant Agency of the Czech Republic under grant No. 102/97/1055 and by European Community under project ALTEC-KIT INCO-COP 96-0195.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Arora, F. T. Leighton, and B. M. Maggs. On-line algorithms for path selection in a nonblocking network. SIAM Journal on Computing, 25(3):600–625, June 1996.

    Article  MATH  MathSciNet  Google Scholar 

  2. B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosén. Competitive non-preemptive call control. In Proceedings of SODA, pages 312–320, 1994.

    Google Scholar 

  3. B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proceedings of FOCS, pages 412–423, 1994.

    Google Scholar 

  4. L. A. Bassalygo and M. S. Pinsker. Complexity of an optimum nonblocking switching network without reconnections. Problems of Information Transmission (translated from Problemy Peredachi Informatsii (Russian)), 9:64–66, 1974.

    Google Scholar 

  5. B. Beizer. The analysis and synthesis of signal switching networks. In Proceedings of the Symposium on Mathematical Theory of Automata, pages 563–576. Brooklyn, NY, Brooklyn Polytechnic Institute, 1962.

    Google Scholar 

  6. V. E. Beneš. Permutation groups, complexes and rearrangeable connecting network. The Bell System Technical Journal, 43,4:1619–1640, 1964.

    MathSciNet  MATH  Google Scholar 

  7. D. G. Cantor. On non-blocking switching networks. Networks, 1:367–377, 1972.

    Article  MATH  MathSciNet  Google Scholar 

  8. P. Feldman, J. Friedman, and N. Pippenger. Wide-sense nonblocking networks. SIAM Journal on Discrete Mathematics, 1, 1988.

    Google Scholar 

  9. J. A. Garay, I. S. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. In Proceedings of the 2nd Israeli Symposium on Theory of Computing and Systems, pages 285–293, 1993.

    Google Scholar 

  10. J. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In Proceedings of FOCS, pages 86–95, 1996.

    Google Scholar 

  11. J. Kleinberg and É. Tardos. Approximations for the disjoint paths problem in high-diameter planar networks. In Proceedings of STOC, pages 26–35, 1995.

    Google Scholar 

  12. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes. Morgan Kaufmann, San Mateo, 1992.

    MATH  Google Scholar 

  13. R. J. Lipton and A. Tomkins. Online interval scheduling. In Proceedings of SODA, pages 302–311, 1994.

    Google Scholar 

  14. R. Melen and J. S. Turner. Nonblocking multirate networks. SIAM Journal on Computing, 18(2):301–313, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  15. C. E. Shannon. Memory requirements in a telephone exchange. Bell Syst. Tech. Journal, 29:343–349, 1950.

    MathSciNet  Google Scholar 

  16. J. Turner and N. Yamanaka. Architectural choices in large scale atm switches. Technical Report WUCS-97-21, Department of Computer Science, Washington University Saint Louis, 1997.

    Google Scholar 

  17. A. Waksman. A permutation network. Journal of the ACM, 15(1):159–163, January 1968.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

    Petr Kolman

Authors
  1. Petr Kolman
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Elettronica e Informatica, Università di Padova, via Gradenigo 6/A, I-35131, Padova, Italy

    Gianfranco Bilardi  & Geppino Pucci  & 

  2. Department of Electrical Engineering and Computer Science, The University of Illinois at Chicago, 851 South Morgan Street - 1009 SEO, Chicago, IL, 60607-7053, USA

    Gianfranco Bilardi

  3. Dipartimento di Matematica Applicata e Informatica, Università “Cá Foscari” di Venezia, via Torino 155, I-30173, Venezia Mestre, Italy

    Giuseppe F. Italiano

  4. Dipartimento di Matematica Pura e Applicata, Università di Padova, via Belzoni 7, I-35131, Padova, Italy

    Andrea Pietracaprina

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kolman, P. (1998). On Nonblocking Properties of the Beneš Network. In: Bilardi, G., Italiano, G.F., Pietracaprina, A., Pucci, G. (eds) Algorithms — ESA’ 98. ESA 1998. Lecture Notes in Computer Science, vol 1461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68530-8_22

Download citation

  • DOI: https://doi.org/10.1007/3-540-68530-8_22

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64848-2

  • Online ISBN: 978-3-540-68530-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation