The study includes a comparison of three routing strategies with increasing degrees of adaptivity under different workloads. We present both performance advantages and possible drawbacks revealed by the particular routing strategies.

Deterministic routing strategies are attractive because they are cheap and fast to implement. However, possible drawbacks include lower throughput, significantly increased message latency under heavy traffic and high contention for resources in a packet switching fabric. Adaptive routing strategies are more flexible but have an inherently more complex implementation which may result in slower routing. Our goal is to investigate the trade-offs involved in using different routing strategies. This report presents the results of a simulation study designed to answer this question for realistic bursty traffic workloads. In particular we compare deterministic and two forms of adaptive strategies and describe their effects on message latency and fabric throughput. Our results indicate that limited levels of fabric saturation.

We also explore the impact of different message scheduling strategies on the performance of a packet-switched network under bursty traffic conditions and different routing strategies. In particular, we compare such different message scheduling as FIFO, Round Robin and Alpha Scheduling and describe their effects on message latency and fabric throughput. Our results indicate that, with intelligent message scheduling and under bursty traffic with a high volume of short messages, adaptive routing practically does not improve the interconnect performance either in latency or in throughput. These results are achieved with either Round Robin or Alpha scheduling, both of which tend to ``smooth'' the burstiness in traffic.

A new scheduling algorithm, Alpha scheduling, improves the interconnect performance 2-3 times over the results provided by FIFO scheduling.

Related Papers and Reports

• L. Cherkasova, A. Davis, R. Hodgson, V. Kotov, I. Robinson, T. Rokicki: Components of Congestion Control. In Proceedings of 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA'96).

• L. Cherkasova, A. Davis, R. Hodgson, V. Kotov, I. Robinson, T. Rokicki: What Are the Pieces in the Congestion Control Puzzle? HP Laboratories Report No. HPL-96-17, February, 1996.

• L. Cherkasova, A. Davis, V. Kotov, I. Robinson, T. Rokicki: How Much Adaptivity is Required for Bursty Traffic? In Proceedings of Seventh International Conference on Parallel and Distributed Computing, Las-Vegas, October, 1994, pp 208-213.

• L. Cherkasova, A. Davis, V. Kotov, I. Robinson, T. Rokicki: Analysis of Different Routing Strategies Under Bursty Traffic. HP Laboratories Report No. HPL-94-92, October , 1994.

• L. Cherkasova, T. Rokicki: Alpha Message Scheduling for Packet-Switched Interconnects. HP Laboratories Report No. HPL-94-71, August, 1994.

• L. Cherkasova, V. Kotov, T. Rokicki: On The Effects of Message Scheduling for Packet Switching Interconnect Fabric. HP Laboratories Report No. HPL-94-70, August, 1994.