Subject: [Idr] Fwd: I-D Action:draft-raszuk-bgp-optimal-route-reflection-00.txt

From: Robert Raszuk <[email-masked]>
Date: Wed, 20 Oct 2010 10:05:57 -0700

FYI.  Will appreciate comments.

Many thx,
R.

-------- Original Message --------
Subject: I-D Action:draft-raszuk-bgp-optimal-route-reflection-00.txt
Date: Sun, 17 Oct 2010 12:00:02 -0700 (PDT)
From: [email-masked]
Reply-To: [email-masked]
To: [email-masked]

A New Internet-Draft is available from the on-line Internet-Drafts 
directories.

	Title           : BGP Optimal Route Reflection (BGP-ORR)
	Author(s)       : R. Raszuk, et al.
	Filename        : draft-raszuk-bgp-optimal-route-reflection-00.txt
	Pages           : 18
	Date            : 2010-10-17

[RFC4456] asserts that, because the Interior Gateway Protocol (IGP)
cost to a given point in the network will vary across routers, "the
route reflection approach may not yield the same route selection
result as that of the full IBGP mesh approach."  One practical
implication of this assertion is that the deployment of route
reflection may thwart the ability to achieve hot potato routing.  Hot
potato routing attempts to direct traffic to the closest AS egress
point in cases where no higher priority policy dictates otherwise.
As a consequence of the route reflection method, the choice of exit
point for a route reflector and its clients will be the egress point
closest to the route reflector - and not necessarily closest to the
RR clients.

Section 11 of [RFC4456] describes a deployment approach and a set of
constraints which, if satsified, would result in the deployment of
route reflection yielding the same results as the iBGP full mesh
approach.  Such a deployment approach would make route reflection
compatible with the application of hot potato routing policy.

As networks evolved to accommodate architectural requirements of new
services, tunneled (LSP/IP tunneling) networks with centralized route
reflectors became commonplace.  This is one type of common deployment
where it would be impractical to satisfy the constraints described in
Section 11 of [RFC4456].  Yet, in such an environment, hot potato
routing policy remains desirable.

This document proposes two new solutions which can be deployed to
facilitate the application of closest exit point policy centralized
route reflection deployments.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-raszuk-bgp-optimal-route-reflection-00.txt

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

---

From: "iLya" <[email-masked]>
Date: Thu, 21 Oct 2010 09:48:41 +0200

Robert,

while I like the vector of the solutions proposed by the draft, there are 
couple problems that will arise when network topology changes (e.g. due to a 
link or a node failure).

For the section 3.1 it looks like RR will need to run SPF N times. Not 
having measured SPF runtime myself I took what was available in the wild. If 
for 200 nodes it takes about 10ms for SPF to complete, then it will take 2 
seconds before RR starts best path selection calculations for the 200th 
RR-client.

For angular distance in section 4 dynamic changes in the network seem to be 
even harder challenge - in case of link failure angular distance remains the 
same while best next hop may change.

As an alternative solution RR could actively communicate RR-clients 
unordered set available next-hops and would get back ordered version of that 
set (or next-hop + metric, which is essentially the same). Even in largest 
networks it will take less than 200-300ms to propagate next-hop preference 
change from an RR-client to the RR, this is 10 times improvement compare to 
2 seconds mentioned above. Of course it comes with the price in form of need 
for mechanism to communicate next-hops between clients and RR, but this 
shouldn't be a big deal. If there is interest in this approach, we could 
discuss details.

Kind regards,
iLya

--------------------------------------------------
From: "Robert Raszuk" <[email-masked]>
Sent: Wednesday, October 20, 2010 7:05 PM
To: <[email-masked]>
Subject: [Idr] Fwd: 
I-DAction:draft-raszuk-bgp-optimal-route-reflection-00.txt

> _______________________________________________
> Idr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/idr
>

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 21 Oct 2010 01:54:12 -0700

Hi iLya,

First many thx for your comment.

> while I like the vector of the solutions proposed by the draft, there
> are couple problems that will arise when network topology changes (e.g.
> due to a link or a node failure).

Right here we need to make sure that our assumptions as to the network 
topology match as well as to the network optimal exit convergence.

Above all is the requirement of fast connectivity restoration and this 
proposal is orthogonal to it. FCR is achieved by backup paths 
propagation to all clients ahead of any failure what in turn can be done 
with or without this proposal today with add-paths or diverse-path 
solutions. That addresses node-failure case.

This work only makes it better to the extend that your best path and 
backup path are optimal for each client as opposed to pretty much random 
today if you happen to move towards Internet-table free core and 
mpls/softwire encapsulation edge to edge.

> having measured SPF runtime myself I took what was available in the
> wild. If for 200 nodes it takes about 10ms for SPF to complete, then it
> will take 2 seconds before RR starts best path selection calculations
> for the 200th RR-client.

One point is that this is ok. When next hop is down clients will notice 
this event from IGP flooding and will switch in 10s of ms and in prefix 
independent way to a backup exit point. Users will not even notice any 
event and in the mean time BGP can take 2-5-10 s to make it again an 
optimal true hot potato exit point and backup exit point. Next hop 
tracking is your friend here.

Today both best path and backup path is send from the IGP point of the 
route reflector or in some implementations by fully ignoring IGP 
position so it is hardly possible to argue how this would be any more 
optimal to both best and backup paths :).

Now 10 ms for 200 node network is the full wide SPF. In most cases we 
are focusing on single failure in the entire domain at any given time so 
it is very likely that partial SPF or incremental SPF can significantly 
bring this time down. Also please do keep in mind that this 10 ms for 
200 full spf number is for not so modern CPUs.

Also nowhere we state that RR needs to complete SPF for all clients then 
start the best path. In most of the modern operating systems this task 
will be parallel to running best path selection as well as to the actual 
advertisement.

So the bottom line and clearly a good network design practice today 
irrespective of this draft is to have a backup paths distributed to the 
clients ahead of any failures. This draft just adds an ability to have 
those optimized for each of the client.

> For angular distance in section 4 dynamic changes in the network seem to
> be even harder challenge - in case of link failure angular distance
> remains the same while best next hop may change.

In case of angular distance IGP link metric does not matter. This is 
proposed on purpose and this is why angular metric solution requires end 
to end encapsulation of traffic. For good or for bad this way of core 
network design is coming. Again this is an approximation. But as it 
turns out such approximation is good enough for a lot of small/mid size 
networks.

In practice many operators expressed interest of only POP to POP hot 
potato routing - not client per client - due to intra POP symmtry. If 
links fail in the core temporary (few seconds) suboptimal exit points 
are just fine.

> unordered set available next-hops

The draft is very clear that if you have add-paths ALL-PATHs option to 
propagate to all clients enabled then there is no need for anything 
else. Also there is no need to get those paths back to the RRs. Remember 
- RRs are control plane only.

But based on the real feedback clients usually are fine with 2 BGP paths 
to satisfy all of modern service requirements. Hence pushing to all of 
them all BGP paths is just an unnecessary architectural overkill.

This draft proposed a way to propagate to clients only the optimal best 
and backup paths.

Best regards,
R.

---

From: "iLya" <[email-masked]>
Date: Thu, 21 Oct 2010 11:37:59 +0200

--------------------------------------------------
From: "Robert Raszuk" <[email-masked]>
Sent: Thursday, October 21, 2010 10:54 AM
To: "iLya" <[email-masked]>
Cc: <[email-masked]>
Subject: Re: [Idr] Fwd: 
I-DAction:draft-raszuk-bgp-optimal-route-reflection-00.txt

> network design is coming. Again this is an approximation. But as it turns 
> out such approximation is good enough for a lot of small/mid size 
> networks.
>

Doesn't angular distance depends on topology because it's just an 
f(IGP_cost)? If topology changes, then relative position of the nodes on the 
circle will change as well, and this why I compared it with IGP cost change.

> propagate to all clients enabled then there is no need for anything else. 
> Also there is no need to get those paths back to the RRs. Remember - RRs 
> are control plane only.
>

Sending multiple path's requires more resources. There are contemporary 
systems (in big quantities) which perform good in forwarding plane but are 
quite slow in the control plane. Exchanging only next-hops rather than 
pushing 2 or three path's may be more efficient for such systems.

Additionally, I forgot to mention in my previous mail, that IGP-based 
solution works only when you have IGP end-to-end. This won't do much for 
Inter-AS MPLS (e.g. BGP confederation) where next-hops are exchanged via 
BGP. For this case exchanging next-hop sets (unordered from RR, ordered from 
RR-c) may be the only solution.

Kind regards,
iLya

---

From: Jie Dong <[email-masked]>
Date: Thu, 21 Oct 2010 17:56:31 +0800

Hi Robert,

One quick comment on algorithm 1 (Client's perspective SPF): does it work in
hierarchical route reflection? 

The top-layer RR runs SPF from its client's perspective, and advertise the
"best path" to that client, which is the lower-layer RR for some other
clients. In this case these clients may not receive "the best path" from
their perspective.

Best regards,
Jie

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Robert Raszuk
> Sent: Thursday, October 21, 2010 1:06 AM
> To: [email-masked]
> Subject: [Idr] Fwd: I-D
Action:draft-raszuk-bgp-optimal-route-reflection-00.txt
directories.
> [RFC4456] asserts that, because the Interior Gateway Protocol (IGP) cost
to a
> given point in the network will vary across routers, "the route reflection
> approach may not yield the same route selection result as that of the full
> IBGP mesh approach."  One practical implication of this assertion is that
the
> deployment of route reflection may thwart the ability to achieve hot
potato
> routing.  Hot potato routing attempts to direct traffic to the closest AS
> egress point in cases where no higher priority policy dictates otherwise.
> As a consequence of the route reflection method, the choice of exit point
for
> a route reflector and its clients will be the egress point closest to the
route
> reflector - and not necessarily closest to the RR clients.
> 
> constraints which, if satsified, would result in the deployment of route
> reflection yielding the same results as the iBGP full mesh approach.  Such
a
> deployment approach would make route reflection compatible with the
> application of hot potato routing policy.
> 
Section
> 11 of [RFC4456].  Yet, in such an environment, hot potato routing policy
> remains desirable.
> 
> facilitate the application of closest exit point policy centralized route
> reflection deployments.
> 
http://www.ietf.org/internet-drafts/draft-raszuk-bgp-optimal-route-reflectio
> n-00.txt

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 21 Oct 2010 07:03:45 -0700

Hello Jie,

Yes it does work for distributed RRs as well as RRs interconnected in 
hierarchy. The draft is pretty clear in defining that between RRs you 
are to exchange all paths. So in your example to RR in top hierarchy 
would propagate all paths to all of it's peer RRs without making any 
best path selection. Only those RRs serving end clients would perform 
customized best path selection.

But let's not loose big picture here. The work is for centralized 
control plane RRs architectures where I do not think a need for RR 
hierarchy really applies.

Cheers,
R.

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 21 Oct 2010 07:14:02 -0700

Hi iLya,

> f(IGP_cost)? If topology changes, then relative position of the nodes on
> the circle will change as well, and this why I compared it with IGP cost
> change.

Nope it does not. It is a proposal to map statically your PEs/ASBRs onto 
a circle to make sure that clients located in close geo-locations would 
not be send exit paths from the other side of the continent.

As it does not depend on IGP it does require end to end network 
encapsulation otherwise clearly loops would form.

> BGP. For this case exchanging next-hop sets (unordered from RR, ordered
> from RR-c) may be the only solution.

Ilya - when we have discussed various options for encoding add-paths 
sending just next hops was clearly considered. If I understand what you 
are proposing is for RR to send set of next hops for a given prefix to 
client, let the client select the optimal one and order them, return it 
to RR then from RR send the rest of the attributes for such next hop's 
path. Is this the case ?

Where you not talking about delays associated with reacting to network 
topology changes events ?

If so I am not sure I see much value in this transactional exchange 
rather then just send all paths to all clients which is clearly an 
alternative design option to this proposal. But this does increase BGP 
state in the entire network significantly and without much reason. For 
most of the applications two or maybe perhaps three paths are needed out 
of on average 10-15 in the SP networks.

Cheers,
R.

---

From: "iLya" <[email-masked]>
Date: Thu, 21 Oct 2010 17:48:21 +0200

> Nope it does not. It is a proposal to map statically your PEs/ASBRs onto a 
> circle to make sure that clients located in close geo-locations would not 
> be send exit paths from the other side of the continent.
>

[R1]------50ms---[R2]
 |                |
5ms               |
 |                |
[R3]              |
 |                |
5ms               |
 |                |
[R4]--------------+

>From R1 perspective angular distance to R3 is less than to R4 which in turn 
is less than to R2 (other side of continent). Based on angular distance and 
desire to send best and next routes RR will send to RR1 two routes - one via 
R3 and one via R4. When link R1-R3 fails angular distance from R1 to other 
three routers changes because now R2 is much close. Or what will make RR to 
send routes via R2 and R4 to R1 after link failure?

> client, let the client select the optimal one and order them, return it to 
> RR then from RR send the rest of the attributes for such next hop's path. 
> Is this the case ?
>

No, I ment something different in the current context. Imagine there is a 
new AFI called "NHv4", which RR and RR-c exchange. When this sessions 
between RR and RR-c first comes up RR sends all (for all prefixes) v4 
next-hops that it knows (won't be too many) to RR-c via AFI NHv4 with cost 
MAX_COST. RR-c returns the same set but now with associated cost. When RR 
needs to send a prefix in any other AFI it first consults NH preference 
table for given client. If client detects change in cost to a known 
next-hop, it sends AFI NHv4 update to RR with new cost for that next-hop. If 
RR detects that some NH is no longer used for any prefix sends WITHDRAW to 
RR-c for that next-hop (and potentially new set of prefixes in other AFI). 
If new next-hop becomes know to RR, RR informs RR-c about it, to which RR-c 
replies with cost to that next-hop. Conversation in AFI NHv4 is not expected 
to be very chatty. Benefit vs 'virtually placing RR as SPT root' is that a) 
SPF calculations are offloaded from RR, b) works for inter-area/level, c) 
has potential working with inter-AS (inter-RR)

