描述
开 本: 32开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787111753186
编辑推荐
本书内容荣获2022年“CCF优秀博士学位论文激励计划”。
互联网之父、图灵奖获得者Vint Cerf早在RFC 1262（Guideline for Internet Measurement Activities, 1991年）中就指出：“互联网的测量对于其未来的发展、演变以及部署规划至关重要”。网络断层扫描是网络测量的重要技术，其核心思想是利用网络监测节点间端到端的测量数据推测网络内部细粒度的性能和状态。随着通信技术的不断发展和应用服务的日益多样化，网络组成复杂性、拓扑动态性以及通信失效性进一步加剧，使得现有网络测量方法不再适用。
本书面向传统互联网和新型网络生态，围绕基于断层扫描的网络测量理论和关键技术展开深入研究。对于链路是否可测这一网络测量的基本问题，提出了考虑时变拓扑及网络失效下链路可测性的充要判据，同时建立了链路可测性与网络拓扑变化的基本关系，使得在给定监测节点的情况下量化任意形式网络的测量能力成为可能。重点针对网络规模大、动态性强和失效性高的特点，本书首次提出了基于界限值推断的链路与路径测量技术、基于时变拓扑序列与失效分类建模的链路测量技术，显著提高了测量效率，为大规模网络测量的应用与推广奠定了良好的理论基础。研究成果具有重要的产业应用价值。
互联网之父、图灵奖获得者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
推荐序Ⅱ
导师序
摘要
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
前 言
信息技术的不断发展和人们对通信需求的不断增加，催生了各种网络系统和服务。一方面，用户数量的增长使有线IP网络的规模变得越来越庞大，多跳连接成为地理位置分布广泛的主机之间正常通信的基本前提；另一方面，物联网技术和应用的成熟使得物联网设备的数量快速增长。截至2019年年底，全球物联网设备数量达到110亿。为了实现资源受限物联网设备的互联互通，涌现出多种无线多跳数据传输技术。面对这些普遍存在的大规模多跳网络，如何对其进行有效的监控和测量成为亟须解决的关键问题。网络测量为服务提供商与网络管理员提供网络内部细粒度的运行状态信息，是网络管理与优化的基础。
网络断层扫描是一种有效地利用监测节点之间端到端测量数据推测网络内部运行状态的测量技术，具有较低的测量开销，引起了国内外学者的广泛关注和研究。现有网络断层扫描研究工作主要集中于测量网络的所有链路性能指标的确切值，存在实现难度大、测量成本高、可用性差等问题。此外，现有研究工作往往基于固定网络拓扑和可靠网络通信的理想假设，未考虑拓扑变化和链路失效对网络测量的影响。面对大规模多跳网络组成复杂、拓扑频繁变化及通信容易失效的重要特征，现有网络断层扫描方法难以达到预期的效果。为此，本书总结了大规模网络性能测量面临的主要挑战，并针对这些挑战提出了四项关键技术，以构建灵活、高效及稳健的性能测量体系。
（1）基于界限值推断的链路测量技术。本书研究了对网络特定链路（即目标链路）性能界限值的测量问题，在满足应用需求的前提下，通过灵活调整链路性能测量的精确度，降低测量复杂度和测量开销。具体地讲，本书首先提出了一种高效的目标链路性能界限值推断算法，在任意一个给定监测节点和端到端测量数据的网络中快速地计算出所有目标链路最紧的性能界限值（包括最紧上界值和下界值）。基于此，本书进一步提出了一种新监测节点的部署算法，在网络已有监测节点的基础上，通过增加一个新监测节点以最大限度地缩小目标链路性能界限区间，以及通过部署最少监测节点以满足服务提供商与网络管理员对目标链路性能界限区间长度减少量的需求。和现有优秀的方法相比，本书提出的方法大幅度减小了目标链路性能界限区间的总长度并显著减少了监测节点的部署数量。相关工作发表在著名国际会议IEEE INFOCOM 2020上。
（2）基于界限值推断的路径测量技术。本书研究了对网络特定路径（即目标路径）性能界限值的测量问题，以较小的开销实现对网络关键服务端到端性能的测量。具体地讲，本书提出了一种目标路径性能界限值推断算法，基于给定监测节点之间的测量数据，推算出网络所有目标路径最紧的性能界限值。此外，本书提出了一种新监测节点的部署算法，在网络已有监测节点的基础上，通过增加一个新监测节点以最大限度地缩小目标路径性能界限区间，以及通过部署最少监测节点以满足对目标路径性能界限区间长度减少量的需求。和现有方法相比，本书提出的方法大幅度减小了目标路径性能界限区间的长度并减少了监测节点的数量。相关工作发表在著名国际期刊IEEE/ACM Transactions on Networking上。
（3）基于时变拓扑序列的链路测量技术。针对网络拓扑的动态性，本书提出了一种面向时变拓扑的链路性能测量技术。基于对网络连通性的预测，本书设计了一种简洁通用的时变拓扑刻画模型。基于该模型，本书提出了一种预先式监测节点部署算法，便于服务提供商与管理员在网络规划阶段，完成对网络运行阶段性能测量所需监测节点的部署，从而减少监测节点更换的开销并提高测量的稳定性。和现有方法相比，本书提出的方法放宽了对网络拓扑模型的假设，从而能够适应更多实际应用场景的需求。相关工作发表在著名国际会议IEEE ICNP 2017和著名国际期刊IEEE/ACM Transactions on Networking上。
（4）基于失效分类建模的链路测量技术。针对网络通信的易失效性，本书研究了在不同类型的网络失效下链路性能的测量问题。具体地讲，基于网络链路失效的可预测性与不可预测性，本书对链路失效进行了不同形式的建模。基于此，本书提出了多种稳健的监测节点部署算法，利用监测节点之间端到端的测量数据，推算出网络所有非失效链路的性能指标值，包括：①简单的部署算法（联合部署和一次性部署），将现有针对不可预测链路失效的部署算法应用于一组由可预测链路失效生成的拓扑（即预测拓扑）上；②增量部署算法，基于已有监测节点，在一组预测拓扑上依次部署额外的监测节点；③综合部署算法，将监测节点部署问题映射为广义的碰撞集问题以全面考虑所有预测拓扑上监测节点的部署需求。此外，本书提供了一个冗余监测节点的识别和移除算法，进一步提高监测节点部署的性能。和现有方法相比，本书提出的方法在保证链路性能可识别性的同时，能够很好地实现测量开销与时间复杂度的平衡。相关工作发表在国际会议ACM TURC 2017和著名国际期刊IEEE/ACM Transactions on Networking上。
网络断层扫描是一种有效地利用监测节点之间端到端测量数据推测网络内部运行状态的测量技术，具有较低的测量开销，引起了国内外学者的广泛关注和研究。现有网络断层扫描研究工作主要集中于测量网络的所有链路性能指标的确切值，存在实现难度大、测量成本高、可用性差等问题。此外，现有研究工作往往基于固定网络拓扑和可靠网络通信的理想假设，未考虑拓扑变化和链路失效对网络测量的影响。面对大规模多跳网络组成复杂、拓扑频繁变化及通信容易失效的重要特征，现有网络断层扫描方法难以达到预期的效果。为此，本书总结了大规模网络性能测量面临的主要挑战，并针对这些挑战提出了四项关键技术，以构建灵活、高效及稳健的性能测量体系。
（1）基于界限值推断的链路测量技术。本书研究了对网络特定链路（即目标链路）性能界限值的测量问题，在满足应用需求的前提下，通过灵活调整链路性能测量的精确度，降低测量复杂度和测量开销。具体地讲，本书首先提出了一种高效的目标链路性能界限值推断算法，在任意一个给定监测节点和端到端测量数据的网络中快速地计算出所有目标链路最紧的性能界限值（包括最紧上界值和下界值）。基于此，本书进一步提出了一种新监测节点的部署算法，在网络已有监测节点的基础上，通过增加一个新监测节点以最大限度地缩小目标链路性能界限区间，以及通过部署最少监测节点以满足服务提供商与网络管理员对目标链路性能界限区间长度减少量的需求。和现有优秀的方法相比，本书提出的方法大幅度减小了目标链路性能界限区间的总长度并显著减少了监测节点的部署数量。相关工作发表在著名国际会议IEEE INFOCOM 2020上。
（2）基于界限值推断的路径测量技术。本书研究了对网络特定路径（即目标路径）性能界限值的测量问题，以较小的开销实现对网络关键服务端到端性能的测量。具体地讲，本书提出了一种目标路径性能界限值推断算法，基于给定监测节点之间的测量数据，推算出网络所有目标路径最紧的性能界限值。此外，本书提出了一种新监测节点的部署算法，在网络已有监测节点的基础上，通过增加一个新监测节点以最大限度地缩小目标路径性能界限区间，以及通过部署最少监测节点以满足对目标路径性能界限区间长度减少量的需求。和现有方法相比，本书提出的方法大幅度减小了目标路径性能界限区间的长度并减少了监测节点的数量。相关工作发表在著名国际期刊IEEE/ACM Transactions on Networking上。
（3）基于时变拓扑序列的链路测量技术。针对网络拓扑的动态性，本书提出了一种面向时变拓扑的链路性能测量技术。基于对网络连通性的预测，本书设计了一种简洁通用的时变拓扑刻画模型。基于该模型，本书提出了一种预先式监测节点部署算法，便于服务提供商与管理员在网络规划阶段，完成对网络运行阶段性能测量所需监测节点的部署，从而减少监测节点更换的开销并提高测量的稳定性。和现有方法相比，本书提出的方法放宽了对网络拓扑模型的假设，从而能够适应更多实际应用场景的需求。相关工作发表在著名国际会议IEEE ICNP 2017和著名国际期刊IEEE/ACM Transactions on Networking上。
（4）基于失效分类建模的链路测量技术。针对网络通信的易失效性，本书研究了在不同类型的网络失效下链路性能的测量问题。具体地讲，基于网络链路失效的可预测性与不可预测性，本书对链路失效进行了不同形式的建模。基于此，本书提出了多种稳健的监测节点部署算法，利用监测节点之间端到端的测量数据，推算出网络所有非失效链路的性能指标值，包括：①简单的部署算法（联合部署和一次性部署），将现有针对不可预测链路失效的部署算法应用于一组由可预测链路失效生成的拓扑（即预测拓扑）上；②增量部署算法，基于已有监测节点，在一组预测拓扑上依次部署额外的监测节点；③综合部署算法，将监测节点部署问题映射为广义的碰撞集问题以全面考虑所有预测拓扑上监测节点的部署需求。此外，本书提供了一个冗余监测节点的识别和移除算法，进一步提高监测节点部署的性能。和现有方法相比，本书提出的方法在保证链路性能可识别性的同时，能够很好地实现测量开销与时间复杂度的平衡。相关工作发表在国际会议ACM TURC 2017和著名国际期刊IEEE/ACM Transactions on Networking上。
评论
还没有评论。