Nearly optimal one-to-many parallel routing in star networks Conference Paper

abstract

• Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and our algorithm has an optimal time complexity. This result significantly improves the previous known algorithms for the problem. Moreover, the algorithm well illustrates an application of the orthogonal partition of star networks, which was observed by the original inventors of the star networks but seems generally overlooked in the subsequent study. We should also point out that similar problems are already studied for hypercubes and have proven useful in designing efficient and fault tolerant routing algorithms on hypercube networks.

name of conference

• 11th International Parallel Processing Symposium (IPPS '97), 1-5 April 1997, Geneva, Switzerland, Proceedings

authors

• Chen, Jianer

published proceedings

• Proceedings of the International Parallel Processing Symposium, IPPS

author list (cited authors)

• Chen, C. C., & Chen, J.

complete list of authors

• Chen, CC||Chen, J

publication date

• January 1997

published in

• Proceedings of the International Parallel Processing Symposium, IPPS  Journal

start page

• 728

end page

• 733