基于圈积的新型Cayley图互联网络模型

张震 肖文俊 王晓明

doi:10.3969/j.issn.1000-565X.2011.02.026

华南理工大学学报(自然科学版) >

2011 , Vol. 39 >Issue 2: 153 - 158

DOI: https://doi.org/10.3969/j.issn.1000-565X.2011.02.026

计算机科学与技术

基于圈积的新型Cayley图互联网络模型

展开

1．华南理工大学计算机科学与工程学院，广东广州 510006；2．暨南大学计算机科学系，广东广州 510632

张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究

收稿日期: 2010-02-09

修回日期: 2010-10-10

网络出版日期: 2011-01-02

基金资助

国家自然科学基金资助项目(60773083)；广东省科技厅基金资助项目(8151063201000022)；暨南大学中央高校基本科研业务费专项资金资助项目(1 1610307)

收起

A New Type of Cayley Graph Model for Interconnection Networks Based on Wreath Product

Expand

1. The south China university of technology, computer science and engineering college, guangdong guangzhou 510006; 2. Jinan university computer science, guangdong guangzhou 510632

张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究

Received date: 2010-02-09

Revised date: 2010-10-10

Online published: 2011-01-02

Supported by

国家自然科学基金资助项目(60773083)；广东省科技厅基金资助项目(8151063201000022)；暨南大学中央高校基本科研业务费专项资金资助项目(1 1610307)

Fold

摘要

为了构建适合大规模网络结构的模型,文中提出了一种新型Cayley图互联网络模型WG2nm,当n≥3时,其节点度为m＋3,当n=2时,其节点度为m＋2.文中还给出了该网络模型的路由算法,得到了其直径上界为﹂5n/2」,并对该网络模型的嵌入性进行了分析.将WG2nm与其它网络模型进行分析比较,发现WG2nm模型能够以更小的代价构造大规模网络结构.

关键词： 互联网络; Cayley图; 路由算法; 网络直径; 嵌入性

本文引用格式

张震肖文俊王晓明 . 基于圈积的新型Cayley图互联网络模型[J]. 华南理工大学学报(自然科学版), 2011 , 39(2) : 153 -158 . DOI: 10.3969/j.issn.1000-565X.2011.02.026

Abstract

Proposed in this paper is a new type of Cayley graph model for building large-scale interconnection networks,namely WG2mn,whose node degree is m＋3 when n≥3 and is m＋2 when n=2.A routing algorithm for the proposed model is also presented,and the upper bound of the algorithm diameter is deduced as 5n/2」.Moreover,the embedding properties of the model are analyzed.It is found that WG2mn is superior to other network models because it helps to construct large-scale interconnection networks with lower cost.

Key words： interconnection networks; Cayley graph; routing algorithm; network diameter; embeddability

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract