Tech-invite3GPPspecsGlossariesIETFRFCsGroupsSIPABNFs   Ti+   SearchTech-invite World Map Symbol

RFC 6830


The Locator/ID Separation Protocol (LISP)

Part 3 of 4, p. 42 to 64
Prev RFC Part       Next RFC Part


prevText      Top      Up      ToC       Page 42 
6.2.  Routing Locator Selection

   Both the client-side and server-side may need control over the
   selection of RLOCs for conversations between them.  This control is
   achieved by manipulating the 'Priority' and 'Weight' fields in
   EID-to-RLOC Map-Reply messages.  Alternatively, RLOC information MAY
   be gleaned from received tunneled packets or EID-to-RLOC Map-Request

   The following are different scenarios for choosing RLOCs and the
   controls that are available:

   o  The server-side returns one RLOC.  The client-side can only use
      one RLOC.  The server-side has complete control of the selection.

   o  The server-side returns a list of RLOCs where a subset of the list
      has the same best Priority.  The client can only use the subset
      list according to the weighting assigned by the server-side.  In
      this case, the server-side controls both the subset list and

Top      Up      ToC       Page 43 
      load-splitting across its members.  The client-side can use RLOCs
      outside of the subset list if it determines that the subset list
      is unreachable (unless RLOCs are set to a Priority of 255).  Some
      sharing of control exists: the server-side determines the
      destination RLOC list and load distribution while the client-side
      has the option of using alternatives to this list if RLOCs in the
      list are unreachable.

   o  The server-side sets a Weight of 0 for the RLOC subset list.  In
      this case, the client-side can choose how the traffic load is
      spread across the subset list.  Control is shared by the server-
      side determining the list and the client determining load
      distribution.  Again, the client can use alternative RLOCs if the
      server-provided list of RLOCs is unreachable.

   o  Either side (more likely the server-side ETR) decides not to send
      a Map-Request.  For example, if the server-side ETR does not send
      Map-Requests, it gleans RLOCs from the client-side ITR, giving the
      client-side ITR responsibility for bidirectional RLOC reachability
      and preferability.  Server-side ETR gleaning of the client-side
      ITR RLOC is done by caching the inner-header source EID and the
      outer-header source RLOC of received packets.  The client-side ITR
      controls how traffic is returned and can alternate using an outer-
      header source RLOC, which then can be added to the list the
      server-side ETR uses to return traffic.  Since no Priority or
      Weights are provided using this method, the server-side ETR MUST
      assume that each client-side ITR RLOC uses the same best Priority
      with a Weight of zero.  In addition, since EID-Prefix encoding
      cannot be conveyed in data packets, the EID-to-RLOC Cache on
      Tunnel Routers can grow to be very large.

   o  A "gleaned" Map-Cache entry, one learned from the source RLOC of a
      received encapsulated packet, is only stored and used for a few
      seconds, pending verification.  Verification is performed by
      sending a Map-Request to the source EID (the inner-header IP
      source address) of the received encapsulated packet.  A reply to
      this "verifying Map-Request" is used to fully populate the
      Map-Cache entry for the "gleaned" EID and is stored and used for
      the time indicated from the 'TTL' field of a received Map-Reply.
      When a verified Map-Cache entry is stored, data gleaning no longer
      occurs for subsequent packets that have a source EID that matches
      the EID-Prefix of the verified entry.

   RLOCs that appear in EID-to-RLOC Map-Reply messages are assumed to be
   reachable when the R-bit for the Locator record is set to 1.  When
   the R-bit is set to 0, an ITR or PITR MUST NOT encapsulate to the
   RLOC.  Neither the information contained in a Map-Reply nor that
   stored in the mapping database system provides reachability

Top      Up      ToC       Page 44 
   information for RLOCs.  Note that reachability is not part of the
   mapping system and is determined using one or more of the Routing
   Locator reachability algorithms described in the next section.

6.3.  Routing Locator Reachability

   Several mechanisms for determining RLOC reachability are currently

   1.  An ETR may examine the Locator-Status-Bits in the LISP header of
       an encapsulated data packet received from an ITR.  If the ETR is
       also acting as an ITR and has traffic to return to the original
       ITR site, it can use this status information to help select an

   2.  An ITR may receive an ICMP Network Unreachable or Host
       Unreachable message for an RLOC it is using.  This indicates that
       the RLOC is likely down.  Note that trusting ICMP messages may
       not be desirable, but neither is ignoring them completely.
       Implementations are encouraged to follow current best practices
       in treating these conditions.

   3.  An ITR that participates in the global routing system can
       determine that an RLOC is down if no BGP Routing Information Base
       (RIB) route exists that matches the RLOC IP address.

   4.  An ITR may receive an ICMP Port Unreachable message from a
       destination host.  This occurs if an ITR attempts to use
       interworking [RFC6832] and LISP-encapsulated data is sent to a
       non-LISP-capable site.

   5.  An ITR may receive a Map-Reply from an ETR in response to a
       previously sent Map-Request.  The RLOC source of the Map-Reply is
       likely up, since the ETR was able to send the Map-Reply to the

   6.  When an ETR receives an encapsulated packet from an ITR, the
       source RLOC from the outer header of the packet is likely up.

   7.  An ITR/ETR pair can use the Locator reachability algorithms
       described in this section, namely Echo-Noncing or RLOC-Probing.

Top      Up      ToC       Page 45 
   When determining Locator up/down reachability by examining the
   Locator-Status-Bits from the LISP-encapsulated data packet, an ETR
   will receive up-to-date status from an encapsulating ITR about
   reachability for all ETRs at the site.  CE-based ITRs at the source
   site can determine reachability relative to each other using the site
   IGP as follows:

   o  Under normal circumstances, each ITR will advertise a default
      route into the site IGP.

   o  If an ITR fails or if the upstream link to its PE fails, its
      default route will either time out or be withdrawn.

   Each ITR can thus observe the presence or lack of a default route
   originated by the others to determine the Locator-Status-Bits it sets
   for them.

   RLOCs listed in a Map-Reply are numbered with ordinals 0 to n-1.  The
   Locator-Status-Bits in a LISP-encapsulated packet are numbered from 0
   to n-1 starting with the least significant bit.  For example, if an
   RLOC listed in the 3rd position of the Map-Reply goes down (ordinal
   value 2), then all ITRs at the site will clear the 3rd least
   significant bit (xxxx x0xx) of the 'Locator-Status-Bits' field for
   the packets they encapsulate.

   When an ETR decapsulates a packet, it will check for any change in
   the 'Locator-Status-Bits' field.  When a bit goes from 1 to 0, the
   ETR, if acting also as an ITR, will refrain from encapsulating
   packets to an RLOC that is indicated as down.  It will only resume
   using that RLOC if the corresponding Locator-Status-Bit returns to a
   value of 1.  Locator-Status-Bits are associated with a Locator-Set
   per EID-Prefix.  Therefore, when a Locator becomes unreachable, the
   Locator-Status-Bit that corresponds to that Locator's position in the
   list returned by the last Map-Reply will be set to zero for that
   particular EID-Prefix.

   When ITRs at the site are not deployed in CE routers, the IGP can
   still be used to determine the reachability of Locators, provided
   they are injected into the IGP.  This is typically done when a /32
   address is configured on a loopback interface.

   When ITRs receive ICMP Network Unreachable or Host Unreachable
   messages as a method to determine unreachability, they will refrain
   from using Locators that are described in Locator lists of
   Map-Replies.  However, using this approach is unreliable because many
   network operators turn off generation of ICMP Destination Unreachable

Top      Up      ToC       Page 46 
   If an ITR does receive an ICMP Network Unreachable or Host
   Unreachable message, it MAY originate its own ICMP Destination
   Unreachable message destined for the host that originated the data
   packet the ITR encapsulated.

   Also, BGP-enabled ITRs can unilaterally examine the RIB to see if a
   locator address from a Locator-Set in a mapping entry matches a
   prefix.  If it does not find one and BGP is running in the Default-
   Free Zone (DFZ), it can decide to not use the Locator even though the
   Locator-Status-Bits indicate that the Locator is up.  In this case,
   the path from the ITR to the ETR that is assigned the Locator is not
   available.  More details are in [LOC-ID-ARCH].

   Optionally, an ITR can send a Map-Request to a Locator, and if a
   Map-Reply is returned, reachability of the Locator has been
   determined.  Obviously, sending such probes increases the number of
   control messages originated by Tunnel Routers for active flows, so
   Locators are assumed to be reachable when they are advertised.

   This assumption does create a dependency: Locator unreachability is
   detected by the receipt of ICMP Host Unreachable messages.  When a
   Locator has been determined to be unreachable, it is not used for
   active traffic; this is the same as if it were listed in a Map-Reply
   with Priority 255.

   The ITR can test the reachability of the unreachable Locator by
   sending periodic Requests.  Both Requests and Replies MUST be rate-
   limited.  Locator reachability testing is never done with data
   packets, since that increases the risk of packet loss for end-to-end

   When an ETR decapsulates a packet, it knows that it is reachable from
   the encapsulating ITR because that is how the packet arrived.  In
   most cases, the ETR can also reach the ITR but cannot assume this to
   be true, due to the possibility of path asymmetry.  In the presence
   of unidirectional traffic flow from an ITR to an ETR, the ITR SHOULD
   NOT use the lack of return traffic as an indication that the ETR is
   unreachable.  Instead, it MUST use an alternate mechanism to
   determine reachability.

6.3.1.  Echo Nonce Algorithm

   When data flows bidirectionally between Locators from different
   sites, a data-plane mechanism called "nonce echoing" can be used to
   determine reachability between an ITR and ETR.  When an ITR wants to
   solicit a nonce echo, it sets the N- and E-bits and places a 24-bit
   nonce [RFC4086] in the LISP header of the next encapsulated data

Top      Up      ToC       Page 47 
   When this packet is received by the ETR, the encapsulated packet is
   forwarded as normal.  When the ETR next sends a data packet to the
   ITR, it includes the nonce received earlier with the N-bit set and
   E-bit cleared.  The ITR sees this "echoed nonce" and knows that the
   path to and from the ETR is up.

   The ITR will set the E-bit and N-bit for every packet it sends while
   in the echo-nonce-request state.  The time the ITR waits to process
   the echoed nonce before it determines the path is unreachable is
   variable and is a choice left for the implementation.

   If the ITR is receiving packets from the ETR but does not see the
   nonce echoed while being in the echo-nonce-request state, then the
   path to the ETR is unreachable.  This decision may be overridden by
   other Locator reachability algorithms.  Once the ITR determines that
   the path to the ETR is down, it can switch to another Locator for
   that EID-Prefix.

   Note that "ITR" and "ETR" are relative terms here.  Both devices MUST
   be implementing both ITR and ETR functionality for the echo nonce
   mechanism to operate.

   The ITR and ETR may both go into the echo-nonce-request state at the
   same time.  The number of packets sent or the time during which echo
   nonce requests are sent is an implementation-specific setting.
   However, when an ITR is in the echo-nonce-request state, it can echo
   the ETR's nonce in the next set of packets that it encapsulates and
   subsequently continue sending echo-nonce-request packets.

   This mechanism does not completely solve the forward path
   reachability problem, as traffic may be unidirectional.  That is, the
   ETR receiving traffic at a site may not be the same device as an ITR
   that transmits traffic from that site, or the site-to-site traffic is
   unidirectional so there is no ITR returning traffic.

   The echo-nonce algorithm is bilateral.  That is, if one side sets the
   E-bit and the other side is not enabled for echo-noncing, then the
   echoing of the nonce does not occur and the requesting side may
   erroneously consider the Locator unreachable.  An ITR SHOULD only set
   the E-bit in an encapsulated data packet when it knows the ETR is
   enabled for echo-noncing.  This is conveyed by the E-bit in the
   Map-Reply message.

   Note that other Locator reachability mechanisms are being researched
   and can be used to compliment or even override the echo nonce
   algorithm.  See the next section for an example of control-plane

