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... - 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. [] 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. - 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] [] 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] (where # is the vertical version of = ) [] 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 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). [] 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 ; ) 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. [] 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). 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... :) [] Please save some time for chats in Atlanta, Cheers, Pascal
_______________________________________________ rtgwg mailing list [email protected] https://www.ietf.org/mailman/listinfo/rtgwg
