Subject: [RRG] How to avoid the side effect of cache in ITR

From: Xu Xiaohu <[email-masked]>
Date: Wed, 10 Oct 2007 22:11:17 +0200

Hi all, 

The cache in ITR reduce the forwarding or querying pressure on some mapping
server, but it also results in the following side effects. Is there any
other better solution to solve the above issues?

First, the mapping entry in cache is not real-time, it depends some ICMP
message to reflect the connection status of the multi-homed site, which
obviously brings some attack risks. The smaller TTL value of mapping entry
will result in frequent mapping request.

Second, it can result in black-hole or sub-optimal forwarding path in some
cases. For example, there are two prefixes in the mapping server, 1.1.1.0/24
and 1.1.0.0/24. At first, ITR receives a packet with destination of 1.1.2.1,
and it will get a mapping response which includes 1.1.0.0/24->ETR mapping.
Then a packet with destination of 1.1.1.1 arrives on ITR, it will result in
black-hole or sub-optimal forwarding path. There are some approaches to
avoid this: one is avoiding the EID prefixes in mapping database overlapped,
the other is replying with all the specific EID-prefixes' mapping covered by
the matching EID-prefix. The former will result in non-aggregation, for
example, some enterprise has a /16 prefix, from which one /24 prefix is
assigned to one site, while the remaining /24 prefixes are assigned to
another site called site B. With this approach, all the remaining /24
prefixes in site B should be stored in the mapping database separately. But
in current Internet, prefix overlapping is permitted. I wonder whether this
overlapping phenomenon is ordinary or not? The latter approach will result
in some useless states in the ITR cache.

Is there any other better solution to solve the above issues?

Best regards,

Xu Xiaohu

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 10 Oct 2007 23:00:50 +0200

Sorry, I should fix a spelling mistake. 1.1.0.0/24 should be 1.1.0.0/16.
And the question “whether this overlapping phenomenon is ordinary or not”
should be expressed more clearly as “whether this overlapping phenomenon is
ordinary or not in an unchanged AS? Taking incremental deployment scenario
into account, it’s impossible to split the aggregated route anymore if this
phenomenon does exist there”.

  _____  

发件人: Xu Xiaohu [mailto:[email-masked]] 
发送时间: 2007年10月10日 22:11
收件人: [email-masked]'
主题: How to avoid the side effect of cache in ITR 

Hi all, 

the other is replying with all the specific EID-prefixes’ mapping covered
by the matching EID-prefix. The former will result in non-aggregation, for

Best regards,

Xu Xiaohu

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 10 Oct 2007 23:02:03 +0200

_____  

Hi all, 

Best regards,

Xu Xiaohu

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 10 Oct 2007 23:02:15 +0200

_____  

Hi all, 

Best regards,

Xu Xiaohu

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 10 Oct 2007 23:02:35 +0200

_____  

Hi all, 

Best regards,

Xu Xiaohu

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 10 Oct 2007 21:46:53 -0400 (EDT)

> From: Xu Xiaohu <[email-masked]>

    > The cache in ITR reduce the forwarding or querying pressure on some
    > mapping server, but it also results in the following side effects.
    > ...
    > it can result in black-hole or sub-optimal forwarding path in some
    > cases. For example, there are two prefixes in the mapping server,
    > 1.1.1.0/24 and 1.1.0.0/24.

I think you meant 1.1.1.0/24 and 1.1.0.0/16, right?

    > There are some approaches to avoid this: one is avoiding the EID
    > prefixes in mapping database overlapped, the other is replying with all
    > the specific EID-prefixes' mapping covered by the matching EID-prefix.
    > ...
    > for example, some enterprise has a /16 prefix, from which one /24
    > prefix is assigned to one site, while the remaining /24 prefixes are
    > assigned to another site
    > ... in current Internet, prefix overlapping is permitted.

Yesssss.... Even if you do longest match in the ITR when it looks through the
mappings that it has on hand, already cached (the way we do longest match now,
on routing table entries) that does not help.

E.g. assume that there are separate mapping entries for 1.1.1.0/24 and
1.1.0.0/16, and the ITR looks up the mapping for 1.1.2.17, and that returns
the 1.1.0.0/16 mapping, which it caches. Now assume the ITR needs to look up
the mapping for 1.1.1.17; the 1.1.0.0/16 mapping which it already has cached
will satisfy that request, even though it is not the right mapping.

I would say that the fix is to not allow a larger mapping to be returned if it
'covers' a smaller one. I.e. the entity which maintains the authoritative
mappings would only have two entries, for 1.1.1.0/24 and 1.1.0.0/16. However,
whenever a request came in for any 1.1.<anything> which was not 1.1.1.N, it
would have to reply with a 'made up' mapping entry of 1.1.<something>/24, to
avoid 'covering up' the 1.1.1.0/24 mapping.

I do not recall the specs well enough to know whether they already do that -
can anyone else confirm if they handle this problem, and if so, how?

	Noel

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Scott Brim <[email-masked]>
Date: Fri, 12 Oct 2007 09:57:51 -0400

On 10 Oct 2007 at 21:46 -0400, Noel Chiappa allegedly wrote:
> E.g. assume that there are separate mapping entries for 1.1.1.0/24
> and 1.1.0.0/16, and the ITR looks up the mapping for 1.1.2.17, and
> that returns the 1.1.0.0/16 mapping, which it caches. Now assume the
> ITR needs to look up the mapping for 1.1.1.17; the 1.1.0.0/16
> mapping which it already has cached will satisfy that request, even
> though it is not the right mapping.

I don't see why this would happen except by a configuration error.
The mapping replies have (EID prefix) -> (set of RLOCs to reach it).
There is no reason why these would be aggregated in flight unless the
result were known to be true.

> I would say that the fix is to not allow a larger mapping to be
> returned if it 'covers' a smaller one. I.e. the entity which
> maintains the authoritative mappings would only have two entries,
> for 1.1.1.0/24 and 1.1.0.0/16. However, whenever a request came in
> for any 1.1.<anything> which was not 1.1.1.N, it would have to reply
> with a 'made up' mapping entry of 1.1.<something>/24, to avoid
> 'covering up' the 1.1.1.0/24 mapping.

The authoritative source should only return what it is authoritative
for.  In CONS there are two different sorts of information flowing.
First is CONS-internal routing information to get to the authoritative
source (aCAR).  Second is the mapping replies themselves.  You
aggregate how to find the aCARs (the CONS-internal routing
information), but you don't aggregate the mapping replies.

swb

---

From: [email-masked] (Noel Chiappa)
Date: Fri, 12 Oct 2007 10:22:47 -0400 (EDT)

> From: Scott Brim <[email-masked]>

    >> .. separate mapping entries for 1.1.1.0/24 and 1.1.0.0/16, and the ITR
    >> looks up the mapping for 1.1.2.17, and that returns the 1.1.0.0/16
    >> mapping, which it caches. Now assume the ITR needs to look up the
    >> mapping for 1.1.1.17; the 1.1.0.0/16 mapping which it already has
    >> cached will satisfy that request, even though it is not the right
    >> mapping.

    > I don't see why this would happen except by a configuration error. The
    > mapping replies have (EID prefix) -> (set of RLOCs to reach it). There
    > is no reason why these would be aggregated in flight unless the result
    > were known to be true.

??? I wasn't positing any mapping in flight; I was just positing that there
were two mappings configured:

    1.1/16 -> (RLocSet A)
    1.1.1/24 -> (RLocSet B)

I.e. the second entry is for a "punch-out" in the first entry.

Now, maybe you want to say that "punch-outs" should be illegal, i.e. that no
two EIDRange->RLocSet mappings can have overlapping EIDRange's, but like I
said, I don't recall recall whether that's currently allowed or not.

If it *is* allowed, then we have the problem I describe (at least in schemes
which do caching; more on this below).

If it is not allowed, then to configure something like the example above, one
would have to configure ~256 entries, one looking like the second one, and
the other ~255 all looking like

    1.1.X/24 -> (RLocSet A)

for all X other than 1.

Unless we do as I suggest below, which amounts to automatically 'converting'
things that look like the first, to the ~256 entry version I just described:

    >> returned if it 'covers' a smaller one. I.e. the entity which maintains
    >> the authoritative mappings would only have two entries, for 1.1.1.0/24
    >> and 1.1.0.0/16. However, whenever a request came in for any
    >> 1.1.<anything> which was not 1.1.1.N, it would have to reply with a
    >> 'made up' mapping entry of 1.1.<something>/24, to avoid 'covering up'
    >> the 1.1.1.0/24 mapping.

    > for.

Well, but it's authoritative for both 1.1/16 and 1.1.1/24. The issue is the
punchout;

    > In CONS there are two different sorts of information flowing. First is
    > CONS-internal routing information to get to the authoritative source
    > (aCAR). Second is the mapping replies themselves.

Yes, in CONS there are two kinds of mappings/bindings (in the generic sense of
the word), the first being:

  EIDRange->CDR/aCAR

which allows you to find the second:

  EIDRange->RLocSet

which is what you actually want. (And I have proposed that we have different
terms for the two kinds of mapping, to prevent confusion - I forget now
exactly what terminology I suggested.)

However:

    > You aggregate how to find the aCARs (the CONS-internal routing

Right, but this problem has little to do with how EIDRange->RLocSet bindings
are distributed; rather, it's mostly a property of how we allowed EIDRange's
to be configured.

I say "little" above, not "nothing", because if you're using a full push
scheme (i.e. all ITR's have the *complete* table of EIDRange->RLocSet
bindings) we can fix this problem, whilst allowing punchout configurations,
simply by saying you have to do longest-match lookups in the table.

But as long as i) ITR's can have incomplete tables, and ii) punchout
configurations are allowed, we have this problem.

	Noel