35
Deadlock
•Deadlock is a condition in which
packets are permanently blocked
•Logically impossible for non-minimal
routers because a packet can always deroute
•Physically,
deadlock is a concern because packets monopolize resources
•Chaos
is deadlock-free by using packet-exchange protocol: A router wanting to
send a
packet must be willing to receive a packet
Invariant -- 1 of the 4 frames is
always available