On the Topological Properties of Grid-Based Interconnection Networks: Surface Area and Volume of Radial Spheres

Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) an...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2011-05, Vol.54 (5), p.726-737
Main Authors: Sarbazi-Azad, H., Khonsari, A., Ould-Khaoua, M.
Format: Article
Language:English
Subjects:
Computer networks
Network topologies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) and with boundary wrap-around (tori). In particular, we study the problem of finding the number of nodes located at/within a given distance from a given node (surface area/volume) in the network and derive some expressions for computing such a number. Furthermore, we provide similar expressions that improve on previous results already reported in the literature for some special cases of grids, notably hypercubes and k-ary n-cubes. We also show some applications of the derived expressions in analytical performance modelling of some grid-based networks under uniform and hotspot traffic loads. [PUBLICATION ABSTRACT]
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxq011