HP Labs Technical Reports

On the Effects of Message Scheduling for Packet Switching Interconnect Fabric

Cherkasova, Ludmila; Kotov, Vadim; Rokicki, Tomas

HPL-94-70

Keyword(s):

Abstract: This report explores the impact of different message scheduling strategies on the performance of a packet-switched network under bursty traffic conditions and different 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. Adaptive routing strategies are more flexible but inherently more complex which may result in slower routing. We investigate the trade-offs involved in using dif- ferent routing strategies while intelligently scheduling the packets from various messages for injection into the interconnect. This paper 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 under three different message scheduling algorithms: FIFO, Round Robin and Alpha scheduling. Our results indicate that for some types of bursty traffic with high volume of short messages, adaptive routing does not improve the interconnect performance, either in latency or in throughput. These performance results can be achieved by using either Round Robin or Alpha scheduling, which both tend to smooth traffic burstiness.

Back to Index