Energy-efficient network routing with discrete cost functions

Lin Wang; Antonio Fernández Anta; Fa Zhang; Chenying Hou; Zhiyong Liu

doi:10.1007/978-3-642-29952-0_32

Energy-efficient network routing with discrete cost functions

Lin Wang^*
, Antonio Fernández Anta
, Fa Zhang
, Chenying Hou
, Zhiyong Liu

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings
Pages	307-318
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-29952-0_32
Publication status	Published - 2012
Externally published	Yes
Event	9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 - Beijing, China Duration: 16 May 2012 → 21 May 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7287 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
Country/Territory	China
City	Beijing
Period	16/05/12 → 21/05/12

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

approximation
network optimization
network routing

Access to Document

10.1007/978-3-642-29952-0_32

Cite this

Wang, L., Fernández Anta, A., Zhang, F., Hou, C., & Liu, Z. (2012). Energy-efficient network routing with discrete cost functions. In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings (pp. 307-318). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS). https://doi.org/10.1007/978-3-642-29952-0_32

Wang, Lin ; Fernández Anta, Antonio ; Zhang, Fa et al. / Energy-efficient network routing with discrete cost functions. Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. pp. 307-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0b79e0e1f13b4006b140b7378c00d325,

title = "Energy-efficient network routing with discrete cost functions",

abstract = "Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.",

keywords = "approximation, network optimization, network routing",

author = "Lin Wang and \{Fern{\'a}ndez Anta\}, Antonio and Fa Zhang and Chenying Hou and Zhiyong Liu",

year = "2012",

doi = "10.1007/978-3-642-29952-0\_32",

language = "English",

isbn = "9783642299513",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "307--318",

booktitle = "Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings",

note = "9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 ; Conference date: 16-05-2012 Through 21-05-2012",

}

Wang, L, Fernández Anta, A, Zhang, F, Hou, C & Liu, Z 2012, Energy-efficient network routing with discrete cost functions. in Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7287 LNCS, pp. 307-318, 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012, Beijing, China, 16/05/12. https://doi.org/10.1007/978-3-642-29952-0_32

Energy-efficient network routing with discrete cost functions. / Wang, Lin; Fernández Anta, Antonio; Zhang, Fa et al.
Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. p. 307-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Energy-efficient network routing with discrete cost functions

AU - Wang, Lin

AU - Fernández Anta, Antonio

AU - Zhang, Fa

AU - Hou, Chenying

AU - Liu, Zhiyong

PY - 2012

Y1 - 2012

N2 - Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.

AB - Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.

KW - approximation

KW - network optimization

KW - network routing

UR - https://www.scopus.com/pages/publications/84860993904

U2 - 10.1007/978-3-642-29952-0_32

DO - 10.1007/978-3-642-29952-0_32

M3 - Conference contribution

AN - SCOPUS:84860993904

SN - 9783642299513

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 307

EP - 318

BT - Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings

T2 - 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012

Y2 - 16 May 2012 through 21 May 2012

ER -

Wang L, Fernández Anta A, Zhang F, Hou C, Liu Z. Energy-efficient network routing with discrete cost functions. In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. p. 307-318. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-29952-0_32

Energy-efficient network routing with discrete cost functions

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this