Subject: [Idr] AS_SET depreciation (RFC6472) and BGP multipath

From: Robert Raszuk <[email-masked]>
Date: Tue, 27 Mar 2012 21:35:11 +0200

/In the light of just reissued draft-ietf-idr-bgp-issues-06)/

Hi,

As number of BGP implementations allow for configuration of i/eBGP 
multipath across paths which do not have identical AS_PATH I would like 
to ask the list what people think is the right current BGP protocol 
behaviour when advertising best multipath path out ?

During discussions of RFC6472 I recall a bit of discussion there on this 
topic, but no conclusion reached.

http://www.ietf.org/mail-archive/web/idr/current/msg04512.html

On the other hand 
http://tools.ietf.org/html/draft-ietf-idr-bgp-issues-06 in section 
"2.11.3. Documenting IBGP Multipath" says:

    If in EBGP multipath traffic is split among routers in difference AS,
    an aggregate SHOULD be formed so as to propagate a route with an
    accurate AS_PATH.  If the resulting aggregate is not more specific
    than the components, the AS_SET SHOULD NOT be dropped.

The question is what an implementation of BGP today should do when 
multipath is enabled, AS_SET is recommended for depreciation and no new 
alternative is even proposed to protect against potential loops ?

Options seems to be:

* Do nothing .. trust that whoever enables multipath across non 
identical AS_PATHs is a non-transit/stub AS and no loop will happen (ios 
approach)

* Continue to call as_aggregate and still generate AS_SET effectively 
depreciating RFC6472 (quagga approach)

* Propose an alternative encoding to address this case specifically for 
multipath use cases, but till this is deployed continue use AS_SET

* Remove all knobs from shipping BGP implementations and forbid to use 
paths with different AS_PATH for multipath (junos approach).

Regards,
R.

---

From: Tony Li <[email-masked]>
Date: Tue, 27 Mar 2012 13:16:47 -0700

On Mar 27, 2012, at 12:35 PM, Robert Raszuk wrote:

> Options seems to be:
> 
> * Do nothing .. trust that whoever enables multipath across non identical AS_PATHs is a non-transit/stub AS and no loop will happen (ios approach)
> 
> * Continue to call as_aggregate and still generate AS_SET effectively depreciating RFC6472 (quagga approach)
> 
> * Propose an alternative encoding to address this case specifically for multipath use cases, but till this is deployed continue use AS_SET
> 
> * Remove all knobs from shipping BGP implementations and forbid to use paths with different AS_PATH for multipath (junos approach).

Another option might be to simply concatenate AS_PATHs.  Yes, this would lose policy information and mis-represent AS topology to management stations and the like, but it would not create any risk of looping and would not require us to reinstitute AS_SET.

Tony

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 27 Mar 2012 22:57:04 +0200

Hi Tony,

>> * Propose an alternative encoding to address this case specifically
>> for multipath use cases, but till this is deployed continue use
>> AS_SET
>
> Another option might be to simply concatenate AS_PATHs.  Yes, this
> would lose policy information and mis-represent AS topology to
> management stations and the like, but it would not create any risk of
> looping and would not require us to reinstitute AS_SET.

Very true. However I am not sure how that would be effectively that much 
different SIDR wise from issue with AS_SET ;)

Said this are there any other issues with AS_SET then SIDR ?

R.

---

From: Jakob Heitz <[email-masked]>
Date: Tue, 27 Mar 2012 19:22:09 -0400

SIDR wise, to aggregate routes, you would have to
aggregate signatures. That means to put both signatures
into the aggregate and sign across the pair of them
at each subsequent hop. yuck.

Alternatively, send both routes and let the end
user decide to use them in a multipath.
Can you say ebgp add-path?

--
Jakob Heitz.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Robert Raszuk
Sent: Tuesday, March 27, 2012 1:57 PM
To: Tony Li
Cc: [email-masked] List
Subject: Re: [Idr] AS_SET depreciation (RFC6472) and BGP multipath

Hi Tony,

R.

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

---

From: Paul Jakma <[email-masked]>
Date: Wed, 28 Mar 2012 14:10:04 +0100 (BST)

On Tue, 27 Mar 2012, Jakob Heitz wrote:

> Alternatively, send both routes and let the end user decide to use them 
> in a multipath. Can you say ebgp add-path?