Top      Up      ToC       Page 48 
6.3.2.  RLOC-Probing Algorithm

   RLOC-Probing is a method that an ITR or PITR can use to determine the
   reachability status of one or more Locators that it has cached in a
   Map-Cache entry.  The probe-bit of the Map-Request and Map-Reply
   messages is used for RLOC-Probing.

   RLOC-Probing is done in the control plane on a timer basis, where an
   ITR or PITR will originate a Map-Request destined to a locator
   address from one of its own locator addresses.  A Map-Request used as
   an RLOC-probe is NOT encapsulated and NOT sent to a Map-Server or to
   the mapping database system as one would when soliciting mapping
   data.  The EID record encoded in the Map-Request is the EID-Prefix of
   the Map-Cache entry cached by the ITR or PITR.  The ITR may include a
   mapping data record for its own database mapping information that
   contains the local EID-Prefixes and RLOCs for its site.  RLOC-probes
   are sent periodically using a jittered timer interval.

   When an ETR receives a Map-Request message with the probe-bit set, it
   returns a Map-Reply with the probe-bit set.  The source address of
   the Map-Reply is set according to the procedure described in
   Section 6.1.5.  The Map-Reply SHOULD contain mapping data for the
   EID-Prefix contained in the Map-Request.  This provides the
   opportunity for the ITR or PITR that sent the RLOC-probe to get
   mapping updates if there were changes to the ETR's database mapping

   There are advantages and disadvantages of RLOC-Probing.  The greatest
   benefit of RLOC-Probing is that it can handle many failure scenarios
   allowing the ITR to determine when the path to a specific Locator is
   reachable or has become unreachable, thus providing a robust
   mechanism for switching to using another Locator from the cached
   Locator.  RLOC-Probing can also provide rough Round-Trip Time (RTT)
   estimates between a pair of Locators, which can be useful for network
   management purposes as well as for selecting low delay paths.  The
   major disadvantage of RLOC-Probing is in the number of control
   messages required and the amount of bandwidth used to obtain those
   benefits, especially if the requirement for failure detection times
   is very small.

   Continued research and testing will attempt to characterize the
   tradeoffs of failure detection times versus message overhead.

Top      Up      ToC       Page 49 
6.4.  EID Reachability within a LISP Site

   A site may be multihomed using two or more ETRs.  The hosts and
   infrastructure within a site will be addressed using one or more
   EID-Prefixes that are mapped to the RLOCs of the relevant ETRs in the
   mapping system.  One possible failure mode is for an ETR to lose
   reachability to one or more of the EID-Prefixes within its own site.
   When this occurs when the ETR sends Map-Replies, it can clear the
   R-bit associated with its own Locator.  And when the ETR is also an
   ITR, it can clear its Locator-Status-Bit in the encapsulation data

   It is recognized that there are no simple solutions to the site
   partitioning problem because it is hard to know which part of the
   EID-Prefix range is partitioned and which Locators can reach any
   sub-ranges of the EID-Prefixes.  This problem is under investigation
   with the expectation that experiments will tell us more.  Note that
   this is not a new problem introduced by the LISP architecture.  The
   problem exists today when a multihomed site uses BGP to advertise its
   reachability upstream.

6.5.  Routing Locator Hashing

   When an ETR provides an EID-to-RLOC mapping in a Map-Reply message to
   a requesting ITR, the Locator-Set for the EID-Prefix may contain
   different Priority values for each locator address.  When more than
   one best Priority Locator exists, the ITR can decide how to load-
   share traffic against the corresponding Locators.

   The following hash algorithm may be used by an ITR to select a
   Locator for a packet destined to an EID for the EID-to-RLOC mapping:

   1.  Either a source and destination address hash or the traditional
       5-tuple hash can be used.  The traditional 5-tuple hash includes
       the source and destination addresses; source and destination TCP,
       UDP, or Stream Control Transmission Protocol (SCTP) port numbers;
       and the IP protocol number field or IPv6 next-protocol fields of
       a packet that a host originates from within a LISP site.  When a
       packet is not a TCP, UDP, or SCTP packet, the source and
       destination addresses only from the header are used to compute
       the hash.

   2.  Take the hash value and divide it by the number of Locators
       stored in the Locator-Set for the EID-to-RLOC mapping.

   3.  The remainder will yield a value of 0 to "number of Locators
       minus 1".  Use the remainder to select the Locator in the

Top      Up      ToC       Page 50 
   Note that when a packet is LISP encapsulated, the source port number
   in the outer UDP header needs to be set.  Selecting a hashed value
   allows core routers that are attached to Link Aggregation Groups
   (LAGs) to load-split the encapsulated packets across member links of
   such LAGs.  Otherwise, core routers would see a single flow, since
   packets have a source address of the ITR, for packets that are
   originated by different EIDs at the source site.  A suggested setting
   for the source port number computed by an ITR is a 5-tuple hash
   function on the inner header, as described above.

   Many core router implementations use a 5-tuple hash to decide how to
   balance packet load across members of a LAG.  The 5-tuple hash
   includes the source and destination addresses of the packet and the
   source and destination ports when the protocol number in the packet
   is TCP or UDP.  For this reason, UDP encoding is used for LISP

