Re: [rrg] LEIDs, SPI & ordinary IP addresses as both IDs & Locs

[Robin Whittle <[e-mail]>]

Short version: Getting down to brass tacks with the bits in a LISP EID
               address (LEID) or an Ivip SPI address and which bits are
               used by:

                  Ordinary routers via their Algorithm 1 approach to
                  using the destination address as a Locator

                  ITRs and the mapping system for their Algorithm 2
                  approach.

               I described these algorithms in (msg06070).

               Whether the destination address is an EID (Ivip SPI)
               address or not, conventional routers and ITRs use it
               as the packet's destination Locator.


Fred wrote:

RW> Yes.  A LEID (LISP EID) or an Ivip SPI address is exactly the same
RW> as any other global unicast IP address in this respect.  A host may
RW> have one or more global unicast IP addresses and (except for anycast
RW> and fancy things which spread load over back-end servers) each
RW> unique global unicast IP address identifies a single host.

> Not quite; an IP address identifies a single host *interface*.
> You would have to turn to something like the HIP HIT if you
> want a true host identifier.

OK - the IP address identifies not just a single host, but if the host
has multiple physical or logical interfaces, then it also identifies a
specific interface.

Still, the IP address identifies a single host.


RW >>> if the LEID destination address is for a host in a network different
RW >>> from that of the sending host, then for part of the journey to the
RW >>> destination host, the LEID address has its Locator semantics
RW >>> interpreted by a new "Algorithm 2", which ITRs execute.

NC >> An LEID _has no general location semantics_.
NC >>
NC >> The fact that you _always_ _have_ to do a mapping from an LEID, to get
NC >> something that _does_ have full location semantics (the RLOC) is
the surest
NC >> sign of that.

> That's not right. For example, if a hypothetical corporation
> decided to tear down its enterprise network and rebuild it
> from scratch, it could number the entire network out of EID
> space only and never have to deploy a single RLOC internally.
> Enterprise-local communications would then be routed based on
> EIDs only, and they would never have to be mapped to RLOCs.
> It is only for communications extending outside the enterprise
> boundaries that an EID-to-RLOC mapping be necessary. 

Yes - this shows that a packet with an EID address in the destination
field is routable in the destination network just like a packet with any
other kind of IP address which the local routing system recognises with
more specific routes than routes with shorter prefixes which would cause
the packet to be forwarded out of this local routing system.

> So, EIDs are routable (i.e., have location semantics) within a
> certain scope, and in some cases that scope may be quite large.

This is what I am trying to state - and that for the EID subset of
global unicast addresses, there is a second algorithm for interpreting
the locator semantics of the address.

A packet with a LEID (or an Ivip SPI address) in its destination field
is routable just like any other packet, using Algorithm 1, in several
contexts:

  1 - In its destination network, as you described - the packet will be
      forwarded towards and ultimately to the destination host.  As you
      note, from the point of view of the routing system, the packet is
      forwarded to a particular interface which announces that it is the
      proper destination for packets with this destination address.
      Conventional routing systems don't seem to have a notion of
      specific hosts.

  2 - At the ETR - and perhaps in an ISP network between the ETR and
      the destination network - the packet will be forwarded, tunneled
      or whatever towards and ultimately to the destination network.

  3 - Outside these two zones, the packet will be forwarded to the
      nearest ITR.  This may be an ITR in the sending host's end-user
      or ISP network, or in the ISP network of the sending host's
      end-user network.  If the packet gets to a DFZ router before
      being forwarded to an ITR, then it will be forwarded to the
      "nearest" (in BGP terms) PTR (LISP) or DITR (Ivip).

      The fact that there may be multiple ITRs (including PTRs and
      DITRs) advertising a prefix which covers this destination
      address (a "coarse" prefix in LISP, using Dino's recent term or
      a Mapped Address Block in Ivip) does not affect the way the
      Locator function of the destination LEID/SPI address is
      implemented.  All these conventional routers use Algorithm 1.

      This is the same as if the packet was inside an ISP network and
      multiple BRs were advertising either a matching prefix or the
      default route - or if the packet was in the DFZ and there were
      multiple BRs advertising a matching prefix.

In all these cases, "Algorithm 1" is used to "implement the Locator
functionality of the destination address" AKA "interpret the LIED/SPI
address's Locator semantics" as I described in:

  http://www.ietf.org/mail-archive/web/rrg/current/msg06070.html

There is a second context:

  4 - The packet arrives at an ITR.  Now, a second Algorithm 2 is
      used to "implement the Locator functionality of the destination
      address" AKA "interpret the LIED/SPI address's Locator semantics".

Algorithm 2 is different from Algorithm 1.  It relies on cached or
recently obtained and then cached information from outside the ITR.
This is "mapping" information, and its nature, and the details of
Algorithm 2 are quite different from Algorithm 1 and the externally
supplied and then cached information a conventional router uses to
interpret the LEID's "Locator semantics".

But nonetheless, with Algorithm 2, the ITR does rely on the LEID
destination address to be the packet's sole Locator, just as with
Algorithm 1.


Noel wrote:

NC >>> you _always_ _have_ to do a mapping from an LEID, to get
NC >>> something that _does_ have full location semantics (the RLOC)

FT >> if a hypothetical corporation decided to tear down its
FT >> enterprise network and rebuild it from scratch, it could
FT >> number the entire network out of EID space only and never have
FT >> to deploy a single RLOC internally.

> Please note the words "to get something that _does_ have full [i.e.
> Internetwork-wide usability] location semantics".

Fred's example only involves the address being recognised by the local
routing system which contains the destination host.  My discussion is
broader than that.

I believe the LEID (or Ivip SPI address) does have:

   "full [i.e. Internetwork-wide usability] location semantics"

The Locator semantics of the LEID can be interpreted in two different
ways - Algorithm 1 by ordinary routers and Algorithm 2 by ITRs.

Both algorithms work all over the world ("Intenetwork-wide").

Let's look in detail at the components of the LEID address.  I will use
a real IP address: 18.26.0.122 (the mail server Noel's messages come
through) and imagine that this is a LISP EID (LEID) or an Ivip SPI
address.  The host this LEID uniquely Identifies belongs to MIT.  Maybe
the host has other IP addresses, LEID or not, but that doesn't alter the
discussion.

Let's say MIT didn't need all its current 18.0.0.0 /8:

  http://ws.arin.net/whois/?queryinput=18.0.0.0

and moved its hosts down to the bottom eighth of this.  Let's say it
returned the top seven eighths to ARIN and made the bottom eighth a LISP
"coarse" prefix (or an Ivip MAB):  18.0.0.0 /11.   MIT would then run
(or pay someone else to run) PTRs (DITRs) in the DFZ all over the world,
since they want to be able to split this space into large numbers of EID
prefixes (Ivip micronets) and use them at sites in Massachusetts and in
other parts of the world.

The "coarse" (MAB) prefix is 18.0.0.0/11:

         18          0            0          9

               11 1111    1111 2222  2222 2233
  0123 4567  8901 2345    6789 0123  4567 8901

  0001 0010  000x xxxx    xxxx xxxx  xxxx xxxx
  ---- ----  ---

Let's say this particular host is in a /26 EID prefix (micronet) which
is used for some hosts in MIT's Computer Science Lab: 18.26.0.64/26:

               11 1111    1111 2222  2222 2233
  0123 4567  8901 2345    6789 0123  4567 8901

  0001 0010  0001 1010    0000 0000  01xx xxxx
  ---- ----  ---- ----    ---- ----  --

So the LEID destination address 18.26.0.122 has its bits in three
distinct sets:

   G     Global  11 bits 0 - 10
   M     Mapped  15 bits        11 - 25
   L     Local    6 bits                26 - 31

               11 1111    1111 2222  2222 2233
  0123 4567  8901 2345    6789 0123  4567 8901

  0001 0010  0001 1010    0000 0000  0111 1010
  GGGG GGGG  GGG
                M MMMM    MMMM MMMM  MM
                                       LL LLLL


Let's say in the destination network there is a router RX leading to two
LANs:

   LAN-A 18.26.0.64 /27
   LAN-B 18.26.0.96 /27

Our example host is in LAN-B, and router RX uses Algorithm 1 on bits 0
to 26 to determine how to forward the packet.

RX advertises 18.26.0.64 /26 in the local routing system, so once the
packet is decapsulated in the ETR, the ETR forwards it to RX.

    (The local routing system may cover multiple prefixes, and
     may contain routes for a shorter prefix than this LEID prefix
     - such as 18.26.0.0 /23.  In that case, the local routing
     system would cover 512 IPv4 addresses, and this LEID would
     deliver packets for 64 of this set.  Presumably other LEIDs,
     of various lengths, would also deliver packets for the
     remainder of the addresses.)

Here are the various ways the bits in this LEID can be used:

 A - In the DFZ or in all ISP and EUNs (End User Networks) except
     the destination network, the LISP "coarse" prefix (or Ivip MAB)
     18.0.0.0 /11:

                          0001 0010  000x xxxx    xxxx xxxx  xxxx xxxx
         Alg. 1:          GGGG GGGG  GGG

     This gets the packet to a PTR (Ivip DITR), since there are one or
     more PTRs (DITRs) which advertise the "coarse" (MAB) prefix:
     18.0.0.0 /11.


 B - At the ITR, the mapping query involves all 32 bits and the reply
     comes back stating that this address is within a particular /26
     LISP EID prefix (Ivip Micronet), which is mapped to (LISP) one or
     more ETRs or (Ivip) a single ETR address.

        Alg 2:

          All 32 bits   { 0001 0010  0001 1010    0000 0000  0111 1010
          used in       { GGGG GGGG  GGG
          mapping query {               M MMMM    MMMM MMMM  MM
                        {                                      LL LLLL


          Map reply     { 0001 0010  0001 1010    0000 0000  01xx xxxx
          only concerns { GGGG GGGG  GGG
          26 bits       {               M MMMM    MMMM MMMM  MM

     The packet is tunneled to a particular ETR.


 C - At the ETR, there is a more specific route for all addresses in the
     LISP EID prefix (Ivip micronet) 18.26.0.64 /26.  This has
     precedence over the default route or any other shorter prefix.

        Alg 1:          { 0001 0010  0001 1010    0000 0000  01xx xxxx
                        { GGGG GGGG  GGG
                        {               M MMMM    MMMM MMMM  MM

     So the packet does not leave the local routing system - it is not
     forwarded towards the DFZ or to any ITR which might be advertising
     the LISP "coarse" prefix (or Ivip MAB) 18.0.0.0 /11.

 D - Within the local routing system, for instance at router RX:

        Alg 1:          { 0001 0010  0001 1010    0000 0000  011x xxxx
                        { GGGG GGGG  GGG
                        {               M MMMM    MMMM MMMM  MM
                        {                                      L

     27 bits are relevant, because the most-specific prefix matching
     18.26.0.122 happens to be, in this case: 18.26.0.96 /27.

In summary, all routers but ITRs use Algorithm 1 and various numbers of
bits, depending on where the packet is.  These routers do not need to be
modified to handle packets addressed to an LEID address.  They just use
Algorithm 1 as they always did.

The only special things about a packet with an LEID (Ivip SPI) address
in the destination field are:

   1 - When not in the destination network, such a packet will be
       forwarded to an ITR (including a LISP PTR or Ivip DITR) - by all
       routers,  using their conventional Algorithm 1 method of
       implementing this IP address's Locator function.

   2 - When they arrive at the ITR, such packets will have the Locator
       function of their destination address implemented with the
       Algorithm 2 method of mapping lookup (if it was not already
       cached) and then tunneling the packet to an ETR.

Various bits are used in various parts of the routing system.  The ITR
can't know initially what length prefix EID prefix the address matches,
so it sends the entire address to the mapping system.

With both Algorithms 1 and 2, there is nothing innate about the bits:

    0001 0010  0001 1010    0000 0000  0111 1010

which tell any router that the packet needs to go to Massachusetts.

Ordinary routers (including DFZ routers) adapt their FIB to forward the
packet to the best neighbour as part of a broader process of getting the
packet closer to its destination, and finally to its destination host.
The information in the FIB for all routers (except the final one)
doesn't specify anything about the destination physical or logical
interface of the destination host.

Ordinary routers develop the information in their FIBs as part of a
self-organising system - and the router bases its decisions on
information arriving from its neighbours.  When performing Algorithm 1,
there's no need to look up any mapping outside the router in order to
handle the packet correctly.

If the ITR is a NERD ITR (full-database), an APT Default Mapper (also
full-database) or an Ivip ITR directly connected to a full database
query server (or the two are integrated into one host), then to perform
Algorithm 2, the ITR doesn't need to get mapping from anywhere else.  It
already has what it needs.

If the ITR is a caching ITR, then to perform Algorithm 2, if it doesn't
currently have the required mapping cached, then it does need to look up
the mapping and receive a reply before it can handle the packet.

The NERD example shows that Algorithm 2 doesn't necessarily involve an
external mapping lookup.

A NERD ITR has already received information from other devices which it
needs to perform Algorithm 2.  This information is the same for all ITRs
in the world - so the ITR's performance of Algorithm 2 is not at all
dependent on its place in the topology.  This is in contrast with
ordinary routers' Algorithm 1 implementation, where the local
information about how to forward packets matching a given prefix varies
depending on the topological location of the router, since this is how
the BGP or iGP routing protocol works as a self-organising system.

None of these distinctions between Algorithm 1 and Algorithm 2, or the
varying number of bits which are needed at each part of the packet's
journey, alters the fact that the destination address is being used as
the destination Locator.

This is true whether the destination address is within the ordinary
"core" ("RLOC") set of global unicast addresses or whether it is an LEID
(Ivip SPI) address in the scalable "edge" subset.

  - Robin