Neural network and algorithmic methods for solving routing problems in high-speed networks.

摘要

Three classes of routing problems, namely, minimum delay routing (MDR), virtual path topology optimization (VPTO), and Quality of Service (QoS) unicast routing in a high speed network environment were investigated through both neural network (NN) optimization and algorithmic methods. A two-phase MDR routing algorithm based on Hopfield neural networks (HNNs) were proposed. The goal in the first phase was to provide a set of alternate routes for each source-destination (SD) pair, while the second phase computed the fraction of traffic to be distributed on each alternate route. Experiments demonstrated that the proposed algorithm could achieve better performance than previous non-exact algorithms. The HNN technique was also applied to solve the VPTO problem, which is a critical problem in a quasi-static VP control strategy. Experiments were also conducted to show the superiority of this approach. Subsequently, a set of NP-complete QoS unicast routing problems were studied based on linear or nonlinear Lagrange relaxation techniques. Three heuristic algorithms based on a single-mixed-weight idea were first proposed to solve the most representative delay-constrained least-cost path problem. Compared to previous approximate algorithms, the proposed algorithms can find solutions of high quality with very low time complexities. This idea was then extended to solve the problem of finding paths subject to two additive constraints. The corresponding approximate algorithm also outperformed almost all known heuristics. The single-mixed-weight idea was also used to develop exact algorithms for multi-constrained-path (MCP) problems and multi-constrained optimal-path (MCOP) problems. These exact algorithms can find exact solutions in a reasonable time for networks of a moderate size. Finally, based on a heuristic proposed by other researchers, we developed a modified heuristic algorithm to solve the MCOP problem. Compared to its predecessor, our modified algorithm can significantly reduce the cost of the obtained solution, while the time complexity was only slightly increased. A recommendation for further study is enclosed.