Subject: [RAM] How does LISP recognise which IP addresses to query mapping for?

From: Robin Whittle <[email-masked]>
Date: Sat, 14 Apr 2007 14:34:03 +1000

This is based on IPv4 and my understanding of LISP, which may be faulty.

In an IPv4 setting, assuming the current /24 granularity of whether
the addresses are advertised in BGP or not, I am curious about how a
LISP implementation would handle packets which were addressed to
addresses not advertised in BGP.

I am thinking mainly of LISP 2 or 3 similar - where the ITR decides
to look up the mapping for a particular IP address via DNS or some
other mechanism.

I don't see how LISP 1 helps reduce the load of growing numbers of
prefixes in the BGP routing system.  I find it hard to imagine the
development of a global alternative routing system for LISP 1.5 and
 I don't see how LISP 1.5 could be deployed incrementally, since the
alternative routing system would need to be in place and LISP
routers would need to be in practically every edge network, to
ensure continued universal reachability of any addresses which were
taken out of the BGP system and accessed as LISP EIDs instead.

I think LISP 2 or 3 could have significant benefits, but I think
they too would require a complete upgrade, since no-one would want
to make their IP addresses inaccessible to the fraction of edge
networks which had not installed LISP routers.  (Unless there is a
way of catching the packets in the DFZ, with special LISP routers -
but then someone would need to pay for that, when it should be the
responsibility of each edge network to pay for its own LISP
capabilities.)

I am mainly thinking of a complete upgrade, over 5 or so years, to
border routers and transit routers, with SRAM forwarding in border
and transit routers and LISP 2/3 functions in the border routers and
perhaps in routers within the edge networks.  However, the questions
below assume only LISP 2 or 3, not SRAM forwarding.

I will refer to a "central mapping database", which could be
implemented via DNS and/or in some other ways.

Here is why I think the central database needs to be able to tell
the ITR a definite "No" if the requested IP address is not mapped by
the LISP system, and to tell the ITR the prefix which this address
is part of, for which the same answer applies.  (I assume that a
response returning mapping would also indicate the enclosing prefix,
as with the 5 bit EID Mask length and 32 bit EID prefix in the
draft-farinacci-lisp-00.)

I also think there needs to be a TTL or similar - to tell the ITR
how long to cache this information for.  (I don't see a TTL in the
ICMP "Control-Plane Packet Format in draft-farinacci-lisp-00 - but
it strikes me that one would be desirable.)

If the database simply gave no response to a query about an address
which was not mapped as an EID by LISP, then I think there would be
problems:

Consider the ITR receiving a packet which is addressed to some
prefix which it knows is not advertised in the global BGP system.

It sends a request to the database.  If the only way the database
can answer "No" is to not respond, then the ITR has to record that
this particular IP address has no LISP mapping, so the packet should
be dropped.  However, the ITR also needs to remember this for that
IP address, for some configurable time, to prevent it repeating the
query when another packet arrives for this address.  The amount of
state to be stored could get out of hand if it was repeated on a
large number of IP addresses, as would happen with a user scanning a
large number of IP addresses for some reason.

If the database always responded by saying "No, this address is not
a LISP EID and neither is this prefix, of which it is a member."
with a TTL such as an hour or a day, then the ITR can then avoid
making similar queries whenever it gets packets addressed to this
prefix.

It might be helpful if the central database maintained a bit-map
file, with one bit for each of the 14.5 million /24 prefixes, where
a '1' means that one or more IP addresses in the corresponding /24
was mapped as a LISP EID.  The ITRs could download this at boot
time.  It is 1.8Mbyte and would compress to much smaller than this.
 The ITRs could periodically request changes, or receive them on a
push basis, either directly from the central database or via some
special form of BGP update.

This would save the ITRs from making queries whenever they
encountered a packet addressed to some /24 which was not routable
via BGP.  Alternatively, if the negative answers had long TTLs and
covered large ranges of addresses, after a while, each ITR would
accumulate these responses and so cover most of the IP address.
However, assuming that in the future there will will be lots
(hundreds of thousands) of pockets of IP addresses used for LISP
interspersed with ranges used for BGP, then this wouldn't work so
well, and downloading and updating a single bit map mask might be
more efficient.

 - Robin

  http://tools.ietf.org/html/draft-whittle-sram-ip-forwarding-01
  http://www.firstpr.com.au/ip/sram-ip-forwarding/

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 15 Apr 2007 23:35:44 -0700

> addresses not advertised in BGP.

Not clear what your question here is. You could be saying how does  
LISP encapsulate a packet when received with a DA that is not in BGP.  
Or what happens when LISP tries to encapsulate with a locator address  
that is not in BGP.

If the former, that would be the PI case situation. Which means, you  
go get the mapping and until you get it, you don't forward packets.  
Or you do a LISP 1.5 and route the packet with the PI address on  
another topology that does carry the address in routing (but not in  
the BGP core).

If the later, then it is a misconfiguration. An ETR must be reachable  
via the BGP core. The ETR possesses a locator address.

> prefixes in the BGP routing system.  I find it hard to imagine the

It doesn't. It's a phase 0 prototype effort.

> development of a global alternative routing system for LISP 1.5 and

It is a simpler one since the advertisement of EID-prefixes are free  
of topological or policy constraints. So better aggregation can be  
achieved with very low entropy.

> taken out of the BGP system and accessed as LISP EIDs instead.

It is done incrementally because if you route to a destination site  
which is not LISP enabled, the ITR in the source site which is LISP- 
enabled, will not learn a mapping so it will not encapsulate the  
packet and send it natively like it does today.

> they too would require a complete upgrade, since no-one would want

What do you mean by complete?

> responsibility of each edge network to pay for its own LISP

In the transition case, where a new site still needs to put their  
routes in the BGP-core, the site still gets ingress traffic  
engineering. So it's not just one problem we are focusing on.

> below assume only LISP 2 or 3, not SRAM forwarding.

Regardless of the type of forwarding engine you have, if an EID- 
prefix is put in what we know today as the FIB, and the next-hop  
encapsulation is IP-in-IP, we can forward LISP encapsulated packets  
today in hardware.

We can do this with GRE and L2TPv3 in shipping routers today.

> draft-farinacci-lisp-00.)

Sure, this can be done.

> it strikes me that one would be desirable.)

Yes, we will add this in the next draft. With a query/reply protocol,  
we need a TTL. With a push protocol, we may not need one.

> large number of IP addresses for some reason.

It has been suggested, to avoid these class or problems, is to have  
the ISP deploy a proxy LISP ETR on behalf a sites that do not have  
LISP enabled.

Dino

---

From: Robin Whittle <[email-masked]>
Date: Tue, 17 Apr 2007 13:49:29 +1000

Thanks Dino for your answers.  Here is what I meant to say in my
first question.

In the case of IPv4, with LISP 2 or 3, which of these three (maybe
all three, or some others) approaches would be used by the ITR to
process each incoming packet?

1 - A single FIB which determines it is to be, for instance:

    a - Forwarded to interface 0.
    b - Forwarded to interface 1 etc.

    f - LISP encapsulated.

    That is, one set of rules which the destination address is
    tested against which implements the BGP FIB and the prefixes
    which the ITR knows about which are subject to LISP mapping.

2 - Firstly send the packet to FIB for BGP routes.

    If the packet fails to match that, then send it to a second set
    of rules which matches all the prefixes the ITR knows about
    which are LISP mapped.

3 - Alternatively, as 2, but try the LISP rules and then the
    BGP rules.

(There could also be a set of rules which specify which addresses
are known not to be LISP-mapped, but which are also currently, not
in the BGP global routing table - to prevent the repeated generation
of queries.)

Since the LISP mapping rules could be quite numerous and subject to
rapid change, there might be problems integrating them into a single
FIB function with the BGP routes, if each update to that FIB
involved lengthy computations and/or rewriting a lot of data.

In all cases, if the packet matches neither set of rules, I guess
there needs to be a set of prefixes which the ITR currently knows
there are no LISP mappings for, and so not to generate a query
to the central database about.  (Alternatively, the set of LISP
rules could specify, for some prefixes, that there was no LISP mapping.)

Failing a match on all three of these sets of rules, I understand
the packet should generate a query to the central database.
Although the packet will probably be dropped, a subsequent packet to
this address may find that a new rule as been added which causes it
to be LISP encapsulated.

RW>> I don't see how LISP 1.5 could be deployed incrementally,
  >> since the alternative routing system would need to be in
  >> place and LISP routers would need to be in practically
  >> every edge network, to ensure continued universal reachability
  >> of any addresses which were taken out of the BGP system and
  >> accessed as LISP EIDs instead.

> It is done incrementally because if you route to a destination
> site which is not LISP enabled, the ITR in the source site which
> is LISP-enabled, will not learn a mapping so it will not
> encapsulate the packet and send it natively like it does today.

What I mean to ask is this:

Lets say there is an attempt to introduce LISP 1.5 incrementally, on
the basis of benefits as deployment increases, rather than purely
because we all need to do it by year X or the sky will fall in.  In
this scenario, I think the reasons an edge network would install
LISP routers inside its network and/or at its border(s) would be:

1 - It wanted to have some of its internal IP addresses LISP-mapped
    and so taken out of the BGP system.

or

2 - It didn't want to LISP map any of its IP addresses, but it
    wanted to support local users communicating with LISP-mapped
    IP addresses in other edge networks.

I foresee a chicken and egg situation.  Why would some low-key,
 cost-constrained, just scraping by, edge network install and
properly configure one or more LISP routers unless a significant
proportion of its users complained that sites, mailservers etc. they
want to access have become inaccessible?

At the other end, in a second edge network which was favourably
disposed to LISP, why would they take some of their addresses out of
the BGP system and make them available only via LISP, when they know
that 90%, 20% or even 0.1% of remote users are in networks which
don't provide an ITR which would enable them to access those IP
addresses?

RW>> I think LISP 2 or 3 could have significant benefits, but I
  >> think they too would require a complete upgrade, since no-one
  >> would want

> What do you mean by complete?

I mean a long-term plan, made in 2007 and broadly agreed to in 2008
as being the only viable long-term option for the development of the
Internet's architecture, which ideally involves replacing things
which are going to be replaced anyway (I am thinking border and
transit routers, or at least multihomed border routers and transit
routers), with new things which conform to a specification which
implements the new architecture.

Then, the impetus is "when replacing, make sure the new gear will be
what we want after 2012".  All this gear will be replaced in that
timeframe anyway.  The incremental cost of the new features would
probably be minimal - and far less than keeping on flogging the old
architecture with more and more expensive conventional router
technology.

The impetus is not that doing something today will bring benefits
today or next month - just that we can transition to a new set of
equipment and (I suggest) new arrangements for address management,
arriving at a complete changeover without actually forcibly ripping
out gear which wouldn't have been replaced anyway.

I am currently thinking of an SRAM-based upgrade to border and
transit routers with something like LISP in the border routers, with
an option for pushing LISP functions back into the edge network if
they are too burdensome for the busier edge routers.

  >> to make their IP addresses inaccessible to the fraction of
  >> edge networks which had not installed LISP routers.  (Unless
  >> there is a way of catching the packets in the DFZ, with special
  >> LISP routers - but then someone would need to pay for that,
  >> when it should be the responsibility of each edge network to
  >> pay for its own LISP capabilities.)

> engineering. So it's not just one problem we are focusing on.

I understand that mapping some IP addresses to LISP provides TE
options and multihoming management down to the granularity of a
single IP address - but the addresses are only accessible by users
of edge networks who have installed LISP routers.

I could imagine a LISP 1.5+ upgrade over the replacement cycle, with
the benefits becoming practical only once all edge networks had
upgraded.  But I can't imagine many edge networks wanting to switch
addresses to LISP-accessibility, until essentially all other edge
networks had fully deployed LISP routers.

  >> Here is why I think the central database needs to be able to
  >> tell the ITR a definite "No" if the requested IP address is not
  >> mapped by the LISP system, and to tell the ITR the prefix which
  >> this address is part of, for which the same answer applies.  (I
  >> assume that a response returning mapping would also indicate
  >> the enclosing prefix, as with the 5 bit EID Mask length and 32
  >> bit EID prefix in the draft-farinacci-lisp-00.)

> Sure, this can be done.

OK.

  >> I also think there needs to be a TTL or similar - to tell the
  >> ITR how long to cache this information for.  (I don't see a TTL
  >> in the ICMP "Control-Plane Packet Format in
  >> draft-farinacci-lisp-00 - but it strikes me that one would be
  >> desirable.)

> Yes, we will add this in the next draft. With a query/reply
> protocol, we need a TTL. With a push protocol, we may not need
> one.

I agree.  BTW, the ICMP packet diagram doesn't have realistic bit
lengths for the EID Mask Length, EID Prefix or Routing Locator.

  >> It sends a request to the database.  If the only way the
  >> database can answer "No" is to not respond, then the ITR has to
  >> record that this particular IP address has no LISP mapping, so
  >> the packet should be dropped.  However, the ITR also needs to
  >> remember this for that IP address, for some configurable time,
  >> to prevent it repeating the query when another packet arrives
  >> for this address.  The amount of state to be stored could get
  >> out of hand if it was repeated on a large number of IP
  >> addresses, as would happen with a user scanning a large number
  >> of IP addresses for some reason.

> It has been suggested, to avoid these class or problems, is to
> have the ISP deploy a proxy LISP ETR on behalf a sites that do not
> have LISP enabled.

I don't understand this.  If the ISP runs the edge network, users of
that ISP need to access an ETR so they can access LISP-mapped IP
addresses.  I understand that this has to be achieved by one or more
ETRs inside the edge network, or by the border routers functioning
as ETRs.  I don't know how an ETR could be deployed amongst transit
routers to save an ISP from having to deploy a LISP router, unless
perhaps there was some trick in BGP to route all LISP-mapped
addresses to this "in-the-core" LISP router.

Maybe we are trying to answer different questions - this is a pretty
wide-ranging discussion!

  - Robin