Research On Objective Conflict Between Overlay Routing Network And Traffic Engineering

With the further development of the Internet, especially the rise of the current mobile Internet, various types of new applications continue to emerge, such as mobile social, mobile commerce, mobile game and, etc.These new applications have put forward higher requirements on the performance of network reliability, delay and packet loss rate. However,the best effort data transmission in the existing Internet is lack of effective guarantee for the quality of service, and can not meet the needs of some business. With the large-scale deployment of the network, it is very difficult to improve the performance of the network by changing the existing network protocol architecture.Overlay network provides a new idea to improve the performance of the Internet. It's a virtual network built above the physical network,which is formed by the interconnection of the overlay nodes through the logical links. Overlay network can provide better service quality than the existing Internet without large-scale changes in the physical network structure, which calculates the route at the application layer according to the specific needs of users and transfers the data through the forwarding of other overlay nodes in the path. Overlay routing refers to a routing mode through the overlay network, which is the key technology of overlay network research and has been widely concerned by scholars both at home and abroad. In reality, in order to improve the performance of services, service providers deploy a large number of various service overlay networks on the Internet. However, overlay routing is selfish routing and makes decision based on the performance metrics of specific service, which is in conflict with the objective of physical network's traffic engineering. Meanwhile, there are also conflicts among co-existing overlay networks due to the competition of network resources. These conflicts affect the efficiency and stability of the network. Aiming at the hybrid interaction in multiple co-existing overlay network environment,this paper uses non-cooperative and cooperative game theory to study the interaction process, focusing on improving the performance and stability of the network. Our work presents the following contributions:(1) Considering the physical network providers physical network resources for multiple co-existing overlay networks, its status should be equal or higher than overlay networks. n+1-player non-cooperative game is adopted to model one situation of the hybrid interaction, in which n+1 participants were n overlay routing and one traffic engineering. In this game, all overlay routing and traffic engineering are equal in status, and they take turns to perform routing under equal conditions. We prove the existence of Nash equilibrium (NE), and propose two algorithms,static optimal response algorithm and dynamic optimal response algorithm, to solve the Nash equilibrium.(2) 1-leader-n-follower Stackelberg-Nash game is adopted to model another situation of the hybrid interaction. In this game, the traffic engineering is the leader, n overlay routing are followers. TE has higher status than overlays and plays its routing strategy first, and then all the overlays react optimally. We prove the existence of Stackelberg-Nash equilibrium (SNE),and physical network in a Stackelberg Nash equilibrium can achieve better performance than that in the Nash equilibrium. Last, we propose a genetic algorithm to solving Stackelberg-Nash equilibrium.(3) Considering the Nash equilibrium and Stackelberg-Nash equilibrium of contribution (1) and (2) are usually inefficient (or not Pareto optimal), the performance improvement on them is possible. Based on this point, we propose a coalition cooperation mechanism and a fair and effective cost allocation scheme base on Shapley value, in which players form a coalition to optimize the common goal and uses Shapley value to determine the cost each player need to share. The simulation results show that all the players obtain better performance than the non-cooperative game.(4) The cloud computing datacenter, which is one of the popular overlay applications, also has the interaction between multiple ISP networks. A noncooperative game theory is adopted to model the interaction between the datacenter selection and traffic engineering of multiple physical network. We prove the existence of Nash equilibrium, and give an example to illustrate the efficiency loss of Nash equilibrium. Then, a fair and effective cooperation method is proposed based on Nash bargaining solution model, and a decomposition algorithm is proposed to solve the Nash bargaining solution for the players. The simulation results show that in the Nash bargaining solution model datacenters and all the physical networks have better performance than that in the non-cooperative game.