Subject: Re: [rrg] draft-narten-radir-problem-statement-05.txt

From: Geoff Huston <[email-masked]>
Date: Tue, 2 Mar 2010 08:51:05 +1100

Hi Thomas,

With reference to the draft you have written in the scaleability of Internet Routing I'd like to add some comments based on an update to my work cited by this draft (namely [1]  <http://www3.ietf.org/proceedings/06mar/slides/grow-3.pdf>).

I was struck by the the two key drivers you reference in section 3, namely the growth of the number of entries in the routing system and the growth in the number of updates.

I have been looking at this for some time, as you are aware, and I'd like to point you to a presentation pack I've prepared that is an update to the data you reference in the draft. The referenced presentation refers to data collection over 2005. The more recent presentation refers to a longer term data set that spans multiple years. You can find the pack at: http://www.potaroo.net/presentations/2010-02-01-bgp2009.pdf. (This work is being presented at APRICOT this week in Kuala Lumpur.)

The first observation I'd like to make is that the growth in the number of prefixes is not clearly superlinear as the draft appears to assert. I have used a technique of taking the one hour snapshots of the BGP table size for the so-called DFZ and firstly generating a daily average, and then applying a sliding window smoothing function to generate a smoothed curve (slide 19 of the pack). I can then generate the daily differences to generate a first order differential (slide 20). If this first order derivative is approximately linear (green line in that slide) then the underlying data function is a second order polynomial (quadratic). If this first order derivative is increasing then the underlying data function is either a higher order polynomial or an exponential function. 

What is evident in the data is the global recession in 2009. What is not clearly evident is that the 6 year trend of this first order differential of growth is anything other than a relatively uniform linear function. This assumption of a linear first order differential yields a polynomial data function of F = 1389 year2 – 5545164 year + 5533345999, which is compared to the raw data on slide 21. I'd offer the opinion that the extended model of eBGP table growth fits a quadratic function remarkably well (x**2) at the moment, and that there is less compelling evidence to suggest that the growth is exponential with a constant doubling period (e**x). Projections of growth of this model are on page 23.

So I agree with your observation that the growth in the number of routed prefixes in BGP in the public Internet is higher than linear, but the long term data series leans towards a model of quadratic growth over a model of exponential growth of this data.

The other observation you make here is based on analysis in 2005 of the update rates of BGP. I claimed in early 2006 that the overall rate of growth of BGP updates is increasing. Further analysis based on observation of the ensuing 5 years of BGP behaviour suggests that I was wrong in making that claim.

Slide 35 of the presentation plots the number of updates each day. When I remove the updates that were the outcome of local BGP session resets (full table transfer). Whats left is a data series of non-local updates that in the first instance looks to be decreasing rather than increasing. A multi-year view (page 36) suggests that the long term trend is a constant, of some 90,000 updates per day (slide 36). Any growth trend in the data is linear at best (slide 37). Withdrawals are similar. They are decreasing, not increasing. The multi-year trend is not so apparent (slide 39), but I'm hesitant to make any claims here about longer term trends.

I then looked at the data using a different form of filter - asking the question "how many prefixes were the subject of oner or more BGP updates each day?". Here (slide 41) you can clearly see those days where there were one of more local session resets (top data series). On the other days where there was no full table reset the number of prefixes that were the subject of updates is close to a constant for some years (page 42). I find this somewhat surprising, but it is certainly part of the data.

In order to understand this a little better I split the updates into isolated events where a given prefix was updated (withdrawn or announced) as an isolated event, and "sequences" where the same prefix is updated multiple times, with no more than 4 MRAI intervals (130 seconds to be precise) between successive updates. The daily number of such convergence sequences is also close to constant over the past 1,000 days. The average time duration of the convergence sequences has been relatively steady at some 73 seconds, and the number of updates in the convergence sequence has been steady at 2.7 updates on average.

In the past 1,000 days the network has increased in population by some 40%, yet the metrics of instability in the network appear to be stable. (I have to say that this is a surprising result. Its a bit like taking the same trip to work each day in your car for years, and noticing that over time the roads have not changed, but you have seen that the number of cars on the roads has doubled, yet your trip to work takes the same time! This observation about the stability of long term convergence behaviour in BGP seems in the first instance to be counter-intuitive.)

In attempting to find a metric of the topology of the Internet that had some correlation to convergence behaviour I plotted the distribution of the number of convergence events of each size over the past 1000 days against the distribution of AS path lengths in the BGP route table. For the first 11 entries, or for 98.6% of all convergence events the correlation is surprisingly good (slide 54).

I suspect that the instability of BGP in terms of the behaviour of a distance vector protocol that is seeking to reach a converged state is related primarily to the metric of the diameter of the network, and not primarily related to the number of discrete elements (prefix count or AS count) that participate in the distribution computation that is the routing protocol. As long as the "diameter" of the network remains approximately constant then the instability of the network (or the convergence properties of the network) is also relatively stable. I therefore cannot completely agree with the assertions in section 5.1 of the draft, and would offer the alternative view that for as long as continued growth of the Internet remains within an overall characteristic of increased "density" while preserving its overall "diameter", then the topology factor that would increase the "amplification" factor of distance vector protocol convergence computation remains bounded. (Parenthetically, if this is indeed the case, then it is possible that slight changes to BGP may provide significant payback in terms of further reducing the update load associated with the convergence seeking behaviour of BGP. The ideas described in draft-li-bgp-stability-01.txt (from 2007) points to one such approach (section 4.3) where a modification of the MRAI behaviour allows a reduction in the number of updates that are generated in the convergence seeking process while having minor impact on the overall time to reach convergence. There may well be other approaches of a similar form.)

