Routing for Broadcasting and Multicasting

• There are two types of communication operations in message passing systems,
  • one-to-one (point-to-point or unicast), a node is allowed to communicate a message to only a single destination, which may be its immediate neighbors.
  • collective communications, a number of routing operations are defined under collective communication.
    • Among these, broadcast and multicast are the most widely used.
    • In broadcast, also known as the one-to-all operation, one node sends the same message to all other nodes. Broadcast is mainly used to distribute data from one node to others during computation of a distributed memory program.
    • In multicast, also known as the one-to-many operation, one node sends its messages to $k$ distinct destinations. Multicast has several uses in large-scale multiprocessors, including parallel search algorithms and single program multiple data (SPMD) computation.
• Practical broadcast and multicast routing algorithms must be deadlock-free and should transmit the message to each destination node in as little time and using as short a path as possible.
• One technique to achieve this is to deliver the message along a common path to as many destinations as possible
  • and then replicate the message and forward each copy on a different channel band for a unique set of destination nodes.
  • The path followed by each copy may further branch in this manner until the message is delivered to every destination node.
  • In such a tree-based communication model, the destination set is partitioned at the source and separate copies are sent on one or more outgoing links.
  • A message may be replicated at intermediate nodes and forwarded along multiple outgoing links towards disjoint subsets of destinations.

  Figure 3: Hypercube broadcast tree-based communication.
• Another method to implement a multicast operation uses separate addressing.
  • In this case, a separate copy of the message is sent directly from the source to every destination. Clearly, this is an inefficient technique.
  A hypercube broadcast tree-based nearest-neighbor communication is shown in Fig. 3.