Subject: Re: [Idr] BGP Optimal Route Reflection (BGP-ORR)

From: <[email-masked]>
Date: Tue, 5 Apr 2011 10:31:57 +0200

I support adoption of this draft as a working group work item.

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Robert Raszuk
Envoyé : jeudi 31 mars 2011 15:35
À : [email-masked] List
Objet : [Idr] BGP Optimal Route Reflection (BGP-ORR)

Authors of "BGP Optimal Route Reflection (BGP-ORR)" draft document would like to propose the adoption of this work as the IDR WG item.

Ref:
http://tools.ietf.org/html/draft-raszuk-bgp-optimal-route-reflection-01

Rgs,
R. Raszuk
C. Cassar
E. Aman
B. Decraene
_______________________________________________
Idr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/idr

********************************************************************************
IMPORTANT.Les informations contenues dans ce message electronique y compris les fichiers attaches sont strictement confidentielles
et peuvent etre protegees par la loi.
Ce message electronique est destine exclusivement au(x) destinataire(s) mentionne(s) ci-dessus.
Si vous avez recu ce message par erreur ou s il ne vous est pas destine, veuillez immediatement le signaler  a l expediteur et effacer ce message 
et tous les fichiers eventuellement attaches.
Toute lecture, exploitation ou transmission des informations contenues dans ce message est interdite.
Tout message electronique est susceptible d alteration.
A ce titre, le Groupe France Telecom decline toute responsabilite notamment s il a ete altere, deforme ou falsifie.
De meme, il appartient au destinataire de s assurer de l absence de tout virus.

IMPORTANT.This e-mail message and any attachments are strictly confidential and may be protected by law. This message is
intended only for the named recipient(s) above.
If you have received this message in error, or are not the named recipient(s), please immediately notify the sender and delete this e-mail message.
Any unauthorized view, usage or disclosure ofthis message is prohibited.
Since e-mail messages may not be reliable, France Telecom Group shall not be liable for any message if modified, changed or falsified.
Additionally the recipient should ensure they are actually virus free.
********************************************************************************

---

From: Danny McPherson <[email-masked]>
Date: Tue, 5 Apr 2011 23:29:30 -0400

I support WG adoption as well..

-danny

---

From: Rob Shakir <[email-masked]>
Date: Wed, 6 Apr 2011 18:01:57 +0100

> http://tools.ietf.org/html/draft-raszuk-bgp-optimal-route-reflection-01

Hi,

I have read/reviewed this draft and support it's adoption as a working group item.

Kind regards,
r.

---

From: Uli Bornhauser <[email-masked]>
Date: Wed, 6 Apr 2011 20:18:43 +0200

Hi Robert, all

I carefully read the new version today. In principle, I fully support WG adoption.

However, I have two minor notes concerning the draft:

In the abstract, you mention that RFC4456 specifies a deployment approach that yields the same result as a full-mesh will do. Reading this paragraph, I implicitly assumed that ORR realizes the same, which is not the case. Of course, this was my fault, but it could be helpful to state this in the abstract.

In section 2, you state that "the route reflector selects and distributes a route to each client based on what would be optimal from the client's perspective". After that, you state that clients do not need new software. I had two aspects in mind, which should IMHO be explicitly mentioned here:
First, if clients do not have a modified software (Add-path and adequate implementation guidelines), Route Reflectors select the same path for a client as if the client would do in a full-mesh BGP environment. However, this path may not be optimal from the client's perspective.
Second, even if the optimal path is distributed by the server, it may be that the client chooses another (local) path which is sub-optimal from a global perspective.

That's all. Again, all in all, I fully support WG adoption.

Regards

Uli

-- 
_______________________________________________________
ULI BORNHAUSER
University of Bonn - Institute of Computer Science 4
Friedrich-Ebert-Allee 144 - D 53113 Bonn - Germany

Web: www.cs.bonn.edu/IV/ub
Email: [email-masked]			
Phone: +49 (228) 73 - 54219
Fax: +49 (228) 73 - 4571

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 06 Apr 2011 20:25:07 +0200

Hello Uli,

Many thx for your valuable comments as well as for your support to adopt 
this work as IDR WG work item.

I will incorporate your points into the next revision of the draft.

Best regards,
R.

> In the abstract, you mention that RFC4456 specifies a deployment
> approach that yields the same result as a full-mesh will do. Reading
> this paragraph, I implicitly assumed that ORR realizes the same,
> which is not the case. Of course, this was my fault, but it could be
> helpful to state this in the abstract.
>
> In section 2, you state that "the route reflector selects and
> distributes a route to each client based on what would be optimal
> from the client's perspective". After that, you state that clients do
> not need new software. I had two aspects in mind, which should IMHO
> be explicitly mentioned here: First, if clients do not have a
> modified software (Add-path and adequate implementation guidelines),
> Route Reflectors select the same path for a client as if the client
> would do in a full-mesh BGP environment. However, this path may not
> be optimal from the client's perspective. Second, even if the optimal
> path is distributed by the server, it may be that the client chooses
> another (local) path which is sub-optimal from a global perspective.
>
>> Authors of "BGP Optimal Route Reflection (BGP-ORR)" draft document
>> would like to propose the adoption of this work as the IDR WG
>> item.
>>
>> Ref:
Rgs,
>> R. Raszuk C. Cassar E. Aman B. Decraene
>> _______________________________________________ Idr mailing list
>> [email-masked] https://www.ietf.org/mailman/listinfo/idr
>

---

From: Ronald Bonica <[email-masked]>
Date: Wed, 6 Apr 2011 17:43:38 -0400

Folks,

I would like to discourage adoption of this draft for the following reasons:

1) A relatively inexpensive solution to this problem is already available. That is, to deploy slightly larger number of route reflectors and to assign clients to reflectors based upon IGP distance.

2) The solutions described in this draft do not scale well. In particular, it is not clear how the solution described in Section 3 works when the BGP domain is so large that it does not fit in a single IGP area. Even if the BGP domain were to fit in a single IGP area, the solution described in Section 3 becomes computationally expensive if the domain contains many POPs.

3) The solution described in Section 4 is operationally complex. While it is theoretically possible to assign an angular position to each rr client, in some network topologies, this is easier said than done. AFAICS, calculation and configuration of the angular position is always a manual operation. Angular positions must be re-evaluated periodically, to account for the addition of network links.

                                                   Ron

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Robert Raszuk
> Sent: Thursday, March 31, 2011 9:35 AM
> To: [email-masked] List
> Subject: [Idr] BGP Optimal Route Reflection (BGP-ORR)
> 
> 
> would
> like to propose the adoption of this work as the IDR WG item.
> 
> Ref:

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 07 Apr 2011 00:10:27 +0200

Thank you for your opinion. Let me explain what the draft proposes in 
the light of your comments ...

> 1) A relatively inexpensive solution to this problem is already
> available. That is, to deploy slightly larger number of route
> reflectors and to assign clients to reflectors based upon IGP
> distance.

Both route reflectors as well as their network operation carry a non 
negligible opex and capex values. It should be the network operator to 
decide if given solution vs available alternative is attractive to him 
or not. Clearly such decision should not be made by a vendor. The goal 
of the draft is to provide such choice to the network operator.

> 2) The solutions described in this draft do not scale well. In
> particular, it is not clear how the solution described in Section 3
> works when the BGP domain is so large that it does not fit in a
> single IGP area.

The draft already contains the detailed explanation on this point:

    In the case of a hierarchical IGP deployment where the client is in a
    different level in the hierarchy to the route reflector, the route
    reflector will compute IGP distance to the BGP nexthop from the Area
    Border Routers (ABR) leading to the client in lieu of the route
    reflector client itself, and use the shortest distance from these
    ABRs to the nexthop. This provides an approximation to the desired
    functionality.

This scales just fine. Moreover there is another method to provide 
precise and not approximated distance of the client to the next hop metric.

The details are described in document titled: "Carrying next-hop cost 
information in BGP" available at 
http://tools.ietf.org/html/draft-varlashkin-bgp-nh-cost-01

 > Even if the BGP domain were to fit in a single IGP
 > area, the solution described in Section 3 becomes computationally
 > expensive if the domain contains many POPs.

Let me point out that what may be computationally expensive for one RR 
platform may not provide a significant load for some other RR 
implementation on other choice of computational platform. Therefor your 
above stated comment seems to be very subjective and quite narrowly 
focused.

> 3) The solution described in Section 4 is operationally complex.
> While it is theoretically possible to assign an angular position to
> each rr client, in some network topologies, this is easier said than
> done. AFAICS, calculation and configuration of the angular position
> is always a manual operation. Angular positions must be re-evaluated
> periodically, to account for the addition of network links.

While the draft does describe angular approximation as manual 
configuration today the aim is for small or middle size networks. For 
much larger networks angular approximation does not need to be a manual 
operation or other ways of deriving client to next hop metric can be 
used. One size does not fit all.

With this in mind let me point out that there are number of automated 
methods to be used for angular metric calculation and assignment which 
if there is further interest in the IDR WG could be documented in a 
separate proposals.

Best regards,
Robert Raszuk.

>> -----Original Message----- From: [email-masked]
>> [mailto:[email-masked]] On Behalf Of Robert Raszuk Sent:
>> Thursday, March 31, 2011 9:35 AM To: [email-masked] List Subject:
>> [Idr] BGP Optimal Route Reflection (BGP-ORR)
>>
>>
Rgs,

---

From: Randy Bush <[email-masked]>
Date: Wed, 06 Apr 2011 16:04:42 -0700

> of the draft is to provide such choice to the network operator.

oh come on.  that logic covers making totally broken routers available
to operators' choice.

ron's point was that this is a bad choice and the ietf should not be
standardizing or blessing bad choices.

randy

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 07 Apr 2011 01:09:25 +0200

> the ietf should not be standardizing or blessing bad choices.

Truly golden statement !

And I wish it would apply to all choices IETF makes what should be 
standardized and what not .....

R.

---

From: Ilya Varlashkin <[email-masked]>
Date: Thu, 7 Apr 2011 01:49:18 +0200

Ron,

let me add few words to what Robert has already said in his response.

> 1) A relatively inexpensive solution to this problem is already available. That is, to deploy slightly larger number of route reflectors and to assign clients to reflectors based upon IGP distance.
(speaking as operator) consider a ring of several dozens of PoP's, two edge routers in each, and extensive set of external peers per router. Distance between PoP's is noticeable, and calls for careful selection of the exit. If we don't deploy route reflector at each PoP we will have to send way too many alternative path's. On the other hand deploying route reflector at each PoP only halves number of participants in the full mesh, while increasing cost significantly because route reflectors need to support very large number of prefixes (both Internet and VPN) so they would need to be high-end devices. From operator perspective BGP-ORR solution looks more appealing.

> 2) The solutions described in this draft do not scale well. In particular, it is not clear how the solution described in Section 3 works when the BGP domain is so large that it does not fit in a si…

(as author of complementary draft) Originally presented at IETF79 solution with exchanging next-hop cost within BGP itself was meant to be part of BGP-ORR draft. But since BGP-ORR does not change neither BGP messages nor algorithm (only source of some info changes) whereas carrying next-hop cost in BGP naturally calls for extension to the protocol, this solution has been published as separate draft (NH SAFI).

Kind regards,
iLya

---

From: Paul Jakma <[email-masked]>
Date: Thu, 7 Apr 2011 11:16:40 +0100 (BST)

> reflectors and to assign clients to reflectors based upon IGP 

And in that vein:

http://tools.ietf.org/html/draft-jakma-idr-stable-bgp-rr-00

As has been pointed out to me by Robert though, this can not address 
cases where BGP and forwarding topology are quite divorced (the 
various overlay / tunneling things that exist to hack around 
various shortcomings of IP), particularly when RR clients sessions 
are deliberately distributed to RRs far and wide in order to 
load-share the BGP/control-plane overhead.

But for the forwarding / aligned-topology case it seems a simple and 
neat solution.

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
"Protozoa are small, and bacteria are small, but viruses are smaller
than the both put together."

---

From: <[email-masked]>
Date: Thu, 7 Apr 2011 12:26:05 +0200

Ron,

I understand your view and can certainly agree on some points.
Let me present a different perspective.

> 1) A relatively inexpensive solution to this problem is already available. That is, to deploy slightly
> larger number of route reflectors and to assign clients to reflectors based upon IGP distance.

Agreed.
Now, where should we place those RR functions?
I see a few options:
- on existing core routers used for packet forwarding. Chosen closed to its clients.
	Pro: That definitely works on some ASes.
	Con: Others ASes (e.g. BGP free core) may have a policy to not run BGP on P routers.

- on a dedicated router collocated with the above "core" router.
	Pro: good topological/IGP location (near its sets of clients).
	Con: There is typically a mismatch between the low speed interface needed/available on the RR and the high speed interfaces available on the core router.

- on a edge router connected to the above core router
	Pro: good match of interface speed. RR box chosen for its control plane performance (hard & soft), independently of the forwarding box. Control & forwarding plane hardware/software/configuration can be upgraded independently.
	Con: Not so good IGP location (biased point of view)

- in a centralized location, in a "service" POP
	Pro: idem above.
	Con: Bad IGP location.

IMO, to allow for flexibility, it would be useful to be able to physically place a RR in a location, and to logically place it in a different location (RR computes IGP costs as if it were somewhere else in the network. Cf §3.2).

> 2) The solutions described in this draft do not scale well. 

Now indeed, there is a whole range of options, from a single IGP/BGP computation per RR, to one IGP/BGP computation per group of clients, up to one IGP/BGP computation per client. With different tradeoffs.

Taking your above use case (a "slightly larger number of RR"), having the ability to place the RR functions anywhere does not change the scaling. On the contrary, you now have the ability to run the RR functions on a reduce number of boxes and simplify the iBGP topology (smaller iBGP full mesh between RR or avoiding an addition level of RR hierarchy).

> In particular, it is not clear how the
> solution described in Section 3 works when the BGP domain is so large that it does not fit in a single
> IGP area. Even if the BGP domain were to fit in a single IGP area, the solution described in Section 3
> becomes computationally expensive if the domain contains many POPs.
> 
> 3) The solution described in Section 4 is operationally complex. While it is theoretically possible to
> assign an angular position to each rr client, in some network topologies, this is easier said than
> done. AFAICS, calculation and configuration of the angular position is always a manual operation.
> Angular positions must be re-evaluated periodically, to account for the addition of network links.

Draft discusses different options with different tradeoff. Personally, I would tend to agree with you and would probably not use the option proposed in section 4. But discussions on "complexity" are usually about a tradeoff between perceived benefits and perceived costs...

Regards,
Bruno

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 07 Apr 2011 12:33:40 +0200

Hi Paul,

Very good comment indeed.

On that very point just to explain more I have spent significant amount 
of time traveling between NANOG, RIPE and other smaller NOGs last year 
to talk about good, old fashioned RR design where RRs are in the data 
plane or at least where clients are "behind" RRs.

Nothing beats this both from optimal path selection as well as from fast 
connectivity restoration for almost no additional burden and cost (case 
where RRs are in data plane on POP to core boundary).

Some references ...

http://www.nanog.org/meetings/nanog48/presentations/Tuesday/Raszuk_To_AddPaths_N48.pdf

http://ripe60.ripe.net/presentations/Raszuk-To_add-paths_or_not_to_add-paths.pdf

Then I got number of comments from real world operators that even though 
they do agree in principle with my slides the suggestions will no longer 
apply to their architectures as their networks are infected by 4 letter 
forwarding encapsulation paradigm.

That was the trigger to start work on Optimal Route Reflection document 
where control plane RRs can be placed in arbitrary network location 
without compromising hot potato routing principle.

Many thx,
R.

>> reflectors and to assign clients to reflectors based upon IGP distance.
>
> And in that vein:
>
> cases where BGP and forwarding topology are quite divorced (the various
> overlay / tunneling things that exist to hack around various
> shortcomings of IP), particularly when RR clients sessions are
> deliberately distributed to RRs far and wide in order to load-share the
> BGP/control-plane overhead.
>

---

From: Paul Jakma <[email-masked]>
Date: Thu, 7 Apr 2011 12:10:27 +0100 (BST)

On Thu, 7 Apr 2011, Robert Raszuk wrote:

> On that very point just to explain more I have spent significant 
> amount of time traveling between NANOG, RIPE and other smaller NOGs 
> last year to talk about good, old fashioned RR design where RRs are 
> in the data plane or at least where clients are "behind" RRs.

> Nothing beats this both from optimal path selection as well as from 
> fast connectivity restoration for almost no additional burden and 
> cost (case where RRs are in data plane on POP to core boundary).

AFAIK, you still need to tweak BGP though in this case to be sure to 
avoid oscillations, IMU. E.g. some thing like using CLUSTER_LIST to 
apply a consistent ordering to decisions, as per Flavel and Roughan's 
work.

Thanks for the links - very interesting!

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
Save energy: be apathetic.

---

From: Jeff Wheeler <[email-masked]>
Date: Thu, 7 Apr 2011 09:28:05 -0400

I had emailed Robert about this off-list, as I have not followed this
discussion closely (limited time in the day), but he suggested I post
it to the list for consideration.

---------- Forwarded message ----------
From: Jeff Wheeler <[email-masked]>
Date: Thu, Apr 7, 2011 at 9:13 AM
Subject: Re: [Idr] BGP Optimal Route Reflection (BGP-ORR)
To: [email-masked]

> forwarding encapsulation paradigm.

I have not posted on these topics because I don't have enough time to
follow more than a few issues, but when I read your post this morning
I wanted to give you an additional point in support of your idea.
Having route-reflectors in the "data plane" can add to cost, plain and
simple.

I have more CPU/RAM for BGP available on few-thousand-dollars branch
office type routers and other current-model < $5k devices than I have
on my older, yet still useful and in production, DFZ routers.  BGP /
control plane limits have forced me to upgrade numerous routers over
the years because they simply do not have enough RAM or fast enough
CPU for being DFZ routers anymore.  If I was doing much R-R on these
boxes I would have had to upgrade them many years ago.

I don't want to replace a 6500/SUP720-3BXL or a M160 that is still
working fine, for the purpose of packets in -> packets out, just
because my iBGP mesh has grown too large and the box no longer has
enough control plane resources to converge quickly.  That upgrade
costs a lot more than a few thousand dollars.

