Subject: [RRG] Opportunistic Topological Aggregation in the RIB->FIB Calculation?

From: "William Herrin" <[email-masked]>
Date: Mon, 21 Jul 2008 10:09:07 -0400

Hi Folks,

Iljitsch's current geoagg plan didn't pan out either, but it gave me
an idea. Your comments are requested.

Suppose when we calculate the FIB from the RIB, we do the following
optimization:

1. Determine which exit has the most routes pointing at it.
2. Add 0.0.0.0/0 pointing at that exit.
3. Mark the routes that point in that direction and aren't cutouts of
a larger route as non-FIB. These won't be imported into the FIB.
4. Mark the rest of the routes for import into the FIB.

5. Look at the routes in the two /1's inside that /0, considering both
the marked and unmarked ones. Do any of the /1's have the majority of
the routes pointing towards a different exit than the /0? If so, add
the /1 and change the markings on the subroutes accordingly.
6. If both /1's point a different direction than the /0, remove the /0.

7. Inside each /1, repeat steps 5 and 6 using /2's.
8. Repeat for /3, /4, ... /8

In theory, this should result in identical routing for all routes
which are actually in the RIB while cutting the FIB size
significantly. In the worst case you should see FIB reduction equal to
1/(number of BGP interfaces) of the RIB table. Near the edge you
should normally get much more.

The obvious weakness of this approach is that packets which would
ordinarily generate a host-unreachable will instead tend to fall into
an odd routing loop until the TTL expires. Other than that, would it
work?

Comments? Criticism? Further thoughts? It is Monday morning and I
haven't thoroughly vetted the idea so it may be DOA.

Regards,
Bill Herrin

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

--
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: "Tony Li" <[email-masked]>
Date: Mon, 21 Jul 2008 11:39:38 -0700

|Comments? Criticism? Further thoughts? It is Monday morning and I
|haven't thoroughly vetted the idea so it may be DOA.

If you look at techniques for just compressing the FIB, there are *many*
things that can and have been done.  

However, those optimizations are not going to impact the RIB and propagate
throughout the net.  [They also can end up being computationally intensive,
sliding the problem around on the time/space tradeoff curve, not necessarily
solving it...]

Again, the problem is not to address just the FIB, the point is to deal with
the overall scalability of the whole control plane.

Tony

---

From: "William Herrin" <[email-masked]>
Date: Mon, 21 Jul 2008 20:17:16 -0400

> the overall scalability of the whole control plane.

Tony,

I disagree.

The RIB cost grows with the width of the system times the number of
entries. The system width is staying relatively static (and that's
expected to continue), so the growth cost is close to linear with the
number of entries. We already know that a $5k ($2k if you're on a
budget) Linux server running Quagga can keep up with 10 times the
entries and churn. With PC hardware's price/performance doubling every
3 years, we haven't long to wait before it can easily handle 100 times
the entries and churn that we have today.

The FIB cost, on the other hand, grows with the number of entries
times the packets per second which have to be routed. Both numbers are
rising quickly and both threaten to move faster. At the bottom end we
can currently route about a gigabit through a server with only
commodity hardware. Beyond that, we need a TCAM or parallel SRAM-based
radix trees, both of which are quite expensive in terms of
manufacturing, electrical draw and heat dissipation. Worse, the static
ram cells used by both are lagging behind PCs overall in terms of
their rate of improvement. We've had 1-meg CPU caches since The Sparc
II in the early '90's. We're only now getting 3-megs per core on
current Xeons. That's only doubling every decade.

All of this means one simple thing: We'll hit the wall on the FIB's
capability long before we hit the wall on the BGP RIB's capability.

Absent a RIB+FIB solution that the operators are enthusiastic about,
it's worth the effort to consider approaches that only reduce the size
of the FIB.

Regards,
Bill Herrin

---

From: "Tony Li" <[email-masked]>
Date: Mon, 21 Jul 2008 18:51:06 -0700

Hi Bill,