Where's the document to describe how to do multi-pathing using add-path? 
E.g. what should happen when there is a non-add-path capable neighbour?

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
The Second Law of Thermodynamics:
 	If you think things are in a mess now, just wait!
 		-- Jim Warner

---

From: Jakob Heitz <[email-masked]>
Date: Wed, 28 Mar 2012 10:11:20 -0400

I don't know. I'm just throwing ideas around.
However, it appears that inter AS multipath
has a lot of problems.

--
Jakob Heitz.

-----Original Message-----
From: Paul Jakma [mailto:[email-masked]] 
Sent: Wednesday, March 28, 2012 6:10 AM
To: Jakob Heitz
Cc: [email-masked]; Tony Li; [email-masked] List; sidr wg list
Subject: Re: [sidr] [Idr] AS_SET depreciation (RFC6472) and BGP multipath

regards,

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 16:32:01 +0200

Jakob,

The issue is also about intra-as ibgp multipath not inter-as one. Observe that data usually flows into opposite direction then routing ;)

Cheers,
R.

---

From: Jakob Heitz <[email-masked]>
Date: Wed, 28 Mar 2012 10:56:52 -0400

The issue is SIDR can not aggregate multiple paths.

Solutions I can think of:
1. Aggregate the signatures of the paths being aggregated.
2. Don't aggregate, but send both paths. 

Should SIDR work on path aggregation?
Are there other possibilities?

--
Jakob Heitz.

-----Original Message-----
From: Robert Raszuk [mailto:[email-masked]] 
Sent: Wednesday, March 28, 2012 7:32 AM
To: Jakob Heitz
Cc: Paul Jakma; [email-masked] List; Tony Li; sidr wg list
Subject: Re: [Idr] [sidr] AS_SET depreciation (RFC6472) and BGP multipath

Jakob,

Cheers,
R.

---

From: Paul Jakma <[email-masked]>
Date: Wed, 28 Mar 2012 17:01:18 +0100 (BST)

> Should SIDR work on path aggregation?

If we ever want to make routing state scale sub-linearly (i.e. make IDR 
"compact") in the size of the internet, then we're almost certainly going 
to need some form of conglomeration of routing information in some shape 
or form. Still having support for aggregation in BGP could then be useful.

It'd be a shame if we ended up having to choose between scalable and 
secure routing.

(OTOH scalable routing is potentially so far off in the future, and might 
be so different, that it's hard to say what level of extra engineering or 
overhead, if any would be justified for SIDR).

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
COBOL:
 	Completely Over and Beyond reason Or Logic.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 28 Mar 2012 12:15:16 -0400

On Wed, Mar 28, 2012 at 12:01 PM, Paul Jakma <[email-masked]> wrote:
> "compact") in the size of the internet, then we're almost certainly going to
> need some form of conglomeration of routing information in some shape or
> form. Still having support for aggregation in BGP could then be useful.

or we could have fixed the problem with locator/id separation... oh well.

>
> It'd be a shame if we ended up having to choose between scalable and secure
> routing.

it's hardly a choice of one or the other, framing the question in this
manner is a 'suckers choice'.

<http://sourcesofinsight.com/refuse-the-suckers-choice-4/>

It's certianly possible that at some point when aggregation between
AS's becomes used properly and effectively... someone will figure out
the security properties if this configuration.

> (OTOH scalable routing is potentially so far off in the future, and might be
> so different, that it's hard to say what level of extra engineering or

it seems that to date, folk can't seem to figure out the aggregation
bits, maybe that will change in the future.

-chris

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 18:29:45 +0200

Chris,

> bits, maybe that will change in the future.

Let me point out that IBGP multipath is used very commonly today. When 
you do that you need to advertise something meaningful out to your 
neighbors. Yes that is open IDR topic no one seems to be actively 
working on. However let's not block any work on it just because SIDR can 
not handle some solutions.

Are we going to freeze any AS_PATH modifications by operator's policy 
too ? I mentioned replace-as which all major vendors support. There can 
be more knobs like this coming in the future.

CDNI is just getting extended to BGP (new SAFI) and they have their own 
uses for AS_PATH being sort of over the top of classic ASes.

Regards,
R.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 28 Mar 2012 12:38:09 -0400

On Wed, Mar 28, 2012 at 12:29 PM, Robert Raszuk <[email-masked]> wrote:

> Are we going to freeze any AS_PATH modifications by operator's policy too ?
> I mentioned replace-as which all major vendors support. There can be more
> knobs like this coming in the future.

replace as i think is dealt with .... sign again and pcount=0 and move along.

> CDNI is just getting extended to BGP (new SAFI) and they have their own uses
> for AS_PATH being sort of over the top of classic ASes.

good for them?

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 18:43:42 +0200

> replace as i think is dealt with .... sign again and pcount=0 and move along.

replace-as allows to replace any arbitrary match of list of ASes in the 
AS_PATH by your own AS. Does not need to be the last one.

I don't think SIDR has a solution to deal with such policy.

Best regards,
R.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 28 Mar 2012 12:45:22 -0400

> AS_PATH by your own AS. Does not need to be the last one.

ah yes, was thinking of local-as. the 'replace-as' seems like
loop-creation, joy.

> I don't think SIDR has a solution to deal with such policy.

nope, seems crazy though:) (to use it I mean)

