219:
that use these links are not increased any more, and you continue increasing the rates for other sources. All the sources that are stopped have a bottleneck link. This is because they use a saturated link, and all other sources using the saturated link are stopped at the same time, or were stopped before, thus have a smaller or equal rate. The algorithm continues until it is not possible to increase. Lastly, when the algorithm terminates, all sources have been stopped at some time and thus have a bottleneck link. This allocation is max-min fair.
110:, where the resources are divided with the goal to achieve the same cost to each user, or to minimize the maximum cost per unit that a dataflow reaches. Expensive data flows achieve lower service quality than others in proportional fairness, but do not suffer from starvation. Max-min fairness results in more stable service quality, and therefore, perhaps, more "happy customers".
99:, where the least expensive flows are assigned all capacity they can use, and no capacity might remain for the most expensive flows. In a wireless network, an expensive user is typically a mobile station at far distance from the base station, exposed to high signal attenuation. However, a maximum throughput policy would result in
80:) provide high average throughput but low stability in the service quality, meaning that the achieved service quality is varying in time depending on the behavior of other users. If this instability is severe, it may result in unhappy users who will choose another more stable communication service.
178:
The name “max-min” comes from the idea that it is the rate of the smaller (or minimum) flows that is made as large as possible (maximized) by the algorithm. Hence we give higher relative priority to small flows. Only when a flow asks to consume more than C/N (link capacity/number of flows) is it at
218:
If resources are allocated in advance in the network nodes, max-min fairness can be obtained by using an algorithm of progressive filling. You start with all rates equal to 0 and grow all rates together at the same pace, until one or several link capacity limits are hit. The rates for the sources
91:
policy of the resources. In equal sharing, some dataflows may not be able to utilize their "fair share" of the resources. A policy for equal sharing would prevent a dataflow from obtaining more resources than any other flow, and from utilizing free resources in the network.
174:
is “max-min fair” if and only if an increase of any rate within the domain of feasible allocations must be at the cost of a decrease of some already smaller rate. Depending on the problem, a max-min fair allocation may or may not exist. However, if it exists, it is unique.
31:
is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessarily results in the decrease in the allocation of some other participant with an equal or smaller allocation.
144:. Each data flow has a defined initial node, a destination node, and a desired data rate. A flow on its path through the network may be divided between "parallel" links, in a
64:
and best-effort networks, since it gives scheduling priority to users that have achieved lowest data rate since they became active. In case of equally sized data packets,
50:, meaning that an ill-behaved flow, consisting of large data packets or bursts of many packets, will only punish itself and not other flows.
296:
96:
265:
210:
A data rate allocation is max-min fair if and only if a data flow between any two nodes has at least one bottleneck link.
203:
achieves overall maximum data rate. Note that this definition is substantially different from a common meaning of a
207:. Also note, that this definition does not forbid a single bottleneck link to be shared between multiple flows.
239:
46:(FCFS) scheduling policy is often used. The advantage with max-min fairness over FCFS is that it results in
268:
Jean-Yves Le Boudec (EPFL Lausanne) "Rate adaptation, Congestion
Control and Fairness: A Tutorial" Nov 2005
118:
Max-min fairness in communication networks assumes that resources (capacities of communication links) are
301:
306:
245:
145:
84:
281:
61:
39:
43:
233:
76:
Generally, policies for sharing resources that are characterized by low level of fairness (see
65:
20:
188:
8:
107:
100:
266:
https://web.archive.org/web/20230422115954/https://ica1www.epfl.ch/PS_files/LEB3132.pdf
51:
87:
in wireless networks) and better utilization of the resources than a work-conserving
228:
77:
47:
290:
106:
A compromise between max-min fairness and maximum throughput scheduling is
95:
On the other hand, max-min fairness provides lower average throughput than
57:
24:
123:
36:
83:
Max-min fair resource sharing results in higher average throughput (or
71:
133:
60:
is an example of a max-min fair packet scheduling algorithm for
103:
of expensive flows, and may result in fewer "happy customers".
242:- choosing between alternatives based on the max-min principle
179:
any risk of having its bandwidth throttled by the algorithm.
248:- a generalization of max-min fairness to multiple resources
113:
199:) and of all the flows sharing this link, the data flow
72:
Comparison with other policies for resource sharing
288:
213:
159:-th coordinate is the allocation for flow
114:Max-min fair link capacity pre-allocation
54:is consequently to some extent avoided.
289:
97:maximum throughput resource management
27:and the division of scarce resources,
195:is a link that is fully utilized (is
236:in multitasking operational systems
182:
122:to flows in advance, as opposed to
13:
163:, i.e. the rate at which the user
14:
318:
275:
259:
240:Egalitarian social choice rule
1:
297:Network scheduling algorithms
252:
214:Progressive filling algorithm
282:Max-min fair share algorithm
7:
222:
10:
323:
246:Dominant resource fairness
85:system spectral efficiency
167:is allowed to emit data.
62:statistical multiplexing
40:statistical multiplexing
44:first-come first-served
170:An allocation of rate
66:round-robin scheduling
21:communication networks
151:An allocation vector
108:proportional fairness
136:, sometimes called
302:Routing algorithms
52:Network congestion
307:Fairness criteria
78:fairness measures
68:is max-min fair.
16:Scheduling policy
314:
269:
263:
229:Fairness measure
191:for a data flow
183:Bottleneck links
29:max-min fairness
322:
321:
317:
316:
315:
313:
312:
311:
287:
286:
278:
273:
272:
264:
260:
255:
225:
216:
189:bottleneck link
185:
116:
74:
48:traffic shaping
17:
12:
11:
5:
320:
310:
309:
304:
299:
285:
284:
277:
276:External links
274:
271:
270:
257:
256:
254:
251:
250:
249:
243:
237:
231:
224:
221:
215:
212:
184:
181:
146:load balancing
115:
112:
73:
70:
15:
9:
6:
4:
3:
2:
319:
308:
305:
303:
300:
298:
295:
294:
292:
283:
280:
279:
267:
262:
258:
247:
244:
241:
238:
235:
232:
230:
227:
226:
220:
211:
208:
206:
202:
198:
194:
190:
180:
176:
173:
168:
166:
162:
158:
154:
149:
147:
143:
139:
135:
132:
127:
125:
121:
111:
109:
104:
102:
98:
93:
90:
89:equal sharing
86:
81:
79:
69:
67:
63:
59:
55:
53:
49:
45:
41:
38:
33:
30:
26:
22:
261:
217:
209:
204:
200:
196:
192:
186:
177:
171:
169:
164:
160:
156:
152:
150:
141:
137:
130:
128:
119:
117:
105:
94:
88:
82:
75:
58:Fair queuing
56:
34:
28:
25:multiplexing
18:
124:best-effort
37:best-effort
291:Categories
253:References
234:Scheduling
205:bottleneck
134:data flows
126:networks.
101:starvation
197:saturated
129:Consider
120:allocated
223:See also
148:scheme.
142:sources
155:whose
138:users
42:, a
140:or
35:In
19:In
293::
187:A
23:,
201:i
193:i
172:x
165:i
161:i
157:i
153:x
131:i
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.