Deadlock Free Minimum Hop Routing Table

[proshno]

Hi Guys,

I'm a student at UT Austin and currently facing critical problem in solving a problem called "Finding Deadlock Free Minimum Hop Routing Table Generation".

In this problem a network topology will be given (as an adjacency list), and the output will be a routing table (adjacency matrix), such that each node can send packet to any other node without causing deadlock and using minimum possible hops.

Example Topology:
1--2
| |
3--4

Corresponding Input Adjacency List:
1 2
1 3
2 4
3 4

Output Adjacency Matrix:

Destination Node
1 2 3 4
Current 1 X 2 3 2 --\
Node 2 1 X 4 4 \ NextHop
3 1 1 X 4 /
4 2 2 3 X --/

Here if the last row were "4 1 2 3 X", it would cause deadlock in the following case:
1 to 4 => 1 > 2 > 4 (2 is blocking)
2 to 3 => 2 > 4 > 3 (4 is blocking)
4 to 1 => 4 > 3 > 1 (3 is blocking)
3 to 2 => 3 > 1 > 2 (1 is blocking)

but the given output routing table gives following:
1 to 4 => 1 > 2 > 4 (2 is blocking)
2 to 3 => 2 > 4 > 3 (4 is blocking)
4 to 1 => 4 > 2 > 1 (2 is blocking)
3 to 2 => 3 > 1 > 2 (1 is blocking)

Here 3 is not blocking, thus there is no deadlock.

This is a very very simple example. The network might be more complex.

I saw Up/Down Routing algorithm which gives deadlock free routing table but not in minimum possible hops.

Can anyone PLEASE :'( suggest me how to solve this problem? some code, implementation, pseudocode would really be very helpful.

Regards,
Arif