Network Dimensioning with Maximum Revenue Efficiency for the Fairness Index

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

Abstrakty

EN

Network dimensioning is a specific kind of the resource allocation problem. One of the tasks in the network optimization is to maximize the total flow on given pairs of nodes (so-called demands or paths between source and target). The task can be more complicated when different revenue/profit gained from each unit of traffic stream allocated on each demand is taken into account. When the total revenue is maximized the problem of starvation of less attractive paths can appear. Therefore, it is important to include some fairness criteria to preserve connections between all the demands on a given degree of quality, also for the least attractive paths. In this paper, a new bicriteria ratio optimization method which takes into account both, the revenue and the fairness is proposed. Mathematical model is built in a form of linear programming. The solutions are analyzed with some statistical measures to evaluate their quality, with respect to fairness and efficiency. In particular, the Gini’s coefficient is used for this purpose.

Słowa kluczowe

EN

allocation problem; decision problems; dimensioning networks; fair-optimization; linear programming; maximization; multi-criteria

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2016
• Tom: nr 4
• Strony: 15--21
• Opis fizyczny: Bibliogr. 23 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] J. Rawls, Theory of Justice. Cambridge: Harvard Univ. Press, 1971.
• [2] H. P. Young, Equity in Theory and Practice. Princeton: Princeton Univ. Press, 1994.
• [3] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
• [4] W. Ogryczak and A. Wierzbicki, “On multi-criteria approaches to bandwidth allocation", Control and Cybernet., vol. 33, no. 3, pp. 427-448, 2004.
• [5] 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.
• [6] W. Ogryczak, M. Pióro, and A. Tomaszewski, “Telecommunications network design and Max-Min optimization problem", J. of Telecommun. & Inform. Technol., no. 3, pp. 43-56, 2005.
• [7] H. Luss, “On equitable resource allocation problems: A lexicographic minimax approach", Operation Res., vol. 47, no. 3, pp. 361-378, 1999.
• [8] F. Kelly, A. Mauloo, and D. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability", J. Oper. Res. Soc., vol. 49, pp. 206-217, 1997.
• [9] R. Denda, A. Banchs, and W. Effelsberg, “The fairness challenge in computer networks", Lect. Notes Comp. Sci., vol. 1922, pp. 208-220, 2000.
• [10] R. R. Yager, “On ordered weighted averaging aggregation operators in multicriteria decision making", IEEE Trans. on Systems, Man, and Cybernet., vol. 18, no. 1, pp. 183-190, 1988.
• [11] R. R. Yager, J. Kacprzyk, and G. Beliakov, Recent Developments in the Ordered Weighted Averaging Operators: Theory and Practice. Springer, 2011.
• [12] M. M. Kostreva and W. Ogryczak, “Linear optimization with multiple equitable criteria", RAIRO Oper. Res., vol. 33, no. 3, pp. 275-297, 1999.
• [13] W. Ogryczak, “Bicriteria models for fair and efficient resource allocation", in Social Informatics, L. Bolc, M. Makowski, A. Wierzbicki, Eds. LNCS, vol. 6430, pp. 140-159. Springer, 2010.
• [14] T. Lan, D. Kao, M. Chiang, and A. Sabharwal, “An axiomatic theory of fairness in network resource allocation", in Proc. 29th Conf. on Comp. Commun. IEEE INFOCOM 2010, San Diego, CA, USA, 2010, pp. 1-9.
• [15] W. Ogryczak, “Inequality measures and equitable approaches to location problems", Eur. J. Oper. Res., vol. 122, no. 2, pp. 374-391, 2000.
• [16] M. Dianati, X. Shen, and S. Naik, “A new fairness index for radio resource allocation in wireless networks", Proc. IEEE Wirel. Commun. & Networking Conf. WCNC 2005, New Orleans, LA, USA, 2005, vol. 2, pp. 712-717.
• [17] W. Ogryczak, “Inequality measures and equitable locations", Annals of Oper. Res., vol. 167, no. 1, pp. 61-86, 2009.
• [18] W. Ogryczak and M. Zawadzki, “Conditional median: a parametric solution concept for location problems", Annals of Oper. Res., vol. 110, no. 3, pp. 167-181, 2002.
• [19] W. Ogryczak and A. Tamir, “Minimizing the sum of the k largest functions in linear time", Inform. Processing Lett., vol. 85, no. 3, pp. 117-122, 2003.
• [20] A. B. Atkinson, “On the measurement of inequality", J. Econom. Theory, vol. 2, pp. 244-263, 1970.
• [21] R. Jain, D. Chiu, and W. Hawe, “A quantitative measure of fairness and iscrimination for resource allocation in shared computer system", Eastern Res. Lab., Digital Equipment Corp., 1984.
• [22] W. Ogryczak and T. Śliwiński, “On equitable approaches to resource allocation problems: The conditional minimax solutions", J. of Telecommun. & Inform. Technol., no. 3, pp. 40-48, 2002.
• [23] S. Orłowski, R. Wessaly, and M. Pióro, and A. Tomaszewski, “SNDlib 1.0 - survivable network design library", Networks, vol. 55, no. 3, pp. 276-286, 2009.

Uwagi

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