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

Authors

DOI:

https://doi.org/10.26636/jtit.2016.3.732

Keywords:

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

Abstract

Dimensioning of telecommunications networks requires the allocation of the flows (bandwidth) to given trac demands for the source-destination pairs of nodes. Unit flow allocated to the given demand is associated with revenue that may vary for different 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 flows 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.

Downloads

Download data is not yet available.

References

[1] W. Ogryczak and A. Wierzbicki, “On multi-criteria approaches to bandwidth allocation”, Control and Cybernet., vol. 33, pp. 427–448, 2004.
View in Google Scholar

[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.
View in Google Scholar

[3] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches. Cambridge: MIT Press, 1988.
View in Google Scholar

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

[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.
View in Google Scholar

[6] J. Rawls and E. Kelly, Justice as Fairness: A Restatement. Cambridge: Harvard Univ. Press, 2001.
View in Google Scholar

[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).
View in Google Scholar

[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.
View in Google Scholar

[9] H. Luss, “On equitable resource allocation problems: A lexicographic minimax approach”, Operation Research, vol. 47, no. 3, pp. 361–378, 1999.
View in Google Scholar

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

[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.
View in Google Scholar

[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.
View in Google Scholar

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

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[17] D. Bertsimas, V. F. Farias, and N. Trichakis, “The price of fairness”, Operations Research, vol. 59, pp. 17–31, 2011.
View in Google Scholar

[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.
View in Google Scholar

Downloads

Published

2016-09-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
G. Zalewski and W. Ogryczak, “Comparison of Selected Fair-optimization Methods for Flow Maximization between Given Pairs of Nodes in Telecommunications Network”, JTIT, vol. 65, no. 3, pp. 18–24, Sep. 2016, doi: 10.26636/jtit.2016.3.732.

Most read articles by the same author(s)

1 2 > >>