Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Selfish Resource Allocation in Optical Networks

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 7878))

Included in the following conference series:

Abstract

We introduce Colored Resource Allocation Games as a new model for selfish routing and wavelength assignment in multifiber all-optical networks. Colored Resource Allocation Games are a generalization of congestion and bottleneck games where players have their strategies in multiple copies (colors). We focus on two main subclasses of these games depending on the player cost: in Colored Congestion Games the player cost is the sum of latencies of the resources allocated to the player, while in Colored Bottleneck Games the player cost is the maximum of these latencies. We investigate the pure price of anarchy for three different social cost functions and prove tight bounds for each separate case. We first consider a social cost function which is particularly meaningful in the setting of multifiber all-optical networks, where it captures the objective of fiber cost minimization. Additionally, we consider the two usual social cost functions (maximum and average player cost) and obtain improved bounds that could not have been derived using earlier results for the standard models for congestion and bottleneck games.

This research has been co-financed by the European Union (European Social Fund–ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) — Research Funding Program: THALIS Investing in knowledge society through the European Social Fund.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973)

    Article MATH  Google Scholar 

  2. Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14, 124–143 (1996)

    Article MathSciNet MATH  Google Scholar 

  3. Roughgarden, T.: Selfish routing and the price of anarchy. The MIT Press (2005)

    Google Scholar 

  4. Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  5. Nomikos, C., Pagourtzis, A., Zachos, S.: Routing and path multicoloring. Inf. Process. Lett. 80(5), 249–256 (2001)

    Article MathSciNet MATH  Google Scholar 

  6. Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Routing and wavelength assignment in multifiber WDM networks with non-uniform fiber cost. Computer Networks 50(1), 1–14 (2006)

    Article MATH  Google Scholar 

  7. Andrews, M., Zhang, L.: Complexity of wavelength assignment in optical network optimization. In: INFOCOM. IEEE (2006)

    Google Scholar 

  8. Andrews, M., Zhang, L.: Minimizing maximum fiber requirement in optical networks. J. Comput. Syst. Sci. 72(1), 118–131 (2006)

    Article MathSciNet MATH  Google Scholar 

  9. Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC, pp. 67–73 (2005)

    Google Scholar 

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

    Article  Google Scholar 

  11. Margara, L., Simon, J.: Wavelength assignment problem on all-optical networks withk 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 

  12. Bampas, E., Pagourtzis, A., Pierrakos, G., Potika, K.: On a noncooperative model for wavelength assignment in multifiber optical networks. IEEE/ACM Trans. Netw. 20(4), 1125–1137 (2012)

    Article  Google Scholar 

  13. Busch, C., Magdon-Ismail, M.: Atomic routing games on maximum congestion. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol. 4041, pp. 79–91. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  14. Nash, J.: Non-cooperative games. The Annals of Mathematics 54(2), 286–295 (1951)

    Article MathSciNet MATH  Google Scholar 

  15. Banner, R., Orda, A.: Bottleneck routing games in communication networks. In: INFOCOM. IEEE (2006)

    Google Scholar 

  16. Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Mitzenmacher, M. (ed.) STOC, pp. 513–522. ACM (2009)

    Google Scholar 

  17. Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  18. Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4), 385–409 (2001)

    Article MATH  Google Scholar 

  19. Kannan, R., Busch, C.: Bottleneck congestion games with logarithmic price of anarchy. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 222–233. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  20. Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 29–38. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Bilò, V., Moscardelli, L.: The price of anarchy in all-optical networks. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 13–22. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  22. Bilò, V., Flammini, M., Moscardelli, L.: On Nash equilibria in non-cooperative all-optical networks. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 448–459. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  23. Georgakopoulos, G.F., Kavvadias, D.J., Sioutis, L.G.: Nash equilibria in all-optical networks. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 1033–1045. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  24. Milis, I., Pagourtzis, A., Potika, K.: Selfish routing and path coloring in all-optical networks. In: Janssen, J., Prałat, P. (eds.) CAAN 2007. LNCS, vol. 4852, pp. 71–84. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  25. Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proceedings. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 295–304 (October 2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Elec. & Comp. Engineering, National Technical University of Athens, Greece

    Evangelos Bampas & Aris Pagourtzis

  2. School of Electrical Engineering & Computer Sciences, UC Berkeley, USA

    George Pierrakos

  3. Computer Science Dept., Cornell University, USA

    Vasilis Syrgkanis

Authors
  1. Evangelos Bampas

    You can also search for this author inPubMed Google Scholar

  2. Aris Pagourtzis

    You can also search for this author inPubMed Google Scholar

  3. George Pierrakos

    You can also search for this author inPubMed Google Scholar

  4. Vasilis Syrgkanis

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Engineering, Department of Computer Engineering and Informatics, University of Patras, 265 00, Patras, Greece

    Paul G. Spirakis

  2. LSI Department, Edif Omega, Universitat Politècnica de Catalunya, Campus Nord, Jordi Girona 1-3, 08034, Barcelona, Spain

    Maria Serna

Rights and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bampas, E., Pagourtzis, A., Pierrakos, G., Syrgkanis, V. (2013). Selfish Resource Allocation in Optical Networks. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_3

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

[8]ページ先頭
©2009-2025 Movatter.jp