[Cst-1b] Deadlock Avoidance Routing

[Leo Dearden]

Martin Harper wrote:
> 
> This is VERY briefly mentioned in DigiComms notes(slide 104) - I can't quite
> work out how deadlock could occur in practice, anyway.

Deadlock (most simple):

Routers A, B. Each has buffer space for one packet. 

Router can send packet on iff there is space for it at the other end.
The important thing is that it isn't allowed to drop packets
deliberately.

Packets x, y. x is going through B via A. y is going through A, via B.

A receives x, B receives y. Both now have full buffers.
A cannot send x 'cos B doesn't have room for it, and similarly,
B cannot send y 'cos A etc...

For more complexity, rings of dependency can be long, bounded only by
the number of participating routers.

If you want more detail a search for "Deadlock Avoidance Routing" on
Google seems pretty fertile. The first page of results yields 
http://www.cs.wisc.edu/~tvrdik/8/html/Section8.html#AAAAADeadlock
avoidance theory

which is fairly technical, and shows that the subject is of significant
complexity. Probably why the notes are so inadequate. :)
	
Leo.