The network need not make use of MPLS to see a cost advantage from
moving R-R duties out of the data plane.

--
Jeff S Wheeler <[email-masked]>
Sr Network Operator  /  Innovative Network Concepts

---

From: Randy Bush <[email-masked]>
Date: Thu, 07 Apr 2011 07:59:30 -0700

> moving R-R duties out of the data plane.

history has repeatedly shown that, when the control plane and the data
plane, in fact any two layers, are not congruent, debugging and other
opex costs go quite badly.

randy

---

From: Jeff Wheeler <[email-masked]>
Date: Thu, 7 Apr 2011 11:42:42 -0400

> opex costs go quite badly.

If you want the BGP control plane and data plane to have identical
topologies, then you had better do one of these things:
* confederate and make every router its own sub-AS
* make every router an R-R client of every other router
* install links between every router and every other router (full mesh)

If you have not done this, your iBGP mesh is already a control plane
with a different topology for signalling than your data plane for
bearing traffic.  It's designed to work that way.

Since you enjoy arguing in useless generalities, rather than the
practical world, I suggest you stay away from telephony.  The PSTN has
relied on SS7 for inter-office signalling for quite some time.

Perhaps you would care to share some specific accounts of incidents
where dedicated route-reflectors have caused you debugging difficulty
or increased operational expense which offset the cost advantage of
deferring upgrades to backbone routers.

---

From: Hannes Gredler <[email-masked]>
Date: Thu, 7 Apr 2011 18:50:35 +0200

hi robert,

i have mixed feelings about this draft:

1. downside:
   there is no real advantage in terms of
   computational load. i.e. it is a zero-sum game -
   you are proposing to _centralize_ a _distributed_ computation
   by moving (BGP per-POP best-path selection, non-self-rooted IGP
   calculation) from the clients to the RR. i am bit worried if RRs can be
   scaled up enough to support "enough" distinct POPs.

   note: ilya's next-hop AF cost NLRI solves the IGP calculation
   nicely, but has the usual deployment-tax of new protocols
   (especially since we need to consider that new software
   needs to get deployed on older control-plane CPUs).

2. upside: 
   section - 3.2. Configuration-based flexible route reflector
   placement. this is a neat idea, as one can deploy central
   RRs in the data-center and still get decent path-diversity.

suggestion:
  any hard feelings about spinning out section 3.2 into
  a "Virtualized Route Reflection" draft, where all the implications
  wrt to IGP changes, BGP route resolver changes etc. are described
  in more detail ? - i can contribute some text if you want;

/hannes

On Thu, Mar 31, 2011 at 03:34:31PM +0200, Robert Raszuk wrote:
| 
| Authors of "BGP Optimal Route Reflection (BGP-ORR)" draft document
| would like to propose the adoption of this work as the IDR WG item.
| 
| Ref:
| http://tools.ietf.org/html/draft-raszuk-bgp-optimal-route-reflection-01

---

From: Shane Amante <[email-masked]>
Date: Thu, 7 Apr 2011 11:00:00 -0600

> opex costs go quite badly.

To be clear, "not congruent" should not be taken to mean "perfectly congruent", i.e.: one must run RR's on Core or PE routers.  Said differently, history also shows that even though the speeds + feeds + data-plane features in routers are [generally] more than adequate for several years of useful life; however, CPU + DRAM in RE's/RP's have traditionally *not* kept pace with the need for moderate to fast convergence of the RIB, (let alone the added 'stress' of acting as a RR).  

In case it's not clear from the above, I have read this draft and support it's adoption as a WG draft.

-shane

---

From: Randy Bush <[email-masked]>
Date: Thu, 07 Apr 2011 10:06:53 -0700

>> history has repeatedly shown that, when the control plane and the
>> data plane, in fact any two layers, are not congruent, debugging and
>> other opex costs go quite badly.
> To be clear, "not congruent" should not be taken to mean "perfectly
> congruent"

my damned mac keeps running out of ink

> ie.: one must run RR's on Core or PE routers.

that can not forward the traffic?

randy

---

From: Shane Amante <[email-masked]>
Date: Thu, 7 Apr 2011 11:32:18 -0600

> my damned mac keeps running out of ink

:-)

> that can not forward the traffic?

I'm not sure what you're getting at.  Like many design choices, dedicated, "out-of-band" RR's are a trade-off, each operator gets to make, currently between 'congruency' vs. moderate to fast convergence.  
- route-reflection is /already/ a CPU and memory (DRAM) intensive process;
- RR's need to consume several [very] large Adj-RIB-In's from their iBGP peers (RR's at the same level of the RR hierarchy) as well as a much smaller number of (best-path) routes from downstream RR clients.

OTOH, RR-clients (typically, PE's), only need to hold Adj-RIB-In from their eBGP peers (customers/peers) as well as a much, much smaller Adj-RIB-In from (two) upstream RR's.

Just given the existence of the ORR + NH-SAFI drafts, should point out that many operators have already gone done the path of "out-of-band" RR's and are [finally] seeking improvements to get back to [optimal] congruency.

-shane

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 07 Apr 2011 19:35:02 +0200

Hello Hannes,

>     scaled up enough to support "enough" distinct POPs.

It is not a zero-sum game.

Even if you would need to perform customized path selection and 
customized update generation for each client it would still be much 
better then pushing all domain external paths to all clients and allow 
them to select the best and optimal path.

It is even more of a non zero-sum game due to the fact that Optimal 
Reflection easily allows to group clients and generate optimal best path 
for the group of them which both saves the total sum of network 
processing and amount of BGP state other wise needed to be distributed 
and maintain across all clients.

There are number of other advantages which are very important to keep in 
mind:

* Even if you would place RRs within each POP (not acting as ABR) it 
will only have visibility into given POP. While intra POP best path 
selection will be optimal inter-POP BGP best path selection will be far 
from optimal.

* As you are very well aware we already have all the tools in the 
implementations to allow non-self-rooted IGP calculations. We do it for 
all surrounding nodes during LFA. As it has been already indicated on 
the list before there are algorithms allowing for implementation 
optimizations in this space as well if it turns out that there is a need.

* The point of computational load needs to be substantial and 
demonstrated in practice in order to start considering this or any 
proposal as "too heavy". I have not seen any solid data proving that RR 
implementation could not run 20-50 non-self-rooted SPFs (including all 
SPF optimizations). As a matter of fact you may only need as many SPFs 
or update generations as many unique BGP next hops you have if you take 
an up-side down BGP implementation design into consideration.

>     needs to get deployed on older control-plane CPUs).

Ilya's proposal is extremely light way of providing the nh metric. And 
no this is not a new protocol as such, but an extension to existing 
protocol. If your worry is that it would have problems to be deployed 
due to CPU processing power limits I think you may be envisioning 
something very different then what is currently in the spec.

NH SAFI does not require any new computation overhead. It just lifts the 
values already present and sends it over new BGP SAFI.

>    in more detail ? - i can contribute some text if you want;

It is true that section 3.2 of the current spec was invented as a side 
product and it has it's own value even if used as stand-alone. However 
it has even greater value if used together with optimal route reflection.

And considering all support received from number of network operators 
both on the list as well as off the list for the draft as is today I 
would not like to separate it from the main spec at this point.

Many thx,
R.

---

From: Randy Bush <[email-masked]>
Date: Thu, 07 Apr 2011 10:58:35 -0700

> - RR's need to consume several [very] large Adj-RIB-In's

those are RE loads.  should still be able to forward.

> Just given the existence of the ORR + NH-SAFI drafts, should point out
> that many operators have already gone done the path of "out-of-band"
> RR's and are [finally] seeking improvements to get back to [optimal]
> congruency.

i usually suspect that the number of drafts is an indicator of resume
issues, not useful technology.

if i was in a deeper curmudgeonly mood i might comment on adding more
kludge in an attempt to ameliorate a poor design choice.

randy

---

From: Hannes Gredler <[email-masked]>
Date: Thu, 7 Apr 2011 19:58:59 +0200

On Thu, Apr 07, 2011 at 07:35:02PM +0200, Robert Raszuk wrote:
| Hello Hannes,
| 
| >1. downside:
| >    there is no real advantage in terms of
| >    computational load. i.e. it is a zero-sum game -
| >    you are proposing to _centralize_ a _distributed_ computation
| >    by moving (BGP per-POP best-path selection, non-self-rooted IGP
| >    calculation) from the clients to the RR. i am bit worried if RRs can be
| >    scaled up enough to support "enough" distinct POPs.
| 
| It is not a zero-sum game.
| 
| Even if you would need to perform customized path selection and
| customized update generation for each client it would still be much
| better then pushing all domain external paths to all clients and
| allow them to select the best and optimal path.

guess my main concern here is that on RRs you have typically
a single peer-group. your proposal forces the RRs to have
N peer-groups (at least one per POP). so update generation is
not as cheap as it used to be.

| It is even more of a non zero-sum game due to the fact that Optimal
| Reflection easily allows to group clients and generate optimal best
| path for the group of them which both saves the total sum of network
| processing and amount of BGP state other wise needed to be
| distributed and maintain across all clients.
| 
| There are number of other advantages which are very important to
| keep in mind:
| 
| * Even if you would place RRs within each POP (not acting as ABR) it
| will only have visibility into given POP. While intra POP best path
| selection will be optimal inter-POP BGP best path selection will be
| far from optimal.
| 
| * As you are very well aware we already have all the tools in the
| implementations to allow non-self-rooted IGP calculations. We do it
| for all surrounding nodes during LFA. As it has been already
| indicated on the list before there are algorithms allowing for
| implementation optimizations in this space as well if it turns out
| that there is a need.
| 
| * The point of computational load needs to be substantial and
| demonstrated in practice in order to start considering this or any
| proposal as "too heavy". I have not seen any solid data proving that
| RR implementation could not run 20-50 non-self-rooted SPFs
| (including all SPF optimizations). As a matter of fact you may only
| need as many SPFs or update generations as many unique BGP next hops
| you have if you take an up-side down BGP implementation design into
| consideration.

you are right, usually router vendors know how to get this right.
do you think that the additional internal peer-groups for update
generation come for free ?

| >    note: ilya's next-hop AF cost NLRI solves the IGP calculation
| >    nicely, but has the usual deployment-tax of new protocols
| >    (especially since we need to consider that new software
| >    needs to get deployed on older control-plane CPUs).
| 
| Ilya's proposal is extremely light way of providing the nh metric.
| And no this is not a new protocol as such, but an extension to
| existing protocol. If your worry is that it would have problems to
| be deployed due to CPU processing power limits I think you may be
| envisioning something very different then what is currently in the
| spec.

my reasoning is as such:
usually proto-extensions are available for the lastest software release,
- later software releases have typically a larger footprint,
and since this work is targeted at preserving older infrastructure,
i am wondering if this is practicaly feasible.

| NH SAFI does not require any new computation overhead. It just lifts
| the values already present and sends it over new BGP SAFI.

i understand that, but i'd assume (unless your company has found the
magic key to unbloat software ;-)) that a potential optimal-RR/next-hop AFI
enabled software comes with a software release, which has storage/mem/cpu
requirements not suitable to the routers which the feature tries to protect.

| >2. upside:
| >    section - 3.2. Configuration-based flexible route reflector
| >    placement. this is a neat idea, as one can deploy central
| >    RRs in the data-center and still get decent path-diversity.
| >
| >suggestion:
| >   any hard feelings about spinning out section 3.2 into
| >   a "Virtualized Route Reflection" draft, where all the implications
| >   wrt to IGP changes, BGP route resolver changes etc. are described
| >   in more detail ? - i can contribute some text if you want;
| 
| It is true that section 3.2 of the current spec was invented as a
| side product and it has it's own value even if used as stand-alone.
| However it has even greater value if used together with optimal
| route reflection.
| 
| And considering all support received from number of network
| operators both on the list as well as off the list for the draft as
| is today I would not like to separate it from the main spec at this
| point.

bummer;

for the record, i do not support this draft as a wg-item, since
it breaks the most important scaling tool available on RRs.
which is efficient update generation through a single peer-group.

/hannes

| >On Thu, Mar 31, 2011 at 03:34:31PM +0200, Robert Raszuk wrote:
| >|
| >| Authors of "BGP Optimal Route Reflection (BGP-ORR)" draft document
| >| would like to propose the adoption of this work as the IDR WG item.
| >|
| >| Ref:
| >| http://tools.ietf.org/html/draft-raszuk-bgp-optimal-route-reflection-01
| >
|

---

From: John Scudder <[email-masked]>
Date: Thu, 7 Apr 2011 14:10:17 -0700

On Apr 6, 2011, at 6:10 PM, Robert Raszuk wrote:
...
> above stated comment seems to be very subjective and quite narrowly 

It depends on how you construe "computationally expensive".  I had my computer science big-O scaling glasses on, and from that point of view I think Ron's comment is right on.  Your response seems to express the view that if you have a platform with a factor of N headroom, you may not care that some of BGP's core computations have gotten N times more expensive.  

As an outline, components of increased cost include:

- Best path run per distinct group of clients
- Update generation and queueing per distinct group of clients
- Possibly, IGP run per distinct group of clients (I realize this 
  is optional in some variants; the others are not)

A straightforward Theory of Comp 101 analysis of the relevant algorithms says that no matter how much you finesse your implementation, you are going to increase the costs of several of the key computations of the BGP protocol, at least those listed above.  The increase will be at best linear in the number of topologically distinct groups of clients.

Another way of thinking about this is that you'll need similar computational resources on your converged RR as you need on distributed set of RRs.  If you're replacing 10 RRs with one converged one, you will need something like 10x the computes and memory on that converged box.  Some economy of scale may be possible but remember that sometimes you get diseconomies of scale too, such as the step function to upgrade to a larger and more complex box.

This doesn't mean that the proposal is infeasible.  People may want to implement software for, install and maintain fewer, much larger, boxes.  But it does mean that the costs have to be very clearly understood and not hand-waved over.

With my individual contributor hat and other clothing items on, I discourage adoption of this draft until the scaling implications are more clearly elucidated.  I realize Section 5 touches on this briefly but I think a more rigorous analysis is called for.

--John

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 07 Apr 2011 23:48:42 +0200

Hi John,

Since you asked for it please allow me to focus and summarize few facts 
which should address comments from you, Ron and Hannes which perhaps 
just accidentally are all from the same page:

* It is a well known fact that routers have limited CPUs as compared 
with industry computing platforms. Even CPU refresh of an average 
computing platform does happen much more frequently then respin of any 
RP or RE in the router. Leave alone the cost of it. However let me point 
out that once we are discussing control plane RRs those do not need to 
run on routers.

* It is also to be observed that some routing operating systems already 
for years are 64 bit and can easily address large amount of memory while 
some other operating systems are still 32 bit and the work is just in 
progress to move them to 64 bit.

While I could prove in the numbers some particular platforms scaling 
data I do not believe that this sort of marketing data is a proper 
argument to be used in any of the IETF working groups and I find it 
improper.

With this in mind it is perfectly understood that if someone does not 
have a right car to participate in the race they will discourage or 
perhaps even attempt to try to call off the tournament all together even 
before the race starts.

Please allow me to "more clearly elucidate" that basic tests over linux 
home made PC reveal that even running 50 separate instances of BGP each 
generating updates of full IPv4 real Internet table feed of 10 paths to 
group of clients does not indicate any significant CPU or processing 
burden. And this is 50 independent IGPs too without any optimization 
between SPFs. After all there are multi CPU motherboards in Fry's today 
with each CPU containing 4-6 cores.

Last let's keep in mind that by adopting a work item which clearly 
already has indicated a strong support among real world operators we are 
allowing to officially work on it within IDR. It is not last call, it is 
not place to review the implementation reports and compare it's 
implementation scaling numbers. I do hope that you as the IDR co-chair 
will recognize this and would in fact encourage this or perhaps many 
other similar proposals to be adopted within the working group in spite 
of the fact that some of the vendor's may have an issue with 
commercially productizing them today.

Best regards,
R.

> On Apr 6, 2011, at 6:10 PM, Robert Raszuk wrote: ...
>>> Even if the BGP domain were to fit in a single IGP area, the
>>> solution described in Section 3 becomes computationally expensive
>>> if the domain contains many POPs.
>>
>> Let me point out that what may be computationally expensive for one
>> RR platform may not provide a significant load for some other RR
>> implementation on other choice of computational platform. Therefor
>> your above stated comment seems to be very subjective and quite
>> narrowly focused.
>
> It depends on how you construe "computationally expensive".  I had my
> computer science big-O scaling glasses on, and from that point of
> view I think Ron's comment is right on.  Your response seems to
> express the view that if you have a platform with a factor of N
> headroom, you may not care that some of BGP's core computations have
> gotten N times more expensive.
>
> - Best path run per distinct group of clients - Update generation and
> queueing per distinct group of clients - Possibly, IGP run per
> distinct group of clients (I realize this is optional in some
> variants; the others are not)
>
> A straightforward Theory of Comp 101 analysis of the relevant
> algorithms says that no matter how much you finesse your
> implementation, you are going to increase the costs of several of the
> key computations of the BGP protocol, at least those listed above.
> The increase will be at best linear in the number of topologically
> distinct groups of clients.
>
> Another way of thinking about this is that you'll need similar
> computational resources on your converged RR as you need on
> distributed set of RRs.  If you're replacing 10 RRs with one
> converged one, you will need something like 10x the computes and
> memory on that converged box.  Some economy of scale may be possible
> but remember that sometimes you get diseconomies of scale too, such
> as the step function to upgrade to a larger and more complex box.
>
> This doesn't mean that the proposal is infeasible.  People may want
> to implement software for, install and maintain fewer, much larger,
> boxes.  But it does mean that the costs have to be very clearly
> understood and not hand-waved over.
>
> With my individual contributor hat and other clothing items on, I
> discourage adoption of this draft until the scaling implications are
> more clearly elucidated.  I realize Section 5 touches on this briefly
> but I think a more rigorous analysis is called for.
>
> --John

---

From: Ilya Varlashkin <[email-masked]>
Date: Fri, 8 Apr 2011 00:31:31 +0200

John,

> A straightforward Theory of Comp 101 analysis of the relevant algorithms says that no matter how much you finesse your implementation, you are going to increase the costs of several of the key comp…

I think Best Path and IGP computations will have less than linear increase of cost. For Best Path if you sort next-hops in "certain way" you can calculate Best Path in single traversal of the RIB, spending more time not on every step but only when next-hops are considered, which grows less than linearly. Some blocks of Update Generation could be potentially optimised in similar fashion or even done at the same time. For IGP it has been already shown some month's ago that algorithms exist that could find multiple shortest paths in single go, may be even with the same O-complexity as some routers may already use now for single-rooted SPF calculations. Have I misunderstood something?

> Another way of thinking about this is that you'll need similar computational resources on your converged RR as you need on distributed set of RRs.  If you're replacing 10 RRs with one converged one…
Upgrading memory on one RR won't cost as much as 10 complete boxes. On the other hand, it looks like there is better-than-linear scaleability, in which case we don't even need 10 times better hardware.

/iLya

---

From: Mark Austen <[email-masked]>
Date: Fri, 8 Apr 2011 17:14:14 +1000

>From an operators perspective I fully support the solutions put forward in
this draft. They provide the best approach that I have seen so far to ensure
a centralized route reflector selects the optimal BGP route for a client.

On 8 April 2011 08:31, Ilya Varlashkin <[email-masked]> wrote:

> > A straightforward Theory of Comp 101 analysis of the relevant algorithms
> says that no matter how much you finesse your implementation, you are going
> to increase the costs of several of the key computations of the BGP
> protocol, at least those listed above.  The increase will be at best linear
> in the number of topologically distinct groups of clients.
> >
>
> I think Best Path and IGP computations will have less than linear increase
> of cost. For Best Path if you sort next-hops in "certain way" you can
> calculate Best Path in single traversal of the RIB, spending more time not
> on every step but only when next-hops are considered, which grows less than
> linearly. Some blocks of Update Generation could be potentially optimised in
> similar fashion or even done at the same time. For IGP it has been already
> shown some month's ago that algorithms exist that could find multiple
> shortest paths in single go, may be even with the same O-complexity as some
> routers may already use now for single-rooted SPF calculations. Have I
> misunderstood something?
>
> computational resources on your converged RR as you need on distributed set
> of RRs.  If you're replacing 10 RRs with one converged one, you will need
> something like 10x the computes and memory on that converged box.  Some
> economy of scale may be possible but remember that sometimes you get
> diseconomies of scale too, such as the step function to upgrade to a larger
> and more complex box.
> >
> Upgrading memory on one RR won't cost as much as 10 complete boxes. On the
> other hand, it looks like there is better-than-linear scaleability, in which
> case we don't even need 10 times better hardware.
>
> /iLya
>
>
>

---

From: John Scudder <[email-masked]>
Date: Fri, 8 Apr 2011 12:01:37 -0700

Robert,

With regard to your points that bigger boxes can be built:  Yes of course.  In fact I directly addressed this point in my previous message.  

Your exclusive focus in your reply on proving that bigger boxes can be built maybe is an implicit agreement with my analysis of the computational complexity of an ORR -- that is, maybe you are agreeing that there is no free lunch, an ORR will require more compute resources than a current RR.  In that case, we are close to being on the same page.  The fact that bigger boxes can be built has nothing to do with analysis of the proposal's computational complexity. [*]  In my reading of both the draft and the conversation to date it seems as though there is (what may be) too much optimism about the ability to optimize ORR code to perform at equal scale on current hardware.  That may be possible with current workloads.  It very likely may not.  It definitely will not with a pessimal workload.  (See also my reply to Ilya.)

I am perplexed by your apparent dismissal of the value of understanding of the proposal's intrinsic scaling properties.  I realize this is not an academic conference but I assume that most of us as protocol designers have some Computer Science background and understand there is a place for analysis of computational complexity.  To draw an analogy to mechanical engineering, it is not always necessary to build a bridge and watch it fall down in order to know there was something wrong with its design. [**]

So, to be clear: My concern is that those who are supporting the proposal's adoption should understand that we are talking about replacing N smaller boxes with one box containing O(N) times the compute resources.  I want to be sure the proposal is not being represented (and bought) as a free lunch.  People become justifiably upset when their free lunch turns out to have a cost.  On the other hand, if the WG has considered the cost of the lunch and wants to buy and eat it, OK.

--John

[*] http://en.wikipedia.org/wiki/Computational_complexity

[**] This is an analogy, meant to illustrate the value of analysis as opposed to pure build-it-and-try-it or throw-more-hardware-at-it hacking.  It is NOT meant to be an opinion about the value of the current proposal.

---

From: John Scudder <[email-masked]>
Date: Fri, 8 Apr 2011 12:01:40 -0700

Ilya,

Thank you for responding on-topic!  

After giving your message some thought it seems to me that you are pointing out that there is scope for optimization such that the expected cost under some workloads will be less than O(N) in the number of topologically distinct groups.  Granted, but please note several things:

- The upper bound is still O(N).
- AFAICT your implicit assumption is that many routes will tie-break before the 
  IGP step is reached.  But for such routes, the behavior of a current RR is the
  same as an ORR.  Thus if the ORR is interesting, that would seem to demonstrate 
  that the expected workload does include many routes that tie-break at or after 
  the IGP step.
- This seems to indicate that the optimizations you mention would not often come 
  into play for the expected workload.
- I'm primarily concerned with the costs inherent in the BGP protocol here.  I 
  tried to be clear in my previous that I'm willing for sake of argument to neglect
  any IGP related costs.

Also, please remember that O(N) doesn't mean "is N times higher" it means "is linearly higher".  (That's what I was trying to get at by "... *something* *like* 10x ...")

I don't see how you get to the conclusion that "it looks like there is better-than-linear scaleability", unless you are talking about the expected case under a workload that tie-breaks before the IGP step, in which case I've already argued you don't even need an ORR.

In closing let me repeat my remark to Robert: My concern is that those who are supporting the proposal's adoption should understand that we are talking about replacing N smaller boxes with one box containing O(N) times the compute resources.  No free lunch.

Thanks,

--John

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 08 Apr 2011 21:22:22 +0200

Hi John,

Except one point below I do agree with your comments.

> In my reading of both the draft and the conversation to date it seems
> as though there is (what may be) too much optimism about the ability
> to optimize ORR code to perform at equal scale on current hardware.

It really depends what you define as the "current hardware".

If by "current hardware" you mean currently deployed route reflectors 
which would get new software and they automagically be able to perform N 
times more computations per sec - I think everyone on the list is clear 
that this is not the assumptions the draft makes.

However if by "current hardware" you mean currently available control 
plane computing platforms on the market which do have much more 
computing power then 10s of current route reflectors for fraction of 
current route reflector's cost than I do not see any substantial data 
which would prove that such hardware can not easily meet the 
computational requirements of the ORR draft in question.

Best regards,
R.

> Robert,
>
> With regard to your points that bigger boxes can be built:  Yes of
> course.  In fact I directly addressed this point in my previous
> message.
>
> Your exclusive focus in your reply on proving that bigger boxes can
> be built maybe is an implicit agreement with my analysis of the
> computational complexity of an ORR -- that is, maybe you are
> agreeing that there is no free lunch, an ORR will require more
> compute resources than a current RR.  In that case, we are close to
> being on the same page.  The fact that bigger boxes can be built has
> nothing to do with analysis of the proposal's computational
> complexity. [*] In my reading of both the draft and the conversation
> to date it seems as though there is (what may be) too much optimism
> about the ability to optimize ORR code to perform at equal scale on
> current hardware. That may be possible with current workloads.  It
> very likely may not. It definitely will not with a pessimal workload.
> (See also my reply to Ilya.)
>
> I am perplexed by your apparent dismissal of the value of
> understanding of the proposal's intrinsic scaling properties.  I
> realize this is not an academic conference but I assume that most of
> us as protocol designers have some Computer Science background and
> understand there is a place for analysis of computational
> complexity. To draw an analogy to mechanical engineering, it is not
> always necessary to build a bridge and watch it fall down in order to
> know there was something wrong with its design. [**]
>
> So, to be clear: My concern is that those who are supporting the
> proposal's adoption should understand that we are talking about
> replacing N smaller boxes with one box containing O(N) times the
> compute resources.  I want to be sure the proposal is not being
> represented (and bought) as a free lunch.  People become justifiably
> upset when their free lunch turns out to have a cost.  On the other
> hand, if the WG has considered the cost of the lunch and wants to
> buy and eat it, OK.
>
> --John
>
> [**] This is an analogy, meant to illustrate the value of analysis
> as opposed to pure build-it-and-try-it or throw-more-hardware-at-it
> hacking.  It is NOT meant to be an opinion about the value of the
> current proposal.
>
>> Since you asked for it please allow me to focus and summarize few
>> facts which should address comments from you, Ron and Hannes which
>> perhaps just accidentally are all from the same page:
>>
>> * It is a well known fact that routers have limited CPUs as
>> compared with industry computing platforms. Even CPU refresh of an
>> average computing platform does happen much more frequently then
>> respin of any RP or RE in the router. Leave alone the cost of it.
>> However let me point out that once we are discussing control plane
>> RRs those do not need to run on routers.
>>
>> * It is also to be observed that some routing operating systems
>> already for years are 64 bit and can easily address large amount
>> of memory while some other operating systems are still 32 bit and
>> the work is just in progress to move them to 64 bit.
>>
>> While I could prove in the numbers some particular platforms
>> scaling data I do not believe that this sort of marketing data is
>> a proper argument to be used in any of the IETF working groups and
>> I find it improper.
>>
>> With this in mind it is perfectly understood that if someone does
>> not have a right car to participate in the race they will
>> discourage or perhaps even attempt to try to call off the
>> tournament all together even before the race starts.
>>
>> Please allow me to "more clearly elucidate" that basic tests over
>> linux home made PC reveal that even running 50 separate instances
>> of BGP each generating updates of full IPv4 real Internet table
>> feed of 10 paths to group of clients does not indicate any
>> significant CPU or processing burden. And this is 50 independent
>> IGPs too without any optimization between SPFs. After all there
>> are multi CPU motherboards in Fry's today with each CPU containing
>> 4-6 cores.
>>
>>  already has indicated a strong support among real world operators
>> we are allowing to officially work on it within IDR. It is not
>> last call, it is not place to review the implementation reports
>> and compare it's implementation scaling numbers. I do hope that you
>> as the IDR co-chair will recognize this and would in fact
>> encourage this or perhaps many other similar proposals to be
>> adopted within the working group in spite of the fact that some of
>> the vendor's may have an issue with commercially productizing them
>> today.
>>
>> Best regards, R.
>>
>>>>>  solution described in Section 3 becomes computationally
>>>> Let me point out that what may be computationally expensive
>>>> for one RR platform may not provide a significant load for
>>>> some other RR implementation on other choice of computational
>>>> platform. Therefor your above stated comment seems to be very
>>>> subjective and quite narrowly focused.
>>>
>>> It depends on how you construe "computationally expensive".  I
>>> had my computer science big-O scaling glasses on, and from that
>>> point of view I think Ron's comment is right on.  Your response
>>> seems to express the view that if you have a platform with a
>>> factor of N headroom, you may not care that some of BGP's core
>>> computations have gotten N times more expensive.
>>>
>>> - Best path run per distinct group of clients - Update
>>> generation and queueing per distinct group of clients - Possibly,
>>> IGP run per distinct group of clients (I realize this is optional
>>> in some variants; the others are not)
>>>
>>> implementation, you are going to increase the costs of several
>>> of the key computations of the BGP protocol, at least those
>>> listed above. The increase will be at best linear in the number
>>> of topologically distinct groups of clients.
>>>
>>>  memory on that converged box.  Some economy of scale may be
>>> possible but remember that sometimes you get diseconomies of
>>> scale too, such as the step function to upgrade to a larger and
>>> more complex box.
>>>
>>> This doesn't mean that the proposal is infeasible.  People may
>>> want to implement software for, install and maintain fewer, much
>>> larger, boxes.  But it does mean that the costs have to be very
>>> clearly understood and not hand-waved over.
>>>
>>> discourage adoption of this draft until the scaling implications
>>> are more clearly elucidated.  I realize Section 5 touches on this
>>> briefly but I think a more rigorous analysis is called for.
>>>
>>> --John
>>
>
>

---

From: Ilya Varlashkin <[email-masked]>
Date: Fri, 8 Apr 2011 21:47:56 +0200

John,

Please see comments inline.

> - The upper bound is still O(N).

Yes, indeed but only in step that breaks tie on next-hop, not before (meaning _increase_ total complexity of best path selection is far below linear when number of prefixes is large like in contemporary Internet). Only dependance is not on number of clients, but on number of next-hops (and sometimes on subset of next-hops). Once optimisation employed, complexity remains constant regardless whether we add or remove clients. If all policy towards all RR clients is the same, then rather than depending on number of clients, N is actually number of next-hops. For every prefix there will be at most N (which is still number of next-hops) groups of RR clients with unique choice of best next hop.

>  that the expected workload does include many routes that tie-break at or after 

On contrary, I've described only worst-case scenario where for every prefix selection algorithm proceeds beyond MED consideration.

>  into play for the expected workload.

On networks that you've described, where ties are broken before next-hop, there will be of course little gain but there we don't need optimised Route Reflection at all. However the networks I had in mind are those with dense peerings across the globe, where breaking tie on next-hop will be reached more often than not.

>  tried to be clear in my previous that I'm willing for sake of argument to neglect
So did I, considering costs can be retrieved from sources other than IGP.

> Also, please remember that O(N) doesn't mean "is N times higher" it means "is linearly higher".  (That's what I was trying to get at by "... *something* *like* 10x ...")
Although years after finishing university most of my math skills are in latent state, I'm aware of big-O notation. Good that we're talking about the same things.

> I don't see how you get to the conclusion that "it looks like there is better-than-linear scaleability", unless you are talking about the expected case under a workload that tie-breaks before the I…

Key is in finding (once per next-hop, not per prefix) for which set of RRc given next-hop is best, then second-best then i-th-best. This needs to be done only once for given RR-c topology and not performed during best path selection at all.

Kind regards,
iLya

---

From: Danny McPherson <[email-masked]>
Date: Fri, 8 Apr 2011 17:17:10 -0400

> With my individual contributor hat and other clothing items on, I discourage adoption of this draft until the scaling implications are more clearly elucidated.  I realize Section 5 touches on this…

I like this idea - if we intend to apply it ubiquitously and 
there are folks willing to do it.  Some other places application 
seems prudent:

1) System-wide sub-optimalities introduced by current route 
reflection implementations in order to minimize local processing 
overhead (e.g., the RR-dont-reflect-back-to-client function 
removed in 2796).

2) All the add-path work that's happening..

3) Securing routing work when it finally finds it's way to IDR.

To date, everything IDR does is largely about introducing more state 
and rate in the network in order to solve _real [relative] problems, 
I'm pleasantly surprised to see you press so hard against this one 
based on the scale premise.

-danny

---

From: John Scudder <[email-masked]>
Date: Fri, 8 Apr 2011 14:32:45 -0700

> that this is not the assumptions the draft makes.

I meant "hardware currently performing RR functionality in the network".  Perhaps I should have written "equivalent hardware" or "the same hardware".  I trust you get the idea -- what you meant by the above paragraph.

I'm not confident this was clear from the draft or previous discussion; I expect this conversation has made it clearer.  The response I have in my inbox from Ilya seems to indicate there is not agreement on this point, but at minimum people must be aware it is open to question.

> computational requirements of the ORR draft in question.

That is not what I meant.  I trust this is abundantly clear by now.

--John

---

From: Ilya Varlashkin <[email-masked]>
Date: Sat, 9 Apr 2011 00:01:26 +0200

> I'm not confident this was clear from the draft or previous discussion; I expect this conversation has made it clearer.  The response I have in my inbox from Ilya seems to indicate there is not agr…

I have intentionally omitted hardware discussion in my previous response to address only algorithmic part, but not to express agreement or disagreement on skipped part. To make my position clear, I do believe that contemporary (PC) hardware is well capable of running BGP-ORR functions without requiring much expenses. More elaborative explanation: if such contemporary hardware is used as a Route Reflector without BGP-ORR functionality, then it (hardware) will be running at small fraction of its potential. Deploying X such boxes would cost me X times more than single box. On the other hand I could just employ unused potential of single box to run BGP-ORR functions. From this perspective BGP-ORR does not require X times better hardware than X boxes running legacy variant of RR.

Kind regards,
iLya

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 09 Apr 2011 00:33:40 +0200

Hi John,

I appreciate the fact that you are trying to make sure that people who
support it do realize perhaps the need for new RR platform. But in my
point of view I give people participating in the IDR enough of credit 
that they understand the proposal if they are commenting on it. 
Otherwise it is normal that they would ask questions for clarification 
then comment on it.

But with Danny's point in mind let me stop for a moment on the scaling
aspects of things.

At no point in the draft there is a claim that all clients or client
groups must be supported by single route reflector.

Here let me allow to point out that the exact same claim has been made 
in the past by others that at no point in the network one would need to 
keep all L3VPN state. If amount of state exceeds the capacity or 
processing power of any single router (RR or PE) you divide it by 
introducing another router. So without going further on that example let 
me point out that if one ORR enabled RR can not serve all groups of 
clients in the network you divide the load and introduce another ORR 
enabled RR to server another group of clients. Very simple.

And just like Danny I am also very happy to see you so strongly 
protecting against increase of BGP state and processing cycles even on 
few route reflectors in the network. I hope the same will happen on 
other proposals which call for increase of BGP state and processing 
power not only in few RRs but network wide. Future will likely to prove 
this very soon.

Also you seem to stay really focused on the additional CPU and memory
load of the RR. Let me reiterate what Jeff and others have already 
observed that this in the same time will result in decrease of state of 
processing of BGP churn on 100s or 1000s of given network's PEs and 
ASBRs without compromising the optimal exit point.

Otherwise EACH such PE or ASBR would have to be equipped with exact same 
amount of memory and CPU what will be used by such ORR enabled RR to 
server single group of clients (for example sharing given POP). For me 
this is pure gain of the factor of number of routers in the POP.

Moreover if such PEs or ASBRs are in the IGP hierarchical area they will 
not be able to determine the optimal exit points of BGP paths with next 
hops residing in other areas even assuming that such box get's all 
domain external paths via add-paths to it. That is functional advantage 
of ORR not available today in hierarchical networks (assuming no 
next-hop-self and no domain wide /32 leaking).

