Study On Routing Algorithm In Overlay Network

Overlay network is virtual network, which composed by a lot of nodes and links. Every node and link between nodes are in some AS (Autonomy Systems) which managed by ISP (Internet Service Provider). Overlay network can provide reliable service to user, and can not change the framework of Internet. The capability of a overlay network is decided by the ability to provide QoS.The research QoS in overlay network, the routing algorithm of overlay network model is very important. The study routing algorithm in overlay network is testified that one algorithm which represents the best performance in someone overlay network framework maybe is the worst performance in another one. The different overlay network models have different overlay network routing algorithm, which have different cost value or parameter of QoS. The goal of all routing algorithms in overlay network are search a satisfy path for service meanwhile the algorithm must have the ability of load balancing in SON (Service Overlay Network) which could offer more service with the same network resource.QUEST is one of model about overlay network, is first bring forward by X.Gu. QUEST framework is a QoS-assured Composition service infrastructure. It can simultaneously achieve QoS assurances and load balancing in SON. The core of routing algorithms in QUEST is QSCB algorithm. The job of QSCB algorithm is choose the path for the service which determine by the path's cost value, when two or more paths have the same cost value, the QSCB is choose one randomly. According to analysis and study the QSCB, we found the way of QSCB to solve the problem which more paths have the same cost value is not consider the ability of load balancing , and can not load balancing in SON at all, so it's not accord with the goal of routing algorithms in overlay network. We follow the way of other routing algorithms in overlay network, add a balancing parameter to the QSCB. The purposes is change the same cost value to different, and finally choose the best path which satisfy the parameter of QoS and load balancing in SON. By get the better load balancing in SON, we can not only offer more service with the same network resource, but can improve the rate of QoS satisfaction and the rate of node and link's using.In our simulate experiment, we choose the nodes, links, service randomly to build a model of overlay network. The result of comparison of QSCB and improved is that the improved algorithm is better in the aspect of the rate of QoS satisfaction and the rate of node and link's using, but is not obviously. According to our analysis, the improved algorithm is only solve the problem of more paths have the same cost value, the more problem happen, the better effect of improved algorithm. And we still try another test to testify the validity of our improved algorithm. We choose seven nodes and three services and regulate the links and parameter of QoS to simulate the instance happen. In this test we can prove our improve algorithm is validity.In the end, we can get a conclusion. The improved algorithm is better than QSCB in the aspect of solving the problem of more paths have the same cost value. And it improved the rate of QoS satisfaction and the rate of node and link's using of QUEST.