Yue Wang Internet-Draft CUHK Expires: DATE Li Zhang Beijing Univ. of Tech. Zhinan Han Boston Univ. Wei Yan Beijing Univ. DATE Anycast Extension to OSPFv3 draft-wang-aospf-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on DATE. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document describes AOSPF (Anycast Extensions to OSPFv3), a routing protocol which extends OSPFv3 to support anycast, which we implemented and tested successfully in our IPv6 test bed. And the performance analysis shows the overhead of AOSPF is low. Yue Wang, et al Expires DATE [Page 1] Internet-Draft Anycast Extensions to OSPFv3 DATE Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Anycast Requirements for OSPFv3 . . . . . . . . . . . . . . 2 3. Anycast Extensions to OSPFv3 . . . . . . . . . . . . . . . . . 3 3.1. Representation of Anycast Address . . . . . . . . . . . . . 3 3.2. Topological Region Check for Anycast Address. . . . . . . . 3 3.3. Aggregation of Anycast Address . . . . . . . . . . . . . . . 4 3.4. Flooding of Anycast Address. . . . . . . . . . . . . . . . 4 3.5. Route Calculation of Anycast Address. . . . . . . . . . . . 5 3.5.1. Intra-Area Route Calculation. . . . . . . . . . . . . . 5 3.5.2. Inter-area Route Calculation. . . . . . . . . . . . . . 6 3.5.3. External Route Calculation. . . . . . . . . . . . . . . 7 3.5.4. Summary. . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Performance Considerations. . . . . . . . . . . . . . . . . . . 7 5. IANA considerations. . . . . . . . . . . . . . . . . . . . . . 7 6. Security considerations . . . . . . . . . . . . . . . . . . . . 7 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.1. Normative Consideration. . . . . . . . . . . . . . . . . . . 9 8.1. Informative Consideration. . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 Intellectual Property and Copyright Statements . . . . . . . . . 11 1. Introduction Anycast is a new communication model that was first proposed in [RFC1546], and then formally defined in IPv6 [RFC4291]. An anycast address is an address that is assigned to more than one interfaces (which typically belonging to different nodes), with the property that a packet sent to an anycast address is routed to the "nearest" interface of this address (according to the routing protocol's measure of distance). Consequently, anycast can easily improve server load balancing, service reliability and latency. But due to the problems facing anycast and the limited deployment of IPv6 in the Internet, few implementations exist and even fewer have been tested outside simulators [Survey04]. OSPF is a successful Intra-AS (Autonomous System) routing protocol in the Internet, whose IPv6 version is OSPFv3 [RFC2740]. But OSPFv3 does not explicitly support anycast. And this document is to extend the functionality of OSPFv3 for anycast routing. Yue Wang, et al Expires DATE [Page 2] Internet-Draft Anycast Extensions to OSPFv3 DATE Before further discussion, we introduce the definition of IPv6 anycast address. In IPv6, anycast addresses are allocated from the unicast address space and syntactically indistinguishable from unicast addresses. Thus anycast nodes must be explicitly configured to know its anycast address. In general, an anycast address is composed of two parts: a prefix that defines the topological region in which all interfaces of this anycast address reside, and the remaining part as a group identifier to distinguish anycast groups in the topological region. IPv6 has a temporary restriction against assigning anycast addresses to hosts for security considerations (e.g. unauthenticated anycast servers advertise to the routing system). However, we neglect it here and leave the solution to some secure group management protocol [AnycastMLD02], [SAGM03]. So, when anycast group management protocol discovers any new-come or new-left anycast address, it will signal OSPF. As a result, the routes to the anycast address are caculated in the OSPF network. 2. Anycast Requirements for OSPFv3 Anycast addresses differ from unicast addresses in two aspects. First, unlike unicast addresses which can address networks, anycast addresses can only address interfaces or nodes. Therefore, within its topological region, the anycast address must be maintained as a separate route entry; outside its topological region, the anycast address may be aggregated into the routing entry of its prefix. Second, although anycast and unicast routing have a common goal of finding the shortest paths to a destination, an anycast address can locate in multiple links or networks that somewhat complicates route calculation. So, the following extensions are requisite for OSPFv3 to support anycast routing. Above all, we need mark anycast addresses since they are syntactically indistinguishable from unicast addresses, so that we can make different process for them. Second, when an anycast address enters into the OSPF routing domain, OSPF should ensure the anycast address resides in the topological region it claims; when an anycast address leaves its OSPF area or AS, the area border or AS boundary routers may aggregate it. In here, we do not consider here that OSPF exchanges anycast routes with neighboring ASes, which involves inter-AS routing. Finally, route calculation may needs some modifications due to multiple locations of an anycast address. Yue Wang, et al Expires DATE [Page 3] Internet-Draft Anycast Extensions to OSPFv3 DATE 3. Anycast Extensions to OSPFv3 In this section we propose the key extensions of OSPFv3 to support anycast routing - the AOSPF routing protocol, which follows the definition of IPv6 anycast and does not affect current unicast routing. And we implemented and tested AOSPF successfully in our IPv6 test bed [AOSPF05]. 3.1. Representation of Anycast Address In OSPFv3, IPv6 address prefixes are represented by the combination of three fields: PrefixLength, PrefixOptions and AddressPrefix. Figure 1 shows the representation for an anycast address. We introduce an 'A-bit' in PrefixOptions, with 1 for anycast address, 0 for not. The length of the topology region of the anycast address is placed in PrefixLength. AddressPrefix is the 128-bit anycast address. +-+-+-+-+-+-+-+-+ | A | +-+-+-+-+-+-+-+-+ \ / \ / 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PrefixLength | PrefixOptions | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Address Prefix | | (128-bit Anycast Address) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: Anycast Address Representation 3.2 Topological Region Check for Anycast Address When an anycast address first enters into the routing system, the routing system must ensure the anycast address is authenticated and resides in the topological region it claims. The authentication can be done by some secure anycast group management protocol, while the topological region check is the job of routing protocols. Thus AOSPF makes the following check when discovering a new-come or new-left anycast address on its links typically from the anycast group manangement protocol: Yue Wang, et al Expires DATE [Page 4] Internet-Draft Anycast Extensions to OSPFv3 DATE (a) If the prefix of the link covers or equals to the prefix of the anycast address, AOSPF filters the anycast address because the route to the link is enough to locate the anycast address. (b) If the prefix of the anycast address covers but does not equals to the prefix of the link, AOSPF admits the anycast address, as the link is a subnet of the address' topological region. (c) Otherwise, AOSPF filters the anycast address for the link is not within the address' topological region, as this case indicates a false placement of the corresponding anycast hosts. 3.3. Aggregation of Anycast Address OSPFv3 can aggregate routes on ABRs (Area Border Routers) or ASBRs (AS Boundary Routers). When the anycast address is advertised outside its OSPF area or AS, AOSPF may aggregate it: (a) If the address ranges of the OSPF area (or AS) covers or equals to the prefix of the anycast address, the anycast address is not advertised outside the OSPF area (or AS) as its topological region is within the OSPF area (or AS). (b) Otherwise, the anycast address is advertised outside the area (or AS). 3.4. Flooding of Anycast Address The flooding mechanism for anycast address is similar to unicast address except that LSAs (Link State Advertisements) use the anycast address representation. Specially, when an AOSPF router admits a new-come anycast address on its links, it floods the anycast address via Link-LSA and Intra-Area-Prefix-LSA with the LS age field set as zero, so that other AOSPF routers will install the LSAs in their link state databases; When an AOSPF router admits a new-left anycast address on its links, it floods the anycast address via Link-LSA and Intra-Area-Prefix-LSA with the LS age field set as MaxAge, so that the other AOSPF routers will erase the LSAs from theirs link state database. We shall describle inter-area flooding of anycast addresses in Section 3.5.2. Yue Wang, et al Expires DATE [Page 5] Internet-Draft Anycast Extensions to OSPFv3 DATE 3.5. Route calculation of Anycast Address OSPF routing domain is composed of one backbone area and multiple directly connected non-backbone areas by ABRs. Thus the route calculation can be divided into three parts: intra-area, inter-area and external route calculation. Within areas, routes are calculated by Dijkstra SPF (Shortest Path First) algorithm; ABRs exchange inter-area routes across the backbone area. And the inter-area routes are calculated in the similar way of the distance vector algorithm; External routes (i.e. routes from the other routing domains) are imported into the OSPF routing domain by ASBRs. As the anycast address resides in multiple links, or in multiple OSPF areas, or even outside the OSPF routing domain, we need to find the shortest paths among them. 3.5.1. Intra-Area Route Calculation OSPFv3 seprarates the topology infomation and address prefixes. The SPF tree in each router are calculated based on Router-LSAs and Network-LSAs. A SPF tree node denotes a router or transit link, and the root denotes the router in computation. Thus, we can reuse the SPF tree in anycast routing. For anycast, AOSPF obtains the anycast address and its attached router or transit link IDs from Intra-Area-Prefix-LSAs and associates the anycast address to the corresponding SPF tree nodes. Since multiple Intra-Area-Prefix-LSAs (for location on multiple links) can carry the same anycast address, we should select the smallest-cost SPF tree node with the anycast address. However, if we simply treat the anycast address as a 128-bit unicast address, we cannot guarantee selecting the shortest path. Consider the network where anycast address "A" has two hosts a1 and a2. Figure 2 shows the SPF tree in R0. The costs to a1 and a2 are 1 and 2, respectively. So the route to "A" is "R0-R1". Case 1: a1 first joins the network, and then does a2. In this case, R0 finally selects the shortest path to a2 (i.e. R0-R2-N2) as the route to "A", which is considered as the updated one. Case 2: Assume a1 and a2 already joined the network, and R0-R1 is the route of "A", which corresponds to the shortest path to a1. When a1 leaves "A", the route to "A" is then removed, until a1 or a2 is re-advertised after the LSA retransmission timer expires. In both cases, OSPF falsely select the route to "A" (Case 2 even does not have a route for some time). To solve this problem, we should maintain a sorted list of the shortest paths to all the anycast hosts for a given anycast address (here we refer it to as "anycast backup path list"). When the "nearest"anycast hosts join or leave the network, we can select the alternative route from the path list. Yue Wang, et al Expires DATE [Page 6] Internet-Draft Anycast Extensions to OSPFv3 DATE +-----+ | R0 |-------- +-----+ | | | |1 |1 | | +-----+ +-----+ | R1 | | R2 | +-----+ +-----+ | | a1("A") |1 | +-----+ | N2 |- a2("A") +-----+ Figure 2: A SPF tree with anycast address "A" 3.5.2. Inter-Area Route Calculation ABR originates a separate Inter-Area-Prefix-LSA for the inaggregatable anycast addresses in each of its attached areas. Specially, when the ABR finds a new-come anycast address in its attached area (the corresponding intra-area anycast backup path list changes from empty to not empty), it originates an Inter-Area-Prefix-LSA with "LS age" set as zero; when the ABR finds a new-left anycast address in its attached area (the corresponding intra-area anycast backup path list changes from not empty to empty), it originates an Inter-Area-Prefix-LSA with "LS age" set as MaxAge; When the ABR find the cost of the anycast address' intra-area route changes, it originates an Inter-Area-Prefix-LSA for the anycast address with the changed cost. The "Metric" of the LSA is set as the cost of the anycast address' intra-area route. Inter-Area-Prefix-LSAs are flooded into all areas in the OSPF network. For the same reason as in Section 3.5.1, each router should maintain an inter-area backup path list for each anycast address, and the shortest one as the inter-area route. Yue Wang, et al Expires DATE [Page 7] Internet-Draft Anycast Extensions to OSPFv3 DATE 3.5.3. External Route Calculation. ASBRs learn external routes outside the OSPF routing domain and flood them into the whole domain by AS-external-LSAs. Similarly, AOSPF keeps a backup path list for each type 1 external anycast address, as the storage is small for just a few neighboring routing domains. But the storage is huge for type 2 external anycast routes, if anycast is deployed on a large scale of the Internet, which is known as anycast scalability problem. Researches on this problem tend to contrive new inter-domain protocols [GIA00]. And we ignore type 2 external anycast routing, which goes beyond this document. 3.5.4. Summary. We summarize anycast routing process of AOSPF. Receiving updated intra-Area-Prefix-LSAs, Inter-Area-Prefix-LSAs and type 1 AS-external-LSAs for the anycast address will trigger intra-area, inter-area and type 1 external anycast route calculations, respectively. And the final anycast routes in the forwarding table are the shortest ones among them. The correctness of AOSPF can be easily proved. Briefly, each router have the same intra-area topology information. And the star structure of inter-area topology avoids any loops. 4. Performance Considerations We focus on intra-domain anycast routing in OSPF networks. The total number of originated LSAs for each anycast address is proportional to the number of links on which the anycast address resides. And the flooding scope is an area or the whole OSPF domain for aggregatable or inaggregatable anycast addresses, respectively. Although the flooding is expensive, the total message overhead is typically small because anycast is designed for providing services and thus hosts' joining or leaving anycast groups, which originates new LSAs and triggers route calculation, are not frequent. As for the calculation overhead, one anycast route calculation is equivalent to one insertion or deletion of some anycast backup path list and possible updating of the forwarding table. So the total calculation overhead is small. Besides, as shown in [AOSPF05], the frequency of anycast route updating in the forwarding table is much smaller than the frequency of anycast route calculations. Yue Wang, et al Expires DATE [Page 8] Internet-Draft Anycast Extensions to OSPFv3 DATE The storage overhead is proportional to the number of anycast addresses times the average number of their locations (i.e. links and areas for intra-area and inter-area path list, respectively). We can make further improvements. First, although the frequency of joining and leaving anycast groups is normally low, we need some protection in case that the network could suffer from exhausting anycast routing due to misoperations or DoS attacks. We can apply some damping mechanisms (e.g., we can set some secure interval and max allowable times) to lazily respond to too frequent joining and leaving anycast groups. The second concern is on unnecessary high-cost backup paths that occupy the storage space. Because network status is normally stable in the Internet and LSAs are refreshed typically every 30 minutes, it is sufficient to keep a small number of backup paths, say 5 paths, for each anycast address. 5. IANA Considerations This document creates a new IANA registry for the PrefixOptions fileld shown in Section 3.1. This document defines an 'A-bit' in PrefixOptions, with 1 for anycast address, 0 for not. Future assignments in this field are to be coordinated via IANA under the policy of "Specification Required" [RFC2434]. It is expected that this policy will allow for other (non-IETF) organizations to more easily obtain assignments. 6. Security Considerations The implementation of AOSPF should be interfaced to some secure anycast group management protocol, from which AOSPF can obtain authenticated anycast addresses. 7. Acknowledgements This work was done in the Computer Networks and Distributed Systems Laboratory of Beijing University, funded by National Science Foundation of China under grant number 60273002. We thanks for their supports and discussions. Yue Wang, et al Expires DATE [Page 9] Internet-Draft Anycast Extensions to OSPFv3 DATE 8. References 8.1 Normative References [RFC1546] C. Partridge, T. Mendez, and W. Milliken, "Host Anycasting Service", RFC 1546, Nov. 1993. [RFC4291] R. Hinden, and S. Deering, "IP Version 6 Addressing Architecture", RFC4291, Feb. 2006. [RFC2740] R. Coltun, D. Ferguson, and J. Moy, "OSPF for IPv6", RFC2740, Dec. 1999. [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, Oct. 1998. 8.2 Informative References [Survey04] S. Weber, and L. Cheng, "A Survey of Anycast in IPv6 Networks", IEEE Communication Magine, Jan. 2004, pp. 127-132. [AnycastMLD02] B. Haberman, and D. Thaler, "Host-based Anycast using MLD", draft-haberman-ipngwg-host-anycast-01.txt (work in progress), May 2002. [SAGM03] Y. Wang, L. Zhang, and W. Yan, "Research on IP Anycast Secure Group Management", Proc.16th APAN Meetings /network research workshop, Korea, 2003, pp. 49-55. [GIA00] D.Katabi, and J.Wroclawski, "A Framework for Scalable Global IP-Anycast (GIA)", Proc. of SIGCOMM, Sept. 2000, pp. 3-15. [AOSPF05] Y. Wang, L. Zhang, Z. Han, and W. Yan, "Anycast Extensions to OSPFv3", Proc. of ICPADS, Jul. 2005. Yue Wang, et al Expires DATE [Page 10] Internet-Draft Anycast Extensions to OSPFv3 DATE Authors' Addresses Yue Wang The Chinese University of Hong Kong Email: ywang@cse.cuhk.edu.hk Li Zhang Beijing University of Technology Email: Zhangli828@bjut.edu.cn Zhinan Han Boston University Email: jennyhan@cs.bu.edu Wei Yan Beijing University Email: yanwei@net.pku.edu.cn Yue Wang, et al Expires DATE [Page 11] Internet-Draft Anycast Extensions to OSPFv3 DATE Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Yue Wang, et al Expires DATE [Page 12]