Dead Locks

An ultimate congestion is called Dead Lock.(Also called Lock Up). First IMP cannot proceed until second IMP does something and second IMP cannot proceed because it waits for first IMP to do something. Both IMPs have ground to a complete halt and will stay that way forever.

The simplest lockup can happen with two IMPs. Suppose that IMP A has five buffers, all of which are queued for output to IMP B. Similarly, IMP B has five buffers, all of which are occupied by packets needing to go to IMP A. Neither IMP can accept any incoming packets from the other. They are both stuck. This situation is called direct store-and-forward lockup. The same thing can happen on a larger scale. Each IMP is trying to send to a neighbor, but nobody has any buffers available to receive incoming packets. This situation is called indirect store-and-forward lockup. When an IMP is locked up, all its lines are effectively blocked, including those not involved in the lockup.

Solution for Dead Lock:

A directed graph is constructed with being the nodes of the graph. Arcs connect pairs of buffers (in the same IMP or on adjacent IMPs). The graph is designed in such a way that if packets move from buffer to buffer along the arc, then there is no deadlock.