Chinese Journal of Computers   Full Text
Title	A Parallel QoS Routing Optimization Based on Pareto Subsets
Authors	QIN Yong1),2) XIAO Wen-Jun2) HUANG Han3) LIANG Ben-Lai4) ZHAO Cheng-Gui2) WEI Wen-Hong2)
Address	1)(Center of Information and Networks, Maoming University, Maoming, Guangdong 525000) 2)(School of Computer Science and Engineering, South China University of Technology, Guangzhou 510641) 3)(School of Software Engineering, South China University of Technology, Guangzhou 510641) 4)(School of Computer and Software, Taiyuan University of Technology, Taiyuan 030024)
Year	2009
Issue	No.3(463—472)
Abstract &   Background	Abstract The QoS routing is based on the computing of each flow. In order to optimize the volatile status messages and hysteresis quality of the dynamic routing request, a method (QPAS) for parallel routing optimization based on Pareto of QoS Metrics is proposed to find the feasible path quickly and inerrably. Parallel routing precomputing is used to obtain the Pareto subsets which satisfy the multiple routing request constraints, and a proper route is selected from these subsets synthetically. QPAS is proved to be valid and effective by simulated experiments, with its parallelized status collection and parallelized routing searching. QPAS can be used to solve the complex QoS routing problems and other actual information transmission cases in the finite-node networks. Keywords parallel routing algorithm; QoS Metrics; Pareto subsets; multi-constraints; algorithm complexity Background This research is partly supported by the National Natural Science Foundation of China (60433020, 10471045, 60673023), Natural Science Foundation of Guangdong Province (970472, 000463, 04020079, 05011896), Natural Science Foundation of Education Department of Guangdong Province in China (Z03080). As hot focus research topics, the network status messages time-variation and network control hysteresis are prominent questions of QoS infrastructure and transmission control in the new generation of internet architecture. For the dynamic route computation, to find the feasible path quickly and inerrably is necessary, algorithms should have fairly satisfactory running times, low complexity to adapt the rapid dynamic route request and route status information, multiple QoS metrics in the evaluation of routing dispatch tactics should be considered. In many cases, the problem of QoS routing is known to be NP-complete and thus mostly dealt with using heuristics and approximations. At present, most of popular multi-constraints QoSR algorithms have been proposed based on determining the discontinuities of functions related to the optimization by using serial Dijkstra-based algorithms. Thus, these current major heuristics static routing algorithms and quasi-dynamic routing algorithms have exceeding complexity so as to cannot be used in actual networks; or lack satisfied computing ability to find a actual feasible path; most of them can only face some special cases in QoSR, they are inadaptable for the complex QoS multi-metrics on finite-node networks. This paper meets the opportunity to propose a paralleling optimization based multiple QoS metrics for the dynamic route precomputation, and the authors hope that the network resource effectiveness could be maximized by proposing a new aggravating approximation link price definition throughout all QoS metrics in conjunction, and the computation complexity of QPAS could provide good average case behavior, in addition to guaranteeing polynomial worst-case running time. Its basic thought contains restricting the number of unfeasible paths by analyzing theory of Pareto route optimization. Experimental results are elaborated to be valid and effective. QPAS can be used to solve the QoS routing problem on the finite-node networks and other actual cases of network information transmission. The prospects of the further research works are considered to avoid elusive redundant computation ulteriorly based on constraint sets, the relation between route updating frequencies and multi-level paralleling route computing are anticipant to be extended in the next generation algorithms. Adaptability and transplant of these algorithms in new generation of internet architecture FIND, GENI and FIRE could also be a new challenging prospect.1)(Center of Information and Networks, Maoming University, Maoming, Guangdong 525000) 2)(School of Computer Science and Engineering, South China University of Technology, Guangzhou 510641) 3)(School of Software Engineering, South China University of Technology, Guangzhou 510641) 4)(School of Computer and Software, Taiyuan University of Technology, Taiyuan 030024)