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 protected]> 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 protected] > > 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 protected] > > You can reach the person managing the list at > [email protected] > > 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 protected]> > To: "Gábor Sándor Enyedi" <[email protected]>, > "[email protected]" <[email protected]> > Cc: "Dirk Anteunis \(danteuni\)" <[email protected]>, "Patrice Bellagamba > \(pbellaga\)" <[email protected]> > 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 protected]] > Sent: mardi 16 octobre 2012 12:09 > To: Pascal Thubert (pthubert); [email protected] > 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 protected] [mailto:[email protected]] On Behalf Of > Pascal Thubert (pthubert) > Sent: Saturday, October 13, 2012 6:59 PM > To: [email protected] > 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 protected] > https://www.ietf.org/mailman/listinfo/rtgwg > _______________________________________________ rtgwg mailing list [email protected] https://www.ietf.org/mailman/listinfo/rtgwg
