On multi-criteria approaches to bandwidth allocation

• Autorzy: Ogryczak W. , Wierzbicki A.
• Języki publikacji: EN

Abstrakty

EN

Modern telecommunication networks face an increasing demand for services. Among these, an increasing number are services that can adapt to available bandwidth, and are therefore referred to as elastic traffic. Nominal network design for elastic traffic becomes increasingly significant. Typical resource allocation methods are concerned with the allocation of limited resources among competing activities so as to achieve the best overall performance of the system. In the network dimensioning problem for elastic traffic, one needs to allocate bandwidth to maximize service flows and simultaneously to reach a fair treatment of all the elastic services. Thus, both the overall efficiency (throughput) and the fairness (equity) among various services are important. In such applications, the so-called Max-Min Fairness (MMF) solution concept is widely used to formulate the resource allocation scheme. This approach guarantees fairness but may lead to significant losses in the overall throughput of the network. In this paper we show how the concepts of multiple criteria equitable optimization can be effectively used to generate various fair resource allocation schemes. We introduce a multiple criteria model ecluivalent to equitable optimization and we develop a corresponding reference point procedure to generate fair efficient bandwidth allocations. The procedure is tested on a sample network dimensioning problem and its abilities to model various preferences are demonstrated.

Słowa kluczowe

EN

multiple criteria optimization; efficiency; fairness; equity; reference point method; resource allocation; network design; elastic traffic

PL

optymalizacja wielokryterialna; efektywność; alokacja zasobów

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2004
• Tom: Vol. 33, no 3
• Strony: 427--448
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Ogryczak W.

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

autor

Wierzbicki A.

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

Bibliografia

• Bertsekas, D. and Gallager, R. (1987) Data Networks. Prentice-Hall, Englewood Cliffs.
• Denda, R., Banchs, A. and Effelsberg, W. (2000) The Fairness Challenge in Computer Networks. Lecture Notes in Computer Sci.1922,208–220.
• Jaffe, J. (1980) Bottleneck Flow Control. IEEE Trans. on Communications 7, 207–237.
• Kaliszewski, I. (1994) Quantitative Pareto Analysis by Cone SeparationTechnique. Kluwer, Dordrecht.
• Kelly, F., Mauloo, A. and Tan, D. (1997) Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability. J. Oper. Res. Soc. 49, 206–217.
• Kostreva, M.M. and Ogryczak, W. (1999) Linear Optimization with Multiple Equitable Criteria. RAIRO Rech. Oper. 33, 275–297.
• Kostreva, M.M., Ogryczak, W. and Wierzbicki, A. (2004) Equitable Aggregations and Multiple Criteria Analysis. European Journal of Operational Research 158, 362–367.
• Lewandowski, A. and Wierzbicki, A.P. (1989) Aspiration Based Decision Support Systems — Theory, Software and Applications. Springer, Berlin.
• Luss, H. (1999) On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach. Operations Research 47, 361–378.
• Marchi, E. and Oviedo, J.A. (1992) Lexicographic Optimality in the Multiple Objective Linear Programming: The Nucleolar Solution. European Journal of Operational Research 57, 355–359.
• Marshall, A.W. and Olkin, I. (1979) Inequalities: Theory of Majorization and Its Applications. Academic Press, New York.
• Nash, J.F. (1950) The Bargaining Problem. Econometrica 18, 155–162.
• Ogryczak, W. (1997) Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support (in Polish). Warsaw University Press, Warsaw.
• Ogryczak, W. (2001) Comments on Properties of the Minimax Solutionsin Goal Programming. European Journal of Operational Research 132, 17–21.
• Ogryczak, W. (2002) Multiple Criteria Optimization and Decisions under Risk. Control and Cybernetics 31, 975–1003.
• Ogryczak, W. and Śliwiński, T. (2002) On Equitable Approaches to Resource Allocation Problems: the Conditional Minimax Solution. Journalof Telecommunications and Information Technology 3, 40–48.
• Ogryczak, W. and Śliwiński, T. (2003) On Solving Linear Programs with the Ordered Weighted Averaging Objective. European Journal of Operational Research 148, 80–91.
• Ogryczak, W., Śliwiński, T. and Wierzbicki, A. (2003) Fair Resource Allocation Schemes and Network Dimensioning Problems, Journal of Telecommunications and Information Technology 3, 34–42.
• Ogryczak, W. and Tamir, A. (2003) Minimizing the Sum of the k Largest Functions in Linear Time. Information Processing Letters 85, 117–122.
• Pióro, M., Malicsḱo, G. and Fodor, G. (2002) Optimal Link Capacity Dimensioning in Proportionally Fair Networks. Lecture Notes in Computer Sci. 2345, 277–288.
• Pióro, M. and Medhi, D. (2004) Routing, Flow and Capacity Design in Communication and Computer Networks. Morgan Kaufmann Publ., San Francisco.
• Rawls, J. (1971) The Theory of Justice. Harvard Univ. Press, Cambridge.
• Rawls, J. and Kelly, E. (2001) Justice as Fairness: A Restatement. Harvard Univ. Press, Cambridge.
• Steinhaus, H. (1949) Sur la division pragmatique. Econometrica 17, 315–319.
• Steuer, R.E. (1986) Multiple Criteria Optimization: Theory, Computation & Applications. Wiley, New York.
• Vincke, Ph. (1992) Multicriteria Decision–Aid. Wiley, New York.
• Wierzbicki, A.P. (1982) A Mathematical Basis for Satisficing Decision Making. Mathematical Modelling 3, 391–405.
• Wierzbicki, A.P., Makowski, M. and Wessels, J. (2000) Model Based Decision Support Methodology with Environmental Applications. Kluwer, Dodrecht.
• Yager, R.R. (1988) On ordered weighted averaging aggregation operators inmulticriteria decision making. IEEE Trans. Syst. Man Cybern.18, 183–190.