As your draft notes, it remains the case that the distribution of updates is a heavy tail distribution, and 1% of the origin ASs continue to contribute more than 40% of the update load in  BGP (recent data is at http://bgpupdates.potaroo.net/instability/bgpupd.html). (again parenthetically, this observation may also provide some approaches to update filtering that would attempt to filter out persistent instability from BGP updates.)

In any case, I would offer the opinion that there is more to understand about the actual behaviour of this network in terms of dynamic routing behaviour. It is not immediately apparent that the underlying growth over the past few years of BGP in both population count and in dynamic update behaviour in and of itself represents sufficient grounds to believe that BGP routing is in a dire place at present. However, it is an unconstrained system as you point out in section 3.2 of your draft, and the pressures of address exhaustion in IPv4 in the coming years represent a massive unknown when attempting to forecast the near term future for routing scale. 

   Geoff

---

From: Robin Whittle <[email-masked]>
Date: Fri, 05 Mar 2010 00:37:17 +1100

Hi Geoff,

In the "Re: [rrg] draft-narten-radir-problem-statement-05.txt" thread
  http://www.ietf.org/mail-archive/web/rrg/current/msg06152.html

and in "BGP in 2009":
  http://www.potaroo.net/presentations/2010-02-01-bgp2009.pdf

you presented some interesting research about DFZ activity.  I think
we are all greatly indebted to you for your long-term, BGP data
gathering and for your detailed and continuing analysis.

(Unfortunately, your mail client sends each paragraph as a single
line, so the web-archives require a copy and paste to an editor in
order to read them.)

I agree with your slide 30 comment:

    BGP Scaling and Table Size
      As we get further into the IPv6 transition we may see:

        – accelerated IPv4 routing fragmentation as an outcome
          from the operation of a V4 address trading market that
          starts to slice up the V4 space into smaller routed
          units

        – parallel V6 deployment that picks up pace

However, I think increasing growth in the number of IPv4 DFZ prefixes
will increase, for the reasons you suggest, irrespective of however
rapidly IPv6 is adopted.

It is puzzling that there is continued growth in the number of IPv4
DFZ prefixes while the rate of updates remains static.  Perhaps an
increasing proportion of end-user networks and ISPs are keen to avoid
being mentioned in your BGP Hall of Shame, AKA "The BGP Instability
Report":

   http://bgpupdates.potaroo.net/instability/bgpupd.html

I think your work is an excellent analysis of the most visible part
of the routing scaling problem - analogous to the part of the iceberg
which is above water: the burden on the DFZ control plane due to PI
prefixes and due to unreasonably frequent updates to a small subset
of all advertised prefixes.

Keeping a lid on these problems is important.  However, the
harder-to-measure part of the routing scaling problem is the large
number of end-user networks which want or need Portability,
Multihoming and/or inbound TE but can't get them due to the costs and
other barriers involved in gaining and advertising PI space in the
IPv4 DFZ.

Brian Carpenter recently suggested we should expect something in the
order of 10^7 such networks:

  http://www.ietf.org/mail-archive/web/rrg/current/msg05801.html

     Firstly, I'd like to support the ten million estimate. Based on
     the projected world population of just under ten billion by
     2050, that amounts to one enterprise per thousand humans, and
     that seems to be roughly what you find in the available data for
     developed economies (ignoring dummy companies and sole
     practitioners).

I have made the same 10 million WAG on the same basis.

This is not counting mobility, which could easily go to 3 or 5
billion hand-held devices in the foreseeable future, and perhaps as
high as 10 billion in the next century.  Some people exclude mobility
from the routing scaling discussion, but mobility is prominently
mentioned in the RRG's Charter.  With the TTR Mobility architecture:

  http://www.firstpr.com.au/ip/ivip/TTR-Mobility.pdf

a Core-Edge Separation architecture such as Ivip or LISP can be
extended to provide a globally mobile IPv4 address or IPv6 /64 to
mobile nodes, no matter how they connect to the Net (including behind
NAT or on scalable "edge" addresses) - with no mapping update
required when the MN gains a new address or access network.

I just wrote a message "Recommendation suggestion from RW" which
summarizes all the things I believe are important about scalable
routing and the opportunity we have for making major architectural
upgrades to IPv4 and IPv6.  Its nearly 10k words - but I hope you
would find it interesting.

  - Robin

---

From: Robin Whittle <[email-masked]>
Date: Sat, 13 Mar 2010 14:29:14 +1100

Hi Paul,

I am replying to your message

  Re: [rrg] 2 Possible Consensus Items
  http://www.ietf.org/mail-archive/web/rrg/current/msg06277.html

in this earlier thread:

  http://www.ietf.org/mail-archive/web/rrg/current/msg06163.html

since you were discussing Geoff Huston's research and the question of
the current interdomain routing system and its routers scaling.

>   http://www.potaroo.net/presentations/2010-02-01-bgp2009.pdf

You wrote, in part:

  It's possible that the current architecture of the internet is
  holding back growth that should otherwise be there.

Yes.  If we concentrate only on non-mobile networks, there are two
broad aspects of the routing scaling problem:

  1 - The unreasonable, arguably unscalable, burden placed on the
      DFZ routers individually, and on the DFZ control plane in
      general, by the set of end-user networks which currently
      get portability, multihoming and inbound TE by the only
      means available: getting their own space and advertising it
      as PI prefixes in the DFZ.

  2 - The much larger number of end-user networks which could use 2
      or more ISPs and which want or need portability, multihoming or
      inbound TE but don't have it because they are unable to get the
      space and advertise it.  (Perhaps a subset of these could do
      it, but don't because they known how unscalable it is.)

The growth in BGP advertised PI prefixes is the simplest measure of
the first aspect - which is like the tip of the iceberg.  The less
visible part is point 2, like the main body of the iceberg.

Then there is mobility - which has a prominent place in the RRG
Charter's description of the routing scaling problem.  Broadly
speaking, mobility is a whole other iceberg, so far completely submerged.

So even if Moore's Law keeps up in some acceptable manner with the
pace of growth in the number of PI prefixes in the DFZ, this doesn't
help with point 2 or with mobility.

Sorry I haven't had time to revisit our discussions in early
February.  I have a backlog of RRG messages to read and respond to -
mainly discussion following from my critiques of several
architectures - and I need to give priority to paying work.

  - Robin

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 12 Mar 2010 23:22:09 -0500

>      as PI prefixes in the DFZ.

it's not just their own space, it's PA space as well, leaked around
the provider, or through the provider.

>      it, but don't because they known how unscalable it is.)

I reckon most folks don't do it because they haven't hit a reason that
they see to actually do it. If there were a scalable, simple method
for most anything to be 'multihomed' I suspect you'd see a whole lot
more multihoming going on (or mobility, or simple device/network
agility)

> speaking, mobility is a whole other iceberg, so far completely submerged.

providers see this in their own networks, but today the technology
doesn't work/exist (no need to debate which) to have this work
reliably and simply across provider boundaries, so it seems
'submerged'.

> help with point 2 or with mobility.

Tony's and VInce's work seems to say that moores law: 1) isn't going
to cut it, 2) doesn't apply anyway... we should just drop this from
the idea bench.

-chris

---

From: Robin Whittle <[email-masked]>
Date: Sat, 13 Mar 2010 23:09:13 +1100

Hi Chris,

> the provider, or through the provider.

OK - for brevity I usually write just PI prefixes, but I understand
some end-user networks get a prefix as PA space from one ISP and then
have another ISP advertise it for multihoming service restoration.

> they see to actually do it. 

A reason strong enough to get a bunch of address space from an RIR,
with whatever initial and ongoing expenses that involves, plus having
their ISPs advertise it.

> If there were a scalable, simple method

Yes - including multihoming a small business network which uses
relatively inexpensive connections, such as DSL, fibre, HFC cable or
WiMAX.  Such networks would generally never have the resources or
expertise to get address space, or the type of Internet connectivity
which ISPs are ready to use with prefixes they advertise in the DFZ.

I think most networks on these DSL etc. services don't need
portability or multihoming, but I think we should aim for a scalable
routing solution which is light-weight enough that those who do what
these benefits should be able to get it, without too much expense,
administrative stuff or expertise.  I think my Ivip system could do this:

  http://tools.ietf.org/html/draft-whittle-ivip-arch
  http://tools.ietf.org/html/draft-whittle-ivip-drtm

and that LISP could too, if it adopted a mapping system like DRTM and
 if it involved address arrangements along the lines I plan for Ivip.

Dino recently mentioned (msg06229):

  > No, no renumbering required. Plus we want people to use their
  > existing PI or PA prefixes as EID-prefixes when they convert to
  > LISP.

I can't imagine how it could be scalable or desirable for end-user
networks to use their PA prefixes as EIDs.  Each EID prefix needs to
be covered by a "coarse" prefix which is advertised by multiple PTRs
in the DFZ. (For Ivip, each micronet is within a MAB which is
advertised in the DFZ by multiple DITRs).

These "coarse" prefixes (MABs) need to cover the EID prefixes
(micronets) of many end-user networks, otherwise there is
insufficient scaling benefit.

There's no way I can imagine sufficient routing scalability
improvements being achieved by converting an isolated PA prefix into
an EID, since each such EID prefix, or set of them for one end-user
network, would need its own "coarse" prefix in the DFZ.

> reliably and simply across provider boundaries, so it seems

I am keen to get some critiques / discussion of the TTR Mobility
architecture, which will provide globally mobile global unicast
addresses for mobile nodes, for IPv4 and IPv6, no matter what sort of
address the MN has, including behind NAT:

> to cut it, 2) doesn't apply anyway... we should just drop this from

I agree.  We can't keep relying on semiconductors becoming more powerful.

  - Robin

---

From: Paul Jakma <[email-masked]>
Date: Sun, 14 Mar 2010 17:30:18 +0000 (GMT)

>>   http://www.potaroo.net/presentations/2010-02-01-bgp2009.pdf

Those are the ones. I'd read that email too, but had forgotten of its 
existence in replying to this thread - thanks for highlighting it.

>      as PI prefixes in the DFZ.

Well, why is it "unreasonable" exactly? If the system works and is 
scalable, what's the problem?

It's only unreasonable if there's a /good/ way to keep those prefixes 
out of the DFZ (i.e. good in the sense that it's at least as good as 
what we have today). If such a way exists, then that's great - we 
should definitely research ways to improve routing, of course.

However, it does not seem justified to say the current routing 
architecture has a scaling problem. So it would not be justified, at 
thhis time (AFAICT), to excuse inefficiencies added by proposed 
changes on the basis that there's a pressing problem with the current 
architecture.

> visible part is point 2, like the main body of the iceberg.

Well, the internet is going to grow. That's hardly a surprise. What's 
the problem with the internet growing? Geoff's results seem to show 
that the growth is well within the scaling abilities of the 'net.

> pace of growth in the number of PI prefixes in the DFZ, this 
> doesn't help with point 2 or with mobility.

Sure, but:

a) If the scope of the problem suddenly is "those very small
    networks which want portability/multi-homing but aren't big enough
    to get an AS and PI", then:

    - it's a much, much smaller problem in terms of affected parties
      than "internet routing doesn't scale"

    - it's not clear even that such networks exist to any
      meaningful extent (OK, I'm geeky enough that I'd love portability
      and multihoming for my home network), i.e. if this is the
      problem being solved then that changes the economic incentives
      of roll-out.

b) If the problem is that fewer networks today can get PI, then we
    should be able to see a change in the mode of prefix growth in the
    historical data. However, TTBOMLK, we don't see this in the data.

Basically, if there's a problem then where is the evidence of it, now 
that we seem to have initial evidence to suggest otherwise?

> February.  I have a backlog of RRG messages to read and respond to 
> - mainly discussion following from my critiques of several 

No worries, that was just speculation on my part anyway. :)

regards,
-- 
Paul Jakma	[email-masked]	Key ID: 64A2FF6A
Fortune:
If you don't have a nasty obituary you probably didn't matter.
 		-- Freeman Dyson

---

From: Amund Kvalbein <[email-masked]>
Date: Sun, 14 Mar 2010 21:33:44 +0100

Folks,

In this context, I think you might be interested in a measurement study 
that will be presented at INFOCOM this coming week. The focus of the 
study is BGP scalability with respect to churn rates. We have analyzed 
six years of Routeviews BGP update traces from four monitors in 
different tier-1 networks.

Some of the main findings are that
- BGP churn varies widely on many time scales, and cannot be understood 
through "black-box" statistical analysis.
- The most severe churn experienced by these monitors are caused by 
mis-configurations and events that are local to the monitored AS.
- Surprisingly, as much as 40% of churn consists of duplicate 
announcements, which are unnecessary for correct protocol operation. 
This figure has been pretty constant over our measurement period.
- After filtering out duplicates, local effects and anomalies caused by 
a few specific events, we find that there is an increasing trend in 
"baseline" churn over the past six years, but that this growth is quite 
modest, and much slower than the growth in the DFZ RIB size.

The paper can be found at
http://simula.no/research/nd/publications/Simula.nd.435
Comments are always welcome.

Regards,
Amund

----

Amund Kvalbein, Post Doc
Simula Research Laboratory
http://simula.no/people/amundk

On 14. mars 2010 18:30, Paul Jakma wrote:
> what we have today). If such a way exists, then that's great - we should
> definitely research ways to improve routing, of course.
>
> thhis time (AFAICT), to excuse inefficiencies added by proposed changes
> on the basis that there's a pressing problem with the current architecture.
>
> the problem with the internet growing? Geoff's results seem to show that
> the growth is well within the scaling abilities of the 'net.
>
>> Sorry I haven't had time to revisit our discussions in early February.
>> I have a backlog of RRG messages to read and respond to - mainly
>> discussion following from my critiques of several architectures - and
>> I need to give priority to paying work.
>

---

From: Robin Whittle <[email-masked]>
Date: Mon, 15 Mar 2010 14:16:16 +1100

Short version:   Paul appears to think there is no routing scaling
                 problem.

Hi Paul,

> existence in replying to this thread - thanks for highlighting it.

Also, as just mentioned by Amund Kvalbein:

   BGP churn evolution: A perspective from the core

http://simula.no/research/nd/publications/Simula.nd.435/simula_pdf_file

> scalable, what's the problem?

I understand that many people regard it as unreasonable that the act
of some end-user network somewhere in the world advertising its own
prefix in the DFZ (typically their PI prefix, but also sometimes a
prefix they got as PA space from an ISP other than the one they are
now advertising it through) causes a real burden on all DFZ routers
and on the DFZ control plane in general.  This is because the people
who run these DFZ routers receive no payment, and little or no
benefit, from that prefix being advertised in the DFZ.  Cumulatively,
these prefixes add up to the single biggest identifiable problem at
the heart of the routing scaling problem.

> definitely research ways to improve routing, of course.

This is what we have been doing since the RAWS workshop in 2006, and
some folks have been researching this since before RAWS.

> architecture has a scaling problem. 

Whoah . . .  You are arguing against the positions of pretty much
everyone who is involved in the RRG.  Please see 17.2.x of:

  http://www.ietf.org/mail-archive/web/rrg/current/msg06219.html

for a summary of my understanding of the nature of the problem.  See
also:

   http://tools.ietf.org/html/rfc4984
   http://www.iab.org/about/workshops/routingandaddressing/
   http://tools.ietf.org/html/draft-irtf-rrg-design-goals-01
   http://tools.ietf.org/html/draft-narten-radir-problem-statement-05

> So it would not be justified, at

You have asserted there is no routing scaling problem, but you
haven't argued why this is the case - such as by arguing in detail
against the arguments presented in the five above documents.

> the growth is well within the scaling abilities of the 'net.

That's not what most RRG people think, and the above documents
include many arguments for why we think this.

>      than "internet routing doesn't scale"

It is an instance of the needs of many networks not being met by
current techniques.  Since there is a growth in this number of
networks, this is arguably a scaling problem.

>      problem being solved then that changes the economic incentives

I understand the RRG's aims are not just to get existing
PI-advertising end-user prefixes to change to using a new arrangement
with less burdens on the DFZ control plane, or to cope with the
expected growth in networks of the same nature (same size, same
needs, same resources).  I understand our aim includes providing a
more accessible and highly scalable method by which a larger number
of end-user networks can get portability, mulithoming and inbound TE
than those which currently get it via advertising their own prefixes
individually in the DFZ.

Furthermore, we are aiming to find a better, scalable, form of mobility:

  http://www.irtf.org/charter?gtype=rg&group=rrg

    At the moment, the Internet routing and addressing
    architecture is facing challenges in scalability, mobility,
    multi-homing, and inter-domain traffic engineering. Thus the RRG
    proposes to focus its effort on designing an alternate
    architecture to meet these challenges.

>    historical data. However, TTBOMLK, we don't see this in the data.

The mapping for TTBOMLK was not in my cache.  Google resolved my
query in a fraction of a second:

  To The Best Of My Knowledge

Its is not that fewer networks advertise PI prefixes today than in
the past, but that there is a growing number of networks wanting
portability, multihoming and inbound TE, that only a subset of them
are getting this at all (through advertising their PI prefixes or PA
prefixes, individually), that there are already too many who can't
get these benefits and that due to growth in the number of networks
of this kind, more and more cannot get these benefits at all - while
the subset who do get these benefits do so in a way which (we
believe) involves unfair and unsustainable burdens on others.

>> mainly discussion following from my critiques of several architectures
>> - and I need to give priority to paying work.
> 

OK - in the context of the work which has been done so far, I suggest
that your assertion that there is no routing scaling problem is just
speculation too!

  - Robin

---

From: Paul Jakma <[email-masked]>
Date: Mon, 15 Mar 2010 04:27:47 +0000 (GMT)

> http://simula.no/research/nd/publications/Simula.nd.435/simula_pdf_file

Yes, saw the post of that. Its conclusion does not disagree with 
Geoff's results, indeed it seems to concur somewhat. (Geoff goes 
further and made the neat observation about possible correlation with 
path-length, I think).

> DFZ.  Cumulatively, these prefixes add up to the single biggest 
> identifiable problem at the heart of the routing scaling problem.

Well, let's look at the flip-side for a moment. Imagine if there were 
/no/ growth in prefixes. Is that good? I think the answer clearly is 
"no". No growth in prefixes implies no growth in the internet, 
implies no growth in revenue for those who make money from activities 
associated with attaching to the net.

I.e. given much of the planet does not have internet access, and 
hence assuming the internet is at least a few decades away from any 
natural slow-down in growth due to saturation (I havn't plugged Brian 
Carpenters 10M prefix figure into Geoff's growth formula, but it 
feels like we've got at least a decade to go):

 	growth in prefixes == good
 	growth in prefixes == healthy internet

So to some extent, (I would say a greater degree) growth in prefixes 
is desirable, at this time.

> some folks have been researching this since before RAWS.

Well, yes. I know.

I've been discussing scalable and/or IPv6 multihoming with people on 
lists on/off for approaching a decade, perhaps a little more (i'd 
have to go check my mail archives).

> everyone who is involved in the RRG.  Please see 17.2.x of:

Yes. I know. I used to not doubt much there was a scaling problem 
myself (that's what everyone thought and why should i disagree?). 
It's hard to maintain that view though when data starts coming in 
that seems to suggest otherwise. If we're to be scientific about 
this, we have to take heed of data.

> You have asserted there is no routing scaling problem,

Did I?

Could you go perhaps go back to my message where I said how I wished 
to vote. I think you'll find you've misunderstood me.

> but you haven't argued why this is the case - such as by arguing in 
> detail against the arguments presented in the five above documents.

Why do I need to argue the case?

Let the data do the arguing. At the moment it's looking like BGP 
maybe is coping with growth just fine. I.e. we can not yet safely 
conclude there is an urgent scaling problem with internet routing 
(despite path-vector being known now to have some inefficient 
behaviours even when working as intended).

Where's the data suggesting routing is or is going to run into 
problems? Not /fears/ that it will, but actual data.

> query in a fraction of a second:

I didn't invent TTBOMLK on the fly and so it's certainly more 
googleable than some acronyms, yes. ;)

>  To The Best Of My Knowledge

The L is "Limited". fwiw ;)

> OK - in the context of the work which has been done so far, I 
> suggest that your assertion that there is no routing scaling 
> problem is just speculation too!

I suspect you've misunderstood my scribblings.

regards,
-- 
Paul Jakma	[email-masked]	Key ID: 64A2FF6A
Fortune:
Chinese saying: "He who speak with forked tongue, not need chopsticks."

---

From: Robin Whittle <[email-masked]>
Date: Mon, 15 Mar 2010 16:00:18 +1100

Hi Paul,

You wrote:

>> Could you go perhaps go back to my message where I said how I
>> wished to vote. I think you'll find you've misunderstood me.

I have not mentioned anything about voting - there is no voting in
the RRG, and I understand no attempt will be made to seek or reach
consensus on the final recommendation. (msg06220)

I thought that you were arguing against the existence of the routing

  > architecture has a scaling problem.

Since I have difficulty understanding what you describe as your
"scribblings" in a manner you agree with, I will not pursue this
discussion further except to note that:

  1 - I was not complaining about "TTBOMLK".

  2 - I disagree with your "Let the data do the arguing." - people
      can argue, data can't.

  3 - Our arguments must concern our reasonable fears about the
      future, since we have no data about the future.

  - Robin

---

From: Paul Jakma <[email-masked]>
Date: Mon, 15 Mar 2010 05:17:17 +0000 (GMT)

On Mon, 15 Mar 2010, Robin Whittle wrote:

> I thought that you were arguing against the existence of the 
> routing scaling problem, because in your first message in this 
> thread, you wrote:
>
> "scribblings" in a manner you agree with,

If a person disagrees that a hypothesis has been proven, it does not 
of itself follow that the person believes the hypothesis has been 
disproven.

You seem to exclude "Insufficient evidence at this time to draw a 
conclusion" from the set of valid views people may hold on a topic 
(as does the straw poll that led to me post).

regards,
Necessity hath no law.
 		-- Oliver Cromwell

---

From: Tony Li <[email-masked]>
Date: Sun, 14 Mar 2010 23:35:40 -0800

Hi Paul,

> associated with attaching to the net.

Actually, no growth in prefixes does not imply that there is no growth in
the Internet.  You can still add customers within existing prefix
allocations and improve your addressing efficiency.

Also, since you can grow the net very efficiently with even a tiny amount of
prefix additions, it would seem like much, much, much slower growth would be
acceptable to meet your reasonable request that the Internet keep growing.

> behaviours even when working as intended).

First, no one is claiming that there is an imminent and urgent problem.
What I feel that we've shown is that we have a long term systemic problem.
Given that truly dealing with this issue does appear to require major
amounts of time to deploy, it only seems reasonable to start dealing with it
long before it becomes an urgent problem.
 
> problems? Not /fears/ that it will, but actual data.

Please see my RAWS presentation.  It shows that prefix growth exceeds the
speedup that we can expect in DRAM.  This in turn implies that BGP will take
longer to converge at a given node when that node has to process the full
table.

Tony

---

From: Lixia Zhang <[email-masked]>
Date: Sun, 14 Mar 2010 23:43:20 -0700

On Mar 14, 2010, at 1:33 PM, Amund Kvalbein wrote:

> Folks,
>
> In this context, I think you might be interested in a measurement  
> study that will be presented at INFOCOM this coming week. The focus  
> of the study is BGP scalability with respect to churn rates. We have  
> analyzed six years of Routeviews BGP update traces from four  
> monitors in different tier-1 networks.
>
> - BGP churn varies widely on many time scales, and cannot be  
> understood through "black-box" statistical analysis.

we did a measurement study to understand the causes of such excessive  
duplicate announcements, the results are reported in the following  
paper:
"Investigating Occurrence of Duplicate Updates in BGP Announcements"
http://www.cs.ucla.edu/~jpark/dupbgp.pdf
to be presented at PAM conference next month

An earlier presentation can be found at
    http://www.cs.ucla.edu/~jpark/grow-5.pdf

> - After filtering out duplicates, local effects and anomalies caused  
> by a few specific events, we find that there is an increasing trend  
> in "baseline" churn over the past six years, but that this growth is  
> quite modest, and much slower than the growth in the DFZ RIB size.
>

---

From: Lixia Zhang <[email-masked]>
Date: Mon, 15 Mar 2010 00:16:04 -0700

> (as does the straw poll that led to me post).

it is interesting to watch this series of exchange between Paul and  
Robin:)
One position states that we face serious routing scalability problem  
today.
another position states that insufficient evidence exists today to  
support the above.

If I take on a 3rd position: this debate seems a supporting evidence  
for what we discussed at Hiroshima meeting (see my presentation on  
behalf of the evolution solution team, http://www.cs.ucla.edu/~lixia/aggregation.pdf 
, slide 4),
- Internet is big and diverse -> routing scalability problem
   is not universal
- Internet has no boss -> no universal buy‐in, no flag day/year/decade

Thus we need solutions that can be deployed by individual parties who  
need it, and can provide clearly identifiable returns (slide 5)

Lixia

---

From: Tony Li <[email-masked]>
Date: Mon, 15 Mar 2010 00:42:08 -0800

[Off topic warning...]

> to be presented at PAM conference next month

Interestingly, I'm not sure that this is worth fixing.  Most BGP
implementations store a copy of all of the best paths that they've received
from neighbors.  They then compute the 'best path' amongst this set and
advertise it appropriately.  Truly fixing this problem would require that an
implementation retain state on a per-neighbor basis about which attributes
were advertised (and in some cases, what changes to what attributes were
performed).  Further, the implementation would still have to effectively
compute the update because output policy could have a substantial impact on
the result.  Thus, the question really becomes whether transmitting the
update and receiving it is more expensive than additional filtering in the
sender.  Given that bandwidth is 'free', the tradeoff is now between the
sender with additional state and processing, or the processing in the
receiver.  Note that the receivers task is to parse the update, realize that
there is, in fact, no change, and not do anything.

Tony

---

From: Tom Vest <[email-masked]>
Date: Mon, 15 Mar 2010 08:33:48 -0400

Paul raises a critical point that IMO gets insufficient attention here... 

> allocations and improve your addressing efficiency.

