Probabilistic Trans-Algorithmic Search

Online configuration of large-scale systems such as networks requires parameter optimization within a limited amount of time. This time limit is even more pressing when configuration is needed as a recovery response to a failure in the system. To quickly configure such systems in an online manner, we propose a Probabilistic Trans-Algorithmic Search (PTAS) framework which leverages multiple optimization search algorithms in an iterative manner. PTAS applies a search algorithm to determine how to best distribute available experiment budget among multiple optimization search algorithms. It allocates an experiment budget to each available search algorithm and observes its performance on the system-at-hand. PTAS then reallocates the experiment budget for the next round proportional to each algorithm's performance relative to the rest of the algorithms. This "roulette wheel" principle favors the more successful algorithm in the next round. Following each round, the PTAS framework "transfers" the best result(s) among the individual algorithms, making our framework a "trans-algorithmic" one. PTAS thus aims to systematize how to "search for the best search". We show the performance of PTAS on well-known benchmark objective functions including scenarios where the objective function changes in the middle of the optimization process. To illustrate applicability of our framework to automated network management, we apply PTAS on the problem of optimizing link weights of an intra-domain routing protocol on three different topologies obtained from the Rocketfuel dataset. We also apply PTAS on the problem of optimizing aggregate throughput of a wireless ad hoc network by tuning data rates of traffic sources. We compared the experimental results of PTAS against other three well-known search algorithms, i.e., Random Recursive Search, Simulated Annealing, and Genetic Algorithm. We observe that PTAS outperforms other three search algorithms in the majority of experiments. Especially, when the network system at-hand is very dynamic with factors, such as link failures and link recovery, PTAS performs better, and adapts to the new system more quickly due to its hybrid nature.

Level thesis:degree_level

Doctorate Degree

Year dc:date.issued

2011

Author dc:creator

• Gonen, Bilal

Advisor dc:contributor.advisor

• Yuksel, Murat

Committee members dc:contributor.committeemember

• Bryant, Bobby
• Fadali, Sami
• Gunes, Mehmet
• Louis, Sushil

• network management
• networks
• optimization
• routing

Statement dc:rights

• In Copyright(All Rights Reserved)

Handle dc:identifier.uri

http://hdl.handle.net/11714/3907

OAI identifier oai:identifier

oai:scholarwolf.unr.edu:11714/3907