Subject: Re: [Isis-wg] downstream paths?

From: mike shand <[email-masked]>
Date: Tue, 01 May 2001 09:36:24 +0100

This was another of those things which it was easier to allow to be put in 
there than it was to argue against it. As I recall it was a guy called 
Mikel Silvest (I may have the spelling wrong) who wanted this. We had 
already had to remove the description of the SPF algorithm from the 
normative text into a non-normative appendix (since from an 
interoperability point of view it doesn't matter WHAT the algorithm is, it 
only matters that it gives the same results).

Dave might remember more.

As far as I am aware, nobody has ever attempted to implement this.

Yes, the idea I think was to be able to do better load balancing, but I was 
never convinced it was a good idea.

At 18:31 30/04/2001 -0400, Jeff Learman wrote:

>Radia,
>
>Thanks for the clarification.
>
>Your interpretation matches the only interpretation I have ever
>been able to glean from the spec.  I am at a loss for why anyone
>would bother to do more work to get less optimal routes, other
>than to be able to do load balancing in more circumstances.
>(Whether that kind of LB would actually be a good idea is another
>question.)
>
>I can't answer whether this is implemented in any integrated IS-IS
>implementations, but I will be surprised if it is.  If it was, it
>could not be used in conjunction with reverse path filtering,
>of course.
>
>Regards,
>Jeff
>
>At 03:38 PM 4/30/2001, Radia Perlman - Boston Center for Networking wrote:
> >OK. Reading Jeff Parker's reply I now understand, but perhaps
> >it's worth having a 2nd person explain it.
> >
> >I didn't remember this from IS-IS at all (I assume
> >it got put in by ISO and wasn't in the original DECnet
> >Phase V routing algorithm), but apparently (based on
> >the section quoted by Jeff) you're
> >allowed to forward a packet destined to D to neighbor N even if
> >N isn't on a minimal path from you to D, but instead neighbor N
> >is closer to D than you are. In other words, you have a path through
> >neighbor N1 to D that is of cost 50, and that's your best path.
> >Your cost to neighbor N is, say, 5. N can get to D at a cost of 48.
> >If you forward through N your path will be 53, clearly worse than
> >your path through N1, but since N is closer to D than you (N is
> >48 away, you're 50 away), you're allowed to forward to N.
> >
> >A neighbor closer to D than you is "downstream". So N (as well as N1)
> >would be downstream.
> >
> >The normal Dijkstra calculation wouldn't tell you all neighbors closer
> >to D than you. The only way to get this is to calculate Dijkstra
> >from the point of view of each neighbor. That's why, if you have k
> >neighbors, you'd have to calculate Dijkstra from your own point of
> >view, plus from the point of view of each neighbor (to find out, for
> >each destination, which of your neighbors is closer to the destination
> >than you are).
> >
> >And with multiple metrics, you'd have to multiply the number of Dijkstra
> >calculations by the number of metrics (I never did like the multiple
> >metric thing, especially the way ISO specified it...that you leave out
> >links that don't advertise that metric so you're calculating an "optimal"
> >path based on a subset of the links!).
> >
> >So that explains why the section you quoted says if there are 4
> >metrics, and you want to "calculate downstream paths) i.e., find out
> >which neighbors are closer than you for each destination), you
> >"would execute the algorithm 4 * (number of neighbours +1) times"
> >
> >I always thought the multiple metrics were not worth the extra
> >calculation and configuration (and were actually quite dangerous
> >given how ISO specified it since it's very nonintuitive why you
> >might get really horrible routes if you use any metric that isn't
> >universally supported on every link). I'd think this "calculating
> >downstream paths" would also not be worth the extra computation
> >and storage. Does any IS-IS implementation bother with this
> >"downstream paths" thing?
> >
> >Radia
> >
> >_______________________________________________
> >Isis-wg mailing list  -  [email-masked]
> >http://external.juniper.net/mailman/listinfo/isis-wg
>
>_______________________________________________
>Isis-wg mailing list  -  [email-masked]
>http://external.juniper.net/mailman/listinfo/isis-wg

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

