Subject: [Idr] draft-dickson-idr-second-best-backup-02

From: Brian Dickson <[email-masked]>
Date: Wed, 05 Mar 2008 00:51:18 -0500

Brian Dickson wrote:
> draft-dickson-idr-second-best-backup-01 has been posted to the expected place:
> http://www.ietf.org/internet-drafts/draft-dickson-idr-second-best-backup-01.txt
>
>   

Version -02 will be posted when postings are permitted again, after Philly.

> There have been some rather substantial changes made to parts of it, especially as far as how withdrawals are structured, and matched to updates.
>
> Also, the capabilities have been rolled together, since one type (backup) relies on the other to achieve the goal of preventing wedgies.
>
> For IETF-71, I'll be doing some comparisons between this and other proposals (e.g. the walton add-paths one).
>
> In the meantime, feedback is welcome, although no updates will occur between now and the impending IETF meeting. :-)
>   

I exaggerated a bit, unfortunately.

After some discussions (kudos to Joel Halpern), I've managed to strip a 
lot of unnecessary elements from the proposal, and cleaned up the text.

I think it will be much clearer, and be easier to read or even skim 
over, now.

Because of that, and to be kind to those like myself who read IDs only 
shortly before or during the IETF meetings, I'm posting this to the list.

Please accept my apologies for not doing so sooner, but better a little 
late and much cleaner, is a good way to go IMHO.

(The "backup" stuff has been removed, and will instead be proposed as a 
new "well-known" community value instead.)

Brian Dickson

idr                                                           B. Dickson
Internet-Draft                                       Afilias Canada, Inc
Expires: August 4, 2008                                    February 2008

       Enhanced BGP Capabilities for Exchanging Second-Best Paths
                draft-dickson-idr-second-best-backup-02

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on August 4, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2008).

Dickson                  Expires August 4, 2008                 [Page 1]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Abstract

   This Internet Draft describes an enhanced way to exchange prefix
   information, to permit two copies of a prefix with different paths to
   be announced and withdrawn.

   This negotiated capability facilitates faster local (inter-AS) and
   global (intra-AS) convergence, reduces path-hunting, improves route-
   reflector behaviour, including eliminating persistent oscillations.

   Additional prefix instances have a new optional BGP attribute to
   control path selection.

   Withdrawal of prefixes will require a slight modification to
   disambiguate prefix instances.

   Benefits are seen both when deployed intra-AS, and on inter-AS
   peering.

Dickson                  Expires August 4, 2008                 [Page 2]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Author's Note

   This Internet Draft is intended to result in this draft or a related
   draft(s) being placed on the Standards Track for idr.

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [4].

   Intended Status: Proposed Standard.

Table of Contents

   1.  Background . . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  The Best Path Chaining and the Best Path Tree  . . . . . .  4
     1.2.  The Withdrawal Problem . . . . . . . . . . . . . . . . . .  4
     1.3.  The Uniqueness Property  . . . . . . . . . . . . . . . . .  5
   2.  Proposed Changes . . . . . . . . . . . . . . . . . . . . . . .  6
     2.1.  New Negotiated Option: USE_SECOND_BEST . . . . . . . . . .  6
     2.2.  New Optional Path Attribute: SECOND_BEST . . . . . . . . .  6
     2.3.  New Update Format  . . . . . . . . . . . . . . . . . . . .  7
     2.4.  New Withdraw Format  . . . . . . . . . . . . . . . . . . .  7
   3.  Modifications to BGP Behavior  . . . . . . . . . . . . . . . .  9
     3.1.  Changes to Path Selection Rules  . . . . . . . . . . . . .  9
     3.2.  Second Best - Basic Method . . . . . . . . . . . . . . . . 10
     3.3.  Second Best - Route Reflector  . . . . . . . . . . . . . . 10
     3.4.  Second Best - Inter-AS Hybrid Method . . . . . . . . . . . 10
     3.5.  IBGP vs EBGP . . . . . . . . . . . . . . . . . . . . . . . 10
   4.  Implementation Guidelines  . . . . . . . . . . . . . . . . . . 12
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . . 14
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 15
   7.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
     8.1.  Normative References . . . . . . . . . . . . . . . . . . . 17
     8.2.  Informative References . . . . . . . . . . . . . . . . . . 17
   Appendix A.  Path-Hunting Examples . . . . . . . . . . . . . . . . 18
   Appendix B.  Persistent Oscillation Examples . . . . . . . . . . . 19
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21
   Intellectual Property and Copyright Statements . . . . . . . . . . 22

Dickson                  Expires August 4, 2008                 [Page 3]

Internet-Draft         BGP Second-Best and Back-up         February 2008

1.  Background

   Even when all the best current practises are observed, operational
   problems may be experienced when running a BGP network.

   These include slow convergence due to "path-hunting" and persistant
   oscillations [1].

   Standardization of MRAI timers helps path-hunting, and oscillations
   can be worked around with RFC 5004 [3].

   However, both of these RFCs identify the above issues as needing
   further work.

1.1.  The Best Path Chaining and the Best Path Tree

   In a stable system of BGP speakers, for every given prefix, the
   selected best paths should form a spanning tree.  At each node, the
   best path selected points further up the tree.  The root of the tree
   is the destination, i.e. the originator of the prefix.  The path from
   any leaf to the root forms a "chain" of best paths.

   There are any number of ways that path attributes may be modified
   over time, at arbitrary places in this tree.  When this happens,
   individual segments of the tree may conceptually "stretch" or
   "shrink".  These changes may have no effect on the overall set of
   choices of best path, or they may cause a cascade effect "below" that
   point in the tree, with nodes migrating to new locations in a new
   version of the tree.

   However, each node makes its choice of best path locally, and every
   time a node changes its selection of best path, that change is
   visible to its peers, and may in turn affect their own choice of best
   path.  This propogation of changes is not instantaneous, and owing to
   the non-tree-like nature of the actual connectivity between nodes,
   can and does result in race conditions.

   Depending on connectivity, peering policy, and initial conditions,
   the behavior may border on that of systems best describe through
   chaos theory.  The time to reach a stable state, while generally
   bounded, is often far from fast, not necessarily predictable, and not
   necessarily consistent.

1.2.  The Withdrawal Problem

   Under normal circumstances, a change in attributes for a prefix will
   "flow" along the tree of best paths, without disrupting the structure
   of the tree itself signficantly.  Even when a node selects a new best

Dickson                  Expires August 4, 2008                 [Page 4]

Internet-Draft         BGP Second-Best and Back-up         February 2008

   path (and thus re-attaches itself to the tree in a new location), it
   typically will continue to pass the new attributes along the branch
   of the tree for which it is the root.

   However, under certain circumstances, its choice of new best path,
   requires it to WITHDRAW the prefix from those peers, and effectively
   sever the branch.  It is in the after-effects of this truncation that
   much of the path-hunting behavior gets triggered.

   When a withdrawal effectively severs a branch of the tree, all the
   nodes on the tree will need to find new paths to the root.  The
   problem is, that it takes some time for them to learn this fact.

   In the mean time, the nodes in the severed branch may continue to
   use, and propogate, paths that are technically infeasible.

   The idea is to fast-track the flooding of the infeasibility of paths
   throughout all parts of the tree below a given link, so as to
   minimize the use of infeasible paths.

1.3.  The Uniqueness Property

   Currently, for each prefix, only one path for that prefix is ever
   announced from one peer to another (ignoring Route Reflectors).
   Because of this property, uniqueness, a withdrawal on a prefix does
   not require path information.  This also means that a change of best
   path is accomplished via an update for a prefix with the new path
   information.

   If, however, more than one path for a given prefix were sent, then
   any attempt to withdraw a prefix+path would require some mechanism to
   distinguish between prefix instances.

   In an environment where multiple path announcments per prefix are
   possible, but only one "best" path per prefix is maintained, then two
   steps would be involved in changing the "best" path.  In no
   particular order, that would be the withdrawal of the old prefix+
   path, and the announcement of the new prefix+path.

Dickson                  Expires August 4, 2008                 [Page 5]

Internet-Draft         BGP Second-Best and Back-up         February 2008

2.  Proposed Changes

   What is being proposed is, maintaining a "top two" for each prefix,
   and sending both of these rather than just the "best" path.

   When either of the "top two" becomes infeasible, a withdrawal is
   sent.  If a withdrawal is received, it receives special fast-track
   handling, taking advantage of the "top two" information.  If either
   of the top two is affected by the withdrawal, it is immediately
   flooded to peers without doing a full BGP table walk.

   The supposition is that pruning all infeasible branches, while
   maintaining information on second-best paths, allows for fast removal
   of all best paths which are dependent on infeasible paths, and fast
   reconvergence with pre-computed alternate paths.  It is expected that
   the second-best mechanism should act as a stop-gap until, but not
   actually replace, full BGP table walking to generate a new set of
   "top two" paths.

2.1.  New Negotiated Option: USE_SECOND_BEST

   This is a new BGP Capabilities value, which can be optionally
   included in the capabilities negotiation.  The specific value is a
   code-point to be assigned by IANA.

   When negotiated:

   o  Update messages MUST be in the new format

   o  Updates without any of the new optional attributes are considered
      BEST

   o  For each prefix, at most one of each type (BEST and SECOND_BEST)
      may be sent

2.2.  New Optional Path Attribute: SECOND_BEST

   This is a new BGP Path Attribute type.  It MAY be used only if the
   USE_SECOND_BEST capability has been negotiated.  The type value is a
   new code point to be assigned by IANA.

   This is an Optional, Non-Transitive, Non-Extended, Non-Partial
   attribute.  All the "attr flag bits" (from BGP [2]) are zero.  The
   length is 1, and the value is 1.

Dickson                  Expires August 4, 2008                 [Page 6]

Internet-Draft         BGP Second-Best and Back-up         February 2008

2.3.  New Update Format

   Update messages are identical to existing format, with the exception
   of the new Withdrawal format, and the new optional Path Attribute
   (SECOND_BEST).  If BGP capability USE_SECOND_BEST has been
   negotiated, any Update MAY have a Path Attribute of SECOND_BEST.
   More than one instance of a given prefix, with distinct values of
   Path Attributes, MAY be sent between BGP speakers.

   At most two instances may be sent, specifically one of each
   combination of with/without SECOND_BEST.

   Two prefix paths are considered identical if they differ only in the
   presence or absence of the new attribute.  An Update which contains a
   path which differs from the previous path of that type (BEST or
   SECOND_BEST), will result in the path information for the prefix and
   type being modified.

2.4.  New Withdraw Format

   Since it is no longer possible to identify which instance of an
   prefix is affected by an update containing a withdrawal, a new format
   for Withdrawals is needed.  For simplicity of implementations, this
   consists of two Withdrawal sections, one for each of the types (BEST,
   SECOND_BEST).  They occur in REVERSE order, to simplify state
   transitions if/when a "BEST" path is withdrawn.  Each Withdrawal sub-
   section has the same format as the original Withdrawal section.

         +-----------------------------------------------------+
         |   Withdrawn Routes Length (2 octets)                |
         +-----------------------------------------------------+
         |   Withdrawn Routes (variable)                       |
         +-----------------------------------------------------+
         |   Total Path Attribute Length (2 octets)            |
         +-----------------------------------------------------+
         |   Path Attributes (variable)                        |
         +-----------------------------------------------------+
         |   Network Layer Reachability Information (variable) |
         +-----------------------------------------------------+

                                 Figure 1

   Withdrawn Routes Length:  This 2-octets unsigned integer indicates
      the total length of the Withdrawn Routes field in octets.  Its
      value allows the length of the Network Layer Reachability
      Information field to be determined, as specified below.

Dickson                  Expires August 4, 2008                 [Page 7]

Internet-Draft         BGP Second-Best and Back-up         February 2008

      A value of 0 indicates that no routes are being withdrawn from
      service, and that the WITHDRAWN ROUTES field is not present in
      this UPDATE message.

   Withdrawn Routes Field:  This field now consists of two sub-fields
      and their respective lengths.  The value for Withdrawn Routes
      Length above, must be the sum of the two lengths, plus 4 (the sum
      of the lengths of the Subfield Lengths).

      The format and sequence of the subfields is as follows:

      +----------------------------------------------------------------+
      |   Withdrawn SECOND_BEST Routes Length (2 octets)               |
      +----------------------------------------------------------------+
      |   Withdrawn SECOND_BEST Routes (variable)                      |
      +----------------------------------------------------------------+
      |   Withdrawn BEST Routes Length (2 octets)                      |
      +----------------------------------------------------------------+
      |   Withdrawn BEST Routes (variable)                             |
      +----------------------------------------------------------------+

                                   Figure 2

   Withdrawn Routes Subfield Lengths  These 2-octets unsigned integers
      indicates the total length of their respective Withdrawn Routes
      subfields in octets.

   Withdrawn Routes Subfields:  Each of these is a variable-length field
      that contains a list of IP address prefixes for the routes that
      are being withdrawn from service.  Each IP address prefix is
      encoded as a 2-tuple of the form <length, prefix>, whose fields
      are described below:

                     +---------------------------+
                     |   Length (1 octet)        |
                     +---------------------------+
                     |   Prefix (variable)       |
                     +---------------------------+

Dickson                  Expires August 4, 2008                 [Page 8]

Internet-Draft         BGP Second-Best and Back-up         February 2008

3.  Modifications to BGP Behavior

3.1.  Changes to Path Selection Rules

   The path selection rules for BGP (section 9.1.2.2 of BGP4 [2]) are
   changed as follows:

   o  The following rule is a modification to step (c).

      It MAY only be needed when the node is acting as a Route
      Reflector.  If a node is NOT a Route Reflector, a simplified
      modification (remove any paths marked SECOND_BEST) MAY be used.
      (This modification exists to resolve the Persistent Oscillation
      problem only.)

      The modification to step (c) is:

      Step (c) is first performed INCLUDING paths with SECOND_BEST.

      If, at the end of the first attempt at step (c), only paths with
      SECOND_BEST remain, re-run step (c), this time EXCLUDING the paths
      with SECOND_BEST.

      After this modified version of step (c), the remaining paths MUST
      NOT have the SECOND_BEST attribute.

      In other words, Step (c) MUST remove any SECOND_BEST paths.

   o  The remainder of the usual BGP path selection rules are applied as
      normal

   The path selection rules for "Second Best" path are as follows:

   o  The already-selected "best" path is removed from the set of paths
      to compare

   o  The SECOND_BEST entry for the prefix, from the same in-RIB-SB that
      the "best" path came from, is temporarily promoted to "best".

   o  The same rules are applied as for the "best" path

   o  The selected path is advertised with the attribute SECOND_BEST
      applied

   The prefix instances for consideration of second-best path are the
   REMAINDER of non-SECOND_BEST instances, and the SECOND_BEST instance
   received on the in-RIB from which the best path was selected (if one
   exists).  Only one SECOND_BEST instance received may be considered

Dickson                  Expires August 4, 2008                 [Page 9]

Internet-Draft         BGP Second-Best and Back-up         February 2008

   for the local (and out-RIB) SECOND_BEST path.

3.2.  Second Best - Basic Method

   Once the capabality for doing so has been negotiated between a pair
   of BGP speakers, each sends the best two paths for each prefix.  The
   path information will include the additional SECOND_BEST attribute on
   the second best path.

   When the current "best" path is withdrawn, the withdrawal MAY be
   propogated without having to perform a full BGP table path selection.
   The current "second best" path in the local-RIB is promoted to
   "best".  This is because the alternate candidates have already been
   evaluated and "second-best" has already been selected.

   Whenever an AS consists of a mesh of BGP speakers who have negotiated
   this capability, the withdrawal will propogate through the entire AS.
   This will either have no effect, or with a change in "best" without
   requiring non-local information to choose the new "best" path.

   The second-best path from a neighbor MUST ONLY be considered as a
   candidate for best path, when the previous best path from that
   neighbor is withdrawn.  When this occurs, the path in question is
   promoted to "best" status.

3.3.  Second Best - Route Reflector

   The "best" and "second best" are reflected.  The same mechanism is
   used for determining both best and second-best per prefix.  Updates
   must be reflected whenever the choice of either or both of the "best"
   or "second best" change.  Withdrawals may be propogated immediately.

3.4.  Second Best - Inter-AS Hybrid Method

   When a withdrawal of the current best path is received from a peer
   doing USE_SECOND_BEST, and the rules for sending updates require that
   an update for this prefix be sent to a peer who does not support
   USE_SECOND_BEST, the current second-best instance of the prefix is
   sent to that peer in an Update.  The neighbor does not need the
   withdrawal, since the new path replaces the old path.