Last but not least it really needs to be highlighted that if the RR is
reflecting customized best path for a group of clients not all IGP
events in the network will result in best path change to everyone. This
again will save CPU cycles of the ASBRs and PEs as they will not need to 
process BGP churn which does not apply to them.

 > response I have in my inbox from Ilya seems to indicate there is not
 > agreement on this point,

My reading of Ilya response clearly indicates that he was precisely 
responding to your questions without repeating the same statements made 
already on the list by others over and over.

Best regards,
R.

PS.

But I must admit one thing .. that if the strategy of repeating the same 
point of RR scale issue without even considering all scaling aspects 
network wide is targeted to burn out the co-author of an idea,  where 
such idea has been born from the real needs of the operational community 
and is proposed to help efficient network operations .. you are slowly 
succeeding.

I do hope that where IDR charter talks about work on "BGP scalability" 
it does not only mean to accommodate and welcome all proposals which 
increase BGP scale. I do hope that there is some perhaps small room for 
proposals which target network wide decrease of BGP state while 
maintaining or enhancing routing efficiency and both capex and opex costs.

>>> In my reading of both the draft and the conversation to date it
>>> seems as though there is (what may be) too much optimism about
>>> the ability to optimize ORR code to perform at equal scale on
>>> current hardware.
>>
>> If by "current hardware" you mean currently deployed route
>> reflectors which would get new software and they automagically be
>> able to perform N times more computations per sec - I think
>> everyone on the list is clear that this is not the assumptions the
>> draft makes.
>
> I meant "hardware currently performing RR functionality in the
> network".  Perhaps I should have written "equivalent hardware" or
> "the same hardware".  I trust you get the idea -- what you meant by
> the above paragraph.
>
> I'm not confident this was clear from the draft or previous
> discussion; I expect this conversation has made it clearer.  The
> response I have in my inbox from Ilya seems to indicate there is not
> agreement on this point, but at minimum people must be aware it is
> open to question.
>
>> However if by "current hardware" you mean currently available
>> control plane computing platforms on the market which do have much
>> more computing power then 10s of current route reflectors for
>> fraction of current route reflector's cost than I do not see any
>> substantial data which would prove that such hardware can not
>> easily meet the computational requirements of the ORR draft in
>> question.
>

---

From: John Scudder <[email-masked]>
Date: Fri, 8 Apr 2011 17:13:03 -0700

Folks,

This thread has diverged in some interesting and even surprising ways.  I don't intend to follow up further over the weekend but I did want to close on my original point:

> With my individual contributor hat and other clothing items on, I discourage adoption of this draft until the scaling implications are more clearly elucidated.  I realize Section 5 touches on this…

As far as I'm concerned the extensive conversation over the last couple of days on this topic has shed sufficient light, and I withdraw my objection.

--John

---

From: Jeff Wheeler <[email-masked]>
Date: Sat, 9 Apr 2011 12:18:23 -0400

On Fri, Apr 8, 2011 at 6:33 PM, Robert Raszuk <[email-masked]> wrote:
> I do hope that where IDR charter talks about work on "BGP scalability" it
> does not only mean to accommodate and welcome all proposals which increase
> BGP scale. I do hope that there is some perhaps small room for proposals
> which target network wide decrease of BGP state while maintaining or
> enhancing routing efficiency and both capex and opex costs.

It should be on our minds that "BGP scalability" means different
things to different operators.  It is not always a simple matter of
the most routes in the least convergence time on the control planes
available in the routers.  The very concept of route-reflection is
designed to allow for shifting work from one node to another as well
as reducing total work.  Some networks have a greater need to shift
work onto nodes where CPU and RAM is plentiful than they do to simply
reduce the total amount of work to be done.

In the last decade or so, we have seen a remarkable shift from big
iron servers and vertically-scaled systems to distributed server farms
and horizontally-scaled applications.  Networks with large VPN
customer-bases have also realized this is possible and indeed
necessary as the needs of VPN customers exceed various resource limits
(FIB/CPU/RAM) of available routing platforms.

We should all recognize that there is more than one way to scale the network.

---

From: Paul Jakma <[email-masked]>
Date: Mon, 11 Apr 2011 13:40:14 +0100 (BST)

On Fri, 8 Apr 2011, John Scudder wrote:

> After giving your message some thought it seems to me that you are 
> pointing out that there is scope for optimization such that the 
> expected cost under some workloads will be less than O(N) in the 
> number of topologically distinct groups.  Granted, but please note 
> several things:

> In closing let me repeat my remark to Robert: My concern is that 
> those who are supporting the proposal's adoption should understand 
> that we are talking about replacing N smaller boxes with one box 
> containing O(N) times the compute resources.  No free lunch.

It may be worse than that. You have N boxes, each doing O(N) 
route-selection work. So in total that's O(N^2) worth machines, which 
this proposal (IIUC) intends to centralise somewhat. There already 
have been RR systems deployed at large IXes which do 
client-perspective route selection, and the O(N^2) scaling is a big 
problem for them, both for memory and CPU.

So, not to say there isn't value in this, but just don't expect to 
get much out of it in terms of the client:RR ratio.

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
"To vacillate or not to vacillate, that is the question ... or is it?"

---

From: "iLya" <[email-masked]>
Date: Mon, 11 Apr 2011 15:32:17 +0200

--------------------------------------------------
From: "Paul Jakma" <[email-masked]>
Sent: Monday, April 11, 2011 2:40 PM
To: "John Scudder" <[email-masked]>
Cc: "Ilya Varlashkin" <[email-masked]>; <[email-masked]>; <[email-masked]>
Subject: Re: [Idr] BGP Optimal Route Reflection (BGP-ORR)

>> In closing let me repeat my remark to Robert: My concern is that those 
>> who are supporting the proposal's adoption should understand that we are 
>> talking about replacing N smaller boxes with one box containing O(N) 
>> times the compute resources.  No free lunch.
>
> route-selection work. So in total that's O(N^2) worth machines, which this 
> proposal (IIUC) intends to centralise somewhat. There already have been RR 
> systems deployed at large IXes which do client-perspective route 
> selection, and the O(N^2) scaling is a big problem for them, both for 
> memory and CPU.
>

ok, if N in this thread is used as number of clients, let me call total 
number of possible next-hops as K. If an UPDATE contains all K next-hops, 
then every client is guaranteed to have one of them as best so we need only 
K iterations (not N). If an UPDATE contains only (K-M) next-hops, then it's 
guaranteed that each of them will be no worse than (M+1)-best for any 
client. With graph of next-hop preferences we can find group of clients 
"interested in given next-hop under given circumstances" in only few 
iterations so we can both select best-hop for each and prepare UPDATE 
message regardless of number of clients. Of course you still need to iterate 
through all sockets to send messages out (either user-land, or kernel-land), 
but you'd do so in current RR just the same. It's fair to mention that if 
number of clients is small, then falling back on iteration through clients 
rather than next-hops may be more efficient (I say may because I haven't yet 
evaluated optimisation possibilities on that side). But if you have only 
handful of exits from an area with 100 clients, then next-hop-based 
optimisation makes BGP-ORR work not that difficuly.

> So, not to say there isn't value in this, but just don't expect to get 
> much out of it in terms of the client:RR ratio.
>
In fact quite opposite - more clients, more gain. Also, let's not forget 
that with BGP-ORR we efectively scale control-plane and forwarding-plane 
independently. I can buy high-throughput box with prehistoric computational 
capabilities and a number-cruncher both for reasonable money, without 
BGP-ORR I need to get high-throughput-number-cruncher at much higher cost.

Kind regards,
iLya

---

From: Paul Jakma <[email-masked]>
Date: Mon, 11 Apr 2011 15:52:43 +0100 (BST)

On Mon, 11 Apr 2011, iLya wrote:

> ok, if N in this thread is used as number of clients, let me call 
> total number of possible next-hops as K. If an UPDATE contains all 
> K next-hops, then every client is guaranteed to have one of them as 
> best so we need only K iterations (not N).

Ah, ok. Though, note that K is independent of N - it may even be the 
same as or much greater than it.

> If an UPDATE contains only (K-M) next-hops, then it's guaranteed 
> that each of them will be no worse than (M+1)-best for any client. 
> With graph of next-hop preferences we can find group of clients 
> "interested in given next-hop under given circumstances" in only 
> few iterations so we can both select best-hop for each and prepare 
> UPDATE message regardless of number of clients.

You're still doing that work for each of the N clients, in order to 
know their preference to each of the K nexthops - even if it's 
looking up their preference in a pre-existing graph. So that's O(NK), 
which is O(X^2), for some value of X >= both N and K (this is 
assuming the route selection process is linear). If N and K are 
similar in magnitude then NK is fairly closely bounded by X^2 
obviously.