6.6.  Changing the Contents of EID-to-RLOC Mappings

   Since the LISP architecture uses a caching scheme to retrieve and
   store EID-to-RLOC mappings, the only way an ITR can get a more up-to-
   date mapping is to re-request the mapping.  However, the ITRs do not
   know when the mappings change, and the ETRs do not keep track of
   which ITRs requested its mappings.  For scalability reasons, we want
   to maintain this approach but need to provide a way for ETRs to
   change their mappings and inform the sites that are currently
   communicating with the ETR site using such mappings.

   When adding a new Locator record in lexicographic order to the end of
   a Locator-Set, it is easy to update mappings.  We assume that new
   mappings will maintain the same Locator ordering as the old mapping
   but will just have new Locators appended to the end of the list.  So,
   some ITRs can have a new mapping while other ITRs have only an old
   mapping that is used until they time out.  When an ITR has only an
   old mapping but detects bits set in the Locator-Status-Bits that
   correspond to Locators beyond the list it has cached, it simply
   ignores them.  However, this can only happen for locator addresses
   that are lexicographically greater than the locator addresses in the
   existing Locator-Set.

   When a Locator record is inserted in the middle of a Locator-Set, to
   maintain lexicographic order, the SMR procedure in Section 6.6.2 is
   used to inform ITRs and PITRs of the new Locator-Status-Bit mappings.

   When a Locator record is removed from a Locator-Set, ITRs that have
   the mapping cached will not use the removed Locator because the xTRs
   will set the Locator-Status-Bit to 0.  So, even if the Locator is in
   the list, it will not be used.  For new mapping requests, the xTRs

Top      Up      ToC       Page 51 
   can set the Locator AFI to 0 (indicating an unspecified address), as
   well as setting the corresponding Locator-Status-Bit to 0.  This
   forces ITRs with old or new mappings to avoid using the removed

   If many changes occur to a mapping over a long period of time, one
   will find empty record slots in the middle of the Locator-Set and new
   records appended to the Locator-Set.  At some point, it would be
   useful to compact the Locator-Set so the Locator-Status-Bit settings
   can be efficiently packed.

   We propose here three approaches for Locator-Set compaction: one
   operational mechanism and two protocol mechanisms.  The operational
   approach uses a clock sweep method.  The protocol approaches use the
   concept of Solicit-Map-Requests and Map-Versioning.

6.6.1.  Clock Sweep

   The clock sweep approach uses planning in advance and the use of
   count-down TTLs to time out mappings that have already been cached.
   The default setting for an EID-to-RLOC mapping TTL is 24 hours.  So,
   there is a 24-hour window to time out old mappings.  The following
   clock sweep procedure is used:

   1.  24 hours before a mapping change is to take effect, a network
       administrator configures the ETRs at a site to start the clock
       sweep window.

   2.  During the clock sweep window, ETRs continue to send Map-Reply
       messages with the current (unchanged) mapping records.  The TTL
       for these mappings is set to 1 hour.

   3.  24 hours later, all previous cache entries will have timed out,
       and any active cache entries will time out within 1 hour.  During
       this 1-hour window, the ETRs continue to send Map-Reply messages
       with the current (unchanged) mapping records with the TTL set to
       1 minute.

   4.  At the end of the 1-hour window, the ETRs will send Map-Reply
       messages with the new (changed) mapping records.  So, any active
       caches can get the new mapping contents right away if not cached,
       or in 1 minute if they had the mapping cached.  The new mappings
       are cached with a TTL equal to the TTL in the Map-Reply.

Top      Up      ToC       Page 52 
6.6.2.  Solicit-Map-Request (SMR)

   Soliciting a Map-Request is a selective way for ETRs, at the site
   where mappings change, to control the rate they receive requests for
   Map-Reply messages.  SMRs are also used to tell remote ITRs to update
   the mappings they have cached.

   Since the ETRs don't keep track of remote ITRs that have cached their
   mappings, they do not know which ITRs need to have their mappings
   updated.  As a result, an ETR will solicit Map-Requests (called an
   SMR message) from those sites to which it has been sending
   encapsulated data for the last minute.  In particular, an ETR will
   send an SMR to an ITR to which it has recently sent encapsulated

   An SMR message is simply a bit set in a Map-Request message.  An ITR
   or PITR will send a Map-Request when they receive an SMR message.
   Both the SMR sender and the Map-Request responder MUST rate-limit
   these messages.  Rate-limiting can be implemented as a global rate-
   limiter or one rate-limiter per SMR destination.

   The following procedure shows how an SMR exchange occurs when a site
   is doing Locator-Set compaction for an EID-to-RLOC mapping:

   1.  When the database mappings in an ETR change, the ETRs at the site
       begin to send Map-Requests with the SMR bit set for each Locator
       in each Map-Cache entry the ETR caches.

   2.  A remote ITR that receives the SMR message will schedule sending
       a Map-Request message to the source locator address of the SMR
       message or to the mapping database system.  A newly allocated
       random nonce is selected, and the EID-Prefix used is the one
       copied from the SMR message.  If the source Locator is the only
       Locator in the cached Locator-Set, the remote ITR SHOULD send a
       Map-Request to the database mapping system just in case the
       single Locator has changed and may no longer be reachable to
       accept the Map-Request.

   3.  The remote ITR MUST rate-limit the Map-Request until it gets a
       Map-Reply while continuing to use the cached mapping.  When
       Map-Versioning as described in Section 6.6.3 is used, an SMR
       sender can detect if an ITR is using the most up-to-date database

   4.  The ETRs at the site with the changed mapping will reply to the
       Map-Request with a Map-Reply message that has a nonce from the
       SMR-invoked Map-Request.  The Map-Reply messages SHOULD be rate-
       limited.  This is important to avoid Map-Reply implosion.

Top      Up      ToC       Page 53 
   5.  The ETRs at the site with the changed mapping record the fact
       that the site that sent the Map-Request has received the new
       mapping data in the Map-Cache entry for the remote site so the
       Locator-Status-Bits are reflective of the new mapping for packets
       going to the remote site.  The ETR then stops sending SMR

   Experimentation is in progress to determine the appropriate rate-
   limit parameters.

   For security reasons, an ITR MUST NOT process unsolicited
   Map-Replies.  To avoid Map-Cache entry corruption by a third party, a
   sender of an SMR-based Map-Request MUST be verified.  If an ITR
   receives an SMR-based Map-Request and the source is not in the
   Locator-Set for the stored Map-Cache entry, then the responding
   Map-Request MUST be sent with an EID destination to the mapping
   database system.  Since the mapping database system is a more secure
   way to reach an authoritative ETR, it will deliver the Map-Request to
   the authoritative source of the mapping data.

   When an ITR receives an SMR-based Map-Request for which it does not
   have a cached mapping for the EID in the SMR message, it MAY not send
   an SMR-invoked Map-Request.  This scenario can occur when an ETR
   sends SMR messages to all Locators in the Locator-Set it has stored
   in its map-cache but the remote ITRs that receive the SMR may not be
   sending packets to the site.  There is no point in updating the ITRs
   until they need to send, in which case they will send Map-Requests to
   obtain a Map-Cache entry.

6.6.3.  Database Map-Versioning

   When there is unidirectional packet flow between an ITR and ETR, and
   the EID-to-RLOC mappings change on the ETR, it needs to inform the
   ITR so encapsulation to a removed Locator can stop and can instead be
   started to a new Locator in the Locator-Set.

   An ETR, when it sends Map-Reply messages, conveys its own Map-Version
   Number.  This is known as the Destination Map-Version Number.  ITRs
   include the Destination Map-Version Number in packets they
   encapsulate to the site.  When an ETR decapsulates a packet and
   detects that the Destination Map-Version Number is less than the
   current version for its mapping, the SMR procedure described in
   Section 6.6.2 occurs.

Top      Up      ToC       Page 54 
   An ITR, when it encapsulates packets to ETRs, can convey its own
   Map-Version Number.  This is known as the Source Map-Version Number.
   When an ETR decapsulates a packet and detects that the Source
   Map-Version Number is greater than the last Map-Version Number sent
   in a Map-Reply from the ITR's site, the ETR will send a Map-Request
   to one of the ETRs for the source site.

   A Map-Version Number is used as a sequence number per EID-Prefix, so
   values that are greater are considered to be more recent.  A value of
   0 for the Source Map-Version Number or the Destination Map-Version
   Number conveys no versioning information, and an ITR does no
   comparison with previously received Map-Version Numbers.

   A Map-Version Number can be included in Map-Register messages as
   well.  This is a good way for the Map-Server to assure that all ETRs
   for a site registering to it will be synchronized according to
   Map-Version Number.

   See [RFC6834] for a more detailed analysis and description of
   Database Map-Versioning.

7.  Router Performance Considerations

   LISP is designed to be very "hardware-based forwarding friendly".  A
   few implementation techniques can be used to incrementally implement

   o  When a tunnel-encapsulated packet is received by an ETR, the outer
      destination address may not be the address of the router.  This
      makes it challenging for the control plane to get packets from the
      hardware.  This may be mitigated by creating special Forwarding
      Information Base (FIB) entries for the EID-Prefixes of EIDs served
      by the ETR (those for which the router provides an RLOC
      translation).  These FIB entries are marked with a flag indicating
      that control-plane processing should be performed.  The forwarding
      logic of testing for particular IP protocol number values is not
      necessary.  There are a few proven cases where no changes to
      existing deployed hardware were needed to support the LISP data-

   o  On an ITR, prepending a new IP header consists of adding more
      octets to a MAC rewrite string and prepending the string as part
      of the outgoing encapsulation procedure.  Routers that support
      Generic Routing Encapsulation (GRE) tunneling [RFC2784] or 6to4
      tunneling [RFC3056] may already support this action.

Top      Up      ToC       Page 55 
   o  A packet's source address or interface the packet was received on
      can be used to select VRF (Virtual Routing/Forwarding).  The VRF's
      routing table can be used to find EID-to-RLOC mappings.

   For performance issues related to map-cache management, see
   Section 12.

8.  Deployment Scenarios

   This section will explore how and where ITRs and ETRs can be deployed
   and will discuss the pros and cons of each deployment scenario.  For
   a more detailed deployment recommendation, refer to [LISP-DEPLOY].

   There are two basic deployment tradeoffs to consider: centralized
   versus distributed caches; and flat, Recursive, or Re-encapsulating
   Tunneling.  When deciding on centralized versus distributed caching,
   the following issues should be considered:

   o  Are the Tunnel Routers spread out so that the caches are spread
      across all the memories of each router?  A centralized cache is
      when an ITR keeps a cache for all the EIDs it is encapsulating to.
      The packet takes a direct path to the destination Locator.  A
      distributed cache is when an ITR needs help from other
      re-encapsulating routers because it does not store all the cache
      entries for the EIDs it is encapsulating to.  So, the packet takes
      a path through re-encapsulating routers that have a different set
      of cache entries.

   o  Should management "touch points" be minimized by only choosing a
      few Tunnel Routers, just enough for redundancy?

   o  In general, using more ITRs doesn't increase management load,
      since caches are built and stored dynamically.  On the other hand,
      using more ETRs does require more management, since EID-Prefix-to-
      RLOC mappings need to be explicitly configured.

   When deciding on flat, Recursive, or Re-encapsulating Tunneling, the
   following issues should be considered:

   o  Flat tunneling implements a single tunnel between the source site
      and destination site.  This generally offers better paths between
      sources and destinations with a single tunnel path.

   o  Recursive Tunneling is when tunneled traffic is again further
      encapsulated in another tunnel, either to implement VPNs or to
      perform Traffic Engineering.  When doing VPN-based tunneling, the
      site has some control, since the site is prepending a new tunnel
      header.  In the case of TE-based tunneling, the site may have

