Comparison of Selected Fair-optimization Methods for Flow Maximization between Given Pairs of Nodes in Telecommunications Network

• Autorzy: Zalewski G. , Ogryczak W.
• Języki publikacji: EN

Abstrakty

EN

Dimensioning of telecommunications networks requires the allocation of the ows (bandwidth) to given trac demands for the source-destination pairs of nodes. Unit ow allocated to the given demand is associated with revenue that may vary for dierent demands. Problem the decision-making basic algorithms to maximize the total revenue may lead to the solutions that are unacceptable, due to "starvation" or "locking" of some demand paths less attractive with respect to the total revenue. Therefore, the fair optimization approaches must be applied. In this paper, two fair optimization methods are analyzed: the method of ordered weighted average (OWA) and the reference point method (RPM). The study assumes that ows can be bifurcated thus realized in multiple path schemes. To implement optimization model the AMPL was used with general-purpose linear programming solvers. As an example of the data, the Polish backbone network was used.

Słowa kluczowe

EN

allocation problem; decision problems; fair-optimization; linear programming; multi-criteria; networks; ordered weighted averaging; OWA; reference point method; RPM

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2016
• Tom: nr 3
• Strony: 18--24
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Zalewski G.

• National Institute of Telecommunications, Szachowa st 1 04-894, Warsaw, Poland

autor

Ogryczak W.

• Institute of Control and Computation Engineering, Warsaw University of Technology, Nowowiejska st 15/19, 00-665 Warsaw, Poland

Bibliografia

• [1] W. Ogryczak and A. Wierzbicki, “On multi-criteria approaches to bandwidth allocation”, Control and Cybernet., vol. 33, pp. 427–448, 2004.
• [2] W. Ogryczak, M. Pióro, and A. Tomaszewski, “Telecommunications network design and max-min optimization problem”, J. Telecommun. and Inform. Technol., no. 3, pp. 43–56, 2005.
• [3] T. Ibarakiand and N. Katoh, Resource Allocation Problems, Algorithmic Approaches. Cambridge: MIT Press, 1988.
• [4] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
• [5] R. Denda, A. Banchs, and W. Effelsberg, “The fairness challenge in computer networks”, in QofIS 2000, J. Crowcroft, J. Roberts, and M. Smirnov, Eds. LNCS, vol. 1922, pp. 208–220. Springer, 2000.
• [6] J. Rawls and E. Kelly, Justice as Fairness: A Restatement. Cambridge: Harvard Univ. Press, 2001.
• [7] W. Ogryczak, H. Luss, M. Pióro, D. Nace, and A. Tomaszewski, “Fair optimization and networks: A survey”, J. Appl. Mathem., vol. 2014, pp. 1–25, 2014 (doi: 10.1155/2014/612018).
• [8] W. Ogryczak, “Fair optimization – methodological foundations of fairness in network resource allocation”, in Proc. IEEE 38th Ann. Int. Comp. Softw. & Appl. Conf. COMPSAC 2014, Västerås, Sweden, 2014, pp. 43–48.
• [9] H. Luss, “On equitable resource allocation problems: A lexicographic minimax approach”, Operation Research, vol. 47, no. 3, pp. 361–378, 1999.
• [10] J. Kleinberg, Y. Rabani, and E. Tardos, “Fairness in routing and load balancing”, J. Comput. Syst. Sci., vol. 63, no. 1, pp. 2–21, 2001.
• [11] F. Kelly, A. Maulloo, and D. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, J. Oper. Res. Soc., vol. 49, no. 3, pp. 206–217, 1997.
• [12] R. R. Yager, “On ordered weighted averaging aggregation operators in multicriteria decision making”, IEEE Trans. Sys., Man and Cyber., vol. 18, no. 1, pp. 183–190, 1988.
• [13] R. R. Yager, J. Kacprzyk, and G. Beliakov, Recent Developments in the Ordered Weighted Averaging Operators: Theory and Practice. Springer, 2011.
• [14] W. Ogryczak and B. Kozłowski, “Reference point method with importance weighted ordered partial achievements”, TOP, vol. 19, no. 2, pp. 380–401, 2011.
• [15] W. Ogryczak and A. Tamir, “Minimizing the sum of the k-largest functions in linear time”, Inform. Process. Lett., vol. 85, no. 3, pp. 117–122, 2003.
• [16] M. Rothschild and J. E. Stiglitz, “Some further results in the measurement of inequality”, J. Economic Theory, vol. 6, no. 2, pp. 188–204, 1973.
• [17] D. Bertsimas, V. F. Farias, and N. Trichakis, “The price of fairness”, Operations Research, vol. 59, pp. 17–31, 2011.
• [18] S. Orłowski, R. Wessaly, M. Pióro, and A. Tomaszewski, “SNDlib 1.0 – survivable network design library”, Networks, vol. 55, no. 3, pp. 276–286, 2009.