english Icono del idioma   español Icono del idioma  

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12008/2914 How to cite
Title: GRASP heuristics for Wide Area Network design
Authors: Robledo Amoza, Franco Rafael
Obtained title: Doctor en Informática
University or service that grants the title: Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación – PEDECIBA
Tutor: Cancela, Héctor
Rubino, Gerardo
Type: Tesis de doctorado
Keywords: TOPOLOGICAL DESIGN, METAHEURISTIC, ACCESS NETWORK, BACKBONE NETWORK, SURVIVABILITY, GRASP, RNN
Issue Date: 2005
Abstract: A wide area network (WAN) can be considered as a set of sites and a set of communication lines that interconnect the sites. Topologically a WAN is organized in two levels: the backbone network and the access network composed of a certain number of local access networks. Each local access network usually has a tree-like structure, rooted at a single site of the backbone, and connects users (terminal sites) either directly to this backbone site or to a hierarchy of intermediate concentrator sites which are connected to the backbone site. The backbone network has usually a meshed topology, and its purpose is to allow efficient and reliable communication between the switch sites that act as connection points for the local access networks. In this thesis we tackled the problem of designing a WAN by breaking it down into two inter-related sub-problems: the Access Network Design Problem (ANDP) and the Backbone Network Design Problem (BNDP). In both models we considered only the construction costs, e.g. the costs of digging trenches and placing a fiber cable into service. We modeled the ANDP as a variant of the Steiner Problem in Graphs (SPG), and the BNDP on the basis of the Generalized Steiner Problem with Node-Connectivity Constraints (GSP-NC). In addition, we studied the specific case of BNDP when there exist 2-node-survivability requirements between pairs of backbone fixed nodes. We call it BNDP2NS and it is analogous to the Steiner 2-node-survivable network problem (STNSNP). ANDP, BNDP, and BNDP2NS are NP-Hard problems. Our goal was to attack the ANDP, BNDP, and BNDP2NS models heuristically. We opted for the GRASP (Greedy Randomized Adaptive Search Procedure) methodology for solving them. GRASP is a powerful method which has been used with success to find good quality solutions to many combinatorial optimization problems. We developed GRASP algorithms for these three problems, designing different alternative algorithms for the construction and local each phases
Publisher: UR. FI-INCO,
Citation: ROBLEDO AMOZA, F. "GRASP heuristics for Wide Area Network design". Tesis de doctorado, Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación – PEDECIBA, 2005.
License: Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Appears in Collections:Tesis de posgrado - Instituto de Computación

Files in This Item:
File Description SizeFormat  
tesisd-robledo.pdf1,46 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons