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

• 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: Communication switching; Communications Society; Computer science; Network topology; Routing; Stacking; Switches; Switching systems; Telecommunication traffic; Unicast
• ISSN: 0090-6778; 1558-0857
• DOI: 10.1109/26.789678

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.