Subject: Re: rtgwg Digest, Vol 94, Issue 12

From: Srini <[email-masked]>
Date: Mon, 22 Oct 2012 11:45:24 -0700

Dear Pascal & Gabor:

I was looking at the examples that Pascal gave.  One of the key points
that's missed in MRT can tolerate at most one link failure in an ear.
Once the packet moves from one ear to another, it can tolerate another
failure.  If you assume that you have one bit that indicates whether
you have seen a failure or not, you can view it as this being reset
every time the packet moves from one ear to another.

This property is well-known, please see the paper below:

Path Splicing with Guaranteed Fault Tolerance
T. Erlebach and A. Mereu
GLOBECOM 2009

With this the behavior of MRT and ARC are the same in the examples
that Pascale listed out in the email below.

Best regards,
Srini.
Associate Professor, ECE & CS
University of Arizona
http://srini.ca

On Thu, Oct 18, 2012 at 12:00 PM,  <[email-masked]> wrote:
> If you have received this digest without all the individual message
> attachments you will need to update your digest options in your list
> subscription.  To do so, go to
>
> https://www.ietf.org/mailman/listinfo/rtgwg
>
> Click the 'Unsubscribe or edit options' button, log in, and set "Get
> MIME or Plain Text Digests?" to MIME.  You can set this option
> globally for all the list digests you receive at this point.
>
>
>
> Send rtgwg mailing list submissions to
>         [email-masked]
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://www.ietf.org/mailman/listinfo/rtgwg
> or, via email, send a message with subject or body 'help' to
>         [email-masked]
>
> You can reach the person managing the list at
>         [email-masked]
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of rtgwg digest..."
>
> Today's Topics:
>
>    1. more subtle differences between Ears and ARCs
>       (Pascal Thubert (pthubert))
>    2. (no subject)
>
>
> ---------- Forwarded message ----------
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> To: "Gábor Sándor Enyedi" <[email-masked]>, "[email-masked]" <[email-masked]>
> Cc: "Dirk Anteunis \(danteuni\)" <[email-masked]>, "Patrice Bellagamba \(pbellaga\)" <[email-masked]>
> Date: Thu, 18 Oct 2012 18:06:31 +0000
> Subject: more subtle differences between Ears and ARCs
> Hello Gábor
>
>> So there is a * tradeoff *: basic MRT avoids single node or link failures, while ARCs may hit a single failures multiple times. It's a management decision which one is better.
>
> Resisting multiple breakages is probably the most evident difference but more subtle ones exist:
>
> 1) ARCs always bring you back quickly to a shortest path that is followed till the end or the next breakage.
> With MRT, once we are in a plan B, that plan B cannot be qualified vs. shortest path, and it can be a large detour.
>
> 2) ARCs have generalized the concept of the destination as well.
> For instance Omega can be the set of border routers between this area and that area, and the lowest ARC can actually join shortest path to two different border  routers.
>
> 3) ARCs enable load balancing with recursive properties.
> If an ARC is congested at one edge, traffic can be more balanced towards the other. If both edges are congested, the congestion can be pushed back to the edge of incoming ARCs.
>
> In fact, the red and blue tree are completely non overlapping and that's probably an exaggerated property that yields a heavy cost.
> With ARCs, we never to build end to end non-congruent paths though we know they exist.
>
> Did you consider how that impacts the bi-casting solutions?
>
> Cheers,
>
> Pascal
>
>
> -----Original Message-----
> From: Gábor Sándor Enyedi [mailto:[email-masked]]
> Sent: mardi 16 octobre 2012 12:09
> To: Pascal Thubert (pthubert); [email-masked]
> Cc: Dirk Anteunis (danteuni); Patrice Bellagamba (pbellaga)
> Subject: RE: Ears and ARCs
>
> Great summarization, thanks. Just some small notes to this, which may make the difference a bit clearer for the WG:
>
> - In basic version, MRT can correct one failure, while ARCs can correct one per ARC, which means that if there is a lucky multi-failure situation, ARCs may solve it, while the basic MRT can't.
> - Current MRT is designed in this way (i.e. that it can avoid only one failure), since avoiding multiple failures has its price: in some single failure cases, you may need to reroute packets multiple times with ARCs. Since rerouting means that a packet is using links and nodes multiple times (once in both direction), we thought that this is a greater problem then to wait for IGP when there are multiple unrelated failures at the same time.
> As an example consider a network very similar to the one in Pascal's example:
>
> 2 -- X1 -- 3
> |          |
> |          |
> 1 -- X2 -- 4
> |          |
> |          |
> ---Omega ---
>
> Let the ARCs be similar:
>
> 2<=> X1 <=>3
> |          |
> V          V
> 1<=> X2 <=>4
> |          |
> |          |
> -->Omega <--
>
> If now node 1 goes down, then node 2 will reroute, packet will be decapsulated at node 4, and if we're unlucky and the shortest path would be 4->X2->1->Omega, X2 will need to reroute again.
>
> So there is a * tradeoff *: basic MRT avoids single node or link failures, while ARCs may hit a single failures multiple times. It's a management decision which one is better.
>
> What is important to mention is that all the previous was true for basic MRT. However, it is very easy to see that the endpoint of the MRT detour is not needed to be terminated at the destination (e.g. the egress router), but it can be at several other nodes, e.g. at nodes, which are strictly closer to the destination; this is what we call "endpoint selection". Naturally, it is possible to select not only closer nodes as endpoints, when we can guarantee to avoid loops, so with some endpoint selection algorithm we may hit a single failure multiple times. The most exciting is that with a proper ear selection (i.e. with selecting the ears using the algorithm described in ARC draft), and using proper endpoint selection (i.e. endpoint is the end of the ear), we can get EXACTLY the same packet path, as with ARCs. :) Moreover, if I understood ARCs correctly, we can even reproduce the effect of "combs".
>
> Thus, I think that there is so much common in the two approaches that we may need to consider to merge the two together somehow.
>
> Gabor
>
>
>
>
> ________________________________
>
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Pascal Thubert (pthubert)
> Sent: Saturday, October 13, 2012 6:59 PM
> To: [email-masked]
> Cc: Dirk Anteunis (danteuni); Patrice Bellagamba (pbellaga)
> Subject: Ears and ARCs
>
>
>
> Dear WG:
>
>
>
> I received an unicast a question that was, bascally, what's the difference between MRT and ARCs.
>
>
>
>
>
> ---------- Forwarded message ----------
> From:
> To:
> Cc:
> Date:
> Subject:
> perties, up to us to find interesting applications and maybe find new solut=
> ions to existing problems. The core of that tool is the reversible link, so=
>  that we form downwards U-shaped arcs as opposed to arrows for routing.
>
> =20
>
> But maybe the simpler approach is to make an exercise and see what we get -=
>  my current understanding here, G=E1bor please correct me if I'm wrong -.
>
> =20
>
> So, say we have this simple network.=20
>
> =20
>
>  2 --- 3
>
>  |     |
>
>  |     |
>
>  1 --- 4
>
>  |     |
>
>   |     |
>
> Destination
>
> =20
>
> I illustrated naming the routers with a value that matches my understanding=
>  of the values of the partial order, to make things simple.
>
> =20
>
> We end up with 2 ARCs and 2 ears, which are basically collocated. The ARC v=
> iew is
>
> =20
>
> =20
>
> =20
>
>  2 <=3D> 3
>
>  |     |          where links 2 - 3 and 1 - 4 are reversible.
>
>   V     V
>
>  1 <=3D> 4
>
>   |     |
>
>   V     V
>
> Destination (Omega)
>
> =20
>
> A first property of the ARCs can be seen immediately. ARCs are hierarchical=
>  routing friendly.=20
>
> We can collapse each ARC to simplify the representation which becomes:
>
> =20
>
>    2
>
>   | |
>
>   V V
>
>    1
>
>   | |
>
>   V V
>
> Destination
>
> =20
>
> =20
>
> If we break any link both ears and ARCs provide an alternate route, that's =
> FRR for you. Now let us see what happens with more than one breakage.
>
> There are double breakages that isolate a piece of the network, say if link=
> s 2 - 1 and 3 - 4 both break, there is no solution in the world that can ke=
> ep 3 connected to the Destination.=20
>
> =20
>
> Say now that 3 - 4 and 1 - Destination are both broken a 2 has a packet to =
> send.
>
> =20
>
> =20
>
>  2 --- 3
>
>  |     |        =20
>
>   V     X
>
>  1 --- 4
>
>   |     |
>
>   X     V
>
> -------------Destination (Omega)
>
> =20
>
> =20
>
> - With ears, using the increasing order 2 will pass to 3, and 3 to 4 will f=
> ail.=20
>
> So the packet is switched to decreasing order and the packet reaches 1 via =
> 2.
>
> 1 fails to send to the destination and we are screwed.
>
> =20
>
> =20
>
>  PPPPP>>       <<ppppp       2 --- 3      PPP packet progressing in increas=
> ing order
>
>  |     |       |     |       p     |      ppp packet progressing in decreas=
> ing order
>
>   V     X       V     X       p     X   =20
>
>   1 --- 4       1 --- 4       V --- 4      When packet reaches 1 must be dr=
> opped  =20
>
>   |     |       |     |       |     |      because increasing again may cau=
> se a loop           =20
>
>   X     V       X     V       X     V      =20
>
>   -----------------------------------------Destination (Omega)
>
> =20
>
> =20
>
> - With ARCS, say that bad luck the shortest path is via 3. 2 passes to 3 an=
> d 3 to 4 will fail.=20
>
> So 3 u-turns the packet along the ARC, back to 2.=20
>
> Some tagging indicates that the packet was u-turned which can happen only o=
> nce in that ARC.
>
> =20
>
>  2--p->3       2<=3D=3Dp=3D3       2 --- 3       2 --- 3       2 --- 3   -p=
> -> in shortest path  =20
>
>   |     |       |     |       p     |       |     |       |     |   =3Dp=3D=
>> vs. returned       =20
>
>   V     X       V     X       V     X       V     X       V     X        pa=
> cket
>
>  1 --- 4       1 --- 4       1 --- 4       1=3D=3Dp=3D>4       1 --- 4
>
>   |     |       |     |       |     |       |     |       |     p   packet =
> reaches Omega
>
>   X     V       X     V       X     V       X     V       V     V
>
>   ------------------------------------------------------------------Destina=
> tion (Omega)
>
> =20
>
> say that bad luck again the shortest path for 2 is via 1.
>
> 2 passes to 1 and since the ARC is exited the marking is removed.
>
> 1 fails to send to the destination, marks the packet and sends it along its=
>  ARC.
>
> Packet reaches Destination via 4.
>
> =20
>
> =20
>
> IOW, ARCs form isolated recovery domains and allow up to as many breakages =
> as the ARC or Comb has exits, with no disruption.
>
> =20
>
> Also, ARCs can form multi-ended structures called combs with better recover=
> y capabilities than a 2-ended structure.
>
> =20
>
> For bicasting, the difference will be a bit more subtle. In a biconnected g=
> raph, ears will build non congruent path every time, but they might be far =
> away from shortest. ARCs will attempt to stay closer to shortest but may in=
> cur collisions, which are then resolved.
>
> =20
>
> Then ARCs can be employed for other purposes. We have an interesting approa=
> ch to the Olympic rings issue for instance.
>
> =20
>
> Cheers,
>
> =20
>
> Pascal
>
> =20
>
>
>
> _______________________________________________
> rtgwg mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rtgwg
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 23 Oct 2012 09:41:03 +0000

