Browse Prior Art Database

Optimal Multicast Algorithm in Wormhole-Routed Meshes

IP.com Disclosure Number: IPCOM000103978D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 1 page(s) / 25K

Publishing Venue

IBM

Related People

Ho, CT: AUTHOR

Abstract

Disclosed is an optimal algorithm for unicast-based multicast communication on a d-dimensional mesh, where d<=2, with the wormhole-like routing. For a multicast among an arbitrary set of m nodes in a mesh, there is a source node in the set which needs to broadcast a message to every other node in the set. In a mesh with a wormhole-like routing, a point-to-point (unicast) communication can be modeled as one step, regardless of the distance, as long as there is no congestion. For multicast among a set of m nodes, this algorithm performs in a minimal number of steps, i.e., the ceiling of log sub 2 m. Furthermore, the routing guarantees that the messages are routed without congestion even in an asynchronous environment, i.e., regardless of the message latency and receiving node's overhead.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Optimal Multicast Algorithm in Wormhole-Routed Meshes

      Disclosed is an optimal algorithm for unicast-based multicast
communication on a d-dimensional mesh, where d<=2, with the
wormhole-like routing.  For a multicast among an arbitrary set of m
nodes in a mesh, there is a source node in the set which needs to
broadcast a message to every other node in the set.  In a mesh with a
wormhole-like routing, a point-to-point (unicast) communication can
be modeled as one step, regardless of the distance, as long as there
is no congestion.  For multicast among a set of m nodes, this
algorithm performs in a minimal number of steps, i.e., the ceiling of
log sub 2 m. Furthermore, the routing guarantees that the messages
are routed without congestion even in an asynchronous environment,
i.e., regardless of the message latency and receiving node's
overhead.  Previous algorithms either do not guarantee optimality or
assume a synchronous network.  That is they may yield congestion in
an asynchronous network and result in a higher complexity.

Anonymous.