Top      Up      ToC       Page 56 
      control if it is prepending a new tunnel header, but if the site's
      ISP is doing the TE, then the site has no control.  Recursive
      Tunneling generally will result in suboptimal paths but with the
      benefit of steering traffic to parts of the network that have more
      resources available.

   o  The technique of re-encapsulation ensures that packets only
      require one tunnel header.  So, if a packet needs to be re-routed,
      it is first decapsulated by the ETR and then re-encapsulated with
      a new tunnel header using a new RLOC.

   The next sub-sections will examine where Tunnel Routers can reside in
   the network.

8.1.  First-Hop/Last-Hop Tunnel Routers

   By locating Tunnel Routers close to hosts, the EID-Prefix set is at
   the granularity of an IP subnet.  So, at the expense of more
   EID-Prefix-to-RLOC sets for the site, the caches in each Tunnel
   Router can remain relatively small.  But caches always depend on the
   number of non-aggregated EID destination flows active through these
   Tunnel Routers.

   With more Tunnel Routers doing encapsulation, the increase in control
   traffic grows as well: since the EID granularity is greater, more
   Map-Requests and Map-Replies are traveling between more routers.

   The advantage of placing the caches and databases at these stub
   routers is that the products deployed in this part of the network
   have better price-memory ratios than their core router counterparts.
   Memory is typically less expensive in these devices, and fewer routes
   are stored (only IGP routes).  These devices tend to have excess
   capacity, both for forwarding and routing states.

   LISP functionality can also be deployed in edge switches.  These
   devices generally have layer-2 ports facing hosts and layer-3 ports
   facing the Internet.  Spare capacity is also often available in these

8.2.  Border/Edge Tunnel Routers

   Using Customer Edge (CE) routers for tunnel endpoints allows the EID
   space associated with a site to be reachable via a small set of RLOCs
   assigned to the CE routers for that site.  This is the default
   behavior envisioned in the rest of this specification.

Top      Up      ToC       Page 57 
   This offers the opposite benefit of the first-hop/last-hop Tunnel
   Router scenario: the number of mapping entries and network management
   touch points is reduced, allowing better scaling.

   One disadvantage is that fewer network resources are used to reach
   host endpoints, thereby centralizing the point-of-failure domain and
   creating network choke points at the CE router.

   Note that more than one CE router at a site can be configured with
   the same IP address.  In this case, an RLOC is an anycast address.
   This allows resilience between the CE routers.  That is, if a CE
   router fails, traffic is automatically routed to the other routers
   using the same anycast address.  However, this comes with the
   disadvantage where the site cannot control the entrance point when
   the anycast route is advertised out from all border routers.  Another
   disadvantage of using anycast Locators is the limited advertisement
   scope of /32 (or /128 for IPv6) routes.

8.3.  ISP Provider Edge (PE) Tunnel Routers

   The use of ISP PE routers as tunnel endpoint routers is not the
   typical deployment scenario envisioned in this specification.  This
   section attempts to capture some of the reasoning behind this
   preference for implementing LISP on CE routers.

   The use of ISP PE routers as tunnel endpoint routers gives an ISP,
   rather than a site, control over the location of the egress tunnel
   endpoints.  That is, the ISP can decide whether the tunnel endpoints
   are in the destination site (in either CE routers or last-hop routers
   within a site) or at other PE edges.  The advantage of this case is
   that two tunnel headers can be avoided.  By having the PE be the
   first router on the path to encapsulate, it can choose a TE path
   first, and the ETR can decapsulate and re-encapsulate for a tunnel to
   the destination end site.

   An obvious disadvantage is that the end site has no control over
   where its packets flow or over the RLOCs used.  Other disadvantages
   include difficulty in synchronizing path liveness updates between CE
   and PE routers.

   As mentioned in earlier sections, a combination of these scenarios is
   possible at the expense of extra packet header overhead; if both site
   and provider want control, then Recursive or Re-encapsulating Tunnels
   are used.

Top      Up      ToC       Page 58 
8.4.  LISP Functionality with Conventional NATs

   LISP routers can be deployed behind Network Address Translator (NAT)
   devices to provide the same set of packet services hosts have today
   when they are addressed out of private address space.

   It is important to note that a locator address in any LISP control
   message MUST be a globally routable address and therefore SHOULD NOT
   contain [RFC1918] addresses.  If a LISP router is configured with
   private addresses, they MUST be used only in the outer IP header so
   the NAT device can translate properly.  Otherwise, EID addresses MUST
   be translated before encapsulation is performed.  Both NAT
   translation and LISP encapsulation functions could be co-located in
   the same device.

   More details on LISP address translation can be found in [RFC6832].

8.5.  Packets Egressing a LISP Site

   When a LISP site is using two ITRs for redundancy, the failure of one
   ITR will likely shift outbound traffic to the second.  This second
   ITR's cache may not be populated with the same EID-to-RLOC mapping
   entries as the first.  If this second ITR does not have these
   mappings, traffic will be dropped while the mappings are retrieved
   from the mapping system.  The retrieval of these messages may
   increase the load of requests being sent into the mapping system.
   Deployment and experimentation will determine whether this issue
   requires more attention.

