Subject: [rrg] FYI: Architectural Implications of Locator/ID Separation

From: David Meyer <[email-masked]>
Date: Mon, 8 Dec 2008 14:44:07 -0800

Just posted this to the internet-drafts repository, but
	here's an early look. 

	As always, comments greatly appreciated.

	Dave

--

Network Working Group                                           D. Meyer
Internet-Draft                                                  D. Lewis
Intended status: Informational                                     Cisco
Expires: June 11, 2009                                  December 8, 2008

          Architectural Implications of Locator/ID Separation
                 draft-meyer-loc-id-implications-00.txt

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 June 11, 2009.

Abstract

   Recent work on Locator/ID Separation has focused primarily on the
   control plane protocols concerned with finding Identifier-to-Locator
   mappings.  However, experience gained with a trial deployment of a
   system designed to implement Locator/ID Separation has revealed two
   general classes of problems which must be resolved after the mapping
   is found: The Locator Path Liveness Problem and the State
   Synchronization Problem.  These problems have implications for the
   data plane as well as the control plane.

Meyer & Lewis             Expires June 11, 2009                 [Page 1]

Internet-Draft          Loc/ID Split Implications          December 2008

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  The Problem Space  . . . . . . . . . . . . . . . . . . . . . .  4
   3.  The Locator Path Liveness Problem  . . . . . . . . . . . . . .  4
     3.1.  Complexity . . . . . . . . . . . . . . . . . . . . . . . .  6
       3.1.1.  Complexity of Host-Based Probing . . . . . . . . . . .  7
       3.1.2.  Complexity of Network-Based Probing  . . . . . . . . .  7
     3.2.  Possible Optimizations . . . . . . . . . . . . . . . . . .  7
     3.3.  Security Issues  . . . . . . . . . . . . . . . . . . . . .  9
   4.  Site-Based State Synchronization . . . . . . . . . . . . . . . 10
     4.1.  Complexity . . . . . . . . . . . . . . . . . . . . . . . . 11
   5.  Conclusions  . . . . . . . . . . . . . . . . . . . . . . . . . 11
   6.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 11
   7.  IANA Considersations . . . . . . . . . . . . . . . . . . . . . 11
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     8.1.  Normative References . . . . . . . . . . . . . . . . . . . 11
     8.2.  Informative References . . . . . . . . . . . . . . . . . . 13
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13
   Intellectual Property and Copyright Statements . . . . . . . . . . 14

Meyer & Lewis             Expires June 11, 2009                 [Page 2]

Internet-Draft          Loc/ID Split Implications          December 2008

1.  Introduction

   Locator/ID Separation (hereafter Loc/ID split) has been proposed as
   an architectural enhancement to the Internet architecture to
   facilitate, among other things, scaling of the global routing system
   [RFC1498][Chiappa99][Fuller06][RFC4984].  The basic idea is that the
   current number space (the IPv4/IPv6 address space) is overloaded with
   both location and identity semantics.  One consequence of this
   overloading is that it is difficult to assign routing locators
   (RLOCs) in a way that is congruent with the underlying network
   topology; this makes aggregation difficult (if not impossible).  This
   property is sometimes referred to as Rekhter's Law, and is frequently
   formulated as follows:

     "Addressing can follow topology or topology can follow
      addressing. Choose one."

   Endpoint Identifiers (EIDs), on the other hand, are typically
   assigned without regard to the underlying network topology (e.g.,
   Host Identity Tags [RFC4423]).  This makes it difficult for a single
   numbering space to efficiently serve the routing locator and endpoint
   identifier roles.

   Locator/Identity Separation can be used to decouple the allocation of
   of EIDs from RLOCs, enabling the RLOC space to be aggressively
   aggregated (i.e., by aligning RLOC allocations with the underlying
   network topology).  The positive effect of such aggregation would be
   to control the growth of global routing state (note that aggregation
   in the EID space may also an issue, but as of this writing hasn't
   been extensively explored).

   Recent work on Locator/ID Separation has focused almost exclusively
   on control plane protocols for finding Identifier-to-Locator mappings
   (for example, [I-D.fuller-lisp-alt][I-D.jen-apt]
   [I-D.lear-lisp-nerd]).  However, experience gained with a trial
   deployment of a system designed to implement Locator/ID Separation
   has revealed two general classes of problems which must be resolved
   after the mapping is found: The Locator Path Liveness Problem and the
   State Synchronization Problem.  These problems have implications for
   the data plane as well as the control plane.

   This document focuses on the Locator Path Liveness and State
   Synchronization problems, and is organized as follows: Section 2
   provides an overview of the problem space.  Section 3 discusses the
   Locator Path Liveness problem, and Section 4 discusses the State
   Synchronization problem.  Finally, Section 5 provides a few
   conclusions.

Meyer & Lewis             Expires June 11, 2009                 [Page 3]

Internet-Draft          Loc/ID Split Implications          December 2008

2.  The Problem Space

   Decoupling Location and Identity has profound implications both the
   control and data planes.  In particular, decoupling location from
   identity leads to the two difficult problems: First, give a set of
   source locators and a set of destination locators, it must be
   possible to determine whether a particular destination locator is
   reachable.  We refer to this general problem as the Locator Path
   Liveness Problem.  The Locator Path Liveness Problem is exhibited in
   host-based architectures such as SHIM6 [I-D.ietf-shim6-proto]) and
   network-based architectures such as eFIT [EFIT] and [LISP]).  The
   "Hybrid Rewriting" class of architectures (e.g., ,GSE [ODell97])
   exhibit a slight variant on the problem.  Locator Liveness is
   discussed in Section 3.

   The second problem is that mapping state may need to be shared among
   network elements (this is as opposed to the determining if the
   locator itself is up or down).  This is referred to as the Site-Based
   State Synchronization Problem, and is specific to network-based
   architectures.  The Site-Based State Synchronization problem is
   discussed in Section 4.

3.  The Locator Path Liveness Problem

   The Locator Path Liveness Problem can be stated as follows:

     Given a set of source locators and a set of destination
     locators, can bidirectional connectivity be determined between
     the <source locator,destination locator> address pairs?

   A simple example illustrates the problem: Consider the scenario
   depicted in Figure 1.  Here a site S0 is multihomed to provider A and
   provider B. Further, suppose that S0 has a Provider Assigned (PA)
   locator from provider A (call it La) and a PA locator, Lb, from
   provider B. Suppose that provider A peers with provider B. In this
   case, S0 might "advertise" that its EID-prefixes can be reached
   through nodes La and Lb (either via DNS, explicit protocol message
   such as a Map-Reply message [LISP], or other method) to its
   correspondent sites.

   Now, suppose that a correspondent site S1 is connected to provider C,
   and that S0 has told S1 that it can reach S0 on either La or Lb.
   Suppose further that S1 chooses La to reach S0, so that packets
   sourced from S1 destined for S0 traverse the path S1->C->B->A->S0.
   Note that if connectivity between provider B and provider A is
   disrupted (for either business or technical reasons), La will not be
   reachable from S1.  In this case, S1 must detect that La is no longer

Meyer & Lewis             Expires June 11, 2009                 [Page 4]

Internet-Draft          Loc/ID Split Implications          December 2008

   reachable and use Lb to restore connectivity (in the event that S1
   wants to restore connectivity; in today's Internet, would S0 would
   continue to be unreachable).

                                          S1
                                           |
                                           |
                                           C
                                           |
                                           |
                         A-----------------B
                          \  peering link /
                           \             /
                            \           /
                             \         /
                              \       /
                              La    Lb
                                \  /
                                 S0

                      Figure 1: Reachibility Failure

   The Locator Path Liveness problem arises in subtly different ways,
   depending on the contents of the mapping database (i.e., EIDs, RLOCs,
   or some combination of these), who queries the database (host or
   network element), and how knowledge is distributed between hosts and
   routing.  Note that in general, Locator Path Liveness must be tested
   in the data plane (although an implementation might take advantage of
   various "hints; see Section 3.2).

   Host-Based Architectures:  In host-based architectures (e.g., SHIM6
      [I-D.ietf-shim6-proto]), the problem arises because queries to the
      database (DNS in this case) return "addresses" which can be
      thought of as a concatenation of the RLOC and EID.  Since a host
      is anticipated to have multiple such "addresses" (at least in the
      SHIM6 case), it must choose a working <source,destination> pair
      from among its potential source addresses and its correspondent
      destination addresses.  REAP [I-D.ietf-shim6-failure-detection] is
      a probe-based reachability protocol which is designed to address
      this problem.

   Hybrid Network-Based Rewriting Archtectures:  In hybrid network-based
      rewriting architectures (e.g., GSE [ODell97]), the problem arises
      because there is a knowledge asymmetry between the host and
      routing.  Specifically, while the host is responsible for
      selecting the destination Routing Goop (RG) (i.e., the ingress
      point to the destination domain, essentially the destination
      RLOC), it is routing that selects the source RG.  So while the IGP

Meyer & Lewis             Expires June 11, 2009                 [Page 5]

Internet-Draft          Loc/ID Split Implications          December 2008

      routing in a domain can be intelligent about egress points from
      the domain, it is the destination address, chosen by the host,
      that selects the ingress point in the destination domain.  However
      it is routing, and not the host, that knows if the destination is
      reachable or not.  Section 4.2 of [Zhang06] discusses this issue
      from a slightly different point of view.

      This asymmetry gives rise to the following problem: Hosts will
      likely want information, at some granularity, about which
      <source,destination> pairs currently work.  However, the host has
      no information about how many RGs are available to the site or if
      they are currently reachable.  So the host can not test the set of
      <source,destination> pairs for active paths.  On the other hand,
      the routing can't either, unless it snoops on TCP connections
      (which doesn't deal with asymmetric paths, UDP flows, or
      unidirectional flows).

      It is worth noting that unlike most "modern" descriptions of how
      GSE uses the DNS (e.g., [Zhang06]), the original GSE design
      [ODell97][ODell08] envisioned that the DNS would have a new
      resource record type, the RG record, to carry a site's RGs.  Hosts
      would only have AAAA records.  The idea was that for a given
      destination domain, a host in the source domain would compute the
      Cartesian Product {RGs}x{A4s}.  Thus alternate path sensing would
      become a a matter of local policy, and not hard-wired by the
      destination domain (or whoever happens to be authoritative for the
      destination domain's names).  Notice however that even the
      introduction of the RG resource record, the knowledge asymmetry
      remains.

   Network-Based Map-and-Encap Archtectures:  In the case of map-and-
      encap network-based architectures, the problem arises because the
      mapping element (e.g., Ingress Tunnel Router, or ITR) must choose
      among the RLOCs it has learned for a given EID-prefix.  Here since
      the ITR holds the mappings that knows the set of possible remote
      "addresses" and not the host, the host may choose among multiple
      EIDs, but it cannot choose among the possible RLOCs (the host has
      no access to that information).  Hence if the ITR chooses a RLOC
      that may not be reachable, traffic to the destination site will be
      blackholed, and the host is left with no recourse.

3.1.  Complexity

   The complexity of testing Locator Path Liveness in the data plane is
   roughly O(M*N), where there are M source addresses and N destination
   addresses.  The following sections more closely analyze the
   complexity of host-based and network-based liveness probing.

Meyer & Lewis             Expires June 11, 2009                 [Page 6]

Internet-Draft          Loc/ID Split Implications          December 2008

3.1.1.  Complexity of Host-Based Probing

   Host-based implementations must keep per-correspondent host liveness
   state.  The complexity of probing in a host-based implementation can
   be though of as follows:

       Let C   = the number of correspondent hosts
       Let D_i = the number of destination locators for host C_i
       Let S   = the number of source locators

       Then the complexity of host-based probing, P_host, is

       O(P_host), where P_host = S*sum(D_i), i = 0...C-1

3.1.2.  Complexity of Network-Based Probing

   Network-based implementations must keep per-destination egress point
   liveness.  The complexity of probing in a network-based
   implementation can be thought of as follows:

       Let N   = the number of EID-prefixes in a network element's
                 cache
       Let L_i = the number of locators for EID-prefix N_i
       Let M   = the number of source locators

       Then the complexity of network-based probing, P_network,  can
       be described as

       O(P_network), where P_network = M*sum(L_i), i = 0...N-1

   Note that a network-based probing scheme might have an advantage here
   since a single EID-prefix may cover many correspondent hosts.  That
   is, sum(L_i), i = 0...N-1 << sum(D_i), i = 0...C-1

3.2.  Possible Optimizations

   The previous sections analyzed the complexity of explicitly probing
   to assess Locator Path Liveness.  In order to mitigate this
   complexity, an implementation might attempt to rely on the various
   "hints".  The following sections, while not intended to be an
   exhaustive survey, outline some of the Locator Path Liveness hints an
   implementation may utilize.

   Data Traffic:  When data is received, an implementation might assume
      that the source of that traffic is reachable, and as such probing
      might not be needed.  Of course, this is at best a unidirectional
      "hint" that an implementation might use to determine locator
      liveness.  Of course, only a complete round trip, wherein the

Meyer & Lewis             Expires June 11, 2009                 [Page 7]

Internet-Draft          Loc/ID Split Implications          December 2008

      distant site says something back to the local site which the local
      site originally sent to the distant site, can one then guarantee
      that the distant site can hear the local site.

      A variation on this theme is to "piggyback" liveness testing on
      user data traffic, by adding a Solicit-User-Probe-Reply bit, which
      tells the far end to send back the next user data packet(s) with
      the outbound nonce, and a User-Probe-Reply bit set.  Of course,
      this optimization depends on the existence of some traffic (even
      if not for the same connection) going between pairs of border
      elements.  That is, if a particular pair has only traffic in one
      direction, this method fails.  In addition, it requires extra
      processing on user data packets, extra overhead in the packets (a
      field, some bits), and extra protocol complication.  Of course,
      such piggybacking only provides the view from remote domain, not
      whether the locator is actually reachable from the recipient of
      the "User-Probe-Bit".

   Protocol Control Messages:  If a protocol control message is received
      (for example, a Map-Reply), an implementation may conclude that
      the source of that is reachable.  Again, in the best case, this is
      only a hint, since receipt of the control message proves only
      unidirectional connectivity.

   Piggybacking Liveness Indications:  A network-based architecture
      might piggyback indication of intra-domain locator liveness on
      other data and/or protocol messages.  An example of this approach
      is LISP's use of loc-reach bits to indicate which Egress Tunnel
      Routers in a domain are up (from an inside the domain
      perspective).

   Existence of the Locator in underlying routing:  A device which is
      responsible for locator liveness can utilize underlying routing to
      determine if the locator is at all available.  If the network
      prefix (or a covering aggregate) for the destination locator is
      NOT found in underlying routing, then the path will not be
      available.  This is at best a negative detection, it can show when
      a path is not available, but liveness of a particular locator.  A
      given locator may still be unavailable and this not be shown in
      routing, due to data plane filtering, or the reachability being
      hidden by aggregation of the particular locator prefix.

   Positive Feedback From Other Protocols:  An implementation may be
      able to deduce some forms of reachability from other protocols.
      For example, TCP might indicate to the IP layer that it believes
      that there is bidirectional connectivity between a given address
      pair.  This might be signalled to the source when it receives a
      SYN-ACK from the destination RLOC.  As pointed out in

Meyer & Lewis             Expires June 11, 2009                 [Page 8]

Internet-Draft          Loc/ID Split Implications          December 2008

      [I-D.ietf-shim6-failure-detection], this is similar to how IPv6
      Neighbor Unreachability Detection can be avoided when upper layers
      provide information about bidirectional connectivity [RFC4861].

      If an implementation has access to higher layer protocols (e.g.,
      BGP), it might get a hint as to the reachability of a given
      locator.  In the case of BGP, an implementation might conclude
      that the locator is reachable if there is a covering prefix in the
      BGP Routing Information Base (RIB).  Again, this is a hint,
      because the correspondent host may be down.

   Timeouts:  An implementation may be able to deduce some forms of
      Unreachability from timeouts of other protocols.For example, TCP
      to indicate that there is a lack of connectivity because it is not
      getting ACKs (of course, the signal is overloaded: there may be
      congestion).

   ICMP Messages:  While ICMP is an available signalling protocol, due
      to its lack of security (in particular, ease of spoofing
      [I-D.ietf-tcpm-icmp-attacks]) and the fact that common policy is
      to block or rate limited ICMP, its utility has been somewhat
      marginalized (see Section 3.3).  As such, ICMP may perhaps be used
      as a hint but beyond that, an implementation can not rely on ICMP
      as a signalling mechanism.

   QQQ: Again, when do I know a locator is up?  If I probe and the
   response is positive, does that mean its up (i.e., it can go down in
   the interim, so what is the time granularity, and what effect does
   that have on efficiency?

   In general, depending on end-to-end liveness indications is
   applicable to only to host-based solutions (e.g.,
   [I-D.ietf-shim6-proto]).  A network-based implementation may rely on
   higher layer protocols to indicate liveness (for example, an
   implementation may be able deduce a limited form of reachability from
   the existence of a BGP route covering the destination RLOC), but
   these too can only be used as hints.  In the general case, however,
   an architecture that implements Loc/ID split (either host-based or
   network-based) will need to test Locator Path Liveness in the data
   plane

3.3.  Security Issues

   Mere inspection of insecure traffic may lead to false negative
   detection due to the insertion of malicious traffic.  For instance,
   packets that masquerade as coming from a site may tamper with the
   loc-reach-bits, making the site locators look unreachable where in
   fact they are reachable [LISP].

Meyer & Lewis             Expires June 11, 2009                 [Page 9]

Internet-Draft          Loc/ID Split Implications          December 2008

   ICMP Messages:  ICMP messages are are easily spoofable
      [I-D.ietf-tcpm-icmp-attacks], so may be exploited to provide false
      negatives.  However, they are also rate limited and often outright
      disabled, leaving a site sending data to a remote RLOC under the
      impression that the RLOC is reachable (as a false positive side
      effect).

   Existance of the Locator in the BGP RIB:  This vulnerability is
      shared by non-Loc/ID split architectures (need reference to
      Pakistani-youtube example as a way compromised routing can break
      path liveness).

   Aside from the ability to mislead a poorly implemented probing
   mechanism with data spoofing, probing creates a fundamentally
   unscalable relationship between site pairs (see Section 3.1).  This
   leads to both implicit (unscalable) and explicit (vulnerable to probe
   floods) Denial of Service vulnerability in the systems receiving
   probe requests.

   Finally, note that in the case of network-based Loc/ID split
   architectures, the RLOCs of border elements represent reachability on
   behalf of entire site.  As a result, failure to detect path liveness
   can disrupt connectivity to the entire site.  On the other hand, in
   host-based LIS, only individual hosts are compromised.

4.  Site-Based State Synchronization

   The Site-Based State Synchronization problem is specific to network-
   based Loc/ID split architectures.  There are two kinds of state
   synchronization that might need to be performed: mapping state
   synchronization and locator liveness synchronization.

   The Site-Based State Synchronization problem can most easily be
   demonstrated by a simple example.  Consider the following case: A
   site has two ITRs; one ITR is on the active path and the other ITR is
   on a backup path.  In this case, all traffic egressing from the site
   traverses the ITR on the active path, and as a result that ITR is
   caching the mapping state for all of the active flows.  The ITR on
   the backup path has no mapping state.  Now, when the ITR on the
   active path fails, traffic is naturally shifted to the ITR on the
   backup path.  If the now active ITR hasn't synchronized its state
   with the previously active ITR(s), then the newly active ITR has to
   reconstruct the mapping state for the flows that were traversing the
   failed ITR.  In particular, the failure, which is local to the site,
   requires the now active ITR to go off-site to reconstruct the state.

Meyer & Lewis             Expires June 11, 2009                [Page 10]

Internet-Draft          Loc/ID Split Implications          December 2008

4.1.  Complexity

   TBD

5.  Conclusions

   Architectures that implement Locator/ID Separation (either host or
   network based) need to carefully evaluate the complexity inherent in
   determining Locator Path Liveness.  The complexity of mapping state
   synchronization is an additional concern for network-based
   architectures.

6.  Acknowledgments

   Scott Brim, Noel Chiappa, John Day, Dino Farinacci, Vince Fuller,
   Mike O'Dell, Andrew Partan, and John Zwiebel provided insightful
   comments on early versions of this document.

7.  IANA Considersations

   This document creates no new requirements on IANA namespaces
   [RFC2434].

8.  References

8.1.  Normative References

   [Chiappa99]
              Chiappa, N., "Endpoints and Endpoint Names: A Proposed
              Enhancement to the Internet Architecture", xxx 1999.

   [EFIT]     Massey, D., "A Proposal for Scalable Internet Routing &
              Addressing", Feb 2007.

   [Fuller06]
              Fuller, V., "Scaling issues with ipv6 routing+
              multihoming", Oct 2006.

   [I-D.fuller-lisp-alt]
              Farinacci, D., "LISP Alternative Topology (LISP+ALT)",
              draft-fuller-lisp-alt-02 (work in progress), April 2008.

   [I-D.ietf-shim6-failure-detection]
              Arkko, J. and I. Beijnum, "Failure Detection and Locator

Meyer & Lewis             Expires June 11, 2009                [Page 11]

Internet-Draft          Loc/ID Split Implications          December 2008

              Pair Exploration Protocol for IPv6  Multihoming",
              draft-ietf-shim6-failure-detection-13 (work in progress),
              June 2008.

   [I-D.ietf-shim6-proto]
              Nordmark, E. and M. Bagnulo, "Shim6: Level 3 Multihoming
              Shim Protocol for IPv6", draft-ietf-shim6-proto-10 (work
              in progress), February 2008.

   [I-D.ietf-tcpm-icmp-attacks]
              Gont, F., "ICMP attacks against TCP",
              draft-ietf-tcpm-icmp-attacks-03 (work in progress),
              March 2008.

   [I-D.jen-apt]
              Jen, D., Meisel, M., Massey, D., Wang, L., Zhang, B., and
              L. Zhang, "APT: A Practical Transit Mapping Service",
              draft-jen-apt-01 (work in progress), November 2007.

   [I-D.lear-lisp-nerd]
              Lear, E., "NERD: A Not-so-novel EID to RLOC Database",
              draft-lear-lisp-nerd-04 (work in progress), April 2008.

   [LISP]     Farinacci, D., Fuller, V., Oran, D., and D. Meyer,
              "Locator/ID Separation Protocol (LISP)",
              draft-farinacci-lisp-10 (work in progress), Oct 2008.

   [ODell08]  Odell, M., "GSE - An Alternate Addressing Architecture for
              IPv6 (Private Communication)", Dec 2008.

   [ODell97]  Odell, M., "GSE - An Alternate Addressing Architecture for
              IPv6", Oct 2006.

   [RFC1498]  Saltzer, J., "On the Naming and Binding of Network
              Destinations", RFC 1498, August 1993.

   [RFC2434]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", BCP 26, RFC 2434,
              October 1998.

   [RFC4423]  Moskowitz, R. and P. Nikander, "Host Identity Protocol
              (HIP) Architecture", RFC 4423, May 2006.

   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
              September 2007.

   [RFC4984]  Meyer, D., Zhang, L., and K. Fall, "Report from the IAB

Meyer & Lewis             Expires June 11, 2009                [Page 12]

Internet-Draft          Loc/ID Split Implications          December 2008

              Workshop on Routing and Addressing", RFC 4984,
              September 2007.

   [Zhang06]  Zhang, L., "An Overview of Multihoming and Open Issues in
              GSE", Sept 2006.

8.2.  Informative References

Authors' Addresses

   David Meyer
   Cisco

   Email: [email-masked]

   Darrel Lewis
   Cisco

   Email: [email-masked]

Meyer & Lewis             Expires June 11, 2009                [Page 13]

Internet-Draft          Loc/ID Split Implications          December 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].

Meyer & Lewis             Expires June 11, 2009                [Page 14]

_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: Robin Whittle <[email-masked]>
Date: Mon, 22 Dec 2008 20:22:46 +1100

Short version:  The problems mentioned in draft-meyer-loc-id-
                implications apply to LISP-ALT and to some
                extent LISP-NERD, APT and TRRP.

                None of these problems exist with Ivip.

Hi David and Darrel,

Regarding your I-D:

  Architectural Implications of Locator/ID Separation
  http://tools.ietf.org/html/draft-meyer-loc-id-implications-00

I think the two problems you raise:

  Locator Path Liveness Problem
  State Synchronization Problem

are problems for LISP-ALT.  I think the first is a problem for
LISP-NERD, but not the second.

I think the first is a problem for APT and TRRP, since in these
schemes - as in LISP - the ITR is given multiple LOC addresses for
any one EID prefix, and achieves multihoming service restoration by
testing reachability to these LOCs and choosing which one to use for
traffic.

The Locator Path Liveness Problem does not exist with Ivip.  A system
external to Ivip is used to probe reachability of the ETRs, and this
system will typically automatically change the mapping in real-time
to achieve whatever multihoming service restoration goals the
end-user network administrator desires.  The probing, decision making
and mapping change system is likely to be distributed over multiple
geographically dispersed servers all over the Net, and to be operated
by a company which specialises in such services.  Each end-user
network will be able to choose between multiple such companies and
have their chosen company probe the reachability of their network in
any manner they desire.

Since Ivip's mapping changes in real-time in response to multihoming
outages, or as a means of dynamically achieving inbound traffic
engineering, the mapping information consists of a single ETR
address.  So ITRs are not involved in reachability testing and have
no decisions to make between multiple ETR addresses for multihoming
or for TE.

The State Synchronization Problem does in principle exist in Ivip.
If there are two caching ITRs and one of them is currently getting
all the traffic, its cache will be fresh and fully matched to the
traffic.  If, for some reason - such as a change in the internal
routing system - a second ITR suddenly receives all this traffic, the
second ITR won't have the mapping already cached for the various
micronets (EIDs in LISP terminology) of the destination addresses of
that traffic.

In LISP-ALT, this is a big problem, because it will often take one or
more seconds to get this mapping information, and in the meantime,
the ITR needs to send the traffic packets on the ALT network, where
they act as mapping requests and by which they are routed to the
correct ETR.  This is slow due to two reasons at least.

Firstly, the ALT network is on a global scale.  The ETRs are the only
query servers and they are physically scattered all over the world.
This makes the ALT network slow and unreliable compared to APT's or
Ivip's use of Full Database Query Servers in the local ISP network
(in APT, these are called "Default Mappers").

Secondly, the ALT network is likely to involve very long paths from
ITR to ETR (the response is typically sent back directly via the
Internet to the ITR), due to the high level of address aggregation in
that network, and due to the fact that the paths up and down the ALT
hierarchy are likely to involve a number of routers which are
geographically widely separated.

  LISP-ALT's long path problem again
  http://psg.com/lists/rrg/2008/msg01676.html
  http://www.antd.nist.gov/~ksriram/strong_aggregation.png

With Ivip, or with APT, there is very little problem due to delays,
since the second caching ITR will request mapping information for all
the micronets (EIDs) it needs and get the responses very quickly
(milliseconds) and reliably, from one of the Full Database Query
Servers in the same ISP (or end-user) network.  With APT, the
response comes from one of the Default Mappers in the same ISP.

Also, the security issues noted in section 3.3 don't apply to Ivip,
since Ivip ITRs are not probing reachability.

A properly designed reachability testing system for Ivip (which is
quite outside the Ivip system, and so can use any techniques at all)
would be secure against interference from spoofed packets.  It would
probe reachability of ETRs - and behind them the reachability of one
or more routers or hosts in the end-user network - from multiple
locations in the Net.  Depending on the results of these probes, the
system might issue a mapping change command to cause ITRs all around
the world to tunnel or forward packets to an alternative ITR.

Likewise, the problem you describe (3.3):

   Aside from the ability to mislead a poorly implemented probing
   mechanism with data spoofing, probing creates a fundamentally
   unscalable relationship between site pairs (see Section 3.1).
   This leads to both implicit (unscalable) and explicit (vulnerable
   to probe floods) Denial of Service vulnerability in the systems
   receiving probe requests.

Applies to LISP-ALT, LISP-NERD, APT and TRRP - but not to Ivip, since
there is only one system probing reachability, irrespective of the
number of ITRs which are currently handling data for a particular ETR
or end-user network.

  Regards

    - Robin

  http://www.firstpr.com.au/ip/ivip/Ivip-summary.pdf

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 07:05:54 -0800

Hey Robin,

>                 None of these problems exist with Ivip.

	Well, stating that is one thing, demonstrating it at a
	sufficent level of detail is another. I'd welcome the
	latter. 

> LISP-NERD, but not the second.

	Well, NERD does have this problem. It just pays the
	(pre-sync) price at some central site. That has its own
	set of problems, but they all derive from the same basic
	issue. The difference is basically one of "pay me now or
	pay me later" (or as many folks on this list are fond of
	saying, TANSTAAFL).   

> have their chosen company probe the reachability of their network in

	"A system external"..."is likely". Really?

	Please explain. There's not enough information in what
	you said to understand what you are proposing. But
	briefly, the "system external" to Ivip (whatever that may
	be) is needed precisely because Ivip (and every other
	Loc/ID split architecture I've seen) has the reachibility
	problem.

	I'll note here that host based solutions (e.g., HIP,
	SHIM6) also have the locator liveness problem,  but in
	general don't have the state sync problem. 

> no decisions to make between multiple ETR addresses for multihoming

	So you put reachability information in the mapping
	database? 

> micronets (EIDs in LISP terminology) of the destination addresses of

	Well, you state the problem does not exist and go on to
	describe the problems that we've already described. What
	would be useful/interesting is for you to provide a
	detailed description of what you are proposing as a
	solution to either or both of these problems, and how
	they avoids, say the trivial failure secnaros described
	in the draft. 

> response comes from one of the Default Mappers in the same ISP.

	Have you noticed that the default mapper is in the data
	path? It (the default mapper) is also in the site's
	IGP. That may be ok, but you're talking about a big piece
	forwarding engine to handle this. In addition it (the
	default mapper) needs to be on-path during failures to be
	able to re-route to another ETR. Now information is split
	between the ITR (which during the failure has old
	information) and the default mapper.

	BTW, note that the default mapper also also needs to get
	mappings from outside the site, so the fact that it's in
	the same ISP isn't really relevant (sure, you can push
	all the mappings (equivalent to hosts.txt) to the default
	mapper (that's the NERD case), but that doesn't help when
	things are changing (of course, there's a state latency
	tradeoff here). 

> since Ivip ITRs are not probing reachability.

	Agin, you state that, but you don't state how. The devil
	here is the details.

	Based on your comments, it seems to me that you didn't
	understand that the purpose of the draft was to more
	deeply understand the architectural implications of
	Loc/ID split, not to advocate for or against any
	particular proposal. 

	Dave

---

From: "William Herrin" <[email-masked]>
Date: Mon, 22 Dec 2008 14:34:42 -0500

On Mon, Dec 22, 2008 at 10:05 AM, David Meyer <[email-masked]> wrote:
> "A system external"..."is likely". Really? Please explain.

David,

What I proposed in TRRP, and I *think* what Robin proposed in Ivip, is
that the choice to switch between locators should be driven by a
heuristic system external to the protocol itself.

The destination system uses this external heuristic to choose its
locators, and the source system blindly follows the destination
system's instruction. If the path between the source and destination
locators is dead, it's up to the destination to figure this out (using
the external heuristic system) and alter its locator to one that
works.

Examples of such a heuristic include:

1. I think my Internet link is bunged up, so I press the "switch
locators" button and that alters my map entry.

2. A monitoring system at my network border polls external public
probe sites and watches for retransmission in the TCP sessions which
pass by it. If the failure rate exceeds the programmed threshold, it
decides my Internet link is bunged up and alters my map entry to favor
a different locator.

3. A globe-spanning Akamai-like system of testpoints builds a complex
map of Internet path states. Combined with some basic information
about the state of my connections to my ISPs, it can compute what will
usually be a good current locator selection for me. I subscribe to
this service.

This approach addresses the locator liveness problem by substituting a
heuristic for an algorithm. It accepts that while the result will
usually be good enough it won't always be perfect and may rarely
require intervention.

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 12:23:40 -0800

Bill,

	Before diving in here, a few people mentioned that I
	should have put the following in front of my last post
	(to Robin) instead of at the end:

> locators" button and that alters my map entry.

	What does "alters my map entry" mean? Who does it, on
	what time scale, who has visibility into data and when,
	what bits get sent where, etc. You get the picture. 

	What we need to see detail, precisely because that is
	where the problems arise. From that perspective, "alters
	my map entry" is almost (if not completely) content free.
	
> decides my Internet link is bunged up and alters my map entry to favor

	Really? You want to put the dependency that routers (or
	something) must snoop the data plane for TCP state to
	make connectivity work? Notwithstanding the wisdom of
	introducing that dependency, what if traffic is
	unidirectional (or otherwise asymmetric), UDP, or ...
	And what if its multiple 10GE fire hoses blasting data at
	you? 

	I won't even start down the security/privacy path with
	that one.

> usually be a good current locator selection for me. I subscribe to

	If you can't reach the endpoints (good or bad), none of 3.
	matters; not I think that making the network layer depend
	on this kind infrastructure, and not to mention the
	circular dependency that could arise. 

	But again, these high level descriptions of how something
	that is largely unspecified (notably the "heuristic system
	external to the protocol itself") doesn't help me
	understand (i). what mechanism you are proposing,
	(ii). what its properties are, and (iii). if it even
	works.  

	OTOH, what would be helpful would be for you and/or Robin
	to describe  *the mechanism and how it works, in detail*
	that you are proposing, then show how it solves the
	simple example problem in Section 3 (Figure 1) for the
	draft. 

> usually be good enough it won't always be perfect and may rarely

	I guess I'm not understanding, primarily it seems since
	you haven't given any detail about how this would
	actually work. 

	My point is that  statements like "substituting a
	heuristic for an algorithm" don't really enighten us as
	to the solutions (or their properties) that you are
	proposing.  

	Please give details so we can understand.

	Dave

---

From: "William Herrin" <[email-masked]>
Date: Mon, 22 Dec 2008 16:42:21 -0500

David,

>> locators" button and that alters my map entry.

My authoritative locator map is stored on several DNS servers, each
sitting on BGP-advertised PA addresses. In the map, La has the top
priority. Lb has second priority. When I press the "switch locators"
button, the device performs a dynamic DNS update to each of those
authoritative DNS servers, installing the map in which Lb has top
priority. The device has a PA address from each of A and B, and it
retries the dynamic update using each source until it succeeds.

When the TTL on the map expires at C as much as a minute later, C
re-queries the locator map from one of the DNS servers sitting on its
BGP-advertised PA address and starts using Lb instead of La.

>> decides my Internet link is bunged up and alters my map entry to favor

Same except the monitoring machine is the device in question and it
presses the button for me.

>> usually be a good current locator selection for me. I subscribe to

Akamai detects that provider A has encountered a significant network
bump. Testpoints at providers B and C can no longer reach testpoints
at provider A. It verifies that I appear to still be adequately
connected to provider B, as I claimed when I signed up. It performs a
dynamic DNS update to each of my authoritative servers, changing Lb to
top priority.

Being clever, Akamai notices that I am still connected to provider A
and provider A isn't completely dead. So, it leaves the one DNS server
on provider A reporting that La has the top priority. Anyone who can
still reach provider A to get to the DNS server I have there will
still  reach me at La.

>        unidirectional (or otherwise asymmetric), UDP, or ...

Then you use a heuristic device that is more appropriate to your
particular network configuration. That's one point of pushing the
function out into an external device: the solutions aren't one size
fits all.

>        And what if its multiple 10GE fire hoses blasting data at

I'm not going to interact with 10ge flows. None of the Strategy-A
systems are. I'm going to deploy my equipment shallow enough in the
network to work with flows manageable on commodity PC hardware, which
is currently sub-gige. The hundred gig-e flows are on the coreward
side of the ITR.

And if you look around at operations today, you'll find very few
places where that's the slightest bit challenging and none where it
can't be done at all.

>        you haven't given any detail about how this would

Start by reading http://bill.herrin.us/network/trrp.html . Don't just
scan it. Read it. It's six pages long; it won't kill you.

If there are any details for which you still don't have a solid mental
picture, I'll be pleased to expand on them until you do.

Regards,
Bill Herrin

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 14:00:15 -0800

> picture, I'll be pleased to expand on them until you do.

	Thnx, will do.

	Dave

---

From: "William Herrin" <[email-masked]>
Date: Mon, 22 Dec 2008 17:06:42 -0500

David,

On second thought, my external manager in TRRP doesn't take any action
at all to solve figure 1.

I have two map servers (DNS servers) one using a BGP PA address at A
and one using a BGP PA address at B. This is a typical redundant
configuration for DNS servers.

My map entry on the server at A is different than my map entry on the
server at B. This is unusual for DNS servers today but not unheard of.
The map at A gives La priority. The map at B gives Lb priority.

S1 found La by following the DNS root down to my map server at A and
querying my map there. When A becomes unreachable to C, packets from
S1 stop reaching S0. A few seconds to a minute later, the map TTL
expires. S1 refreshes the map from my map servers.

S1 can't get a response from the map server at A so it tries the one
at B (normal DNS resolver behavior). The server at B provides a map in
which Lb has priority. Since S1 can reach Lb, communication between S1
and S0 resumes.

Have fun,
Bill Herrin

---

From: David Meyer <[email-masked]>
Date: Tue, 23 Dec 2008 07:56:43 -0800

Bill,

>> Start by reading http://bill.herrin.us/network/trrp.html.
>> Don't just scan it. Read it. It's six pages long; it won't
>> kill you. 

	Thanks for the hint. You are right, it is a short
	document, and I'm still alive (by most accounts :-)).  

	That said, I just want to deal with the architectural
	issue that I'm interested here: locator liveness. I have
	a bunch of other questions, but I just stuck them at the
	end of this message because they don't directly deal with
	this particular issue. 

	In any event, you say:	

	  "The ITR finds an Egress Tunnel Router (ETR) for the
	  destination IP address via a DNS lookup."

	and later 

	  "The ITR should look up the route entry when it first
	  sees a packet for the destination. If possible, it
	  should hold packets for the destination in a buffer
	  until a route is found. " 

	(For this discussion, I'm ignoring issues around
	buffering packets while waiting for a mapping, what
	scalability constraints are put on the DNS, the effects
	of having the mapping data be opqaue to the mapping
	system, configuration of p2mp GRE tunnels, ...; see below
	for questions around these things). 

	So what you describe is the well-known, standard
	map-and-encap behavior. A packet hits the ITR, the ITR
	looks up the mapping (existing mapping, DNS, APT, ALT,
	static, or whatever), encaps the packet, sends it to the
	destination ETR. Now, at this point if you have to asses
	reachability somehow, or you can create a persistent
	failure by latching on the wrong "route" (or "routes"; a
	route here is analogous to what folks are calling RLOCs
	in other contexts). 

	Of course, the host can always back off to another EID,
	but if the ITR thinks a "route" (RLOC) that is associated
	with that EID (however that happens) is reachable when it
	isn't and continues to encapsulate packets to that
	"route", then you have a persistant failure. 

	The upshot is that TRRP has the same locator liveness
	problem I've been describing. I'm not at all surprised by
	this, as I am under the impression that this is a general
	property of the Loc/ID split architecture, and not any
	particular proposal. 

	Dave

----

	A few comments on your document (and thanks for pushing
	on me to read it).

	- In "General statement of the solution:"

          " An AS-interior default route leads from the BGP
	  routers to the ITR."

	   Is this saying that there is a default in the
	   site's iBGP or IGP that tells it how to get to the
	   exit points for the site? If so, is this just an
	   implementation detail or a requirement?

	  "The ITR finds an Egress Tunnel Router (ETR) for the
	  destination IP address via a DNS lookup."

	    What destination address? The destination address in
	    the packet emitted by the host? So I saw this:

	     "The ITR should look up the route entry when it
	     first sees a packet for the destination. If
	     possible, it should hold packets for the destination
	     in a buffer until a route is found. "

	   So this is standard map-and-encap behavior (mod
	   holding the packet). I see that you inverse address
	   query for a TXT record associated with the IP address
	   in the destination address in the packet that 
	   the host emitted (this TXT record encodes information
	   about the RLOCs of the ETRs, if you will). Yes? 

	   So at this point if you have to asses reachability
	   somehow, or you can create a persistent failure by
	   latching on the wrong "route" (or "routes"). The host
	   has no visibility into this, so whatever it does is
	   more or less irrelevant. Now, in theory you could
	   snoop data traffic (note GSE can't do this), so you
	   might be able to determine liveness w/o probing, at
	   least for symmetrical (TCP) flows. 

	   The upshot is that TRRP has the same locator liveness
	   problem I've been describing. I'm not at all surprised
	   by this, as I'm under the impression that this is a
	   general property of the Loc/ID split architecture, and
	   not any particular proposal (BTW, it'd be great if
	   someone could show otherwise).

	- "The ITR then tunnels the packet via GRE to the "best"
	   ETR."

	    So the ITR got a set of ETR addresses from the
	    DNS (TXT records) in the previous step, each of which
	    is a candidate site for where it might send the
	    (encapsulated?) packet. Correct?

	    In addition, the ITR gets this list when it inverse
	    address queries for whatever was in the destination
	    of the packet that the host emitted (this is how I
	    understand your use of the DNS). It encapsulates this
	    packet over GRE to the destination found in the TXT
	    record (with some processing of the options in the
	    TXT record). Correct? 

	    If so, how does the ITR know which ETRs its going to
	    talk to (in order to set up the GRE tunnels)? Or does
	    the ITR not set up s GRE tunnel between the ITR and
	    ETR? Or did you mean some kind of dynamic GRE (i.e.,
	    just uses GRE encap, or ?). 

	    I see from this example that its the ETR that sets up
	    a p2mp tunnel:

		Cisco IOS configuration example:

		interface Tunnel0
		  description TRRP Egress Tunnel Router
		  no ip address
		  tunnel source FastEthernet0/0
		  tunnel mode gre multipoint
		  tunnel key 1

	   makes it seem lile the ETR will need to know where all
	   the other ITRs that might want to talk to it are. How
	   does that work?

	- "The ETR, which must have an IP address within space
	   announced via BGP, knows a local-scope route to the 
	   destination IP address and delivers the packet. "

	   That makes sense. The IGP (or possibly iBGP) knows how
	   to how to route packets within the domain (that's the
	   point of the IGP, AFAIK). Anyway, that makes sense.

	- "Longer route prefixes are then withdrawn from BGP
	   until a comfortable BGP table size is attained."  

	   I couldn't get that to follow from what you said, or
	   how it works.

	- Other notes:

	(i).	dig couldn't find a nameserver for either
	        v4.trrp.arpa or v6.trrp.arpa, or
		v4.trrp.in-addr.arpa or v6.trrp.in-addr.arpa 
	
	(ii).	The term "route" is somehow overloaded in your
		document. In particular, when you're talking
		about the TXT record encoding, you overview the
		encoding as 'pp,ii,route pp,ii,route ..." and in
		the encoding you have stuff like 

		  00 = always prefer this route
		  40 = prefer this route
		  80 = normal
		  b0 = avoid this route
		  ff = use this route only as a last resort

		These are really the decapsulation point for the
		source packet that's about to be encapped. Its
		not really a route (or doesn't seem to be to me);
		you really don't care what path the packet takes
		(within reason), you just care that the packet
		can tet to the "route" to be decapsulated. Yes?

	(iii).	Host unreachables

		You say that the ETR needs to unreachables do to 
		the insecurity of ICMP. You suggest sending ICMP
		echo-request. This is another form of searching
		(with data probes) for locator liveness. In
		addition, if the destination is unreachable, you
		take it down for 5 minutes (mod you see traffic
		for it). That's a failure mode we don't have in
		the internet today; if the host is unreachable
		due to, say, a routing anomaly, it becomes
		reachable when routing converges. You're scheme
		doesn't. Note here that I'm just observing the
		properties of the mechanism you propose and
		comparing that to what we see today.

	(iv).	BGP with the "Holey Route Authority"

		You say:

		  A central route authority keeps track of all
		  holey routes and peers them with all ASes which
		  implement an ITR. Each such AS implements a
		  route-map to force those prefixes to head the
		  same direction as the default route.

		All I can say is that hasn't worked to date.

	(v).	Preemptive Change Notification (PCN)

		You say (PCN Type 1): 

		  PCN Type 1: Notification of change by the DNS
		  server The authoritative DNS Route server
		  remembers all IP addresses which requested each
		  Route entry during the entry's TTL. Immediately
		  upon the Route entry's change, the Route Server
		  sends a UDP message to port XX of the
		  requestor. The first byte of the message is
		  0x01. The remaining bytes are the DNS query
		  which should immediately expire. 

		Can you comment on the scaling propeties of this?

	I'll stop here.

	Anyway, I hope this gets us going a bit.

	Thanks,

	Dave

---

From: "William Herrin" <[email-masked]>
Date: Tue, 23 Dec 2008 15:19:56 -0500

>        route here is analogous to what folks are calling RLOCs

Hi Dave,

For clarity's sake, lets say: "Latching on to a currently unreachable ETR."

TRRP moves the connectedness problem away from the ITR. At the primary
level, the ITR is not responsible for deciding whether it can reach a
particular ETR. Period.

The connectedness problem is moved entirely to the destination
network's external system that selects the priority at which ETRs go
into the map. The scope of the connectedness problem reduces to:

1. Deciding which of my ETRs can currently reach me, and
2. Deciding which of my ETRs are "fully connected" to the Internet for
some heuristic definition of "fully connected."

The ITR latches on to an unreachable ETR only if the destination
selects an ETR for himself which is not fully connected to the
Internet.

Let's be clear about something with the connectedness problem:

It's a statistics game. The overall unreliability of your Internet
link is additive from all the components which introduce failures. The
probability of latching on to an unreachable ETR when another is
reachable doesn't have to be zero. Unless it always fails for the same
group, it just has to be a small fraction of the overall unreliability
of the system.

>        A few comments on your document (and thanks for pushing

Thank you!

>           implementation detail or a requirement?

If a route for the destination address exists in eBGP, then a packet
with that destination address follows that route across the core to
the machine using the address.

If a specific route for the destination address exists in the IGP, the
packet follows that route within the ISP to the machine using the
address.

Otherwise the packet follows a default route in the IGP. The default
route leads to an ITR. The ITR encapsulates the packet inside a tunnel
packet with the destination address of an ETR. The destination address
for the ETR must be selected from the subset of addresses for which
routes exist in eBGP.

>            the packet emitted by the host?

Yes.

>           about the RLOCs of the ETRs, if you will). Yes?

Yes.

>           somehow.

No. The destination network has already made a determination that the
ETR is reachable by all hosts on the Internet. He made this
determination when he set the contents of that TXT record. If he made
the wrong choice then he is unreachable, just as if all possible paths
to him were down.**

** Not strictly true; it may still be possible to reach him. For the
purpose of quantifying the worst case scenario, the destination is
unreachable if the ETR to which he assigned top priority is
unreachable.

>            (encapsulated?) packet. Correct?

Yes with a caveat: the expected behavior is that the ITR will select
the one ETR address at the top of the stack. None of the others are
initially candidates. The others become candidates only under
circumstances in which one of the secondary mechanisms has shown
itself to be functioning successfully.

For example, if a packet sent to the ETR at the top of the stack
returns a host unreachable then the second ETR in the stack becomes a
candidate. But if no packet returns, either because they're all
delivered or because the packets are dropping into a black hole, the
second and later ETRs in the TXT record never become candidates.

>            record (with some processing of the options in the

Yes.

>            just uses GRE encap, or ?).

It's stateless; there is no setup. I think Scott Brim described the
system as a "funnel" rather than a tunnel, and that's pretty good way
to put it. The ETR decapsulates packets with its destination address
that are in the GRE format. Unless you tell it otherwise, it doesn't
care what the source address of the GRE packet was.

>           the other ITRs that might want to talk to it are.

No. Note the absence of a "tunnel destination" parameter. That
particular configuration will accept and decapsulate GRE packets with
key 1 from any source IP address.

I originally tried to do it without a gre key too. Linux was happy but
IOS decided that with neither a tunnel destination nor a tunnel key,
it couldn't decide which tunnel interface to associate the incoming
packets with.

>           I couldn't get that to follow from what you said, or

Let's say you have a 192.1.1.0/24. You announce that with eBGP into
the network core via, let's say, Sprint.

One day you get a call from a Verizon rep. The Verizon rep says:

"We see that you announce 192.1.1.0/24 from Sprint. We're going to
stop accepting /24's from Sprint 90 days from now. The /24 routes from
other ISPs cost us too much money and we don't get paid for them. If
you want to continue talking to Verizon customers, you must do one of
the following:"

"A. Pay us $50/month to continue accepting your 192.1.1.0/24 route from Sprint."

"B. Deploy TRRP on your network."

You're really pissed off at Verizon for trying to extort money from
you, so you look into this TRRP thing instead.

It turns out that what you have to do is get Sprint to give you two IP
address from their 65.160.0.0/13 block. You ask Sprint to give you two
and they assign 65.160.123.45 and 65.160.123.46. You pull an old Cisco
2501 out of the closet and configure it with a GRE tunnel on the
65.160.123.45 address.

Next you have to go over to ARIN. They manage the address space for
192.1.1.0/24, and thus the DNS domain for 1.1.192.v4.trrp.arpa. You
tell ARIN: "Please delegate 1.1.192.v4.arpa my DNS server at
ns1.1.1.192.v4.arpa, whose IP address is 65.160.123.46."

Finally, you set up a DNS server on 65.160.123.46 which has just one
entry: *.1.1.192.v4.arpa TXT 80,g4,65.160.123.45

Done.

90 days later, Verizon stops accepting 192.1.1.0/24. Inside their
network, packets follow a default route to an ITR. The ITR queries the
TXT record in your DNS server and encapsulates packets for you in a
GRE packet with a destination address of 65.160.123.45. You don't even
notice.

A few weeks later, an AT&T rep calls and says, "Listen, we're not
going to keep accepting your route for free. Pay us $50 or deploy
TRRP." You respond: "Screw you, I already have TRRP."

>                v4.trrp.in-addr.arpa or v6.trrp.in-addr.arpa

It doesn't exist. No point requesting resources at that level for an
experimental protocol when any subdomain will do.

>                the encoding you have stuff like

I wrote the document in earlier days before some of the terminology
was sorted out. It could use some cleanup.

>                (with data probes) for locator liveness.

Bear in mind that this is a *secondary* mechanism. In a subset of
cases, it allows the ITR to try to find an alternate path when the
destination network made a poor choice of ETR.

If the ping succeeds, the ITR must ignore the unreachable. Otherwise
this secondary mechanism could disrupt the primary mechanism and
errantly latch on to an ETR other than the one the destination network
told it to use.

All I'm really saying here is this: the connectivity decision is
supposed to be made by the destination network, but there's no reason
to be excessively dogmatic about it. When normal operations provides
you with "free" information to the effect that the destination network
chose badly, why not use it?

>                All I can say is that hasn't worked to date.

Another approach would be to add a BGP option or community or
something to the supernet announcement which advises all recipients
that the supernet prefix is associated with TRRP use and should be
discarded by systems which support TRRP.

Admitted as a particularly nasty and not truly solved corner case in TRRP.

>                Can you comment on the scaling propeties of this?

PCN doesn't scale. The reality of it is that if you use it you'll pick
a maximum size for the pool of requestors you're going to remember and
when it's full it's full. Everybody else will have to pick up the
change after the TTL expires.

PCN is an optional, secondary mechanism. In a subset of cases it
allows TRRP to fail over to an alternate ETR faster than the baseline
of a few tens of seconds.

Regards,
Bill Herrin