论文部分内容阅读
在分布式计算背景下，作者参与的多个项目与在线文档处理、数据备份相关。本人在项目中承担两个任务：改进文档的版本备份算法和优化大文件在广域网中传输。从中产生的两个原创性工作构成了本文的主体内容：快速连续脆弱哈希的理论和应用，BitZigzag覆盖网络技术。
快速连续脆弱哈希刻画了计算机科学理论和工程技术中广泛存在的一类指纹。
在快速连续脆弱哈希的理论层面，包括两方面的内容：快速连续脆弱哈希的构造和实现、快速连续脆弱哈希的冲突概率分析。
在快速连续脆弱哈希的构造和实现中，从一般代数结构的角度统一规划了该类哈希的构造框架。包括三个方面：有限域、有限群、有限环。其中：(1)在有限域中，将MichaelO．Rabin通过有限域上质数阶不可约多项式所产生的指纹推广到有限域上非质数阶不可约多项式所产生的指纹，证明了前者的哈希冲突上界也适用于后者。(2)在有限群中，解决了所有幂2阶Abel群在当代电子计算机的快速运算；对于幂2阶非Abel群，本文也构造了一类特殊的GL群。利用这些幂2阶群的群运算来实现一类串上的快速连续脆弱哈希。(3)在有限环中，通过递推给出了一类快速连续脆弱哈希；其低阶形式就是Adler校验和。
在对快速连续脆弱哈希的哈希冲突分析中，本文将MichaelO．Rabin的理论成果改进和加强了，给出了一个更小的冲突概率上界。现实实验数据例证了本文的理论分析。
在快速连续脆弱哈希的应用层面，也包括两方面的内容：理论应用和工程应用。
理论应用是通过推广串匹配的Karp-Rabin算法，应用快速连续脆弱哈希解决了一种特殊的文本串匹配问题，两个串的顺序抽取公共子串问题(SECS)。工程应用是设计快速同步协议和算法X-Sync来解决宽带网络和云计算环境下文档多版本内容的实时备份和实时检索问题。
总之，通过理论分析和应用示例，加深了对广泛存在的快速连续脆弱哈希的认识。
为了加速大文件在长距离高延迟网络中的传输，BitZigzag(BZ)覆盖网络技术原创性地将地理信息融入P2P的中继路由。
本文首先从Internet体系结构上的角度来解释业已为网络测量界所熟知的长距离大数据文件传输的拥塞假象；traceroute实验结果例证了该解释。并且从方方面面论证了BitZigzag借助P2P优化大文件在长距离高延迟网络中路由中继的合理性：理论基础(Internet AS的分层结构理论)、Internet测量依据(长距离网络的实际物理尺度)、Internet部署依据(信息地理学)、技术可行性(IP地理定位)。
作为BitZigzag的数学基础而提出的球面四边形多尺度分割网，本质上就是一种物联网资源寻址模型。球面上任何一个位置都可以通过极点大区编号PolarID和地理IP地址GeoIP唯一定位。
BitZigzag的基本设计理念主要有5条：区域聚合(地理聚类Peer);散敛播(多径选路、多级中继和多路传输)；分离传输的数据和控制(适应长距离带来的高延迟)；内嵌网络测量(覆盖Internet);公平激励和中层AS(选择中继Peer)。
在BitZigzag覆盖网络中，通过最长GeoIP偶数前缀匹配算法来定位和组织Peer。通过父子关系，逻辑上将所有Peer组织成具有高可扩展性的树状结构；通过局部子图的双连通通信，超级Peer的物理部署克服了树通信的脆弱性；通过引入软链接技术，克服地理分布的不规则性。
BitZigzag引入Internet路由的地理局部性原理：地理局部性原理根据Internet中通信接口的位置信息(AS、GeoIP、PolarID)对通信接口进行聚类，对聚类后的通信接口间的链路性能进行估计。BitZigzag将整个Internet看作一个AS，对其进行多维度测量(位置、区域、跳数、距离、时间)，BitZigzag成为这个超级AS的OSPF。其中的源路由多跳快照式测量在串行化地得到同一条路径上各个链路RTT的同时，又并行化地得到了这些链路的吞吐率。
BitZigzag中的Peer使用动态端口，在同一个端口上同时绑定TCP和UDP两个服务：通过UDP在应用层实现数据的源路由传输，通过TCP收发消息进行Peer间的交互。BitZigzag数据报的传输控制机制，是通过保量算法和保质算法实现的。通信复杂度的理论分析显示BitZigzag的传输控制机制是有效的。BitZigzag的传输控制机制特别适用于高延迟链路，包括那些低速链路。
在流量优化中，BitZigzag通过路分复用不等式(最值排序不等式)保证路径簇的总吞吐率达到最大。
总之，在BitZigzag的设计过程中，由于将地理位置信息引入路由和网络测量，从而在Internet路由体系结构和P2P体系结构领域引入了一些全新的思想方法、策略机制。BitZigzag为利用P2P技术来改造现在越来越僵化的Internet体系结构提供了新的视角思路，为网络测量提供了新的观察维度，为弹性路由提供了新的实现途径。