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

Jaskóła, P. ; Arabas, P. ; Karbowski, A.

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 1, pp. 231-243.

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

Keywords: MINLP, MIQP, network optimization, green networking, fairness, multicriteria
Mots-clés : MINLP, MIQP, optymalizacja sieci, wielokryterialność

Bibliographie

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

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

[3] 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.

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

[5] 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.

[6] 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.

[7] 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.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

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

[13] 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.

[14] 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.

[15] 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.

[16] 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.

[17] 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.

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

[19] 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.

[20] 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.

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

[22] Li, D. and Sun, X. (2006). Nonlinear Integer Programming, Springer, New York, NY.

[23] 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.

[24] 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.

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

[26] 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.

[27] 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.

[28] 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.

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

[30] 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.

[31] 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.

[32] 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.

[33] 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.

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

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

[36] 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.

[37] 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.