Subject: On VPLS and Routing Protocols

From: Alex Zinin <[email-masked]>
Date: Tue, 22 Jul 2003 11:56:24 -0700

[RTG TA hat on]

I'd like to comment on the issue of routing protocol operations under
the condition of a PW failure in a VPLS.

First, let me note that both ISIS and OSPF protocols already know how
to deal with NBMA clouds that exhibit the same behavior as VPLS as far
as connectivity is concerned.

ISIS takes the simplest approach--assumes any-to-any connectivity
(essentially full mesh of VCs) and treats the cloud as broadcast
media--DIS is elected, and the cloud itself is abstracted as a
pseudo-node with all routers attached to it. The broadcast service
itself is provided by the interface driver that replicates the
multicast packets for multiple VCs. The same approach is used in
OSPF's NBMA mode. The catch here is in potentially nasty problems that
show up when connectivity between non-DR/DIS routers changes. Here's
an example:

               10.2/16
                   |
              ...[R2]...
             .   /  \   .
   10.1/16--[R1]+----+[R3]--10.3./16
             .          .
              ..........

Assume that R2 is elected as the DIS on the segment/cloud.

R1 will establish an adjacency with R2, but not with R3, because both
R1 and R3 are non-DIS routers. This means that the RP will be actively
checking connectivity of the R1-R2 and R2-R3 VCs only, and if the
R1-R3 VC goes down, the RP will not notice it. However, connectivity
between R1 and R3 is still assumed by the protocol, and R1, for
example, will install a route to 10.3/16 as follows:

  10.3/16 -> FrameRelay0/0, R3

That is, R1 will try to route directly to R3, not through R2. So if
R1-R3 VC is down, traffic will be black-holed.

In the case of VPLS, the situation is essentially the same-- there is
a risk of traffic black-holing when one PW goes down.

Another risk is inconsistency in the DIS/DR calculations among the
attached routers because of the differences in the sets of visible
neighbors. This one leads to problems with adjacency establishment,
which is a bit better, since they are visible at the RP level and
should be reported to the admin.

There are no additional and already existing mechanisms in ISIS that
could help us address the problem. The operational model is to monitor
the status of each VC/PW and troubleshoot when an alarm is received.
OSPF is a little different.

What we would like to have in the VPLS case is awareness of the PW
topology and ability of the RP to reroute around a failure (R1
rerouting through R2 in the example above.) As only fully established
adjacencies are used to abstract the network topology, we essentially
need any-to-any adjacency establishment (vs DR/BDR to others in the
normal NBMA case). We also need the RP to abstract connectivity over
an emulated LAN as a set of p2p links, rather than a pseudo-node with
all routers connected to it.

What's described above is the point-to-multipoint mode in OSPF. It is
normally used for NBMA clouds, but can be reused for the VPLS case.
There's one subtle detail though--neighbor discovery.

Normally, in the p2mp mode, neighbors are assumed to be configured
manually. However, we don't want to require that VPLS customers have
to configure them, so we need hello-broadcast neighbor discovery
combined with p2mp OSPF network type. I know at least one major vendor
that supports it, but others may not, so it is worth spelling out.

Note that the choice of treating an emulated LAN as a broadcast
network with DR/DIS vs a p2mp one, is not straight-forward. It is
about the balance between protocol scalability and network
availability. With the p2mp network approach, the number of
adjacencies is O(N^2) (vs O(N) in the broadcast network case), which
affects complexity of the protocol operation, most notably flooding
and SPF computation. On the other hand, it gives us better
connectivity in PW failure scenarios.

Hope this sheds some light on this issue.

If there's interest within the WG, these considerations could
be captured in a short document.

Regards

-- 
Alex
http://www.psg.com/~zinin/

---

From: "Vach Kompella" <[email-masked]>
Date: Tue, 22 Jul 2003 12:22:47 -0700

Given a VPLS model that includes HVPLS, there is a straightforward modification
of the VPLS topology to remove the blackhole.  However, it may result in
flapping.

Here's how the black hole can be resolved:

If a VPLS node loses one PW (which has to be a PW on which the split horizon
rule applies), it declares all but one of its PWs to be down, and turns the
remaining PW into a VPLS spoke, i.e., split horizon doesn't apply to it.

Just bringing a PW down doesn't quite cut it, since that ripples across the
entire VPLS and causes the VPLS to come down.  Instead, a special state would
apply to those PWs such that they are "blocking" to use a spanning tree term.