Now, at least one of the proposals in the draft is to compute the 
shortest path for each client (i.e. construct the graph of next-hop 
preferences which you mention), in which case the per-client 
route-selection work will be /higher/ than linear. All-pairs shortest 
path is O(V^3), where V >= K+N. If K+N << V it might be better to run 
Dijkstra N times, which is O(N*(E+VlogV). If V is of similar 
magnitude to N+K, then O(VE+V^2logV) is a tight-ish upper-bound, 
which is in between V^2 and V^3.

So you're looking at Omega(X^2), O(X^3) complexity potentially.

You can of course cache the SPF results, trading compute time for 
RAM, for as long as the underlying network remains stable. You /may/ 
be able to group some clients together - but that's not going to make 
much impact on how NK-pairs shortest-path scales, unless you restrict 
the scope to fairly trivial topologies. Note that grouping clients 
may itself scale worse than O(N).

The IXes I know of aren't trying to do per-client SPF. However 
they're doing eBGP-per-client-selection and every client is different 
so there's little to no homogeneity of selection that can be 
exploited & and over which to amortise the costs, as there might be 
in the iBGP case, as you point out.

Exactly how much scope there is in practice for such optimisation, I 
don't know. Optimal RR could scale better or perhaps worse than the 
IX cases I know about.

> forget that with BGP-ORR we efectively scale control-plane and 
> forwarding-plane independently. I can buy high-throughput box with 
> prehistoric computational capabilities and a number-cruncher both 
> for reasonable money, without BGP-ORR I need to get 
> high-throughput-number-cruncher at much higher cost.

That'd be nice, yes. I don't disagree that this draft could be 
helpful, even if scaling limits the achievable client:RR ratio. I 
just wanted to caution against having too high expectations of that 
ratio.

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
This wasn't just plain terrible, this was fancy terrible.  This was terrible
with raisins in it.
 		-- Dorothy Parker

---

From: "iLya" <[email-masked]>
Date: Mon, 11 Apr 2011 17:56:33 +0200

>> If an UPDATE contains only (K-M) next-hops, then it's guaranteed that 
>> each of them will be no worse than (M+1)-best for any client. With graph 
>> of next-hop preferences we can find group of clients "interested in given 
>> next-hop under given circumstances" in only few iterations so we can both 
>> select best-hop for each and prepare UPDATE message regardless of number 
>> of clients.
>
> You're still doing that work for each of the N clients, in order to know 
> their preference to each of the K nexthops - even if it's

You do this only once, not for every UPDATE message. As long as number of 
clients is far less than number of routes being exchanged, that's negligible 
work.

> which is O(X^2), for some value of X >= both N and K (this is assuming the 
> route selection process is linear). If N and K are similar in magnitude 
> then NK is fairly closely bounded by X^2 obviously.
>
In practice N=K case would happen only when every client is also potential 
exit point, like in flat networks. There are further optimisations possible 
depending on nature of that "flatness". E.g. in Opt-C you could leverage the 
fact that most of "final next-hops" will be reachable via relatively small 
subset of ABR/ASBR, effectively reducing K significantly. In simple IPv4 net 
you can also separate customer routes and external routes and apply 
different style of optimisation.

> Now, at least one of the proposals in the draft is to compute the shortest 
> path for each client (i.e. construct the graph of next-hop preferences 
> which you mention), in which case the per-client route-selection work will 
> be /higher/ than linear. All-pairs shortest path is O(V^3), where V >= 
> K+N. If K+N << V it might be better to run Dijkstra N times, which is 
> O(N*(E+VlogV). If V is of similar magnitude to N+K, then O(VE+V^2logV) is 
> a tight-ish upper-bound, which is in between V^2 and V^3.
>
Strictly speaking we don't really need to know all-pairs SPF, only from any 
client to any exit point (so no K+N here). And as above network topology 
knowledge may aid optimisation - if path to all exits lies through small set 
of hub points (e.g. P-routers), then preference calculations can be split in 
two (from client to hub and from hub to exit), which may significantly 
reduce amount of calculations that needs to be done.

> So you're looking at Omega(X^2), O(X^3) complexity potentially.
Only in maxed-out densely interconnected network, which is hardly 
description of majority real-world networks.

> You can of course cache the SPF results, trading compute time for RAM, for 
> as long as the underlying network remains stable. You /may/ be able to 
> group some clients together - but that's not going to make much impact on 
> how NK-pairs shortest-path scales, unless you restrict the scope to fairly 
> trivial topologies. Note that grouping clients may itself scale worse than 
> O(N).
>
If we're talking about update-groups dictated by different outgoing policies 
(with serialisation optimisation in mind), then you could pass prefixes 
through policies either before considering next-hops or in parallel and 
merge the results, so again you're not dependant on number of clients. You 
will no longer have static (config-time) update-groups but you get dynamic 
group as a side effect of best-path + policy calculations. The only thing 
that changes with ORR is that where you had G1 static update-groups before, 
you will have somewhere between G1 and K*G1 update groups (actually, number 
of next-hops preferred by all clients for given prefix) with ORR.

> The IXes I know of aren't trying to do per-client SPF. However they're 
> doing eBGP-per-client-selection and every client is different so there's 
> little to no homogeneity of selection that can be exploited & and over 
> which to amortise the costs, as there might be in the iBGP case, as you 
> point out.
>
I'm not sure comparisson with IXes is fair here because at IXes you usually 
don't compare cost to next-hop. If you do (e.g. geographically distributed 
IX architecture and you want to take RTT into account), then BGP-ORR is 
relevant only to the part where next-hop cost comes into play and in exactly 
the same way as in case of iBGP (with policy optimisation described above).

> Exactly how much scope there is in practice for such optimisation, I don't 
> know. Optimal RR could scale better or perhaps worse than the IX cases I 
> know about.
>
Next-hop-based-path-selection and applying policies can be done in 
(pseudo-)parallel, in which case each of them is as good or as bad 
independently.

>> prehistoric computational capabilities and a number-cruncher both for 
>> reasonable money, without BGP-ORR I need to get 
> That'd be nice, yes. I don't disagree that this draft could be helpful, 
> even if scaling limits the achievable client:RR ratio. I just wanted to 
> caution against having too high expectations of that ratio.
>
Good, we're progressing :-)

Kind regards,
iLya

---

From: Paul Jakma <[email-masked]>
Date: Mon, 11 Apr 2011 18:06:19 +0100 (BST)

On Mon, 11 Apr 2011, iLya wrote:

> You do this only once, not for every UPDATE message. As long as 
> number of clients is far less than number of routes being 
> exchanged, that's negligible work.

Couple of things:

a) I did say later that you could trade some space for CPU

b) It doesn't matter if you only do it every now and then if, when
    you must do it, the system then takes an unacceptably long amount
    of time to complete the task.

c) I do not see how it is guaranteed that BGP UPDATE messages will
    come in much faster than IGP changes. It may be /often/ true,
    but it's far from guaranteed to be true, so you can't rely on it
    for worst-case big-Oh analysis.

> In practice N=K case would happen only when every client is also 
> potential exit point, like in flat networks. There are further 
> optimisations possible depending on nature of that "flatness". E.g. 
> in Opt-C you could leverage the fact that most of "final next-hops" 
> will be reachable via relatively small subset of ABR/ASBR, 
> effectively reducing K significantly. In simple IPv4 net you can 
> also separate customer routes and external routes and apply 

Things like finding hubs in graphs tends not to be entirely trivial 
though.

It may range from O(V^3) kind of hard (feasible to a point, but far 
from ideal scaling) if you want to judge by, say, the relative number 
of shortest paths in the network that go through each node; to 
actually NP-hard (exact solutions for various kinds of graph 
optimisation problems).

> Strictly speaking we don't really need to know all-pairs SPF, only 
> from any client to any exit point (so no K+N here).

Doesn't matter, if we call the exit-point P, even if each K -> P 
lookup is O(1), that's still K operations that must be done.

You could do it in stages perhaps, doing the K K->P lookups first and 
then the PN per-client work, for O(K + PN). But you're still at 
Omega(N^2) or Omega(P^2), depending on how P and N compare to each 
other. Omega meaning lower-bound, i.e. the SPF overhead is still to 
be applied on top of that:

> And as above network topology knowledge may aid optimisation - if 
> path to all exits lies through small set of hub points (e.g. 
> P-routers), then preference calculations can be split in two (from 
> client to hub and from hub to exit), which may significantly reduce 
> amount of calculations that needs to be done.

If you can do that, generally, in less than O(V^3), your name 
potentially could go down in the algorithm text books. In less than 
O(V^2) and fame would be guaranteed I suspect.. ;)

Anyway...

I support the adoption of the draft.

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
Hi!  I'm Larry.  This is my brother Bob, and this is my other brother
Jimbo.  We thought you might like to know the names of your assailants.

---

From: Ilya Varlashkin <[email-masked]>
Date: Mon, 11 Apr 2011 20:04:55 +0200

>   for worst-case big-Oh analysis.

Assumption is that your network is more stable than The Internet, so you don't have as many IGP events as BGP updates.

>> Strictly speaking we don't really need to know all-pairs SPF, only from any client to any exit point (so no K+N here).
> 
> Doesn't matter, if we call the exit-point P, even if each K -> P lookup is O(1), that's still K operations that must be done.
> 

Considering that K used to be number of exit points the above is a bit confusing. If you mean K is number of clients (used to be N) and P number of exit points. Assuming you want to fall back to Dijkstra, then just reverse metrics (if they're asymmetric, NOP otherwise) and run P iterations of Dijkstra (from next-hop back to the client).

> I support the adoption of the draft.

Thank you!

Kind regards,
iLya