Subject: [Idr] Advertising Multiple Next Hop Routes in BGP

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 10 Aug 2006 06:26:17 +0530

Folks,

A revised draft of draft-bhatia-bgp-multiple-next-hops-01.txt has been 
posted to the internet draft repository.  This revision simplifies the 
operation, and addresses some of the concerns expressed by IDR working group 
participants. The simplification comes primarily from removing a capability 
which analysis showed was purely informational.  The previous draft amongst 
other things allowed for sending advertisements which differed on AS path 
but had the same next-hop.  In discussions, it was noted that since these 
paths had the same next-hop, the receiver would need to combine them anyway. 
Therefore, the draft now requires that when sending multiple advertisements 
for the same NLRI, these advertisements must use differing next-hops. As a 
result of this, the next-hop becomes the distinguishing attribute, along 
with the NLRI, for the advertisement.  Thus, implicit withdrawls are 
supported without needing to introduce additional indexing attributes.

The proposal is compatible with IPv6 support, MPLS label advertisement, and 
BGP multi-protocol support.

The text for optional support of only ECMP routes, a refinement of sending 
all routes with distinct next-hops for an NLRI, and the description of the 
constraints on how multiple advertisements are compressed when they are 
being used by a BGP speaker, will be folded in as a short portion of the 
next revision of this document or a separate draft as deemed fit by the WG.

http://www.ietf.org/internet-drafts/draft-bhatia-bgp-multiple-next-hops-01.txt

Thanks,
Manav

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

---

From: "Glen Kent" <[email-masked]>
Date: Thu, 10 Aug 2006 21:38:26 +0530

I have been following the progress of this draft as the proposal of
allowing advertisement of multiple BGP paths interests me and i think
its a logical next step that BGP has to take at some point of time in
future. The operators may not see a glaring need now but i think the
proposal has enough merits to warrant a closer inspection of what all
can be achieved with it.

I know the draft claims to support multi-protocol BGP but an example
or some text elucidating this would be extremely illuminating for most
of the readers.

Glen.

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 11 Aug 2006 15:22:54 +0530

Hi Glen,

Thanks for the comments.

Let me illustrate how our proposal would work with mpbgp routes.

A and B are two BGP speakers that have negotiated this capability with the 
RM bit set. This means that A and B are both willing to accept multiple BGP 
paths, so the other can announce the same.

Assume A receives two routes to some destination X (afi=x1, safi=x2) with 
mpbgp next-hops n1 and n2. It encodes the first route in MP_REACH_NLRI and 
advertises that route.

To advertise the next route the nlri part is encoded in MP_REACH_NLRI and 
the nexthop is encoded in MULTIPLE_HOP attribute as shown below:

MP_REACH_NLRI (as per draft-ietf-idr-rfc2858bis-10.txt) that encodes X:

afi = x1
safi = x2
length of next hop address = 0
reserved = 0
nlri = X

MULTIPLE_HOP is encoded as:

afi = x1
safi = x2
number of nexthops = 1
length of nexthop = length of n2
network address = n2

The receiving BGP speaker B appends this route as it comes with along with 
the MULTIPLE_HOP path attribute. It thus now has two routes (next-hops n1 
and n2) to reach X.

Hope this helps.

Regards,
Manav

---

From: "Glen Kent" <[email-masked]>
Date: Fri, 11 Aug 2006 22:36:30 +0530

Hi Manav,

> length of nexthop = length of n2

All right, this would work. Thanks for the explanation.

Looking at this in another light leads me to think that its now kinda
possible to disassociate the AFI-SAFI (or simply the network layer
protocol) of the next-hop with that of the NLRI in a more elegant and
a scalable way.

I have in the past expressed my displeasure at how we pad NULL RDs in
2547 when filling the next-hop information in the mp-reach-nlri path
attribute. To me mp-reach-nlri/2547 is a big kludge and i dont see a
reason why we need to restrict the network layer address family of the
next-hop to be the same as that of the NLRI. I call it a kludge
because we may land up with some applications where the address of
nexthop may not align with the format of the NLRI information by mere
padding.

