On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks

被引：0

作者：

Bampas, Evangelos ^{[1
]}

Pagourtzis, Aris ^{[1
]}

Pierrakos, George ^{[1
]}

Potika, Katerina ^{[1
]}

机构：

[1] Natl Tech Univ Athens, Sch Elect & Comp Engn, Athens 15780, Greece

来源：

ALGORITHMS AND COMPUTATION, PROCEEDINGS | 2008年 / 5369卷

关键词：

Selfish wavelength assignment; non-cooperative games; price of anarchy; multifiber optical networks; path multicoloring;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 all fiber multiplicity that her color (wavelength) choice incurs and the social cost is the maximum player cost.. We investigate the price of anarchy of games and provide 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.

引用

页码：159 / 170

页数：12

共 25 条

[1] Minimizing maximum fiber requirement in optical networks [J].

Andrews, M ;

Zhang, L .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (01) :118-131

[2]

Andrews M, 2004, LECT NOTES COMPUT SC, V3142, P134

[3]

ANDREWS M, 2006, INFOCOM 2006

[4]

ANSHELEVICH E, 2004, FOCS, P295

[5]

BANNER R, 2006, INFOCOM 2006

[6]

Bilò V, 2005, LECT NOTES COMPUT SC, V3404, P448

[7]

Bilò V, 2004, LECT NOTES COMPUT SC, V3104, P13

[8]

Busch C, 2006, LECT NOTES COMPUT SC, V4041, P79

[9]

Caragiannis I, 2005, LECT NOTES COMPUT SC, V3827, P809, DOI 10.1007/11602613_81

[10]

CHIEN S, 2007, SODA, P169

← 1 2 3 →