Fairness in Communication and Computer Network Design Nilsson, Pål 2006 Link to publication Citation for published version (APA): Nilsson, P. (2006). Fairness in Communication and Computer Network Design. [Doctoral Thesis (monograph), Department of Electrical and Information Technology]. Department of Communication Systems, Lund University. Total number of authors: 1 General rights Unless other specific re-use rights are stated the following general rights apply: Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. • Users may download and print one copy of any publication from the public portal for the purpose of private study or research. • You may not further distribute the material or use it for any profit-making activity or commercial gain • You may freely distribute the URL identifying the publication in the public portal Read more about Creative commons licenses: https://creativecommons.org/licenses/ Take down policy If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately and investigate your claim. LUND UNIVERSITY PO Box 117 221 00 Lund +46 46-222 00 00 Fairness in communication and computer network design P˚al Nilsson Department of Communication Systems Lund Institute of Technology ii ISSN 1101-3931 ISRN LUTEDX/TETS–1080–SE+138P (cid:13)c P˚al Nilsson Printed in Sweden Tryckeriet i E-huset Lund 2006 iii To my family iv This thesis is submitted to Research Board FIME - Physics, Informatics, Mathematics and Electrical Engineering - at Lund Institute of Technology, Lund University in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Engineering. Contact information: P˚al Nilsson Department of Communication Systems Lund University Box 118 SE-221 00 LUND Sweden Phone: +46 46 222 03 68 Fax: +46 46 14 58 23 e-mail: [email protected] v Abstract In communication networks, fair sharing of resources is an important issue for one main reason. The growth of network capacity is in general not matching the rapid growth of traffic. Consequently, the resources consumed by each user have to be limited. This implies that users cannot always be assigned the end-to-end bandwidth they ask for. Instead, the limited network resources should be distributed to users in a way that assures fair end-to-end bandwidth assignment among them. Obtaining fairness between network users and at the same time assuring efficient network utilization, is a source of non-trivial network optimization problems. Complicating factors are that each user has limited access to the (limited) network resources and that different users require and consume different amounts and types of resources. In this thesis different types of optimization problems associated with fair resource sharing in communication networks are studied. Initially, the notions of max-min fairness, proportional fairness, α-fairness etc., are put in a formal framework of fair rational preference relations. A clear, unified definition of fairness is presented. The theory is first applied to different types of allocation problems. Fo- cus is put on convex and non-convex max-min fair traffic allocation prob- lems, and a difference in difficulty between the two groups of problems is demonstrated. The studies are continued by an investigation of proportionally fair di- mensioning. Two different cases are studied – a simpler, when no resilience to failures is required, and a more complicated, assuming the possibility of link failures. In the context of fair sharing of the resources of a communication net- work, this thesis presents several original theoretical findings as well as so- lution algorithms for the studied problems. The results are accompanied by numerical results, illustrating algorithm efficiency for virtually all of the studied problems. vi Acknowledgements My gratitude goes out to all the people who did, in any sense, contribute to the creation of this thesis. Thanks to my precious family – Rebecka, Alfred andLovisa, andtoMumandDadwhodidalways supportme. Manythanks to my supervisor Michal Pioro and to my colleague Eligijus Kubilinskas. I am also grateful to Ulf Ahlfors, Jens K Andersson, Mikael Andersson, Jian- huaCao, MateuszDzida, ZbigniewDziong, GaborFodor,TorgnyHolmberg, Johan M Karlsson, Ulf K¨orner, Christian Nyberg, Wlodzimierz Ogryczak, Henrik Persson, Lars Reneby and Michal Zagozdzon, who did all help me in different aspects during my Ph.D. studies. Long live Contents 1 Introduction 5 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Backbone networks . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Backbone network traffic . . . . . . . . . . . . . . . . . . . . . 9 1.4 The multicommodity flow model . . . . . . . . . . . . . . . . 9 1.5 Subject of the thesis . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Introductory examples . . . . . . . . . . . . . . . . . . . . . . 10 1.6.1 Fairness vs throughput . . . . . . . . . . . . . . . . . . 10 1.6.2 The fairest solution. . . . . . . . . . . . . . . . . . . . 11 1.7 The framework . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.7.1 Mathematical programming . . . . . . . . . . . . . . . 12 1.7.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.8 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.9 List of publications . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Optimization models for fairness 19 2.1 The notion of fairness . . . . . . . . . . . . . . . . . . . . . . 20 2.1.1 Fair rational preference relations . . . . . . . . . . . . 20 2.1.2 Fairly nondominated vectors . . . . . . . . . . . . . . 22 2.1.3 Fairness and Pareto-efficiency . . . . . . . . . . . . . 22 2.2 General ways of defining fairness . . . . . . . . . . . . . . . . 24 2.2.1 p-norm fairness . . . . . . . . . . . . . . . . . . . . . . 24 2.2.2 Ordered weighted averaging . . . . . . . . . . . . . . . 25 2.2.3 α-fairness . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3 Max-min fairness . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Weak and strong max-min fairness . . . . . . . . . . . 29 2.3.2 Max-min fairness in the solution space . . . . . . . . . 31 2.4 Algorithms that achieve max-min fairness . . . . . . . . . . . 32 2.4.1 The convex case . . . . . . . . . . . . . . . . . . . . . 33 2.4.2 Non-convex cases . . . . . . . . . . . . . . . . . . . . 36 2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1 2 CONTENTS 3 Convex allocation problems 41 3.1 Max-min fair allocation problems . . . . . . . . . . . . . . . . 42 3.1.1 Max-min fair flows on fixed paths. . . . . . . . . . . . 42 3.1.2 Max-min fair flows on optimized paths . . . . . . . . 45 3.2 Max-min fair reallocation . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Problem description . . . . . . . . . . . . . . . . . . . 55 3.2.2 Notation and definitions . . . . . . . . . . . . . . . . . 55 3.2.3 A lower bound . . . . . . . . . . . . . . . . . . . . . . 56 3.2.4 Optimal solutions . . . . . . . . . . . . . . . . . . . . 58 3.2.5 Numerical examples . . . . . . . . . . . . . . . . . . . 60 3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 Non-convex allocation problems 65 4.1 Max-min fairness of modular flows . . . . . . . . . . . . . . . 66 4.1.1 Problem description . . . . . . . . . . . . . . . . . . . 67 4.1.2 The assumption of modular flows . . . . . . . . . . . . 68 4.1.3 Properties of the optimal integral solution . . . . . . . 68 4.1.4 Computational complexity . . . . . . . . . . . . . . . . 70 4.1.5 An algorithm . . . . . . . . . . . . . . . . . . . . . . . 74 4.1.6 A numerical experiment . . . . . . . . . . . . . . . . . 76 4.2 Max-min fairness of unsplittable flows . . . . . . . . . . . . . 76 4.2.1 Problem description . . . . . . . . . . . . . . . . . . . 78 4.2.2 Computational complexity . . . . . . . . . . . . . . . . 78 4.2.3 Resolution algorithms . . . . . . . . . . . . . . . . . . 86 4.2.4 Numerical experiments . . . . . . . . . . . . . . . . . 94 4.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5 Dimensioning problems 101 5.1 Proportionally fair dimensioning . . . . . . . . . . . . . . . . 102 5.1.1 Bounded flows . . . . . . . . . . . . . . . . . . . . . . 105 5.1.2 An objective function extension . . . . . . . . . . . . . 109 5.1.3 Numerical examples . . . . . . . . . . . . . . . . . . . 110 5.2 Resilient PF dimensioning . . . . . . . . . . . . . . . . . . . . 113 5.2.1 Problem formulation . . . . . . . . . . . . . . . . . . . 114 5.2.2 Resolution methods . . . . . . . . . . . . . . . . . . . 116 5.2.3 Linear approximation . . . . . . . . . . . . . . . . . . 119 5.2.4 Extensions of the basic problem. . . . . . . . . . . . . 120 5.2.5 Numerical results . . . . . . . . . . . . . . . . . . . . 121 5.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6 Summary and contribution 127 6.1 Optimization models for fairness (Chapter 2) . . . . . . . . . 128 6.2 Convex allocation problems (Chapter 3) . . . . . . . . . . . . 129 6.3 Non-convex allocation problems (Chapter 4) . . . . . . . . . . 130 CONTENTS 3 6.4 Dimensioning problems (Chapter 5) . . . . . . . . . . . . . . 132