> topology changes events ?

in context of add-path? can't say for sure whether I was involved, but I 
would have probably supported that PoV :-) what I'm proposing here is 
slightly different.

> If so I am not sure I see much value in this transactional exchange rather 
> then just send all paths to all clients which is clearly an alternative 
> design option to this proposal. But this does increase BGP state in the 
> entire network significantly and without much reason. For most of the 
> applications two or maybe perhaps three paths are needed out of on average 
> 10-15 in the SP networks.
>

In general I like the idea of 'virtual placing' as long as it's clear that 
SPF calculation can be done in short time and has better than linear 
dependancy on number of nodes and links. But please also consider inter-area 
and inter-AS cases.

Kind regards,
iLya

---

From: "Robert Raszuk (raszuk)" <[email-masked]>
Date: Thu, 21 Oct 2010 11:09:19 -0700

Hi Ilia, 

I do like your proposal for new safi to ask clients to provide metrics to next hops. If you would like please write it up and I will be very happy to add it to the draft as an option of metric calculations.

Many thx,
R.

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 21 Oct 2010 12:53:17 -0700

Hi iLya,

Let me answer those two other questions you have posted.

> is less than to R2 (other side of continent). Based on angular distance
> and desire to send best and next routes RR will send to RR1 two routes -
> one via R3 and one via R4. When link R1-R3 fails angular distance from
> R1 to other three routers changes because now R2 is much close. Or what
> will make RR to send routes via R2 and R4 to R1 after link failure?

Nothing. Static allocation of this distance to clients is proposed to 
work in practice on group of nodes basis. For example if you have 10 
POPs each with 10 routers you may assign same metric to each of the 
router in the POP and relative circle mapped metric to other POPs. As 
POPs are usually well connected to the core of the network single 
failure of a link will not result in any bad effects and in particular 
will not result in the any worse case then we have total randomness in 
the centralized control plane RRs.

Of course the drawback of manual mapping is that any permanent major 
network topology change requires the update of the metric matrix.

I think that it may be pretty hard to satisfy all requirements. That's 
why I am all for providing a set of choices on how metric between 
clients and next hops are provided and let operator to choose a way he 
considers the most optimal for his network topology.

> In general I like the idea of 'virtual placing' as long as it's clear
> that SPF calculation can be done in short time and has better than
> linear dependancy on number of nodes and links. But please also consider
> inter-area and inter-AS cases.

Seems like we agree completely here. As mentioned in the other email I 
like your proposal mostly from the point of very good accuracy for 
hierarchical IGPs.

For flat IGPs I think option 1 in the draft seems much more elegant as 
such RR would already have all required information in place.

On the other hand reg your inter-as case(s) perhaps you could on the 
list or offline comment what are those cases as to me really comes only 
one - 2547 option C with same RD VRFs - for good or for bad a little bit 
of corner case I would say :) Otherwise I don't see how per client path 
on RRs may help those EBGP sessions.

Cheers and many thx for the comments,
R.

---

From: Aleksi Suhonen <[email-masked]>
Date: Fri, 29 Oct 2010 11:20:20 +0000

> will take 2 seconds before RR starts best path selection calculations

This is an implementation issue. There are algorithms out there that are 
much better than SPF for many-to-many-best-path-selection.

Besides, I thought running SPF a lot was a non-issue, Ilya. ;-)

> remains the same while best next hop may change.

My 2 cents: I don't feel the angular distance proposal would be very 
useful in the real world, where networks can be very very two dimensional.

-- 
	Aleksi Suhonen, Researcher
	Department of Communications Engineering
	Tampere University of Technology

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 29 Oct 2010 15:18:49 +0200

Hi Aleksi,

Many thx for your comments.

 > This is an implementation issue. There are algorithms out there
 > that are much better than SPF for many-to-many-best-path-selection.

If you don't mind providing some links to read about them would be of 
great help. Perhaps we could include them into the draft as references.

 > Besides, I thought running SPF a lot was a non-issue, Ilya. ;-)

Yes I don't think anyone really claims that that is an issue. But keep 
in mind that closest exit just from IGP metric point of view is already 
today not sufficient. End to end encapsulation opens a wide range of 
ability to specify different exit preferences for transit traffic within 
your network. And one of the goals of this draft is to enable those new 
preferences to become useful and deployed.

 > useful in the real world, where networks can be very very two

Clearly it is not designed to address all types of networks. But my 
primary objective was to provide a pop to pop granularity where 
essentially a group of routers would carry a metric which in turn could 
be relative to other groups of routers in calculation of less then 
random optimal exit point.

But at this point this is just one section in the draft seeking for a 
feedback/improvements. And clearly if there is no substantial support we 
can easily remove it in next revision.

Cheers,
R.