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

From: Aleksi Suhonen <[email-masked]>
Date: Mon, 01 Nov 2010 11:00:34 +0200

On 10/29/10 16:18, Robert Raszuk wrote:
>  > 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.

A quick browse through Wikipedia produced the following examples:

http://en.wikipedia.org/wiki/Johnson%27s_algorithm
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf

(And the references on those articles looked like good reading to me.)

I think I have one dissertation at home which also mentions some 
algorithms for this.

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

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 01 Nov 2010 11:13:47 +0100

Hi Aleksi,

Thank you for the provided pointers. Especially the last pdf document is 
excellent in comparing many algorithms as well as number of Dijkstra's 
flavors.

However in number of networks IGP shortest path to the exit may not 
always be the main desired factor to consider while selecting BGP path 
as best/N-th best. Often external and not visible in the IGP parameters 
may take precedence over IGP metric to next hop distance.

While today accomplishing it is quite hard in practice the new area of 
work I am trying to start is also targeted to open such possibilities. 
As example to achieve such flexible way of best path selection number of 
ISPs is twicking IGP link metrics which is usually non a trivial exercise.

Neverless the IGP metric will likely still remain a factor and using 
some of the described below alternatives may turn as very good optimization.

Many thx,
R.

---

From: Pierre Francois <[email-masked]>
Date: Thu, 11 Nov 2010 07:43:18 +0100

Robert,

You received a comment stating that Add-All-Paths was maybe not necessary
to do optimal route reflection in Add-paths.

This is indeed true.
As per draft-uttaro-idr-add-paths-guidelines-03, there are a bunch of proposals
that advertise less paths and provide optimal route reflection.

Regards,

Pierre.

On 20/10/10 19:05, Robert Raszuk wrote:
> 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.
>
>
>
> _______________________________________________
> Idr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/idr

---

From: "Robert Raszuk (raszuk)" <[email-masked]>
Date: Thu, 11 Nov 2010 14:58:07 +0800

Hi Pierre,

How those paths selłected as N if N is less then all are guaranteed to be optimal for the client in the scenario of RRs not being in topological forwarding paths in the front of the client.

Imagine you have 10 exit paths and N is 3. RRs are in the core. How those N selected in any selection mode will be optimal for all clients ... I do not see this.

I do not see at all happening in the guidelines draft.

Many thx,
R.

---

From: Uli Bornhauser <[email-masked]>
Date: Thu, 11 Nov 2010 08:29:28 +0100

Hi Robert,

I read the draft again, and believe that Pierre refers to the following statement in the draft:

   One possible valid solution or workaround to this problem requires
   sending all domain external paths from the RR to all its clients.
   [...]
   In practical terms, add/
   diverse path deployments are expected to result in the distribution
   of 2, 3 or n (where n is a small number) 'good' paths rather than all
   domain external paths.  While the route reflector chooses one set of
   n paths and distributes those same n paths to all its route reflector
   clients, those n paths may not be the right n paths for all clients.
   In the context of the problem described above, those n paths will not
   necessarily include the closest egress point out of the network for
   each route reflector client.

If you think of N as a static value I think you, Robert, are indeed right. It is very easy to construct examples where a Core Route Reflector has to provide a set of N+1 "static" paths (the same paths for all clients) to its clients.
However, if you think of n as a dynamic value, different solutions are possible where less than all static paths are necessary. One simple example would be to advertise all paths with highest Loc_Pref, shortest AS-path length, and lowest MED for the corresponding peer-AS group. In general, this covers less than all paths.

Please correct me if there is any misunderstanding on my side!

Regards

Uli 

-- 
_______________________________________________________
ULI BORNHAUSER
University of Bonn - Institute of Computer Science 4
c/o Bonn-Aachen International Center for Information Technology B-IT 
Dahlmannstr. 2 - D-53113 Bonn - Germany

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

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 11 Nov 2010 09:09:17 +0100

Hi Uli,

 > If you think of N as a static value I think you, Robert, are indeed
 > right. It is very easy to construct examples where a Core Route
 > Reflector has to provide a set of N+1 "static" paths (the same paths
 > for all clients) to its clients.

Yes you have summarized this in an excellent way.

But I am working on the ISPs requirement assumption where:

Case A) they have no network wide policies and AS_PATHs lengths are 
equal which in this case the tie break is the IGP metric to the next hop 
on the RRs for vast majority of paths

Case B) their network exit policy does not need to be uniform and 
identical for all RR clients.

With this in mind I really do not see how add-paths "All AS-Wide Best 
Paths" option or any other add-paths advertisement option which is less 
then ALL to all clients would address their requirements.

Many thx,
R.

> If you think of N as a static value I think you, Robert, are indeed
> right. It is very easy to construct examples where a Core Route
> Reflector has to provide a set of N+1 "static" paths (the same paths
> for all clients) to its clients. However, if you think of n as a
> dynamic value, different solutions are possible where less than all
> static paths are necessary. One simple example would be to advertise
> all paths with highest Loc_Pref, shortest AS-path length, and lowest
> MED for the corresponding peer-AS group. In general, this covers less
> than all paths.
>

---

From: Pierre Francois <[email-masked]>
Date: Thu, 11 Nov 2010 09:49:56 +0100

Robert,

I get your point.

Add-All-paths advertises *all* paths, but the Add-AS-Wide best paths mode for 
example only advertises the ones who made it to the IGP tie-break,
and provides "optimal reflection".

This is not all paths, unless of course in the particular case where you have 
same Local pref, AS Path length, and MED for all the paths available at your 
borders.

So there is a worst case where you would need to advertise the same set of paths 
as the add-all, but you don't need to turn add-all on to obtain optimal reflection.

Regards,

Pierre.

On 11/11/10 07:58, Robert Raszuk (raszuk) wrote:
> Hi Pierre,
>
> How those paths selłected as N if N is less then all are guaranteed to be optimal for the client in the scenario of RRs
> not being in topological forwarding paths in the front of the client.
>
> Imagine you have 10 exit paths and N is 3. RRs are in the core. How those N selected in any selection mode will be optimal for all clients... I do not see this.
>

>
> Many thx,
> R.
>
> On Nov 11, 2010, at 2:43 PM, "Pierre Francois"<[email-masked]>  wrote:
>
>>
>> Robert,
>>

---

From: Pierre Francois <[email-masked]>
Date: Thu, 11 Nov 2010 09:55:01 +0100

Robert,

Haaa okay I missed the requirements depicted in your case A.

Regards,

Pierre.

On 11/11/10 09:09, Robert Raszuk wrote:
> Case A) they have no network wide policies and AS_PATHs lengths are equal which
> in this case the tie break is the IGP metric to the next hop on the RRs for vast
> majority of paths
>
> Case B) their network exit policy does not need to be uniform and identical for
> all RR clients.
>
> With this in mind I really do not see how add-paths "All AS-Wide Best Paths"
> option or any other add-paths advertisement option which is less then ALL to all
> clients would address their requirements.
>
> Many thx,
> R.
>
>

---

From: Uli Bornhauser <[email-masked]>
Date: Thu, 11 Nov 2010 13:39:46 +0100

Hi Robert,

>> in this case the tie break is the IGP metric to the next hop on the RRs for vast

yep, under this assumption you are of course right. Thanks for the details!

Regards

Uli