3.5.  IBGP vs EBGP

   The same rules apply for EBGP->EBGP, EBGP->IBGP, IBGP->EBGP, and
   IBGP->IBGP.  If a particular peering has had USE_SECOND_BEST
   negotiated, then any update for a particular prefix that results in
   new selection of either or both of best and second-best, the new
   selections (and possible withdrawal of old selections) is sent to the

Dickson                  Expires August 4, 2008                [Page 10]

Internet-Draft         BGP Second-Best and Back-up         February 2008

   appropriate peers.

Dickson                  Expires August 4, 2008                [Page 11]

Internet-Draft         BGP Second-Best and Back-up         February 2008

4.  Implementation Guidelines

   In order to encourage effective implementation schemes, and to
   demonstrate some of the benefits of deployment, here are some
   suggestions for facilitating fast propogation of path changes, which
   are anticipated as improving behavior.  This applies in particular to
   Path Hunting issues.

   In-RIB-SB (many) -> RIB-SB -> out-RIB-SB
                       |   \
                       v    `-> out-RIB (to non-SB peers)
                       RIB -> FIB

   +----------+-------+--------+-----------------|
   |   PREFIX | IN-SB | OUT-SB | *PATH-info-ptr  |
   +----------+-------+--------+-----------------|

                                 Figure 4

   Where IN-SB and OUT-SB are 2-bit fields indicating what the
   SECOND_BEST (SB) state is (BEST, SECOND_BEST).  Valid values for
   IN-SB are "10" and "01"; for OUT-SB, are "00", "10", and "01".  IN-SB
   are the attributes received from a peer.  OUT-SB is non-zero for ONLY
   those prefixes selected for inclusion into the RIB-SB, what the
   corresponding attributes are.

   For example, if all external peers have NOT negotiated SBAB, those
   prefixes would have SB binary values of 10.  Each In-RIB-SB would
   have at most one instance.  And for each prefix, at most one
   In-RIB-SB would be selected as best, and have its corresponding
   OUT-SB set to binary value 10.

   This forward-chaining allows for processing of SB updates to
   determine whether withdrawals need to be flooded to peers, and if so,
   what SBAB attribute to apply to the withdrawals that are flooded.
   This flooding MAY be performed in parallel to normal BGP table update
   processing.

   For clarity, it should be pointed out that:

   o  The process for the step RIB-SB to RIB is "select prefixes marked
      'best'".

   o  The process for the step RIB-SB to out-RIB is also "select
      prefixes marked 'best'".

Dickson                  Expires August 4, 2008                [Page 12]

Internet-Draft         BGP Second-Best and Back-up         February 2008

   o  The process for the step RIB-SB to out-RIB-SB is the same as
      ordinary RIB to out-RIB, except for preservation of SB attributes
      (if any).

Dickson                  Expires August 4, 2008                [Page 13]

Internet-Draft         BGP Second-Best and Back-up         February 2008

5.  Security Considerations

   No additional security considerations beyond those already present in
   BGP are introduced.

Dickson                  Expires August 4, 2008                [Page 14]

Internet-Draft         BGP Second-Best and Back-up         February 2008

6.  IANA Considerations

   IANA will need to assign new code points for BGP Capabilities for
   USE_SECOND_BEST.  IANA will need to assign new code points for BGP
   Attribute Types for SECOND_BEST.

Dickson                  Expires August 4, 2008                [Page 15]

Internet-Draft         BGP Second-Best and Back-up         February 2008

7.  Acknowledgements

   The author wishes to acknowledge the helpful guidance of Joe Abley,
   Tony Li, and Yakhov Rehkter.  The author thanks the following for
   feedback during the review and revision process: Joel M. Halpern,
   Tony Li.  The author also wishes to acknowledge the insight gained
   from his Scottish Deerhound, Skylar, winning a Reserve Best-in-Show.
   (The selection method of "second best" comes from the Reserve system
   used at the group and best-in-show levels of dog shows).

Dickson                  Expires August 4, 2008                [Page 16]

Internet-Draft         BGP Second-Best and Back-up         February 2008

8.  References

8.1.  Normative References

   [1]  McPherson, D., Gill, V., Walton, D., and A. Retana, "Border
        Gateway Protocol (BGP) Persistent Route Oscillation Condition",
        RFC 3345, August 2002.

   [2]  Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4
        (BGP-4)", RFC 4271, January 2006.

   [3]  Chen, E. and S. Sangli, "Avoid BGP Best Path Transitions from
        One External to Another", RFC 5004, September 2007.

8.2.  Informative References

   [4]  Bradner, S., "Key words for use in RFCs to Indicate Requirement
        Levels", BCP 14, RFC 2119, March 1997.

Dickson                  Expires August 4, 2008                [Page 17]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Appendix A.  Path-Hunting Examples

   (These will be included in a subsequent version of this ID.)

Dickson                  Expires August 4, 2008                [Page 18]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Appendix B.  Persistent Oscillation Examples

   Consider the example in Figure 5 where o R1, R2, R3, R4, and R5
   belong to one AS. o R1 is a route reflector with R2 and R3 as its
   clients. o R4 is a route reflector with R5 as its client. o The IGP
   metrics are as listed. o External paths (a), (b), and (c) are as
   described in Figure 6.

   +----+      1      +----+
   | R1 |-------------| R4 |
   +----+             +----+
    |  \                |
    |   \               |
   3|    \ 2            | 6
    |     \             |
    |      \            |
   +----+  +----+     +----+
   | R2 |  | R3 |     | R5 |
   +----+  +----+     +----+
    |        |          |
   (a)      (b)        (c)

                                 Figure 5

   Path    AS_PATH MED
    a       1 3    10
    b       2 3     1
    c       2 3     0

                                 Figure 6

   With the addition of "second best", we have:

   R1 has the following:

   Path    AS_PATH MED IGP-metric
    a       1 3    10   3 (received:best) (best)
    b       2 3     1   2 (received:best)
    c       2 3     0   7 (received:best) (second_best - not sent)

   R4 has the following:

   Path    AS_PATH MED IGP-metric
    a       1 3    10   4 (received:best) (best - not sent)
    c       2 3     0   6 (received: best) (second_best)

Dickson                  Expires August 4, 2008                [Page 19]

Internet-Draft         BGP Second-Best and Back-up         February 2008

   This results in R1 having:

  Path    AS_PATH MED IGP-metric
   a       1 3    10   3 (received:best) (best)
   b       2 3     1   2 (received:best)
   c       2 3     0   7 (received:second_best) (second_best - not sent)

   By including the second_best in the best path calculation, the
   persistent oscillation problem is resolved.

Dickson                  Expires August 4, 2008                [Page 20]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Author's Address

   Brian Dickson
   Afilias Canada, Inc
   4141 Yonge St,
   Suite 204
   North York, ON  M2P 2A8
   Canada

   Email: [email-masked]
   URI:   www.afilias.info

Dickson                  Expires August 4, 2008                [Page 21]

Internet-Draft         BGP Second-Best and Back-up         February 2008

Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   [email-masked].

Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).

Dickson                  Expires August 4, 2008                [Page 22]

_______________________________________________
Idr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/idr

---

From: Pekka Savola <[email-masked]>
Date: Mon, 10 Mar 2008 03:36:36 +0200 (EET)

On Mon, 18 Feb 2008, Iljitsch van Beijnum wrote:
> A while ago I had a short discussion with Robert Raszuk about (the
> lack of) an inter-AS metric, and he asked me to write my idea up in a
> draft. I did. Let me know what you think.

I've read this but I'm not quite sure which problem this is trying to 
solve.  The abstract talks about reducing TE deaggregation, but 
Introduction jumps right into inter-tier1 load-balancing without 
describing how these are related.

The premise in Introduction appears to be that if a tier1 
customer would want to balance (in definition "get closer to 50/50 
tier1 propotion" instead of "80/20") its incoming traffic, a AS_PATH 
prepending is too coarse a tool.

This offers a way to do this, IAC metric allows finer granularity 
balancing and tuning (by the operators in the middle, not the site 
itself, except potentially by proxy using IAC-controlling 
communities). This may be applicable for a customer solely connecting 
to two tier1's (a bad idea as you may end up being hurt by depeering 
politics), but outside of that context, AS_PATH length has only 
limited usefulness -- being overridden by LOCAL_PREF and longest 
prefix matching.

Further, the more difficult TE problem is traffic optimization (e.g. 
finding lowest RTT or least utilized path for source/destination pair) 
not just load balancing.  If this aims to offer tools for 
optimization, I don't see how it achieves that.

As a result I don't yet see if this is worth the trouble. This 
certainly wouldn't have any impact on the number of more specific TE 
routes in the DFZ (because few are caused by inter-tier1 policies) 
which seems to be the implicit motivation based on Abstract.

At the very least, the draft should be much clearer on how this 
approach is supposed to address the deaggregation issues mentioned in 
the Abstract, or if that's not the goal, the abstract should be 
rewritten.

Btw: the spec should define that (and how) a neighboring router checks 
that the {-14,112} +/-operation has happened within acceptable limits. 
The problem of not doing that is mentioned in passing in security 
considerations.

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings
_______________________________________________
Idr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/idr

---

From: Brian Dickson <[email-masked]>
Date: Tue, 18 Mar 2008 11:41:42 -0400

Uli Bornhauser wrote:
> Hi Brian,
>
> I worked with your draft and I have a question regarding the modified 
> step c) (section 3.1.):
>
> You wrote that this step is to be repeated without the SECOND BEST 
> paths, if only SECOND_BESTs remain. In other words, this step is not 
> to be repeated, if at least one path *without* SECOND_BEST attribute 
> is remained.
>

Yes, your interpretation is correct.

> However, right after that you wrote that step c) must remove all 
> SECOND_BEST paths. Well, from my point of view, this does not fit to 
> what you wrote above. Can you explain me what you mean at this point?
>

What that statement is meant for, is an explanation for *why* there is 
the need to repeat the step if only SECOND_BESTs remain (or to rephrase 
in the presence of N'th-bests, if no "best" paths remain).
Which is, that there *must* be a path selected, which was a received 
"best" path, in order to proceed to the next step, or to terminate the 
path selection (i.e. because only one path remains, and it is a received 
"best" path).

Perhaps a better way to word it would be, "must have removed all...".

> Another, perhaps more important point, regarding the question (I read 
> in the IEFT-meetings) how many paths (2 or n) are to be sent: You 
> wrote that the approach you presented eliminates persistent 
> oscillations. Provided that I don't misunderstand you, this is not 
> totally right.
> If you consider Appendix B: Oscillation is avoided by your approach as 
> long as you have one path (path b) which may be selected by R4 as best 
> one, while a path (path c) of R4 is required by R1 to reach a stable 
> routing. Generally spoken for this example, you approach works fine, 
> as long as n paths are announced, provided that R4 may select not more 
> than (n-1) paths as best one. If more than (n-1) may be selected by R4 
> as best one, path c is not announced to R1 and oscillation appears.
>
> I attach an extended example based on your ones where the announcement 
> of two signaling paths does not work anymore. It would require that 
> the first, second, and third best is announced. This example can be 
> extended for each static number of paths which are announced by your 
> approach. Thus, to avoid oscillation certainly, a dynamic number of 
> paths must be announceable, for example as described in the walton-draft.
>

Thank you, that is a very helpful example. Would it be alright if I use 
it in the draft?

> Let me know what you think.
I will definitely be modifying the draft, to incorporate N rather than 
just 2 for the additional paths.

I'll be using most of the walton-draft, as it covers the N-path 
codification quite well.

Thanks,

Brian

---

From: Enke Chen <[email-masked]>
Date: Tue, 18 Mar 2008 09:01:46 -0700

Hi, Brian:

I have several questions below.

Brian Dickson wrote:

[snip]
> I'll be using most of the walton-draft, as it covers the N-path 

Have you asked for permission from the walton-draft authors to "use most 
of the walton-draft", and have you been granted such a permission?

I must be missing something here.  You will be "using most of the 
walton-draft" in your draft to solve a subset of the problem that the 
walton-draft has already covered?

-- Enke

---

From: Brian Dickson <[email-masked]>
Date: Tue, 18 Mar 2008 12:35:40 -0400

Enke Chen wrote:
>> I will definitely be modifying the draft, to incorporate N rather 
>> than just 2 for the additional paths.
>>
> Have you asked for permission from the walton-draft authors to "use 
> most of the walton-draft", and have you been granted such a permission?
>

As I haven't made the changes yet, I haven't asked yet.

I will be asking permissions from all of the authors, including the 
authors of the referenced incorporated work.

However, technically, I would note that such permission is not required. 
See section 7.3 of BCP78.

Please don't jump to any conclusions about my intentions, simply because 
I haven't yet asked. I only just got back from the IETF on the weekend! :-)

I plan on using language very similar to that found in the walton-draft, 
where it acknowledges that it itself was making use of earlier work by 
Chen et al.

This is consistent with IETF WG documents and procedures.

> walton-draft has already covered?
No, I am adding in only the elements of the walton-draft to encode N-way 
rather than 2-way additional paths.
And, I will be modifying those substantively, since they do not encode 
order on the multiple paths.

What my draft covers, is strictly a superset, not a subset, of what 
walton-draft covered.

And notably, there are corner cases that walton-draft does not handle, 
that my draft does.
Specifically, the modified step (c) handles cases which the walton-draft 
would not handle, or where it would select infeasible paths.
(This happens to be a critical part of ensuring that the propagation on 
inter-as additional paths is valid and correct. The walton-draft didn't 
explicitly cover inter-as at all.)

Brian

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 18 Mar 2008 09:53:08 -0700

Hi Brian,

 > What my draft covers, is strictly a superset, not a subset, of what

I am afraid what your draft talks about is not only subset of what 
draft-walton including "incorporated work" has already described, but 
your draft proposes to send additional single path in a new attribute 
which is actually a step back.

The value of your draft could be in the modeled behavior analysis.

I agree with Enke that if you have some suggestions to draft-walton you 
should send them to the authors or to the idr list rather then "use of 
their draft" and issue a new version of draft-dickson-idr-second-best-backup

Cheers,
R.

---

From: Brian Dickson <[email-masked]>
Date: Tue, 18 Mar 2008 13:20:25 -0400

> which is actually a step back.

I was referring to the solution space of the drafts (path hunting vs 
oscillations), not the encoding schemes.
Mine covers path hunting, which necessarily must include work which 
addresses persistent oscillations (as that can trigger persistent path 
hunting!).

And, if you had been following discussion on my draft, you would realize 
that the "step back" will no longer be the case.

But, I suggest you wait for the next version (under a slightly modified 
name due to the removal of "backup") before commenting further.

Thanks,
Brian

---

From: Brian Dickson <[email-masked]>
Date: Tue, 18 Mar 2008 14:21:49 -0400

> most of the walton-draft", and have you been granted such a permission?

Clarification - I was referring to using much of 
draft-walton-bgp-add-paths, not draft-walton-bgp-oscillations-stop.

And by using, I mean creating an encoding scheme that resembles 
add-paths, but with larger scope, and thus looks like a derivative of, 
rather than incorporation of, add-paths.

Brian

---

From: Uli Bornhauser <[email-masked]>
Date: Tue, 18 Mar 2008 23:20:58 +0100

Hello Brian,

Brian Dickson schrieb:
> the need to repeat the step if only SECOND_BESTs remain (or to 
> rephrase in the presence of N'th-bests, if no "best" paths remain).
> path selection (i.e. because only one path remains, and it is a 
> received "best" path).
>
I guess it would be the best to remove this comment at this point. It 
should also be OK if the SECOND_BEST paths are removed after step d), 
e), or f).
>> I attach an extended example based on your ones where the 
>> announcement of two signaling paths does not work anymore. It would 
>> require that the first, second, and third best is announced. This 
>> example can be extended for each static number of paths which are 
>> announced by your approach. Thus, to avoid oscillation certainly, a 
>> dynamic number of paths must be announceable, for example as 
>> described in the walton-draft.
>>
>
> Thank you, that is a very helpful example. Would it be alright if I 
> use it in the draft?
Yes indeed, the intention of the example was to clarify the problem, 
this also holds in a draft.

Another question for the case that covers n paths: Do you want to 
announce the information on each path whether it is the, best, second 
best, third best, ...?
> Brian
Regards

Uli

-- 
______________________________________________________________
Uli Bornhauser                University of Bonn
                              Institute of Computer Science IV
Email: [email-masked]      Roemerstr. 164
Phone: +49 (228) 73 - 4550    D - 53117 Bonn
Fax:   +49 (228) 73 - 4571    Germany