Skip to main content
SpringerLink
Log in

Resource Allocation Problems in Multifiber WDM Tree Networks

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2003)

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

Included in the following conference series:

Abstract

All-optical networks with multiple fibers lead to several interesting optimization problems. In this paper, we consider the problem of minimizing the total number of fibers necessary to establish a given set of requests with a bounded number w of wavelengths, and the problem of maximizing the number of accepted requests for given fibers and bounded number w of wavelengths. We study both problems in undirected tree networks T=(V,E) and present approximation algorithms with ratio 1 + 4|E|log|V|/OPT and 4 for the former and ratio 2.542 for the latter. Our results can be adapted to directed trees as well.

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. Awerbuch, B., Azar, Y., Fiat, A., Leonardi, S., Rosén, A.: On-line competitive algorithms for call admission in optical networks. Algorithmica 31(1), 29–43 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  2. Awerbuch, B., Bartal, Y., Fiat, A., Rosén, A.: Competitive non-preemptive call control. In: Proceedings of the 5th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 1994), pp. 312–320 (1994)

    Google Scholar 

  3. Beauquier, B., Bermond, J.-C., Gargano, L., Hell, P., Perennes, S., Vaccaro, U.: Graph problems arising fromwavelength-routing in all-optical networks. In: Proceedings of IPPS 1997, Second Workshop on Optics and Computer Science, WOCS (1997)

    Google Scholar 

  4. Chekuri, C., Mydlarz, M., Shepherd, F.: Multicommodity demand flow in a tree. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 410–425. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  5. Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(E logD) time. Combinatorica 21(1), 5–12 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  6. Erlebach, T., Jansen, K.: Maximizing the number of connections in optical tree networks. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 179–188. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  7. Erlebach, T., Jansen, K.: The complexity of path coloring and call scheduling. Theoretical Computer Science 255(1-2), 33–50 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Erlebach, T., Jansen, K., Kaklamanis, C., Mihail, M., Persiano, P.: Optimal wavelength routing in directed fiber trees. Theoretical Computer Science 221, 119–137 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  9. Erlebach, T., Pagourtzis, A., Potika, K., Stefanakos, S.: Resource allocation problems in multifiber WDM tree networks. TIK-Report 178, Computer Engineering and Networks Laboratory (TIK), ETH Zürich (August 2003)

    Google Scholar 

  10. Ferreira, A., Perennes, S., Richa, A., Rivano, H., Stier, N.: On the design of multifiber WDM networks. In: Proc. AlgoTel 2002, Mèze, France, May 2002, pp. 25–32 (2002)

    Google Scholar 

  11. Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  12. Gargano, L., Vaccaro, U.: Routing in all-optical networks: Algorithmic and graph-theoretic problems. In: Althöfer, I., et al. (eds.) Numbers, Information and Complexity, pp. 555–578. Kluwer Academic Publishers, Dordrecht (2000)

    Google Scholar 

  13. Golumbic, M.C., Jamison, R.E.: The edge intersection graphs of paths in a tree. J. Comb. Theory Series B 38(1), 8–22 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  14. Green, P.E.: Fiber Optic Networks. Prentice Hall, Englewood Cliffs (1993)

    Google Scholar 

  15. Klasing, R.: Methods and problems of wavelength-routing in all-optical networks. Technical Report CS-RR-348, Department of Computer Science, University of Warwick, Presented as invited talk at the MFCS 1998 Workshop on Communications (September 1998)

    Google Scholar 

  16. Li, G., Simha, R.: Onthewavelength assignment problem in multifiber optical tree networks. In: Terabit Optical Networking: Architecture, Control, and Management Issues, number 4213 in Proceedings of SPIE, November 2000, pp. 84–91 (2000)

    Google Scholar 

  17. Li, G., Simha, R.: On the wavelength assignment problem in multifiber WDM star and ring networks. IEEE/ACM Transactions on Networking  9(1), 60–68 (2001)

    Article  Google Scholar 

  18. Margara, L., Simon, J.: Wavelength assignment problem on all-optical networks with k fibres per link. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 768–779. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  19. Margara, L., Simon, J.: Decidable properties of graphs of all-optical networks. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 518–529. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  20. Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Path multi-coloring in weighted graphs. In: Proceedings of the 8th Panhellenic Conference on Informatics, Nicosia, Cyprus, November 2001, vol. I, pp. 178–186 (2001)

    Google Scholar 

  21. Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Fiber cost reduction and wavelength minimization in multifiber WDM networks (2003) (manuscript)

    Google Scholar 

  22. Nomikos, C., Pagourtzis, A., Zachos, S.: Routing and path multicoloring. Information Processing Letters 80(5), 249–256 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  23. Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pp. 134–143 (1994)

    Google Scholar 

  24. Ramaswami, R., Sivarajan, K.N.: Routing and wavelength assignment in all-optical networks. IEEE/ACM Transactions on Networking 3(5), 489–500 (1995)

    Article  Google Scholar 

  25. Wan, P.-J., Liu, L.: Maximal throughput in wavelength-routed optical networks. In: Multichannel Optical Networks: Theory and Practice. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 46, pp. 15–26. AMS, Providence (1998)

    Google Scholar 

  26. Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 830–831 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Engineering and Networks Laboratory (TIK), ETH Zürich, CH-8092, Zürich, Switzerland

    Thomas Erlebach & Stamatis Stefanakos

  2. Department of Computer Science, School of ECE, National Technical University of Athens, Greece

    Aris Pagourtzis & Katerina Potika

Authors
  1. Thomas Erlebach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aris Pagourtzis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Katerina Potika
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stamatis Stefanakos
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Information and Computing Sciences, Utrecht University, The Netherlands

    Hans L. Bodlaender

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Erlebach, T., Pagourtzis, A., Potika, K., Stefanakos, S. (2003). Resource Allocation Problems in Multifiber WDM Tree Networks. In: Bodlaender, H.L. (eds) Graph-Theoretic Concepts in Computer Science. WG 2003. Lecture Notes in Computer Science, vol 2880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39890-5_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-39890-5_19

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20452-7

  • Online ISBN: 978-3-540-39890-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation