Ruminations on the Next Hop Philip Almquist March 25, 1993 Status of This Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress." Please check the I-D abstract listing contained in each Internet Draft directory to learn the current status of this or any other Internet Draft. Distribution of this memo is unlimited. Summary This memo discusses how routers do, can, and should decide how to use the routing information available to them to route packets. It is particularly concerned with the problems of border routers and other routers which have to choose from among routes learned from multiple routing domains, often using different routing protocols. Although many of the details of this paper are specific to the problem of forwarding Internet Protocol (IP) packets, I believe that the problems identified and the general approach to the solution would also be relevant to those working with CLNP or other connectionless Network Layer protocols. Acknowledgments This memo owes considerable debt to the IETF's Router Requirements Working Group, which started me to thinking about the issues in this paper and also reviewed several earlier drafts. I am particularly indebted to Ross Callon, who helped me understand enough about area routing to understand why the algorithm in section 4.2 is inadequate, and also pointed out several errors in my description of Integrated IS-IS. Vint Cerf and Noel Chiappa provided additional useful comments. This memo also owes considerable debt to Stanford University and BARRNet, my former employers, for supporting much of the work on this memo. 1. Introduction The fundamental thing that a router does is to receive packets, examine their headers, and decide where to send them next. I have chaired several meetings at which a group of experts (the Internet Engineering Task Force's Router Requirements Working Group) attempted to reach consensus on a precise description of how routers should make that decision. Lengthy and often heated debate produced little concrete agreement. I was rather fascinated to discover that this seemingly simple process of deciding where to send the packet next is apparently not well understood, and in fact seems to hide some difficult open questions. This memo attempts to carefully examine how a router should use the routing information available to it to decide how to route packets. A companion document, "Ruminations on Route Leaking" [1], discusses the related issue of how a router passes on routes available to it to other routers. Readers should be forewarned that the algorithms given in this memo are rather different than the ones that good router implementor would use. The reason for this is that a memo such as this one needs to describe the actions taken by routers in a way that they is concise, easy to understand, and relatively independent of the details of the particular internet and routing protocols being used. A good implementor, on the other hand, will choose algorithms which produce the same results as those in this memo but do so more quickly by sacrificing a certain amount of simplicity or generality. I believe that this memo does not recommend anything that could not be implemented efficiently but (except for the all-too-brief discussion in Section 8) the art of efficient router implementation is outside of the scope of this memo. 1.1 Overview of the Routing Function Each router maintains a "forwarding information base (FIB)", a conceptual database of all routes known to the router. In order to allow the router to choose from among the routes in the FIB, each route has various attributes associated with it. In order to maintain its FIB, a router generally belongs to one or more "routing domains." A routing domain is a collection of routers which coordinate their routing information using a routing protocol. Each router adds routes to and deletes routes from its FIB based on rules prescribed by the protocol. Most routers also allow the router's manager to manipulate the contents of the FIB through configuration or network management commands. For purposes of this memo, a router whose FIB contains routes added by such manual means can be thought of as being a member of its own (degenerate) routing domain, referred to as a "static routing domain", in addition to any routing domain(s) it may be a member of by virtue of its use of routing protocols. To facilitate route leaking [1] and the functions described in Sections 6.2 and 6.5, a router may benefit from an ability to divide its static routes among multiple static routing domains. When the router receives a packet to be forwarded, it examines attributes of the packet and compares them to values of the attributes of routes in the FIB. This allows the router to determine the appropriate route for the packet (or to determine that the packet must be discarded because no matching route is available). Because the size of the FIB would likely be unwieldy if it contained a route for each possible combination of attributes a packet might have, comparing the attributes of the packet to the attributes of the routes in the FIB is not usually a straightforward equality test of the attributes. Instead, the router uses a "route lookup algorithm" to determine which route best matches the attributes of the packet. It is important to note that the FIB talked about in this memo is not exactly the same as the forwarding table found in most routers. The FIB contains all of the current routing information which has been provided to the router by its routing domains. A router can often determine that its route lookup algorithm would never choose certain routes, and that it may therefore safely discard them. The fact that real implementations usually partially precompute the results of the route lookup algorithm in this manner is an important bit of implementation-related complexity which is nonetheless ignored throughout most of this memo. 1.2 The Problem As I shall discuss in greater detail shortly, there has traditionally been a consensus on an appropriate route lookup algorithm. Unfortunately, a number of factors have conspired to render that algorithm obsolete: - New routing protocols are being developed which require different, incompatible route lookup algorithms. Examples of such protocols in the Internet protocol suite include OSPF [6] and Integrated IS-IS [3]. - The traditional route lookup algorithm makes its decision based on only one attribute of the packet being forwarded: its destination address. There is a growing consensus that the algorithm should also consider the Network Layer quality of service (TOS) requested by the packet. Some people believe that additional attributes should also be considered in the forwarding decision. - The traditional route lookup algorithm assumes that a router is a part of (at most) one routing domain, and therefore contains no mechanism for choosing among routes to the same destination learned from different routing protocols (or multiple instances of the same routing protocol). To solve this, router implementors have had to invent a variety of policy mechanisms. Unfortunately, these mechanisms are highly implementation- dependent, contributing to the difficulties of building a network using routers from multiple vendors. 1.3 Outline of this Memo Section 2 briefly recaps the history of this topic and describes the traditional view of how routers pick routes when routing packets. Section 3 provides a generic model of how route lookup algorithms work and describes the component rules from which such algorithms are constructed. Section 4 gives concise but fairly precise descriptions of several route lookup algorithms which are used or have been proposed. It also discusses the good and bad points of each. Section 5 considers the lessons we might learn from Section 4. Is there a single "correct" route lookup algorithm? How could a router choose an appropriate route when it learns routes from several routing protocols simultaneously? Several mechanisms are discussed, and one of them (the "Meta-lookup Algorithm." approach) is picked as the most workable alternative. Sections 6 and 7 considers the Meta-lookup Algorithm approach in detail. A specific meta-lookup algorithm is proposed, along with some policy controls. Section 8 briefly considers efficient implementation. 2. Some Historical Perspective It is useful to briefly review the history of our topic. beginning with what I think of as the "classic model" of how a router makes routing decisions. This model predates IP (see, for example, reference [9]). Under this model, a router speaks some single routing protocol such as RIP [4]. The protocol completely determines the contents of the router's FIB. The route lookup algorithm is trivial: the router looks in the FIB for a route whose destination attribute exactly matches the network number portion of the destination address in the packet. If one is found, it is used; if none is found, the destination is unreachable. Because the routing protocol keeps at most one route to each destination, the problem of what to do when there are multiple routes which match the same destination cannot arise. Over the years, this classic model has been augmented in small ways. With the advent of default routes, subnets, and host routes, it became possible to have more than one routing table entry which in some sense matched the destination. This was easily resolved by a consensus that there was a hierarchy of routes: host routes should be preferred over subnet routes, subnet routes over net routes, and net routes over default routes. With the advent of variable length subnet masks, the general approach remained the same although its description became a little more complicated. We now say that each route has a bit mask associated with it. If a particular bit in a route's bit mask is set, the corresponding bit in the route's destination attribute is significant. A route cannot be used to route a packet unless each significant bit in the route's destination attribute matches the corresponding bit in the packet's destination address, and routes with more bits set in their masks are preferred over routes which have fewer bits set in their masks. This is simply a generalization of the hierarchy of routes described above, and will be referred to for the rest of this memo as choosing a route by preferring longest match. Another way the classic model has been augmented is through a small amount of relaxation of the notion that a routing protocol has complete control over the contents of the routing table. First, static routes were introduced. For the first time, it was possible to simultaneously have two routes (one dynamic and one static the same destination. When this happened, a router had to have a policy (in some cases configurable, and in other cases chosen by the author of the router's software preferred. However, this policy was only used as a tie-breaker when longest match didn't uniquely determine which route to use. Thus, for example, a static default route would never be preferred over a dynamic net route even if the policy preferred static routes over dynamic routes. The classic model had to be further augmented when inter-domain routing protocols were invented. Traditional routing protocols came to be called "interior gateway protocols" (IGPs), and at each Internet site there was a strange new beast called an "exterior gateway", a router which spoke EGP [7] to several "BBN Core Gateways" (the routers which made up the Internet backbone at the time) at the same time as it spoke its IGP to the other routers at its site. Both protocols wanted to determine the contents of the router's routing table. Theoretically, this could result in a router having three routes (EGP, IGP, and static) to the same destination. Because of the Internet topology at the time, it was resolved with little debate that routers would be best served by a policy of preferring IGP routes over EGP routes. However, the sanctity of longest match remained unquestioned: a default route learned from the IGP would never be preferred over a net route from learned EGP. Although the Internet topology, and consequently routing in the Internet, have evolved considerably since then, this slightly augmented version of the classic model has survived pretty much intact to this day in the Internet (except for routers which use the OSPF or the Integrated IS-IS protocols, which will be discussed shortly). Conceptually (and often in implementation) each router has a routing table and one or more routing protocol processes. Each of these processes can add any entry that it pleases, and can delete or modify any entry that it has created. When routing a packet, the router picks the best route using longest match, augmented with a policy mechanism to break ties. Although this augmented classic model has served us well, it has a number of shortcomings: - It ignores (although it could be augmented to consider) path characteristics such as quality of service and MTU. - It doesn't support routing protocols (such as OSPF and Integrated IS-IS) thatrequire route lookup algorithms different than pure longest match. - There has not been a firm consensus on what the tie-breaking mechanism ought to be. Tie-breaking mechanisms have often been found to be difficult if not impossible to configure in such a way that the router will always pick what the network manger considers to be the "correct" route. 3. Route Lookup Algorithms A route lookup algorithm chooses the best route (if there is one) for a packet from those available in the FIB. Conceptually, any route lookup algorithm starts out with a set of candidate routes which consists of the entire contents of the FIB. The algorithm consists of a series of steps which discard routes from the set. In this memo, these steps are referred to as "pruning rules". Normally, when the algorithm terminates there is exactly one route remaining in the set. If the set ever becomes empty, the packet is discarded because the destination is unreachable. It is also possible for the algorithm to terminate when more than one route remains in the set. In this case, the router may arbitrarily discard all but one of them, or may perform "load-splitting" by choosing whichever of the routes has been least recently used. Some steps are mandatory, and must be applied even if the set has already been reduced to a single route. Some algorithms also contain optional steps, which may be skipped if the set has already been reduced to a single route. The steps must generally be applied in order, since rearranging the steps can change the result. There are a number of common pruning rules. The route lookup algorithms in use generally use some combination of these rules. Basic Match This step discards any routes to destinations other than the destination of the packet. For example, if a packet was addressed to 36.144.2.5, this step would discard a route to net 128.12.0.0 but would retain any routes to net 36.0.0.0, any routes to subnet 36.144.0.0, and any default routes. More precisely, we assume that each route has a destination attribute, which we'll call "route.dest", and a corresponding mask, which we'll call "route.mask", to specify which bits of route.dest are significant. We'll call the IP destination address of the packet being routed "ip.dest". This step discards all routes from the set of candidate routes except those for which (route.dest & route.mask) = (ip.dest & route.mask). This is (logically, at least) the first step performed by any route lookup algorithm. Longest Match This step was described on page 5. The precise definition of Longest Match is a refinement of Basic Match, described above. After Basic Match pruning is performed, the remaining routes are examined to determine the maximum number of bits set in any of their route.mask attributes. The step then discards from the set of candidate routes any routes which have fewer than that maximum number of bits set in their route.mask attributes. Weak TOS There is a growing consensus that routers should consider quality of service requested when making their routing decisions. This could be done in a number of ways, but the one used in IP is the one I refer to as Weak T OS. Under this method, a route which has the exact TOS requested is used if there is one; otherwise, a route with the default (0000) TOS is used if there is one. Routes which have other TOS values are never used, even when they are the only available routes to the packet's destination. More precisely, we assume that each route has a type of service attribute, which we'll call "route.tos", whose possible values are assumed to be identical to those used in the TOS field of the IP header. Routing protocols which distribute TOS information fill in route.tos appropriately in routes they add to the FIB; routes from other routing protocols are treated as if they has the default TOS. We'll call the TOS field in the IP header of the packet being routed "ip.tos". The set of candidate routes is examined to determine if it contains any routes for which route.tos = ip.tos. If so, all routes except those for which route.tos = ip.tos are discarded. If not, all routes except those for which route.tos = 0000 are discarded from the set of candidate routes. Additional discussion of routing based on Weak TOS may be found in [2]. OSPF Route Class Routing protocols which have areas or make a distinction between internal and external routes divide their routes into classes, where classes are rank-ordered in terms of preference. A route is always chosen from the most preferred class unless none is available, in which case one is chosen from the second most preferred class, and so on. In OSPF, the classes (in order from most preferred to least preferred) are intra-area, inter-area, type 1 external (external routes with internal metrics), and type 2 external. As an additional wrinkle, a router is configured to know what addresses ought to be accessible via intra-area routes, and will not use inter- area or external routes to reach these destinations even when no intra-area route is available. More precisely, we assume that each route has a class attribute, called "route.class", which is assigned by the routing protocol. The set of candidate routes is examined to determine if it contains any for which route.class = "intra- area". If so, all routes except those for which route.class = "intra-area" are discarded. Otherwise, router checks whether the packet's destination falls within the address ranges configured for the local area. If so, the entire set of candidate routes is deleted. Otherwise, the set of candidate routes is examined to determine if it contains any for which route.class = "inter-area". If so, all routes except those for which route.class = "inter-area" are discarded. Otherwise, the set of candidate routes is examined to determine if it contains any for which route.class = "type 1 external". If so, all routes except those for which route.class = "type 1 external" are discarded. IS-IS Route Class IS-IS route classes work identically to OSPF's. However, the set of classes defined by Integrated IS-IS is different, such that there isn't a one-to-one mapping between IS-IS route classes and OSPF route classes. The route classes used by Integrated IS-IS are (in order from most preferred to least preferred) intra-area, inter-area, and external. The Integrated IS-IS internal class is equivalent to the OSPF internal class. Likewise, the Integrated IS-IS external class is equivalent to OSPF's type 2 external class. However, Integrated IS- IS does not make a distinction between inter- area routes and external routes with internal metrics -- both are considered to be inter-area routes. Thus, OSPF prefers true inter-area routes over external routes with internal metrics, whereas Integrated IS-IS gives the two types of routes equal preference. Best Metric Routes have metrics which allow a router to compare the relative goodness of otherwise equally attractive candidate routes. However , since metrics are meaningful only within a routing domain, it makes no sense to compare the metrics of routes learned from different routing domains. More precisely, we assume that each route has a metric attribute, called route.metric, and a routing domain identifier, called route.domain. Each member of the set of candidate routes is compared with each other member of the set. If route.domain is equal for the two routes and route.metric is strictly "inferior" for one than the other, the one with the inferior metric is discarded from the set. The determination of "inferior" is usually by a simple arithmetic comparison, though some protocols may have structured metrics requiring more complex comparisons. Policy Policy is sort of a catch-all to make up for the fact that the previously listed rules are often inadequate to chose from among the possible routes. Policy pruning rules are extremely vendor-specific. IDPR Policy A specific case of Policy. The IETF's Inter-domain Policy Routing Working Group is devising a routing protocol called Inter-Domain Policy Routing (IDPR) [8] to support true policy- based routing in the Internet. Packets with certain combinations of header attributes (such as specific combinations of source and destination addresses or special IDPR source route options) are required to use routes provided by the IDPR protocol. Thus, unlike other Policy pruning rules, IDPR Policy would have to be applied before any other pruning rules except Basic Match. Specifically, IDPR Policy examines the packet being forwarded to ascertain if its attributes require that it be forwarded using policy-based routes. If so, IDPR Policy deletes all routes not provided by the IDPR protocol. 4 Some Route Lookup Algorithms This section examines several route lookup algorithms that are in use or have been proposed. Each is described by giving the sequence of pruning rules it uses. The strengths and weaknesses of each algorithm are enumerated. 4.1 The Revised Classic Algorithm The Revised Classic Algorithm is the current version of the traditional algorithm which was discussed on page 5. The steps of this algorithm are: 1. Basic match 2. Longest match 3. Best metric 4. Policy Some implementors omit the Policy step, since it is needed only when routes may have metrics that are not comparable (because they were learned from different routing domains). The advantages of this algorithm are: 1. It is widely implemented. 2. Except for the Policy step (which an implementor can choose to make arbitrarily complex) the algorithm is simple both to understand and to implement. As I pointed out in Section 1.2, its disadvantages are: 1. It does not handle IS-IS or OSPF route classes, and therefore cannot be used for Integrated IS-IS or OSPF. 2. It does not handle TOS or other path attributes. 3. The policy mechanisms are not standardized in any way, and are therefore are often implementation-specific. This causes extra work for implementors (who must invent appropriate policy mechanisms) and for users (who must learn how to use the mechanismsficult to create consistent configurations for routers from different vendors. This presents a significant practical deterrent to multi-vendor interoperability. 4. The proprietary policy mechanisms currently provided by vendors are often inadequate in complex parts of the Internet. 4.2 The Router Requirements Algorithm The IETF Router Requirements Working Group has produced a number of draft versions of an RFC-1009 replacement. The early drafts mandated a route lookup algorithm which I will call the "Router Requirements Algorithm." This algorithm is similar to the Revised Classic Algorithm, with two important differences. The first is that it includes support for type of service routing. The second is that it attempts to extend the Revised Classic Algorithm to explicitly support routers which are in more than one routing domain, primarily by standardizing the policy mechanisms (but allowing implementors to supplement the standard mechanisms with proprietary ones). The steps in the Router Requirements Algorithm are: 1. Basic match 2. Longest match 3. Weak TOS 4. Best metric 5. Policy This model has some advantages over the Revised Classic Algorithm: 1. It supports type of service routing. 2. Its rules are written down, rather than merely being a part of the Internet folklore. 3. Partial standardization of the policy step (hopefully) would make life a lot easier for managers of those parts of the Internet where routing is complex. However, this algorithm retains some of the disadvantages of the Revised Classic Algorithm: 1. It does not handle IS-IS or OSPF route classes, and therefore cannot be used for Integrated IS-IS or OSPF. 2. Path properties other than type of service (e.g. MTU) are ignored. It is also worth noting a deficiency in the way that TOS is supported: routing protocols which support TOS are implicitly preferred when forwarding packets which have non-zero TOS values. This may not be appropriate in some cases. 4.3 The Variant Router Requirements Algorithm Some Router Requirements Working Group members have proposed a slight variant of the algorithm described in the previous section. In this variant, matching the type of service requested is considered to be more important, rather than less important, than matching as much of the destination address as possible. For example, this algorithm would prefer a default route which had the correct type of service over a network route which had the default type of service, whereas the algorithm in the previous section would make the opposite choice. The steps of the algorithm are: 1. Basic match 2. Weak TOS 3. Longest match 4. Best metric 5. Policy Debate between the proponents of this algorithm and the regular Router Requirements Algorithm suggests that each side can show cases where its algorithm leads to simpler, more intuitive routing than the other's algorithm does. In general, this variant has the same set of advantages and disadvantages that are described in the previous section, except that pruning on W eak TOS before pruning on Longest Match makes this algorithm less compatible with OSPF and Integrated IS-IS than the standard Router Requirements Algorithm. 4.4 The OSPF Algorithm OSPF uses an algorithm which is virtually identical to the Router Requirements Algorithm except for one crucial difference: OSPF considers OSPF route classes. Also, although I have listed a Policy step in the algorithm, the OSPF specification does not admit to the existence of such a step. The algorithm is: 1. Basic match 2. OSPF route class 3. Longest match 4. Weak TOS 5. Best metric 6. Policy Type of service support is optional; if disabled, the fourth step would be omitted This algorithm has some advantages over the Revised Classic Algorithm: 1. It supports type of service routing. 2. Its rules are written down, rather than merely being a part of the Internet folklore. 3. It (obviously) works with OSPF. However, this algorithm also retains some of the disadvantages of the Revised Classic Algorithm: 1. Path properties other than type of service (e.g. MTU) are ignored. 2. As in the Revised Classic Algorithm, the details (or even the existence Policy step is left to the discretion of the implementor. The OSPF Algorithm also has a further disadvantage (which is not shared by the Revised Classic Algorithm): 1. OSPF internal (intra-area or inter-area) routes are always considered to be superior to routes learned from other routing protocols, even in cases where the OSPF route matches fewer bits of the destination address. This is a policy decision that is inappropriate in some networks. Finally, it is worth noting that the OSPF Algorithm's TOS support suffers from the same deficiency noted at the end of Section 4.2. 4.5 The Integrated IS-IS Algorithm Integrated IS-IS uses an algorithm which is similar to but not quite identical to the OSPF Algorithm. Integrated IS-IS uses a different set of route classes, and also differs slightly in its handling of type of service. The algorithm is: 1. Basic Match 2. IS-IS Route Classes 3. Lonhgest Match 4. Weak TOS 5. Best Metric 6. Policy Although Integrated IS-IS uses Weak TOS, the protocol is only capable of carrying routes for a small specific subset (defined in Section 3.5 of [3] and amended by Appendix A.4 of [2]) of the possible values for the TOS field in the IP header. Packets containing other values in the TOS field are routed using the default TOS. Type of service support is optional; if disabled, the fourth step would be omitted. As in OSPF, the specification does not include the Policy step. This algorithm has some advantages over the Revised Classic Algorithm: 1. It supports type of service routing. 2. Its rules are written down, rather than merely being a part of the Internet folklore. 3. It (obviously) works with Integrated IS-IS. However, this algorithm also retains some of the disadvantages of the Revised Classic Algorithm: 1. Path properties other than type of service (e.g. MTU) are ignored. 2. As in the Revised Classic Algorithm, the details (or even the existence) of the Policy step is left to the discretion of the implementor. 3. It doesn't work with OSPF because of the dif ferences between IS-IS route classes and OSPF route classes. Also, because IS-IS supports only a subset of the possible TOS values, some obvious implementations of the Integrated IS-IS algorithm would not support OSPF's interpretation of TOS. The Integrated IS-IS Algorithm also has a further disadvantage (which is not shared by the Revised Classic Algorithm): 1. IS-IS internal (intra-area or inter-area) routes are always considered to be superior to routes learned from other routing protocols, even in cases where the IS-IS route matches fewer bits of the destination address and doesn't provide the requested type of service. This is a policy decision that may not be appropriate in all cases. Finally, it is worth noting that the Integrated IS-IS Algorithm's TOS support suffers from the same deficiency noted at the end of Section 4.2. 5. The Problem Revisited In the previous section, we examined the routing algorithms used in the Internet, as well as a couple of proposed alternative ones. Among other things, we noted that OSPF and Integrated IS-IS each require a specialized route lookup algorithm that doesn't work with any other Internet routing protocol. This is certainly unfortunate for implementors, since those who want to support both the new routing protocols and the traditional ones have to implement three different route lookup algorithms. However, things become even more problematic when a router wishes to simultaneously use multiple routing protocols. Unfortunately, the growing complexity of the Internet is requiring more and more routers to do just that. Suppose, for example, that a router is simultaneously using RIP and Integrated IS-IS, and a packet arrives at the router, waiting to be forwarded. Does the router use Integrated IS-IS's route lookup algorithm, or the Revised Classic Algorithm that is commonly used with RIP? Does it try both, and hope that they both give the same answer? The rest of this section looks at several ways out of this dilemma that have been proposed. 5.1 The "Master Protocol" Approach In the "master protocol" approach, a single routing protocol is given responsibility for maintaining the routing table. A route lookup algorithm appropriate for use with that routing protocol is used. Routes learned from other routing protocols are "redistributed" into the master protocol, which generally considers these routes to be "external" (where the meaning of "external" depends on the particular master protocol in use). The obvious advantage to this approach is that it requires no change to whatever route lookup algorithm is already being used. However, there are a number of substantial drawbacks: 1. If the master protocol used is one which automatically treats "external" routes as inferior, the protocol's own routes will always be considered better than routes learned from other routing protocols, even in cases where the protocol's own route matches fewer bits of the destination address and doesn't provide the requested type of service. This is a policy decision which may not be appropriate in all cases. 2. Redistributing routes into the master protocol can be non-trivial if the protocol whose routes are being redistributed uses a route lookup algorithm different than that used by the master protocol(1). ---------------------------------------------------------------------- 1. I need to think about this some more... ---------------------------------------------------------------------- 3. Most implementations assume that routes redistributed into the master protocol ought to be announced to other routers by the master protocol. This may or may not be desirable. 5.2 The "Rank Ordering of Routing Protocols" Approach In this approach, the routing protocols in use are ranked according to a preference ordering. There is no global FIB; each routing protocol maintains its own, separate routing database. When a packet is to be routed, the most preferred routing protocol is queried to see if it has a route to the destination. That protocol uses a route lookup algorithm which is appropriate to it to determine whether it has a route. If so, that route is used; if not, the second most preferred routing protocol is queried, and so on, until either a route is found or all of the routing protocols have been queried. This approach also has a pleasant simplicity, and avoids some of the problems of the previous approach. However: 1. It potentially requires several route table lookups for each packet switched. 2. It is often not possible to rank order the protocols in a sensible way. More often, each protocol will supply some routes which the router would like to consider primary and some routes which it would like to consider to be backup routes. 3. A route provided by a more preferred routing protocol will be chosen even if it matches fewer bits of the destination address than a route provided by a less- preferred protocol. This may or may not be desirable. 5.3 The "Meta-lookup Algorithm" Approach As in the Rank Ordering approach, each routing protocol that is being used maintains its own independent routing database. When a packet is to be routed, each active routing protocol is asked to submit a candidate route. Each protocol chooses a route (or determines that it has no appropriate route) using a route lookup algorithm appropriate to the particular routing protocol. After this takes place, the router is left with a set of candidate routes, containing at most one route suggested by each of the routing protocols. The router then uses a special route lookup algorithm, called a "meta-lookup algorithm", to choose from among those routes. This approach has some obvious disadvantages: 1. A router running "n" routing protocols has to do "n+1" route lookups per packet. 2. It isn't entirely obvious what the meta-lookup algorithm should be. However, this approach has a number of fairly strong advantages: 1. Depending on what meta-lookup algorithm is chosen, it can support virtually any policy, including those supported by the previously listed options. 2. Unlike the previous options, it can support a policy of preferring the route from whichever routing protocol has the route which best matches the packet's destination address and requested TOS. This probably matches most peoples' intuitions about what the router ought to do. Given the complexity and difficulty of routing, I consider it extremely important that the solution match peoples' intuition. 3. Because the routing protocols operate independently of each other and maintain their own routing tables, there is no need to worry that interactions between the protocols might make some of the protocols act incorrectly. 4. Likewise, because each routing protocol uses its own route lookup algorithm on its own routing table, it is easy to ensure that any route chosen by this approach will in fact be the preferred route of one of the routing protocols. This greatly reduces the probability of routing loops. Because of its strong advantages, the Meta-lookup Algorithm approach seems to be the most promising choice. The remainder of this memo considers this approach in greater detail, and considers how its disadvantages can be mitigated. 6 The Recommended Policy Pruning Rule Before examining the Meta-lookup Algorithm approach in detail it is necessary to take a brief diversion to consider Policy pruning rules. One common aspect of all of the algorithms examined so far is that the Policy pruning rule is not specified. As a result, it can differ vastly among implementations. This has been useful in that it has allowed the Internet community to experiment with a number of approaches, but has also lead to diminished interoperability among different implementations. In an attempt to improve interoperability without stiffling invention, this memo does not fully specify the Policy pruning rule. Instead, it recommends that two specific components be included in any Policy pruning rule. Taken together, these two components provide what practical experience has shown to be a very useful set of baseline capabilities that I think should be common to all implementations. Implementors would be free to augment these basic capabilities by adding additional steps of their own devising. 6.1 Step 1: Route Preference Value Pruning The primary mechanism of the recommended Policy pruning rule is that each route has associated with it a "preference value", based on various attributes of the route (specific mechanisms for assignment of preference values are suggested in section 6.5). This preference value is an integer in the range [0..255], with zero being the most preferred and 254 being the least preferred. 255 is a special value that means that the route should never be used. The first step in the Policy pruning rule discards all but the most preferable routes (and always discards routes whose preference value is 255). It is worth noting that Route Preference Policy is not "safe" in that it can easily be misused to create routing loops. Since no protocol ensures that the preferences configured for a router are consistent with the preferences configured in its neighbors, network managers must exercise care in configuring preferences. It is also worth noting the relationship between the special preference value of 255 and the route filtering features provided by some implementations. The route filtering features prevent routes from being installed in the FIB, whereas the preference value of 255 allows a route to be included in the FIB but discards it as one of the final steps of the meta-lookup algorithm. As a result, the route filtering features can cause the protocol-specific lookup algorithms or the earlier steps in the meta-lookup algorithm to choose less specific routes, whereas the preference vale of 255 can only cause some (or all) of the routes chosen by the previous steps to be discarded. Another difference is that a preference value of 255 may be assigned to any route, whereas route filtering cannot legally discard routes learned from SPF-based protocols. 6.2 Step 2: Routing Domain Equivalence Pruning The secondary mechanism of the recommended Policy pruning rule is "routing domain equivalence". If a router is configured to treat a set of routing domains as equivalent then routes from those domains can be compared based on their TOS and metric values. Since this step is applied after Route Preference Value pruning, routes are compared only if they have identical preference values. The primary utility of this feature is to allow the metrics of static routes to be compared to those of dynamic routes, but there will also be other cases where this can be useful because the network manager knows that the metrics of two routing domains are comparable. For example, routing in certain parts of the Internet depends on the fact that the routers used can consider the metrics of routes learned from different EGP autonomous systems to be comparable. Routing Domain Equivalence pruning uses a procedure similar to Weak TOS pruning. The TOS values of the candidate routes are checked. If any have the requested TOS then any routes which do not are discarded (unlike W eak TOS pruning, routes which do not have TOS values are retained rather than discarded). The metrics of the remaining routes are then compared, and those with inferior metrics are discarded. 6.3 Other Possible Policy Pruning Steps Of course, many other policy pruning mechanisms are possible. For example: MTU If any of routes in the set of candidate routes have an MTU large enough to forward the packet without fragmenting it then all routes which would require fragmentation are discarded from the set. 6.4 Load Splitting At the end of the Policy pruning step multiple routes may still remain. A router has several options when this occurs. It may arbitrarily discard some of the routes. It may reduce the number of candidate routes by comparing metrics of routes from routing domains which are not considered equivalent. It may retain more than one route and employ a "load-splitting" mechanism to divide traffic among them. Perhaps the only thing that can be said about the relative merits of the options is that load-splitting is useful in some situations but not in others, so a wise implementor who implements load-splitting will also provide a way for the network manager to disable it. 6.5 Assignment of Preference Values It is important to give network managers adequate flexibility in assignment of preference values so that they can implement whatever policies they desire. In practice, this seems to require the ability to assign preference values at the granularity of individual routes. However, since a router may have thousands of routes, it is equally important that the network manager not be required to specify an individual preference value for each and every route. The following mechanisms seem to provide adequate expressive power without overly complicating the configuration process. The implementor of the router chooses for each routing protocol (and for static routes) a default preference value. There is no standard way of choosing these preference values, but a good rule of thumb is to choose the values in such a way that static routes are preferred over routes learned from an IGP , and routes learned from an IGP are in turn preferred over routes learned from an inter-domain routing protocol (e.g. EGP or BGP [5]). It is probably also wise to choose the default preference values such that no two routing protocols have the same default preference value. The router associates with each routing domain it is a member of a default preference value, which will be assigned to any routes which are learned from that routing domain but which do not have their preference value set by one of the mechanisms below. The router should allow the network manager to specify for each routing domain (including static routing domains) the default preference value for the routing domain. For any routing domain for which the network manager has not explicitly configured a default preference value, the default preference value for the routing protocol should be used as the default preference value for that routing domain. The above mechanisms are usually adequate to assign preference values to most routes, but additional mechanism is needed to provide the fine-grained control. Although the only remaining mechanism that is strictly necessary is a mechanism to assign specific preferences to individual routes, configuration can be considerably simplified if mechanisms are provided to assign a particular preference value to the subset of routes from a particular routing domain which share some common characteristic. The following mechanisms for classifying routes have proven to be useful (and, conveniently, comprise a superset of the set of classifications used by the route leaking mechanisms described in [1]): Address match It is useful to be able to assign a single preference value to all routes (learned from the same routing domain) to any of a specified set of destinations, where the set of destinations is all destinations that match a specified address/mask pair. Route class For routing protocols which maintain the distinction, it is useful to be able to assign a single preference value to all routes (learned from the same routing domain) which have a particular route class (intra-area, inter-area, external with internal metrics, or external with external metrics). Interface It is useful to be able to assign a single preference value to all routes (learned from a particular routing domain) that would cause packets to be routed out a particular logical interface on the router (logical interfaces generally map one-to-one onto the router's network interfaces, except that any network interface which has multiple IP addresses will have multiple logical interfaces associated with it). Source router It is useful to be able to assign a single preference value to all routes (learned from the same routing domain) which were learned from any of a set of routers, where the set of routers are those whose updates have a source address which match a specified address/mask pair. Originating AS For routing protocols which provide the information, it is useful to be able to assign a single preference value to all routes (learned from a particular routing domain) which originated in another particular routing domain. For BGP routes, the originating AS is the first AS listed in the route's AS_PATH attribute. For OSPF external routes, the originating AS may be considered to be the low order 16 bits of the route's external route tag if the tag's Automatic bit is set and the tag's PathLength is not equal to 3 [10]. External route tag It is useful to be able to assign a single preference value to all OSPF external routes (learned from the same routing domain) whose external route tags match any of a list of specified values. Because the external route tag may contain a structured value [10], it may be useful to provide the ability to match particular subfields of the tag. AS path It may be useful to be able to assign a single preference value to all BGP routes (learned from the same routing domain) whose AS path "matches" any of a set of specified values. It is not yet clear exactly what kinds of matches are most useful. A simple option would be to allow matching of all routes for which a particular AS number appears (or alternatively, does not appear) anywhere in the route's AS_PATH attribute. A more general but somewhat more difficult alternative would be to allow matching all routes for which the AS path matches a specified regular expression. 7 The Meta-lookup Algorithm Approach in Detail So far, this memo has discussed the problem of how a router which simultaneously uses several routing protocols might choose an appropriate route to a particular destination. The previous section described several approaches to solving the problem, and identified the Meta-lookup Algorithm approach as the most promising. This section considers that approach in greater detail. 7.1 The Recommended Meta-lookup Algorithm One of the features of the Meta-lookup Algorithm approach which gives it so much flexibility is that any meta-lookup algorithm one wants to choose will work and will not violate the assumptions of any of the router's routing protocols. However, it would be undesirable to leave the algorithm completely to the discretion of the implementor, since then it would continue to be difficult if not impossible to configure routers from different vendors in a consistent manner. To me, the most obvious candidate for a meta-lookup algorithm would be a stripped down version of the Revised Classic Algorithm from Section 4.1 on page 10. This algorithm is familiar to both implementors and users, and intuitively does "the right thing" in most cases. The Basic Match pruning step can be omitted, since it can be safely assumed that the none of the routes provided by the protocol-specific route lookups would be discarded by a Basic Match pruning step. Likewise, the Best Metric pruning step would never discard any routes, and can therefore be omitted. The reason for this is that (as described on page page 9) Best Metric only compares metrics of routes from the same routing domain. One major shortcoming of the Revised Classic Algorithm for this purpose is that it would have to be augmented to include an IDPR Policy pruning step (described on page 10) in order to support the IDPR protocol. This can be rectified by replacing the Basic Match pruning step in the Revised Classic Algorithm with an IDPR Policy pruning step. The other major shortcoming of the Revised Classic Algorithm for our purposes is that it leaves the details of the Policy pruning step unspecified, an omission that would need to be corrected to ensure easy interoperability among routers from different vendors. This can be rectified by replacing the generic Policy pruning rule with the specific pruning steps recommended in Section 6. Some people have suggested that the Router Requirements Algorithm (described in Section 4.2 on page 1 1) ought to be used in place of the Revised Classic Algorithm, since the former supports TOS while the latter does not. Using the Router Requirements Algorithm would make it more likely that a route with the correct TOS would be chosen, but at the expense of implicitly preferring protocols that support TOS. Even with the Revised Classic Algorithm, no route would be chosen that didn't have either the requested TOS or the default TOS as long as all routing protocols which support TOS continue to choose Weak TOS over alternative pruning rules to select routes of an appropriate TOS. To summarize, the recommended meta-lookup algorithm is: 1. IDPR policy 2. Longest match 3. Route preference policy 4. Routing domain equivalence policy where the first step may be omitted by routers which do not support the IDPR protocol and additional Policy steps may be added at the discretion of the implementor. 7.2 The Alternative Meta-lookup Algorithm The meta-lookup algorithm recommended in the previous section applies Longest Match before applying Route Preference Policy . As a consequence, the most specific route to a destination is always chosen even if its preference value is inferior to that of a less specific route. As a result, the recommended algorithm cannot be configured to emulate the behavior of the Rank Ordering of Routing Protocols approach that was discussed in Section 5.2 on page 16. I believe that this choice is usually the correct one, but some network managers may wish to be able to configure their routers to make the opposite choice. Thus, an implementation may wish to include an option to use the following alternative meta-lookup algorithm: 1. IDPR policy 2. Route preference policy 3. Longest match 4. Routing domain equivalence policy where (as before) the first step may be omitted by routers which do not support the IDPR protocol and additional Policy steps may be added at the discretion of the implementor. 8 Performance and Implementation Issues This section briefly considers ways to mitigate the problem that the Meta-lookup Algorithm approach (conceptually at least) requires "n+1" route table lookups for each packet forwarded. It assumes that the meta-lookup algorithm being used is the one from Section 7.1 on page 21, but the general approach is probably applicable to any meta-lookup algorithm. 8.1 Serialization of the Recommended Algorithm Although it is conceptually necessary to do several route table lookups and then afterwards apply the meta-lookup algorithm to the results, it is possible to do everything necessary in a single pass through the FIB. The precise algorithm required to do this depends on which route lookup algorithms are used by the routing protocols that are supported, but the following algorithm is believed to support all of the existing IP routing protocols: 1. Basic match 2. IDPR policy 3. Generic route class 4. Longest match 5. Generic weak TOS 6. Best metric 7. Route preference policy 8. Routing domain equivalence policy Most of the steps are pruning rules which have been previously discussed, but pruning rules 3 and 5 are modified versions of previously discussed rules, and are defined as follows: Generic Route Class This is simply an agglomeration of the protocol-specific route class pruning rules. OSPF route class pruning (which was described on page 8) is applied to any OSPF routes (but not any other routes) in the set of candidate routes. Likewise, IS-IS route class pruning (which was described on page 9) is applied to any Integrated IS-IS routes in the set of candidate routes. If any other routing protocol are used which also support route classes, protocol-specific route class pruning would likewise be applied to those routes. Generic Weak TOS This is exactly like Weak TOS, except that is applied separately to the routes learned from each routing protocol. Thus, for example, finding an OSPF route whose TOS matched the TOS requested in the packet might cause other OSPF routes to be discarded, but would not cause RIP or Integrated IS-IS routes to be discarded. Using this algorithm is more time-consuming than using one of the traditional route lookup algorithms, but should prove significantly speedier than performing one route lookup per protocol and then executing the meta-lookup algorithm on the resultant routes. 8.2 Route Caching Another way to improve the performance of the route lookup algorithm is to execute it less often. One way to do this is to maintain a cache which records the next hop address for each pair. Since it is usually the case that a packet for a particular destination will be followed in short order by other packets for the same destination, the hit rate on the cache is usually high enough to more than offset the cost of maintaining the cache. It is necessary to flush the cache whenever the FIB is changed, but that is a rare event in most networks. 8.3 Precomputation of Routes Routers typically improve performance by partially precomputing the results of the route lookup algorithm. The result of this precomputation is typically a "forwarding table", a data structure containing only the subset of routes in the FIB which could actually be chosen by the route lookup algorithm. I believe that it would be possible to create a forwarding table corresponding to the serialized algorithm in section 8.1, but the details are beyond the scope of this memo. 9 Conclusion This memo looked closely at how routers have traditionally chosen how to route packets to their destinations, and how that traditional method of choice is being overrun by changes in routing protocols and by the ever-increasing complexity of the Internet. The memo then examined several alternatives to the traditional method, and sketched out some of the details of a preferred one. References [1] P. Almquist Ruminations on Route Leaking Paper in progress. [2] P. Almquist Type of Service in the Internet Protocol Request for Comments (RFC) 1349, DDN Network Information Center, SRI International, Menlo Park, California, USA, July 1992. [3] R. Callon Use of OSI IS-IS for Routing in TCP/IP and Dual Environments Request for Comments (RFC) 1195, DDN Network Information Center, SRI International, Menlo Park, California, USA, December 1990. [4] C. L. Hedrick Routing Information Protocol Request for Comments (RFC) 1058, DDN Network Information Center, SRI International, Menlo Park, California, USA, June 1988. [5] K. Lougheed and Y. Rekhter A Border Gateway Protocol 3 (BGP-3) Request for Comments (RFC) 1267, DDN Network Information Center, SRI International, Menlo Park, California, USA, October 1991. [6] J. Moy OSPF Version 2 Request for Comments (RFC) 1247, DDN Network Information Center, SRI International, Menlo Park, California, USA, July 1991. [7] L. J. Seamonson and E. C. Rosen "STUB" Exterior Gateway Protocol Request for Comments (RFC) 888, DDN Network Information Center, SRI International, Menlo Park, California, USA, January 1984. [8] M. Steenstrup Inter-Domain Policy Routing Protocol Specification and Usage: Version 1 Work in progress (INTERNET DRAFT ). [9] E. Taft Gateway Information Protocol (Revised) Xerox Inter-Office Memorandum to: Communication Protocols, location: PARC/CSL, file: [Maxc1]GatewayInformation.press, date: May 30, 1979. [10] K. Varadhan BGP OSPF Interaction Request for Comments (RFC) 1403, DDN Network Information Center, SRI International, Menlo Park, California, USA, January, 1993. Security Considerations The proposals in this memo and its companion document [1] are intended to facilitate routing which is correct and consistent with local policies at points in the Internet where routing domains meet or overlap. To the extent that this memo is successful in its goals, a net increase in security should result. The proposals in this memo also provide some minimal guidance on integrating support for the IDPR protocol into routers which also support more conventional routing protocols. To the extent that source-demand routing is more secure than hop-by-hop routing this memo facilitates enhanced security The proposals in this memo have no other known impacts, either positive or negative, on security . In certain environments it would be useful to consider security labelling of paths and packets when making routing decisions, but the algorithms in this memo do not do so because current routing protocols (other than IDPR) do not convey the security labelling of available paths. It would probably be straightforward to modify the algorithms in this document to make correct use of such labelling information if routing protocols which provide it are developed. Security considerations are not otherwise addressed in this memo. Author's Address Philip Almquis 214 Cole Street, Suite 2 San Francisco, CA 94117-1916 Phone: 415-752-2427 EMail: almquist@Jessica.Stanford.EDU Working Group Address Although this document is not the product of an IETF Working Group, the issues it discusses are within the purview of the IETF's Router Requirements Working Group. EMail: ietf-rreq@Jessica.Stanford.EDU