Hello Srini:

All the trouble is to determine whether a second reroute will place you back on the way of the first failure.
If you can't avoid that then the traffic could end up following a path that looks like the infinite sign, between twisted ears (that must hurt!).

If ears are organized as ARCs, that is they form a directed acyclic graph, and packets can exit each end of the ear, then we have the desired properties. 
But then, hey, ears became ARCs in the process; just place a cursor somewhere and that we inherit all sorts of good properties on the way like shortest path, load balancing and optimized bicasting. 

In the meantime, the partial order that Gábor described in this thread in end-to-end, and so it builds 2 non-congruent end-to-end paths.
Though this is what he, too, clearly wants to achieve next, the current description fails to isolate and organize smaller recovery domains, like ARCs.

The paper you indicate seems to be generalizing MRT to build more than 2 trees; how does this change the bottom line?

Cheers,

Pascal

-----Original Message-----
From: Srini [mailto:[email-masked]] 
Sent: lundi 22 octobre 2012 20:45
To: [email-masked]; Pascal Thubert (pthubert); [email-masked]; Patrice Bellagamba (pbellaga)
Subject: Re: rtgwg Digest, Vol 94, Issue 12

Dear Pascal & Gabor:

I was looking at the examples that Pascal gave.  One of the key points that's missed in MRT can tolerate at most one link failure in an ear.
Once the packet moves from one ear to another, it can tolerate another failure.  If you assume that you have one bit that indicates whether you have seen a failure or not, you can view it as this being reset every time the packet moves from one ear to another.

