Document Open Access Logo

Competitive Packet Routing with Priority Lists

Authors Tobias Harks, Britta Peis, Daniel Schmand, Laura Vargas Koch

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.49.pdf
  • Filesize: 488 kB
  • 14 pages

Document Identifiers

Author Details

Tobias Harks
Britta Peis
Daniel Schmand
Laura Vargas Koch

Cite As Get BibTex

Tobias Harks, Britta Peis, Daniel Schmand, and Laura Vargas Koch. Competitive Packet Routing with Priority Lists. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.49

Abstract

In competitive packet routing games, packets are routed selfishly through a network and scheduling policies at edges determine which packages are forwarded first if there is not enough capacity on an edge to forward all packages at once. We analyze the impact of priority lists on the worst-case quality of pure Nash equilibria. A priority list is an ordered list of players that may or may not depend on the edge. Whenever the number of packets entering an edge exceeds the inflow capacity, packets are processed in list order. We derive several new bounds on the price of anarchy and stability for global and local priority policies. We also consider the question of the complexity of computing an optimal priority list. It turns out that even for very restricted cases, i.e., for routing on a tree, the computation of an optimal priority list is APX-hard.

Subject Classification

Keywords
  • packet routing
  • Nash equilibrium
  • price of anarchy
  • priority policy
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yossi Azar, Lisa Fleischer, Kamal Jain, Vahab S. Mirrokni, and Zoya Svitkina. Optimal coordination mechanisms for unrelated machine scheduling. Operations Research, 63(3):489-500, 2015. Google Scholar
  2. Sayan Bhattacharya, Janardhan Kulkarni, and Vahab S Mirrokni. Coordination mechanisms for selfish routing over time on a tree. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 186-197, 2014. Google Scholar
  3. Vittorio Bilò. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In Approximation and Online Algorithms - 10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers, pages 215-228, 2012. Google Scholar
  4. Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, and Paul Spirakis. Direct routing: Algorithms and complexity. Algorithmica, 45(1):45-68, 2006. Google Scholar
  5. Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica, 66(3):512-540, 2013. Google Scholar
  6. George Christodoulou, Elias Koutsoupias, and Akash Nanavati. Coordination mechanisms. Theoretical Computer Science, 410(36):3327-3336, 2009. Google Scholar
  7. Richard Cole, José R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, and Neil Olver. Inner product spaces for minsum coordination mechanisms. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 539-548, 2011. Google Scholar
  8. Roberto Cominetti, José R. Correa, and Omar Larré. Existence and uniqueness of equilibria for flows over time. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, pages 552-563, 2011. Google Scholar
  9. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  10. Lester R Ford Jr and Delbert Ray Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6(3):419-433, 1958. Google Scholar
  11. Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, and Shang-Hua Teng. Competitive routing over time. Theoretical Computer Science, 412(39):5420-5432, 2011. Google Scholar
  12. Nicole Immorlica, Li Erran Li, Vahab S Mirrokni, and Andreas S Schulz. Coordination mechanisms for selfish scheduling. Theoretical Computer Science, 410(17):1589-1598, 2009. Google Scholar
  13. Ronald Koch, Ebrahim Nasrabadi, and Martin Skutella. Continuous and discrete flows over time. Mathematical Methods of Operations Research, 73(3):301-337, 2011. Google Scholar
  14. Ronald Koch, Britta Peis, Martin Skutella, and Andreas Wiese. Real-time message routing and scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pages 217-230, 2009. Google Scholar
  15. Ronald Koch and Martin Skutella. Nash equilibria and the price of anarchy for flows over time. Theory of Computing Systems, 49(1):71-97, 2011. Google Scholar
  16. Janardhan Kulkarni and Vahab S. Mirrokni. Robust price of anarchy bounds via LP and fenchel duality. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1030-1049, 2015. Google Scholar
  17. Frank Thomson Leighton, Bruce Maggs, and Satish Rao. Packet routing and job-shop scheduling in 𝒪(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  18. Frank Thomson Leighton, Bruce Maggs, and Andrea W Richa. Fast algorithms for finding 𝒪(congestion + dilation) packet routing schedules. Combinatorica, 19(3):375-401, 1999. Google Scholar
  19. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994. Google Scholar
  20. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, 1991. Google Scholar
  21. Britta Peis, Martin Skutella, and Andreas Wiese. Packet routing: Complexity and algorithms. In Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers, pages 217-228, 2009. Google Scholar
  22. Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM, 62(5):32, 2015. Google Scholar
  23. Martin Skutella. An introduction to network flows over time. In Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, pages 451-482, 2008. Google Scholar
  24. Aravind Srinivasan and Chung-Piaw Teo. A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM Journal on Computing, 30(6):2051-2068, 2001. Google Scholar
  25. William L Wilkinson. An algorithm for universal maximal dynamic flows in a network. Operations Research, 19(7):1602-1612, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact