Subject: [Ila] Scaling mapping systems (was Re: [5gangip] BOF Description)

From: Tom Herbert <[email-masked]>
Date: Sat, 3 Feb 2018 08:50:22 -0800

On Fri, Feb 2, 2018 at 10:37 AM, Dino Farinacci <[email-masked]> wrote:
>
> The question to be answered is if all 10 million need to be stored in one place at the same time.
>
> Lorenzo, do you think the DNS is scaling? And if the mapping system is designed roughly the same way, could it scale?
>
Right, there now are many examples of sharded databases to draw
lessons from. At 10M entries per router, to get to 1B aggregate
mappings in a network that's 100 routers. Assuming a 5x replication
factor then network needs 500 identifier/locator routers. I would
target scaling this by two orders of magnitude within ten years to
accommodate influx of IoT devices and fined grained object addressing
in virtualization. I know this is simplistic math and scaling this is
a hard problem, but I believe it's a solvable problem.

>
> Also, the other point you made about third-party dependency, is a another question about push versus pull style of operation.
>

There is a related question that needs to be addressed and that's
DOSability of a mapping cache.

For instance, from RFC6380:

"6.  The ITR receives the Map-Reply message, parses the message (to
check for format validity), and stores the mapping information from
the packet.  This information is stored in the ITR's EID-to-RLOC
mapping cache.  Note that the map-cache is an on-demand cache.  An ITR
will manage its map-cache in such a way that optimizes for its
resource constraints. "

This on-demand mapping cache is the reason that LISP is not in Linux.
The argument is that it is easily DOSed. A attacker could flood an ITR
with packets to random destinations that would trigger map requests.
If the map requests are rate limited then that could prevent requests
being made for legitimate traffic. If map replies are generated for
the bogus traffic they they could fill up the cache and block out
legitimate users.

I think the the request rate limiting problem can be mitigated by
using a redirect model instead, but I don't have complete answer yet
for the cache exhaustion attack (my patches that would facilitate an
ILA mapping cache we also rejected).

Dino, has this DOS issue been looked at for LISP?

Thanks,
Tom

---

From: Dino Farinacci <[email-masked]>
Date: Sat, 3 Feb 2018 15:26:00 -0800

> a hard problem, but I believe it's a solvable problem.

I think so too and has been an effort of mine for many years. And something I requested and wanted IDEAs to tackle.

> For instance, from RFC6380:

You mean RFC6830. And what you are commenting on below is the map-cache and not the global mapping system. That is the point I want to get Lorenzo’s opinion about.

> This on-demand mapping cache is the reason that LISP is not in Linux.

Right, I realize that. But that is not for architectural design reasons. It’s for Linux implementors idealist reasons. And that is okay.

> The argument is that it is easily DOSed. A attacker could flood an ITR

And I have said dozens (probably more) that a “cache" and a “table” is not different. And you think a “BGP table” cannot be DoSed either?

Having said that, I just don’t want to say everything sucks, so I want to give you a proactive response.

Just like you use white-lists for push based routing protocols (which doesn’t include the link-state protocols), you can use rate-limiting an white-lists for cache population. 

And in 90% of the cases, most ITRs will have default map-cache entries with I’d say on a larger scale deployment pointing to 4 to 8 RLOCs. Those RLOCs go to RTRs that are larger such products to deal with this.

Please note that carrier grade NATs are cached based systems to. Why would they ever get deployed?

> the bogus traffic they they could fill up the cache and block out

Right, I have heard the argument many times. But if you didn’t have a cache, you wouldn’t flee from the problem. And having a cache will allow you to scale better by storing the state in need where you and when you need it.

Geoff Huston showed a decade ago that only 10% of the routes are being used in, at that time, a 500,000 route entry routing table. This was in big core routers in big ISPs at the time. I wonder what the number is now.

> Dino, has this DOS issue been looked at for LISP?

Yes, over and over again and has been solved in many ways. RTRs are the current solution as long as NATs are being used and packets need to be encapsulated in IPv4 RLOCs for whatever reason.

RTRs also have the benefit for updating less places for EID mobility. Here is a quick example. Say 1000 EIDs are talking to my LISP based Macbook EID. I’m sitting in a coffee shop behind a coffee shop resident NAT. Those 1000 ITRs have my EID cached with the RTR’s RLOC. The RTR is the only node that can get packets through the coffee-shop NAT. So its map-cache has my EID cached with the tranlsated RLOC. When I move to another coffee-shop my translated RLOC changes, so only the 1 RTR needs updating versus the 1000 ITRs that are talking to me.

RTRs are also useful for traffic-engineering and multicast replication. See draft-ietf-lisp-te and draft-ietf-lisp-signal-free-multicast for details.

That is the indirection you may be referring to. Please correct if I got that wrong.

Dino

---

From: Tom Herbert <[email-masked]>
Date: Sun, 4 Feb 2018 07:48:19 -0800

> You mean RFC6830. And what you are commenting on below is the map-cache and not the global mapping system. That is the point I want to get Lorenzo’s opinion about.
Dino,

One question about the packet flow sequence in section 4.1 of RFC6830.
On a cache miss, what does an ITR do with the packet? Is it dropped,
queued for pending resolution, forwarded to a node that would have the
mapping, or other?

Thanks,
Tom

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 5 Feb 2018 08:55:57 +0900

> queued for pending resolution, forwarded to a node that would have the

From an architectural point of view we wanted it to behave like ARP (and many ND implementations as well). That is drop the packet. There are implementations that queue the first packet that invokes the Map-Request or the last packet that was received while waiting for the Map-Reply. 

We were told by financial apps that dropping is better than queuing and sending older data. 

As time has gone on with experience in deployment, forwarding to another node that has a large shared cache, like an RTR, seems to deal with the issue in a compromised way. 

Dino

---

From: Tom Herbert <[email-masked]>
Date: Mon, 5 Feb 2018 07:37:11 -0800

On Sun, Feb 4, 2018 at 3:55 PM, Dino Farinacci <[email-masked]> wrote:

> From an architectural point of view we wanted it to behave like ARP (and
> many ND implementations as well). That is drop the packet. There are
> implementations that queue the first packet that invokes the Map-Request or
> the last packet that was received while waiting for the Map-Reply.
>
> As time has gone on with experience in deployment, forwarding to another
> node that has a large shared cache, like an RTR, seems to deal with the
> issue in a compromised way.
>

