基于断层扫描的网络测量关键技术研究

本书内容荣获2022年“CCF优秀博士学位论文激励计划”。
互联网之父、图灵奖获得者Vint Cerf早在RFC 1262（Guideline for Internet Measurement Activities, 1991年）中就指出：“互联网的测量对于其未来的发展、演变以及部署规划至关重要”。网络断层扫描是网络测量的重要技术，其核心思想是利用网络监测节点间端到端的测量数据推测网络内部细粒度的性能和状态。随着通信技术的不断发展和应用服务的日益多样化，网络组成复杂性、拓扑动态性以及通信失效性进一步加剧，使得现有网络测量方法不再适用。
本书面向传统互联网和新型网络生态，围绕基于断层扫描的网络测量理论和关键技术展开深入研究。对于链路是否可测这一网络测量的基本问题，提出了考虑时变拓扑及网络失效下链路可测性的充要判据，同时建立了链路可测性与网络拓扑变化的基本关系，使得在给定监测节点的情况下量化任意形式网络的测量能力成为可能。重点针对网络规模大、动态性强和失效性高的特点，本书首次提出了基于界限值推断的链路与路径测量技术、基于时变拓扑序列与失效分类建模的链路测量技术，显著提高了测量效率，为大规模网络测量的应用与推广奠定了良好的理论基础。研究成果具有重要的产业应用价值。

谁动了我的奶酪？身处互联网浪潮中的我们时常会听到这个疑问。为回答该问题，本书创新性地聚焦于基于断层扫描的网络测量技术，开展了系统深入的研究。书中的模型设计摆脱了现有网络测量技术的单一应用场景和严格前提假设，充分考虑到现代网络通信系统组成复杂、拓扑频繁变化、通信容易失效等重要特征，构建了灵活高效的网络测量技术新体系。本书首先全面分析了网络测量的研究背景和意义，并梳理了该领域的演进历程和研究现状。随后针对网络测量在灵活性、有效性和稳健性等方面日益突出的关键需求，逐一设计了相应的解决方案，并对其进行了详细的理论分析和性能评测。最后介绍了网络测量领域的未来发展趋势，对建立智能普适的网络测量框架进行展望。本书适合具备相关数学、网络基础的研究者和实践者阅读，也可为计算机通信与网络等领域的从业人员和管理人员提供参考。

从书序

推荐序Ⅰ

推荐序Ⅱ

导师序

摘要

ABSTRACT

第1章绪论

1.1研究背景1

1.2研究目的与研究内容8

第2章相关工作

2.1网络测量概述15

2.2精度及粒度固定的网络测量技术19

2.3静态拓扑的网络测量技术25

2.4通信可靠的网络测量技术28

2.5本章小结31

第3章基于界限值推断的链路测量技术

3.1需求与挑战34

3.1.1测量精度与测量开销平衡35

3.1.2链路性能界限值推断37

3.2设计与实现37

3.2.1链路性能界限值的定义38

3.2.2图论相关概念43

3.2.3最紧链路性能界限值推断算法45

3.2.4最紧链路性能界限值推断算法分析55

3.2.5新监测节点的部署算法59

3.2.6新监测节点的部署算法分析68

3.3性能评价69

3.3.1评价方法70

3.3.2链路性能界限紧密性评价72

3.3.3新监测节点部署开销评价74

3.4本章小结75

第4章基于界限值推断的路径测量技术4.1需求与挑战77

4.1.1网络路径监测78

4.1.2路径性能界限值推断78

4.2设计与实现79

4.2.1路径性能界限值的定义80

4.2.2最紧路径性能界限值推断算法84

4.2.3最紧路径性能界限值推断算法分析95

4.2.4新监测节点的部署算法96

4.2.5新监测节点的部署算法分析104

4.3性能评价106

4.3.1评价方法106

4.3.2路径性能界限紧密性评价108

4.3.3新监测节点部署开销评价110

4.4本章小结111

第5章基于时变拓扑序列的链路测量技术

5.1需求与挑战113

5.1.1拓扑动态性114

5.1.2预先式监测节点部署116

5.2设计与实现117

5.2.1时变拓扑刻画模型117

5.2.2预先式监测节点部署算法121

5.2.3预先式监测节点部署算法分析136

5.3性能评价154

5.3.1评价方法154

5.3.2预先式监测节点部署性能评价158

5.3.3监测节点部署算法运行开销162

5.4本章小结164

第6章基于失效分类建模的链路测量技术

6.1需求与挑战166

6.1.1网络通信失效167

6.1.2网络测量稳健性169

6.2设计与实现170

6.2.1链路失效类型的定义171

6.2.2图论相关概念177

6.2.3稳健监测节点部署算法179

6.2.4稳健监测节点部署算法分析190

6.2.5冗余监测节点识别算法195

6.2.6冗余监测节点识别算法分析201

6.3性能评价205

6.3.1评价方法206

6.3.2稳健监测节点部署性能评价207

6.3.3链路失效对网络测量的影响213

6.4本章小结217

第7章总结与展望

7.1全书总结及创新点219

7.2未来的工作221参考文献223

攻读博士学位期间的科研成果235

致谢237

丛书跋240