Subject: [RRG] How to avoid black-hole in LISP-CONS with aggregation mechanism?

From: Xu Xiaohu <[email-masked]>
Date: Mon, 27 Aug 2007 16:55:45 +0800

Hi all,
I have a doubt about how to avoid black-hole in LISP-CONS with aggregation
mechanism? My doubt is explained as follows:

                          +---------+ 1.0.0.0/8  CDR-1
                          |  CDR-3  |
                          +----+---\+ 1.1.0.0/16 CDR-2
                         /          \\
                       //             \
                     //                \\
    Push 1.0.0.0/8  /                    \ Push 1.1.0.0/16
                   /                      \
                 /                         \\
               //                            \
             //                               \\
       +----/---+ 1.1.0.0/16 CAR-1           +--\-----+
       |CDR-1   | 1.2.0.0/16 CAR-2           |CDR-2   | 1.1.0.0/16 CAR-3
       +---+--\-+                            +---+----+
           |   \\                                |
           |     \\                              |
           |       \\ Push 1.2.0.0/16            |Push 1.1.0.0/16
   Push 1.1.0.0/16   \\                          |
           |           \\                        |
           |             \\                      |
           |               \\                    |
       +---+----+        +---\------+       +----+----+
       |CAR-1   |        |CAR-2     |       |CAR-3    |
       +--------+        +----------+       +---------+
      1.1.0.0/24         1.2.0.0/24         1.1.2.0/24
      1.1.1.0/24         1.2.1.0/24         1.1.3.0/24

As shown in the above figure, CAR-1 has two EID-prefixes, 1.1.0.0/24 and
1.1.1.0/24, and it sends an aggregated EID-prefix 1.1.0.0/16 to CDR-1. CAR-2
also sends an aggregated EID-prefix 1.2.0.0/16 to CDR-1. CDR-1 sends an
aggregated EID-prefix 1.0.0.0/8 to its parent CDR, CDR-3.
CAR-3 has two EID-prefixes, 1.1.2.0/24 and 1.1.3.0/24, and it sends an
aggregated EID-prefix 1.1.0.0/16 to CDR-2. CDR-2 sends a EID-prefix
1.1.0.0/16 to its parent CDR, CDR-3.
Now CDR-3 has two EID-prefixes, one is 1.0.0.0/8 with a nexthop of CDR-1,
the other is 1.1.0.0/16 with a nexthop of CDR-2. If CDR-3 receives a mapping
request for longest-matching entry for 1.1.1.1, it will result in a
black-hole. 

How to avoid it? Use the same aggregation granularity within the same level?
Or aggregation will not be available until all the component EID-prefixes
exists in the EID-prefix database of the aggregation attempter?

Best regards,
Steven XU

--
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: [email-masked] (Noel Chiappa)
Date: Mon, 27 Aug 2007 09:19:53 -0400 (EDT)

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

    > how to avoid black-hole in LISP-CONS with aggregation mechanism?
    > ...
    > Now CDR-3 has two EID-prefixes, one is 1.0.0.0/8 with a nexthop of
    > CDR-1, the other is 1.1.0.0/16 with a nexthop of CDR-2. If CDR-3
    > receives a mapping request for longest-matching entry for 1.1.1.1, it
    > will result in a black-hole.

Yes, this is a problem. I identified the same problem back in early July, and
raised it with the CONS authors privately.

    > How to avoid it? Use the same aggregation granularity within the same
    > level? Or aggregation will not be available until all the component
    > EID-prefixes exists in the EID-prefix database of the aggregation
    > attempter?

It seemed to me that the only way it can work is to have the requirements that
all CDRs which are 'authoritative' (to borrow terminology from DNS) for a
particular portion S of the address space i) have to all be siblings, and ii)
have to know which sub-portions of S each of their siblings is authoritative
for, to allow requests to be forwarded to the correct sibling CDR, if it
arrives at a CDR which is not authoritative for the particlar sub-portion of
S which the request is in.

I did discuss this with the authors, and I think that was the answer, but I
can't verify that because we took the issue up on a conference call, and I
don't have notes of everything that was said there!

(Something to remember is that he CONS specification in the Internet-Draft is
really a very early draft, and so there are some issues (such as this one)
which aren't clearly covered yet.)

	Noel

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 27 Aug 2007 10:46:09 -0700

>        | CDR-1  | 1.2.0.0/16 CAR-2           | CDR-2  | 1.1.0.0/16  
> CAR-3
>        +---+--\-+                            +---+----+
>            |    \\                               |
>        |  CAR-1 |      |  CAR-2   |         |  CAR-3  |
> CDR-1,

The diagram has two problems:

1) You are aggregating to the same level (to CDR-3) with different  
mask-lengths.

2) CDR-1 and CDR-2 need to be part of the same CDR-mesh. That is all  
the CARs 1-3
    are authoritative for the same length prefix and hence need to  
advertise to
    the same mesh upstream.

Now having said that, you could have CAR-1 and CAR-3 advertise to the  
same CDR-1 mesh, but since CAR-2 has 1.2 as it's prefix, it could  
advertise into CAR-3 which is a different CDR-mesh. And then both  
CDR-1 and CDR-2 can advertise 1.0.0.0/8 upstream to CDR-3.

Dino

---

From: Lixia Zhang <[email-masked]>
Date: Mon, 27 Aug 2007 14:56:00 -0700

I believe most people on RAM are also on RRG.
lets carry out this discussion on RRG list only.
(so I removed RAM from cc: list)

Lixia

On Aug 27, 2007, at 10:46 AM, Dino Farinacci wrote:

> 2) CDR-1 and CDR-2 need to be part of the same CDR-mesh. That is  
> all the CARs 1-3
> Now having said that, you could have CAR-1 and CAR-3 advertise to  
> the same CDR-1 mesh, but since CAR-2 has 1.2 as it's prefix, it  
> could advertise into CAR-3 which is a different CDR-mesh. And then  
> both CDR-1 and CDR-2 can advertise 1.0.0.0/8 upstream to CDR-3.
>
> Dino
>
> _______________________________________________
> RAM mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ram

---

From: Lixia Zhang <[email-masked]>
Date: Mon, 27 Aug 2007 14:56:25 -0700

I believe most people on RAM are also on RRG.
Lets carry out this discussion on RRG list only.
(I removed RAM from cc: list)

Lixia

---

From: Scott Brim <[email-masked]>
Date: Wed, 29 Aug 2007 08:22:55 -0400

> S which the request is in.

Agreed.  You simply wouldn't set up the CDR tree like this.  In this
case you would re-home the CARs so that they hung off the appropriate
aggregating CDRs (for example, CAR-3 off CDR-1).  This is an
administrative tree and physical topology isn't a limiting factor.  In
fact you might expect authoritative CARs for a particular EID prefix to
be geographically separated.

Scott

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 30 Aug 2007 18:56:26 +0800

Hi,
Once aggregating to the same level with same mask-lengths is adopted, it may
result in inefficient lookup. For example, CDR-11 within level-1 CDR-mesh is
authoritative for 1.1.0.0/16, with 1.1.1.0/24 and 1.1.2.0/24 in its
EID-prefix table, and CDR-12 with level-1 CDR-mesh is authoritative for 1.2.
0.0/16, with only 1.2.1.0/24 in its EID-prefix table. Should both of them
push 1.0.0.0/8 to their common parent CDR-mesh which is authoritative for 1.
0.0.0/8?

IMO, it's better that CDR-11 pushes 1.1.0.0/16 and CDR-12 pushes 1.2.1.0/24
to their common parent CDR-mesh. As long as the aggregation does not exceed
its authoritative address space, it's OK.

Best regards,
Steven XU

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 代表 Dino Farinacci
发送时间: 2007年8月28日 1:46
收件人: Xu Xiaohu
抄送: [email-masked]; [email-masked]; [email-masked]
主题: [RRG] Re: [RAM] How to avoid black-hole in LISP-CONS with aggregation
mechanism?

Dino

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 30 Aug 2007 10:38:43 -0400 (EDT)

> .. it may result in inefficient lookup.
    > ...
    > As long as the aggregation does not exceed its authoritative address
    > space, it's OK.

Again, this is a topic that has been discussed fairly extensively, but it's
not completely resolved yet, in part because I don't think there is a perfect
answer.

In general, if the advertisments upward only cover what a CDR is actually
authoritative for, and that recurses upward, that does result in optimal
'routing' of requests down the CDR 'pseudo-hierarchy'. (I call is a
'pseudo-hierarchy' since it is basically hierarchical in form, but the
existence of cross-links among siblings mean it's not a pure hierarchy).

The problem with doing that is that you may not get much reduction in the
amount of information passed upward, so that in the higher levels of the
pseudo-hierarchy the tables could get quite large. (How much aggregation you
actually get depends on how the EID name-space is allocated, etc - e.g. if a
node has childrem which are authoritative for say, 128.52.0/17 and
128.52.128/17, then it can aggregate that to a single entry to advertise
upward, i.e. 128.52/16. However, if it only has a large number of entries of
the form 128.52.X/24, with gaps, then it may not be able to aggregate them
all into a single entry.)

This is of course very similar to the tradeoff in normal hierarchical
routing, where you have a tradeoff between routing overhead, and path
optimality. (We don't have a single perfect solution there, either!)

In CONS, as it stands, a request could (in the worst case) take an extra
'sideways' hop at each level. One can think of a number of possible
optimizations, e.g. simple heuristics for limiting the upward advertisements
(e.g. to one level above the parent of the node that originates an
advertisment) which can reduce this a lot, but attention has been focused
elsewhere recently, for a variety of reasons. (For one, we won't know how bad
the aggregation is until we look at some actual data.)

I have been thinking hard about possible optimizations for CONS, and have
come up with a long list of things we could possibly do. Of course, not all
of them will be cost-effective, so only the ones that make sense will
eventually be added.

Of those, I have been thinking about the ones that seem to have the most
payoff in some detail, e.g. caching 'popular' EID->RLOC bindings in the CDR
hierarchy (so that requsts for the mapping for major content providers don't
have to go all the way through the pseudo-hierarchy, to the CAR which holds
that mapping).

Eventually we will get back to this issue of optimizing the request descent
path through the CDR pseudo-hierarchy, and try and work out some good
heuristics for optimizing it. If anyone has any good ideas, they would
certainly be welcome!

	Noel

---

From: Scott Brim <[email-masked]>
Date: Thu, 30 Aug 2007 13:30:05 -0400

On 8/30/07 6:56 AM, Xu Xiaohu allegedly wrote:
> Hi,
> Once aggregating to the same level with same mask-lengths is
> adopted, it may result in inefficient lookup. For example, CDR-11
> within level-1 CDR-mesh is authoritative for 1.1.0.0/16, with
> 1.1.1.0/24 and 1.1.2.0/24 in its EID-prefix table, and CDR-12 with
> level-1 CDR-mesh is authoritative for 1.2.0.0/16, with only
> 1.2.1.0/24 in its EID-prefix table. Should both of them push
> 1.0.0.0/8 to their common parent CDR-mesh which is authoritative for
> 1.0.0.0/8?
>
> IMO, it's better that CDR-11 pushes 1.1.0.0/16 and CDR-12 pushes
> 1.2.1.0/24 to their common parent CDR-mesh. As long as the
> aggregation does not exceed its authoritative address space, it's
> OK.

That's right.  There is no need for all children to have the same
prefix lengths, and the key restriction is to stay within the
delegated prefix.

Scott

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 30 Aug 2007 10:46:19 -0700

>> 1.0.0.0/8 to their common parent CDR-mesh which is authoritative for

It really doesn't have to push it up, the Map-Request that comes from  
the top of the hierarchy will just travel one additional hop  
southbound and then a CONS Unreachable Message with code 2 (i.e. Not  
Found) is returned to the requesting CAR.

> prefix lengths, and the key restriction is to stay within the

Definitely agree. But as Noel said (I'll paraphrase), you don't want  
a free for all where there are more specifics all over the place or  
you lose your benefit of information reduction.

If we let this happen, we may as well get to a push model like NERD  
or RPMD. So CONS is the model where we are strongly attempting to  
reduce information at the expense of lookup latency (but as Noel  
mentioned, he is trying to improve lookup latency).

Dino