Unlike deadlock, livelocked packets continue to move through the network, but never reach their destination.
This is primarily a concern for non-minimal routing algorithms that can misroute packets.
If there is no guarantee on the maximum number of times a packet may be misrouted, the packet may remain in the network indefinitely.
Dropping flow control techniques can also cause livelock.
If a packet is dropped every time it re-enters the network, it may never reach its destination.
There are two primary techniques for avoiding livelock, deterministic and probabilistic avoidance.
In deterministic avoidance, a small amount of state is added to each packet to ensure its progress.
The state can be a misroute count, which holds the number of times a packet has been misrouted.
Once the count reaches a threshold, no more misrouting is allowed.
This approach is common in non-minimal, adaptive routing.
A similar approach is to store an age-based priority in each packet.
When a conflict between packets occurs, the highest priority (oldest) packet wins.
When used in deflection routing or dropping flow control, a packet will become the highest priority packet in the network after a finite amount of time.
This prevents any more deflections or drops and the packet will proceed directly to its destination.
Probabilistic avoidance prevents livelock by guaranteeing the probability that a packet remains in the network for T cycles approaches zero as T tends to infinity(无穷大).
For example, we might want to avoid livelock in a 2-ary k-mesh with deflection routing and single flit packets.
The maximum number of hops a packet can ever be from its destination is H_max = 2(k−1).
We then write a string for the history of a packet, where t denotes a routing decision toward the destination and d represents a deflection (such as tddtdtt . . .).
If the number of t ’s in the string minus the number of d’s ever exceeds H_max , then we know the packet must have reached its destination.
As long as the probability of a packet routing toward destination is always non-zero, the probability of this occurring approaches one.
Therefore, our network is livelock-free as long as we can always guarantee a non-zero chance of a packet moving toward its destination at each hop.
