覆盖路由网络与流量工程间目标冲突问题研究

发布时间：2018-03-30 13:51

本文选题：覆盖网络　切入点：流量工程　出处：《北京邮电大学》2016年博士论文

【摘要】：随着互联网的进一步发展,特别是当前移动互联网的兴起,各种类型的新型应用不断涌现,例如移动社交、移动电商、手机游戏和虚拟现实等,这些新型应用对网络的可靠性、时延和丢包率等性能提出了更高的要求。然而,当前互联网采用的尽力而为的数据传输方式缺乏对服务质量的有效保障,无法满足某些业务的需求。随着互联网大规模的部署,想要通过改变现有网络协议架构来提高网络性能将会非常困难。覆盖网络(Overlay Network)为改进互联网性能提供了一种新思路。它是构建在物理网络之上的一种虚拟网络,由分布在网络中的覆盖节点通过逻辑链路连接而成。覆盖网络不需要大规模改变物理网络结构就能提供比现有互联网更好的服务质量,它能根据用户的特定需求在应用层上计算路由,并通过传输路径中其它覆盖节点的转发来完成数据的传输。覆盖路由是指通过覆盖网络进行的路由模式,是覆盖网络研究的关键技术,受到了国内外学者的广泛关注。在现实中,为了提升服务的性能,服务提供商在互联网上部署了大量支持各种类型服务的覆盖网络。然而,覆盖路由的本质是自私路由,它根据具体服务的需求进行路由,与物理网络流量工程的路由目标通常并不一致,因此常常会发生冲突;同时,共存的覆盖网络之间也可能会因为竞争网络资源而出现冲突。这种冲突所引起的路由交互问题,严重影响了网络的效率和稳定性。本文针对多个覆盖网络共存环境下路由的混合交互问题展开研究,主要采用非合作和合作博弈理论对整个交互过程进行分析,专注于提高网络的性能和稳定。全文的研究内容和主要贡献概括如下:(1)考虑到物理网络为上层的覆盖网络提供物理网络资源,它的地位应该等于或者高于覆盖网络,本文采用n+1参与者非合作博弈对物理网络地位与覆盖网络相等情况下的混合交互进行建模,其中n+1个参与者分别为n个覆盖路由和1个流量工程。在该博弈中,所有覆盖路由和流量工程的地位相等,它们在平等条件下轮流执行。本文证明了纳什均衡的存在,并分别提出了静态最优反应算法和动态最优反应算法两种算法来求解纳什均衡。(2)采用1领导者n跟随者的斯塔克尔伯格-纳什博弈对物理网络地位高于覆盖网络情况下的混合交互进行建模。在该博弈中,流量工程为领导者,n个覆盖路由为跟随者,流量工程的地位高于所有覆盖路由,覆盖路由之间的地位相等。流量工程作为领导者先执行,然后所有覆盖路由基于它的策略给出最优反应,所有覆盖路由的策略依赖流量工程的策略。本文证明了斯塔克尔伯格-纳什均衡的存在,以及流量工程在斯塔克尔伯格-纳什均衡状态的性能要好于在纳什均衡状态的性能,并给出了斯塔克尔伯格-纳什均衡求解算法。(3)考虑到创新点(1)和(2)得到的纳什均衡和斯塔克尔伯格-纳什均衡都是非合作博弈情况下的结果,通常是非帕累托最优的,对它们进行性能改进是可行的。本文提出了一种联盟合作机制和一种基于夏普利值的公平有效的成本分配方案,即参与者通过结成联盟来共同优化联盟的目标,并使用夏普利值来决定联盟内每个参与者需要分担的成本。仿真实验验证在联盟合作方案下,各参与者均获得了比独立非合作博弈时更好的性能。(4)考虑到覆盖网络热门应用之一的云计算数据中心和多个互联网服务提供商的网络之间也存在交互问题,本文首先采用非合作博弈理论对数据中心选择和多个物理网络流量工程之间的交互进行建模,证明了纳什均衡的存在并用例子说明了纳什均衡的有效性损失。然后,基于纳什讨价还价解模型提出了一个公平有效的合作方法,并设计了一个分解算法来求解纳什讨价还价解。仿真实验验证了在纳什讨价还价解模型中,数据中心和所有物理网络都获得了比非合作时更好的性能。
[Abstract]:With the further development of Internet, especially the rise of the mobile Internet, new applications of various types are emerging, such as mobile social networking, mobile providers, mobile phone games and virtual reality, the reliability of these new applications of the network, such as delay and packet loss rate can put forward higher requirements. However, the current data transmission mode the Internet uses the best effort the lack of effective protection of the quality of service, can not meet the needs of some services. With the large-scale deployment of Internet, want to change the existing network protocol architecture to improve the performance of the network will be very difficult. The overlay network (Overlay Network) provides a new way to improve the performance of the Internet. It is built on a the virtual network physical network, covered by the distribution of nodes in the network through logical link connection and coverage. The network does not need to be large. Change the mode of physical network architecture can provide better quality of service than the existing Internet, it can according to the specific requirements of the user computing routing at the application layer, and through the transmission path of other overlay nodes to transmit data. Overlay routing refers to the routing mode covering network, is the key technology of network coverage the widespread attention of scholars at home and abroad. In reality, in order to improve the performance of services, service providers support the deployment of a large number of various types of service overlay network on the Internet. However, covering the road by nature is selfish routing, it according to the specific needs of service routing, routing and physical network traffic engineering usually are not the same, so often clash; at the same time, may also be because of the coexistence between the overlay network and the emergence of cyber source competition conflict. This impact The routing problem caused by the interaction process, which seriously affects the efficiency and stability of the network. Based on the multiple overlay network coexistence environment routing mixed interaction issues, mainly by non cooperative and cooperative game theory to analyze the whole process, focus on improving network performance and stability. The main research content and main contributions are summarized as follows: (1) considering the physical network to provide physical and cyber source for overlay network layer, its status should be equal to or higher than the overlay network, this paper adopts n+1 non cooperative game participants mixed to physical network status and network coverage under the same interaction model, the n+1 participants respectively n overlay routing and 1 traffic engineering. In the game, covering all routing and traffic engineering are equal, they take turns in equal conditions. The Wen Zhengming The existence of the Nash equilibrium, and then proposed the static optimal algorithm and dynamic response optimal reaction algorithm two algorithm to solve Nash equilibrium. (2) the 1 N leader follower Stackelberg game - Nash on the physical network status is higher than that of hybrid overlay network under the condition of interactive modeling. In the game, traffic engineering as a leader, a n overlay routing is the follower, traffic engineering status is higher than that of all overlay routing overlay routing between equals. As the leader of the first implementation of traffic engineering, then all overlay routing based on its strategy of optimal reaction, all overlay routing strategy on traffic engineering strategy. This paper proves that the Stackelberg - the existence of Nash equilibrium, and traffic engineering in Stackelberg Nash equilibrium state is better than the performance in the Nash equilibrium, and gives the Adams Berg Tucker - Nash equilibrium solution algorithm. (3) considering innovation (1) and (2) to get the Nash equilibrium and Stackelberg Nash equilibrium are non cooperative game conditions, is usually non Pareto optimal, for their performance improvement is feasible. This paper proposes a kind of alliance cooperation mechanism and a Shapley value of fair and effective cost allocation scheme based on which the participants through formed an alliance to jointly optimize the objectives of the alliance, and use Shapley value to determine the alliance each participant need to share the cost. The simulation verification in the alliance cooperation scheme, each participant had better performance than non cooperation the game. (4) also has the problem of interaction between one of the popular network applications covering cloud computing data center and a number of Internet service providers network into account, this paper firstly uses non alloy As the game theory to model the interaction between the data center and multiple physical network traffic engineering, proves the existence of Nash equilibrium is illustrated by an example of loss of effectiveness of the Nash equilibrium. Then, Nash bargaining solution model put forward a fair and effective cooperation method based on a decomposition algorithm to solve the Nash bargaining the solution is designed. The simulation experiment in the Nash bargaining solution model, data center and all the physical network have better performance than non cooperative.

【学位授予单位】：北京邮电大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.0

【参考文献】