### Randomized parallel communications on an extension of the omega networkRandomized parallel communications on an extension of the omega network

Access Restriction
Subscribed

 Author Mitra, D. ♦ Cieslak, R. A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known omega networks. Valiant and Aleliunas have demonstrated randomized algorithms, for a certain context which we call nonrenewal, that complete the communication task in time $\textit{O}(log$ $\textit{N})$ with overwhelming probability, where $\textit{N}$ is the number of sources and destinations. Our scheme has advantages because it uses switches of fixed degree, requires no scheduling, and, for the nonrenewal context, is as good in proven performance. The main advantage of our scheme comes when we consider the renewal context in which packets are generated at the sources continually and asynchronously. Our algorithm extends naturally from the nonrenewal context. In the analysis in the renewal context we, first, explicitly identify the maximum traffic intensities in the internal links of the extended omega networks over all source-destination traffic specifications that satisfy loose bounds. Second, the benefits of randomization on the stability of the network are identified. Third, exact results, for certain restricted models for sources and transmission, and approximate analytic results, for quite general models, are derived for the mean delays. These results show that, in the stable regime, the maximum mean time from source to destination is asymptotically proportional to log $\textit{N}.$ Numerical results are presented. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 4 Page Count 23 Starting Page 802 Ending Page 824

#### Open content in new tab

Source: ACM Digital Library