9.  Traceroute Considerations

   When a source host in a LISP site initiates a traceroute to a
   destination host in another LISP site, it is highly desirable for it
   to see the entire path.  Since packets are encapsulated from the ITR
   to the ETR, the hop across the tunnel could be viewed as a single
   hop.  However, LISP traceroute will provide the entire path so the
   user can see 3 distinct segments of the path from a source LISP host
   to a destination LISP host:

Top      Up      ToC       Page 59 
      Segment 1 (in source LISP site based on EIDs):

          source host ---> first hop ... next hop ---> ITR

      Segment 2 (in the core network based on RLOCs):

          ITR ---> next hop ... next hop ---> ETR

      Segment 3 (in the destination LISP site based on EIDs):

          ETR ---> next hop ... last hop ---> destination host

   For segment 1 of the path, ICMP Time Exceeded messages are returned
   in the normal manner as they are today.  The ITR performs a TTL
   decrement and tests for 0 before encapsulating.  Therefore, the ITR's
   hop is seen by the traceroute source as having an EID address (the
   address of the site-facing interface).

   For segment 2 of the path, ICMP Time Exceeded messages are returned
   to the ITR because the TTL decrement to 0 is done on the outer
   header, so the destinations of the ICMP messages are the ITR RLOC
   address and the source RLOC address of the encapsulated traceroute
   packet.  The ITR looks inside of the ICMP payload to inspect the
   traceroute source so it can return the ICMP message to the address of
   the traceroute client and also retain the core router IP address in
   the ICMP message.  This is so the traceroute client can display the
   core router address (the RLOC address) in the traceroute output.  The
   ETR returns its RLOC address and responds to the TTL decrement to 0,
   as the previous core routers did.

   For segment 3, the next-hop router downstream from the ETR will be
   decrementing the TTL for the packet that was encapsulated, sent into
   the core, decapsulated by the ETR, and forwarded because it isn't the
   final destination.  If the TTL is decremented to 0, any router on the
   path to the destination of the traceroute, including the next-hop
   router or destination, will send an ICMP Time Exceeded message to the
   source EID of the traceroute client.  The ICMP message will be
   encapsulated by the local ITR and sent back to the ETR in the
   originated traceroute source site, where the packet will be delivered
   to the host.

9.1.  IPv6 Traceroute

   IPv6 traceroute follows the procedure described above, since the
   entire traceroute data packet is included in the ICMP Time Exceeded
   message payload.  Therefore, only the ITR needs to pay special
   attention to forwarding ICMP messages back to the traceroute source.

Top      Up      ToC       Page 60 
9.2.  IPv4 Traceroute

   For IPv4 traceroute, we cannot follow the above procedure, since IPv4
   ICMP Time Exceeded messages only include the invoking IP header and
   8 octets that follow the IP header.  Therefore, when a core router
   sends an IPv4 Time Exceeded message to an ITR, all the ITR has in the
   ICMP payload is the encapsulated header it prepended, followed by a
   UDP header.  The original invoking IP header, and therefore the
   identity of the traceroute source, is lost.

   The solution we propose to solve this problem is to cache traceroute
   IPv4 headers in the ITR and to match them up with corresponding IPv4
   Time Exceeded messages received from core routers and the ETR.  The
   ITR will use a circular buffer for caching the IPv4 and UDP headers
   of traceroute packets.  It will select a 16-bit number as a key to
   find them later when the IPv4 Time Exceeded messages are received.
   When an ITR encapsulates an IPv4 traceroute packet, it will use the
   16-bit number as the UDP source port in the encapsulating header.
   When the ICMP Time Exceeded message is returned to the ITR, the UDP
   header of the encapsulating header is present in the ICMP payload,
   thereby allowing the ITR to find the cached headers for the
   traceroute source.  The ITR puts the cached headers in the payload
   and sends the ICMP Time Exceeded message to the traceroute source
   retaining the source address of the original ICMP Time Exceeded
   message (a core router or the ETR of the site of the traceroute

   The signature of a traceroute packet comes in two forms.  The first
   form is encoded as a UDP message where the destination port is
   inspected for a range of values.  The second form is encoded as an
   ICMP message where the IP identification field is inspected for a
   well-known value.

9.3.  Traceroute Using Mixed Locators

   When either an IPv4 traceroute or IPv6 traceroute is originated and
   the ITR encapsulates it in the other address family header, one
   cannot get all 3 segments of the traceroute.  Segment 2 of the
   traceroute cannot be conveyed to the traceroute source, since it is
   expecting addresses from intermediate hops in the same address format
   for the type of traceroute it originated.  Therefore, in this case,
   segment 2 will make the tunnel look like one hop.  All the ITR has to
   do to make this work is to not copy the inner TTL to the outer,
   encapsulating header's TTL when a traceroute packet is encapsulated
   using an RLOC from a different address family.  This will cause no
   TTL decrement to 0 to occur in core routers between the ITR and ETR.

Top      Up      ToC       Page 61 
10.  Mobility Considerations

   There are several kinds of mobility, of which only some might be of
   concern to LISP.  Essentially, they are as follows.

10.1.  Site Mobility

   A site wishes to change its attachment points to the Internet, and
   its LISP Tunnel Routers will have new RLOCs when it changes upstream
   providers.  Changes in EID-to-RLOC mappings for sites are expected to
   be handled by configuration, outside of LISP.

10.2.  Slow Endpoint Mobility

   An individual endpoint wishes to move but is not concerned about
   maintaining session continuity.  Renumbering is involved.  LISP can
   help with the issues surrounding renumbering [RFC4192] [LISA96] by
   decoupling the address space used by a site from the address spaces
   used by its ISPs [RFC4984].

10.3.  Fast Endpoint Mobility

   Fast endpoint mobility occurs when an endpoint moves relatively
   rapidly, changing its IP-layer network attachment point.  Maintenance
   of session continuity is a goal.  This is where the Mobile IPv4
   [RFC5944] and Mobile IPv6 [RFC6275] [RFC4866] mechanisms are used and
   primarily where interactions with LISP need to be explored.

   The problem is that as an endpoint moves, it may require changes to
   the mapping between its EID and a set of RLOCs for its new network
   location.  When this is added to the overhead of Mobile IP binding
   updates, some packets might be delayed or dropped.

   In IPv4 mobility, when an endpoint is away from home, packets to it
   are encapsulated and forwarded via a home agent that resides in the
   home area the endpoint's address belongs to.  The home agent will
   encapsulate and forward packets either directly to the endpoint or to
   a foreign agent that resides where the endpoint has moved to.
   Packets from the endpoint may be sent directly to the correspondent
   node, may be sent via the foreign agent, or may be reverse-tunneled
   back to the home agent for delivery to the mobile node.  As the
   mobile node's EID or available RLOC changes, LISP EID-to-RLOC

Top      Up      ToC       Page 62 
   mappings are required for communication between the mobile node and
   the home agent, whether via the foreign agent or not.  As a mobile
   endpoint changes networks, up to three LISP mapping changes may be

   o  The mobile node moves from an old location to a new visited
      network location and notifies its home agent that it has done so.
      The Mobile IPv4 control packets the mobile node sends pass through
      one of the new visited network's ITRs, which needs an EID-to-RLOC
      mapping for the home agent.

   o  The home agent might not have the EID-to-RLOC mappings for the
      mobile node's "care-of" address or its foreign agent in the new
      visited network, in which case it will need to acquire them.

   o  When packets are sent directly to the correspondent node, it may
      be that no traffic has been sent from the new visited network to
      the correspondent node's network, and the new visited network's
      ITR will need to obtain an EID-to-RLOC mapping for the
      correspondent node's site.

   In addition, if the IPv4 endpoint is sending packets from the new
   visited network using its original EID, then LISP will need to
   perform a route-returnability check on the new EID-to-RLOC mapping
   for that EID.

   In IPv6 mobility, packets can flow directly between the mobile node
   and the correspondent node in either direction.  The mobile node uses
   its "care-of" address (EID).  In this case, the route-returnability
   check would not be needed but one more LISP mapping lookup may be
   required instead:

   o  As above, three mapping changes may be needed for the mobile node
      to communicate with its home agent and to send packets to the
      correspondent node.

   o  In addition, another mapping will be needed in the correspondent
      node's ITR, in order for the correspondent node to send packets to
      the mobile node's "care-of" address (EID) at the new network

   When both endpoints are mobile, the number of potential mapping
   lookups increases accordingly.

   As a mobile node moves, there are not only mobility state changes in
   the mobile node, correspondent node, and home agent, but also state
   changes in the ITRs and ETRs for at least some EID-Prefixes.

Top      Up      ToC       Page 63 
   The goal is to support rapid adaptation, with little delay or packet
   loss for the entire system.  Also, IP mobility can be modified to
   require fewer mapping changes.  In order to increase overall system
   performance, there may be a need to reduce the optimization of one
   area in order to place fewer demands on another.

   In LISP, one possibility is to "glean" information.  When a packet
   arrives, the ETR could examine the EID-to-RLOC mapping and use that
   mapping for all outgoing traffic to that EID.  It can do this after
   performing a route-returnability check, to ensure that the new
   network location does have an internal route to that endpoint.
   However, this does not cover the case where an ITR (the node assigned
   the RLOC) at the mobile-node location has been compromised.

   Mobile IP packet exchange is designed for an environment in which all
   routing information is disseminated before packets can be forwarded.
   In order to allow the Internet to grow to support expected future
   use, we are moving to an environment where some information may have
   to be obtained after packets are in flight.  Modifications to IP
   mobility should be considered in order to optimize the behavior of
   the overall system.  Anything that decreases the number of new
   EID-to-RLOC mappings needed when a node moves, or maintains the
   validity of an EID-to-RLOC mapping for a longer time, is useful.

10.4.  Fast Network Mobility

   In addition to endpoints, a network can be mobile, possibly changing
   xTRs.  A "network" can be as small as a single router and as large as
   a whole site.  This is different from site mobility in that it is
   fast and possibly short-lived, but different from endpoint mobility
   in that a whole prefix is changing RLOCs.  However, the mechanisms
   are the same, and there is no new overhead in LISP.  A map request
   for any endpoint will return a binding for the entire mobile prefix.

   If mobile networks become a more common occurrence, it may be useful
   to revisit the design of the mapping service and allow for dynamic
   updates of the database.

   The issue of interactions between mobility and LISP needs to be
   explored further.  Specific improvements to the entire system will
   depend on the details of mapping mechanisms.  Mapping mechanisms
   should be evaluated on how well they support session continuity for
   mobile nodes.

Top      Up      ToC       Page 64 
10.5.  LISP Mobile Node Mobility

   A mobile device can use the LISP infrastructure to achieve mobility
   by implementing the LISP encapsulation and decapsulation functions
   and acting as a simple ITR/ETR.  By doing this, such a "LISP mobile
   node" can use topologically independent EID IP addresses that are not
   advertised into and do not impose a cost on the global routing
   system.  These EIDs are maintained at the edges of the mapping system
   (in LISP Map-Servers and Map-Resolvers) and are provided on demand to
   only the correspondents of the LISP mobile node.

   Refer to [LISP-MN] for more details.

(page 64 continued on part 4)

Next RFC Part