11.20.2012

A Visual Approach to Mutual Redistribution Loops

When a system becomes sufficiently complex, so as to confound our efforts to predict its behavior, we begin speaking of probabilistic, rather than deterministic, outcomes. The convergence of mutually redistributed routing domains is often discussed probabilistically, forcing engineers to rely on lab results, rules-of-thumb, and intuition for guidance during design. And while misconfiguration no doubt lies at the bottom of nearly all pathological behaviors that emerge, I would wager these more often stem from a failure of imagination than cavalier planning.

My intent is to elevate the level of discourse regarding mutual redistribution loops and introduce tools that permit objective, accurate predictions to be made easily, for all but the most unlikely topologies. To accomplish this, I need to introduce two new concepts: a modest notation by which redistributed routes and their corresponding routing domains may be classified, called D-notation, and a simple diagramming scheme, consisting of what I call Juno diagrams. These are intended only as tools to aid discourse and can by no means be regarded as rigorous models of behavior—though I feel my own predictive powers have benefited greatly. That said, I hasten to add that neither idea is beyond improvement nor reproach: both are very young and can only benefit from critical assessment.

The next two sections introduce both D-notation and Juno diagrams. Following these is a section on the construction and interpretation of Juno diagrams, along with a few illustrative examples. A final section will then look briefly at loop classification.

D-notation

Where mutual redistribution is concerned, routing information loops form whenever a redistributed route is preferred over a non-redistributed route, or—more generally—a route redistributed fewer times. If every route were accompanied by a redistribution counter, to be incremented upon each redistribution, the route with the lowest counter could be preferred, avoiding the entire problem. Of course, there is no such counter, but D-notation provides us a convenient way to speak as if there were.

The "D" in D-notation stands for "Domain," and it merely establishes a common language for quantifying how many routing domains removed a particular route is from its origin. Put another way, D-notation counts the number of times a route has been redistributed. For example, a D0 route is a route that has not been redistributed, residing solely within its originating domain. Were this route to be redistributed, we would say that the D0 route now supported a D1 counterpart in a neighboring domain. Redistributing the route again would produce a D2 route, and so on. In the general case, it is also permissible to refer to Di and Di+1 routes rather than speak of a particular i. One might also refer to the totality of Di routes as D0...n, where Dn always refers to the largest possible i, given the topology.

Fig. 1 - A D0 route supports D1 and D2 counterparts

Fig. 2 - Routes and their corresponding domains may be discussed relative to one another

We might also speak of an entire routing domain as a Di domain with respect to a particular route. In this way, we can recount a crude history of a route's life over the course of its (potentially) many redistributions, discussing preceding and succeeding domains as D0 and D1, Di and Di+1, or Dn-1 and Dn. It is also possible for a domain to assume multiple values for i, as when a routing information loop is formed. Bear in mind, D0 must at all times refer to the domain of origin to prevent ambiguity. It may be tempting to refer to any preceding domain as D0, starting wherever one left off, but this only promotes confusion. The general forms of Di and Di+1, or Di-1 and Di, should make adequate substitutes for discourse, if they are required at all.

Fig. 3 - Redistributing Di routers are also Di+1 routers

For routers that lie within a Di domain, we naturally refer to these as Di routers. In the case of redistributing routers, we acknowledge these as both Di and Di+1 routers, as they have an equal claim to both domains. When the distinction between redistributing and non-redistributing Di routers must be made, the terms edge and internal may be used, where internal Di routers do not perform redistribution. To give a flavor of the structure implied, consider the statement, "a D0 router installs a D1 route." The only way a D0 router can learn a D1 route is if that router lies at the edge of D0 and D1. Otherwise, the route would have to be redistributed back into D0 from D1, whereby internal D0 routers would learn a D2 route, not a D1 route.

Fig. 4 - Internal routers, by definition, do not perform redistribution

Caveats

A potential caveat of D-notation is that it inherently treats routes as abstract objects, separate from the mechanisms by which they propagate. On the one hand, the reliance of Dnn-1, n-2, ..., 1 routes on their D0 counterpart creates the sense that any Di route is merely a shadow or reflection of the D0 route that led to its creation. (I consider this analagous to the way in which feedback may only occur between two mirrors made to face one another; in doing the opposite, this feedback is immediately broken.) On the other hand, if a D0 route were to meet its Dn counterpart, so to speak, it would fail to recognize its own offspring, suggesting the Dn route has just as much substance as the D0 route. Certainly, in the case of self-stabilizing (or fowarding) loops, where a D2 route usurps its D0 progenitor, the presence or absence of the D0 route becomes inconsequential. This is rather like a bad Twilight Zone episode, in which some sinister doppelgänger assumes the identity of its ill-fated double.

Three Stages

Let us now turn to matters more concrete. Using D-notation, we can identify, in a concise way, three key events or stages that lead to pathological behavior in a mutually redistributed internetwork. These are:

1. Di routers install Di+1 routes
2. Di routers propagate Di+2 routes
3. Di routers install Di+2 routes

Fig. 5 - At stage 1, edge routers install routes learned from their connecting domains

At stage 1, looped routes merely become candidates for redistribution, whereas, at stage 2, the looped (Di+1) routes are redistributed and advertised. By the time stage 3 is reached, Di internal routers have begun learning and installing the looped (Di+2) routes: the damage is done. In the worst case, stage 3 sees other Di edge routers install the looped (Di+2) routes, creating either route oscillation or self-stabilizing routing loops that persist after advertisement of the instigating D0 route has ceased.

Fig. 6 - At stage 2, edge routers redistribute Di+1 routes, advertising Di+2 routes into Di

Fig. 7 - Stage 3 occurs when Di routers install Di+2 routes

Fortunately, there are corrective actions that may be taken for each stage, and intervening at an earlier stage prevents all later ones. Summarization, despite its indifference to any of the three stages, can be effective but depends strongly on the topology and can create new problems. Metric manipulation, in those topologies for which it proves effective, can prevent stage-3 behavior while permitting stage-1 and -2 events. AD (administrative distance) manipulation can be used to prevent stage-1 behavior in topologies involving two routing domains but is insufficient for topologies in which a high-AD domain lies between two low-AD domains, or vice versa. A more direct approach, route filtering, can be quite effective in stopping stage-1 or -2 behavior but can result in loss of routing in some failure scenarios. Route filtering can also permit Di edge routers to prefer Di+1 over Di routes, but this behavior may be acceptable under certain conditions.

An Appeal

The reframing of familiar tools and troubles in the language of D-notation has been tedious, but necessary, work. Yet the reader may still feel D-notation's importance is not evident, or its use, not justified. Indeed, augmenting a complex network with a new system of notation may seem to defeat the purpose of establishing a convenient basis for discourse. But D-notation—rather than collapsing the network's complexity—seeks to ease discussion through calculated abstraction and the imposition of a well-defined structure. Put another way, D-notation abbreviates rather than simplifies, describing complex events in a more concise and modular form, and I believe this is a crucial first step towards eventually automating the detection and mitigation of routing loops.

For actually solving mutual redistribution problems, we must instead rely on D-notation's visual expression: Juno diagrams. It is to these that we turn next.

Introduction to Juno Diagrams

When trying to predict the converged state of a network involving mutual redistribution, the main difficulty lies in holding, in one's mind, a rather long chain of cause and effect. To make matters worse, several scenarios must be tested before one can be satisfied of the final design, and often a balance must be struck between fulfillment of the requirements and acceptable levels of extraneous behavior. Of course, when one variable is altered, its effect on the whole delicate chain must be reassessed to ensure the integrity of the design.

This can be taxing. More crucially, during an examination—or, far worse, while troubleshooting—this process can be time-consuming. Having a simple way to record the effects of mutual redistribution in a given network eliminates the hassle of remembering chains of cause and effect for several scenarios. If the representation is visual, problem assessment is made faster, saving precious minutes that could be spent elsewhere. And, when used as an aid to design, the final result may also stand as finished documentation.

Fig. 8 - A sample stage-1 diagram: RIP/OSPF mutual redistribution

Juno diagrams (so named for their resemblance to the letters j-u-n-o) visually describe what happens at each of the three stages expressed by D-notation. Each diagram consists of several arrows representing (in stage-1 and -2 diagrams) the flow of information in the control plane or (in the case of stage-3 diagrams) next-hop vectors in the forwarding plane. The arrows in stage-1 and -2 diagrams are also annotated with the corresponding routing domain's AD--and route-type or metric, where relevant.

Fig. 9 - Here, stage-2 pathology manifests as a potential metric conflict

New information is conveyed in each stage's Juno diagram. Stage-1 diagrams help identify AD conflicts and inform the construction of stage-2 diagrams. Stage-2 diagrams provide information about the converged network (after race conditions), metric conflicts, and the extent of the damage caused by loops. Stage-3 diagrams, while not essential to solving mutual redistribution problems, are useful for predicting the flow of traffic once the network converges. Moreover, stage-3 diagrams tend to give a better sense of how metrics affect the forwarding plane when loops are present.

