Routing Potential Problems

• A number of possible problems can result from the use of certain routing mechanisms in message passing systems. These include deadlock, livelock, and starvation.
• Deadlock; When two messages each hold the resources required by the other in order to move, both messages will be blocked. This is called a deadlock.
• Resources must be allocated in a manner that avoids deadlock. A straightforward, but inefficient, way to solve the deadlock problem is to allow rerouting (maybe discarding) of the messages participating in a deadlock situation.
  • Rerouting of messages gives rise to non-minimal routing, while discarding messages requires that messages be recovered at the source and retransmitted. This preemptive technique leads to long latency and, therefore, is not used by most message passing networks.
  • A more common technique is to avoid the occurrence of deadlock. This can be achieved by ordering network resources and requiring that messages request use of these resources in a strict monotonic order. This restricted way for using network resources prevents the occurrence of circular wait, and hence prevents the occurrence of deadlock.
• Livelock; Livelock describes a situation in which a message keeps going around the network and never reaches its destination.
• It is a phenomenon that results from using adaptive routing algorithms where messages are rerouted in the hope to find another path to their destinations.
• When nodes need to communicate, they inject their messages into the network.
  • A static injection model results when all nodes inject their messages at the same moment, with the network clear of messages.
  • This is to be compared to dynamic injection, according to which nodes can inject their messages at arbitrary times. Livelock can take place if dynamic injection is used. It cannot occur if static injection is used.
• A number of routing policies can be used to avoid livelock. They are based on the following. Let $S$ be a set of priorities that is totally ordered. Whenever a message is injected into the network, some priority is assigned to it. In order to avoid livelock, the following must hold.
  • Messages are routed according to their priorities;
  • Once a message has been injected, only a finite number of messages will be injected with higher or equal priority.
• Starvation; A node is said to suffer from starvation if it has a message to inject into the network but is never allowed to do so.
  • Starvation cannot arise if static injection is used.
  • A number of routing policies can be used in order to avoid starvation taking place.
    • The simplest among them is to allow each node to have its injection queue, where it stores the messages it wants to inject into the network.
    • This queue is considered in the same way as the queues of the incoming links to that node and it competes with them.
    • As long as a fair queue management policy is used, this method prevents starvation from happening.
    • The main disadvantage is that a node with a high message injection rate can slow down all the other nodes in the network.