Heuristic algorithms for adaptive load sharing in local networks

Load sharing algorithms which do not use any control messages are investigated. Four such algorithms are proposed and compared with a well-known algorithm which uses control messages. Under heavy load, the proposed algorithms have superior performance. The first algorithm uses a central controller which has the sole responsibility for determining where a task should be sent. The second algorithm improves upon the first one by replacing a long task transmission to the controller by two short control messages and by reducing the communication bottleneck at the controller. The third algorithm removes the controller completely, having its function performed in each processor without global knowledge. The fourth algorithm improves upon the third algorithm by utilizing global information which is easily available due to the broadcast nature of the network. The algorithms with a central controller perform very well up to about 30 processors, even under heavy load. The second algorithm performs significantly better than the first one. The third algorithm performs surprisingly well even though it uses no global information. The fourth algorithm performs better than the third algorithm, but it does not bring a substantial improvement