When the PW that went down comes back up again, the state of all the PWs that
were blocking goes back to split-horizon, along with the one PW that went into
spoke mode.

E.g., R1 to R2 goes down:

          R1-----R2
          | \   / |
          |  \ /  |
          |  / \  |
          | /   \ |
          R3-----R4

This becomes

          R1     R2
          | \   / |
          |  \ /  |
          |  / \  |
          | /   \ |
          R3-----R4

With the above rules, let's say R1 takes the action (for some a priori tie
breaking rule between R1 and R2 so there is no need to communicate between R1
and R2)

          R1     R2
          | \   / |
          |  \ /  |
          |  / \  |
          | /   \ |
          R3-----R4

One PW becomes a spoke: let's say R1-R3.
All but one PWs are marked blocking: let's say R1-R4 is marked blocking.

          R1     R2
          |     / |
          |    /  |
          |  /    |
          | /     |
          R3-----R4

Note that the remaining VPLS nodes are in a full mesh.  Some relearns are
necessary to fix blackholes.

We'd have to deal with flapping PWs.

-Vach

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of
> Alex Zinin
> Sent: Tuesday, July 22, 2003 11:56 AM
> To: [email-masked]
> Subject: On VPLS and Routing Protocols
>
>
> [RTG TA hat on]
>

---

From: Eric Rosen <[email-masked]>
Date: Wed, 23 Jul 2003 13:21:31 -0400

Wouldn't it be nice  if the CE only had to be a routing  peer of its PE, and
if the PEs were responsible  for redistributing all the routing info (using,
say, BGP)?  Then we wouldn't have  this "look like a LAN for scalability but
look like a full mesh of  p2p links for availability" conundrum.  Oh, sorry,
wrong working group ... ;-)

If we look at the problem from  an IPLS perspective, the "lack of full mesh"
problem is  that not all  of the PEs  supporting a given IPLS  instance have
operational PWs to  all of the CEs that are attached  to that IPLS instance.
Note that each PE supporting an  IPLS instance must know the IP addresses of
all the  CEs attached to that  IPLS instance.  If  each PE sends to  all the
others  the list  of CEs  that it  "sees",  then every  PE will  be able  to
determine whether there is a proper  full mesh or not.  In the non-transient
absence of a full mesh, alarms could start to go off. 

Of course, the notion of "a PE sees  a (remote) CE" would have to mean "a PE
has an operational  PW to a CE", where "operational"  means "can pass data".
The notion of "non-transient" would also have to be defined.  One could also
consider whether  there should  be any automatic  action in addition  to the
sending of alarms.

---

From: Eric Rosen <[email-masked]>
Date: Wed, 23 Jul 2003 13:41:36 -0400

Vach> If a VPLS node  loses one PW (which has to be a  PW on which the split
Vach> horizon rule applies), it declares all  but one of its PWs to be down,
Vach> and  turns the remaining  PW into  a VPLS  spoke, i.e.,  split horizon
Vach> doesn't apply to it. 

Doesn't this mean  that if one PE  crashes, every other PE will  try to turn
into a spoke? 

You also have to deal with the case  in which a PW fails to come up to begin
with,  and the  case in  which a  PE fails  to learn  about the  need  for a
particular PW, due perhaps to a failure in the autodiscovery procedure. 

Note  that the  only  failures  this protects  against  are hardware  and/or
software bugs; since  such failures may easily impact more  than one PW, I'm
not sure  that a procedure which  will redo the  topology in the event  of a
single PW failure is really worthwhile.

---

From: Alex Zinin <[email-masked]>
Date: Thu, 24 Jul 2003 18:05:55 -0700

Vach,

  Optimizations are fine. However, from the routing perspective,
  if there still are potential cases where any-to-any connectivity
  is not maintained, those considerations apply.

> of the VPLS topology to remove the blackhole.  However, it may result in
[...]

---

From: Eric Rosen <[email-masked]>
Date: Fri, 25 Jul 2003 14:06:42 -0400

Alex> Vach,

Alex>   Optimizations are fine. However, from the routing perspective,
Alex>   if there still are potential cases where any-to-any connectivity
Alex>   is not maintained, those considerations apply.

I'm not sure you've fully understood  Vach's proposal.  He is trying to come
up with  a scheme that  maintains the any-to-any  connectivity even if  a PW
fails.  Such a scheme, if  successful, would certainly eliminate the routing
problem that you've described.

