The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Unsplittable max-min demand allocation - a routing problem

Author

  • Pål Nilsson
  • Michal Pioro

Summary, in English

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.

Publishing year

2005

Language

English

Document type

Conference paper

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering
  • Communication Systems

Conference name

HET-NETs '05 Third International working conference

Conference date

2005-07-18 - 2005-07-20

Conference place

ILkley, United Kingdom

Status

Published