In ILAMP (https://tools.ietf.org/html/draft-herbert-ila-ilamp-00) secure
redirects are defined to be the primary means of populating a cache. On a
cache miss, a packet is forwarded into the network and routing should
forward the packet to an ILA router that contains the complete set of
mappings for the associated shard. The router performs the transformation
and can send a redirect back to the caching node. The redirect can be
cached so that subsequent packets take a direct route and avoid the
trianglular routing. Redirects must be secure so that they cannot be
spoofed, so for that reason (and some others) the protocol is over TCP. The
mapping cache is only an optimization and packets are never dropped or
queued for pending cache resolution. If the cache weren't present,
communications would still be viable but sub-optimal; that characteristic
establishes a bound for the worst case DOS attack.

Any thoughs on this approach?

Tom

---

From: Lorenzo Colitti <[email-masked]>
Date: Tue, 6 Feb 2018 15:34:00 +0900

> Any thoughs on this approach?

The obvious ones would seem:

   - Will the working set of cache mappins fit in whatever memory is
   available in, say, a large peering router? Remember that memory that is
   capable of sustaining routing lookups at tens of gigabits per second is
   extremely expensive.
   - How do you defend against state exhaustion attacks whereby a large
   number of spoofed sources send packets to nonexistent destinations?
   - How much bandwidth will be used for the redirects? How much CPU time
   will be used to process them?
   - How many servers are needed to store

Suggest gaming this out for a large mobile operator with, say, 100M
clients, 100 Internet connection points and 10T of traffic.

---

From: Tom Herbert <[email-masked]>
Date: Tue, 6 Feb 2018 12:27:46 -0800

On Mon, Feb 5, 2018 at 10:34 PM, Lorenzo Colitti <[email-masked]> wrote:

> Hi Lorenzo,

Thanks for the feedback!

>    available in, say, a large peering router?
>
> The cache needs to be sized to fit the working set. Please look at the
reference topology of section N. The intent is that caches would not be
used at edge or peer routers, ILA router are used there which shard the
mapping database across some number of  nodes. Mapping caches are at ILA-Ns
which are deployed deeper in the network towards the end hosts (like toward
gNB). There are more of these than ILA-Rs, however they are serve a small
set of users and would be implemented on lower end devices. The purpose of
the cache is to optimize latency and throughput of performance critical
intra-network communications (Ue to UE, UE to application server in
network).

>
>    - Remember that memory that is capable of sustaining routing lookups
>    at tens of gigabits per second is extremely expensive.
> No cache state is created for nonexistent destinations.

> clients, 100 Internet connection points and 10T of traffic.

I did an analysis of ILA scalability for a couple of scenarios (see
attached), For the 100M UEs, the number of ILA routers came out to 530.

Tom

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 7 Feb 2018 06:16:43 -0800

> In ILAMP (https://tools.ietf.org/html/draft-herbert-ila-ilamp-00) secure redirects are defined to be the primary means of populating a cache. On a cache miss, a packet is forwarded into the network and routing should forward the packet to an ILA router that contains the complete set of mappings for the

In LISP, we have PITRs that do roughly the same thing. But it comes at an expense that EIDs need to be advertised into the core routing system. I guess in your case, it is on the SIR-prefix that is injected and a packet destined for any ID with a SIR-prefix goes to the closest ILA router. Is that right?

> associated shard. The router performs the transformation and can send a redirect back to the caching node. The redirect can be cached so that subsequent packets take a direct route and avoid the

But you will get some out of order packets. Until the cache is populated, packets are still in the network, either packets that have not reached the ILA router, or packets that have been transformed. So if the ILA router near the source, or the source itself, sends directly, there is a chance it is a shorter path. So new packets arrive to the destination before packets in flight.

> trianglular routing. Redirects must be secure so that they cannot be spoofed, so for that reason (and some others) the protocol is over TCP. The mapping cache is only an optimization and packets are never dropped or queued for pending cache resolution. If the cache weren't present, communications would

But the ILA router in the network needs to have the mapping. And if it does not, what happens then?

> still be viable but sub-optimal; that characteristic establishes a bound for the worst case DOS attack.
> 

You’ll really need to put signatures in the Redirect messages if you want robust authentication.

Dino

---

From: Tom Herbert <[email-masked]>
Date: Wed, 7 Feb 2018 11:14:09 -0800

On Wed, Feb 7, 2018 at 6:16 AM, Dino Farinacci <[email-masked]> wrote:

> > In ILAMP (https://tools.ietf.org/html/draft-herbert-ila-ilamp-00)
> secure redirects are defined to be the primary means of populating a cache.
> On a cache miss, a packet is forwarded into the network and routing should
> mappings for the
> In LISP, we have PITRs that do roughly the same thing. But it comes at an
> expense that EIDs need to be advertised into the core routing system. I
> guess in your case, it is on the SIR-prefix that is injected and a packet
> destined for any ID with a SIR-prefix goes to the closest ILA router. Is
> that right?
>
> Yes. The packet is routed to an ILA router based on a prefix that contains
the shard index.

> > associated shard. The router performs the transformation and can send a
> redirect back to the caching node. The redirect can be cached so that
> subsequent packets take a direct route and avoid the
>
> But you will get some out of order packets. Until the cache is populated,
> packets are still in the network, either packets that have not reached the
> ILA router, or packets that have been transformed. So if the ILA router
> near the source, or the source itself, sends directly, there is a chance it
> is a shorter path. So new packets arrive to the destination before packets
> in flight.
>

Yes. OOO packets are possible during a transition period. In order delivery
is not a requirement of IP and the window for OOO packets is relatively
small anyway.

> communications would
> The ILA router is considered authoritative for its shard. If it doesn't
have a mapping then the packet is silently dropped as having an unreachable
destination.

> You’ll really need to put signatures in the Redirect messages if you want

The redirects are sent over an established TCP connection to an ILA-N so
that deters message spoofing. For stronger security, TCP authentication
option or TLS can be used.

Tom

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 7 Feb 2018 18:48:44 -0800

> Yes. OOO packets are possible during a transition period. In order delivery is not a requirement of IP and the window for OOO packets is relatively small anyway.

Right but frequent out-of-order delivery does not make the system as a whole work well. And the “transition period” is for *every new destination” that is not cached. So this can be a steady state situation.

> The ILA router is considered authoritative for its shard. If it doesn't have a mapping then the packet is silently dropped as having an unreachable destination.

Does the ILA router for the shard only route to destinations inside of the shard? And if so, it is kept small so you can push the mappings and make it scale at that level?

> The redirects are sent over an established TCP connection to an ILA-N so that deters message spoofing. For stronger security, TCP authentication option or TLS can be used.

Is it worth the state to hold millions of TCP connections only the occasion redirect message?

Dino

---

From: Tom Herbert <[email-masked]>
Date: Wed, 7 Feb 2018 20:19:55 -0800

On Wed, Feb 7, 2018 at 6:48 PM, Dino Farinacci <[email-masked]> wrote:

> > Yes. OOO packets are possible during a transition period. In order
> delivery is not a requirement of IP and the window for OOO packets is
> relatively small anyway.
>
> Right but frequent out-of-order delivery does not make the system as a
> whole work well. And the “transition period” is for *every new destination”
> that is not cached. So this can be a steady state situation.
>
> Hi Dino,

I'm not sure I understand. OOO packets most often happen when packets for
the same flow take two different paths through the network at the same time
so that packets sent later beat earlier ones to the destination. W.r.t. to
the cache, the window for OOO delivery is when cache is entry is
instantiated, but there are already packets inflight that presumably are
taking non-cached scenic route. Once the non-cached packets have been
received, all the packets for the flow go through the cache taking the same
path so there is no more OOO. It's a small window. Also, if multiple
connections are simultaneously suffer OOO from this I doubt this would have
a material impact-- congestion window collapse is unlikely without packet
loss. Of course, a stateful firewall in the path might not be so tolerant
of OOO packets...

> Does the ILA router for the shard only route to destinations inside of the
> shard?

Yes.

> And if so, it is kept small so you can push the mappings and make it scale
> at that level?
>

Small is relative. The ILA router first needs to being able to forward the
load, so provisioning would need to consider the worse case where no
entries hit the cache. Redirects would likely be rate limited (probably
capped by throughput). In a network, design I would probably target a cache
hit rate of at least 95%.

> occasion redirect message?

It might be millions of TCP connections spread across a large network, but
for ILA-Ns it's at most a couple of hundred connections and for a mapping
resolution ILA-R it's probably no more than 50K. Assuming 2K memory per TCP
connection ctx (and TLS if in use) that's a 100M on the ILA-Rs. In addition
to security, the other reasons to use TCP is it's reliable transport and
provides congestion control and avoidance. There's also the option of using
TFO if the amount of state were to become an issue.

Tom

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 8 Feb 2018 02:40:36 -0800

> Hi Dino,
> 
> I'm not sure I understand. OOO packets most often happen when packets for the same flow take two different paths through the network at the same time so that packets sent later beat earlier ones to the destination. W.r.t. to the cache, the window for OOO delivery is when cache is entry is

Right.

> instantiated, but there are already packets inflight that presumably are taking non-cached scenic route. Once the non-cached packets have been received, all the packets for the flow go through the cache taking the same path so there is no more OOO. It's a small window. Also, if multiple connectionr.s

For the same destination yes.

> are simultaneously suffer OOO from this I doubt this would have a material impact-- congestion window collapse is unlikely without packet loss. Of course, a stateful firewall in the path might not be so tolerant of OOO packets…

In ILA there is likely a one-to-one association between locator and ID. So the out of order situation can happen to each new specific flow. In LISP, the locator can be a prefix used for many EIDs so the out of order or drop situation on the ITR only happens for one destination and not to all the others that start a flow for the same prefix.

> Does the ILA router for the shard only route to destinations inside of the shard? 
> 
> Yes.
>  
> And if so, it is kept small so you can push the mappings and make it scale at that level?
> 
> Small is relative. The ILA router first needs to being able to forward the load, so provisioning would need to consider the worse case where no entries hit the cache. Redirects would likely be rate limited (probably capped by throughput). In a network, design I would probably target a cache hit rate of at least 95%.

In any loc/ID design push can be used and scale. But is it practical (and necessary) for 1B entries?

> It might be millions of TCP connections spread across a large network, but for ILA-Ns it's at most a couple of hundred connections and for a mapping resolution ILA-R it's probably no more than 50K. Assuming 2K memory per TCP connection ctx (and TLS if in use) that's a 100M on the ILA-Rs. In addition to security, the other reasons to use TCP is it's reliable transport and provides congestion control and avoidance. There's also the option of using TFO if the amount of state were to become an issue.

Okay. Agree its not a memory-issue proble I was referring to. It was how to manage the connections. And how much is exposed to a network admin engineer to debug. Managing 100s of BGP connections have been a challenged with the customers I have worked with in the past.

Dino

---

From: Tom Herbert <[email-masked]>
Date: Thu, 8 Feb 2018 09:05:35 -0800

>
>
> In ILA there is likely a one-to-one association between locator and ID. So
> the out of order situation can happen to each new specific flow. In LISP,
> the locator can be a prefix used for many EIDs so the out of order or drop
> situation on the ITR only happens for one destination and not to all the
> others that start a flow for the same prefix.
>

That would also be true of ILA, flows going to the same destination will
share the same cache entry.

At the start of a flow (or resumption from idle) a connection should be in
slow start so that there wouldn't be a lot of packets inflight to create
OOO packets, or it might even be only a single SYN in flight. It's likely
that the RTT to get the redirect is less than the application response time
so that the cache would be populated before a sender sends its second round
of packets.

As you pointed out the alternative to redirect is do a query and either
drop packets or queue packets until there is a response from the mapping
server. Dropping is problematic because it can introduce latency, consider
that if an initial SYN is dropped the sender takes an initRTO which is at
least 1 sec delay. Queuing is a problem of resources management and the
queue becomes a possible DOS target.

> > > The ILA router is considered authoritative for its shard. If it
> doesn't have a mapping then the packet is silently dropped as having an
> unreachable destination.
> >
> > Small is relative. The ILA router first needs to being able to forward
> the load, so provisioning would need to consider the worse case where no
> This isn't doing push in the pub/sub sense which I agree won't scale to 1B
entries. Redirect are reactions to forwarded packets so the packets
effectively are the mapping request.

> > > The redirects are sent over an established TCP connection to an ILA-N
> so that deters message spoofing. For stronger security, TCP authentication
> > It might be millions of TCP connections spread across a large network,
> but for ILA-Ns it's at most a couple of hundred connections and for a
> mapping resolution ILA-R it's probably no more than 50K. Assuming 2K memory
> per TCP connection ctx (and TLS if in use) that's a 100M on the ILA-Rs. In
> addition to security, the other reasons to use TCP is it's reliable
> transport and provides congestion control and avoidance. There's also the
> option of using TFO if the amount of state were to become an issue.
>
> Okay. Agree its not a memory-issue proble I was referring to. It was how
> to manage the connections. And how much is exposed to a network admin
> engineer to debug. Managing 100s of BGP connections have been a challenged
> with the customers I have worked with in the past.
>
> My sense is that network control protocols are trending to use TCP with an
RPC layer. For instance in the datacenter use case, an operator like Google
or Facebook are going to be most comfortable with a protocol over TCP using
a their common RPC and authentication infrastructure (i.e. Google would
probably want to use gRPC, Facebook probably Thrift as they seem to be
using in Open/R). For 3GPP 5G the service-based interfaces are HTTP 2.0
(REST) over TCP.

Tom

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 9 Feb 2018 14:33:13 +0900

> That would also be true of ILA, flows going to the same destination will share the same cache entry.

Yes true if ILA was deployed on a eNodeB/UPF. 

> At the start of a flow (or resumption from idle) a connection should be in slow start so that there wouldn't be a lot of packets inflight to create OOO packets, or it might even be only a single SYN in flight. It's likely that the RTT to get the redirect is less than the application response time so that the cache would be populated before a sender sends its second round of packets.

Yep - that was our justification in LISP too when experiencing a cache miss. 

> This isn't doing push in the pub/sub sense which I agree won't scale to 1B entries. Redirect are reactions to forwarded packets so the packets effectively are the mapping request.

Right. Agee. 

Dino