Communication in Parallel Systems

. Efficient communication in networks is a prerequisite to exploit the performance of large parallel systems. For this reason much effort has been done in recent years to develop efficient communication mechanisms. In this paper we survey the foundations and recent developments in designing and analyzing efficient packet routing algorithms. 1 Introduction Communication among the processors of a parallel computer usually requires a large portion of the runtime of a parallel algorithm. These computers are often realized as sparse networks of a large number of processors such that each processor can directly communicate with a few neighbours only. Thus, most of the communication must proceed through intermediate processors. One of the basic problems in this context is to route simultaneously many messages through the network. Telecommunicaton networks, computer networks in companies and universities, or the internet are examples for networks that have to process many communication reques..