Simultaneous routing and flow rate optimization in energy-aware computer networks

Przemysław Jaskóła ; Piotr Arabas ; Andrzej Karbowski

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016), p. 231-243 / Harvested from The Polish Digital Mathematics Library

Résumé

The issue of energy-aware traffic engineering has become prominent in telecommunications industry in the last years. This paper presents a two-criteria network optimization problem, in which routing and bandwidth allocation are determined jointly, so as to minimize the amount of energy consumed by a telecommunication infrastructure and to satisfy given demands represented by a traffic matrix. A scalarization of the criteria is proposed and the choice of model parameters is discussed in detail. The model of power dissipation as a function of carried traffic in a typical software router is introduced. Then the problem is expressed in a form suitable for the mixed integer quadratic programming (MIQP) solver. The paper is concluded with a set of small, illustrative computational examples. Computed solutions are implemented in a testbed to validate the accuracy of energy consumption models and the correctness of the proposed traffic engineering algorithm.

Détail

Publié le : 2016-01-01

Zbl 1336.90024

EUDML-ID : urn:eudml:doc:276689

Bibliographie

[000] Bertsekas, D. and Gallager, R. (1992). Data Networks, Second Edition, Prentice-Hall International, Inc., Englewood Cliffs, NJ. | Zbl 0734.68006

[001] Bertsekas, D.P. and Tsitsiklis, J.N. (1989). Parallel and Distributed Computation: Numerical Methods, Prentice Hall Inc., Englewood Cliffs, NJ. | Zbl 0743.65107

[002] Bianco, F., Cucchietti, G. and Griffa, G. (2007). Energy consumption trends in the next generation access network-a telco perspective, 29th International Telecommunication Energy Conference (INTELEC 2007), Rome, Italy, pp. 737-742.

[003] Bisschop, J. (2007). AIMMS Optimization Modeling, Paragon Decision Technology, Haarlem.

[004] Bolla, R., Bruschi, R., Carrega, A. and Davoli, F. (2010). Theoretical and technological limitations of power scaling in network devices, 2010 Australasian Telecommunication Networks and Applications Conference (ATNAC), Auckland, New Zealand, pp. 37-42.

[005] Bolla, R., Bruschi, R., Carrega, A. and Davoli (2014). Green networking with packet processing engines: Modeling and optimization, IEEE/ACM Transactions on Networking 22(1): 110-123.

[006] Bolla, R., Bruschi, R., Davoli, F. and Cucchietti, F. (2011). Energy efficiency in the future internet: A survey of existing approaches and trends in energy-aware fixed network infrastructures, IEEE Communications Surveys & Tutorials 13(2): 223-244.

