Research On Multi-metrical-driven Path Selection Mechanism

The rapid development of broadband networking technology and multi-media services lead the number of users to increase significantly. The streaming services are playing vital role in broadband networks and multimedia commu-nication. Within streaming service area, Quality of Service (QoS) mechanism is a dispensable ingredient for multimedia services provisioning. However, the current Internet cannot provide any QoS guarantees, which becomes the major barrier to the Internet evolution. Therefore, establishing an effective mechanis-m to provide QoS guarantees is realized as an open topic by both industrial and academia.Multi-metrical QoS path selection (or known as multiconstrained path) problem, as the key component of QoS provisioning, has been attracted much attention recent years. Though much progress has been made toward solving this problem efficiently, they are too complex to deploy in real-world networks. This paper investigates the problem of multi-metrical QoS path selection from a more practical perspective. The research study emphasizes the algorithmic design and its application in various networking scenario on the problem. The contributions made in this paper includes●A proactive approximation algorithm based on the graph-extending tech-nique and the theoretical analysis on the proposed algorithm, where the graph-extending could unify all QoS metrics in a single one graph and the theoretical analysis gives the performance of proposed algorithm. Through comparison between the proposed algorithm and previous best-known algorithms, it is found that the algorithm presented in this paper is superior to the best-known algorithms in terms of both execution time and the quality of solution. The proposal is effective and efficient, thus enriching the QoS routing research. ●By re-considering the design of the proposed approximation algorithm and observing the geometrical properties of linear combination and non-linear combination, a proactive heuristic, which is the first to employ the technique of nonlinear combination, is proposed. A deployment analysis of heuristic on the practical network protocol is conducted. Both theoreti-cal analysis and experimental results show that the proposed heuristic can reduce the time and space complexity dramatically, that is, the proposed heuristic achieves a good trade-off between execution time and quality of solution. The research study forms the basis of application of QoS routing algorithms in real-world networking systems.●A heuristic and an approximation algorithm for constructing QoS-aware multicast routing tree, in which the heuristic is presented by introducing nonlinear combination in a best-known algorithm, and approximation al-gorithm is given by an algebraic extension of the proposed algorithm.To the best of author’s knowledge, this is the first work to apply approxima-tion algorithm in resolving multiconstrained QoS-aware multicast rout-ing tree problem. The comparison is conducted between heuristic and approximation algorithm from both theoretical analysis and experiments show that the research presented provides new ways for establishing QoS-aware multicast routing tree.●A theoretical Framework for end-to-end QoS routing in future Internet is presented. The framework presented in this paper emphasizes modeling, algorithms as well as analysis on end-to-end QoS routing. That is, mod-eling the serving capability of underlying resources from a "bottom-up" perspective; developing efficient algorithms including a special case of an exact algorithm and a variant form of the proposed approximation algo-rithm to select the optimal routes for each routing request; and analyzing how these algorithms deploy and work in future Internet. The theoreti-cal derivations and experimental results show that the modeling technique and the algorithms developed in this paper are general and flexible; thus are applicable to the various networking systems in future Internet.●A model for the end-to-end multimedia service delivery in network virtu-alization environments, proposal of efficient algorithms embracing an ex-act and an improved approximation algorithm for selecting paths travers-ing the network infrastructure for QoS provisioning in virtual networks, and analysis of the effectiveness and efficiency of the proposed algorithm-s are presented. Both theoretical analysis and experimental results show that the modeling technique and the algorithms proposed in this paper are general and flexible, and therefore applicable to the delivery of multime-dia content in various heterogeneous networking systemsIn conclusion, this thesis investigates the problem of multi-metrical QoS path selection and its application in QoS-aware multicast routing tree, end-to-end QoS provisioning, and service selection in network virtualization. Some new computing results are given in this work, which systematically enrich the theory of "multi-metrical QoS path selection". The research presented in this thesis sets a good example for developing related theory.