Subject: Re: [rrg] BGP scaling limit?

From: [email-masked]
Date: Fri, 2 Jan 2009 07:08:01 EST

In einer eMail vom 02.01.2009 01:34:12 Westeuropäische Normalzeit schreibt  
[email-masked]:

ICBW,  but I think you're describing what's been called the "Memory 
|wall" by  Wulf & McKee:
|
|   http://www.cs.virginia.edu/papers/Hitting_Memory_Wall-wulf94.pdf
|
|and  see also:
|
|   http://www.csl.cornell.edu/~sam/papers/cf04.pdf

Thank you for the  excellent references, I think they're exactly on point.
Routing is simply  one of the applications that is going to hit the  memory
wall.

Thanks for these very interesting documents.It tells me: after the ignoring  
phase and now the rejection phase TARA will still get -within a decade- its  
chance. Not because of eliminating the update churn or the table size problem  
but for eliminating the need to cache at any  transit-router.
 
Ignoring phase:
I am still waiting for the promised detailed response by Lixia, or for  
Bill's explanation why a link-state protocol cannot express the same policy as a  
DV protocol, and -wrt to the above - I only got collective silence when I said  
in spite of 300 000 stored routes DV does only enable one third of them, ie 
that  twice the number cannot be provided.Very very rougly. Let me eloborate 
more  on this factor by the following example:
 
Imagine destination node d surrounded by a tightly meshed network such that  
each node has 6 neighbor nodes whereby 2 are closer, 2 are equidistant and 2 
are  more remote wrt to d. Now assume a source node s being 10 hops away from d 
and  let us consider the number of different paths (differing at least by one 
 hop):
Dijkstra provides 1 path. ECMP provides 2^10 paths (at least this is what I  
accredit to/expect from ECMP). My own algorithm provides 6^10 paths. This is 
not  just twice but 3^10 times  what can ECMP (and DV ?)provide. These are such 
 extremely big numbers that you don't want to store a single route of them,  
instead look for a more intelligent mechanism.Keep in mind the average path  
length is said to be 20, not 10.
 
Heiner
_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: [email-masked]
Date: Tue, 6 Jan 2009 15:11:49 EST

In einer eMail vom 06.01.2009 20:37:35 Westeuropäische Normalzeit schreibt  
[email-masked]:

True,  but deploying a new architecture will have a one-time cost impact.
Paid  for, over and done.  It will be spread out over each system that  needs
to be upgraded, but it is a fixed and finite cost.   

Paying for a more expensive control plane is likely to be an ongoing,  ever
increasing cost.

|   Would the industry be  willing to buy into the *promise* of
|   "a paradise" in the  *long* term at the price of fairly certain
|   cost increases in  the *short/medium* term ? 
|
|   All of the above means that a  "promise" of cost reduction in the
|   *long* term may not be  sufficient - the new routing architecture
|   needs to deliver in  the *short/medium* term sufficient *tangible*
|   benefits to  justify its *short/medium* term cost.

One might look it at it  instead as avoiding the guarantee of long term
higher costs.

In any  case, there are numerous problems that we do feel we need to overcome
with  the new architecture.  Whether the deployment costs are  sufficiently
justified will in part depend on what we produce, and we will  not know that
until we have consensus on a workable  architecture.

| - One may argue that the real problem is not in the  cost increases,
|   but in the way how these increases are  absorbed by the system.
|   Namely, the real problem is that  those who do not benefit
|   are still required to pay for  covering the cost imposed by those
|   who do benefit. That  applies both to the current system, as well 
|   as to any  proposal for a new routing architecture.

Changing the topology agnostic BGP to a well-reduced topology aware BGP,  
where there is no update churn anymore, where a router  may have to deal  with a 
small number of nodes and strict/loose links only, where the next hop is  
determined by either one or three lookups so that it doesn't need caching  
capability either, 
         
                          will reduce the monetary costs immensely.
 
Yakov also mentioned the huge number of mobile IP users to be expected  in 
the future. 
Wrt to mobility it would be crazy to continue with LISP 's LOC  -routing, i.e 
to NOT switch over to location routing. We may aso be  going to see 
applications where users are only mobile, i.e. have no home place  at any time.
 
Heiner

---

From: [email-masked]
Date: Mon, 12 Jan 2009 18:29:01 EST

Danny,
I agree with you. It is not ok to say "we have to solve this inter-domain  
scalability problem and don't care/ don't want to mingle it with any  
intra-domain scalability problem".
 
You hilight another big point of TARA being an architecture which doesn't  
depend on/doesn't need user reachability information dissemination at all -  
neither of inter-domain prefixes nor of intra-domain prefixes. 
Its advantages of a much faster next-hop look-up will result in a much  
faster forwarding for the entire path, if the same mechanism is applied from the  
ingress intra-domain router to the egress-intra-domain router.
 
Heiner

 
In einer eMail vom 12.01.2009 16:08:08 Westeuropäische Normalzeit schreibt  
[email-masked]:

On Jan  6, 2009, at 4:23 PM, Tony Li wrote:
>
>
> I know that the  internal tables are always a pain, but since we have  
> to  deal
> with the global issues, the internal, private growth (self-  
> inflicted ;-) has
> to necessarily be out of scope for  RRG.

That's quite odd to me, considering by today's  definitions
"internal [BGP] tables" are where the routing scalability  and
stability are it's worst - today, and unquestionably, the  first
place things will break IF/WHEN they do, as a result of  an
inter-domain routing protocol architecture that forces  either
full-mesh or hierarchies such as route reflection that  themselves
introduce additional paths and state in the network (even  with
implicit aggregation effects).

And they're not going to break  because of a 100k unique
internal-only routes, they're going to break  because of
an order or magnitude or more paths (and all of their  overhead)
- paths introduced as a result of "global issues" and  solutions
that focus on solely minimizing DFZ size, rather than  looking
at where the problem is actually worst -  today.

-danny
_______________________________________________
rrg  mailing  list
[email-masked]
http://www.irtf.org/mailman/listinfo/rrg

_______________________________________________
rrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/rrg