Network Dimensioning with Maximum Revenue Efficiency for the Fairness Index
DOI:
https://doi.org/10.26636/jtit.2016.4.758Keywords:
allocation problem, decision problems, dimensioning networks, fair optimization, linear programming, maximization, multi-criteriaAbstract
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.
Downloads
References
[1] J. Rawls, Theory of Justice. Cambridge: Harvard Univ. Press, 1971.
View in Google Scholar
[2] H. P. Young, Equity in Theory and Practice. Princeton: Princeton Univ. Press, 1994.
View in Google Scholar
[3] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
View in Google Scholar
[4] W. Ogryczak and A. Wierzbicki, “On multi-criteria approaches to bandwidth allocation”, Control and Cybernet., vol. 33, no. 3, pp. 427–448, 2004.
View in Google Scholar
[5] J. Kleinberg, Y. Rabani, and É. Tardos, “Fairness in routing and load balancing”, J. Comput. Syst. Sci., vol. 63, no. 1, pp. 2–21, 2001.
View in Google Scholar
[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.
View in Google Scholar
[7] H. Luss, “On equitable resource allocation problems: A lexicographic minimax approach”, Operation Res., vol. 47, no. 3, pp. 361–378, 1999.
View in Google Scholar
[8] F. Kelly, A. Maulloo, and D. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability”, J. Oper. Res. Soc., vol. 49, pp. 206–217, 1997.
View in Google Scholar
[9] R. Denda, A. Banchs, and W. Effelsberg, “The fairness challenge in computer networks”, Lect. Notes Comp. Sci., vol. 1922, pp. 208–220, 2000.
View in Google Scholar
[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.
View in Google Scholar
[11] R. R. Yager, J. Kacprzyk, and G. Beliakov, Recent Developments in the Ordered Weighted Averaging Operators: Theory and Practice. Springer, 2011.
View in Google Scholar
[12] M. M. Kostreva and W. Ogryczak, “Linear optimization with multiple equitable criteria”, RAIRO Oper. Res., vol. 33, no. 3, pp. 275–297, 1999.
View in Google Scholar
[13] W. Ogryczak, “Bicriteria models for fair and efficient resource allocation”, in Social Informatics, L. Bolc, M. Makowski, and A. Wierzbicki, Eds. LNCS, vol. 6430, pp. 140–159. Springer, 2010.
View in Google Scholar
[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.
View in Google Scholar
[15] W. Ogryczak, “Inequality measures and equitable approaches to location problems”, Eur. J. Oper. Res., vol. 122, no. 2, pp. 374–391, 2000.
View in Google Scholar
[16] M. Dianati, X. Shen, and S. Naik, “A new fairness index for radio resource allocation in wireless networks”, in Proc. IEEE Wirel. Commun. & Networking Conf. WCNC 2005, New Orleans, LA, USA, 2005, vol. 2, pp. 712–717.
View in Google Scholar
[17] W. Ogryczak, “Inequality measures and equitable locations”, Annals of Oper. Res., vol. 167, no. 1, pp. 61–86, 2009.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[20] A. B. Atkinson, “On the measurement of inequality”, J. Econom. Theory, vol. 2, pp. 244–263, 1970.
View in Google Scholar
[21] R. Jain, D. Chiu, and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer system”, Eastern Res. Lab., Digital Equipment Corp., 1984.
View in Google Scholar
[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.
View in Google Scholar
[23] S. Orłowski, R. Wessäly, M. Pióro, and A. Tomaszewski, “SNDlib 1.0 – survivable network design library”, Networks, vol. 55, no. 3, pp. 276–286, 2009.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2016 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
