Subject: FW: draft-thubert-rtgwg-arc

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 2 Oct 2012 16:48:01 +0000

[resending due to excess size ]

Dear Routing area;

About http://www.ietf.org/id/draft-thubert-rtgwg-arc-00.txt

The ARC technology derives from some internal research at cisco, and following that line of thought, we found a number of interesting properties that we want to share with you.

Some of you already know about ARCs. This is not yet another FRR solution, but rather another way of looking at a routing topology and forwarding. Instead of following the arrows along a path, a packet will cascade from arc to arc, each arc providing at least 2 edges that the packet can use to progress. Certainly, ARCs can be used for fast reroute, but there are tons of other applications. This particular draft mainly presents the concepts, and will defrer to more drafts to specify actual solutions for the specific problems that we want to address with ARCs.

We have begun recently to open the technology for particular applications, in particular at ISA100 and IEC SC65C in the context of industrial wireless networking. Those networks require multiple forwarding solutions for each node and a packet may hit multiple transient failures along its way over a multihop wireless mesh.  Industrial WSN is thus a practical use case for which simple DAGS cannot apply and where even the MRT approach is not sufficient.

As you go through the draft, you'll find that an ARC topology is made of multiple ARCs and that each ARC allows at least one breakage with the FRR low packet loss. You’ll find that an ARC topology can be made to follow the SPF path in normal operation and yet provide an alternate for all nodes in a biconnected graph. You’ll find that monoconnected zones are easily isolated and that the proposed computation can recurse there to obtain a maximal redundancy.

An ARC topology can be exploited in classical routing or in MPLS. The recovery can be data plane or control plane which provides additional capabilities. Because ARCs are (at least) dual ended, an ARC topology also enables load balancing and a recursive overflow management to take the traffic away from the pain points. There's probably a lot more, but we'll have to discover that together.

About IPR: Stewart recommended that I talk to Alia (and effectively Joel) in Taipei to make sure that the IPR cisco has on ARC is not on the way of MRT, and we concluded that these were effectively 2 different technologies. So cisco did not claim IPR regarding MRT but we certainly have IPR on ARCs. We'll post ASAP on that.

Please let us know if this approach triggers interest. We wish to discuss ARCs during the RTGWG meeting in Atlanta and will be asking for a slot from the chairs.

Cheers,

Pascal

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Wed, 3 Oct 2012 17:26:48 +0200

Hi Pascal,
 
I think Alia was wrong, and ARC is extremely close to MRT. Unfortunately, I can't be completely sure, since I only read about ARC today, but I think that the phrase "ARC" is what MRT calls "ear". To be more precise, ARCs seems to be special ears, which must meet with some extra requirement, namely that you can get a shortest path along a well defined order of the ears. Could you please read through the MRT draft and help me to find the fundamental difference between the concept of ear and ARC?
 
Gabor
 
PS: No doubt, there is some difference between the two techniques, since packets leave the detour when it leaves an ARC/ear (if I understood that correctly). However, this behavior can easily be reproduced with MRT, if we pop the packets from the detour not at the destination/egress router, but at the endpoint of the ear. Actually this is a special case of what we call "endpoint selection" (and currently working on); MRT detours do not need to end at the destination, but packets can be put back to the shortest path at several other nodes (e.g. at a node closer to the destination), so that is worth to compute a good endpoint... one such endpoint can be the end of the ear, if the ears are selected as you do.
 
Currently with MRT we are working on 
1. what should be the specific algorithm to calculate MRTs
2. what should be the endpoint of the detours
 
ARC seems to me as a specific combination of 1+2.

________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf Of Pascal Thubert (pthubert)
Sent: Tuesday, October 02, 2012 6:48 PM
To: [email-masked]
Subject: FW: draft-thubert-rtgwg-arc

Dear Routing area;

As you go through the draft, you'll find that an ARC topology is made of multiple ARCs and that each ARC allows at least one breakage with the FRR low packet loss. You'll find that an ARC topology can be made to follow the SPF path in normal operation and yet provide an alternate for all nodes in a biconnected graph. You'll find that monoconnected zones are easily isolated and that the proposed computation can recurse there to obtain a maximal redundancy.

Cheers,

Pascal

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 3 Oct 2012 17:23:15 +0000

Hi Gabor:

[Gabor] I think Alia was wrong, and ARC is extremely close to MRT. Unfortunately, I can't be completely sure, since I only read about ARC today, but I think that the phrase "ARC" is what MRT calls "ear". To be more precise, ARCs seems to be special ears, which must meet with some extra requirement, namely that you can get a shortest path along a well defined order of the ears. Could you please read through the MRT draft and help me to find the fundamental difference between the concept of ear and ARC?

[Pascal] I'll have a close look at those ears... Alia showed Joel and I an algorithm in which I did not recognize -at all- anything related to ARCs, but I'm certainly willing to go to the bottom of it.
I hope we can chat at the next IETF and we'll figure if cisco needs to publish some IPR about MRT drafts and/or to present additional potential prior art to the USPTO for our pending claims.
In any case I'll focus on the technical for now:

[Pascal] It is important to note that including the shortest path is not a requirement for ARCs but just a preferred option for our applications. Conceptually you could pick a first arbitrary sequence of nodes with the edges at the destination, call that an arc  and add it to the destination. And again till you can't form ARCs anymore. You'll end up with an ARC set that leads to the destination with no loop and a plan B for everyone in the set. The algorithm in the draft can be optimized to cash on already explored stuff, but variations would be expected to give the same result, that is join together the lowest shortest-paths into an arc, and then attach all possible buttressing arcs to reinforce that structure. And again. After playing a number of such variations, I found that this particular expression of the oLAF algorithm was the easiest to communicate.

[Pascal] From the FRR perspective, the fundamental difference, IMHO, is that ARC does not build trees (one red and one blue tree as I understand MRT does) but a DAG of ARCs that cascades to the destination(s). With blue and red trees, upon a first failure we need to paint the packet, say, in blue. If the blue tree is broken later then we're screwed - at least that is my understanding. ARCs, on the other hand, create small domains where the error isolation and correction is contained. Once you leave an ARC, the packet is cleaned pure white again, and it can face the next breakage in another ARC down the cascade. Thus ARCs can sustain multiple breakages, at least one per ARC. And in a classical mesh, most ARCs are collapsed in one node. So that is a great many breakages. 

[Pascal] There are other differences: 
-> ARC is an approach rather than a FRR solution, a new tool for us to play with that replaces arrows with arcs in the way we figure routing graphs. The possibilities are quite something. 
-> The ARC generalization (comb) is multi ended, and can sustain more breakages, something like a non-equal cost multipath version of an ARC or an ear if you like.

[Gabor] PS: No doubt, there is some difference between the two techniques, since packets leave the detour when it leaves an ARC/ear (if I understood that correctly). However, this behavior can easily be reproduced with MRT, if we pop the packets from the detour not at the destination/egress router, but at the endpoint of the ear. Actually this is a special case of what we call "endpoint selection" (and currently working on); MRT detours do not need to end at the destination, but packets can be put back to the shortest path at several other nodes (e.g. at a node closer to the destination), so that is worth to compute a good endpoint... one such endpoint can be the end of the ear, if the ears are selected as you do.
 
[Pascal] I think you understand it well, and your proposition is beyond what I gathered about MRT. I'm not aware of detours though I could figure stuff from the name and your explanation. Certainly great discussions ahead.
 
[Gabor] Currently with MRT we are working on
1. what should be the specific algorithm to calculate MRTs 2. what should be the endpoint of the detours
 
[Pascal] Then you have a proposal on the table based on ARCs : ) Conceptually, it's not really detours, rather walking the current ARC or Comb till you find an exit to cascade into - that is another ARC that's nearer to the destination. Probably we may end up computing similar if not the same result. On the way ARCs will allow you to simplify the visualization of the network,  and will play ball with routing hierarchies, load balancing, etc...
 
[Gabor] ARC seems to me as a specific combination of 1+2.

[Pascal] I agree that ARC can help solve problems 1 and 2. And other problems as well. ARCs can be used to solve the Olympic rings problem in MPLS-TP for instance. Then again greats talks ahead. 

Thanks for all this Gabor,

Cheers,

Pascal

Dear Routing area;

 

Cheers,

Pascal

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 5 Oct 2012 11:54:23 +0200

Hi Pascal,

Just some notes and a simple example, which may help to find the common points:

- You should probably not focus on the trees (they are not so important, just useful to make the concept easier to understand), but on the GADAG (Generalized Almost Directed Acyclic Graph). This is the graph we get, if we combine our ears. This is something like a partial order of the nodes in the network. As far as I understood, you also have an order in the ARCs, and if you cannot get out along the increasing direction, you try the decreasing (or vice versa). The difference is that not all nodes are in a common order, just those in the same ARC.

- Here is a simple example graph. Keep in mind that this example is really simple and useful only for some rough understanding; some problems do not show up, thus I don't cover all the details. Let the destination be [Omega], and find the ARCs/ears and the GADAG in that (now, we are not interested in shortest paths, but have some arbitrary algorithm):

[Omega]----[A]-------[E]
 |          |         |
 |          |         |
 |          |         |
[D]--------[C]-------[F]
 |                    |
 |                    |
 |                    |
[G]--------[H]-------[I]

Start from the Omega, let the first ARC be made up by D-C-A, and use this order (i.e. D<C<A). Let the first ear be the same. Then the second ARC/ear can be E-F. However, with ears, you'll need to keep up order. The ear is connected to the previous at A and C, and C<A (we defined that for the previous ear), so we must have that C<F<E<A. Graphically, we can represent that with a directed graph, where edges are always pointing to the increasing direction:

[Omega]<---[A]<------[E]
 |          ^         ^
 |          |         |
 V          |         |
[D]------->[C]------>[F]

Finally, we find ARC/ear G-H-I. For ears, we need to consider that D<F, so we will have that D<G<H<I<F.

Thus, we will have this GADAG:

[Omega]<---[A]<------[E]
 |          ^         ^
 |          |         |
 V          |         |
[D]------->[C]------>[F]
 |                    ^
 |                    |
 V                    |
[G]------->[H]------>[I]

The graph view is extremely similar:

[Omega]<---[A]<------[E]
 ^          ^         ^
 |          #         #
 |          V         V
[D]<======>[C]<------[F]
 ^                    ^
 |                    |
 |                    |
[G]<======>[H]<=====>[I]

(where # is the vertical version of = )

How can we use the GADAG for routing? Start from a given node, and always increase; you will get to Omega (use the direction of the edges; when multiple edges go out from that node, select one of them). This is the increasing path. The decreasing path is the one you get when you always move in the opposite direction; you get to Omega as well (this is the reason why we call this as an Almost DAG; if you remove the root/Omega, you get a DAG).
What is important to note that if there is a directed path from X to Y, then Y>X. But in general GADAGs there can be such X and Y, where neither X>Y, nor Y>X. Thus GADAG is representing a PARTIAL order in general. This partial order is a total order in the previous example.

Endpoint selection is a method to select detour endpoints other than Omega. For example if node [I] goes down, and the shortest path from D to Omega doesn't go through [I], H can select D as an endpoint. Sending packets to other node than Omega is simple, since with a single GADAG we can compute increasing and decreasing path not only to the Omega, but to all the nodes in the network; but this is an other story far beyond the complexity we can discuss in this mail... :)

BR,

Gabor

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]] 
Sent: Wednesday, October 03, 2012 7:23 PM
To: Gábor Sándor Enyedi; Patrice Bellagamba (pbellaga); [email-masked]; Alia Atlas ([email-masked])
Cc: [email-masked]
Subject: RE: draft-thubert-rtgwg-arc

Hi Gabor:

 
 
[Gabor] Currently with MRT we are working on 1. what should be the specific algorithm to calculate MRTs 2. what should be the endpoint of the detours

Cheers,

Pascal

Dear Routing area;

 

Cheers,

Pascal

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 8 Oct 2012 06:42:31 +0000

Hello Gábor

[] resending got bounced... I snipped the original xchg.

[] I had to use HTML and play with fonts t be able to format your drawings. Please bear with me...

[] Looks like ears and arcs could obtain similar results on a given use case. This certainly does not mean we are using the same tool but clearly indicates that agree on what the improvement is about. Great :)

And yes, we have an order between ARCs (they form a DAG) but what happens inside an ARC could be anything as long as you do not loop and yet explore all the possible exits. IOW what you do inside an ARC is not necessarily correlated to what you do outside, where you're going etc...

I think it is important to create subdomains that isolate a problem. This has interesting properties when you start looking at routing hierarchies. I'm a bit enthusiastic about ARCs because they really open avenues for thinking and yet do not yield additional complexity. In fact, the DAG of ARCs topology is largely a simplification from the original mesh.

[Omega]----[A]-------[E]

|          |         |

|          |         |

|          |         |

[D]--------[C]-------[F]

|                    |

|                    |

|                    |

[G]--------[H]-------[I]

[Omega]<---[A]<------[E]

|          ^         ^

|          |         |

V          |         |

[D]------->[C]------>[F]

[Omega]<---[A]<------[E]

|          ^         ^

|          |         |

V          |         |

[D]------->[C]------>[F]

|                    ^

|                    |

V                    |

[G]------->[H]------>[I]

[] If I'm with you ... Either you follow the arrows to the end or you follow the reverse arrows to the end.

Either way you reach omega. I'm still confused what happens on a double breakage, say F has a packet and Both D-omega and F-E are broken...

: The graph view is extremely similar

[Omega]<---[A]<------[E]

^          ^         ^

|          #         #

|          V         V

[D]<======>[C]<------[F]

^                    ^

|                    |

|                    |

[G]<======>[H]<=====>[I]

[] With the ARC approach, if F has a packet  to omega and F-E is broken, F hands the pak to C;  if D is shortest path then C passes the pak D along ARC D=C=A. If D-omega is broken then the pak  sent the other way (over a backup label along the ARC of MPLS is the name of the game). So the pak ends up doing F, C, D, C, A, Omega.

[] Yep, that's what ARCs will give you. Note that if H is cursor, it may distribute traffic to its left and right for instance. F can further distribute between E and C, etc. ARCs have properties way beyond FRR

[] again yes, and  I like it :) And yes the ears could be collocated with ARCs. Though rapidly ARCs will build more complex and robust structures, eg combs, which will make the ears look like Frankenstein's ; )

[] There are cool properties with the fact that ARCs are local constructs whereas the partial order has to be end to end on a path. Now an ARC must have a metric that is more than that of the ARCs it ends into (to form a DAG).

[] Please save some time for chats in Atlanta,

Cheers,

Pascal