Accession Number : ADA469511


Title :   Use of Tabu Search in a Solver to Map Complex Networks onto Emulab Testbeds


Descriptive Note : Master's thesis


Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH GRADUATE SCHOOL OF ENGINEERING AND MANAGEMENT


Personal Author(s) : MacDonald, Jason E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a469511.pdf


Report Date : Mar 2007


Pagination or Media Count : 144


Abstract : The University of Utah's solver for the testbed mapping problem uses a simulated annealing metaheuristic algorithm to map a researcher's experimental network topology onto available testbed resources. This research uses tabu search to find near-optimal physical topology solutions to user experiments consisting of scale-free complex networks. While simulated annealing arrives at solutions almost exclusively by chance, tabu search incorporates the use of memory and other techniques to guide the search towards good solutions. Both search algorithms are compared to determine whether tabu search can produce equal or higher quality solutions than simulated annealing in a shorter amount of time. It is assumed that all testbed resources remain available, and that hardware faults or another competing mapping process do not remove testbed resources while either search algorithm is executing. The results show that tabu search produces a higher proportion of valid solutions for 34 out of the 38 test networks than simulated annealing. For cases where a valid solution was found, tabu search executes more quickly for scale-free networks and networks with less than 100 nodes.


Descriptors :   *TEST BEDS , *PROBLEM SOLVING , *MAPPING , *COMPUTER NETWORKS , ALGORITHMS , NETWORK TOPOLOGY , SIMULATION , HEURISTIC METHODS , THESES , ANNEALING


Subject Categories : Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE