Robust network design takes the very successful framework of robust optimization and applies it to the area of network design, motivated by applications in communication networks. The main premise is that demands across the network are not fixed, but are variable or uncertain. However, they are known to fall within a prescribed uncertainty set. Our solution must have sufficient capacity to route any demand in this set; moreover, the routing must be oblivious, meaning it must be fixed up front, and not depend on the particular choice of demand from within the uncertainty set. A particular choice of uncertainty set within this framework yields the "hose model", which has received particular attention due to applications to virtual private networks. A 2-approximation was known for the problem, using a solution template in the form of a tree. It was conjectured that this tree solution is actually always optimal; this became known as the "VPN Conjecture". As one of the central results of this thesis, we prove this conjecture in full generality. In addition, we demonstrate a counterexample to a stronger multipath (fractional routing) version of the conjecture which had also been proposed. We initiate a study of the robust network design problem more generally, with a focus on approximability. In the general model, where the uncertainty set is given by an arbitrary separable polyhedron, we give a strong inapproximability result. We then consider a new and natural model generalizing the symmetric hose model, based on demands routable on a given tree, and provide a constant factor approximation algorithm. Lastly, we compare oblivious routing with the much more flexible (but also less practical) dynamic routing scheme where the routing may vary depending on the demand pattern. We show that in the worst case, the cost of an optimal oblivious routing solution can be much more expensive than the dynamic optimum, by up to a logarithmic factor. / Motivé par les applications concernantes les réseaux de communication, le dessein des réseaux robustes applique les méthodes très réusies provenant de l'optimisation robuste. La prémisse principale est que les demandes sur le réseau ne sont pas fixes, mais variables ou incertaines. Cependant, nous savons qu'elles sont tirées d'un ensemble d'incertitude prescrit. Il faut que la solution ait une capacité suffisante pour pouvoir router toute demande appartenant à cet ensemble. En outre, il faut que le routage soit oublieux, ce qui signifie qu'il peut être fixé à l'avance, et ne dépends pas du choix particulier de la demande appartenant de l'ensemble d'incertitude. Dans ce cadre, il existe un choix particulier d'ensemble d'incertitude qui mène au « modèle de tuyau ». Ce modèle a reçu une attention particulière à causede ses applications aux réseaux privés virtuels. On connaissait un 2-rapprochement utilisant une solution en forme d'arbre. La « Conjecture de VPN » énonce que cette solution en forme d'arbre est toujours optimale. L'un des résultats principaux de cette thèse démontre cette conjecture en toute généralité. En outre, nous donnons un contre-exemple à une version plus forte de la conjecture concernant les chemins multiples (le routage étant fractionnel) qui avait également été proposée. Nous initions l'étude du problème de la conception de réseaux robustes dans une plus grande généralité, en insistant sur l'approximabilité. Dans le modèle général, où l'ensemble d'incertitude est un polyèdre séparable arbitraire, nous donnons un résultat fort d'inapproximabilité. Nous considérons ensuite un nouveau modèle naturel généralisant le modèle de tuyau symétrique, qui est basé sur des demandes qui peuvent être routées sur un arbre donné, et nous fournissons un algorithme ayant un facteur de rapprochement constant. Finalement, nous comparons le routage oublieux avec le schéma beaucoup plus flexible (
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.95085 |
| Date | January 2010 |
| Creators | Olver, Neil |
| Contributors | Adrian Roshan Vetta (Internal/Cosupervisor2), Frederick Shepherd (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0016 seconds