[007] Bolla, R., Bruschi, R. and Ranieri, A. (2009). Green support for PC-based software router: Performance evaluation and modeling, IEEE International Conference on Communications (ICC'09), Dresden, Germany, pp. 1-6.

[008] Brownlee, N., Mills, C. and Ruth, G. (1999). Traffic Flow Measurement: Architecture, RFC 2722 (Informational), Internet Engineering Task Force, http://www.ietf.org/rfc/rfc2722.txt

[009] Callaway, R.D., Devetsikiotis, M., Viniotis, Y. and Rodriguez, A. (2010). An autonomic service delivery platform for service-oriented network environments, IEEE Transactions on Services Computing 3(2): 104-115.

[010] Chabarek, J., Sommers, J., Barford, P., Estan, C., Tsiang, D. and Wright, S. (2008). Power awareness in network design and routing, 27th Conference on Computer Communications (INFOCOM 2008), Phoenix, AZ, USA, pp. 457-465.

[011] Chen, L., Low, S.H. and Doyle, J.C. (2011). Cross-layer design in multihop wireless networks, Computer Networks 55(2): 480-496. | Zbl 1218.68037

[012] Chiang, M., Low, S.H., Calderbank, A.R. and Doyle, J.C. (2007). Layering as optimization decomposition: A mathematical theory of network architectures, Proceedings of the IEEE 95(1): 255-312.

[013] Chiaraviglio, L., Mellia, M. and Neri, F. (2009). Energy-aware backbone networks: A case study, 1st International Workshop on Green Communications/IEEE International Conference on Communications (ICC'09), Dresden, Germany, pp. 1-5.

[014] Chiaraviglio, L., Mellia, M. and Neri, F. (2011). Minimizing ISP network energy cost: Formulation and solutions, IEEE/ACM Transactions on Networking 20(2): 463-476.

[015] Fisher, W., Suchara, M. and Rexford, J. (2010). Greening backbone networks: Reducing, energy consumption by shutting off cables in bundled links, 1st ACM SIGCOMM Workshop on Green Networking (Green Networking'10), New Delhi, India, pp. 29-34.

[016] Idzikowski, F., Orlowski, S., Raack, C., Rasner, H. and Wolisz, A. (2010). Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios, 14th Conference on Optical Network Design and Modeling (ONDM'10), Kyoto, Japan, pp. 42-47.

[017] IEEE (2012). IEEE 802.3az Energy Efficient Ethernet Task Force, http://grouper.ieee.org/groups/ 802/3/az/public/index.html.

[018] Jain, R., Chiu, D. and Hawe, W. (1984). A quantitative measure of fairness and discrimination for resource allocation in shared computer systems, DEC Research Report TR-301, Digital Equipment Corporation, Maynard, MA.

[019] Jaskóła, P. and Malinowski, K. (2004). Two methods of optimal bandwidth allocation in TCP/IP networks with QoS differentiation, Summer Simulation Multiconference (SPECTS'04), San Jose, CA, USA, pp. 373-378.

[020] Kelly, F. (1997). Charging and rate control for elastic traffic, European Transactions on Telecommunications 8(1): 33-37.

[021] Li, D. and Sun, X. (2006). Nonlinear Integer Programming, Springer, New York, NY. | Zbl 1140.90042

[022] Mahadevan, P., Sharma, P., Banerjee, S. and Ranganathan, P. (2009). Energy aware network operations, Proceedings of the 28th IEEE International Conference on Computer Communications Workshops, INFOCOM'09, Rio de Janeiro, Brazil, pp. 25-30.

[023] Malinowski, K., Niewiadomska-Szynkiewicz, E. and Jaskóła, P. (2010). Price method and network congestion control, Journal of Telecommunications and Information Technology 2010(2): 73-77.

[024] Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking 8(5): 556-567.

[025] Nedevschi, S., Popa, l., Iannacone, G., Wetherall, D. and Ratnasamy, S. (2008). Reducing network energy consumption via sleeping and rate adaptation, 5th USENIX Symposium on Networked Systems Design and Implementation, San Francisco, CA, USA, pp. 323-336.

[026] Niewiadomska-Szynkiewicz, E., Sikora, A., Arabas, P., Kamola, M., Mincer, M. and Kołodziej, J. (2014). Dynamic power management in energy-aware computer networks and data intensive computing systems, Future Generation Computer Systems 37: 284-296.

[027] Pióro, M., Mysłek, M., Juttner, A., Harmatos, J. and Szentesi, A. (2001). Topological design of MPLS networks, GLOBECOM'2001, San Antonio, CA, USA.

[028] Qureshi, A., Weber, R. and Balakrishnan, H. (2009). Cutting the electric bill for internet-scale systems, SIGCOMM'09, Barcelona, Spain, pp. 123-134.

[029] Rajahalme, J., Conta, A., Carpenter, B. and Deering, S. (2004). IPv6 Flow Label Specification, RFC 3697 (Proposed Standard), Internet Engineering Task Force, http://www.ietf.org/rfc/rfc3697.txt.

[030] Restrepo, J., Gruber, C. and Machuca, C. (2009). Energy profile aware routing, 1st International Workshop on Green Communications/IEEE International Conference on Communications (ICC'09), Dresden, Germany, pp. 1-5.

[031] Roy, S.N. (2008). Energy logic: A road map to reducing energy consumption in telecommunications networks, 30th International Telecommunication Energy Conference (INTELEC 2008), San Diego, CA, USA, pp. 1-9.

[032] Tian, H., Bose, S.K., Law, C.L. and Xiao, W. (2008). Joint routing and flow rate optimization in multi-rate ad hoc networks, Computer Networks 52(3): 739-764. | Zbl 1151.68003

[033] Tsitsiklis, J.N. and Bertsekas, D.P. (1986). Distributed asynchronous optimal routing in data networks, IEEE Transactions on Automatic Control 31(4): 325-332. | Zbl 0587.90093

[034] Vasić, N. and Kostić, D. (2010). Energy-aware traffic engineering, 1st International Conference on EnergyEfficient Computing and Networking (E-ENERGY 2010), Passau, Germany.

[035] Wang, J., Li, L., Low, S.H. and Doyle, J.C. (2005). Cross-layer optimization in TCP/IP networks, IEEE/ACM Transactions on Networking 13(3): 582-595.

[036] Wang, M., Tan, C.W., Xu, W. and Tang, A. (2011). Cost of not splitting in routing: Characterization and estimation, IEEE/ACM Transactions on Networking 19(6): 1849-1859.