I don't know if the authors of this draft had this in mind, but a side
effect of this mechanism is that we can now disassociate the two
entities. And i find this useful in addition to what it already
achieves.

Glen

---

From: "Deepak Pandey" <[email-masked]>
Date: Mon, 14 Aug 2006 06:47:27 +0530

Hi,

I think i understand the answer but just making sure that i am in synch ..

To advertise multiple BGP paths we would need to change our decision
process. That is, at some point of time we would say that all
candidate routes left must be announced to the remote speaker if it
had the RM bit set when it did the multiple_hop capability
negotiation. I dont see you guys discussing this anywhere in your
draft. Is it because the draft doesnt care as to WHEN one announces
the multiple paths but rather deals with HOW one can do it?

If its the latter, then its application dependent on when one would
advertise multiple paths. Thus to solve the MED problem one would not
look at the Router ID for tie breaking and would instead advertise all
the remaining routes to the remote peer.

Is this the case? If so, then i trust that there is value in adding
this to the draft. If not, then i would want to see the details of
when an implementation decides to announce multiple BGP paths.

Warm Regards,
Deepak

---

From: "Manav Bhatia" <[email-masked]>
Date: Tue, 15 Aug 2006 08:32:30 +0530

Hi Deepak,

The draft details the procedures that a router must follow in order to 
advertise multiple BGP paths to a peer router.

We do not mandate a logic on how a router may select multiple paths that it 
may want to advertise. This leaves flexibility and room for an 
implementation to :

o advertise all the routes that it has (IXes)
o advertise equal cost routes by filtering the paths fully, up until it 
would use router ID/peer-address based tie breakers.
o advertise all routes matching some criterion (a community for example or 
user defined routemaps)
.. the list goes on.

Hope this helps.

Cheers,
Manav

----- Original Message ----- 
From: "Deepak Pandey" <[email-masked]>
To: "Manav Bhatia" <[email-masked]>; <[email-masked]>; 
<[email-masked]>
Cc: <[email-masked]>
Sent: Monday, August 14, 2006 6:47 AM
Subject: Re: [Idr] Advertising Multiple Next Hop Routes in BGP

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 15 Aug 2006 09:34:53 -0700

Glen,

[clipped...]

> next-hop to be the same as that of the NLRI. 

draft-ietf-idr-rfc2858bis-10.txt does *not* restrict the network
layer address family of the next hop to be the same as that of the NLRI.
Quoting from the spec (draft-ietf-idr-rfc2858bis-10.txt):

  Address Family Identifier:

     This field in combination with the Subsequent Address Family
     Identifier field identifies the Network Layer protocol associated
     with the Network Address of Next Hop and the semantics of
     the Network Layer Reachability Information that follows.

In other words, the same (afi, safi) tuple defines two things: (1)
the network layer protocol associated with the Network Address of
Next Hop, and (2) the encoding/semantics of NLRI.

Nowhere in the spec there is a requirement that the encoding/semantics
of Next Hop be the same as NLRI. For example let's look at
VPLS auto-discovery with BGP (draft-ietf-l2vpn-signaling-08.txt).
Quoting from the spec:

   In summary, the BGP advertisement for a particular VSI at a given PE
   will contain:

   o  an NLRI of AFI = L2VPN, SAFI = TBA, encoded as RD:PE_addr

   o  a BGP next hop equal to the loopback address of the PE

Here you have AFI = L2VPN, yet the next hop contains a plain IPv4
address.

So, clearly for a given (afi,safi) one could place a plain IPv4
address in the Next Hop, yet carry some non IPv4 NLRI, and use AFI
that is not the IPv4 AFI.

Yakov.

---

From: "Glen Kent" <[email-masked]>
Date: Tue, 15 Aug 2006 23:03:34 +0530

Yakov,

