ROLAND : a tool for the realistic optimisation of local access network design

Simple item page
dc.contributor.advisorKritzinger, Pieter Sen_ZA
dc.contributor.authorBuffler, Simonen_ZA
dc.date.accessioned2014-11-04T08:48:57Z
dc.date.available2014-11-04T08:48:57Z
dc.date.issued1999en_ZA
dc.descriptionBibliography: p. 141-147.en_ZA
dc.description.abstractInvestment in the local access network represents between 50% and 70% of capital investment of a telecommunications company. This thesis investigates algorithms that can be used to design economical access networks and presents ROLAND: a tool that incorporates several of these algorithms into an interactive environment. The software allows a network designer to explore different approaches to solving the problem, before adopting a particular one. The family of problems that are tackled by the algorithms included in ROLAND involve determining the most economical way of installing concentrators in an access network and connecting demand nodes such as distribution points to these concentrators. The Centre-of-Mass (COM) Algorithm identifies clusters of demand in the network and suggests good locations for concentrators to be installed. The problem of determining which concentrators in a set of potential sites to install is known as the concentrator location problem (CPL) and is an instance of the classical capacitated plant location problem. Linear programming techniques such as branch-and-bound can be used to find an optimal solution to this problem, but soon becomes infeasible as the network size increases. Some form of heuristic approach is needed, and ROLAND includes two such heuristics, namely the Add and Drop Heuristic. Determining the layout of multi-drop lines, which allow a number of demand nodes to share the same connection to a concentrator, is analogous to finding minimal spanning trees in a graph. Greedy approaches such as Kruskal's algorithm are not ideal however, and heuristics such as Esau-William's algorithm achieve better results. Kruskal's algorithm and Kershenbaum's Unified Algorithm (which encapsulates a number of heuristics) have been implemented and come bundled with ROLAND. ROLAND also includes an optimal terminal assignment algorithm for associating distribution points to concentrators. A description of ROLAND's architecture and GUI are provided. The graphical elements are kept separate from the algorithm implementations, and an interface class provides common data structures and routines for use by new algorithm implementations. A test data generator, able to create random or localized data, is also included. A new hybrid concentrator location algorithm, known as the Cluster-Add Heuristic is presented. The implementation of this algorithm is included in ROLAND, and demonstrates the ease with which new solution methods can be integrated into the tool's framework. Experimentation with the concentrator location algorithms is conducted to show the Cluster-Add Heuristic's relative performance.en_ZA
dc.identifier.apacitationBuffler, S. (1999). <i>ROLAND : a tool for the realistic optimisation of local access network design</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/9067en_ZA
dc.identifier.chicagocitationBuffler, Simon. <i>"ROLAND : a tool for the realistic optimisation of local access network design."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Computer Science, 1999. http://hdl.handle.net/11427/9067en_ZA
dc.identifier.citationBuffler, S. 1999. ROLAND : a tool for the realistic optimisation of local access network design. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Buffler, Simon AB - Investment in the local access network represents between 50% and 70% of capital investment of a telecommunications company. This thesis investigates algorithms that can be used to design economical access networks and presents ROLAND: a tool that incorporates several of these algorithms into an interactive environment. The software allows a network designer to explore different approaches to solving the problem, before adopting a particular one. The family of problems that are tackled by the algorithms included in ROLAND involve determining the most economical way of installing concentrators in an access network and connecting demand nodes such as distribution points to these concentrators. The Centre-of-Mass (COM) Algorithm identifies clusters of demand in the network and suggests good locations for concentrators to be installed. The problem of determining which concentrators in a set of potential sites to install is known as the concentrator location problem (CPL) and is an instance of the classical capacitated plant location problem. Linear programming techniques such as branch-and-bound can be used to find an optimal solution to this problem, but soon becomes infeasible as the network size increases. Some form of heuristic approach is needed, and ROLAND includes two such heuristics, namely the Add and Drop Heuristic. Determining the layout of multi-drop lines, which allow a number of demand nodes to share the same connection to a concentrator, is analogous to finding minimal spanning trees in a graph. Greedy approaches such as Kruskal's algorithm are not ideal however, and heuristics such as Esau-William's algorithm achieve better results. Kruskal's algorithm and Kershenbaum's Unified Algorithm (which encapsulates a number of heuristics) have been implemented and come bundled with ROLAND. ROLAND also includes an optimal terminal assignment algorithm for associating distribution points to concentrators. A description of ROLAND's architecture and GUI are provided. The graphical elements are kept separate from the algorithm implementations, and an interface class provides common data structures and routines for use by new algorithm implementations. A test data generator, able to create random or localized data, is also included. A new hybrid concentrator location algorithm, known as the Cluster-Add Heuristic is presented. The implementation of this algorithm is included in ROLAND, and demonstrates the ease with which new solution methods can be integrated into the tool's framework. Experimentation with the concentrator location algorithms is conducted to show the Cluster-Add Heuristic's relative performance. DA - 1999 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1999 T1 - ROLAND : a tool for the realistic optimisation of local access network design TI - ROLAND : a tool for the realistic optimisation of local access network design UR - http://hdl.handle.net/11427/9067 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/9067
dc.identifier.vancouvercitationBuffler S. ROLAND : a tool for the realistic optimisation of local access network design. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Computer Science, 1999 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/9067en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Computer Scienceen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherComputer Scienceen_ZA
dc.titleROLAND : a tool for the realistic optimisation of local access network designen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_1999_buffler_s.pdf
Size:
10.69 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters