Loading…

Yet another result on multi-log/sub 2/N networks

One-to-many connection (i.e., multicast) is an important communication primitive used in parallel processing and high-speed switching in order to simultaneously send data from an input to more than one output. We prove that for even (respectively, odd) n, a multi-log/sub 2/N network is strictly nonb...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on communications 1999-09, Vol.47 (9), p.1425-1431
Main Authors: Yeonghwan Tscha, Kyoon-Ha Lee
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:One-to-many connection (i.e., multicast) is an important communication primitive used in parallel processing and high-speed switching in order to simultaneously send data from an input to more than one output. We prove that for even (respectively, odd) n, a multi-log/sub 2/N network is strictly nonblocking for a one-to-many connection traffic if it is designed by vertically stacking at least (/spl delta/n)/4+1((/spl delta//2)(n-1)+1) planes of a log/sub 2/N network together, where N=2/sup n/, /spl delta/=2/sup [n/2]/, and [x] denotes the greatest integer less than or equal to x. We thus give answer to the open problem and introduce yet another strictly nonblocking multicast network. The characterized network has self-routing capability, regular topology, O(2log/sub 2/N+2log/sub 2/(log/sub 2/N)) stages, and fewer crosspoints than the Clos network for N/spl ges/512. We then extend multi log/sub 2/N multicast networks to the fanout restricted nonblocking networks. It turns out that the multi-log/sub 2/N network nonblocking in a strict-sense for a one-to-one connection traffic is also wide-sense nonblocking for a multicast traffic in which the fanout of any connection does not exceed /spl delta/, provided that for even (respectively, odd) n, the fanout capability of each log/sub 2/N network is restricted to stage (n/2)(((n-1)/2)+1) through n-1.
ISSN:0090-6778
1558-0857
DOI:10.1109/26.789678