The Library
Multipath selection for resilient network routing
Tools
Kazmi, Nayyar A. (2013) Multipath selection for resilient network routing. PhD thesis, University of Warwick.
|
Text
WRAP_THESIS_Kazmi_2013.pdf - Submitted Version Download (2290Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2691892~S1
Abstract
In this dissertation we study the routing problem for multi-commodity
survivable network
ows, with splittable demands, and propose end-to-end
path-based solutions where maximum link utilization is minimized, in order
to improve resilience in existing telecommunication networks.
We develop mixed integer programming models, and demonstrate that,
when the selection of disjoint paths is part of the optimization problem (rather
than when k-shortest paths are pre-selected, as in earlier works), maximum
link utilization is reduced and the overall network also balances out. We
find that three paths are usually enough to reap the benefits of a multipath
approach. A reduction in maximum link utilization also provides a margin by
which demand values can grow without causing congestion.
We also prove that the disjoint multipath selection problem is NPcomplete,
even for the case of one node-pair. This warrants a recourse to effi-
cient solution methods within ILP (such as decomposition), and to matheuristics.
Our literature survey of applications of heuristic techniques, and those
combining heuristics with exact methods, shows a research gap, which we attempt
to bridge through a novel heuristic algorithm. The heuristic works well
and, in several cases, yields better solutions than ILP (in a given time limit),
or provides solutions for problems where ILP could not even find one valid
solution in the given time limit.
We also study this problem within a decomposition methods framework:
i.e., column generation. The pricing sub-problem is a mixed non-linear
programme, for which we propose an ILP formulation. We find some lower
bounds for missing dual values and use them as surrogates. We then show that
the lower bounds are valid and present examples where the proposed pricing
is applied to path generation for self-protecting multipath routing.
Item Type: | Thesis (PhD) |
---|---|
Subjects: | Q Science > QA Mathematics T Technology > T Technology (General) |
Library of Congress Subject Headings (LCSH): | Network analysis (Planning), Integer programming, Linear programming |
Official Date: | May 2013 |
Institution: | University of Warwick |
Theses Department: | Warwick Business School |
Thesis Type: | PhD |
Publication Status: | Unpublished |
Supervisor(s)/Advisor: | Branke, Jürgen, 1969-; Koster, Arie M. C. A. |
Extent: | xii, [4], 197 leaves. |
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year