本书重点介绍国防科技大学并行与分布计算课题组一个时期内在分布计算技术领域的研究成果,在某种意义上,也从一个视角反映该领域的技术发展。全书以课题组多年来培养的部分博士生毕业论文为基础,并进行必要的删减整编而成,内容既有网络、操作系统等传统方向,也涉及事务内存、量子计算等新兴方向。
样章试读
目录
- 目录
前言
第1章 基于Kautz图的常量度数高性能覆盖网 1
1.1 研究背景 1
1.2 静态Kautz图与拥塞特性 4
1.2.1 静态Kautz图及其属性 4
1.2.2 常量拥塞 5
1.3 FissionE覆盖网设计 10
1.3.1 拓扑构造 10
1.3.2 资源对象的命名与发布 11
1.3.3 消息路由 13
1.4 动态维护 14
1.4.1 节点加入 14
1.4.2 节点退出 15
1.4.3 并发加入和退出 17
1.4.4 容错路由和动态负载平衡 18
1.5 理论分析 18
1.5.1 邻居关系不变量 19
1.5.2 命名算法有效性 20
1.5.3 路由正确性 22
1.5.4 性能特征 24
1.6 实验评估 25
1.7 本章小结 29
参考文献 29
第2章 移动自组网络中的广播技术 31
2.1 移动白组网络简介 31
2.1.1 基本概念 31
2.1.2 应用背景 32
2.1.3 研究问题 34
2.2 移动白组网络中的广播技术 35
2.2.1 基于洪泛的广播技术 35
2.2.2 基于簇的广播技术 36
2.2.3 基于连通支配集的广播技术 37
2.3 移动白组网络中的广播问题 37
2.3.1 研究假设 37
2.3.2 广播问题分析 38
2.3.3 定义 39
2.3.4 广播冗余 40
2.4 利用冗余信息的广播算法 41
2.4.1 算法描述 41
2.4.2 算法正确性 42
2.4.3 延迟时间的选择 42
2.5 消减冗余的广播协议 43
2.5.1 数据结构与报文格式 43
2.5.2 链路状态监测 44
2.5.3 广播过程 44
2.5.4 协议实现考虑 45
2.5.5 单向链路问题 45
2.6 模拟性能评估 46
2.6.1 模拟设置 46
2.6.2 模拟结果 49
2.7 本章小结 53
参考文献 53
第3章 高效的覆盖网拓扑和路由 55
3.1 概述 55
3.2 相关工作 56
3.2.1 基本概念 56
3.2.2 线图迭代 57
3.3 基本DL迭代 59
3.3.1 拓扑图统一描述机制 59
3.3.2 DL迭代与DL图 60
3.3.3 DL图的基本性质 62
3.4 逻辑点合并与分裂 68
3.4.1 DL+图 68
3.4.2 路由算法 70
3.4.3 DL+图的基本性质 71
3.5 基于DLG变换构建DHT拓扑 73
3.5.1 节点加入 73
3.5.2 节点退出 74
3.5.3 快速处理 75
3.6 模拟评估 75
3.6.1 路由延迟 76
3.6.2 拓扑维护 76
3.7 本章小结 78
参考文献 78
第4章 Crossbar的串行轮询调度技术 79
4.1 大步调度思想 79
4.1.1 多步调度 79
4.1.2 串行轮询 81
4.2 基于大步调度的高效算法——ISP算法 83
4.2.1 ISP算法定义 83
4.2.2 ISP的性能分析 85
4.3 ISP调度器的实现 93
4.3.1 顶层设计 93
4.3.2 子模块设计 95
4.3.3 相关工作比较 97
4.3.4 小结 97
4.4 本章小结 98
参考文献 98
第5章 移动自组网络组密钥生成与更新 99
5.1 概述 99
5.2 问题描述 100
5.2.1 应用分类 100
5.2.2 设计目标与挑战 100
5.2.3 系统模型 101
5.3 分布式组密钥管理框架 102
5.3.1 设计原理 102
5.3.2 基本概念与符号表示 103
5.3.3 信任模型 103
5.3.4 密钥信息部署 104
5.3.5 组密钥的生成 104
5.3.6 分组数据源认证 108
5.3.7 组密钥的一致性 109
5.4 组密钥更新算法 l10
5.4.1 组密钥更新问题 110
5.4.2 分布式组密钥更新算法 114
5.4.3 模拟实现与性能评估 118
5.5 本章小结 123
参考文献 123
第6章 移动自组网络中的数据复制技术 125
6.1 移动白组网络简介 125
6.1.1 基本概念 125
6.1.2 移动白组网络的应用背景 127
6.1.3 移动白组网络的研究领域 127
6.2 移动白组网络环境中的数据复制技术简介 129
6.3 基于分簇的数据复制协议框架 130
6.3.1 问题描述 131
6.3.2 CDRP的设计思路 133
6.3.3 CDRP框架 137
6.4 基于α-稳定路径的分簇算法 142
6.4.1 问题描述 142
6.4.2 基于。稳定路径的分簇算法 145
6.5 模拟与分析 152
6.5.1 模拟实验参数 152
6.5.2 模拟结果 153
6.6 本章小结 155
参考文献 155
第7章 IBGP健壮性拓扑设计问题建模与分析 157
7.1 IBGP招扑的健壮性问题 157
7.2 网络模型和符号定义 158
7.3 IBGP会话失败概率 159
7.3.1 基于IGP平均恢复时间的IBGP会话失败概率计算方法 159
7.3.2 IGP路由恢复时间 160
7.3.3 SFPC_AIRRT的缺陷 160
7.3.4 一种新的IBGP会话故障概率计算方法 161
7.4 种新的IBGP拓扑设计测度 161
7.4.1 已有测度 161
7.4.2 流量损移率:一种新的IBGP拓扑设计测度 163
7.5 冗余路由反射拓扑设计问题 165
7.5.1 问题描述 165
7.5.2 可解条件 165
7.5.3 复杂性分析 166
7.6 路由反射器可冗余及会话约束的IBGP拓扑设计问题 169
7.6.1 路由反射器冗余度和流量损移率关系 169
7.6.2 RR-TS优化的下界 170
7.7 实验分析 170
7.7.1 数据来源 170
7.7.2 搜寻最优的IBGP拓扑 172
7.7.3 模拟实验 173
7.8 本章小结 176
参考文献 176
第8章 域间路由系统动态演化模型研究 177
8.1 相关研究 177
8.1.1 拓扑生成模型 178
8.1.2 动态演化模型 181
8.2 域间路由系统动态演化模型 183
8.2.1 域间路由系统层次分析 184
8.2.2 CMV-HOT定义 185
8.2.3 模型建立 186
8.3 CMV-HOT分析 188
8.3.1 一般情况 190
8.3.2 幂律特性的产生分析 192
8.4 模拟比较 192
8.4.1 评价参数定义 193
8.4.2 结果比较 194
8.4.3 模型总结 199
8.5 利用CMV-HOT分析域间路由系统 201
8.5.1 多宿主 201
8.5.2 AS间的商业关系 203
8.6 本章小结 205
参考文献 205
第9章 虚拟计算环境的内存资源共享技术 207
9.1 概述 207
9.2 相关工作 208
9.2.1 网络内存 208
9.2.2 分布式共享主存 210
9.2.3 异同点分析 211
9.3 系统结构和基本机制 211
9.3.1 研究动机 211
9.3.2 系统结构 214
9.3.3 基本机制 217
9.4 内存资源的按需聚合 220
9.4.1 研究思路 220
9.4.2 聚合模型 221
9.4.3 聚合算法 224
9.5 内存资源的自主协同预取 227
9.5.1 研究思路 227
9.5.2 预取机制 229
9.5.3 预取算法 231
9.6 模拟评估 233
9.6.1 内存密集型应用 233
9.6.2 110密集型应用 235
9.7 本章小结 238
参考文献 239
第10章 基于服务质量感知的副本放置 240
10.1 个体服务质量约束 240
10.2 基于服务质量感知的副本放置问题 242
10.2.1 副本放置基本概念 242
10.2.2 符号与基本定义 242
10.2.3 Griden-CM简化模型 243
10.3 优化创建开销的服务质量感知副本放置方法 244
10.3.1 研究动机 244
10.3.2 矩阵操作 245
10.3.3 矩阵表示 246
10.3.4 基于矩阵操作的副本放置算法MAPA 247
10.3.5 分布式三阶段算法CPI MAPA 249
10.3.6 模拟评估 251
10.4 访问代价优化的副本环方法 255
10.4.1 概述 255
10.4.2 副本环结构 256
10.4.3 基于副本环的qGREP算法 259
10.4.4 qGREP算法模拟评估 261
10.5 本章小结 266
参考文献 266
第11章 基于动态测试用例生成的二进制软件缺陷自动发掘 268
11.1 概述 268
11.2 相关工作 269
11.2.1 动态测试用例生成技术 269
11.2.2 其他软件预发布阶段的相关测试技术 271
11.3 支持测试系统可重定向的元指令集体系结构 273
11.4 基于动态测试用例生成的精确可达路径覆盖方法 275
11.4.1 路径可达性的完备判定理论 276
11.4.2 DBAPC-F方法 281
11.4.3 面向软件可攻击面的DBAPC方法 282
11.5 线性时空复杂度的DBAPC优化方法 286
11.5.1 单赋值污点变换方法 287
11.5.2 TSADAG及其构建 287
11.5.3 目标分支入口条件相干性的路径约束简化方法与理论 292
11.6 Hunter系统与实验分析 293
11.6.1 Hunter系统的体系结构与实现 294
11.6.2 测试目标的选择与缺陷发掘结果 295
11.6.3 Hunter系统中各个功能组件评估 297
11.7 本章小结 298
参考文献 298
第12章 面向NUMA体系结构的事务内存冲突规避方法 300
12.1 简介 300
12.2 相关研究 301
12.2.1 事务内存 301
12.2.2 CC-NUMA体系结构 302
12.3 已有事务内存机制在CC-NUMA机器上的实验分析 303
12.4 NUMA敏感的冲突规避方法PBC 305
12.5 实验结果与分析 308
12.6 本章小结 310
参考文献 310
第13章 图相似性检测的量子算法 312
13.1 最大公共子图检测的量子算法 312
13.1.1 问题重述与相关工作 313
13.1.2 离散量子漫步在图中的特性 315
13.1.3 基于量子漫步的对称性检测 318
13.1.4 算法流程 321
13.1.5 复杂度分析 323
13.1.6 失效性分析 323
13.1.7 算法评测 325
13.2 量子图核函数设计 331
13.2.1 图核定义 331
13.2.2 基于随机漫步的R-convolution图核研究 332
13.2.3 基于量子漫步的图核设计 333
13.2.4 快速迭代计算方法设计与证明 336
13.2.5 改进的量子图核设计 337
13.2.6 复杂度分析 338
13.2.7 性能评测 338
13.3 本章小结 343
参考文献 344