Re: DPA replacement?

[Tony Bates <[e-mail]>]

 "John G. Scudder" <[e-mail]> writes:
  * A little while ago I was wrestling with the current DPA drafts and figured
  * out the the respective drafts and RFCs (the DPA draft, the DPA usage draft,
  * and RFC 1771) form kind of a contradiction loop.  This seems to stem from
  * the fact that the current DPA draft wants to treat DPA as a global
  * administratively defined metric (which still carries around AS numbers for
  * some reason even though there's not a reasonable way to use them) or maybe

The purpose of the AS number is just for potential debugging use as it
indicates which AS originated ther DPA value. As you state you can see
that we have been back on forth on this issue a few times within the drafts.

  * (it isn't clear) as an arbitrary tag (even though Communities does this
  * just fine).  It's quite clear in either case that the DPA should be used to
  * bias or set localpref.  The usage draft, on the other hand, keeps the
  * earlier idea of making DPA a MED-like metric which is only comparable when
  * the AS part of the DPA matches.  But, RFC 1771 says you can't do elections

Yes this is really our fault for not tidying up the usage draft after
we finalized on making DPA be an influence on LOOCAL_PREF.

  * when biasing or setting localpref.
  * 
  * This got me thinking about what DPA really wants to do and I ended up with
  * the following ideas, which are basically tricks to try to make a global
  * metric useful.  Your feedback is solicited.  Comments from network
  * operators as to the real-world usefulness of any mechanism such as this (or
  * the current DPA draft for that matter) would be particularly interesting.
  * 

This really comes down to trying to give some indication of the range
you want something like DPA to apply within the LOCAL_PREF influence
algorithm. I still need to think about your proposal but at first pass
using LOCAL_PREF as we stated seems to be equally as easy (or hard
depending on your perspective) as calculating the values in your
global metric for the tricky case below.  However, one thing I think
this type of calculation lends itself to is the notion of "scope"
which could well be of use. Need to think about this ore first though.

		--Tony


  * This is still pretty drafty; there are a number of unresolved notes in
  * [square brackets].  Also, I didn't spend any time trying to come up with a
  * clever TLA, this leads to some textual awkwardness where I refer to "the
  * attribute" or "the metric" generically.  Sorry.
  * 
  * --John
  * 
  * 
  * Introduction
  * ------------
  * 
  * The current DPA proposal <draft-ietf-idr-bgp-dpa-05.txt> differs from
  * earlier versions of the document in that it eliminates the requirement that
  * only DPAs with like source ASes be comparable.  This makes the AS# portion
  * of the DPA largely redundant; it also increases the possibility of
  * conflicts in scenarios such as that shown in section 3 of
  * <draft-ietf-idr-dpa-application-02.txt>.
  * 
  * Also, scenarios such as the aforementioned suffer from DPA's inability to
  * select between multiple branching paths.  The application document suggests
  * using Local_Pref to overcome this limitation.  This proposal outlines
  * another approach, involving a globally significant metric which is refined
  * in smaller and smaller increments as it propagates further from its
  * originator.
  * 
  * The proposed algorithm allows the preference of each AS in the path to be
  * reflected in the metric.  Total ordering is preserved in many cases, but
  * see the "Limitations" section for notable exceptions.
  * 
  * Path Attribute
  * --------------
  * 
  * This document proposes an optional transitive path attribute of fixed
  * length.  The attribute is a range of integers represented by a pair <lower,
  * upper>.  Both values are four octet, non-negative integers.  The attribute
  * may be modified by ASes other than the orginator, according to the
  * following algorithm.  The attribute must not be replaced other than
  * according to the following algorithm.  [How about removing it?]
  * 
  * [Originator's AS# could also be included if anyone can think of a good use
  * for it.]
  * 
  * Route Selection Process
  * -----------------------
  * 
  * For the purposes of route selection, <lower> should be considered to be the
  * metric.  Routes with a higher metric should be preferred to routes with a
  * lower metric.  [This could be by biasing the local_pref, or by including
  * the comparison after the local_pref comparison.]  Routes with any metric
  * should be preferred over similar routes without any metric.
  * 
  * Operation
  * ---------
  * 
  * When an AS originates routes for which it wishes to bias upstream selection
  * preference, it should set the metrics according to the following algorithm:
  * 
  * Call the received attribute <rcv_lower, rcv_upper>
  * range = rcv_upper - rcv_lower
  * n = number of distinct preferences with which the route is to be offered
  * p = ordinal preference of the route in question, with the most preferred
  * route having the highest preference, and the least preferred route having
  * preference ordinal 1.  Note that several routes could have the same
  * preference.
  * 
  * For a route with preference p,
  * 
  *         lower = rcv_lower + (p-1) * range/n
  *         upper = rcv_lower +   p   * range/n
  * 
  * When originating a route, rcv_lower is defined as 0 and rcv_upper is
  * defined as 2^32-1.  [Or rcv_lower could be defined as 1; this could be
  * convenient since 0 could be used as a magic cookie meaning "no metric"
  * which would also sort correctly per the rules above.]  Otherwise, when
  * propagating a route, rcv_lower and rcv_upper are taken from the received
  * attribute.
  * 
  * If the AS propagating the route has no wish to bias upstream selection
  * preference, it need not (and should not) modify the attribute.
  * 
  * The intent of this algorithm is to divide the original sender's preference
  * up into a set of non-overlapping ranges whose ordering reflects the
  * preferences of all transit ASes which have such preference.  [But see
  * "Limitations" for cases where ranges can overlap.]
  * 
  * [Hmm, what do we do when we work range sizes all the way down to zero?
  * This won't take long in principle, but in practice we might actually have a
  * low enough diameter to make this a non-issue?]
  * 
  * Example
  * -------
  * 
  * Here is an example, with a comparison to DPA:
  * 
  *         A-------B----------------D----+
  *         |                        |\   |
  *         +-------C--------E-------+ \  |
  *                 |\                  | |
  *                 | -------F----------+ |
  *                 |                     |
  *                 +--------G------------+
  * 
  * Consider A-G to be ASes.  Suppose that A prefers to receive packets via B.
  * Likewise, C prefers to receive packets for A via E over F and F over G.
  * 
  * Using DPAs, A could send DPA <A, 2> to B and <A, 1> to C.  C could send DPA
  * <C, 3> to E, <C, 2> to F and <C, 1> to G.  D would have no way within the
  * context of DPA of choosing between B and E.  This could be fixed using
  * Local_Pref, but the amount of coordination required seems undesirable if
  * another workable option is available.
  * 
  * Using the algorithm above, A would originate two attributes.  To B, it
  * would send <2147483648, 4294967295>.  To C it would send <0, 2147483648>.
  * C would originate three attributes.  To E it would send <1431655765,
  * 2147483648>.  To F it would send <715827883, 1431655765>.  To G it would
  * send <0, 715827883>.  D would then be able to determine the desired
  * ordering (B beats E beats F beats G).
  * 
  * Limitations
  * -----------
  * 
  * This scheme preserves a total ordering on the metric so long as each AS
  * where branching occurs has a preference and thus modifies the attribute
  * (such as in the example).  In the event that a branching occurs with no
  * modification of the preference, followed by a reconvergence of paths, some
  * of the ordering property is lost.  That is, ranges may overlap.  For
  * example:
  * 
  * 	B--------C--------E--------J
  * 	|	 |		   |
  * 	|	 +--------F--------|
  * 	|			   |
  * 	+--------D--------G--------|
  * 		 |		   |
  * 		 +--------H--------+
  * 
  * Suppose B has no preference between C or D, but C prefers E over F, and D
  * prefers G over H.  When J receives B's routes from E, F, G and H it will be
  * able to determine that it should prefer (E or G) over (F or H) but will not
  * be able to determine by examining the metric whether to prefer E or G.
  * 
  * As long as all "primary" paths are up, this behaves as desired, by allowing
  * J to choose whichever preferred path it likes.  However, if one primary
  * path (E, for example) goes down, traffic for B will be "attracted" to the
  * remaining "primary" path (G in this case).  This might not be desirable.
  * 
  * In a similar vein, consider this case, similar to the previous but with the
  * addition of AS K.  D prefers G over H over K:
  * 
  * 	B--------C--------E--------J
  * 	|	 |		   |
  * 	|	 +--------F--------|
  * 	|			   |
  * 	+--------D--------G--------|
  * 		 |		   |
  * 		 |--------H--------|
  * 		 |		   |
  * 		 +--------K--------+
  * 
  * In this case J will prefer (E or G) over (F or H or K).  However, we also
  * now have H preferred over F preferred over K.  This is just an artifact of
  * the algorithm and doesn't really reflect any particular preference of any
  * downstream AS.
  * 
  * --
  * John Scudder                        email:  [e-mail]
  * Internet Engineering Group, LLC     phone:  [phone]
  * 122 S. Main, Suite 280              fax:    [phone]
  * Ann Arbor, MI  41804                www:    http://www.ieng.com
  * 
  *