I see we need to talk about the problem _again_.  ;-(

|The RIB cost grows with the width of the system times the number of
|entries. The system width is staying relatively static (and that's
|expected to continue), so the growth cost is close to linear with the
|number of entries. We already know that a $5k ($2k if you're on a
|budget) Linux server running Quagga can keep up with 10 times the
|entries and churn. With PC hardware's price/performance doubling every
|3 years, we haven't long to wait before it can easily handle 100 times
|the entries and churn that we have today.

In fact, the PC hardware doesn't actually do that.  What we really see is
that DRAM memory speed grows at about 1.2X every two years and that our
growth rate is at least 1.3X every two years.  Since BGP can't live in a
cache (at a sane price point), BGP's performance (or any other protocol that
would carry the same number of prefixes) is bounded to converge at the rate
that we can actually perform DRAM writes at.  As we're growing faster than
DRAM gets quicker, BGP necessarily converges a little more slowly every
year.  

See: 

http://www.iab.org/about/workshops/routingandaddressing/Router_Scalability.p
df

|All of this means one simple thing: We'll hit the wall on the FIB's
|capability long before we hit the wall on the BGP RIB's capability.
|
|Absent a RIB+FIB solution that the operators are enthusiastic about,
|it's worth the effort to consider approaches that only reduce the size
|of the FIB.

Those matters, since they are implementation details that actually have
private solutions known to some in the industry are really not our
balliwick.  Again, our charter is to address the routing and addressing
architectural issues that cause a lack of aggregation in the first place.

Regards,
Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 22 Jul 2008 11:49:56 +0200

> the entries and churn that we have today.

100 times the entries * 100 times the churn = 10000 times the  
processing. I'm afraid that your DRAM isn't going to keep up with that  
in a traditional design.

However, route processing isn't inherently serial. So it should be  
possible to make a route processor that has 100 systems-on-a-chip that  
all process 1% of the routing table. Of course current BGP isn't  
particularly suitable for that, but I don't see a reason why changes  
that allow parallel BGP processing can't be made.

---

From: Lixia Zhang <[email-masked]>
Date: Tue, 22 Jul 2008 09:32:59 -0700

Hi Bill,

if I got it right, the above description sounds like a special case of  
the more general "virtual aggregation" scheme by Paul Francis.

in terms of drawbacks: in addition to what you mentioned above,  
virtual aggregation in general can lead to longer paths (trading path  
lengths for FIB size reduction; in the above, this can happen at step  
5).

Paul is pushing hard on the virtual aggregation solution on multiple  
venues.  Have you thought about joining force with that effort?

Lixia

---

From: "William Herrin" <[email-masked]>
Date: Tue, 22 Jul 2008 14:32:40 -0400

On Tue, Jul 22, 2008 at 12:32 PM, Lixia Zhang <[email-masked]> wrote:
> if I got it right, the above description sounds like a special case of the
> more general "virtual aggregation" scheme by Paul Francis.

Hi Lixia,

No, Paul is on to a very different idea. His idea is: partition the
BGP FIB among multiple routers and then use a few short routes plus
MPLS to move the packet to the router which has the of the FIB for
that destination. I like Paul's idea but I'm chasing a different
track.

> in terms of drawbacks: in addition to what you mentioned above, virtual
> aggregation in general can lead to longer paths (trading path lengths for
> FIB size reduction; in the above, this can happen at step 5).

No, I'm going a different way. *IF* I'm right, the approach I describe
has the property that for all routes actually in the RIB, a FIB lookup
still chooses exactly the same exit that it would if all the RIB
routes were entered into the FIB individually.

Right now routers have an implied default route to the "host
unreachable" virtual interface.  Routes not otherwise expressed in the
FIB are directed to "host unreachable" which generates an ICMP message
back to the source.

What I'm saying is: ditch the implied default route. Instead, treat
unrouted space as "don't care" destinations which may be sent in any
direction. They'll eventually die from TTL expired, and except for the
wasted resources we mostly don't care where they go.

Then, rebuild the FIB based on the assumption that you're going to
compress the RIB entries with the most common exit plus all of the
"don't cares" into a single default route and enter that into the FIB.
All the rest of the RIB routes that point to some other exit will be
cutout routes in the FIB which poke holes in the default and send
their packets in a different direction.