Point of clarification: 
*Existing* (aka incumbent) providers may be able to add additional customers under *existing* prefixes.
It's not possible to assume anything beyond that without assuming facts not in evidence  -- e.g., a widely adopted new architecture, and/or a widely adopted new addressing format (IPv6), and/or a widely adopted mechanism for redistributing IPv4 address space that is already allocated.

The implication is that while this possibility may exist (for some), its existence doesn't matter (in general).

> acceptable to meet your reasonable request that the Internet keep growing.

It seems that the problem of "super-linear" growth in demands on the routing system is one of (if not THE) most central issues motivating this exercise. And yet the ambiguous nature of this characterization is apparent even in draft-narten-radir-problem-statement-05.txt. 

Assuming that "super-linear growth" is driven by some combination of factors like

(a) new routing service providers, plus
(b) incremental address provisioning (i.e., post-CIDR IPv4 scarcity management), plus
(c) new sites, plus
(d) multihoming, plus
(e) supplemental traffic engineering,

...any new architecture that solves this routing *inflation* problem, but in the process suppresses (a), or leaves (a) to be sorted out through exogenous mechanisms is quite likely to create the opposite problem. IMO, any network architecture that is inherently vulnerable to that other risk of routing system *deflation* -- i.e., the arbitrary rationing/structural exclusion of future aspiring routing service providers -- is unlikely to be widely adopted, and should be considered harmful, fatal. 

In short, that first factor -- new entrants into the routing services sector -- constitutes an upward-sloping growth "line" that *must* be sustained, no matter how effective or ineffective the new architecture is in eliminating the "super-linear" scalability problems caused by the other factors.

> long before it becomes an urgent problem.

I would argue that the exhaustion of unallocated IPv4 represents a very imminent an urgent problem, for the same reason outlined above. Given current architecture and the current state of IPv6 deployment, (a) shares fate with the availability of unallocated IPv4.

No doubt if (when) the existing mechanisms for sustaining (a) no longer work, other forces will come into play in response to the unmet demand (e.g., markets, regulation, piracy, etc.). But as a result, the base rate of new entry (a) will no longer be strongly influenced by technical scalability considerations -- and the collateral effects of those external forces could have additional, unpredictable effects on the deployability or other scalability benefits (ala b~e) of the new architecture. 

> longer to converge at a given node when that node has to process the full

I agree that premature obsolescence/abandonment and/or collapse is a real problem, but I think we should recognize that routing system inflation is just one (of at least two) paths that lead in that general direction.

TV

---

From: Paul Jakma <[email-masked]>
Date: Mon, 15 Mar 2010 17:13:11 +0000 (GMT)

> allocations and improve your addressing efficiency.

Hehe, My implicit assumption is that there's no significant change in 
allocation densities. :) Stuff like that generally seems to be an 
administive issue, so it's maybe unlikely it can be affected through 
routing changes.

> First, no one is claiming that there is an imminent and urgent 
> problem. What I feel that we've shown is that we have a long term 
> systemic problem. Given that truly dealing with this issue does 
> appear to require major amounts of time to deploy, it only seems 
> reasonable to start dealing with it long before it becomes an 
> urgent problem.

> Please see my RAWS presentation.  It shows that prefix growth 
> exceeds the speedup that we can expect in DRAM.

I remember reading that.

> This in turn implies that BGP will take longer to converge at a 
> given node when that node has to process the full table.

That's the thing though, the most recent data doesn't seem to show 
any evidence of things like that. If per-node convergence was taking 
significantly longer (in the "scaling badly relative to prefix 
growth" sense), then Sigma(per-prefix per-node convergence) should be 
similarly increasing by at least the same amount and BGP observers 
ought to be able to see that, and so the data should show it.

Yet it doesn't seem to, right?

Further, even if the growth issues only affected a certain subset of 
prefixes, surely there'd be "side-band" issues. I.e. processing 
problems with certain prefixes should adversely affect the processing 
of other prefixes being processed around the same time.

I'm sorry for being such an arse with my scepticism, and I'll 
understand if people reply to me as if I'm half-wit, but if scaling 
is a problem surely it should be apparent in some data somewhere over 
the last decade+ that people have been worrying about it? Where's the 
smoking gun graph, based on real data, that shows the scaling 
problem? I'm somewhat willing to take your word as authoritative, but 
ideally we'd have graphs :).

I stress again that, despite taking this contrarian view of the 
scaling problem, I still think the work here is very important!

I just think this question must have a big impact on which classes of 
solutions are and are not viable.

regards,
-- 
Paul Jakma	[email-masked]	Key ID: 64A2FF6A
Fortune:
We don't understand the software, and sometimes we don't understand the
hardware, but we can *___see* the blinking lights!

---

From: Marshall Eubanks <[email-masked]>
Date: Mon, 15 Mar 2010 13:20:24 -0400

On Mar 15, 2010, at 1:13 PM, Paul Jakma wrote:

> Hehe, My implicit assumption is that there's no significant change  
> in allocation densities. :) Stuff like that generally seems to be an  
> growth" sense), then Sigma(per-prefix per-node convergence) should  
> be similarly increasing by at least the same amount and BGP  
> observers ought to be able to see that, and so the data should show  
> it.
>

Do you have a write-up of this ?

Regards
Marshall

> problems with certain prefixes should adversely affect the  
> processing of other prefixes being processed around the same time.
>
> is a problem surely it should be apparent in some data somewhere  
> over the last decade+ that people have been worrying about it?  
> Where's the smoking gun graph, based on real data, that shows the  
> scaling problem? I'm somewhat willing to take your word as  
> authoritative, but ideally we'd have graphs :).
>
> I just think this question must have a big impact on which classes  
> of solutions are and are not viable.
>
> regards,
> -- 
> _______________________________________________
> rrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/rrg
>

---

From: Paul Jakma <[email-masked]>
Date: Mon, 15 Mar 2010 17:30:01 +0000 (GMT)

On Mon, 15 Mar 2010, Paul Jakma wrote:

> in allocation densities. :)

Oops, here I mean allocation density on a per-prefix basis. (IPv6 
obviously completely changes HD on an proportion-of-address space 
basis - but shouldnt as much on a per-prefix basis).

regards,
-- 
Paul Jakma	[email-masked]	Key ID: 64A2FF6A
Fortune:
There's no time like the pleasant.

---

From: Paul Jakma <[email-masked]>
Date: Mon, 15 Mar 2010 17:51:02 +0000 (GMT)