---

From: heasley <[email-masked]>
Date: Wed, 28 Mar 2012 17:30:10 +0000

Wed, Mar 28, 2012 at 05:00:43PM +0000, Murphy, Sandra:
> Replacing ASs in the AS_PATH sounds like a behavior you would want the security protections to prohibit.  It would enable attacks.
> 
> Can you explain how you would distinguish legitimate uses of this feature?

I've not used this feature, but from cisco's documentation, it doesnt appear
to function as raszuk described.

http://www.cisco.com/en/US/docs/ios/12_3t/12_3t11/feature/guide/gtbgpdas.html

if local-as is configured for a peer(-group), ie: if configured to peer as
a different AS than your own, such as for merging two ASes or changing your
ASN, then:
"The replace-as keyword is used to prepend only the local autonomous-system number (as configured with the ip-address argument) to the AS_PATH attribute. The autonomous-system number from the local BGP routing process is not prepended."

though I think that is unclear, I interpret it to mean that if my ASN is 1
and, I peer as ASN 2 with ebgp peer 3, then a route received from AS 3 will
have the path [2 3], but if configured with replace-as, it will be [3].

I do not believe that the feature allows the arbitrary replacement of AS path
elements.

> --Sandy
> 
> ________________________________________
> From: [email-masked] [[email-masked]] on behalf of Robert Raszuk [[email-masked]]
> Sent: Wednesday, March 28, 2012 12:43 PM
> To: Christopher Morrow
> Cc: [email-masked] List; Paul Jakma; sidr wg list
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 22:07:10 +0200

> the 'replace-as' seems like
> loop-creation, joy.

Nope. No loops at least in one implementation ... the implementation 
mandates that you insert your own AS - that is not optional.

Rgs,
R.

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 22:23:35 +0200

> it doesnt appear to function as raszuk described.

Let me point out that heasley is looking at completely different knob 
which has nothing to do with replace as path policy extension.

The correct pointer is: http://goo.gl/xVToJ

Rgs,
R.

---

From: Brian Dickson <[email-masked]>
Date: Wed, 28 Mar 2012 16:25:06 -0400

Arbitrary AS substitution allows loop creation, even if your own AS is
required.

All that is needed, is multiple instances of replace-as in the loop.

Suppose A replaces B C D with A E F.

Suppose B replaces G A with B C D.

A received B C D, sends A E F to G.

G sends G A E F to B.
B sends B C D E F to A.

We have a loop, which eventually results in path overflow with E F E F E F
etc. at the end of it.

On Wed, Mar 28, 2012 at 4:07 PM, Robert Raszuk <[email-masked]> wrote:

> ______________________________**_________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/sidr<https://www.ietf.org/mailman/listinfo/sidr>
>

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 22:30:21 +0200

Brian,

The customer's workaround was to erase entire AS_PATH via 
redistribution. I am not saying that use of this knob is safe.

I am saying that it exists in shipping implementations and simply asking 
what SIDR behaviour should be when such policy is present.

That's all.

Best,
R.

> We have a loop, which eventually results in path overflow with E F E F E
> F etc. at the end of it.
>
> On Wed, Mar 28, 2012 at 4:07 PM, Robert Raszuk <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>
>     _________________________________________________
>     sidr mailing list
>     [email-masked] <mailto:[email-masked]>
>     https://www.ietf.org/mailman/__listinfo/sidr
>     <https://www.ietf.org/mailman/listinfo/sidr>
>
>

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 28 Mar 2012 16:55:22 -0400

Chris,

> ah yes, was thinking of local-as. the 'replace-as' seems like

It can.  The use of replace-as is typically in situations where you need to
replace private AS numbers with a public number. This is typically done when
you have deployments that have a mix of private and public ASes behind a
common transit carrier and "remove-private" isn't sufficient.

The required behavior in order to avoid problems here is to make sure that
the set of ASes involved are behind that common carrier and either are not
multi-homed to the wider Internet (unlikely since they have private ASes) or
are applying appropriate AS filtering to manually suppress loops.

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 28 Mar 2012 17:03:35 -0400

On Tue, Mar 27, 2012 at 09:35:11PM +0200, Robert Raszuk wrote:
> multipath across paths which do not have identical AS_PATH I would
> like to ask the list what people think is the right current BGP
> protocol behaviour when advertising best multipath path out ?
> 
> During discussions of RFC6472 I recall a bit of discussion there on
> this topic, but no conclusion reached.
> 
> multipath is enabled, AS_SET is recommended for depreciation and no
> new alternative is even proposed to protect against potential loops
> ?
> 
> Options seems to be:
> 
> identical AS_PATHs is a non-transit/stub AS and no loop will happen
> (ios approach)
> 
> * Continue to call as_aggregate and still generate AS_SET
> effectively depreciating RFC6472 (quagga approach)

Generating sets is the safest thing to do.

> for multipath use cases, but till this is deployed continue use

The likely alternative would be a set of vectors of paths. This would be a
massively different AS_PATH and would have significant deployment issues.
E.g.:
Path A: 7 8 9 10
Path B: 4 5 9 10

Aggregated vector path:
7 8
   \
    9 10
   /
4 5

> * Remove all knobs from shipping BGP implementations and forbid to
> use paths with different AS_PATH for multipath (junos approach).

Even junos provides rope.  (As was said at the mic at some point at IETF 83,
"what's a few meters more?")

The feature is safe in cases where the receiving downstream is a
stub AS.

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 28 Mar 2012 17:05:19 -0400

Paul,

On Wed, Mar 28, 2012 at 02:10:04PM +0100, Paul Jakma wrote:
> Where's the document to describe how to do multi-pathing using
> add-path? E.g. what should happen when there is a non-add-path
> capable neighbour?

In add-path, this is no different than receiving routes from directly
attached peers.  You should either do Internet-safe multipath or do the less
safe multipath knowing that you're in a position to cause problems.

Add-path doesn't really change the basic problem of multipath.

-- Jeff

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 28 Mar 2012 23:09:08 +0200

Jeff,

> Generating sets is the safest thing to do.

Glad you said this. I do agree.

> massively different AS_PATH and would have significant deployment issues.

Indeed. Almost like you would require a new attribute for that .. 
however not clear at all how such new attribute even if defined would help.

> The feature is safe in cases where the receiving downstream is a

IBGP multipath is used quite widely. In fact as I am sure you know in 
the case you have encapsulation in the core (for example mpls LSPs) 
there are knobs to skip metric check to the next hop.

Best regards,
R.

---

From: Tony Li <[email-masked]>
Date: Wed, 28 Mar 2012 14:16:36 -0700

> Glad you said this. I do agree.

Understood, but how do you ever secure this?  Set SIDR aside for a second, what would ANY path verification mechanism have to do to secure the full path?

It would seem that the ONLY thing one could reasonably do is to describe the full topology, and that would seem to require the ability to describe an arbitrary tree, not just a set of vectors of paths.

Tony

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 28 Mar 2012 17:17:28 -0400

> 1. Aggregate the signatures of the paths being aggregated.

What are the semantics you're trying to preserve SIDR-wise?  We're hitting
the realm where Russ White would point out that BGP path validation can't
prove how forwarding works.

Presume we managed to pass along two distinct paths for the same multi-path
route in BGP.  What do you do if one doesn't validate?  What do you do if
they do, but you think this is a form of a "route leak" for one path?

As a receiver of the route that is making use of multipath, you can't
selectively choose which sub-paths to take.  (It's not like we're gettng
something like MPLS entropy labels.)

> 2. Don't aggregate, but send both paths. 

That doesn't cover the actual forwarding semantics.

> Are there other possibilities?

The biggest problem here is "SIDR secures BGP".  The issue hasn't been clear
in BGP for years, although I'm perhaps of the cynical opinion that it's been
a well understood problem space for a while now.  The protocol doesn't
reflect what is done operationally.  The safe thing operationally when
aggregating unsafe paths is to generate sets, but some people have never
liked sets.  And as I mentioned elsewhere, it doesn't matter as long as you
take care in where you redistribute such unsafe multipath.