Finally, do that recursively at the /1, /2, ... /8 levels.

This approach should have the property that for all routes actually in
the RIB, a FIB lookup still chooses exactly the same exit that it
would if all the RIB routes were entered into the FIB individually.

The sacrifice is that all routes NOT in the FIB get sent somewhere
too, instead of generating a host unreachable. In fact, if the router
actually has a default route in the RIB, this compression probably
won't work.

I haven't crunched any numbers but my guesstimate is that towards the
edge you'd get compression down to a few thousand FIB entries while
deep in the core you'd get 25% to 50% compression and in the worst
case you'd get 1/X compression where X is the number of BGP interfaces
on the router.

Regards,
Bill Herrin

---

From: "Tony Li" <[email-masked]>
Date: Tue, 22 Jul 2008 11:37:25 -0700

|However, route processing isn't inherently serial. So it should be  
|possible to make a route processor that has 100 
|systems-on-a-chip that  
|all process 1% of the routing table. Of course current BGP isn't  
|particularly suitable for that, but I don't see a reason why changes  
|that allow parallel BGP processing can't be made.

You can take this approach, but it makes costs go non-linear very rapidly.

Tony

---

From: "K. Sriram" <[email-masked]>
Date: Tue, 22 Jul 2008 17:35:21 -0400

>case you'd get 1/X compression where X is the number of BGP interfaces

Bill:

X can be quite large for core BGP routers -- 100s of peers or BGP interfaces.
In that case, the worst case of 1/X would be negligible compression.
Do you have some data available regarding distribution of prefixes
that exit using the same BGP interface? Just looking for some
empirical support for your guesstimate of 25% to 50% compression
in the core.

The other fundamental question would be: Even if it 25% compression,
given that the total number of FIB entries are projected to increase
four fold over what we have today (from ~250K to ~1 million or so),
we would still be seeing an increase (post 25% compression)
from ~188K to ~750K (assuming that the FIB increases are proportional
for all BGP interfaces or exits).

Sriram

K. Sriram, Ph.D.
National Institute of Standards and Technology
Web:  http://www.antd.nist.gov/~ksriram/

---

From: "William Herrin" <[email-masked]>
Date: Tue, 22 Jul 2008 22:04:08 -0400

> empirical support for your guesstimate of 25% to 50% compression

No data. Like I said: purely a SWAG. This is in the "float the idea
and listen to the response" stage.

> X can be quite large for core BGP routers -- 100s of peers or BGP

What scenario? Peering fabric at Equinix Ashburn kind of thing? What's
the guesstimate on the number of routers in service with >= 100 active
BGP sessions to peers? 20? 200? 2000?

> In that case, the worst case of 1/X would be negligible compression.

The worst case construct comes in to play where you have, let's say
100 BGP sessions and 200,000 routes.  Give each session the best path
for exactly 2000 routes. No more than 10 routes in each session are
from the same /8. In this worst-case scenario, the FIB loses 2000 long
prefixes in exchange for adding about 500 short ones.

Obviously the RIB doesn't look that way. Ever. Instead, you have two
dozen best-path routes from this peer and twenty thousand from that
peer, and subdivisions of the /8's for the various RIRs tend to
cluster with peers who have better connectivity to those regions.

> for all BGP interfaces or exits).

That's a fair criticism. But let's flip it around: If 100k of the 150k
BGP routers get a compression ratio bettern than 10:1, 40k get less
than that and 10k get no better than 1.3:1, have we not at least
reduced the scope of the problem? If FIB compression allows 2/3rds of
the BGP routers to keep using 6500 Sup2's even when the RIB passes 2M
entries, is that not at least as significant a cost impact as the
introduction of MPLS these many years past?

Regards,
Bill

---

From: "William Herrin" <[email-masked]>
Date: Tue, 22 Jul 2008 22:15:58 -0400

On Mon, Jul 21, 2008 at 9:51 PM, Tony Li <[email-masked]> wrote:
> http://www.iab.org/about/workshops/routingandaddressing/Router_Scalability.pdf

Tony,

Let's bound the problem a little better, shall we?