> Do you have a write-up of this ?

See Geoff Huston's BGP in 2009 presentation:

   http://www.potaroo.net/presentations/2010-03-04-bgp2009.pdf

Also see the Simula report referred to in this thread, which does not 
disagree with Geoff Huston's data and findings.

regards,
-- 
Paul Jakma	[email-masked]	Key ID: 64A2FF6A
Fortune:
You'll never be the man your mother was!

---

From: Tony Li <[email-masked]>
Date: Mon, 15 Mar 2010 11:34:08 -0800

Hi Constantine,

> Toni, you are raising an interesting issue. However, if the sending routers
> do not check whether an update is duplicate, and if the receiving
> routers do not check whether an update is duplicate, don't we create
> a positive feedback loop?

Yes, but I think it was obvious that the receivers DO check.  If no one
checked, then any update would propagate throughout the net.  Yes, that
would be VERY, VERY bad. Lixia's paper pretty clearly stated that they were
only seeing duplicates go one hop.

Tony

---

From: Tony Li <[email-masked]>
Date: Mon, 15 Mar 2010 14:04:42 -0800

Hi Paul,

> administive issue, so it's maybe unlikely it can be affected through

It's not clear that that's a valid assumption, especially in the face of v4
runout.  Will people just become more efficient?  What happens if carriers
do deploy CGNAT?

> ought to be able to see that, and so the data should show it.

Disagree.  If I understand Geoff's data correctly (and please correct me if
I don't) he's showing that the overall stability of the network hasn't
changed.  The number of updates and the number of withdrawals is scaling
nicely.  He also shows that the incremental convergence of a prefix is
roughly constant.  

This is in no way contradictory to the increasing time that it will take a
router to converge.  The two measures are wholly orthogonal.

Again, consider the situation of a router rebooting somewhere in the middle
of the network.  When the router crashes, adjacent routers will select
alternate paths.  This convergence time is not going to be visible, as Geoff
is measuring the time that it takes from the first change to convergence for
that prefix.  Since the convergence time is largely dominated by MRAI
effects today, it will be difficult to perceive any increase in overall
convergence times due to scale.

Similarly, when a router comes up, it will begin learning and advertising
prefixes.  This will trigger another convergence effect, but the delay in
starting the event will not be shown in Geoff's data.  Subsequent delay in
processing by upstream routers will get lost in MRAI as before.  The router
convergence time that I'm concerned about is the time that it takes this new
router to learn and advertise the full table of routes.  Pretty clearly,
this time is linear in the number of prefixes.  Thanks to the existence of
multiple paths, this delay is not going to be seen by end nodes.

To see this effect more clearly, consider a thought experiment where it
takes a router an hour (or a day, a week or a month) to boot and process all
prefixes.  What is the effect on the network?  Would Geoff's numbers change?

> ideally we'd have graphs :).

<employer hat off>
Any operator who would like to stand up and embarrass their favorite router
vendor by showing a graph of router boot convergence times is welcome to do
so.  ;-)
</employer hat off>
 
> scaling problem, I still think the work here is very important!

I'll just point out the last slide of Geoff's talk:

"Will BGP Continue to Scale?

Only if: the address system continues to maintain strong alignment with
network topology & provider based addressing policies assist in maintaining
a viable global routing infrastructure."

The whole point of the work here is to decouple addressing from identity so
that it can be more easily aligned with topology.

Tony

---

From: Tony Li <[email-masked]>
Date: Mon, 15 Mar 2010 14:04:42 -0800

Hi Paul,

<employer hat off>

Tony

---

From: Christopher Morrow <[email-masked]>
Date: Mon, 15 Mar 2010 23:16:22 -0400

> vendor by showing a graph of router boot convergence times is welcome to do

eh, I don't have a hat nor a graph, but at a former employer we put a
great deal of stress on 2 vendors to bring cold-boot times under
15minutes (cold-boot -> normalized/converged full table). As I
understand things today at that employer, this time has been slowly
increaseing again :( it makes sense, based on the prior conversation.

Another point to keep in mind is that in the overall table let's say
there is a 1% churn per time period (per second for grins). That the
pathway from route-processor (or whatever the part that digests
inbound bgp messages is called on your fav platform) to
forwarding-bits (asics + tcam again whatever it is in your fav device)
can only handle 10,000 changes in that same time period. If the table
grows to beyond where 1% == 10k prefixes I don't think you can expect,
under normal conditions, convergence to ever happen.

Part of the RRG discussion gets back to 'can we sustain the current
model where every butterfly flutter is felt by all devices', this is
what the above is about. I don't think you'll be able to measure this
in the live network until you reach these limitations. I'm CERTAIN
Cisco/Juniper both have a graph that shows where their platforms start
not-converging under bgp update-load. It's trivial to extend that to a
constant X% of the table churning.

Now, keep in mind that Geoff's numbers are for 'full internet routes'
(DFZ routes perhaps even), not 'provider bgp table' which invariably
will include internal deaggregates + other address families.

-chris

---

From: Lixia Zhang <[email-masked]>
Date: Tue, 16 Mar 2010 00:28:52 -0700

top posting: it's my fault for not stating clearly -- Since Amund's  
msg said that

> announcements, which are unnecessary for correct protocol operation.

I was merely offering one explanation for the cause of the observed  
duplicates.
The least to say is that this is not RRG's job (hence the presentation  
was to GROW), even if worth fixing.

Lixia

---

From: Pekka Savola <[email-masked]>
Date: Tue, 16 Mar 2010 10:25:08 +0200 (EET)

> vendor by showing a graph of router boot convergence times is welcome to do