There was a reason I wasn't terribly supportive of the deprecating AS_SETs
I-D.  However, I also knew it was a losing battle. :-)

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 28 Mar 2012 17:23:34 -0400

> ah yes, was thinking of local-as. the 'replace-as' seems like

For the list, as I mentioned in SIDR, the use of local-AS where the router
has more than one local AS will generate AS_SETs in some implementations.
In particular, implementations with gated lineages may do this.

This is because in pretending to be another AS it's still necessary to throw
the global and local ASes in the path to prevent loops in cases where the
local AS on one router may not be configured consistently (global) AS-wide.
In those implementations, a single AS is simply added prior to the global AS
in the path as a sequence or all local ASes as a set.

In another implementation, the local ASes are added as a sequence.

Adding the additional AS to the path would still require an additional
signature step in BGPSEC.  Clearly this doesn't work for AS-sets.

-- Jeff

---

From: Jakob Heitz <[email-masked]>
Date: Wed, 28 Mar 2012 17:57:32 -0400

This can be done.
Like I said before: aggregate the signatures of the paths being aggregated.
String all the signed paths together (after wrapping them with a header), add your SKI and destination AS (as normal) and sign over the lot.

Question is: does anyone want to?

--
Jakob Heitz.

---

From: Jakob Heitz <[email-masked]>
Date: Wed, 28 Mar 2012 18:03:16 -0400

including sidr 

--
Jakob Heitz.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 28 Mar 2012 18:15:14 -0400

> what SIDR behaviour should be when such policy is present.

I guess what I wasn't saying was that not every oddball wierdness
permitted TODAY in BGP is able to be secured, or validate-able. It's
not required that this be the case actually.

-chris

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 29 Mar 2012 03:10:53 -0400

> Question is: does anyone want to?

At minimum, this would further decouple the signature from the actual path.

And given multipath covers *many* routes, the result would likely be
unwieldy.

-- Jeff

---

From: Jakob Heitz <[email-masked]>
Date: Thu, 29 Mar 2012 03:38:00 -0400

of course, we would need to reinvent the AS_SET to go along with it, but this time, enumerating each exact path.

Definitely unwieldy.

--
Jakob Heitz.

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 29 Mar 2012 04:21:03 -0400

Sandy,

> Can you explain how you would distinguish legitimate uses of this feature?

The feature is typically used on private AS numbers.

One could point out that any procedures dealing with them are probably out
of scope of SIDR. :-)

-- Jeff

---

From: "Susan Hares" <[email-masked]>
Date: Thu, 29 Mar 2012 05:29:26 -0400

Jeff and Jakob:

Several people shared the qualm that "AS-SETS" would be necessary.  

However, Sandy has always posited that aggregation creates a point of
change/risk. So, are we just trying to reduce this risk by providing lists
of certificates for paths? 

Or is would an AS-Sets originated at a point in the network - have the
security information to consider the existing certificates and generate a
valid certificate.

Sue 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Jeffrey Haas
Sent: Wednesday, March 28, 2012 5:17 PM
To: Jakob Heitz
Cc: [email-masked] List; Tony Li; Paul Jakma; Robert Raszuk; sidr wg list
Subject: Re: [Idr] [sidr] AS_SET depreciation (RFC6472) and BGP multipath

-- Jeff

---

From: "Murphy, Sandra" <[email-masked]>
Date: Wed, 28 Mar 2012 17:00:43 +0000

--Sandy

Best regards,
R.

---

From: Paul Jakma <[email-masked]>
Date: Fri, 30 Mar 2012 10:39:48 +0100 (BST)

On Wed, 28 Mar 2012, Tony Li wrote:

> Understood, but how do you ever secure this?  Set SIDR aside for a 
> second, what would ANY path verification mechanism have to do to secure 
> the full path?

> It would seem that the ONLY thing one could reasonably do is to describe 
> the full topology, and that would seem to require the ability to 
> describe an arbitrary tree, not just a set of vectors of paths.

Compact routing schemes in the future might also want to be able to 
collect together and summarise parts of the network in some way.

Figuring out how to achieve *both* scalable and secure routing would be a 
nice research topic.

regards,
-- 
Paul Jakma  [email-masked]  twitter: @pjakma  PGP: 64A2FF6A
Fortune:
The more you sweat in peace, the less you bleed in war.