Contribution to Book
On a Non-Cooperative Model for Wavelength Assignment in Multifiber Optical Networks
Algorithms and Computation
(2008)
Abstract
We study path multicoloring games that describe situations in which selfish entities possess communication requests in a multifiber all-optical network. Each player is charged according to the maximum fiber multiplicity that her color (wavelength) choice incurs and the social cost is the maximum player cost. We investigate the price of anarchy of such games and provide two different upper bounds for general graphs—namely the number of wavelengths and the minimum length of a path of maximum disutility, over all worst-case Nash Equilibria—as well as matching lower bounds which hold even for trees; as a corollary we obtain that the price of anarchy in stars is exactly 2. We also prove constant bounds for the price of anarchy in chains and rings in which the number of wavelengths is relatively small compared to the load of the network; in the opposite case we show that the price of anarchy is unbounded.
Keywords
- Selfish wavelength assignment,
- non-cooperative games,
- price of anarchy,
- multifiber optical networks,
- path multicoloring
Disciplines
Publication Date
2008
Series
Lecture Notes in Computer Science
DOI
10.1007/978-3-540-92182-0_17
Publisher Statement
SJSU users: Use the following link to login and access this article via SJSU databases.
Citation Information
Evangelos Bampas, Aris Pagourtzis, George Pierrakos and Katerina Potika. "On a Non-Cooperative Model for Wavelength Assignment in Multifiber Optical Networks" Algorithms and Computation Vol. 5369 (2008) p. 159 - 170 Available at: http://works.bepress.com/aikaterini-potika/25/