Path Splicing with Guaranteed Fault Tolerance T. Erlebach and A. Mereu GLOBECOM 2009

With this the behavior of MRT and ARC are the same in the examples that Pascale listed out in the email below.

Best regards,
Srini.

On Thu, Oct 18, 2012 at 12:00 PM,  <[email-masked]> wrote:
> Cc: "Dirk Anteunis \(danteuni\)" <[email-masked]>, "Patrice 
> Bellagamba \(pbellaga\)" <[email-masked]>
> Subject: more subtle differences between Ears and ARCs Hello Gábor
>
> perties, up to us to find interesting applications and maybe find new 
> solut= ions to existing problems. The core of that tool is the 
> reversible link, so=  that we form downwards U-shaped arcs as opposed to arrows for routing.
>
> =20
>
> But maybe the simpler approach is to make an exercise and see what we 
> get -=  my current understanding here, G=E1bor please correct me if I'm wrong -.
>
> =20
>
> I illustrated naming the routers with a value that matches my 
> understanding=  of the values of the partial order, to make things simple.
>
> =20
>
> We end up with 2 ARCs and 2 ears, which are basically collocated. The 
> ARC v= iew is
>
> =20
>
> =20
>
> =20
>
>  2 <=3D> 3
>
> A first property of the ARCs can be seen immediately. ARCs are 
> hierarchical=  routing friendly.=20
>
> If we break any link both ears and ARCs provide an alternate route, 
> that's = FRR for you. Now let us see what happens with more than one breakage.
>
> There are double breakages that isolate a piece of the network, say if 
> link= s 2 - 1 and 3 - 4 both break, there is no solution in the world 
> that can ke= ep 3 connected to the Destination.=20
>
> =20
>
> Say now that 3 - 4 and 1 - Destination are both broken a 2 has a 
> packet to = send.
>
> =20
>
> =20
>
>  2 --- 3
>
>  |     |        =20
>
>   V     X
>
>  1 --- 4
>
>   |     |
>
>   X     V
>
> So the packet is switched to decreasing order and the packet reaches 1 
> via = 2.
>
> - With ARCS, say that bad luck the shortest path is via 3. 2 passes to 
> 3 an= d 3 to 4 will fail.=20
>
> Some tagging indicates that the packet was u-turned which can happen 
> only o= nce in that ARC.
>
> =20
>
> 1 fails to send to the destination, marks the packet and sends it 
> along its=  ARC.
>
> IOW, ARCs form isolated recovery domains and allow up to as many 
> breakages = as the ARC or Comb has exits, with no disruption.
>
> =20
>
> Also, ARCs can form multi-ended structures called combs with better 
> recover= y capabilities than a 2-ended structure.
>
> =20
>
> For bicasting, the difference will be a bit more subtle. In a 
> biconnected g= raph, ears will build non congruent path every time, 
> but they might be far = away from shortest. ARCs will attempt to stay 
> closer to shortest but may in= cur collisions, which are then resolved.
>
> =20
>
> Then ARCs can be employed for other purposes. We have an interesting 
> approa= ch to the Olympic rings issue for instance.
>
> =20
>
> Cheers,
>
> =20
>
> Pascal
>
> =20
>
>
>