---

From: Dave Katz <[email-masked]>
Date: Tue, 1 May 2001 10:42:34 -0700 (PDT)

In theory I suppose this could be used to provide potentially feasible
"standby" routes that could be quickly plugged in when link failure is
detected locally, thus reducing the black hole period by some nominal
amount, at the cost of additional background calculation.

This kind of scheme is used in EIGRP to determine feasible successors
prior to the failure of the primary path, in order to avoid entering
Active state.  It can also be used for unequal cost load balancing, as
mentioned.  It makes a lot more sense in EIGRP's case, since it takes
no more computation to determine the feasible successors (the
neighbors are already telling you their path cost), and since the cost
of having to find a new path from scratch is relatively high.

--Dave

   X-JNPR-Received-From: outside
   X-Sender: [email-masked]
   X-Mailer: QUALCOMM Windows Eudora Version 4.3.2
   From: mike shand <[email-masked]>
   Cc: Radia Perlman <[email-masked]>, [email-masked],
	   [email-masked]
   References: <[email-masked]>
   Mime-Version: 1.0
   Content-Type: text/plain; charset="us-ascii"; format=flowed
   Sender: [email-masked]
   Errors-To: [email-masked]
   X-BeenThere: [email-masked]
   X-Mailman-Version: 2.0rc1
   Precedence: bulk
   List-Help: <mailto:[email-masked]?subject=help>
   List-Post: <mailto:[email-masked]>
   List-Subscribe: <http://external.juniper.net/mailman/listinfo/isis-wg>,
	   <mailto:[email-masked]?subject=subscribe>
   List-Id: IETF IS-IS working group <isis-wg.external.juniper.net>
   List-Unsubscribe: <http://external.juniper.net/mailman/listinfo/isis-wg>,
	   <mailto:[email-masked]?subject=unsubscribe>
   List-Archive: <http://external.juniper.net/pipermail/isis-wg/>
   Date: Tue, 01 May 2001 09:36:24 +0100

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Tue, 1 May 2001 19:10:03 -0400

Was this idea (of "standby" routes) in anyone's
mind when this text was put in, though?
--
dima.

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Dave Katz
> Sent: Tuesday, May 01, 2001 1:43 PM
> To: [email-masked]
> Cc: [email-masked]; [email-masked]; [email-masked];
> [email-masked]; [email-masked]
> Subject: Re: [Isis-wg] downstream paths?
>
>
>    List-Unsubscribe:
> <http://external.juniper.net/mailman/listinfo/isis-wg>,

---

From: Doug Montgomery <[email-masked]>
Date: Mon, 30 Apr 2001 18:44:52 -0400

Radia,

Of course Dave Oran could do a better job of providing the history, but you
have the basic idea.  Run Dijkstra routed at each of your immediate neighbors
and store forwarding adjacencies for any of them that are closer to the
destination than yourself.

Provides very aggressive load splitting.  A researcher from Denmark (? I can
see the fellow's face, his name escapes me) proposed this in the early days
of ISO standardization.  The rationale at the time involved scenarios in
which one was highly BW constrained and needed to get every drop of load
splitting possible.

I don't think many people other than the author saw the burning need, but on
the other hand, after some analysis, it seemed well specified and workable and
was added as a second algorithm.

I have never seen an implementation of it.

dougm

-- 
+-----------------------------------------------------------------------------+
| Doug Montgomery                 Manager, Internetworking Technologies Group |
| National Institute of Standards and Technology       Email:  [email-masked] |
| Building 820, Room 457                               Voice: +1-301-975-3630 |
| 820 West Diamond Avenue                              Fax:   +1-301-590-0932 |
| Gaithersburg, MD 20899 USA               WWW: http://www.antd.nist.gov/itg/ |
+-----------------------------------------------------------------------------+
_______________________________________________
Isis-wg mailing list  -  [email-masked]
http://external.juniper.net/mailman/listinfo/isis-wg