Subject: [RRG] Not moving the problem to the global mapping system

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Apr 2008 09:49:55 +1200

On 2008-04-10 17:54, Michael Meisel wrote:
...
> I think we should ask this question in terms of the problems we are
> trying to solve. As we all know, one of these problems is the frequency
> of BGP updates today, which are largely coming from edge network. To put
> it a different way, the problem is that the reachability information for
> even the smallest of edge networks is announced globally. Each update
> requires a significant amount of processing by each node that it passes
> through. So the mapping system better not suffer from this same problem,
> or we haven't done any good!
> 
> So, specifically, we should be asking:
> 
> (1) Is the mapping function successful in preventing edge network
> reachability from being propagated into the global routing system?
> 
> (2) If yes, does it do so without simply moving the problem to the
> global mapping system?
> 
> Note that proposals that both (a) put reachability information into the
> mapping system and (b) involve any sort of push model start to look a
> lot like BGP, and therefore are going to have a hard time answering
> "yes" to (2) convincingly.

I can't say how much I agree with this. If the mapping system
degenerates into a reachability-driven routing system, we might
just as well switch to two layers of BGP immediately.

I would suggest turning this into a concrete goal, such as:

<strawman>
The update rate in the mapping system should be at least
two orders of magnitude less than the update rate in
the BGP4 system, at any point in time.
</strawman>

   Brian

--
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: Michael Meisel <[email-masked]>
Date: Thu, 10 Apr 2008 15:01:19 -0700

> just as well switch to two layers of BGP immediately.

I think I wasn't clear, because it sounds like we very much agree. I 
think we should expect a "yes" answer to both questions, and a mapping 
system like you describe is exactly the sort that would have trouble 
doing so.

> the BGP4 system, at any point in time.

Yeah, I think something like that is reasonable, though I think "update 
rate" is probably both too vague and too narrow a metric. We need to 
take into account the order of magnitude in number of devices doing the 
processing, processing required per update, and probably other things I 
haven't thought of.

But I still wonder -- is it truly a useful step towards solving the 
scalability problem to develop a list of such constraints, in and of 
itself? Or is it only useful if we use those constraints to evaluate 
concrete designs? I'm tending towards the latter.

-Michael

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Apr 2008 10:08:57 +1200

Michael, we *do* agree, maybe I confused you by
not using a double negative ;-)

   Brian

---

From: Robin Whittle <[email-masked]>
Date: Fri, 11 Apr 2008 11:19:28 +1000

Hi Brian,

> the BGP4 system, at any point in time.

This might be a reasonable goal or constraint if it was assumed that
the map-encap's mapping system was as costly and problematic (with
problems like convergence time, amplification of changes due to
routers flapping, making half-baked decisions based on limited
information, unfair burden of costs etc.) as BGP is today.

There are good reasons why BGP has to do what it does today.

A map-encap system is a totally different thing, and its mapping
distribution system need have no resemblance whatsoever to BGP.

The map-encap schemes other than Ivip try to avoid the mapping
distribution system being involved in reachability changes.  Ivip
takes the opposite approach, which has various benefits as mentioned
in the recent thread:

   Moving the problem to the global mapping system - fast-push

      http://psg.com/lists/rrg/2008/msg01137.html
      http://psg.com/lists/rrg/2008/msg01139.html
      http://psg.com/lists/rrg/2008/msg01143.html

Ivip's mapping distribution system is much more efficient than BGP,
and there is a fee per update.  So there is no (or much less)
"tragedy of the commons" problem which lies at the heart of the
routing scaling problem we are trying to solve.

Ivip is a map-encap scheme which violates what I think are the
implicit assumptions behind your strawman text: that mapping changes
in the mapping distribution system are at least as burdensome - due
to intrinsic costs and probably the unfair distribution of costs -
as updates are in BGP today.  So I don't think proposals such as
Ivip should be constrained as you suggest.

  - Robin

---

From: "William Herrin" <[email-masked]>
Date: Thu, 10 Apr 2008 21:41:07 -0400

>  the BGP4 system, at any point in time.

Brian,

Depending on the character of the map system, this is either
absolutely critical or blithering nonsense.

Before pushing similar concrete goals, I'd ask you glance through TRRP
for an example of a system in which constraints on the system-wide map
update rate appear unwarranted.

TRRP isn't a push-based system. That difference may prove significant
when considering permissible map update rates and that significance
shouldn't be overlooked by the specified goals.

Anyway, while I think the idea of a map system that doesn't convey
reachability information is interesting at a conceptual level, I don't
see how you can implement it without making the system at least
hybrid-pull.

Just because a particular service provider (BGP AS) can usually reach
a particular endpoint doesn't mean they always can. That holds true
regardless of whether the service provider itself is reachable. And as
we see every time Cogent gets in a spat with someone, just because you
can reach either of two ISPs doesn't necessarily mean they can reach
each other.

If you don't convey reachability information in the map, then the ITR
will have to ask its selected ETR whether a particular endpoint is
currently reachable and it will have to keep verifying that
reachability throughout the session. If you're going to do all that,
why not use a pull system from the beginning and gain all of its
advantages?

Remember, you can't rely on the ETR to tell the ITR that a destination
is no longer reachable. There are common, trivial cases in which that
will fail as discussed here:
http://bill.herrin.us/network/statechange.html

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked] [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Michael Meisel <[email-masked]>
Date: Thu, 17 Apr 2008 14:00:32 -0700

Robin Whittle wrote:
 > [snip]

Hi Robin,

I think your complaint stems from the fact that Brian did not include 
any metric of (non-monetary) update cost in his strawman. We must have 
/some/ constraint on mapping updates -- no matter how little processing 
a single Ivip mapping update requires, its (non-monetary) cost is still 
non-zero. Ivip is unique among the proposals, as you mention, in the 
following way: all other proposals intend to guarantee either fewer 
pushed mapping updates compared to BGP, or pull-only updates /by 
design/. It /might/ be true that the update cost in Ivip is manageable 
due to human or economic factors, but that is only speculation at this 
point, and not enforced by the design.

So all I am saying, and I believe most people on this list would agree, 
is that we need some objective, scientific metric by which to judge 
whether a design is likely to solve the problems in question without 
causing new ones. Something where we can do a quantitative evaluation. 
If, as you suggest, Ivip does not cause problems due to large update 
volume, such an evaluation could prove you right!

-Michael

---

From: Robin Whittle <[email-masked]>
Date: Fri, 18 Apr 2008 15:39:17 +1000

Short version:      Brian's strawman criteria and the current
                    map-encap proposals.

                    A note about LISP-ALT having a form of
                    push added, by which ETRs would solicit
                    a mapping request from ITRs which are
                    sending them traffic packets.

Hi Michael,

I will discuss your comments on the Ivip business model in a
separate thread: "Ivip business models: fast push & OITRDs".

Here I discuss the limitations I perceive in Brian's "strawman"
criteria.

You wrote:

> I think your complaint stems from the fact that Brian did
> not include any metric of (non-monetary) update cost in his
> strawman.

> the BGP4 system, at any point in time.

would require a future map-encap scheme's mapping update rate to be
less than 1% of the current rate of updates (however measured) in
BGP.  Yet, we want the map-encap scheme to support potentially
billions of separately mapped slices of address space.

This seems overly restrictive from several perspectives, including.

  1 - The rate of mapping updates must be minimised because they
      inherently impose burdens on people who do not benefit
      from them.

  2 - The cost to participant devices or operators in the mapping
      system of each update is comparable to the cost of a BGP
      update.

As I tried to indicate in a previous message, point 1 doesn't apply,
or applies to a much lesser degree, to Ivip, since the organisations
which collectively run most of the fast push scheme will be paying
for that system by collecting a fee per update from end-users.

Regarding point 2, I think that for all the map-encap schemes and
especially for Ivip, the cost per any one device which handles a
mapping update - or handles a mapped micronet in its memory - should
be less than the cost per update or BGP advertised prefix in DFZ
routers today.

> We must have /some/ constraint on mapping updates -- no matter how
> little processing a single Ivip mapping update requires, its
> (non-monetary) cost is still non-zero.

I agree.

> Ivip is unique among the proposals, as you mention, in the
> following way: all other proposals intend to guarantee either
> fewer pushed mapping updates compared to BGP, or pull-only updates
> /by design/.

OK - here is my pernickety analysis of your statement and of how
Brian's criteria applies to the current map-encap proposals:

  LISP-NERD - pure push.

         Fewer updates than BGP for a given number of prefixes, due
         to ITRs doing their own reachability detection and making
         their own multihoming service restoration based on the
         options provided in the mapping data.  Likewise the ITRs
         doing their own TE work, rather than having the end-user
         do it via changed mapping data (Ivip) or changing the
         advertisement of the prefix (current BGP practice).

         I am not convinced this would result in the factor of 100
         drop Brian is seeking. For that to be the case, it would
         need to be shown that at least 99% of current BGP updates
         were purely related to multihoming service restoration and
         TE, not to permanent, planned, inevitable changes in where
         prefixes are advertised. It would also need to be shown
         that the alternative ETR addresses contained in the mapping
         data were generally adequate to cope with all outages.  If
         not, then the end-users would hurriedly create new mapping
         to cope with some fault condition they had not fully
         anticipated.  Then it would need to be shown that the rate
         of end-users changing their mapping, in order to fine-tune
         TE or how their multihomed service would be restored, would
         be so low that Brian's ambitious goal could be achieved.

         However, as a LISP-NERD system grew to have more mapped
         prefixes than BGP's current 250k, I am sure the absolute
         number of updates would rise beyond current BGP levels.
         So I can't imagine how a successful LISP-NERD system -
         successful due to providing many more end-user networks
         with MH and TE than the BGP system currently does - could
         meet Brian's factor of 100 reduction requirement.

         While the 100:1 goal probably couldn't be met, I think that
         for a given number of prefixes or end-user networks,
         LISP-NERD would reduce the number of updates compared to
         handling them via current BGP techniques.

  LISP-ALT - pure pull.

        I am not sure how Brian's criteria would apply to ALT,
        because there is no push and so no updates to measure.

        ETRs can change their mapping as frequently as they
        like and no-one would notice, unless by asking for
        the same mapping repeatedly and noting any changes in
        the responses.

        In the Friday 14 March RRG meeting, I recorded the audio
        live (it is not archived at:
        http://limestone.uoregon.edu/ftp/pub/videolab/media/ietf71/)
        and Dino was discussing a way by which ETRs currently
        receiving tunneled traffic packets from ITRs could send back
        new mapping data to ITRs, so providing a form of real-time
        "Notify" system, unconstrained by caching times of ITRs,
        which scales well and which does not burden the ALT network
        itself.  I think this would be done by the ETR asking the
        ITR to request fresh mapping.  My recording cut out for
        reasons unknown in the middle of this.  This would not be as
        effective as Ivip's push and Notify system, since the LISP
        approach assumes that the ITRs can communicate with ETRs
        which have the updated mapping, assumes a high level of
        coordination amongst disparate ETRs in a fault situation,
        and assumes the ITR can securely and reliably decide to
        use the updated mapping.

        Brian's criteria doesn't seem to capture this kind of
        mapping change - and it only applies to the ITRs which
        are currently sending traffic to the ETRs in question.

        LISP-ALT meets your proposal due to it being pure pull -
        but what of this proposed extension to have ETRs send
        fresh mapping to some ITRs?

  APT - slow hybrid push-pull

        Brian's criteria clearly applies to the flooding push
        part of APT - from wherever the updates arise (any
        Default Mapper or from some other sources in APT ISP
        networks?) to every Default Mapper in the APT island.

        As with NERD, to achieve this 100:1 reduction
        for a fixed number of end-user networks seems
        pretty challenging, and seems impossible if the
        APT system grows to cope with millions or billions
        of end-user networks.

        Brian's criteria takes no account of the number of
        network elements partaking in the transfer of mapping
        changes.  With BGP it is the DFZ routers - and we
        only have a rough guess of how many there are: 123k
        or most likely more.

        http://www.ops.ietf.org/lists/rrg/2007/msg00253.html
        http://www.ops.ietf.org/lists/rrg/2007/msg00255.html

        However, with APT, the number of participating
        Default Mappers, or whatever other devices are involved
        in flooding mapping updates across the APT island,
        is likely to be a different number than this.  I guess
        it is less, but maybe not.

        As with LISP-NERD, I expect that for a given number of
        prefixes or end-user networks, APT would result in a
        lower number of updates than would occur with current BGP
        techniques.

  Ivip - fast hybrid push-pull

        Fast push of mapping messages which are simpler and
        therefore shorter than in all the other proposals.

        Participating devices handle updates generally much more
        efficiently than BGP routers do.

        As argued earlier, Brian's criteria doesn't seem well
        suited to the costs and benefits of Ivip, and Ivip's
        update rate will not meet the 100:1 reduction goal.

  TRRP - pure pull

        (Though Bill Herrin has two approaches to a "Notify" system
         - pushing updates towards where they are needed, or at
         least causing ITRs which need them to ask for updated
         mapping - I am not convinced these approaches are
         practical.)

        Similar to LISP-ALT.  The authoritative query servers (ETRs
        in ALT and DNS servers in TRRP) can update their mapping as
        frequently as they like without it being measurable in any
        ordinary sense, or being a burden on anyone.  So Brian's
        criteria does not seem to apply in any practical sense to
        TRRP or LISP-ALT.

        To the extent it is a pure pull system, it meets your
        criteria.  However, as with LISP-ALT, there are proposals
        to add a directed form of push, so this wouldn't fit into
        your criteria, and any such push of mapping changes would
        be measurable and important under Brian's criteria,
        although it would only involve a subset of the whole system.

 - Robin