Ok, I'll jump on my soap box.  In worst case, Juniper high-end routers 
have been demonstrated to take up to 10 minutes to install RIB to FIB. 
During this time, packets usually get blackholed (aka "krt queue 
blocking").  See thread in j-nsp in Dec 2009:

http://www.mail-archive.com/[email-masked]/msg07663.html

A bit of continuation here:

http://www.mail-archive.com/[email-masked]/msg07833.html

This is not a new issue;  It has started appearing over 3 years ago:

http://puck.nether.net/pipermail/juniper-nsp/2007-February/007655.html
http://puck.nether.net/pipermail/juniper-nsp/2007-February/007575.html

I've personally pursued a case with Juniper TAC on this for a long 
time but eventually gave up.  One known architectural bottleneck is 
the slowness of RE-PFE IPC (unix socket), but I don't really belive in 
this being the root cause.  I know others have also tried to work with 
the vendor to get this fixed.

Semi-relevant may also be a graph of BGP update sizes during a BGP DFZ 
flap event that I sent to idr list three years back, showing that of 
87K BGP updates due to a single event, almost all of them are below 
100 bytes in size.

http://www.ietf.org/mail-archive/web/idr/current/msg02398.html

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

---

From: Zied BEN HOUIDI <[email-masked]>
Date: Tue, 16 Mar 2010 14:33:27 +0100

Hi,

I see two distinct issues in your post. The time to receive/send routes and
the time to install them back to FIB.

The first post is about the FIB installing time (krt queue blocking).

In the older posts (three years ago), it was probably more about route
sending rate.

http://puck.nether.net/pipermail/juniper-nsp/2007-February/007655.html
http://puck.nether.net/pipermail/juniper-nsp/2007-February/007575.html
"7 minutes seems rather long as the links between peers are between 2.5G to
10G"

This looks like an issue with the slow BGP route sending rate that we
discovered on routers from three different vendors. In fact, the sending of
routes is one order of magnitude slower than it should be (despite the high
link capacity, the table transfer was slow and both routers, the sender and
the receiver, were almost idle during the table transfer).
We found that it is due to the timer driven implementation of the
interaction between BGP and TCP. We showed, using a software BGP speaker
(sbgp) that an event driven implementation can reduce transfer times from 4
minutes to 7 seconds (680,000 routes). We also opened a case with one of the
router vendors. The vendor confirmed that it was due to the timer driven
implementation and modified its BGP implementation to be event driven.
Convergence time in the vendor's set up went from 12minutes to 47 seconds
with the new implementation/fix.

Here is an experimental study that we've made on this issue and on BGP
routing table transfers in general (it appeared in the last Internet
Measurement Conference IMC2009).
http://delivery.acm.org/10.1145/1650000/1644935/p350-benhouidi.pdf?key1=1644935&key2=8304478621&coll=GUIDE&dl=GUIDE&CFID=82157635&CFTOKEN=81293083
You may find more details about different factors that impact BGP routing
table transfers (route sending, table size, route installing, number of BGP
sessions, router CPU).

Kind regards,
---
Zied Ben Houidi
Phd Candidate at Orange Labs

2010/3/16 Pekka Savola <[email-masked]>

> Ok, I'll jump on my soap box.  In worst case, Juniper high-end routers have
> been demonstrated to take up to 10 minutes to install RIB to FIB. During
> this time, packets usually get blackholed (aka "krt queue blocking").  See
> thread in j-nsp in Dec 2009:
>
> I've personally pursued a case with Juniper TAC on this for a long time but
> eventually gave up.  One known architectural bottleneck is the slowness of
> RE-PFE IPC (unix socket), but I don't really belive in this being the root
> cause.  I know others have also tried to work with the vendor to get this
> fixed.
>
> Semi-relevant may also be a graph of BGP update sizes during a BGP DFZ flap
> event that I sent to idr list three years back, showing that of 87K BGP
> updates due to a single event, almost all of them are below 100 bytes in
> size.
>

---

From: Constantine Dovrolis <[email-masked]>
Date: Mon, 15 Mar 2010 11:37:33 -0400

Toni, you are raising an interesting issue. However, if the sending routers
do not check whether an update is duplicate, and if the receiving
routers do not check whether an update is duplicate, don't we create
a positive feedback loop? I mean, if a router X sends a duplicate
update to N other peers, then each of those other routers can also
generate duplicate updates sent to their own peers, creating a
multiplicative effect. Of course there are several factors that
would act to limit the dissemination of such updates, such as
policy, but in principle the positive feedback is still there, right?

-- 
Constantine

--------------------------------------------------------------
Constantine Dovrolis | 3346 KACB | 404-385-4205
Associate Professor  | Networking and Telecommunications Group
College of Computing | Georgia Institute of Technology
[email-masked]
http://www.cc.gatech.edu/~dovrolis/

---

From: Danny McPherson <[email-masked]>
Date: Thu, 18 Mar 2010 14:01:21 -0600

> there is, in fact, no change, and not do anything.
Indeed, you're trading systemic state for implementation optimizations,
in lots of places where issues such as this are amplified.  > 40%
duplicates in a system today ma not be a problem, however, if prefix,
origin, and path validation techniques are employed down the road in a
secure routing protocol built on the current model, and every one of
those updates have to be processed, I suspect at some point senders will
be a bit more conservative in what they send.

-danny

---

From: Geoff Huston <[email-masked]>
Date: Sat, 20 Mar 2010 08:15:09 +1100

> be a bit more conservative in what they send.

No necessarily - the receivers can cache validation outcomes with reasoinbly
efficient results. See http://www.potaroo.net/papers/phd/pam-2007/bgpcache.pdf
for a study of this approach.

regards,

   Geoff

---

From: Tony Li <[email-masked]>
Date: Fri, 19 Mar 2010 14:40:42 -0700

> for a study of this approach.

One can also point out that an update that is a duplicate of what's already
been accepted is irrelevant.  Regardless of whether it has been validated or
not.  

;-)

Tony

P.s. Ok, small exception in the case where you're in the middle of
transitioning from a non-validated world and you have accepted a
non-validated path and just received a validated path.

---

From: Geoff Huston <[email-masked]>
Date: Sat, 20 Mar 2010 09:44:46 +1100

> been accepted is irrelevant.  Regardless of whether it has been validated or

I'm not sure I understand this Tony. What is in my mind when I read this is 
a counter case when a BGP speaker sees from a peer:

advertise
withdrawal
advertise a dup of the previous advertisement
withdrawal
advertise a dup
etc

i.e. in this case the dups are not irrelevant, and in this case caching of previous
validation outcomes would be beneficial.

Geoff

---

From: Tony Li <[email-masked]>
Date: Fri, 19 Mar 2010 16:51:59 -0700

Hi Geoff,

> validation outcomes would be beneficial.

This is a different case than what I think we were discussing.  At least if
I understand the situation, Lixia and crew were seeing:

Withdrawl
Advertise
Advertise (dup)
Advertise (dup)
Advertise (dup)

Tony

---

From: Amund Kvalbein <[email-masked]>
Date: Sat, 20 Mar 2010 04:44:37 +0100

Yes, in the paper I mentioned (where we observe a sustained level of 
duplicates up to 40% in some monitors), this is the pattern we refer to

Withdrawl
Advertise
Advertise (dup)
Advertise (dup)
Advertise (dup)

Amund