Hi,
my colleague, sara boulahia, forwarded us your conversation about
shortest path routing.
We (myself, eric gourdin and nicolas michel) worked on this subject and
we have some papers published in conferences (DRCN2000, Networks) and
others submitted to revues (SIAM Discrete maths, and telecommunication
systems).
If you have a set of routing paths (may be multiple paths between a pair
of nodes) and you want to find some link weighs such that all these
paths are shortest paths, then you can solve this problem by linear
programming. In fact, if you take all the weights equal to 0, then all
the paths will be shortest paths !! Of course, this solution is not very
good in practice. However, we showed that we can minimize the number of
weights equal to 0, satisfying the constraint of shortest paths.
If you want your paths to be unique shortest paths, then the problem
becomes more complicated. Of course, the sub-optimality condition which
says that if P(a,b) is the path used between a and b, and if this path
contains two nodes c and d, then P(c,d) has to be the sub-path of P(a,b)
linking c and d. This very intuitive sub-optimality condition is a
neccessary condition to find weights satisfying the uniqueness
constraint. However, this condition is not sufficient for general
graphs: you can find paths satifying the sub-optimality conditions, but
for which it is not possible to compute weights making them unique
shortest paths. two other necessary conditions (more complicated) have
been presented in one of our papers. The good news, is that for cycles,
cactus and some other graphs, the sub-optimality conditionn is also
sufficient to find weights.
Let me sum up what is said above : if you do not carry about the
uniqueness of shortest paths, than there is no any difference between
shortest path routing and any other kind of routing. With uniqueness,
things are more complicated in general.
Regards
Walid
-- Walid Ben Ameur, Phd France Telecom R&D - "Optimization, Architectures and Traffic" laboratory 38-40 rue du General-Leclerc - 92794 Issy les Mx France Tel: +(33) 1 45 29 56 84 Fax : +(33) 1 45 29 60 69 E-mail: walid.benameur@francetelecom.com
This archive was generated by hypermail 2b29 : Mon Aug 04 2003 - 04:10:03 EDT