Broadcasting in the Generalized Butterfly Networks

A. Touzene and K. Day (Oman)


Broadcast, Butterfly graph, Cayley graph, Spanning trees, Interconnection networks.


The need for broadcasting or One-to-All broadcast arizes in many parallel or distributed applications. Broadcasting has been studied for many topologies of interconnection networks such as hypercubes, meshes, De Bruijn, star graphs and binary butterfly. In this paper we propose a broadcasting algorithm for the generalized butterfly GBN(d, n) interconnection net works. The generalized butterfly GBN(d, n) has re cently gained some interest as a point-to-point inter connection network rather than the well known multi stage butterfly networks. We consider the GBN(d, n) as a point-to-point interconnection, using store-and forward communication. We propose a broadcasting algorithm for the GBN(d, n), based on a spanning tree of optimal height that avoids data redundancy.

Important Links:

Go Back