Techniques for high-bandwidth, low-latency interconnection network operation at high offered loads

While there are a number of techniques that have enhanced interconnection network performance significantly, known performance problems due to network saturation at high offered loads that result in poor bandwidth and high latencies continue to pose a challenge to system designers. The symptoms of the problems are as follows: the achieved throughput goes up with offered load steadily till a certain point beyond which there is a sudden and significant drop in throughput (and a corresponding increase in latency). This occurs due to imbalances in network resource usage as well as the lack of fast feedback resulting in routers making decisions using only locally available information that may be globally detrimental.; Solutions to this problem can be broadly classified into two categories: (a) congestion control solutions and (b) load balancing solutions. This thesis proposes and evaluates one congestion control technique and two load balancing techniques to overcome the performance problems in k-ary, n-cube networks at high loads.; The first technique is a self-tuned congestion control mechanism— Tune—that has two key features: (a) it uses global congestion information to throttle the offered load when saturation is imminent and thus ensures that the network stays in the high-bandwidth, low latency region of operation and (b) it has a global throughput-driven self-tuning mechanism that enables it to adapt to various communication patterns. Simulations with various communication patterns show that Tune is able to prevent the sudden drop in performance that occurs at saturation. Tune can be used with both wormhole and virtual cut-through switched networks.; The second technique—congestion-aware via routing—attempts to achieve load balancing to prevent saturation. In this technique, packets are directed away from congested network regions using global congestion information by requiring them to go via certain intermediate nodes. I demonstrate that this technique achieves limited improvements for non-uniform traffic patterns. Simulations show that the benefits of congestion aware via-routing , even with perfect global knowledge, are not compelling.; Finally, I propose a new non-minimal routing (i.e. packets can be routed on hops that take them farther from the destination) algorithm— BLAM—that goes beyond the constraints of minimal routing which I assumed for the first two techniques. (Abstract shortened by UMI.)...