First, we're not worried about routine churn as a result of changes in
traffic engineering and far-away failures. The current rate peaks low.
100 times that rate is readily doable.

Second, we're not worried about large churn due to planned nearby link
changes such as intentionally removing a link from service, restoring
a link to service or adding a new link. While it would be inconvenient
for that to take more than a few minutes, it could be managed in a way
that would not increase outages even if it took hours overall.

That excludes all but two problematic cases:

1. Catastrophic churn due to the failure of an attached link. A node
faced with this situation must quickly rebuild the FIB with new
entries for all routes which used that exit. It must also quickly get
the message out to nearby nodes that it no longer has as high a
priority path to those routes and indeed may have no route at all.

2. Major churn on the few tens of "nearby" nodes whose topology
relative to the failed link requires changing many FIB entries. Note I
said FIB entries, not RIB entries. It doesn't matter how long it takes
to update the RIB with the new priorities except where those
priorities cause a different decision about what's placed in the FIB.

So, how can we address this within engineering and operations?

A. If the failed link is internal, MPLS recovers for us without
disrupting the BGP RIB.

B. If the failed link is external, an intentionally programmed tunnel
designated as a "backup" to the interface could usually let us carry
on routing packets while the RIB recomputes optimal routes, the same
as MPLS allows internally. Recall, the FIB lookup returns an index
into an Exits table. If a tunnel link is designed as a full backup and
the tunnel encoding is implemented in the ASICs (like MPLS is) then
it's a trivial matter to just change the exit in the one table.

C. Even if it isn't practical to build such a tunnel, you can
generally pick an alternate link that offers a high probability of
reachability for for the impacted routes. On link failure, cut over to
the alternate while rebuilding the RIB and then FIB.

D. Building on C, create basic loop detection in the forwarding
engine. If the nearby router sees a packet come to him with a
destination that he thinks should go back to the person who sent it,
this should provide early indication that his route is faulty. He can
(and probably should) reduce the priority of that route to a level
below the next best route immediately rather than waiting for
confirmation in a BGP update.

None of this is perfect, but put together it enables a system that
isn't on the brink of collapse at 100 times the current number of
entries.

Let's talk about hardware next.

> growth rate is at least 1.3X every two years.

That figure sounds fishy. As I recall, we were using a 100mhz memory
bus in 1998 and moving in to 133mhz memory bus. Today we're using a
1300mhz memory bus and moving to a 1600mhz memory bus. Math may not be
my first love, but I'm pretty sure doubling every 3 years (like I
said) would give us 800 mhz in 9 years, 1600 mhz in 12 years and
somewhere between the two in 10 years.

Granted the speed of the individual DRAM cells themselves isn't
increasing quickly, but what matters is the aggregate speed with which
a range of memory becomes accessible to the CPU (a cache fill).

Moving on, for a major recomputation of the RIB (which we decided was
the problem case), the recomputation can be performed in a
cache-efficient manner. When we know there's a big change, we don't
have to use the same algorithm we use for one-off changes with routine
churn. This means that for the most part we'll be handling the problem
case at SRAM speeds rather than DRAM speeds.

The task can also be broken up and performed in parallel. This means
that IF memory access can be done in parallel, the task can be
significantly sped up.

Is there any cheap COTS hardware that implements such parallel memory
access? YES, THERE IS.

AMD Opteron processors embed the memory controller in the CPU. Each
CPU manages its own bank of memory with a dedicated memory bus. They
share with each other via a "hypertransport." If the portion of the
RIB associated with part of the address space is intentionally placed
in memory managed by the CPU which will calculate that portion of the
RIB then the computation can proceed in parallel without contention on
the memory bus.

2-way opteron systems are commonplace while 8-way systems are findable
with a google search. That's an instant 8x boost in the catastrophic
RIB recalculation speed with COTS hardware just by parallelizing the
algorithm and managing memory a little better.

In summary:

* 8x boost to your top capacity estimate is cost effective and
immediately available in existing COTS hardware.
* Only have to solve the nearby link-failure case to sustain BGP beyond that.
* Tunnels let us avoid outages from the nearby link-failure case most
of the time.
* Other algorithmic tweaks that don't change the protocol drastically
reduce the outage associated with the nearby link-failure case.