Sasha> In particular, it is capable of delivering LAN broadcasts, hence I do
Sasha> not understand your reference to the "NBMA clouds. "  

That's because  you're taking a layer  1/2 perspective instead of  a layer 3
perspective ;-)

When link  state routing protocols  operate over a  LAN, they use  a certain
"optimization"  (all  that "designated  router"  stuff).  This  optimization
doesn't produce the correct result  if the "VPLS full mesh" fails.  However,
one  could eliminate this  problem by  not using  the optimization  when the
routers are connected over a VPLS. 

Currently routers do know how to  cope with the situation in which there are
multiple peers  out a single interface,  but the LAN  optimizations can't be
used; this is exactly the situation that occurs when a router connects to an
NBMA  cloud.  One  solution is  to have  the routers  use this  same  set of
procedures when connected to a VPLS; that's how "NBMA" entered the picture.

Having  said all  that,  this  probably isn't  really  a workable  solution,
because it  may not  always be apparent  to a  router that a  particular LAN
interface leads to a VPLS rather than a native LAN.  

Sasha> The current VPLS  approach seems to strongly discourage  using of SPT
Sasha> between  virtual LAN  switches interconnected  over the  Ethernet PWs
Sasha> (there  is  a parallel  email  thread running  on  this  list at  the
Sasha> moment).  IMO  you have made a  very good case for  for revising this
Sasha> position. 

I don't think  so.  Using SPT between the virtual LAN  switches has a number
of problems as well: 

- Every PE has  to be able to serve as a transit  point for traffic from any
  second PE  to any  third PE.  (This  in itself  probably makes the  idea a
  non-starter.)

- Highly suboptimal routing in the backbone. 

- The  usual spanning tree issues, e.g.,  all traffic is carried  on a small
  set of links  while other links remain idle, need  to manage spanning tree
  within backbone, no inter-provider support, etc. 

Not to mention that one of the  reasons for this whole effort is to keep the
spanning tree out of the backbone. 

A better approach would be to see if  there is a way to detect that the full
mesh has failed  (say, by having each  PE tell all the others  "here are the
other PEs I  can talk to in the specified VPLS  instance"), and to determine
what action to take when the full mesh does fail.

---

From: Alex Zinin <[email-masked]>
Date: Mon, 28 Jul 2003 16:05:22 -0700

Eric,

Alex>>   Optimizations are fine. However, from the routing perspective,
Alex>>   if there still are potential cases where any-to-any connectivity
Alex>>   is not maintained, those considerations apply.

> problem that you've described.

I understood that, it just wasn't obvious to me that the proposed
mechanism would cover all failure modes, such as failure of more
than one PW.

[rtg part clipped]

> interface leads to a VPLS rather than a native LAN.

Routers would need to be manually configured to treat the interface as
point-to-mutlipoint broadcast. We normally don't have to do so for LAN
interfaces, but it's a one-liner.

[clipped]

> what action to take when the full mesh does fail. 

Agreed, though we should keep the complexity as low as possible, I
believe. From a higher perspective, it seems we have the following
potential approaches to PW failures:

 1. Fix connectivity within the PW mesh so that the VPN
    routing layer does not notice.

 2. Don't fix connectivity and let the VPN routing layer track
    all details and reroute appropriately (the p2mp option
    I described)

 3. When node A looses the PW to node Z, make sure nodes B..Y
    simulate loss of connectivity to A and Z too, so all CEs
    have a consistent view and VPN routing converges properly.
    I.e. PW failure triggers simulation of 2 node failures.

 4. Don't fix connectivity, don't change VPN routing,
    just throw an alarm and wait till the admin fixes the problem.

I'd need to think more if we can do 1) with multiple PW failures
without ending up having to do routing within the PW mesh. Option
2 seems ok, but only applicable to some routing protocols (we can't
guarantee that OSPF, or IP at all for that matter, will be running
across the VPLS), so it would be ok as a recommendation if we
decide to go with 4). It would be interesting to see what people
think of option 3. Option 4 is the back-up we always have :)

Alex

---

From: Alex Zinin <[email-masked]>
Date: Wed, 30 Jul 2003 10:11:50 -0700

Monday, July 28, 2003, 4:05:22 PM, Alex Zinin wrote:
[...]
>     I.e. PW failure triggers simulation of 2 node failures.

