Internet DRAFT - draft-wang-aospf
draft-wang-aospf
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]
