Research On QoS-supported Scalable Reliable Routing Algorithm And Forwarding Technology

ABSTRACT:With the development of network technologies, the service provided by networks is turning from traditional data communication into multiple services including many new real-time multimedia applications, such as video conference and VOIP. As the core technology of packet network, driven by the requirements of new services, routing and forwarding is meeting many great challenges.First, hop-based shortest path routing algorithms can not meet demand of realibilty QoS routing for real-time multimedia applications. So, designing effective multi-constrained disjoint path algorithms is a key question of new gerenration routing algorithm. Second, in order to provide end-to-end (E2E) QoS control service for users, inter-domain QoS routing must be furnished. How to reduce the advertizing data quantity to improve inter-domain QoS routing scalability is a critical question to be solved. Third, current IP networks can hardly delivery the packet of a flow on a specified path, which makes it difficulty to do QoS control and to carry out network management and optimizition work, e.g. charging and traffic enginnering. Thus, how to provide E2E fast flexible forwarding over IP networks is a very important issue to be studied. Fourth, exact QoS control often depends on deterministic calculation of network performance bound, but the high variability and high burstness of internet traffic makes tradiational network analysis models invalid. How to do exact quantitative calculation with the bennifit of new network analysis tools for internet traffic also is a meaningful question greatly deserved to be studied.Aiming at the problems mentioned above, this paper does much comprehensive and deep reaserch work. The main innovation work of our paper is as followes:(1) To deal with the issue that existing algorithms cannot always ensure to find feasible solutions of multi-constrained link-/node-disjoint path pair (MCLPP/MCNPP) problem for realible QoS routing, we present the design principle for exact algorithms. Based on this, we propose the Link Disjoint Optimal Multi-constrained Paths Algorithm (LIDOMPA) for MCLPP problem. Moreover, we extend LIDOMPA and present the Node Disjoint Optimal Multi-constrained Paths Algorithm (NODOMPA) to solve the (MCNPP) problem. Theoritical analysis and extensive experiments show that our algorithms can find the shortest disjoint path pair under multiple QoS constraints and achieve accepted complexity. (2) Directing towarding the scalability problem of inter-domain QoS routing. We present a regular polyline (RPL) based QoS-path aggregation algorithm. To further improve the aggregation performance, we propose a novel six-tuple based hybrid algorithm by combining the proposed RPL algorithm with the existing line segment (LS) approach. In the hybrid algorithm, a better model between the RPL model and the LS one can be adopted automatically to do aggregation. Only a six-tuple array is required to express the aggregated result and O(1) space complexity is achieved. Moreover, we define the aggregation error rate to evaluate the performances of geometric aggregation schemes accurately. Experiment results show that our methods outperform existing ones in terms of lower aggregation error rate and obtain feasible complexity.(3) Aiming at the problem that current network can hardly do scalable fast flexible forwarding. We propose a Link-interface ID Code based Forwarding (LICF) approach, which can forward data packets directly according to the LIC in their headers via establishing connection-oriented LIC paths in advance. LICF is an explicit routing based forwarding approach, which avoids routing lookup in data packets forwarding and can improve network QoS performance and traffic engineering ability. Moreover, since besides the routing tables, no extra information needs to be stored and managed in routers, LICF achieves good scalability. As IP address information can be hidden in data packets transmission, LICF tends to enhance network security. Experiments performed on a prototype show that our scheme obtains fast forwarding and can help to increase network throughput effectively.(4) Based on the work of (3) above, we present the QoS-enhanced LICF (QLICF) network model by introducing fractal leak bucket model and the WFQ model to enhance QoS ability of LICF network. Futher, we analyze the E2E delay bound, jitter bound and the non packet loss buffer size bound of QLICF network by means of the network calculus, a new effective theoretical tool on analyzing the QoS performance of Internet. The formulations of the three bounds mentioned above are presented and proved. We also analyze the variation patterns of these QoS bound versus the parametes including the traffic property and the queuing priority. The obtained conclusions can provide theoretical references for network optimization and QoS controll work.