IF we decide to go this route, the simplest way to do this is for A
and Z to logically put all other PWs they have logically down (stop
sending outgoing and drop incoming traffic on them) when they see a PW
failure. This way, the two-way connectivity of all other CEs with
those attached to A and Z will be broken and VPN routing will
reconverge properly. No extra message exchange, no additional
signaling--everything is a node-local decision.

Alex

---

From: Eric Rosen <[email-masked]>
Date: Wed, 30 Jul 2003 14:34:31 -0400

>> I.e. PW failure triggers simulation of 2 node failures.

Alex> IF we decide to go this route, the simplest way to do this is for A
Alex> and Z to logically put all other PWs they have logically down (stop
Alex> sending outgoing and drop incoming traffic on them) when they see a PW
Alex> failure. This way, the two-way connectivity of all other CEs with
Alex> those attached to A and Z will be broken and VPN routing will
Alex> reconverge properly. No extra message exchange, no additional
Alex> signaling--everything is a node-local decision.

But this doesn't handle the case where  A and Z, for some reason, either (a)
never find out about  each other, or (b) never succeed in  setting up PWs to
each other in the first place.  Also,  if node Z happens to go down, doesn't
this make all the PWs go down?  

I really don't think this can be done based on local knowledge.

---

From: Kireeti Kompella <[email-masked]>
Date: Thu, 31 Jul 2003 08:18:24 -0700 (PDT)

> signaling--everything is a node-local decision.

This might be simpler, but it is a hack.  It is cleaner for A and/or Z
to withdraw their labels so that B..Y all know that their connections
to A and/or Z are down.  The "extra message exchange" ensures
a) all nodes are in sync about what's going on;
b) B..Y can, on learning of the loss of connectivity, signal this change
   to their CEs, (in the fullness of time, when Ethernet OAM/UNI is
   defined);
c) traffic doesn't transit the PSN only to get dropped at A or Z.

Just as a reminder, this was what Norm Finn suggested (Norm, correct
me if I misrepresented you.)

Kireeti.

---

From: Eric Rosen <[email-masked]>
Date: Thu, 31 Jul 2003 12:58:29 -0400

> This might be simpler, but it is a hack. 

Kireeti, I'm surprised at you, calling something a "hack" ;-)

> this was what Norm Finn suggested

Norm  suggested that a  PE not  bring up  any of  its PWs  unless it  had an
operational  PW to  each other  PE that  it learns  about via  the discovery
process.  This also  has the problem that if  you don't have a PW  to Z, you
can't tell locally whether  anyone else has a PW to Z.  (If  no one has a PW
to Z, then of course everything is okay as is.)

---

From: "Cheng-Yin Lee" <[email-masked]>
Date: Thu, 31 Jul 2003 14:46:48 -0400

Alex et al,
Just catching with my email now. Thanks for discussing these issues.

I think in choosing any of these options, it may be preferable if the
approach chosen works on any device on the emulated LAN e.g. for CE
routers, bridges or hosts. Mick Seaman proposed a solution on IEEE 802.1
(or PPVPN?) mailing list prior to this. My understanding of the proposal
is - the VPLS entity shall disable the MAC port presented to the 802.1ad
bridge if a PW fails. I think Himanshu has described a similar approach
("blocking" VPLS port) in this thread.

Also, I think the issue of synching the bringing up of PWs initially and
after PW(s) failure need to be considered as well. In the proposal above
and in the discussion on (3), PEs may need to agree on which are the
currently participating PEs and ensure all other participating PEs have
connectivity to each other, i.e.  a protocol among PEs may be needed in
this approach.

Thanks
Cheng-Yin

---

From: "Cheng-Yin Lee" <[email-masked]>
Date: Thu, 31 Jul 2003 14:57:05 -0400

Eric,

> this make all the PWs go down?
I believe so, unless other PEs can figure out node Z is down and no
longer participating in the VPLS.

Regards
Cheng-Yin

---

From: "Cheng-Yin Lee" <[email-masked]>
Date: Thu, 31 Jul 2003 17:16:49 -0400

> to Z, then of course everything is okay as is.)

Agree VPLS membership info is not sufficient to determine whether
MAC/VPLS/PW port should be blocked. An additional mechanism to know
about other currently participating PW and PE may be needed then.

Having said this, I am not suggesting that this mechanism should be
used, merely trying to think what is needed with the approaches being
discussed, to get things to work.

Regards
Cheng-Yin