论文部分内容阅读
互连网络是各类并行分布式网络计算的关键基础设施。不同的应用系统要求不同性质的互连结构和通信能力,对应于不同类型的网络图的构造设计与评价研究。互连网络的设计需要在高效、稳定和成本之间取得适当的平衡。通过图论方法来研究互连网络的拓扑结构,大都可以归结为网络拓扑性质及其分析评价、网络中的通信问题以及网络映射与模拟这三类带共性的基本问题。根据对互连网络研究及相关应用领域存在问题的洞察分析,本文利用以群论为主的代数图论方法,利用Cayley图、陪集图以及图的同构与同态理论,结合网络图论的其他工具,重点研究了以陪集图和广义二部交换网络为主的互连网络的理论模型、网络拓扑性质、通信算法以及P2P网络应用模型的设计与系统评估方法。论文的主要研究内容及结果包括: 1)为连通正则有向网络建立了基于Sn的陪集图表示模型,建立了两个正则图同构的充要条件及相关自同构群的表示条件,为判定和识别互连网络的同构等价性提供了系统严谨的理论方法;研究了模型和结论在正则有向图的完全着色、扩展de Bruijn网络(LDI网络)的弧着色等方面的应用,为研究相关的并行通信算法提供了有价值的参考方法。2)为蜂巢网络与六度网络构建新型编址方法及建立相关Cayley图和陪集图模型,为相关研究提供了坚实的理论基础,对研究刻划两类网络的拓扑性质,与已经发表的同类模型比较,具有更好的对称性、直观性和便利性。作为应用解决了蜂巢网格的距离公式以及六度环面的直径计算等未解问题,给出了简明高效的最短路径路由算法;为开发六度环面中的最优广播算法提供了可行的构造策略。3)提出并研究了广义二部交换复合网络构建模型GBSN,较相关的几种复合网络更具通用性。揭示了GBSN与一系列著名的互连网络模型的内在联系,包括GBSN与广义OTIS网络的同构等价性;构建了BSN的Cayley图模型和正则Swapped网络的陪集图模型,证明了两者间的同态关系;根据基础网络的拓扑参数计算GBSN的关键拓扑性质,构建了通用的准最短路径路由算法;证明了对基图节点数同为偶数或点数相同的点传递哈密顿图,GBSN也是哈密顿图。4)定义了一类具小世界特征和良好P2P网络性质的新型Cayley图,以此为基础构建了新型P2P覆盖网络模型CayleyCCC,设计了相关的P2P DHT协议,包括路由、节点加入、节点退出等一系列动态对等节点向静态网络的嵌入算法。系统的定量对比评估表明,CayleyCCC相对已知模型具备查询路径短、路由表精简、聚集性高及稳健性好等诸多优势。针对P2P系统性能定量评估选择的评价指标和系统的评估方法,对P2P系统的设计和评估具有重要参考价值。