[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Permutation routing in all-optical product networks

  • Conference paper
  • First Online:
Parallel and Distributed Processing (IPPS 1999)

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

Included in the following conference series:

Abstract

In this paper we study permutation routing techniques for all-optical networks. Firstly, we show some lower bounds on the number of wavelengths needed for implementing any permutation on an alloptical network in terms of bisection of the network. Secondly, we study permutation routing on product networks by giving a lower bound on the number of wavelengths needed, and presenting permutation routing algorithms for the wavelength non-conversion and conversion models, respectively. Finally, we investigate permutation routing on a cube-connectedcycles network by showing that the number of wavelengths needed for implementing any permutation in one round is [2 log n], which improves on a previously known general result for bounded degree graphs by a factor of O(log3 n) for this special case.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber and M. Sudan. Efficient routing in optical networks. J. of the ACM 46:973–1001, 1996.

    Article  MathSciNet  Google Scholar 

  2. N. Alon, F. R. K. Chung, and R. L. Graham. Routing permutations on graphs via matchings. SIAM J. Discrete Math. 7:516–530, 1994.

    MathSciNet  Google Scholar 

  3. B. Awerbuch, Y. Azar, and S. Plotkin. Throughput competitive on-line routing. Proc. of 34th IEEE Symp. on Found. of Computer Science, 1993, 32–40.

    Google Scholar 

  4. B. Awerbuch, Y. Bartal, A. Fiat and A. Rosén. Competitive non-preemptive call control. Proc. of 5th ACM-SIAM Symp. on Discrete Algorithms, 1994, 312–320.

    Google Scholar 

  5. Y. Aumann and Y. Rabani. Improved bounds for all optical routing. Proc. of 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, 567–576.

    Google Scholar 

  6. R. A. Barry and P. A. Humblet. Bounds on the number of wavelengths needed in WDM networks. In LEOS’92 Summer Topical Mtg. Digest 1992, 114–127.

    Google Scholar 

  7. R. A. Barry and P. A. Humblet. On the number of wavelengths and switches in all-optical networks. IEEE Trans. Commun. 42:583–591, 1994.

    Article  Google Scholar 

  8. M. Baumslag and F. Annexstein. A unified framework for off-line permutation routing in parallel networks. Math. Systems Theory 24:233–251, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  9. B. Beauquier, J-C Bermond, L. Cargano, P. Hell, S. Pérnces, and U. Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. Proc. of 2nd Workshop on Optics and Computer Science, IPPS’97, April, 1997.

    Google Scholar 

  10. P. E. Green. Fiber-Optic Communication Networks. Prentice Hall, 1992.

    Google Scholar 

  11. Q-P Gu and H. Tamaki. Routing a permutation in the hypercube by two sets of edge-disjoint paths. Proc. 10th IPPS., IEEE CS Press, 561–576, 1996.

    Google Scholar 

  12. J. M. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. Ph.D dissertation, Dept. of EECS, MIT, Cambridge, Mass., 1996.

    Google Scholar 

  13. J. Kleinberg and E. Tardos. Disjoint paths in densely embedded graphs. Proc. of 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, 52–61.

    Google Scholar 

  14. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays· Trees · Hypercubes. Morgan Kaufmann Publishers, CA, 1992.

    Google Scholar 

  15. C.L. Liu. Introduction to Combinatorial Mathematics McGraw-Hill, NY, 1968.

    MATH  Google Scholar 

  16. A. D. McAulay. Optical Computer Architectures. John Wiley, 1991.

    Google Scholar 

  17. M. Mihail, C. Kaklamanis, and S. Rao. Efficient access to optical bandwidth. Proc. of 36th IEEE Symp. on Founda. of Computer Science, 1995, 548–557.

    Google Scholar 

  18. R. K. Pankaj. Architectures for Linear Lightwave Networks. Ph.D. dissertation. Dept. of EECS, MIT, Cambridge, Mass., 1992.

    Google Scholar 

  19. R. K. Pankaj and R.G. Gallager. Wavelength requirements of all-optical networks. IEEE/ACM Trans. Networking 3:269–280, 1995.

    Article  Google Scholar 

  20. G. R. Pieris and G. H. Sasaki. A linear lightwave Beneš network. IEEE/ACM Trans. Networking 1:441–445, 1993.

    Article  Google Scholar 

  21. F. Preparata and J. Vuillemin. The cube-connected cycles: A versatile network for parallel computation. Comm. ACM 24: 300–309, 1981.

    Article  MathSciNet  Google Scholar 

  22. Y Rabani. Path coloring on the mesh. Proc. of 37th Annual IEEE Symposium on Foundations of Computer Science, Oct., 1996, 400–409.

    Google Scholar 

  23. P. Raghavan and E. Upfal. Efficient routing in all-optical networks. Proc. of 26th Annual ACM Symposium on Theory of Computing, May, 1994, 134–143.

    Google Scholar 

  24. R. Ramaswami. Multi-wavelength lightwave networks for computer communication. IEEE Communications Magazine 31:78–88, 1993.

    Article  Google Scholar 

  25. R. J. Vitter and D. H. C. Du. Distributed computing with high-speed optical networks. IEEE Computer 26:8–18, 1993.

    Google Scholar 

  26. A. Youssef. Off-line permutation routing on circuit-switched fixed-routing networks. Networks 23:441–448: 1993.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Australian National University, 0200, Canberra, ACT, Australia

    Weifa Liang

  2. Computer Science Telecommunications Program, University of Missouri-Kansas City, 64110, Kansas City, MO, USA

    Xiaojun Shen

Authors
  1. Weifa Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaojun Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

José Rolim Frank Mueller Albert Y. Zomaya Fikret Ercal Stephan Olariu Binoy Ravindran Jan Gustafsson Hiroaki Takada Ron Olsson Laxmikant V. Kale Pete Beckman Matthew Haines Hossam ElGindy Denis Caromel Serge Chaumette Geoffrey Fox Yi Pan Keqin Li Tao Yang G. Chiola G. Conte L. V. Mancini Domenique Méry Beverly Sanders Devesh Bhatt Viktor Prasanna

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag

About this paper

Cite this paper

Liang, W., Shen, X. (1999). Permutation routing in all-optical product networks. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097970

Download citation

  • DOI: https://doi.org/10.1007/BFb0097970

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-65831-3

  • Online ISBN: 978-3-540-48932-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation