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. >From the draft, hopefully it appears that an ARC is a new tool with new >properties, up to us to find interesting applications and maybe find new >solutions 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. But maybe the simpler approach is to make an exercise and see what we get - my current understanding here, Gábor please correct me if I'm wrong -. So, say we have this simple network. 2 --- 3 | | | | 1 --- 4 | | | | Destination I illustrated naming the routers with a value that matches my understanding of the values of the partial order, to make things simple. We end up with 2 ARCs and 2 ears, which are basically collocated. The ARC view is 2 <=> 3 | | where links 2 - 3 and 1 - 4 are reversible. V V 1 <=> 4 | | V V Destination (Omega) A first property of the ARCs can be seen immediately. ARCs are hierarchical routing friendly. We can collapse each ARC to simplify the representation which becomes: 2 | | V V 1 | | V V Destination 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 links 2 - 1 and 3 - 4 both break, there is no solution in the world that can keep 3 connected to the Destination. Say now that 3 - 4 and 1 - Destination are both broken a 2 has a packet to send. 2 --- 3 | | V X 1 --- 4 | | X V -------------Destination (Omega) - With ears, using the increasing order 2 will pass to 3, and 3 to 4 will fail. 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. PPPPP>> <<ppppp 2 --- 3 PPP packet progressing in increasing order | | | | p | ppp packet progressing in decreasing order V X V X p X 1 --- 4 1 --- 4 V --- 4 When packet reaches 1 must be dropped | | | | | | because increasing again may cause a loop X V X V X V -----------------------------------------Destination (Omega) - With ARCS, say that bad luck the shortest path is via 3. 2 passes to 3 and 3 to 4 will fail. So 3 u-turns the packet along the ARC, back to 2. Some tagging indicates that the packet was u-turned which can happen only once in that ARC. 2--p->3 2<==p=3 2 --- 3 2 --- 3 2 --- 3 -p-> in shortest path | | | | p | | | | | =p=> vs. returned V X V X V X V X V X packet 1 --- 4 1 --- 4 1 --- 4 1==p=>4 1 --- 4 | | | | | | | | | p packet reaches Omega X V X V X V X V V V ------------------------------------------------------------------Destination (Omega) 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. IOW, ARCs form isolated recovery domains and allow up to as many breakages as the ARC or Comb has exits, with no disruption. Also, ARCs can form multi-ended structures called combs with better recovery capabilities than a 2-ended structure. For bicasting, the difference will be a bit more subtle. In a biconnected graph, 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 incur collisions, which are then resolved. Then ARCs can be employed for other purposes. We have an interesting approach to the Olympic rings issue for instance. Cheers, Pascal _______________________________________________ rtgwg mailing list [email protected] https://www.ietf.org/mailman/listinfo/rtgwg
