墙式网孔  

The Wall Mesh

作　　者：陈贵海[1] 谢立[1] 顾庆[1] LAU F.C.M 周能法 

机构地区：[1]南京大学软件新技术国家重点实验室,南京210093 [2]香港大学计算机科学与信息系统系 [3]美国纽约城市大学计算机与信息科学系,纽约布鲁克林11210

出　　处：《计算机学报》2000年第4期374-381,共8页Chinese Journal of Computers

基　　金：国家自然科学基金!(69803005);日本邮电省电信发展局(TAO)

摘　　要：提出了一种新的网孔──墙式网孔．墙式网孔是一种三度网孔，它通过从普通四度网孔的每个节点删去一度而获得．其节点度节省了２５％，但其直径同普通四度网孔几乎一样．它在计算能力上同普通四度网孔是等价的，因为四度同孔可以有效地嵌入到墙式网孔中，其伸张度为３，拥塞度为４．于是所有现存的基于四度同孔的并行算法都可以毫不费力地移植到三度同孔中且只有常数的减速比．墙式网孔可以通过边界节点回卷相连而产生墙式环托，它是点对称的．进一步重新连接删去的一度，便可得到增强型的墙式网孔，它可克服普通网孔固有的缺陷。The wall mesh is a degree-3 mesh obtained from the ordinary degree-4 mesh by deleting one degree from each node. Its node degree is reduced by 25 % while its diameter is almost the same as the degree-4 mesh. It is computationally equivalent to the degree-4 mesh since a degree--4 mesh can be embedded in a wall mesh with dilation 3 and congestion 3. As a result, all existed algorithms on degree-4 meshes can be effortlessly ported to the wall mesh with only constant slowdown. A wall torus can be obtained from a wall mesh,which has the property of node symmetry. This paper suggests several methods to enhance the wall mesh by adding the deleted degree back to each node. It turns out that the enhanced wall mesh has a much better diameter than the degree--4 mesh,and is suitable for some algorithms that might not perform well on ordinary meshes.

关 键 词：互联网络 墙式网孔 路由 广播 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]