Deadlock Free Minimum Hop Routing Table
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 --\
Node2 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
[1678 byte] By [
proshnoUTa] at [2007-10-3 5:41:33]
AT FIRST....THANK YOU FOR YOUR REPLY!!! :)
> Is deadlock free routing always possible?
The given topology will be strongly connected. I was assuming, for any strongly connected graph, there should be at least one deadlock free routing path for any node to all other node. IS MY ASSPUMTION WRONG?
> Your examples are not very clear.
Sorry for my bad example. However, I'm actually trying to generate deadlock free minimum hop routing table for any multiprocessor network. Each node is a processor and each edge is a bi-directional channel. At the both ends of each channel, there will be receive buffers.
In my example, you may see that deadlock occurs when there is a cycle in the channel dependency graph of a candidate routing table.
does this help anyway? :(
> A more realistic problem would allow packets to be stalled at the current node in case of a deadlock and then allow them to move after the deadlock as passed. Are you allowed to do that?
I'm not sure how it is possible to get rid of deadlock (assuming deadlock detection will not be available, each node will send packet to other node only on the basis of its routing table)?
In my example, all four node are waiting to send their packet to the next node, which are in cycle; routers do not have capability to detect and resolve the deadlock.
Infact, I'm looking a deterministic way to generate the routing table (not adaptive). Here, I can't use virtual channels too.
One way I was thinking the following process:
1. Determining the all-pair-shortest path for the input network topology. (It is highly possibe that thus APSP will contain one or more cycles in its channel dependency graph).
2. Select the node with least degree (incident edges).
3. Simulate all possible paths starting from that node to see if any of them come back to the starting node (meaning a cycle).
4. For a cycle, generate the next possible minimum path between that node and the node after the starting node in that cycle.
5. Update the routing table generated by APSP.
6. Select the node with next least degree and do steps 3-5 util all nodes are done.
Can you suggest me whether it's gonna work?
Thanks
Unless the graph is complete there is always a possibility (albient rare) of contention.
If the graph is complete there is no need for an algorithm like the one you are requesting as
you have a full point to point contention free (and loop free) network. This approach does
not scale very well.
A simpler approach to non-complete graphs is to use something like a crossbar switch.
This takes n inputs and routes each to one of n outputs (i.e. simplifies the problem to a
grid with inputs on the left and outputs on the bottom. There are well behaved
algorithms for solving this problem (its an online problem with requests continually
needing to be rerouted). It can guarentee loop free connections (as one input maps
directly to one output). It can guarentee no contention as long as there is a one to one
mapping between the input requests and the targets they needs to be sent to.
matfud
