Subject: [Idr] FW: I-D ACTION:draft-bhatia-ecmp-routes-in-bgp-01.txt

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 8 Sep 2004 10:17:51 +0530

Hi,

This is the revised draft that was presented in 57th IETF. We would like
this draft to be discussed in the IDR WG to see if it's a sensible work item
for this working group.

Thanks,
Manav

----- Original Message ----- 
From: <[email-masked]>
To: <[email-masked]>
Sent: Wednesday, September 08, 2004 1:26 AM
Subject: I-D ACTION:draft-bhatia-ecmp-routes-in-bgp-01.txt

>A New Internet-Draft is available from the on-line Internet-Drafts
directories.
> 
> 
> Title : Advertising Equal Cost MultiPath routes in BGP
> Author(s) : M. Bhatia,  J. Halpern
> Filename : draft-bhatia-ecmp-routes-in-bgp-01.txt
> Pages : 18
> Date : 2004-9-7
> 
> This document describes an extensible mechanism that will allow a BGP 
>   [BGP4] speaker to advertise equal cost multiple BGP routes for a 
>   destination to its peers. A new BGP capability [BGP-CAP], termed   
>   "Equal Cost Multipath Capability", is defined, which would allow a 
>   local BGP speaker to express its ability to support advertisement of    
>   such multiple paths to its peers.
> 
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-bhatia-ecmp-routes-in-bgp-01.txt
> 
> To remove yourself from the I-D Announcement list, send a message to 
> [email-masked] with the word unsubscribe in the body of the
message.  
> You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce 
> to change your subscription settings.
> 
> 
> Internet-Drafts are also available by anonymous FTP. Login with the
username
> "anonymous" and a password of your e-mail address. After logging in,
> type "cd internet-drafts" and then
> "get draft-bhatia-ecmp-routes-in-bgp-01.txt".
> 
> A list of Internet-Drafts directories can be found in
> http://www.ietf.org/shadow.html 
> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt
> 
> 
> Internet-Drafts can also be obtained by e-mail.
> 
> Send a message to:
> [email-masked].
> In the body type:
> "FILE /internet-drafts/draft-bhatia-ecmp-routes-in-bgp-01.txt".
> 
> NOTE: The mail server at ietf.org can return the document in
> MIME-encoded form by using the "mpack" utility.  To use this
> feature, insert the command "ENCODING mime" before the "FILE"
> command.  To decode the response(s), you will need "munpack" or
> a MIME-compliant mail reader.  Different MIME-compliant mail readers
> exhibit different behavior, especially when dealing with
> "multipart" MIME messages (i.e. documents which have been split
> up into multiple messages), so check your local documentation on
> how to manipulate these messages.
> 
> 
> 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://www1.ietf.org/mailman/listinfo/idr

---

From: Jeffrey Haas <[email-masked]>
Date: Mon, 20 Sep 2004 16:34:51 -0400

Manav,

> this draft to be discussed in the IDR WG to see if it's a sensible work item

I have some concerns about this draft.

MP-BGP encoding issues:
RFC 2858 documents the MP-BGP format.  While I'm not aware of any
implementations that do this, one valid interpretation of RFC 2858
is that it is legal to encode IPv4 unicast data both within the
original BGP NLRI fields and the NEXT_HOP path attribute simultaneously
with the information in the MP_(UN)REACH_NLRI fields and have
the information be different.

Aside from the somewhat contrived issue above, could you clarify
the behavior for MP-BGP processing for the MP nexthop?  What I
would suspect from reading this document is that when the MP nexthop
is specified (length of nexthop != 0) that it should also behave
as an implicit withdrawal of the ECMP paths.  It's somewhat unclear
whether a length of zero in the MP nexthop case is the proper
mechanism.

I would suggest some additional language noting that the implicit 
withdrawal case (advertise a withdrawal and new NLRI simultaneously)
should be processed as just implicit withdrawals.  This may cause
churn in some implementations that may process the unfeasible routes
component of an update and then the feasible routes separately.

Similarly, this would suggest that implementations will need to
carry MP_REACH_NLRI and MP_UNREACH_NLRI simultaneously.  Some
implementations do not appear to do this currently.

Interactions with RFC 3107 Sect. 4, if any,  would be good to have
in this document.

