Adaptive Routing Strategies for Dynamic Applications in Massively Parallel Architectures

Routers in a dynamic environment must efficiently deliver messages without knowledge of an application's process allocation. We've developed an adaptive routing system for a completely dynamic environment. Our system proposes two different strategies, depending on the application's communication patterns. In the first solution, the Hot-Spot Avoiding (HSA) algorithm, each message separately finds the route toward the destination. Even messages exchanged between the same couple of processes follow different, possibly nonminimal, paths. The HSA algorithm uses neighborhood information to choose the node to which the message is forwarded. It limits the number of hops in the source-destination path by reducing the occurrence of loops in it. The second algorithm, Virtual Path (VP), is tailored to long-lasting entities that cooperate intensively by exchanging messages. It achieves efficiency by finding a path at the beginning and following that path for several messages. For performance's sake, this algorithm partially renounces the HSA algorithm's adaptiveness