Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Broadcasting on Meshes with Circuit Switched Routing

IP.com Disclosure Number: IPCOM000109910D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Related People

Ho, CT: AUTHOR

Abstract

Disclosed is a new broadcasting algorithm on a mesh with circuit-switched routing. The broadcast algorithm is based on two path-disjoint spanning trees with certain properties. It improves the best previously know broadcast algorithm by about a factor of two.

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

Broadcasting on Meshes with Circuit Switched Routing

      Disclosed is a new broadcasting algorithm on a mesh with
circuit-switched routing.  The broadcast algorithm is based on two
path-disjoint spanning trees with certain properties.  It improves
the best previously know broadcast algorithm by about a factor of
two.

      More specifically, we assume a communication model of one-port,
circuit-switched and XY-routing, such as the base model for the Intel
Delta machine.  Deriving an efficient broadcast algorithm based on
this model can be attained by achieving two main objectives.  One is
to provide two path-disjoint spanning trees rooted at the source node
such that there is no congestion between the two trees and each node
has at most two children over the two trees.  Another objective is to
provide a "good" scheduling, which is a labeling on the tree edges,
such that the largest label (which accounts for the propagation
delay) is minimized.  We provide construction of two path-disjoint
spanning trees with such desirable properties rooted at any given
source node.  Fig. 1 shows an example of the two trees, which are
path-disjoint, on a 4 x 5 mesh.

      Disclosed anonymously.