Premium
Circuit‐switched row‐column broadcasting in torus and mesh networks
Author(s) -
Lee Park JuYoung,
Choi HyeongAh
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199603)27:2<159::aid-net7>3.0.co;2-j
Subject(s) - torus , broadcasting (networking) , upper and lower bounds , computer science , grid network , topology (electrical circuits) , path (computing) , algorithm , mathematics , combinatorics , computer network , geometry , mathematical analysis , grid
This paper is concerned with broadcasting on 2‐dimensional torus and mesh networks using circuit‐switched, half‐duplex, and link‐bound communication. It is assumed that there are α and β physical channels in the X ‐ and Y ‐dimensions, respectively, and path selection between any two nodes is done using row‐column routing. Given an n × n mesh or torus, we first discuss the lower bounds of broadcasting time; any broadcasting algorithm requires at least [log (2α + 2β + 1) n 2 ] time steps and no broadcasting algorithm achieves this lower bound if α < β(2β + 1). We then show that broadcasting on a (2α + 2β + 1) p × (2α + 2β + 1) p torus can be done in 2 p time steps, which is optimum, for any α ≥ 3 and β = 1. We also present approximation algorithms for the cases of mesh when α ≥ 1 and β = 1 and torus when α ≤ 2 and β = 1. © 1996 John Wiley & Sons, Inc.