Subject: Re: [Isis-wg] Computing hop by hop routes with wide (TE Draft) metrics

From: Radia Perlman - Boston Center for Networking <[email-masked]>
Date: Thu, 11 Jan 2001 17:49:27 -0500 (EST)

From: Tony Przygienda <[email-masked]>

	a strict mathematical demise of the problem (it's not for the faint of 
	heart looking for a quick fix) that also presents a necessary
	and sufficient algorithm to route loop-free in a mixed scenario has been 
	presented in an infocom'99 paper by Khotimsky et al., "Hop by Hope 
Routing
	in Networks with Overlaid Routing Domains".
	
Tony, do you have a URL for the paper? But better...can you describe
the algorithm? I haven't seen this paper, but I've seen incomprehensible
papers, that often get by all the reviewers because they're embarrassed
to say they didn't understand it. If the paper is too hard to understand,
or the algorithm is too complicated to explain in a fairly short
email message, I'd have doubts about whether it could work. Maybe even
the algorithm would theoretically work, but if implementers can't
understand it, then it's unlikely it can be implemented correctly.

Of course it's simpler not to mix old and new, and even simpler to have
had wide enough metrics in the first place (that's my fault). But
is that really realistic? I suppose if there's no mixing strategy that
allows using wider metrics while there are still old routers around,
then I guess it's really not much better than just saying you have to wait
until all your routers are capable of handling the wide metric, and
then doing a flag day.

Radia

_______________________________________________
Isis-wg mailing list  -  [email-masked]
http://external.juniper.net/mailman/listinfo/isis-wg

---

From: Tony Przygienda <[email-masked]>
Date: Fri, 12 Jan 2001 22:44:38 +0100 (MET)

> 	in Networks with Overlaid Routing Domains".

I fear the paper is copyright infocom so you have to go through them.
Otherwise mail Dr. Khotimsky for a copy: [email-masked] and
[email-masked] could work as well.  I don't have the
newest version handy. 

> understand it, then it's unlikely it can be implemented correctly.

I remember the algorithm was a layered Dijkstra and

1) it assumes that if you're TE, you advertise TE and short-metric always and
        they're both equal.  Short-metricc is infinity if you blow 63.

2) you start by computing first Dijkstra using TE links only. Then you run
   another
   Dijkstra using TE destinations you found and graft short-only links onto
   them to find possible destinations that can be only reached by first
   crossing
   TE links and then short links. You NEVER cross TE links, then short
   links, then
   TE links again because that's not loop-free.
   That all is generalized and can be used for many other things
   beside the TE/short problem and is proven to be loop-free and this condition
   is necessary and sufficient for that. The really
   cute thing is that the optimal paths to destinations do NOT form a tree anymore
   albeit                                                                          
   in every topology Bellman's sub-optimality principle holds. Perplexing to
   me and worth a look by someone looking for  a thesis topic ;-)

3) there is another approachn that Henk & Naiming did for LSP shortcuts. It's in
   an expired draft. I think what they did could be genearlized for the
   TE/short
   mix problem but it's just a feeling.

Don't take my words 100% here, it's a while I worked on that stuff and its
implemetation. As well, stuff may have IP claims tied to it.

Again, my feeling is that before you implemented and deployed a solution for the
TE/short porblem, the problem won't exist so easiest is migrate area by area ;-)

	-- tony