Congestion Control in Routing Networks.

Multistage routing networks present an attractive cost-effective method of interconnection for medium to large scale multiprocessors. Recent results concerning performance degradation in the presence of hot spots have raised serious questions about the robustness of previous performance estimates for these routing networks. Research to date has focused on a limited class of hot spots - those in which all the hot spot traffic is destined for the same memory address. We consider a more general kind of traffic imbalance - the hot spot traffic may be of arbitrary composition. By taking this more general view, we hope to understand a wider class of traffic imbalances. In this thesis, we define an analytic framework in which to study the problem of performance degradation due to hot spots. We characterize the performance degradation due to these hot spots. This degradation is very severe. We then employ approximate methods to estimate the time to congest the network, and the time to dissipate that congestion. These approximations are validate by extensive simulation of the model. We subsequently propose a solution to prevent performance degradation due to hot spot traffic imbalances.