[Nsi-wg] route selecting (path finding)

[Radek Krzywania]

Hi Tomohiro,
According to your slides, it seems that pathfinder finds all/multiple
inter-domain paths at once. If I am wrong, you may ignore the rest of this
email ;) If I am right, and pathfinder is about to result in more than one
path, then my experience is that this is quite difficult to implement. The
issues are as follows:
- you need to define how many paths will be returned (e.g. why 5, not 6 or
100), otherwise you will find all of them, which may be thousands.
- Algorithms for graph searching allows you to find one path (e.g. Dijkstra)
or all paths (some graphs searching algorithm). There are some k-Dijkstra
algorithms but they relay on some constraints which we may not accept.
- if you found first path, what are the constraints for the second one?
Avoid all links from the first path, don't use one of the link on the path
(then which one should be avoided), etc. Guessing which links should be
avoided for n-th search is IMHO not the most optimal way of doing that. You
can always remove the most crowded links, but still, you don't know why the
previous (e.g. 1st) path will be refused, so you have no guarantee the next
one (e.g. 2nd) will be optimal in this particular case.

Searching multiple path makes the pathfinding process more complex and
includes some decision mechanisms. Thus I have a question if we are going to
get into it. In AutoBAHN we did it simple - we use Dijkstra to find a sigle
path. If it fails for some reason, we know where (e.g. insufficient
bandwidth on link x or domain y refused the reservation). We temporary
remove x or y from topology and run Dijkstra once again. So we have
alternative path, which is expected to be still optimal (according to
current network condition on x and y). AutoBAHN interface for pathfinder
allows to get multiple path, just in case. But this feature is not used in
practice due to implementation complexity.

Best regards
Radek

-----Original Message-----
From: nsi-wg-bounces at ogf.org [mailto:nsi-wg-bounces at ogf.org] On Behalf Of
Tomohiro Kudoh
Sent: Wednesday, August 19, 2009 1:44 PM
To: NSI WG
Subject: [Nsi-wg] route selecting (path finding)

Hi all,

Attached slide shows my view of route selectiong (path finding) wrt NSI.

I am sorry but I must leave today's call at around 10am EDT.

Tomohiro