Internet Draft Cengiz Alaettinoglu Expires May 17, 1996 USC/ISI draft-ietf-rps-aspath-00.txt Jessica Yu Merit Networking July, 1995 Autonomous System Path Expression Extension to Ripe-181 Status of this Memo This document extends Ripe-181 to enable the specification of AS path expressions in the aut-num objects. This document is an Internet Draft, and can be found as draft-ietf-rps-aspath-00.txt in any standard internet drafts repository. 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. 1 Introduction Ripe-181 [Bates et al., 1994] is a language to specify routing policy constraints for inter-domain routing in the Internet. Ripe-181 allows the specification of both import policy constraints (by specifying as-in and interas-in attributes) and export policy constraints (by specifying as-out and interas-out attributes). There are limitations in the types of preference and access control policies that can be described by RIPE-181 and the limitations became evident when several enterprises tried to use RIPE-181 to describe their routing policies. One such limitation is the lack of ability to specify autonomous-system path expressions, henceforth referred to as AS path expressions, in the policy attributes (i.e. as-in, interas-in, as-out and interas-out attributes). This document extends Ripe-181 to enable the specification of AS path expressions in the aut-num objects. It is assumed that the reader is Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 familiar with Ripe-181. 2 Extended Attributes We define four new policy attributes for the aut-num object, extended-as-in, extended-as-out, extended-interas-in, and extended-interas-out to augment the as-in, as-out, interas-in, and interas-out attributes respectively. The short names for these attributes are as follows: xa for extended-as-in, xb for extended-as-out, xc for extended-interas-in, and xd for extended-interas-out. The original attributes have the following forms [Bates et al., 1994]: as-in: from accept as-out: to announce interas-in: from accept interas-out: to [] announce . Please refer to RIPE-181 [Bates et al., 1994] for the details of their syntax and semantics. The extended attributes have the same syntax and semantics as the corresponding original attributes except that the is extended. That is, we have the following new syntax for the extended attributes: extended-as-in: from accept extended-as-out: to announce extended-interas-in: from accept extended-interas-out: to [] announce . is a logical combination of AS numbers, AS macros, community names, route lists, predefined keywords (currently only the keyword ANY is defined), and AS path expressions. The syntax and semantics of are identical to the syntax and semantics of except that it can contain AS path expressions. An AS path expression has the following syntax: `<' `>'. Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 2] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 The syntax and semantics of AS path regular expressions are given in Appendix A. An AS path expression represents the set of routes which traverses a sequence of autonomous systems matched by the AS path regular expression(1). Note that the AS path regular expression only needs to match a part of the complete AS path traversed. For example, AS path expression matches the AS path ``1'' as well as the AS path ``2 1 3''. The following are examples of extended attributes: extended-as-in: from AS1 5 accept <^AS1 . * AS2$> AND NOT extended-as-out: to AS690 announce (<^AS1> OR <^AS2>) AND COMM_NSF_AUP. The first example means ``accept the set of routes from AS1 with an AS_PATH to AS2 that do not transit AS3 with preference 5. The second example means announce the set of routes learned from AS1 and AS2 which are in COMM_NSF_AUP to AS690. The same Ripe-181 rules that apply to original attributes also apply to the extended attributes. For example, in RIPE-181, one can only specify an interas-in/out attribute if a corresponding as-in/out attributed is specified for that peer AS. Hence, one can only specify an extended-interas-in/out attribute if a corresponding extended-as-in/out attribute is specified for that peer AS. Extended attributes are paired only with corresponding extended attributes. 3 Interaction Between Extended and Original Attributes In specifying policies for a given peer AS, if an AS only uses the original attributes, or only uses the extended attributes, the semantics are clearly defined in the previous section. However, the semantics are not so clear when an AS uses both the original and extended attributes for a given peer AS. We allow only one kind of mixing of the original and the extended attributes as depicted by the following two rules: For a given peer AS, if an AS uses either an extended-as-in or extended-interas-in attribute, then for every extended-as-in policy it specifies, it also has to specify an as-in policy; and for every extended-interas-in policy it specifies, it also has to specify an interas-in policy. For a given peer AS, if an AS uses either an extended-as-out or extended-interas-out attribute, then for every extended-as-out policy it specifies, it also has to specify an as-out policy; and for every extended-interas-out policy it specifies, it also has to specify an interas-out policy. Note that the *-in attributes and *-out attributes are treated separately. When mixing, care should be taken that the policies specified using the original and the matching extended attributes are as equivalent as possible and certainly not contradictory. _______________________________ (1) A router can check this using the AS_PATH attribute in the Border Gateway Protocol [Rekhter and Li, 1994] or RD_PATH attribute in the Inter-Domain Routing Protocol [Rekhter, 1993] (other protocols have similar mechanisms). Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 3] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 When a domain mixes the extended and the original attributes for a peer AS, the tools that do not support the extended attributes use only the original attributes. The tools that support the extended attributes only consider the original as-in/interas-in attributes if there is no extended-as-in/extended-interas-in attributes, for a peer AS. Otherwise, they only consider the extended-as-in/extended-interas-in attributes. The tools that support the extended attributes only consider the original as-out/interas-out attributes if there is no extended-as-out/extended-interas-out attributes, for a peer AS. Otherwise, they only consider the extended-as-out/extended-interas-out attributes. We expect that all tools will be upgraded eventually to support the extended attributes, at which time, original attributes can be replaced by the extended attributes. Here are some valid examples of mixing: Eg. 1. (No mixing, original attributes only) aut-num: AS1 as-in: from AS2 1 accept ANY as-out: to AS2 announce ANY Eg. 2. (No mixing, extended attributes only) aut-num: AS1 extended-as-in: from AS2 1 accept ANY extended-as-out: to AS2 announce ANY Eg. 3. (Perfect mixing) aut-num: AS1 as-in: from AS2 1 accept ANY as-out: to AS2 announce ANY extended-as-in: from AS2 1 accept ANY extended-as-out: to AS2 announce ANY And the following example is not valid because an extended-as-out attribute is used without using an as-out attribute. Eg. 4. (Invalid mixing) aut-num: AS1 as-in: from AS2 1 accept ANY extended-as-in: from AS2 1 accept ANY extended-as-out: to AS2 announce ANY AND NOT Note that the following example, in which as-out line does not reflect the exact export policy of AS1, is valid. Eg. 5. (Valid mixing) aut-num: AS1 as-in: from AS2 1 accept ANY as-out: to AS2 announce NOT AS10 extended-as-in: from AS2 1 accept NOT extended-as-out: to AS2 announce NOT Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 4] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 We allow this so that the existing tools can function and produce approximate results (using the approximate policy constraints as illustrated in the example) at the discretion of the AS. Eg. 6. (Valid mixing, as-out/extended-as-out only) aut-num: AS1 as-in: from AS2 1 accept AS2 as-out: to AS2 announce AS1 extended-as-out: to AS2 announce <^[AS3 AS4 AS5]> OR AS1 In this example, as-out and extended-as-out attributes are mixed, and as-in attribute is not mixed with an extended attribute. 4 Suggestions We reccomend administrators who register extended attributes to also register original attributes when possible as explained in Section 3. We also caution that specifying AS path policy expressions which are too topology specific can have serious consequences (see [Bates et al., 1994]). This is because Internet's topology is dynamic and the changes in the topology can easily affect the set of routes matched by these expressions drastically. The following three represent the same set of routes, however the last one can be translated into a finte state automota much more efficiently than the second one, and the second one can be translated much more efficiently than the first one: o OR < AS2$> OR < AS3$> o <(AS1 | AS2 | AS3)$> o <[AS1 AS2 AS3]$> We recommend the use of the last form whenever possible. 5 Acknowledgments We thank Elise Gerich, Curtis Villamizar, Daniel Karrenberg, Dale Johnson, Laurent Joncheray and various members of the RA team for various discussions and their suggestions. References [Bates et al., 1994] T. Bates, E. Gerich, L. Joncheray, J-M. Jouanigot, D. Karrenberg, M. Terpstra, and J. Yu. Representation of IP Routing Policies in a Routing Registry. Technical Report ripe-181, RIPE, RIPE Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 5] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 NCC, Amsterdam, Netherlands, October 1994. [Rekhter and Li, 1994] Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). Request for Comment RFC-1654, Network Information Center, July 1994. [Rekhter, 1993] Y. Rekhter. Inter-Domain Routing Protocol (IDRP). Journal of Internetworking Research and Experience, 4:61--80, 1993. A AS Path Regular Expressions AS Path Regular Expressions are POSIX compliant regular expressions over the alphabet of AS numbers. The regular expression constructs are informally summarized below: ASN where ASN is an AS number in Ripe-181 notation (e.g. AS1, AS690). ASN matches the AS path that is of length 1 and contains the corresponding AS number (e.g. AS path regular expression AS1 matches the AS path ``1''). ASMacro where ASMacro is an AS macro name (see [Bates et al., 1994]). ASMacro matches any AS path that is matched by one of the AS's in the expansion of ASMacro. . matches any AS path matched by any AS number. [...] is an AS number set. It matches any AS path matched by any AS number listed between the brackets. If a `-' is used between two AS numbers in this set, all AS numbers between the two AS numbers are included in the set. If an AS macro ASMacro is used in this set, all AS numbers in the expansion of ASMacro are included in the set. [^...] is a complemented AS number set. It matches any AS path which is not matched by the AS numbers in the set. ^ Matches the empty string at the beginning of an AS path. $ Matches the empty string at the end of an AS path. We next list the regular expression operators in the decreasing order of evaluation. These operators are left associative, i.e. performed left to right. Unary postfix operators * + ? For a regular expression A, A* matches zero or more occurrence of A; A+ matches one or more occurrence of A; A? matches zero or one occurrence of A. Binary catanation operator This is an implicit operator and exists between two regular expressions A and B when no other explicit operator is specified. The resulting expression AB matches Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 6] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 an AS path if A matches some amount of the beginning of that AS path and B matches the rest of the AS path. Binary alternative (or) operator | For a regular expressions A and B, A | B matches any AS path that is matched by A or B. Paranthesis can be used to override the default order of evaluation. Space, tab, and underscore characters can be used to increase readibility and they are ignored. The BNF that parses the AS path regular expressions is as follows: aspathre: aspathre_term | aspathre '|' aspathre_term aspathre_term: aspathre_closure | aspathre_term aspathre_closure aspathre_closure: aspathre_factor | aspathre_closure '*' | aspathre_closure '?' | aspathre_closure '+' aspathre_factor: aspathre_no | '^' | '$' | '(' aspathre ')' aspathre_no: ASNUM_TOK | ASMACRO_TOK | '.' | '[' aspathre_range ']' | '[' '^' aspathre_range ']' aspathre_range: aspathre_subrange | aspathre_range aspathre_subrange aspathre_subrange: ASNUM_TOK | ASMACRO_TOK | '.' | ASNUM_TOK '-' ASNUM_TOK where ASNUM_TOK is a string whose first two characters are ``AS'' and the rest of the characters form a valid positive integer and ASMACRO_TOK is a string whose first three characters are ``AS-'' and the rest of the characters are uppercase letters from the English alphabet. Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 7] Internet Draft AS Path Expression Extension to Ripe-181 July, 1995 Author's Present Addresses Cengiz Alaettinoglu Information Sciences Institute University of Southern California Marina del Rey, CA 90292 e-mail: cengiz@isi.edu Jessica Yu Merit Networking University of Michigan Ann Arbor, MI 48105 e-mail: jyy@merit.edu Cengiz Alaettinoglu, Jessica Yu Expires May 17, 1996 [Page 8]