Certainly one can do this by creating new AFI and SAFI types.

But then that tuple <AFI, SAFI> can only be used for that particular
nexthop and NLRI set. So each time we require a new permutation we
need to request IANA for getting more code points.

Taking your own example, if the PE uses IPv6 then i would need a
different AFI, SAFI to convey the information.

But Yes, it will work with the existing mechanisms.

Affably,
Glen

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 15 Aug 2006 11:06:43 -0700

Glen,

> need to request IANA for getting more code points.

Using a distinct <AFI, SAFI> for a particular nexthop and NLRI set
is one possible way, but *not* the only one possible (more on this
below).
  
> different AFI, SAFI to convey the information.

You could use a different <AFI, SAFI>. But you can also use the
same <AFI, SAFI>, and distinguish between IPv6 and IPv4 PE by using
the nexthop length.

Yakov.

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 15 Aug 2006 15:11:50 -0700

Hi Yakov,

> same <AFI, SAFI>, and distinguish between IPv6 and IPv4 PE by using

One could also observe that what you indicated is exactly the approach
we took when defining new AFI/SAFI NLRI & NH for RT-Constrain.

http://www.ietf.org/internet-drafts/draft-ietf-l3vpn-rt-constrain-02.txt

Cheers,
R.

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 15 Aug 2006 15:14:05 -0700

Robert,

> http://www.ietf.org/internet-drafts/draft-ietf-l3vpn-rt-constrain-02.txt

You are absolutely correct. Thanks for pointing this out.

Yakov.

---

From: Eric Rosen <[email-masked]>
Date: Fri, 18 Aug 2006 10:15:24 -0400

Yakov> you can also  use the same <AFI, SAFI>,  and distinguish between IPv6
Yakov> and IPv4 PE by using the nexthop length. 

Robert> One could also observe that what you indicated is exactly the approach
Robert> we took when defining new AFI/SAFI NLRI & NH for RT-Constrain. 

For new  AFI/SAFI's we can define  what we want, but  what if we  want to be
able to have a v6 NH for a v4 NLRI, or a v4 NH for a v6 NLRI?  I don't think
it makes much sense  to define new SAFIs for these cases.   But I also don't
think we can  just change the interpretation of the NH  field of an existing
AFI/SAFI without defining a corresponding BGP capability; after all, we need
to know whether a given peer can deal with the fact that a v4 NLRI now has a
v6 NH. 

Once we  have a capability which  means "I can  handle an IPv4 or  IPv6 NLRI
which  has a  NH in  a different  address family",  I'm not  sure I  see the
great advantage of  using the length (rather than a  type field) to indicate
the address family of the next hop.

---

From: Yakov Rekhter <[email-masked]>
Date: Fri, 18 Aug 2006 08:26:06 -0700

Eric,

> it makes much sense  to define new SAFIs for these cases.   

What are the *existing* AFI/SAFI's that you are referring to in the above ?
  
Yakov.

---

From: "Tony Li" <[email-masked]>
Date: Fri, 18 Aug 2006 09:43:33 -0700

> able to have a v6 NH for a v4 NLRI, or a v4 NH for a v6 NLRI? 

Before we worry too much about the how's, I think we ought to first
consider the why's.  I actually had an opportunity to look into this in
a previous life and found some of the issues truly frightening.  

For example: suppose that you do have a v6 prefix with a v4 NH.  How do
you resolve that NH?  Does the v6 BGP code look into the v4 routing
table?  Do you end up putting a v4 NH into your v6 routing table?  How
do you deal with little issues like ARP table lookups in your v6
forwarding path?

Fundamentally, we have worked towards a ships in the night separation of
v4 and v6, modulo some obvious fuzziness around using one for transport
of the other.  This is an instance where we are threatening to
drastically lower the separation between the two and add another order
of magnitude in architectural and implementation complexity.  

I am concerned.

Regards,
Tony

---

From: Eric Rosen <[email-masked]>
Date: Mon, 21 Aug 2006 12:09:50 -0400

> suppose that you do have a v6 prefix with a v4 NH.  How do

The "v6  forwarding path" should  be able to  forward v6 packets  through v4
tunnels, and that already raises all the same issues.  

> I think we ought to first consider the why's. 

In forwarding (tunneling) v6 through a v4  core, or v4 through a v6 core, it
makes sense for the nh to be of the AF supported by the core. 

> of the other. 

Yes, they're completely separate, except for when they aren't ;-)

---

From: "Tony Li" <[email-masked]>
Date: Mon, 21 Aug 2006 10:00:19 -0700

> tunnels, and that already raises all the same issues.  

Not necessarily.

In some implementations, the notion of a tunnel is presented to layer 3
protocols as an abstraction of an "interface".  The transport protocol
(the one providing the tunneling service) is then wholly isolated from
the payload protocol.  This makes it possible, for example, to carry
AppleTalk over a GRE tunnel without modifying the AppleTalk
implementation.  Similarly, it makes it possible to resolve IPv4 next
hops and pass them across an MPLS LSP without having to resolve v4
routes against MPLS next hops.

> makes sense for the nh to be of the AF supported by the core. 

I have to disagree.  If a tunneling layer is providing a transport
service, it is architecturally smart for it to be unaware of the
protocols that it is transporting.  Next hop resolution should be done
by the payload protocol running its own independent routing on top of
the transport layer.

Regards,
Tony

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 21 Aug 2006 11:27:54 -0700

I have to agree with Tony here. Tunneling means very different things to
different people depending who you ask. And part of the mess has been
introduced with 2.5 OSI layer tunnels in the past :)). In this no one
really know if MPLS LSP is L2 or L3 pipe and different commercial
implementations in regards to BGP NH resolution treat it in very
different ways.

I think (my personal opinion) the best approach to carry address
families X over address family Y would with providing the overlay
tunneling layer where control plane would be fully separated from
transport layer.

In that scheme the NH resolution or verification have no issues. Remote
node failures are signaled from FIB tunnel tracking engine up to L3 in
an event driven fashion. BGP is not affected by any need of changes.

So my recommendation to this list would be to let the topic mature and
consider all options before committing to any protocol change which may
have any negative consequence of today's operational networks.

Rgs,
R.

---

From: Eric Rosen <[email-masked]>
Date: Mon, 21 Aug 2006 13:54:46 -0400

> protocols as an abstraction of an "interface". 

That's  one possible  implementation strategy,  but certainly  not  the only
one.  Protocol-specific overlay models have numerous disadvantages.

> This makes it possible, for example,  to carry AppleTalk over a GRE tunnel
> without modifying the AppleTalk implementation. 

If you  want a fast Appletalk  switching path, you  need a piece of  code to
produce some sort of forwarding  table data structure which contains the GRE
header  and  the L2  header.   So  the piece  of  code  which generates  the
Appletalk forwarding table entries needs to be able to get the IP and the L2
info.  It doesn't much matter what you call this piece of code.  

> If  a   tunneling  layer   is  providing  a   transport  service,   it  is
> architecturally smart  for it to  be unaware of  the protocols that  it is
> transporting. 

But what  we're talking about is the  other way around, viz.,  the extent to
which the protocols  being transported need to be  aware of the transporting
protocol.  It is  very common for a higher layer  protocol to define special
procedures for interfacing with a lower layer.  For example, ARP.

---

From: "Tony Li" <[email-masked]>
Date: Mon, 21 Aug 2006 14:45:55 -0700

> one.

True, but it's a common one, including brand C, J and the former brand P
implementations.

> Protocol-specific overlay models have numerous disadvantages.

I agree completely!  Why are you proposing one?

> info.  It doesn't much matter what you call this piece of code.  

If you want to have a fast Appletalk switching path that supports
tunneling, you end up caching an encaps string that is opaque to
Appletalk.  You don't need to modify Appletalk to carry IPv4 next hops.

