of 11
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Metarouting. Timothy G. Griffin



Publish on:

Views: 6 | Pages: 11

Extension: PDF | Download: 0

Metarouting Timothy G. Griffin Computer Laboratory University of Cambridge Cambridge, UK João Luís Sobrinho Instituto de Telecomunicações Instituto Superior Técnico Lisbon,
Metarouting Timothy G. Griffin Computer Laboratory University of Cambridge Cambridge, UK João Luís Sobrinho Instituto de Telecomunicações Instituto Superior Técnico Lisbon, Portugal ABSTRACT There is a shortage of routing protocols that meet the needs of network engineers. This has led to BGP being pressed into service as an IGP, despite its lack of convergence guarantees. The development, standardization, and deployment of routing protocols, or even minor changes to existing protocols, are very difficult tasks. We present an approach called Metarouting that ines routing protocols using a high-level and declarative language. Once an interpreter for a metarouting language is implemented on a router, a network operator would have the freedom to implement and use any routing protocol inable in the language. We enforce a clean separation of protocol mechanisms (link-state, path-vector, adjacency maintenance, and so on) from routing policy (how routes are described and compared). The Routing Algebra framework of Sobrinho [25] is used as the theoretical basis for routing policy languages. We ine the Routing Algebra Meta-Language (RAML) that allows for the construction of a large family of routing algebras and has the key property that correctness conditions guarantees of convergence with respect to the chosen mechanisms can be derived automatically for each expression ining a new routing algebra. Categories and Subject Descriptors C.2 [Computer Systems Organization]: Computer-Communication Networks Network Protocols, Internetworking General Terms Design, Theory, Languages Keywords Routing Protocols, Path Algebras, Algebraic Routing Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGCOMM 05, August 21 26, 2005, Philadelphia, Pennsylvania, USA. Copyright 2005 ACM /05/ $ GOOD ROUTING PROTOCOLS ARE HARD TO FIND Routers today come with a fixed number of routing protocols. Network operators and engineers must solve their routing and connectivity problems as best they can with this small set of tools. For IP unicast routing to which we restrict our attention in this paper this means that their solutions must use only static routing together with the standardized dynamic routing protocols RIP, OSPF, IS- IS, and BGP [13, 1, 21, 11], or the proprietary EIGRP [23] of Cisco Systems. Although BGP was developed as an interdomain routing protocol, it is currently being used by many large enterprises as an intra-domain routing protocol (this should not be confused with using internal BGP, or IBGP, which is an essential component of inter-domain routing). Many researchers may be shocked by the idea of using an EGP as an IGP. Network operators are a much more pragmatic group they have problems to solve now and they simply do their best with the tools available. In fact, several recent books on BGP provide advice on how best to break the rules and use BGP for intra-domain routing. Chapter 5 of [28] and Chapter 3 of [27] both explain the rationale for this approach and present configuration options to address particular kinds of network challenges. BGP is useful as an IGP because it provides more hierarchical structure and enables the implementation of well-ined administrative boundaries often essential in geographically dispersed and administratively heterogeneous networks. Of equal importance is the fact that traditional IGPs are all based on shortest paths with severe limitations in terms of policy control over routing. For example, with shortest path routing it is very difficult to implement different policies for different destinations. In short, BGP is being used as an IGP not because it is ideal, but because it is available, it has expressive policy control mechanisms, it can be used to implement administrative boundaries, and it scales well. An unstated reason is related to the difficulty of developing and deploying new routing protocols, or even minor modifications to existing protocols. Beyond the demanding standardization process, the fact remains that it is very difficult to develop well-behaved protocols with the sophisticated policy control required by intra-domain routing in many large enterprises. This is not a positive development in many regards, since BGP has no convergence guarantees [15]. Furthermore, when BGP is used as an IGP, routing policies have fewer constraints than inter-domain routing where the standard prefer customer routes over peer routes over provider routes policies provides at least partial protection against protocol divergence [6]. Beyond protocol divergence, policy interaction in BGP can result in multiple stable solutions, some intended by policy writers while others are not, and when a routing system becomes wedged in an unwanted routing solution it may be very difficult to debug [10]. In this paper we propose a new approach to the inition and deployment of routing protocols called metarouting. A metarouting specification ines a routing protocol in a high-level and declarative fashion. Routers need only implement an interpreter (or compiler) for a routing metalanguage in order to run any protocol so specified. Metarouting allows any network operator to specify a new routing protocol and then to use it. Our approach is based on four ideas. First, we clearly separate protocol mechanisms (link-state, path-vector, hard- or soft-state, adjacency maintenance) from routing policy (how routes are described and compared). Second, the theoretical framework of metarouting is to be found in the long tradition of path algebras (see [7, 2, 19] for several examples). That is, the means of describing routes and comparing route preference is captured in algebraic structures having rigorously ined semantics. In this paper we will adopt the Routing Algebra framework of Sobrinho [25] as our basic algebraic model. The reason for this is that this algebraic model was developed specifically to address rich policy control as found in BGP. Third, a key novel component of metarouting is the use of a language for ining new and more complex algebras from simpler ones. We present one language for the routing algebras of Sobrinho, called the Routing Algebra Meta-Language (RAML). RAML is a collection of simple base algebras together with a set of operators that take algebras as arguments and return new algebras. In this way, RAML can be used to ine a large family of routing algebras. Fourth, RAML is designed so that correctness conditions can be automatically derived for each expression ining a new algebra. For each base algebra certain monotonicity properties are shown to hold. Then each algebraic operator is associated with rules that describe how it preserves the monotonicity properties of its argument algebras. In this way monotonicity properties are easy to derive for any RAML expression. Metarouting can be viewed within a larger effort attempting to disaggregate and standardize the components of routing software and hardware, which the vendors have typically built as monolithic systems with many proprietary implementation details and interfaces. This work has included kernel design [3], modular implementation data-plane elements in Click [14], modular routing software as with FIRE [22] and XORP [12], and efforts to standardize the interfaces and protocols for low-level forwarding units in the FORCES working group [5] of the IETF. A missing aspect has been how to deal with the complex policy component of routing protocols in a generic yet high-level manner and this is what metarouting is attempting to provide. We do not imagine that every network operator would in fact want to ine their own protocols. We imagine that metarouting could eventually enable a natural division of labor between the IETF and the network operator community metarouting itself could be standardized within the IETF, while metarouting specifications of routing protocols could be developed and standardized within the operator community. Section 2 describes the decomposition of a routing protocol into mechanism and policy components, reviews the routing algebras of Sobrinho [25], and describes algebraic properties of routing algebras that guarantee convergence with a specific routing algorithm. Section 3 presents the Routing Algebra Meta-Language, RAML, and develops monotonicity preservation properties of each RAML construct. For readability and space reasons, all proofs have been eliminated. In Section 4 we show examples of using metarouting to develop and implement a new IGP. Developing new routing protocols will never be a trivial task, but we feel that metarouting will reduce the associated effort by several orders of magnitude. Section 5 presents a metarouting model of BGP, and considers how this approach might aid in improving this protocol. This section illustrates how RAML can aid researchers by providing a framework for the analysis of routing protocols. Section 6 ines label modalities that describe how abstract link labels are actually constructed from the information in router configurations on either side of a routing adjacency. Modalities represent a rug under which we sweep some of the protocol details that are not important from a purely theoretical perspective, but are important from the perspective of a network operator configuring a network of routers. Section 7 concludes with a discussion of directions for future research. 2. WHAT IS A ROUTING PROTOCOL? At the highest level, we can decompose most routing protocols into two components mechanism and policy. By policy we mean the information that describes the characteristics of a route, the method of comparing route characteristics to determine route preference, and the method in which local policy is applied to routes, potentially changing a route s characteristics or limiting the scope of its propagation. By mechanism we mean how routing messages are exchanged, how routing adjacencies are established and maintained, and what type of route selection algorithms are used to select best routes. Route selection algorithms rely on the policy component to determine route preferences. It might seem that route selection algorithm and the method of comparing route characteristics to determine route preference refer to the same thing. However, they are not for a large class of routing protocols. A simple example may help clarify this point. Shortest-path routing attaches weights to links and the important characteristic of a route is the sum of these link weights along the path it represents. We can talk about one route being more preferred than another when it is associated with a lower cost path. Now, there are several route selection algorithms that use this method of preference to compute best routes link information flooding combined with Dijkstra s algorithm and distributed Bellman-Ford are the most well known examples, and of course these are the algorithms associated with link-state and distance-vector routing protocols. What allows us to generalize this picture is an algebraic approach to routing in the tradition of Gondran, Minoux, and Carré [7, 2, 19]. In this paper we use the routing algebras as ined by Sobrinho [25], which are reviewed in detail in Section 2.1. A routing algebra comes with a set of signatures that describes characteristics of a route. It also ines the method of determining route preference based only on route signatures. Finally, a routing algebra generalizes the notion of a link weight to a policy label (referred to simply as a label ), and it ines how a policy label and a signature combine to form a new signature. 2.1 Routing Algebras We now provide a brief overview of routing algebras as developed by Sobrinho [24, 25]. Routing algebras are best understood as a generalization of shortest path routing. This is illustrated in Figure 1(a) for the traditional shortest path scenario. Node v has a path to a route originated by node w, indicated by the dotted line, and the length of this path has been computed to be m (this path may involve multiple nodes). Node v has a neighbor u, and there is an arc from node v to u with weight n. The composition of the (v, u) arc with the w to v path results in a path from w to u of length n + m. We use the convention that the arc s orientation points in the same direction as the flow of routing information in a path-vector protocol. Note that data traffic associated with a route travels in the opposite direction, from u to w. (a) (b) u u n v v n + m σ Figure 1: How path lengths are computed in the standard shortest path setting (a), and how path signatures are computed in the routing algebra setting (b). This basic picture is generalized by routing algebras and is illustrated in Figure 1 (b). A routing algebra A is a tuple m σ A = Σ,, L,, O, where Σ is a set of signatures for describing paths, is a preference relation over signatures, L is a set of labels, is a label application function that maps L Σ to Σ, and O is an origination set describing the signatures that can be associated with originated routes. A preference relation (commonly used in economics, see for example [17]), conforms to two rules, (completeness) for each x, y Σ, we have either x y or y x (or both), (transitivity) for each x, y, z Σ, if x y and y z, then x z. If x y we say that x is weakly preferred to y. If x y but y x does not hold, then we write x y and say that x is strictly preferred to y. If x y and y x, then we write w w x y and say that x and y are equally preferred. Note that x y does not mean that x = y. This fact is important for both the expressiveness of routing algebras and for the modeling of equal-cost multipath routing. For example, consider the simple case where Σ represents sequences of integers (perhaps router IDs or ASNs) and x y holds if and only if the length of x is less than or equal to the length of y. Then (2, 3, 4) (7, 1, 2, 5) and (2, 3, 4) (7, 1, 2) yet (2, 3, 4) (7, 1, 2). This is exactly the kind of comparison that BGP uses on the ASPATH attribute. Note that we have reversed the preference order with respect to the conventions found in most economics texts. We do this because we will be using preference to minimize path cost rather than to maximize some benefit. Our routing algebra notation differs somewhat from that presented in [24, 25] we use a preference relation instead of its implementation in terms of utility functions. Following the original notation we would say that Σ comes with an associated set of weights W totally ordered with and a ranking function f that maps Σ into W. In the notation above, σ 1 σ 2 means that f(σ 1) f(σ 2). Optionally, an algebra may come with a special signature, φ Σ, which is associated with prohibited paths paths with signature φ cannot be used for forwarding and are not propagated by routing protocols. We insist that for all σ φ we have σ φ. The job of a dynamic routing protocol is to compute routes, and for us a route will have the form r = p, nh, σ, where p represents a set of destination addresses (a prefix), nh is the next-hop address, and σ is the signature describing the characteristics of this route. Such routes could represent static routes, or be computed by a routing protocol. In Figure 1 (b), the signature σ Σ describes the path from node v to the originating node w, and L describes the policy applied on the arc from node v to node u. The signature describing the path from node w to u is then σ. Labels and signatures may contain rather complex objects, and it is not required that L = Σ. For route origination, we will ine a set of origination signatures, O Σ, to constrain the signatures that can be legally attached to routes that are injected into the protocol, either from static routes or from other protocols. For example, in BGP originated routes must have an empty AS- PATH, as seen by the originating router. 2.2 Convergence Guarantees The basic notion of correctness for routing protocols can be informally stated as follows. Once all changes have ceased in a network, a routing protocol should eventually determine stable forwarding tables that implement loop-free paths between every pair of endpoints that are allowed connectivity by policy. In the algebraic approach to routing, correctness is ensured with a clean separation of concerns. First, certain algebraic properties are identified for routing algebras. Second, generic algorithms are developed and proved correct for any algebra having the algebraic properties required by the algorithm. For vectoring algorithms (generalizations of distributed Bellman-Ford), Sobrinho [25] showed that the important algebraic property is strict monotonicity (SM): (SM) For all σ Σ {φ}, and for all L, σ σ. A vectoring algorithm that is using an SM algebra will always be correct. The SM property can also be used to show that there can be no forwarding loops in the resulting forwarding paths. The RAML presented in Section 3 is designed to make it easy to derive complex SM algebras. In order to do this we need a slightly weaker property, called monotonicity (M): (M) For all σ Σ, and for all L, σ σ. Note that SM implies M. Protocols such as IS-IS and OSPF are not based on vectoring but use link-state approaches that rely on several distinct components. First, a link-state flooding mechanism is used to distribute each router s local information to all other routers in the link-state routing domain. Second, an algorithm is used locally on each router that computes best paths in the network, as modelled by a weighted graph, and uses these paths to determine next-hops for each route. Typically, some version of Dijksta s algorithm [4] is employed. Third, forwarding paths are constructed by the concatenation of the next hops determined independently at each node. It is possible to generalize link state flooding and Dijkstra s algorithm to an arbitrary algebraic context [19, 24]. However, requirements for correctness are more restrictive. We require the associativity of (which in turn requires that L = Σ), and that the algebra be isotonic (I): (I) For all σ 1,σ 2,σ 3 Σ, if σ 1 σ 2, then σ 3 σ 1 σ 3 σ 2 and σ 1 σ 3 σ 2 σ 3. In addition, SM for such algebras must include the SM ined above (left-sm) as well as a right-sm rule. When constructing new algebras it turns out that these additional constraints are very difficult to preserve. It is important to note that we can still call a mechanism link-state even when the local algorithm bears no relation to Dijkstra s algorithm. In particular, if an algebra is only SM, then one could use a link-state approach with a local algorithm that essentially simulates vectoring on a local model of the network. This is not as strange as it might seem at first glance. In the case that the routing domain is not too large, it may actually be a reasonable, especially if fast convergence and complex policy control are both required. We will call this approach Local Path-Vector Simulation (LPVS). Table 1 indicates when an algebra is correctly associated with a given algorithm. vectoring link-state with Generalized Dijkstra link-state with LPVS SM I assoc. Table 1: Correctness for various algebra/algorithm combinations. 2.3 Base Algebras Table 2 presents a collection of simple routing algebras, together with their monotonicity property. Each algebra is now explained in turn. Algebra Description Properties add(n, m) int addition SM (if 1 n m) mult(n, m) int product M (if 1 n m) mult r(n, m) real product max(n) maximum M min(n) minimum lp(n) local preference op(n) origin preference M seq(n, m) sequences SM simseq(n, m) simple sequences SM tags(t) route tags M Table 2: Basic Routing Alg
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks