覆盖网络技术是下一代互联网、云计算数据中心网领域研究的热门技术。本书紧紧围绕互联网发展的前沿课题，介绍下一代互联网的热点问题及其解决思路。全书从覆盖网络的产生背景、基本原理及应用出发，通过分析现有互联网存在的问题，以及覆盖网络的不足之处，研究了覆盖网络拓扑构建、多路径负载均衡路由、覆盖网无状态多播，以及覆盖路由与底层物理网络流量工程之间目标不一致而导致的路由冲突问题。

本书是作者在密切跟踪该领域研究成果的基础上深入研究的结果，是一本全面论述覆盖网络弹性路由与跨层优化的著作。全书图文并茂、深入浅出，理论与实践相结合，可读性强。可作为计算机科学与技术、网络工程、物联网、信息工程等相关专业的高年级本科生和研究生的教学参考用书，也可以作为关注新一代互联网理论与实践的研究者的参考用书。

随着互联网的进一步普及，基于网络的新型应用不断涌现，如视频点播、视频会议、远程教育、网络多媒体交互协作平台、在线网络游戏等，这些新型应用要求通信网络提供高可靠性、高带宽、低时延的服务。然而，在互联网规模日益扩大的同时，Internet本身的僵化现象越来越明显。例如，链路故障恢复时间长以及路由膨胀等问题，严重影响端到端的传输性能；IP多播的部署难和可扩展性差等问题，限制了日益增长的一对多和多对多数据传输；缺乏对QoS的有效保障，无法满足某些业务的需求。此外，互联网的基础服务提供商（ISP）之间存在复杂的商业利益关系，这使得对现有技术的重大调整变得异常困难。

覆盖网络（Overlay Network）的出现为现有互联网的改造和升级提供了新的思路。覆盖网络是建立在已有网络上的一种逻辑网络，利用隧道或封装机制将覆盖节点（Overlay Nodes）互连起来，形成覆盖网络拓扑来完成数据传输，而无须改变原有的互联网基础设施。覆盖网络除了能完成类似P2P（PeertoPeer）、CDN（Content Delivery Network）这样的内容分发与共享服务之外，随着终端节点性能（CPU带宽和存储能力）的不断提升，也可以提供路由和组播这些原本只能由路由器完成的基础性服务。另一方面，随着服务器虚拟化和存储虚拟化技术的日臻完善，网络虚拟化技术成为国内外科学界研究的热点。覆盖网络技术作为网络虚拟化的一种有效的解决方案，为下一代互联网、云计算和数据中心网的规划设计提供了一种可行的思路。

虽然覆盖网络在提高路由质量、保障QoS、提供组播服务等方面能够对现有的互联网络基础设施起到很好的补充作用，但在构建覆盖网络时如何感知基础设施结构，达到上下层优势互补，还有许多关键问题亟待解决。例如，如何考虑物理网络中部分关键节点对覆盖网络拓扑构造、路由和数据分发的影响；如何解决两条或多条覆盖链路共享物理链路，造成性能下降的问题；如何建立具有节点邻近意识的覆盖网络，减少端到端的时延；在多播通信中如何降低节点状态的维护代价等。其次，覆盖路由是通过覆盖网络进行的路由模/覆盖网络弹性路由与跨层优化/式，是根据用户的特定需求在应用层上计算路由，是覆盖网络研究的关键技术，受到了国内外学者的广泛关注。在现实中，为了提升服务的性能，服务提供商（SP）在互联网上部署了大量支持各种类型服务的覆盖网络。然而，覆盖路由的本质是自私路由，它根据具体服务的需求进行路由，与物理网络流量工程的路由目标通常并不一致，因此常常会发生冲突；同时，共存的覆盖网络之间也可能会因为竞争网络资源而出现冲突。这种冲突所引起的路由交互问题，严重影响了网络的效率和稳定性。本书针对上述问题，对覆盖网络拓扑构建、多路径路由、应用层多播、上下层路由冲突等覆盖网络关键问题进行了深入细致的研究。在研究过程中，遵循IP网络的运行规律，通过问题抽象、模型构建、算法设计与求解、理论证明、实验验证等一系列严谨的过程，其结论对于下一代互联网的规划与设计具有一定的借鉴意义。

全书共分为8章，其中1～6章由田生文编写，第7章和第8章由龚军编写。在撰写过程中，参考且引用了国内外有关覆盖网络、Internet网络等方面的大量文献，在此，向相关作者表示衷心的感谢。

本书的出版得到国家自然科学基金（No. 61170161）的资助。另外，本书的编写还得到鲁东大学邹海林教授、王刚教授、杨洪勇教授；北京邮电大学廖建新教授、王晶教授、王敬宇老师、戚琦老师的大力支持，在此对他们的支持和帮助表示衷心的感谢。

特别感谢清华大学出版社，感谢责任编辑及其他参与此书编辑和出版的各位老师，为本书的顺利出版付出的辛勤劳动。

由于作者水平有限，书中不足之处在所难免，恳请广大读者和同行批评指正。

作者邮箱： sw_tian@yeah.net。

编者