We'll still eventually hit a wall on the BGP RIB, but the cost won't
reach an untenable level until after we've passed 100x the current
size. We'll hit the wall on the FIB much sooner, perhaps as little as
10x.

> architectural issues that cause a lack of aggregation in the first place.

I'll have to think about that one further but I'm sure it has an
appropriate answer as well.

On Tue, Jul 22, 2008 at 5:49 AM, Iljitsch van Beijnum
<[email-masked]> wrote:
> 100 times the entries * 100 times the churn = 10000 times the processing.
> I'm afraid that your DRAM isn't going to keep up with that in a traditional
> design.

You have the combinatorics wrong. Each entry has some probability of
churning each second. So if you have 100 entries, you're 100 times as
likely to see a single-entry churn event. You are NOT 100 times as
likely to see a 100-entry churn event. In fact, you're no more likely
to see a full-table churn event that you were when there was only 1
entry, and each such full-table churn consumes only 100 times the
processing.

The net result is that 100 times the entries ~= 100 times the churn ~=
100 times the processing. NOT 10,000.

Regards,
Bill Herrin

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 23 Jul 2008 11:20:56 +0800

> 4. Mark the rest of the routes for import into the FIB.

Let me take an example, route 1.1.1.0/24 is pointed to interface A, while
route 1.1.0.0/16 is pointed to interface B. if most routes are pointed to
interface A, in your theory, those routes with interface A as exit
interface, including route 1.1.1.0/24, will be replaced by 0.0.0.0/0 in the
FIB. This will cause a wrong route for packets to 1.1.1.0/24. Is my
understanding correct?

Xiaohu XU

---

From: "William Herrin" <[email-masked]>
Date: Tue, 22 Jul 2008 23:53:57 -0400

Nice try, but no. As I alluded to in an earlier message:

>> In fact, if the router actually has a default route in the RIB,
>> this compression probably won't work.

It won't work because as you rightly point out, this approach only
allows you to compress prefixes that don't overlap. If the router has
a real default route, prefixes that take some other exit can't be
compressed. This holds true at every level, not just /0.

So, in your example 1.1.1.0/24 can't be removed because it overlaps
1.1.0.0/16 and takes a different exit (A instead of B). On the other
hand, if you have 1.1.2.0/24 which takes exit B, that -can- be removed
without changing the results of a lookup. Unless you also have
1.1.0.0/20 pointing to exit A. Then you can remove 1.1.1.0/24 but not
1.1.2.0/24.

Detecting covering routes does add complexity to the algorithm, though
not a whole lot: one radix tree lookup for each entry examined. And no
I haven't attempted to work out the big-oh. I'm just floating an idea
here, looking for fatal flaws.

Regards,
Bill Herrin

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 23 Jul 2008 10:23:30 +0200

> the alternate while rebuilding the RIB and then FIB.

Hm, if you know your outage (= detection + convergence times) is short  
enough, say, less than 30 seconds, and certainly if less than 10  
seconds, it doesn't really matter where the packets go, you could even  
drop them and _most_ applications will continue without too much  
trouble.

If it's going to take a minute or more to restore reachability, you  
can't play fast and loose and risk loops, because applications will  
fail.

> isn't on the brink of collapse at 100 times the current number of

This is all highly optimistic. Let's assume you can get your 8 times  
parallelization, so try the current 250k table on a system that's 12 x  
slower than what's on the market now. Let's say a 133 MHz Pentium.

> 1300mhz memory bus and moving to a 1600mhz memory bus.

These busses are optimized for serial reading/writing of large cache  
lines. If you need a single byte, it's still slow.

> RIB then the computation can proceed in parallel without contention on

The problem is that all your BGP updates come in over a single TCP  
session so they must be fanned out to the right CPU. It would be  
better if we could make it such that you'd have 8 sessions that each  
carry the right updates to the right CPU.

> entry, and each such full-table churn consumes only 100 times the

