Advanced

Unsplittable max-min demand allocation - a routing problem

Nilsson, Pål LU and Pioro, Michal LU (2005) HET-NETs '05 Third International working conference
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to conference
publication status
published
subject
conference name
HET-NETs '05 Third International working conference
language
English
LU publication?
yes
id
ccf0c66c-bde1-4d8f-aa62-8e574017a756 (old id 1583120)
date added to LUP
2010-04-06 15:24:00
date last changed
2016-04-16 12:11:52
@misc{ccf0c66c-bde1-4d8f-aa62-8e574017a756,
  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<br/><br>
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<br/><br>
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.},
  author       = {Nilsson, Pål and Pioro, Michal},
  language     = {eng},
  title        = {Unsplittable max-min demand allocation - a routing problem},
  year         = {2005},
}