Fair resource allocation schemes and network dimensioning problems

• Autorzy: Ogryczak W. , Śliwiński T. , Wierzbicki A.
• Języki publikacji: EN

Abstrakty

EN

Resource allocation problems are concerned with the allocation of limited resources among competing activities so as to achieve the best overall performances of the system but providing fair treatment of all the competitors. Telecommunication networks are facing the increasing demand for Internet services. Therefore, a problem of network dimensioning with elastic traffic arises which requires to allocate bandwidth to maximize service flows with fair treatment of all the services. In such applications, the so-called max-min fairness (MMF) solution concept is widely used to formulate the resource allocation scheme. This guarantees the fairness but may lead to significant losses in the overall throughput of the network. In this paper we show how multiple criteria optimization concepts can be used to generate various fair resource allocation schemes. The solution concepts are tested on the network dimensioning problem and their abilities to model various preferences are demonstrated.

Słowa kluczowe

EN

telecommunication networks; network dimensioning; resource allocation; fairness

PL

sieci telekomunikacyjne

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

Twórcy

autor

Ogryczak W.

• Institute of Control and Computation Engineering, Warsaw University of Technology

autor

Śliwiński T.

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

autor

Wierzbicki A.

• Polish-Japanese Institute of Information Technology Koszykowa st 86 02-008 Warsaw, Poland

Bibliografia

• [1] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs: Prentice-Hall, 1987.
• [2] J. F. Campbell, “Hub location and the p-hub median problem”, Oper. Res., vol. 44, pp. 923–935, 1996.
• [3] E. Gourdin, “Optimizing Internet networks”, OR/MS Today, vol. 28, pp. 46–49, 2001.
• [4] ILOG Inc., Using the CPLEX Callable Library. Incline Village: ILOG Inc., CPLEX Division, 1997.
• [5] 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.
• [6] J. G. Klincewicz, “Hub location in backbone/tributary network design: a review”, Loc. Sci., vol. 6, pp. 307–335, 1998.
• [7] M. M. Kostreva and W. Ogryczak, “Linear optimization with multiple equitable criteria”, RAIRO Oper. Res., vol. 33, pp. 275–297, 1999.
• [8] H. Luss, “On equitable resource allocation problems: a lexicographic minimax approach”, Oper. Res., vol. 47, pp. 361–378, 1999.
• [9] E. Marchi and J. A. Oviedo, “Lexicographic optimality in the multiple objective linear programming: the nucleolar solution”, Eur. J. Oper. Res., vol. 57, pp. 355–359, 1992.
• [10] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and its Applications. New York: Academic Press, 1979.
• [11] P. Nilsson and M. Pióro, “Solving dimensioning problems for proportionally fair networks carrying elastic traffic”, Lund Institute of Technology at Lund University, 2002.
• [12] W. Ogryczak, “Comments on properties of the minimax solutions In goal programming”, Eur. J. Oper. Res., vol. 132, pp. 17–21, 2001.
• [13] W. Ogryczak and T. Śliwiński, “On equitable approaches to resource allocation problems: the conditional minimax solution”, J. Telecommun. Inform. Technol., no. 3, pp. 40–48, 2002.
• [14] W. Ogryczak and A. Tamir, “Minimizing the sum of the k lar gest functions in linear time”, Inform. Proc. Lett., vol. 85, pp. 117–122, 2003.
• [15] J. Rawls, The Theory of Justice. Cambridge: Harvard University Press, 1971.
• [16] A. Tomaszewski, “A polynomial algorithm for solving a general max-min fairness problem” in Proc. 2nd Pol.-Germ. Teletraff. Symp. PGTS, 2002, pp. 253-258.
• [17] A. P. Wierzbicki, “A mathematical basis for satisficing decision making”, Math. Modell., vol. 3, pp. 391–405, 1982.
• [18] A. P. Wierzbicki, M. Makowski, and J. Wessels, Eds., Model Based Decision Support Methodology with Environmental Applications.Dordrecht: Kluwer, 2000.
• [19] R. R. Yager, “On ordered weighted averaging aggregation operators in multicriteria decision making”, IEEE Trans. Syst., Man Cybern., vol. 18, pp. 183–190, 1988.
• [20] R. R. Yager, “On the analytic representation of the Leximin ordering and its application to flexible constraint propagation”, Eur. J. Oper. Res., vol. 102, pp. 176–192, 1997.