2017年1月

第1章绪论1

1.1覆盖网络产生的背景1

1.1.1互联网的设计缺陷1

1.1.2下一代互联网设计思路2

1.2覆盖网络的本质7

1.2.1覆盖网络体系结构7

1.2.2覆盖网络的缺陷7

1.3本书的研究内容及结构安排11第2章覆盖网络概述12

2.1覆盖网络基本概念12

2.2覆盖网络的分类13

2.3覆盖网络的应用15

2.3.1P2P网络15

2.3.2内容分发网16

2.3.3应用层多播17

2.3.4增强服务质量（QoS）19

2.3.5云计算数据中心网20

2.3.6覆盖网络在SDN中的应用22

2.4覆盖网络研究现状23/覆盖网络弹性路由与跨层优化/2.4.1覆盖网拓扑构建24

2.4.2覆盖网路由31

2.4.3覆盖网多播34

2.4.4覆盖网感知方式41

2.5本章小结42第3章基于超节点的覆盖网络拓扑构建算法43

3.1研究背景43

3.2基于超节点的覆盖网拓扑构建46

3.2.1问题的描述46

3.2.2超节点的选取47

3.2.3K最小生成树覆盖网拓扑48

3.3覆盖网一跳路由快速恢复机制51

3.4算法性能评价53

3.4.1仿真实验53

3.4.2结果分析55

3.5本章小结62第4章负载均衡的覆盖网络多路径路由机制研究63

4.1研究背景63

4.2负载均衡的一跳覆盖网多路径路由64

4.2.1网络模型64

4.2.2线性规划模型66

4.3启发式算法68

4.3.1中继节点的选择68

4.3.2多路径流量切割率71

4.4多路径覆盖网络的部署72

4.5性能评价72

4.5.1仿真实验72

4.5.2结果分析74

4.6本章小结78第5章基于包内布隆过滤器的无状态覆盖网络多播80

5.1研究背景80

5.2具有节点邻近意识的覆盖网拓扑82

5.2.1节点的网络坐标82

5.2.2TransitStub覆盖网层次拓扑83

5.3基于包内布隆过滤器的覆盖网多播87

5.3.1包内布隆过滤器88

5.3.2无状态多播机制89

5.3.3数据转发中的误判率91

5.4性能评价92

5.4.1仿真实验92

5.4.2结果分析93

5.5本章小结96第6章覆盖网络路由冲突问题98

6.1研究背景98

6.2流量工程概述98

6.2.1流量工程概念98

6.2.2流量工程分类99

6.3路由冲突问题模型103

6.3.1冲突问题模型103

6.3.2冲突问题研究现状105

6.4覆盖路由之间的交互107

6.5本章小结109第7章多覆盖网络共存环境下的混合交互110

7.1研究背景110

7.2网络模型和问题描述112

7.2.1网络模型112

7.2.2交互目标114

7.3n+1参与者非合作博弈117

7.3.1纳什均衡117

7.3.2静态最优反应算法118

7.3.3动态最优反应算法119

7.41领导者n跟随者斯塔克尔伯格纳什博弈123

7.4.1斯塔克尔伯格纳什均衡124

7.4.2斯塔克尔伯格纳什博弈求解算法125

7.5性能评价126

7.5.1仿真实验126

7.5.2结果分析128

7.6本章小结135第8章混合交互的联盟合作机制136

8.1研究背景136

8.2联盟博弈136

8.2.1联盟目标函数136

8.2.2联盟分配方案137

8.3联盟形式139

8.4性能评价141

8.4.1仿真环境141

8.4.2仿真结果141

8.5本章小结146

参考文献147

1. 深刻剖析了互联网络僵化问题产生的原因，全面介绍了国际国内关于下一代互联网络研究的前沿技术，解决方案及关键技术；

2. 全书从覆盖网络的产生背景、基本原理及应用出发，通过分析现有互联网存在的问题，以及覆盖网络的不足之处，研究了覆盖网络拓扑构建、多路径负载均衡路由、覆盖网无状态多播、以及覆盖路由与底层物理网络流量工程之间目标不一致而导致的路由冲突问题。

3. 全书结构清晰，条理分明，遵循IP网络的运行规律，通过问题抽象、模型构建、算法设计与求解、理论证明、实验验证等一系列严谨的过程，其结论对于下一代互联网的规划与设计具有一定的借鉴意义。

1. 深刻剖析了互联网络僵化问题产生的原因，全面介绍了国际国内关于下一代互联网络研究的前沿技术，解决方案及关键技术；

2. 全书从覆盖网络的产生背景、基本原理及应用出发，通过分析现有互联网存在的问题，以及覆盖网络的不足之处，研究了覆盖网络拓扑构建、多路径负载均衡路由、覆盖网无状态多播、以及覆盖路由与底层物理网络流量工程之间目标不一致而导致的路由冲突问题。

3. 全书结构清晰，条理分明，遵循IP网络的运行规律，通过问题抽象、模型构建、算法设计与求解、理论证明、实验验证等一系列严谨的过程，其结论对于下一代互联网的规划与设计具有一定的借鉴意义。