Doctoral Thesis Defense, Optimization and Systems Theory
Thursday, March 21, 2002, 10.00, Kollegiesalen, Administration building, Valhallavägen 79, KTH


Mikael Prytz

On optimization in design of telecommunications networks with multicast and unicast traffic

Akademisk avhandling som med tillstånd av Kungliga Tekniska Högskolan framlägges till offentlig granskning för avläggande av teknologie doktorsexamen torsdagen den 21 mars 2002 kl 10.00 i Kollegiesalen, Administrationsbyggnaden, Kungliga Tekniska Högskolan, Valhallavägen 79.

This thesis addresses certain optimization problems arising in telecommunications network design, specifically capacity dimensioning of telecommunications networks with multicast and unicast traffic, and a multicast routing location problem. The thesis considers optimization models and methods for these problems. It consists of an introduction and four appended papers.

In paper A, an optimization model for capacity dimensioning of multicast enabled backbone communications networks is given. A Lagrangian decomposition branch-and-bound scheme is proposed, where individual Steiner tree and 0-1 knapsack subproblems are solved. Computational results are reported for two sets of test problems with non-uniform and uniform step cost functions. The proposed scheme yields lower bounds superior to a straightforward Lagrangian relaxation on the non-uniform test problems.

In paper B, an optimization model for a capacity dimensioning problem of a backbone network with restrictions on the achievable multicast routing distribution tree topologies is developed. Specifically, distribution trees are found as shortest path trees with respect to a single, strictly positive link routing metric set. The free routing metric and the capacity-induced routing metric cases are investigated. A branch-and-cut scheme, including some valid inequalities, is proposed. Computational results are reported for the two cases on several test problems.

In paper C, the Rendezvous Point (RP) placement problem for shared multicast trees in an existing shortest path routing network is considered. The RP configuration that minimizes the maximum link utilization is sought. An optimization model, including anycast RP (load sharing on more than one RP), is proposed. A solution strategy based on valid surrogate lifted GUB cover inequalities and branch-and-cut is proposed. Computational results are reported for the single and dual RP cases.

In paper D, the unicast network capacity dimensioning problem with general step costs and single path routing is investigated. An optimization model is developed and a Lagrangian decomposition branch-and-bound scheme is proposed. The relaxations decompose into non-negative length shortest path and continuous knapsack subproblems, both which can be solved by efficient algorithms. Computational results are reported for a set of test problems having decreasing per-unit of capacity costs.


Calendar of seminars
Last update: February 19, 2002 by Anders Forsgren, anders.forsgren@math.kth.se.