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
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
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
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.
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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.
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.
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-
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.
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
See [RFC6834] for a more detailed analysis and description of
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.
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
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
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
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
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
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.
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
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:
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.
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
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.
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
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
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
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.
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
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.