Fig. 10 - In the worst case, a forwarding loop develops

Three Stages in Juno

For a topology with two routing domains, two stage-1 diagrams would be used to describe internally injected routes, one for each domain. With three domains, three stage-1 diagrams would be needed, and so on. When connected or static routes are redistributed, additional diagrams may be required, depending on the routing protocol in question. For example, RIP has no concept of internal and external routes: a diagram depicting an externally injected route in RIP is identical to a diagram that depicts an internally injected one. The same could not be said of EIGRP or OSPF.

Fig. 11 - AD conflicts are readily found in stage-1 diagrams

Stage-2 diagrams make explicit the effects of stage-1 events, and thus rely on stage-1 diagrams for the locations of AD conflicts. For each stage-1 diagram, one or more stage-2 diagrams may be constructed, but multiple stage-2 diagrams are only required to observe the effects of race conditions. Topologies with race conditions can converge to one of several stable states, and each state may be depicted by its own stage-2 diagram. In the case of unstable topologies, namely those exhibiting perpetual route oscillation, stage-2 diagrams make explicit the presence of improper metrics.

Fig. 12 - Stage-2 diagrams readily expose potential metric conflicts

For each stage-2 diagram, a corresponding stage-3 diagram may be constructed. Stage-3 diagrams indicate each router's possible next-hops with arrows pointing from one router to the next. The resulting directed graph can then be used to observe the possible paths packets will follow. While not very useful for solving mutual redistribution problems, stage-3 diagrams can be used to predict or confirm symptoms observed in a network troubled by routing loops. That they contain full topological detail, however, makes them unwieldy for all but the simplest networks.

Fig. 13 - In the best case, a metric conflict results in sub-optimal routing

By now, the reader should have a firm grasp of Juno diagrams and their purpose, but this is hardly adequate for making one's own. The next section contains specific instructions for constructing and interpreting Juno diagrams.

Constructing Juno Diagrams

Content forthcoming...

Loop Classification

Di     ~ Di+2  ^  Di     > Di+2 =>  sub-optimal routing
Di     ~ Di+2  ^  Di+2 > Di     =>  self-stabilizing (forwarding) loop
Di+1 ~ Di+3  ^  Di+3 > Di     =>  route oscillation

2 comments:

  1. very interesting, can you continue on the constructing and interpretation of Juno Diagrams? Thanks

    ReplyDelete
    Replies
    1. Admittedly, it's rather irresponsible of me to have let this languish.

      In truth, it took me nearly a year to decide that I should publish even this, but this was purely because of my desire to ensure I wasn't merely reinventing the wheel. The delay, now, is born, first, of a whirlwind of travel and work activity that recently ensued and, second, of my desire to ensure the resulting methodology is as intuitive as possible. I can assure you, I have not forgotten the problem, and I still look forwarding to articulating the solution. Even now, I use Juno diagrams to quickly predict sticking points in topologies I encounter, or to test my assumptions in a design. But the decisions I make while drawing these stem from tacit knowledge, and I must wrest this information from the prison of my skull--often a frustrating endeavor--before I can share a formal process.

      I will tell you that tracing the advertisements accepted by domain border routers comes first. Where multiple arrowheads meet, these are understood to be points of possible contention, and the process of route-selection (AD and route-type) must be considered to determine which advertisements will become candidates for redistribution. The resulting diagram completely describes stage-1 behavior.

      To construct the corresponding stage-2 diagram, any resulting ambiguity in the stage-1 diagram is removed by selecting only one of the possible scenarios. Arrows representing newly redistributed, D2 routes are then drawn from the advertising border routers to all other border routers within the D2 domain. Whether the D2 protocol is link-state or distance-vector decides which, if any, of these arrows may be removed to simplify the diagram, but this isn't crucial. Now, where arrowheads meet, the process of route-selection (AD, route-type, and metric) must be considered to determine which D2 advertisements, if any, will become candidates for redistribution. At this point, D2 routes redistributed by D1 routers create forwarding loops. Route oscillation is only possible where Di+3 routes are preferred over their Di counterparts, and this becomes surprisingly easy to see in the stage-2 diagram.

      This doesn't quite cover all the possibilities, but I hope it serves as a good starting point. In the near future, I fully intend to outline the entire process as a simple, step-by-step approach, complete with examples, and proofs of the proposed loop classifications. I'd also like to include an easy-to-reference table of the various route filtering methods and what levels of extraneous behavior they permit.

      Delete