Robust network design (RND) applies the concept of robustness from optimization with uncertainty to the area of network design. Primary motivations stem from applications in telecommunication networks. The main presupposition is that demands across the networks are variable or unpredictable. They originate from a predefined demand set, called a demand universe. Moreover, practical impediments of network design enforce the routing of the demands to be oblivious, or fixed in advance, and to not depend on a particular instantiation from the demand universe. Additional restrictions, referred to as a routing model, are often enforced on the routing's structure. Shortest paths (SP) and hub (HUB) routing models have received particular attention, both on the theoretical and practical level. In this work, we introduce a new routing model, called the hierarchical hub routing model (HH), as a generalization to HUB. We study the theoretical properties of RND restricted to HH (RNDHH). Namely, we show its APX-hardness and provide a O(log n)-approximation algorithm. We then show how RNDHH is tractable when the problem is constrained to a particular demand universe based on demands routable on a tree. We also compare the costs of optimal solutions to RND using HH and other important oblivious routing models. Finally, we leverage HH in a practical study of a new demand universe called the capped hose model, which is a blend of the hose and the pipe model, two widely used demand universes. We use the capped hose model to shed light on which demand universes favour more a SP-like as opposed to a HH-like routing. To do so, we develop a heuristic algorithm for RNDHH, and benchmark our approach against SP using representative carrier networks and a variety of capped hose demands, parametrized by their similitude to a hose or pipe model. This study reveals conditions under which multi-hub routings, that is HH, gives improvements over single-hub and shortest path routings. / Le design de réseaux robustes (RND) est celui qui applique le concept de robustesse, issu de l'optimisation avec incertitude, au domaine de la conception de réseaux. Les principales motivations derrière cette application découlent de demandes provenant des réseaux de télécommunication. La prémisse principale est que les demandes à travers les réseaux sont variables ou imprévisibles. Toutefois, nous savons que ces demandes proviennent d'un ensemble prédéfini appelé univers de demandes. De plus, des contraintes pratiques du design de réseaux requiert que le routage des demandes soit inconscient, ou fixé d'avance, et qu'il ne dépende pas d'une instanciation particulière de l'univers de demandes. Des contraintes additionnelles, connues sous le nom de modèle de routage, s'appliquent souvent à la structure du routage. Les routages par chemins les plus courts (SP) et par moyeu unique (HUB) ont reçu une attention importante, tant au niveau théorique que pratique. Dans cette thèse, nous introduisons un nouveau modèle de routage appelé routage hiérarchique par moyeux (HH), qui est une généralisation de HUB. Nous étudions les propriétés théoriques de RND restreint à HH (RNDHH). Plus particulièrement, nous démontrons son caractère APX-difficile et fournissons un algorithme O(log n)-approché. Par la suite, nous montrons comment RNDHH devient facilement soluble lorsque restreint à un univers de demandes particulier, basé sur des demandes qui peuvent être routées sur un arbre donné. Nous comparons également le coût des solutions optimales lorsque RND utilise HH ainsi que d'autres modèles de routage inconscients importants. Finalement, nous exploitons HH dans une étude pratique sur un nouvel univers de demandes, appelé modèle par tuyaux restreints, qui est un mélange de deux univers de demandes largement utilisés soit le modèle par tuyaux et le modèle par conduits. Nous utilisons le modèle par tuyaux restreints pour caractériser quel univers de demandes favorise un routage similaire à SP contrairement à un routage HH. Pour ce faire, nous développons un algorithme heuristique pour RNDHH et évaluons notre approche par rapport à SP à l'aide de réseaux d'opérateur ainsi que plusieurs types de demandes du modèle par tuyaux restreints, ceux-ci ayant été paramétrés par leur similitude à un modèle par tuyaux ou un modèle par conduits. Cette étude révèle les conditions à travers lesquelles le routage par multiples moyeux, c'est-à-dire HH, surpasse celui par HUB et SP.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.114431 |
| Date | January 2013 |
| Creators | Fréchette, Alexandre |
| Contributors | 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 | Master of Science (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.0129 seconds