[Nsi-wg] route selecting (path finding)
Jerry Sobieski
jerry at nordu.net
Wed Aug 19 08:18:18 CDT 2009
Hi all-
First: Looking at Tomohiro's diagram I am reminded of the PNNI routing
protocol where every network element was a member of a group. Each NE
had a routing entity and spoke to its neighbor(s). The routing agents
would dynamically elect a "group node" that would speak for the entire
group. That Group Node would learn by flooding within its group which
of its sub-nodes had connections to external groups and what those
groups' Group Nodes were. And the local GN would establish an
adjacentcy with its neigboring GN and exchange only summarized routing
topology (no intra-group topology.)
The diagrams with NSAs and Coordinators looks exactly like the diagrams
they used in the PNNI standards ( but the names have been changed to
protect the innocent:-) IMO, the PNNI hierarchichal approach to
routing is *very* powerful and addresses many of the scalability issues
associated with link state protocols - which are the optimal means for
Path Computation. I suggest that - *if* the group believes the NSI-WG
must consider routing/path comput protocols, that PNNI is something that
should be looked at more closely.
Second: Why do we (the "NSI" WG) care about path computing
algorithms? IMO, in this regard there are two interface definitions
required: #1) The delegated chain model single domain connection
request, and 2) a topology request. If the user wants to pursue a tree
model service establishment process and do their own PC, they can do it
with a #2 followed by a series of one or more #1s. And *how* they
chose the #1s is up to them - not part of the NSI.
...Now back to my regularly scheduled proposal deadline....
Jerry
Radek Krzywania wrote:
> 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
>
> _______________________________________________
> nsi-wg mailing list
> nsi-wg at ogf.org
> http://www.ogf.org/mailman/listinfo/nsi-wg
>
>
More information about the nsi-wg
mailing list