The problem is that the single "100 times" figure is rather  
meaningless as it can both mean what I said and what you said. We know  
that both the number of entries is growing and the number of updates  
per entry, so although it's not going to be as bad as I said, it's  
also not going to be as good as you said.

Obviously the best way to get rid of volatility in the updating is to  
not carry the prefixes in the first place, but we did flap dampening  
10 years ago, I see no reason why we can't do something similar that  
works a bit better.

Of course all of this assumes that we keep the basic BGP paradigms  
intact...

---

From: [email-masked]
Date: Wed, 23 Jul 2008 07:46:32 -0400

> BGP sessions to peers? 20? 200? 2000?

Thanks for your response to my questions.
Please see slides 33-36 from this presentation:

http://www.antd.nist.gov/~ksriram/BGP_Security_Analysis_NIST_Study.pdf

We derived these statistics and plots using AS-level peering topology 
measurement data from Lixia's team at UCLA (December 2005).
This is a good starting point, but in order to fully quantify 
your proposal, a distribution of ratio of prefixes (RIB entries) 
that point to the same peer (per BGP router) is needed.

Sriram
K. Sriram, Ph.D.

---

From: Peter Sherbin <[email-masked]>
Date: Wed, 23 Jul 2008 06:39:19 -0700 (PDT)

RFC 4271: "BGP Identifier A 4-octet unsigned integer that indicates the BGP Identifier of the sender... A given BGP speaker sets the value of its BGP Identifier to an IP address assigned to that BGP speaker..."

Is the above going to change in IPv6?

Thanks,

Peter

--- On Wed, 7/23/08, Iljitsch van Beijnum <[email-masked]> wrote:

> From: Iljitsch van Beijnum <[email-masked]>
> Subject: Re: [RRG] Opportunistic Topological Aggregation in the RIB->FIB Calculation?
> To: "William Herrin" <[email-masked]>
> Cc: [email-masked], "Routing Research Group" <[email-masked]>
> Date: Wednesday, July 23, 2008, 4:23 AM
> >> In fact, the PC hardware doesn't actually do
> that.  What we really  
> >> see is
> >> that DRAM memory speed grows at about 1.2X every
> two years and that  
> >> our
> >> I'm afraid that your DRAM isn't going to
> keep up with that in a  
> >> traditional
> >> design.
>

---

From: Jari Arkko <[email-masked]>
Date: Wed, 23 Jul 2008 17:00:29 +0300

I second what Lixia said.

In general, there are plenty of ways to optimize and compress FIB 
tables, some without changing the end result and some that do change the 
routing (Paul Francis' scheme, for instance). I have not reviewed your 
scheme in detail, but if you search you will find others. Some earlier 
discussion here: 
http://www.ietf.org/mail-archive/web/ram/current/msg00567.html

I view the former class (schemes that do not change forwarding 
decisions) as implementation techniques. On a given platform,  you may 
decide that its reasonable to spend some central CPU time to reduce the 
amount of memory needed on the line cards. Of course, there are 
trade-offs, you cannot determine with certainty that compression will be 
effective on today's RIB even if it was very useful on yesterday's, etc. 
My personal opinion is that these techniques should belong to the 
toolkit for people building routers, perhaps more so than they are 
today. Of course there are many other things in the toolkit as well.

I view the latter (Francis-type) schemes as mostly operational 
techniques that can be useful if and when existing equipment on a given 
operator is otherwise unable to deal with the situation. Note that there 
is a trade-off between buying newer equipment vs. operational effort. I 
would like to see Paul's scheme or something else documented at least.

However, our task in the RRG is not really about these types of 
approaches. We should assume they are being applied (I certainly hope 
so) where needed, and it may be useful for the group to understand that 
such techniques exist. But our task should really be about architectural 
change, something that could yield 10x to 1000x difference in table sizes.

Jari

---

From: "William Herrin" <[email-masked]>
Date: Wed, 23 Jul 2008 13:54:46 -0400

> http://www.antd.nist.gov/~ksriram/BGP_Security_Analysis_NIST_Study.pdf

Very interesting. To summarize: about 10% of the ASes have at least 10
neighbors and a little over 1% have more than 100. One AS appears to
have had 3,622 neighbors!

Can we extrapolate from this to guess at the configuration of
individual routers? I would expect that even with MPLS in play, a
particular router would have a handful of external exits plus a bunch
of MPLS labels functioning as virtual exits, each leading to a router
that then has another handful of external exits.

I would imagine, for example, that the gentleman with 3,622 neighbors
doesn't have 3,622 unique best-next-hops in any one of his routers'
FIBs. So what -does- he have? And how many routers does he have that
on?

Regards,
Bill

---

From: Brian Dickson <[email-masked]>
Date: Wed, 23 Jul 2008 13:21:23 -0400

Jari Arkko wrote:
> tables, some without changing the end result and some that do change 
> the routing (Paul Francis' scheme, for instance). I have not reviewed 
> your scheme in detail, but if you search you will find others. Some 
> earlier discussion here: 
> decide that its reasonable to spend some central CPU time to reduce 
> the amount of memory needed on the line cards. Of course, there are 
> trade-offs, you cannot determine with certainty that compression will 
> be effective on today's RIB even if it was very useful on yesterday's, 
> etc. My personal opinion is that these techniques should belong to the 
> techniques that can be useful if and when existing equipment on a 
> given operator is otherwise unable to deal with the situation. Note 
> that there is a trade-off between buying newer equipment vs. 
> operational effort. I would like to see Paul's scheme or something 
> else documented at least.
>
> so) where needed, and it may be useful for the group to understand 
> that such techniques exist. But our task should really be about 
> architectural change, something that could yield 10x to 1000x 
> difference in table sizes.

This is a cart-before-the-horse issue.

While the tools are potentially capable of significant degrees (or even 
orders-of-magnitude) reduction in FIB (and in many cases RIB) size, they 
are dependent on the data on which they operate.

Garbage (un-aggregateable prefix) in, garbage (bloated RIB and FIB) out.

So, even though the specific implementations *may* be out of scope, the 
notion that the prefix sets being suitable for such processing are 
needed, is definitely *in* scope.

The addressing (and address *allocation*) schemes are absolutely 
architectural in nature.

So, while the specific techniques may be very helpful in informing 
architectural models, even if the techniques themselves get removed at 
the end of the RRG process.

They are, in effect, like the pencil-lines used by artists doing 
realistic perspective work. The lines-to-infinity are needed to shape 
and size objects, but are not part of the finished artwork.

BTW - I'll be contributing more ideas on such aggregation techniques and 
ways to view "sets of things to aggregate" and such, over the next 
several weeks.

Brian Dickson

---

From: Robin Whittle <[email-masked]>
Date: Fri, 25 Jul 2008 13:11:39 +1000

Hi Iljitsch,

> that allow parallel BGP processing can't be made.

Still, those CPUs need to communicate with each other and maintain a
common RIB, as well as information about each conversation with each
BGP neighbour, via DRAM.

So I am not sure that adding CPUs would be any better than the Linux
server situation of 2 or so fast CPUs with caches with a common
DRAM.  I am not sure how suitable the BGP implementation would be to
100 CPUs each with their own DRAM and some kind of communications
link between them.  That sounds even messier.

  - Robin

---

From: "Tony Li" <[email-masked]>
Date: Thu, 24 Jul 2008 21:54:19 -0700

|So I am not sure that adding CPUs would be any better than the Linux
|server situation of 2 or so fast CPUs with caches with a common
|DRAM.  I am not sure how suitable the BGP implementation would be to
|100 CPUs each with their own DRAM and some kind of communications
|link between them.  That sounds even messier.

Several BGP implementors have discussed it.  It's decidedly not pretty.
While it's not impossible, it's again a step up in costs and complexity.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 30 Jul 2008 13:37:07 +0100

> link between them.  That sounds even messier.

If each CPU gets only its own part of the table, it doesn't have to  
talk to the other CPUs that handle other parts of the table at all;  
the only thing it needs is a way to update the FIB for that part of  
the table.

Of course this is much harder to do that a single CPU implementation,  
but once again: you don't want to optimize for stuff that happens on  
human timescales (programming) at the expense of what happens at FIB  
or even RIB processing timescales.