I'm most concerned about the synthesized AS_PATH.
 o In some circumstances, particularly with large AS_SETs, it will not
   be possible to preserve path length.
 o Processing ECMP routes into paths of equivalent length with many
   AS_SETs will impact AS_PATH regular expression engines.
 o The set merging rules of BGP (9.2.2.2, draft 25) can result
   in the AS_PATH being shortened.

-- 
Jeff Haas 
NextHop Technologies

---

From: Enrico Salazar <[email-masked]>
Date: Tue, 21 Sep 2004 09:17:36 -0700 (PDT)

Jeffrey,
 
It is NOT valid to encode IPv4 unicast data both within the original BGP NLRI fields and the NEXT_HOP path attribute simultaneously with the information in the MP_(UN)REACH_NLRI fields - see draft-ietf-idr-rfc2858bis-06.txt Section 6 last paragraph.
 
Enrico.

Jeffrey Haas <[email-masked]> wrote:Manav,

MP-BGP encoding issues:

-- 
Jeff Haas 
NextHop Technologies

		
---------------------------------
Do you Yahoo!?
vote.yahoo.com - Register online to vote today!

---

From: Jeffrey Haas <[email-masked]>
Date: Tue, 21 Sep 2004 13:04:14 -0400

Enrico,

> It is NOT valid to encode IPv4 unicast data both within the original BGP NLRI fields and the NEXT_HOP path attribute simultaneously with the information in the MP_(UN)REACH_NLRI fields - see draft-…

If you are referring to the following:

:   An UPDATE message that contains the MP_UNREACH_NLRI is not required
:   to carry any other path attributes.

This is considerably different than SHALL NOT or MUST NOT.

This caveat in 2858-bis is present to make it allowable to send
an UPDATE message with just a single path attribute, which would be
illegal under draft-25 style BGP-4 since it is missing mandatory
path attributes.

This doesn't preclude sending other reachability or non-reachability.

-- 
Jeff Haas 
NextHop Technologies

---

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 22 Sep 2004 15:05:50 +0530

Jeff,

]MP-BGP encoding issues:
]RFC 2858 documents the MP-BGP format.  While I'm not aware of 
]any implementations that do this, one valid interpretation of 
]RFC 2858 is that it is legal to encode IPv4 unicast data both 
]within the original BGP NLRI fields and the NEXT_HOP path 
]attribute simultaneously with the information in the 
]MP_(UN)REACH_NLRI fields and have the information be different.

Sure. This works here too. You can differentiate between the different
next-hops in ECMP_NEXT_HOP also. <AFI=1, SAFI=1> in ECMP_NEXT_HOP would
correspond to the BGP NLRI and the additional next-hops, while matching
values of <AFI,SAFI> in ECMP_NEXT_HOP will match MP_(UN)REACH_NLRI. 

]
]Aside from the somewhat contrived issue above, could you 
]clarify the behavior for MP-BGP processing for the MP nexthop? 

Scenario 1:

Say you have 2 equal cost paths for an IPv6 prefix with similar path
attributes. These can be advertised as follows:

You put the first MP nexthop and the NLRI in MP_REACH_NLRI. You are now left
with another MP nexthop. You use ECMP_NEXT_HOP path attribute for this. Put
the same AFI, SAFI, length and network address of the MP nexthop in
ECMP_NEXT_HOP and advertise this to the remote peer.

Scenario 2:

You have already advertised one MP_REACH_NLRI and you receive another equal
cost BGP route for the same NLRI (possibly with a different set of path
attributes). You now encode the new information the following way:

Put the NLRI in MP_REACH_NLRI. Set the length and the address of the MP
nexthop as Zero. Put this MP nexthop info in ECMP_NEXT_HOP and advertise
this to your IBGP peer. It will append this route, as it has been advertised
with ECMP_NEXT_HOP.

] What I would suspect from reading this document is that when 
]the MP nexthop is specified (length of nexthop != 0) that it 
]should also behave as an implicit withdrawal of the ECMP 
]paths.  

Yes, if an implementation receives an UPDATE message with MP nexthop inside
MP_REACH_NLRI, then it shall consider this as an implicit withdrawal of the
previous advertised paths.

]It's somewhat unclear whether a length of zero in the 
]MP nexthop case is the proper mechanism.

This needs to be added.

]
]I would suggest some additional language noting that the 
]implicit withdrawal case (advertise a withdrawal and new NLRI 
]simultaneously) should be processed as just implicit 
]withdrawals.  This may cause churn in some implementations 
]that may process the unfeasible routes component of an update 
]and then the feasible routes separately.
]
]Similarly, this would suggest that implementations will need 
]to carry MP_REACH_NLRI and MP_UNREACH_NLRI simultaneously.  
]Some implementations do not appear to do this currently.
]
]Interactions with RFC 3107 Sect. 4, if any,  would be good to 
]have in this document.

You mean, receiving a prefix with multiple labels?

IMO a PE can do load splitting in whatever manner it wants to. It doesn't
need to inform the other PE that there is more than one next-hop available
to reach a destination. Basically its something similar to what we have done
for EBGP peers.

]
]I'm most concerned about the synthesized AS_PATH.
] o In some circumstances, particularly with large AS_SETs, it will not
]   be possible to preserve path length.

Could you give me an example to illustrate this?

] o Processing ECMP routes into paths of equivalent length with many
]   AS_SETs will impact AS_PATH regular expression engines.
] o The set merging rules of BGP (9.2.2.2, draft 25) can result
]   in the AS_PATH being shortened.

I am sorry, I didn't get this!

Manav

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 22 Sep 2004 11:15:49 -0400

Manav,

> values of <AFI,SAFI> in ECMP_NEXT_HOP will match MP_(UN)REACH_NLRI. 

Consider the following case:

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + NEXT_HOP - 192.168.1.1
  + MP_REACH_NLRI
    o AFI - 1 (ipv4)
    o SAFI - 1 (unicast)
    o MP_NEXTHOP - 192.168.1.2
    o MP_NLRI - 10.0.1/24
NLRI: 10.0.0/24

If one wanted to insert an IPv4/Unicast ECMP nexthop set here, which
NLRI set would it apply to?

> ECMP_NEXT_HOP and advertise this to the remote peer.

Right.  In this case the MP_NEXTHOP is being using to "reset" the
nexthops for the prefix and the ECMP_NEXTHOP is being used to add 
additional ones.

> this to your IBGP peer. It will append this route, as it has been advertised

I think what makes me uncomfortable with this mechanism is implicitly
using the normal NEXT_HOP as a reset mechanism.  Just from a coding
standpoint, I'd rather see either no normal nexthop and a set of
ECMP nexthops which always have an implicit withdrawal behavior
or no ECMP nexthops at all.

> ]MP nexthop case is the proper mechanism.

That would clarify things.

> You mean, receiving a prefix with multiple labels?

Yes.

> to reach a destination. Basically its something similar to what we have done

Yes, it could do whatever it wanted to.  However, RFC 3107 implicitly
expects that you only get one nexthop.  If you get more than one,
this will potentially affect the behavior.  The change in behavior
should be discussed somewhere - and I think that your draft is probably
the right place to do that.

> Could you give me an example to illustrate this?

10/8 NH a Path 1 2 [<255 ASes>]
10/8 NH b Path 3 4 [<255 ASes>]

Resulting advertisement:
10/8 ECMP NH a,b Path [1 3] [2 4] [<first part of first path/second path>] [<second part of first path/second path>]

Note that this presumes that the set elements in the original
advertisement are disjoint and thus not prone to merging.

The path is thus lengthened.

> I am sorry, I didn't get this!

As for the first:

I get [1 3] [2 4] (rest)

Previously I would have gotten 1 2 (rest) or 3 4 (rest).

I can do a regular expression that says "Match 1 2 .*$" and prefer this
path.

The behavior of AS Path regular expressions in the presence of sets
is ambiguous at best and not really documented.  However, adjacency
tests don't make clear sense in the presence of sets, especially
given the merging rules.

Per the aggregation rules, one would typically not see sets such as
[1 3] [2 4] in the net.  An implementation would typically create
[1 2 3 4] as part of aggregation.  Generating separate sets is a deviation
from the specification, but not a mandatory one:

            - for each pair of adjacent tuples in the aggregated
            AS_PATH, if both tuples have the same type, merge them
            together, as long as doing so will not cause a segment with
            length greater than 255 to be generated.

The multiple set element encoding doesn't break BGP, but it makes a
presumption that really isn't all that clear in -25.  That presumption
is that an implementation will not take adjacent set elements and
merge them.  Also, it presumes that an implementation wont choose
to clean up sets of the form:

[1 2] [3 4] [3 4]

where the original was:
1 3 3
2 4 4

As by the aggregation rules, a given set element should exist within
the AS_PATH only once.

I suspect it would be ... instructive to find out what various implementations
do with odd AS_PATHs as would be generated by the synthetic AS_PATH.

-- 
Jeff Haas 
NextHop Technologies

---

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 23 Sep 2004 14:36:29 +0530

Jeff,

> NLRI set would it apply to?

Like the other path attributes ORIGIN, AS_PATH, etc. ECMP_NEXT_HOP too
applies to all the NLRIs listed in an UPDATE message. If in this case you
had an additional next-hop for only 10.0.0/24, you could announce this
information in the following two ways.

Let the additional NEXT_HOP be 192.168.1.3

(i) In addition to the above UPDATE message you could announce another one
containing

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + ECMP_NEXT_HOP
    o AFI - 1 (ipv4)
    o SAFI - 1 (unicast)
    o NUM NEXTHOPs - 1
    o LENGTH - 4
    o MP_NEXTHOP - 192.168.1.3
NLRI: 10.0.0/24

The IBGP peer upon receiving this UPDATE message will know that it needs to
append this route rather than replace.

(ii) You could announce the following two UPDATE messages.

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + NEXT_HOP - 192.168.1.1
  + ECMP_NEXT_HOP
    o AFI - 1 (ipv4)
    o SAFI - 1 (unicast)
    o NUM NEXTHOPs - 1
    o LENGTH - 4
    o MP_NEXTHOP - 192.168.1.3
NLRI: 10.0.0/24

and

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + MP_REACH_NLRI
    o AFI - 1 (ipv4)
    o SAFI - 1 (unicast)

How you advertise the routes depends upon the time (apart from your
implementation) at which the information about this additional NEXT_HOP is
known to the originating router.

[..]
> or no ECMP nexthops at all.

Could you elaborate on why using the ordinary NEXT_HOP for implicit
withdrawls makes you feel uneasy? We think having such a mechanism in place,
makes it easier to understand the new capability (everybody is familiar with
how implicit withdrawls work) and introduces no additional burden on the
implementation. The way it works is that any time you receive an UPDATE
message with ECMP_NEXT_HOP, you know that the route needs to be appended and
not replaced!

Let me explain what i think you are suggesting. Correct me if i am wrong.

Lets assume we have two next-hops N1 and N2 for a NLRI. Say after some
point, we get another one N3. You suggest that we should now announce
ECMP_NEXT_HOP N1, N2 and N3. That way, whenever you receive a new UPDATE,
you always treat that as an implicit withdraw, the way BGP works now. Is
that it?

I would prefer the former approach because there can be cases (L3 VPN NLRIs,
etc) where the NLRI may be clubbed with some information (labels, etc) that
may make it non unique. In such cases, its much easier to use the mechanism
that we have described. This'll become clearer when i explain how ECMP can
work with 3107.

> the right place to do that.

I may be missing something, but isn't this more of an implementation
specific issue?

Anyways, there isn't anything in this draft that precludes this.

Assume that a PE router has two next-hops to reach some NLRI x.y.z.w. Let L1
and L2 be the labels associated with these next-hops. It could send this
information the following way

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + MP_REACH_NLRI
    o AFI - IPv4
    o SAFI - VPN
    o MP_NEXTHOP - 0::192.168.1.2
    o MP_NLRI - L1:RD:x.y.z.w

and

WD_NLRI: NULL
Path Attributes:
  + Origin - IGP
  + AS_PATH - 65535
  + MP_REACH_NLRI
    o AFI - IPv4
    o SAFI - VPN
    o MP_NEXTHOP - 0
    o MP_NLRI - L2:RD:x.y.z.w
 + ECMP_NEXT_HOP
    o AFI - IPv4
    o SAFI - VPN
    o NUM NEXTHOPs - 1
    o LENGTH - 4
    o MP_NEXTHOP - 0::192.168.1.3

> 10/8 NH b Path 3 4 [<255 ASes>]

