Abstract
The end-to-end assignment of bandwidth to node-pairs (demands) in a communication network can be considered fair if it is distributed according to the max-min fair (MMF) principle. This paper investigates the problem of
obtaining an MMF allocation if each demand is required to use exactly one path (i.e., to use unsplittable flows). First it is shown that the problem is NP-hard, both if each demand may use an arbitrary path and also if each demand is restricted to use a path from a small, predefined (demand-specific) path-list. Then, a number of mixed integer programmingmodels
are presented for the problem. These models constitute a basis for resolution techniques and are therefore examined in terms of computation times on a set of randomly generated problem instances.
obtaining an MMF allocation if each demand is required to use exactly one path (i.e., to use unsplittable flows). First it is shown that the problem is NP-hard, both if each demand may use an arbitrary path and also if each demand is restricted to use a path from a small, predefined (demand-specific) path-list. Then, a number of mixed integer programmingmodels
are presented for the problem. These models constitute a basis for resolution techniques and are therefore examined in terms of computation times on a set of randomly generated problem instances.
| Original language | English |
|---|---|
| Publication status | Published - 2005 |
| Event | HET-NETs '05 Third International working conference - ILkley, United Kingdom Duration: 2005 Jul 18 → 2005 Jul 20 |
Conference
| Conference | HET-NETs '05 Third International working conference |
|---|---|
| Country/Territory | United Kingdom |
| City | ILkley |
| Period | 2005/07/18 → 2005/07/20 |
Subject classification (UKÄ)
- Electrical Engineering, Electronic Engineering, Information Engineering
- Communication Systems