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

• Autorzy: Jaskóła P. , Arabas P. , Karbowski A.

Identyfikatory

DOI

10.1515/amcs-2016-0016

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

MINLP; MIQP; network optimization; green networking; fairness; multicriteria

PL

MINLP; MIQP; optymalizacja sieci; wielokryterialność

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 1
• Strony: 231--243
• Opis fizyczny: Bibliogr. 37 poz., rys., tab., wykr.

Twórcy

autor

Jaskóła P.

• Research Division, NASK Research and Academic Computer Network, ul. Wąwozowa 18, 02-796 Warsaw, Poland

autor

Arabas P.

• Research Division, NASK Research and Academic Computer Network, ul. Wąwozowa 18, 02-796 Warsaw, Poland; Institute of Control and Computation Engineering, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland

autor

Karbowski A.

• Research Division, NASK Research and Academic Computer Network, ul. Wąwozowa 18, 02-796 Warsaw, Poland; Institute of Control and Computation Engineering, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland

Bibliografia

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

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.