I believe, the above means that each AS_PATH contains 2 ASes in AS_SEQ and
one large AS_SET containing 255 ASes against, each path having 257 ASes in
AS_SEQ.

>
> Resulting advertisement:
> 10/8 ECMP NH a,b Path [1 3] [2 4] [<first part of first path/second path>]
> [<second part of first path/second path>]

Refer to Sec. 16.1 on how we construct the synthetic AS Paths in cases where
the contributing AS Paths consist of AS_SETs.

Resulting advertisement will be:
10/8 ECMP NH a,b Path [1 3] [2 4] [<255 ASes from the first path> <255 ASes
in the second path>]

The problem of over flowing that will occur in constructing this extremely
large AS_SET is also present in ordinary BGP, and yes, something that we
need to work upon!

> The path is thus lengthened.

Yes. If we have more than 255 ASes present in the AS_SET, then we may need
to prepend a new segment of type AS_SET, which will increase the path
length, as each AS_SET is counted as 1, irrespective of the number of ASes
present in the set.

However, this can be easily avoided by introducing a new path segment type
AS_EXT_SET (value 3) which will have exactly the same semantics as the
existing AS_SET, except that it wont be considered when counting the AS_PATH
length.

> I can do a regular expression that says "Match 1 2 .*$" and prefer this

You really cant run your regular expression here that says "match 1 2 .$"
because now your traffic will be split across paths "1 2 (rest)" and "3 4
(rest)". Moreover, this seems to be an implementation issue and i am sure
vendors can find clever ways to do this.

> presumption that really isn't all that clear in -25.

I am not sure if we can call this as "deviating" from the base spec.
Multiprotocol extensions did something similar for NEXT_HOP attribute.

> That presumption

Definitely.

Cheers,
Manav

---

From: Pekka Savola <[email-masked]>
Date: Thu, 23 Sep 2004 14:36:32 +0300 (EEST)

> this draft to be discussed in the IDR WG to see if it's a sensible work item

FWIW,

This seems to change the way BGP works in a relatively fundamental 
way, and I don't see sufficient justification for the proposed 
changes.

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

---

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 23 Sep 2004 17:26:59 +0530

> way, and I don't see sufficient justification for the proposed

Could you elaborate on what you mean by changing the way BGP works in a
"relatively fundamental way"?

All this draft says is that a router should advertise all its equal cost BGP
routes to its IBGP peers *if* its using them. The reason why its advertising
these routes is because its *using* them itself. YOu dont want routing and
forwarding to go different ways. Then, since you are using multiple paths,
you ought to tell everybody else of this. So, you construct a synthetic
as-path and advertise that to your EBGP peers.

Manav

---

From: Enrico Salazar <[email-masked]>
Date: Thu, 23 Sep 2004 07:21:33 -0700 (PDT)

Jeffrey,
 
I am referring to the following paragraph:
 
   An UPDATE message SHOULD NOT include the same address prefix (of the
   same <AFI, SAFI>) in more than one of the following fields: WITHDRAWN
   ROUTES field, Network Reachability Information fields, MP_REACH_NLRI
   field, and MP_UNREACH_NLRI field. The processing of an UPDATE message
   in this form is un-defined.

Enrico.

Jeffrey Haas <[email-masked]> wrote:
Enrico,

-- 
Jeff Haas 
NextHop Technologies

---------------------------------
Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 23 Sep 2004 11:16:01 -0400

Enrico,

>    in this form is un-defined.

I am referring to different prefixes with differing nexthops.

-- 
Jeff Haas 
NextHop Technologies

---

From: Pekka Savola <[email-masked]>
Date: Mon, 27 Sep 2004 14:20:55 +0300 (EEST)

> "relatively fundamental way"?

I said so because BGP builds on the concept of best route and just one
next-hop, not multiple ones.  Change there would seem to be
fundamental.
 
> as-path and advertise that to your EBGP peers.

You asked me why not adapt BGP to advertise multiple syntentic
AS-paths and nexthops, because the nexthops are being used.  I ask you
which spec says there will be multiple BGP next-hops to begin with.

The whole concept of multiple next-hops seems questionable to me.  
For simplicity, BGP should have only one next-hop.  Whatever happens
below BGP (e.g., whether that next-hop address is anycasted,
loadbalanced using IGPs, recursively resolved or whatever) should be
irrelevant to the BGP advertisements themselves.