> But what  we're talking about is the  other way around, 

Exactly.  Why?

Tony

---

From: Eric Rosen <[email-masked]>
Date: Wed, 23 Aug 2006 11:59:23 -0400

[changed the subject line to reflect the subject of discussion]

Tony> In some implementations, the notion  of a tunnel is presented to layer
Tony> 3 protocols as an abstraction of an "interface".

Eric> That's  one possible  implementation strategy,  but certainly  not the
Eric> only one.

Tony> True, but it's a common one, including brand C, J and the former brand
Tony> P implementations. 

It is  by no  means true  that all of  those implementations  always present
tunnels  as  interfaces.   Perhaps  you're  only thinking  of  GRE  tunnels?
Certainly  I know  of many  cases where  MPLS tunnels,  IPsec  tunnels, L2TP
tunnels, and even layer 2 tunnels are not presented to their user layers via
the interface  abstraction.  I also know  of cases where  tunnels were first
imlemented one way and  then had to be changed to the  other way for various
reasons.   That is  properly an  implementation  matter, and  should not  be
dictated by the architecture.

> tunneling, you end up caching an encaps string that is opaque to Appletalk 

Presumably the upper  layer passes the next hop to the  lower layer and gets
back the  opaque string.   In other words,  at least  part of the  "next hop
resolution" requires you to get information from other layers. 

In  any event,  BGP is  already capable  of doing  both v4  and v6  next hop
resolution. 

> You don't need to modify Appletalk to carry IPv4 next hops. 

If Appletalk were expected to  become a major protocol with worldwide scope,
I am sure we would be  talking about doing having Appletalk carrying IP next
hops, and/or  about having  BGP carry Appletalk  next hops.  It's  just that
Appletalk is of so little consequence  now that no one really wants to touch
it.  As such, it  is not necessarily a good model for  how we want to handle
IPv4 and IPv6.

Eric> Protocol-specific overlay models have numerous disadvantages.

Tony> I agree completely!  Why are you proposing one? 

Obviously there's  some talking  at cross-purposes going  on, since  I don't
believe I have suggested any kind of overlay.

The model I want to explore seems  to me to be a rather straightforward one,
and one which adheres closely to existing BGP practices.

There are  a number  of different address  families that BGP  carries today,
especially in the  L3VPN/L2VPN world.  But in most of  these cases, the next
hop still belongs to the IP address family, not to the address family of the
NLRI.  In many of these cases, the next hop can be either an IPv4 address or
an  IPv6 address,  with only  the  length to  distinguish v4  from v6.   The
expectation is that  the next hop will  be an IPv4 address when  IPv4 is the
infrastructure used to reach the next hop,  but that it will be IPv6 if IPv6
is the  infrastructure used to reach the  next hop.  (In some  cases, the IP
address may be encoded in a funny way so it looks like it belongs to another
address family, but that is now generally regarded as a piece of silliness.) 

I think  that when  the NLRI  is IPv4 or  IPv6, the  situation is  really no
different; when  a BGP speaker's address  appears in the next  hop field, it
should  still  be in  the  address  family that  it  is  using  for its  own
communication, which is not necessarily the address family of the NLRI. 

If two BGP  speakers are communicating over an  IPv6 infrastructure, I think
they should  be able  to have a  single BGP  session between them,  and they
should be  able to use that session  to exchange routes for  IPv4, IPv6, and
other address families.  But the BGP  session will be running over IPv6, and
when  a BGP speaker  puts itself  in as  a next  hop, it  should use  its v6
address.

I believe  this is a  straightforward extrapolation of the  current practice
for the cases where  NLRI is not IPv4 or IPv6.  In  fact, I would argue that
it doesn't depart from traditional  practice in pure IPv4 scenarios, because
the next hop has always been  in the address family of the IP infrastructure
that  is used for  communication between  the BGP  speakers.  It's  merely a
coincidence that the NLRI has been in that same family as well ;-)