Internet DRAFT - draft-tao-savi-savo
draft-tao-savi-savo
Network Working Group Tao Zijin
Internet Draft Gong Zhenghu
Lu Zexin
Wang Baosheng
Wang Hong
Li Sudan
Liu YaPing
National University of Defense Technology, China
Bi Jun
Wu JianPing
Tsinghua University,China
Intended status: Informational
Expires: April 20, 2012 November 14, 2011
OSPFv3-based Intra-Domain Source-Address Validation Implementation
draft-tao-savi-savo-01
Abstract
This memo describes SAVO SAVI, a source address validation mechanism
for IPv6 networks based on the OSPFv3 protocol within Intra-Domain
field. The proposed mechanism is intended to complement ingress
filtering techniques to provide a higher granularity on the control
of the forged source addresses and it can deal with the asymmetric
routing for which the common uRPF scheme ([RFC2827]) may fail.
The proposed SAVO mechanism does not need any additional
communication between the routers in which the SAVO mechanism has
been implemented and deployed. It can be incrementally deployed by
the network manager and when it is only partially deployed it still
helps to restrict the effect of the source address forging. It
provides proactive incentives for the users who deploy it for they
will be able to filter the packets with forged source address to a
certain range, especially when the forged addresses are in the range
of OSPF route prefixes.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may not be modified,
and derivative works of it may not be created, and it may not be
published except as an Internet-Draft.
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may not be modified,
and derivative works of it may not be created, except to publish it
as an RFC and to translate it into languages other than English.
Tao Zijin Expires April 20, 2012 [Page 1]
Internet-Draft SAVO SAVI October 2011
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November 10,
2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
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 February 20, 2012.
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents carefully,
as they describe your rights and restrictions with respect to this
document. Code Components extracted from this document must include
Simplified BSD License text as described in Section 4.e of the Trust
Legal Provisions and are provided without warranty as described in
the Simplified BSD License.
Tao Zijin Expires April 20, 2012 [Page 2]
Internet-Draft SAVO SAVI October 2011
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents carefully,
as they describe your rights and restrictions with respect to this
document.
Table of Contents
1. Introduction ................................................ 3
2. SAVO SAVI specification...................................... 8
2.1. The SAVO Basic Algorithm for Calculating the Possible Valid
Incoming Interface (BA-VII) of a certain router in a area..... 8
2.2. Calculating the Incoming Interfaces for Source Addresses in
intra-area route prefix..................................... 11
2.3. Calculating the Incoming Interfaces for source address in
inter-area route prefix..................................... 12
2.4. Calculating the Incoming Interfaces for source addresses in
AS-external route prefix.................................... 13
3. Routing Policy Considerations............................... 14
4. Security Considerations..................................... 14
5. Deployment Considerations................................... 14
6. References ................................................. 15
6.1. Normative References................................... 15
6.2. Informative References................................. 15
Appendix A. SAVO Related Algorithms............................ 16
A.1. Equal-Cost Parent-Vertex Search Algorithm(ECPS) for a known
vertex in a SPF tree........................................ 16
A.2. Basic Algorithm of the Valid Incoming Interfaces for a given
router(BVIIA) .............................................. 17
7. Conventions used in this document........................... 19
1. Introduction
This memo describes SAVO SAVI, a source address validation mechanism
for IPv6 networks based on the OSPFv3 protocol within Intra-Domain
field. The proposed mechanism is intended to complement ingress
filtering techniques to provide a higher granularity on the control
of the forged source addresses and it can deal with the asymmetric
routing for which the common uRPF scheme ([RFC2827]) may fail.
The filtering rules constructed by SAVO are completely based on the
OSPF protocol, their aims are to filter the packets with invalid or
Tao Zijin Expires April 20, 2012 [Page 3]
Internet-Draft SAVO SAVI October 2011
forged source addresses and their keywords to match are the source
address prefixes which are the same as the OSPF route prefixes.
The OSPF is one of the most widely used Intra-Domain routing
protocols in Internet nowadays. For the next generation Internet, the
main network layer protocol is IPv6, and OSPFv3 [1] is proposed as a
substitute for OSPFv2[2] in IPv6 routing.
OSPF is an IGP, used within an AS which is divided into areas, the
topology of an area is hidden from the rest of the Autonomous System,
and in the area the SPF technology is used as the routing means.
In OSPF, the main consideration is on how to get an optimal route
(i.e. nexthop) to a designated destination. In the routing
calculation of OSPF, the destination address can be converted to its
associated routers or links, hence the best route (nexthop) to the
destination can be got by searching the corresponding Router-id or
Link-id in the shortest path tree.
In this draft, on the contrary, the main point is on how to get all
the possible incoming interfaces for designated source addresses
which are in the current OSPF routing table of the router. If the
packets with the forged source addresses which are in the OSPF route
prefixes come from the unintended interfaces, they can be filtered by
the SAVO router.
In OSPF, each router is identified by a certain router-id which is
unique in the domain. The OSPF routes are advertised by each router
via a certain type of Link State Advertisement (LSA). For OSPFv3, the
intra-area route prefix is advertised by intra-area-prefix-LSAs (Type
9), The inter-area route prefix is advertised via the inter-area-
prefix-LSA (Type 5), and the AS-external route prefix is advertised
via the AS-external-LSA (Type 7).
As the route prefix is advertised by one or more certain router(s)
with a unique router-id, the route prefix is associated with the
associated router. From the source address validation's perspective,
the valid (OSPF) source address prefix must be the address prefix
advertised by the OSPF router. So if a router learned a route prefix,
and the route prefix, which can be seen as a source address prefix,
must come from one or more router(s) associated with the prefix. Here
the word 'associated' router means the router either has advertised
the prefix (as the DR or BDR of the link) or has a link which has the
corresponding address prefix configured but not necessarily has
advertised the route prefix.
Tao Zijin Expires April 20, 2012 [Page 4]
Internet-Draft SAVO SAVI October 2011
From the routing perspective, the router searches and constructs the
shortest path from itself to all other routers in the domain by the
topology information received and stored in its link-state database.
The result of the shortest path constructing is an appropriate
nexthop or multiple equal-cost nexthops which the router selects to
be the first hop of the shortest path.
In OSPF, to the intra-area route prefix, the nexthop is the first hop
of the shortest path to the destination in the area; to the inter-
area prefix, the nexthop is the first hop of the shortest path to the
border-router(only for Cisco's implementation of the OSPF, which is
distinct from the original specification of the OSPF); to the
external route prefix, the nexthop is first hop of the shortest path
to the advertising router which may be intra-area or inter-area due
to its relative position in the domain.
From the source address validation perspective, the router analyses
and constructs all the possible paths by which another router in the
domain may choose to get to it. The SAVO router considers all the
previous hops of the possible paths standing at the position of
another router. The way considering the possible paths is just the
reverse of the way considering the shortest path, the only difference
is just between 'all' and 'one'---from the source address validation
perspective, all the possible shortest paths should be taken in
account and included, which can be expressed as n-->n, while from the
routing perspective only the shortest one of them is considered to be
useful without considering the equal-cost paths, which can be
expressed as n-->1.
After the SAVO router has completed the OSPF route calculation and
writing the route to the IPv6 route table, it can compute the valid
incoming interfaces of those routes according to the collected LSDB
information which is also used by the route computation. The
filtering rules for certain source address prefixes can be
constructed by the valid incoming interfaces of those prefixes. The
filter rules can be implemented as the Access Control List (ACL) or
IPTable rules.
The basic assumption of SAVO is as follows:
o The router is the agent or representative of the routing prefix,
every networking host or device should connect to the network by
accessing the routers, the address prefixes of routers' links are the
real address prefixes of the networking hosts or devices;
o the identity of a router is identified by a Router-id which is
unique in the network;
Tao Zijin Expires April 20, 2012 [Page 5]
Internet-Draft SAVO SAVI October 2011
o The LSDBs of all routers in a area are synchronized;
o The inter-area route of every router is determined by selecting the
best route from its border route table.
In Figure 1, to router RT7, the route (nexthop) to network N1 can
only be RT3, while the packets with the source address prefix N1 may
come from RT3 or RT6. To network N2, there are two routers (RT8 and
RT9) on the link, the packets with the source address prefix N2 may
come from any one of them, but there may be only one of them which is
the Designated Router (DR) of the link has advertised it to router
RT7, and router RT7 can get the valid incoming interfaces of N2 from
the corresponding Router LSA and Network LSA about the network N2.
,' N3 o `.
/ | \
; | :
| Area 3 10 |
: | ;
\ RT9 o /
`. | ,'
`. 10 ,' _.------.
`----+--' ,-'' `--
+------------. ; | ,'
/ RT6`. RT1-'' RT2|- . / RT5 N1
/ o--+--48---,'o-----48-----o---`;-10---o----10-----o
/ | \ / | | |\
/ | \ ; |N4 | : :
/ Area 2 10 \ | 10 Area 0 1 \| Area 1
+ | : : | | `.
| RT7| | \ | | RT4 / '--. _.-
| o----1-+---`.o-----30-----o ,' `------''
| /| | RT3--. _.-'
| / | ;| `------''
| ," 1 |
`. / | ,
| 1 RT8| |
| / o |
| ," | ,
| / | |
| o----------| /
| RT9 N2 | /
`-. | ,"
`-._ o /
`-.-----------+
Figure 1 A sample Autonomous System
Tao Zijin Expires April 20, 2012 [Page 6]
Internet-Draft SAVO SAVI October 2011
In Figure 1, to router RT2 and RT4, the route to network N4 is via
RT1 and RT3 separately, but from the source address validation
perspective, both the RT1 and RT3 are the valid source routers for
source address N4.
SAVO satisfies the basic source address validation principles which
are hierarchical architecture (multi-fence solutions), solutions for
IPv6 first, proactive protection, incrementally deployable
(incomplete deployment is still beneficial), provide incentive for
deployment. The most important feature of SAVO may lies in that the
user can deploy the SAVO independently to get the info of all the
possible incoming paths of the OSPFv3 route prefix without any
communication with other routers.
SAVO SAVI is designed to provide a calculation method of all the
valid incoming interfaces of certain OSPF route prefixes only based
on local OSPF Link State (LS) information. This deployment model is
at the level of intra-AS source address validation in the SAVA
Testbed [RFC5210]. Even with partial deployment, SAVO can proactively
limit an attacker's ability to spoof packets. This design allows the
user to determine which interfaces the packets of certain source
address should arrive by its own route information without
additionally communicating with other routers. So, if a router which
has deployed SAVO, it can filter the packets with source addresses
matched with the OSPF route prefix and coming from the invalid
incoming interfaces calculated by SAVO at the ingress side while
allowing the same packets coming from other valid interfaces. The
filter method used by the router may be Access Control List (ACL),
iptables (for Linux), or others.
As the SAVO belongs to Ingress Filtering, it is natual to compare
SAVO with Reverse Path Forwarding [RFC2827]. The main advantage of
SAVO over RPF is that it can deal with the asymmetric routing, which
will lead to improperly discarding packets with valid source
addresses when RPF is used. Another advantage may be at the level of
filtering granularity, to the RPF, when there is a default route, the
RPF may accept the packets with spoofed source when the router can
not find the completely matched incoming interface, but to the SAVO,
the matching operation is much more accurate for the filtering rules
are much more concrete and address pertinent.
The main idea of SAVO comes from the iDPF which is proposed by Z.
Duan et al in a paper named "Controlling IP Spoofing through
Interdomain Packet Filters", where the iDPF is mainly proposed to
deal with the source address forging in the inter-domain cases, where
the BGP protocol is used as the main routing protocol.
Tao Zijin Expires April 20, 2012 [Page 7]
Internet-Draft SAVO SAVI October 2011
To SAVO and iDPF, every router judge the reality of source addresses
by its own routing information, and to do the verification by
filtering the packets with the forged source address. The filtering
rules formed by SAVO do not depend on any extra communication but the
OSPF itself. SAVO tries to find all the valid source routers for the
indicated source address prefixes, but in some cases SAVO can not
assure the unique incoming source of some source address prefixes,
that is to say the SAVO router may pass the packets with truly
spoofed source addresses but can't filter the packets with valid
source addresses.
2. SAVO SAVI specification
2.1. The SAVO Basic Algorithm for Calculating the Possible Valid
Incoming Interface (BA-VII) of a certain router in a area
The SAVO Basic Algorithm (BA-VII) is used to calculate the possible
VII for a certain router in a area. The VII of a source address
prefix can be indirectly got by the SBA with the associated router of
the prefix in a designated area.
As the OSPF uses the shortest path algorithm proposed by Dijkstra to
calculate a route to a certain router, for the SAVO router to
calculate the possible valid incoming interface (VII) from another
router to itself is just equal to finding the last hop of itself in
the reverse shortest reaching path (RSRP) of that router. Appendix A
gives an equal-cost parent-vertex (the lasthop of the current router
in the Reverse Shortest Path Tree) search algorithm and the detailed
process of BA-VII.
The reverse shortest reaching path (RSRP) is just the shortest path
by which another router used to reach the current router in a area.
From the current router's perspective, the RSRP is a shortest path
with another router as root, instead of itself. The RSRP may also
have multiple equal-cost paths which is the same as that in OSPF
[RFC2328]. The best way to get the RSRP is to calculate the Reverse
Shortest Path Tree using the destined router as the root by the LSDB
information stored in the OSPF router, which is the same as that used
in getting the SPT with the current router as root.
As you know, every route prefix is associated with an original router
via which the host send its packets with the source address in that
prefix into the network. To a route prefix of a calculating router
learned from other routers and stored in its routing table, the word
'original' means all the routers which have advertised the same route
prefix of the type of intra-area, inter-area or AS-external. For the
intra-area route prefix, it is associated with a Router-ID or
Tao Zijin Expires April 20, 2012 [Page 8]
Internet-Draft SAVO SAVI October 2011
Network-ID. For the inter-area route prefix, it is associated with a
Router-ID. For the AS-external route prefix, the situation is a
little complicated as the advertiser of the route may be inter-area
and the associated router is determined by the location of the
'forwarding address' field in the AS-external LSA.
As the router calculates the route to a certain destination route
prefix in a area using the shortest-path tree with itself as the root
and each router in a area has an identical link-state database
[RFC2328], it is natural to use the information in the existing
shortest-path tree (SPT) to speculate the reverse shortest reaching
path of a certain router.
If every link's cost in a area, which is defined as 'associated with
the output side of each router interface' in [RFC2328] is the same
(called Symmetric Link, SL) to each attached router, then the area is
defined to be an Symmetric Area (SA), otherwise the area is defined
to be an Asymmetric Area(ASA).
In a SA, a router's Shortest Path (SP) to another router is the same
as the Reverse Shortest Reaching Path (RSRP) from that router. In an
ASA, the SP may be distinct from the RSRP and the router has to
calculate the RSRP with the target router as root using the link-
state information stored in its database, just as the computing of
shortest path tree with itself as root. Since each participating
router in a area has an identical and complete link-state database,
it is possible to do the RSRP computation for all routers in the area.
At the same time, as the symmetry and/or asymmetry of an area may
vary due to some newly received router LSA and Network LSA, the
symmetry of the area MUST be checked when the topology have changed.
Figure 2 expresses the actions to be taken after a SAVO router has
received a new Router LSA or Network LSA. If the network topology
changes frequently, the ACCURATE mode may lead the router not able to
keep with the quick change of the route but the SIMPLE mode only need
the symmetry information of a certain area which is much easier to
get than to get every router's RSPT in the area.
So, there exists two ways to calculate the possible incoming
interfaces of a packet that one is using the SPT of itself, the other
is calculating the RSRP with the role of another router. The first
way is SIMPLE, but may be wrong when there are asymmetric links. The
second way is ACCURATE but lead to a higher calculation burden.
Two RSRP calculation modes are proposed here: one is SIMPLE mode,
which uses the SPT of the router with itself as root to compute the
possible incoming interfaces of a certain source address (prefix),
Tao Zijin Expires April 20, 2012 [Page 9]
Internet-Draft SAVO SAVI October 2011
which may be wrong when there are one or more asymmetric link(s) the
other is ACCURATE mode, which uses the link-state information to
calculate the target router's shortest path to itself, which may
introduce extra computation load. The ACCURATE mode is based on the
indicated router's RSRP which can be calculated by the same link-
state information used to calculate the SPT. As the name of ACCURATE
mode has indicated, it can speculate the valid incoming interfaces of
certain source address prefixes accurately. When the ACCURATE mode is
implemented and used in a SAVO router, an extra calculation thread
different from the current OSPF routing calculation thread may be
introduced to reduce the performance impact on the routing process.
+-------------------------------------+
| Received Network LSA or Router LSA |
+---+--------------+------------------+
|
+------------------+------------------+
| (Re)Compute the SPT with itself as |
| the root in the corresponding area|
+-----------------+-------------------+
|
_,.+.__
__..--'' `'`--...__ No (SIMPLE mode)
,.,-'' ACCURATE mode ? `i=..._________
`--.._ _,.--' |
`'--.._ _,.--' |
`'-+'' |
|Yes |
+-----------------------------------+ +-----------------+
| (Re)Compute the Reverse SPT with | | (Re)Compute the |
| every other router as the root | | symmetry of |
| in the cooressponding area | | of the area |
+-----------------------------------+ +-----------------+
| __.--'
| __.--'
| __.--'
+-----------------------+--'----------------------------+
| (Re)Compute the Valid Incoming Interfaces of the |
| corresponding source address prefix using the new RSPT|
| or area symmetry |
+-------------------------------------------------------+
Figure 2 Actions after newly received a Network LSA or Router LSA
Although the SIMPLE mode is not so accurate as the ACCURATE mode and
may be wrong when there are asymmetric links, it is much more
efficient in calculation than the ACCURATE mode. When there are
asymmetric links in a area, the remedy to correct the mistake of the
SIMPLE mode can be adding all links of that area in the current
router as the possible incoming interfaces in that area.
Tao Zijin Expires April 20, 2012 [Page 10]
Internet-Draft SAVO SAVI October 2011
When calculating the valid incoming interfaces for the SIMPLE mode,
the only work that is need to do is to judge whether an area is
symmetric or not, and if any one link of the area is not symmetric
then the area is not symmetric anymore and no any other computation
is needed, so the computation burden is light to the SAVO router and
the SIMPLE mode can adapt to the change of the network topology
quickly. If the area is symmetric, the result of SIMPLE mode is the
same as ACCURATE mode but to the asymmetric area, its result is not
so accurate that there may be more cases that the packets of spoofed
source addresses are passed without being filtered than that of
ACCURATE mode and the probability of falsely passing that kind of
packets is dependent on the number of interfaces in a area.
The extra computation load introduced by the ACCURATE mode depends on
the number of routers and links in a area and for each router except
the calculating router itself the Dijkstra shortest path algorithm
has to be run again if the router-LSAs or network-LSAs in a certain
area have been changed. So the running times of Dijkstra algorithm in
a SAVO router with ACCURATE mode is at least accumulation of the
number of routers in each area decreased by one, which may be a high
computation burden on the router. For an area with n nodes, the SAVO
router needs to compute the Reverse Shortest Path Tree (RSPT) for n-1
times and the SPT for 1 time. As the algorithm complexity of
Dijikstra is O(n^2), the complexity of the ACCURATE mode is O(n^3),
which is a rank higher than that of the SIMPLE mode.
The ACCURATE and SIMPLE mode forms the basics of the SAVO algorithm,
and all the other algorithms used to calculate the incoming
interfaces of the three types of route which will be introduced below
is based on the basic algorithm of the valid incoming interfaces (BA-
VII).
2.2. Calculating the Incoming Interfaces for Source Addresses in intra-
area route prefix
This section explains how to calculate the valid incoming interfaces
for the source address in intra-area route prefix.
Since the intra-area route is calculated by the intra-area-prefix-
LSAs, it is natural to analyze the possible incoming interfaces of a
intra-area route from the intra-area-prefix-LSAs stored in the LSDB.
From the OSPF specification, if the router has received all the
intra-area-prefix-LSA, inter-area-prefix-LSA, AS-external-LSA which
are of the same prefix, then the router should set the route type to
intra-area because the intra-area route type is preferred over the
other two types. The following steps are the process to analyze the
Tao Zijin Expires April 20, 2012 [Page 11]
Internet-Draft SAVO SAVI October 2011
possible incoming interface when the router has just got an intra-
area route and at the last step the algorithms to calculate the VII
of the inter-area route and AS-external route are used to analyze the
exceptional cases when there are LSAs of the type of inter-area or
AS-external and have advertised the same route prefix, and the other
two algorithms will be introduced below.
(1) Search all the valid intra-area-prefix-LSAs that match the route
prefix in all area's LSDB;
(2) If the corresponding LSA is found, then look up what type of LSA
is the current LSA referred to, which may be Network LSA or Router
LSA;
(3) If the referred LSA is of Network Type, then find what routers
are the corresponding Network LSA associated to and the associated
routers is the possible source router of that route prefix except the
current router itself. The attached routers of a network link must be
associated routers but the associated routers may not be the attached
routers since the associated routers may be introduced indirectly by
the DR who has advertised the Network LSA;
(4) If the referred LSA is of Router Type, then the corresponding
router is the associated router;
(5) Get the VII of the associated routers by the Basic Algorithm of
the Valid Incoming Interfaces for a given router(BVIIA), and the
input parameter of the BIIA are the router id of the associated
router, the corresponding area and the router id of myself;
(6) Further more, consider the exceptional cases which may exist when
the router has received some inter-area-prefix-LSAs and/or AS-
external LSA with the same prefix just as there are the routes with
the same prefix which type is inter-area or AS-external. The
corresponding methods to deal with these two kinds of LSAs may be
described below.
2.3. Calculating the Incoming Interfaces for Source Addresses in Inter-
Area Route Prefix
As in the previous intra-area cases, when the router has got a inter-
area route there may exist some AS-external LSAs advertising the same
prefix as the inter-area route, since the inter-area-prefix-LSAs are
preferred over the AS-external LSAs.
The following steps are the process to analyze the possible incoming
interfaces when the router has just got an inter-area route and at
Tao Zijin Expires April 20, 2012 [Page 12]
Internet-Draft SAVO SAVI October 2011
the last step the algorithm to calculate the VII of the AS-external
route are used to analyze the exceptional case when there are some
AS-external LSAs with the same prefix, and the algorithm for the AS-
external route will be introduced as follows.
(1) Search all the valid inter-area-prefix-LSAs that match the route
prefix in all area's LSDB and can be used to generate that route;
(2) If the corresponding LSA has been found, then the advertiser of
that LSA is the associated router;
(3) Get the VII of the associated router by Basic Algorithm of the
Valid Incoming Interfaces for a given router(BVIIA), and the input
parameter of the BIIA are the router id of the associated router, the
corresponding area and the router id of myself;
(4) Furthermore, consider the exceptional case which may exist when
the router has received some AS-external LSA with the same prefix
just as there are the routes with the same prefix which type is AS-
external. The corresponding methods to deal with this kind of LSAs
may be described below.
2.4. Calculating the Incoming Interfaces for Source Addresses in AS-
External Route Prefix
The VII algorithm for the AS-external route is a little more
complicated than that of the other two types of route, for which the
reason is that the AS-external route depends on the location of the
advertised router or the forwarding router listed in the LSA, which
may be intra-area or inter-area depending on whether or not the
router has received some inter-area-router-LSAs. From OSPF
specification, it is known if the router does not have any route
information of the forwarding router, the AS-external LSA should be
ignored. So if the router has got an AS-external route, it must exist
some route information of the forwarding router in the SPF tree of
one area or the top-level border-router table. The VII algorithm of
the AS-external route is as follows.
(1) Search the router's top level LSDB to find the proper AS-external
LSA which match the AS-external route prefix;
(2) According to the OSPF specification, if the forwarding router
field of the found LSA is zero, then the forwarding router is the
advertising router of the LSA, or the forwarding router is indicated
by this field value. So first search the forwarding router in each
area's SPF tree to see if the router id of the forwarding router is
in it and if found, then calculate the VII of the forwarding router
Tao Zijin Expires April 20, 2012 [Page 13]
Internet-Draft SAVO SAVI October 2011
by the Basic Algorithm of the Valid Incoming Interfaces for a given
router(BVIIA);
(3) Search in each area's LSDB to find if there are some matched
inter-area-router-LSAs which destination router id field describes
the inter-area route to the forwarding router, and if it exists such
LSAs, then the advertising routers of those LSAs should be the
associated routers and calculate the VII of those routers in the
corresponding area by the BA-VII.
3. Routing Policy Considerations
In general, most current routing policies of OSPF is about how to
deal with the formed routes, such as whether it is allowed to
redistribute a certain route into the OSPF. With the current
experience there are no routing policies set to deal with the
received LSAs nowadays. When the formed route matches a route policy
rule (route-map), it is dealt with as the rule has indicated.
From the perspective of accuracy and correctness of the routing and
SAVO rules' calculation, the routing policy does not affect the
calculation result directly. On the other hand, SAVO calculation only
needs the OSPF's LSDB info and does not depends on the routing policy.
If needed, the network administrator may add some source address
validation rules to permit or deny the indicated incoming interfaces
for some source addresses according to the special situation of the
current network.
4. Security Considerations
First of all, it should be noted that the function of the SAVO
solution heavily depends on the security of the OSPF protocol itself.
It is assumed that all the OSPF protocol packets are authenticated
and believable, so the router's link state information is credible.
In particular, according to OSPFv3 specification, the security of the
OSPF can be achieved by the IP Authentication Header (see [IPAUTH])
and the IP Encapsulating Security Payload (see [IPESP]).
Since SAVO does not generate and send any protocol packets, the SAVO
itself does not need any additional security scheme.
5. Deployment Considerations
Though the SAVO can be deployed arbitrarily, the network manager can
select the most appropriate sites to deploy SAVO to decrease the
calculation cost and at the same time to achieve the best prevention
effects as the AS is under a unified management. The desired goal of
Tao Zijin Expires April 20, 2012 [Page 14]
Internet-Draft SAVO SAVI October 2011
SAVO is try to deploy it in less number of sites but to achieve the
same coverage ratio and the same effectiveness as SAVO was deployed
widely.
From the OSPF specification, we know that the whole network has a
backbone area (which is denoted as Area 0) and every inter-area route
must transit through area 0 and the related area-border routers. In
SAVO specification, if the source address prefix is intra-area, the
VII can be calculated by the RSRP or SPT directly. So the most
appropriate deployment sites may lie in all the area-border routers
as the area-border routers knows more intra-are route than other
routers. When all the area borders have deployed SAVO, they can form
a source address forging prevention circle as the forged packets can
not transit through the area border into the backbone.
The prototype of SAVO has been implemented in the OSPF6 software
package of Quagga Routing Suite in Linux by this draft's proposers.
6. References
6.1. Normative References
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
April 1998.
[RFC5340] Coltun, R., Ferguson, D., and J. Moy, "OSPF
for IPv6", RFC 5340, December 1999.
[RFC2827] Ferguson, P. and D. Senie, "Network Ingress
Filtering: Defeating Denial of
Service Attacks which employ IP Source
Address Spoofing", BCP 38, RFC 2827, May 2000.
6.2. Informative References
[DPF] K. Park and H. Lee, On the effectiveness of
route-based packet filtering for distributed
DoS attack prevention in power-law internets,
in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001.
[iDPF] Z. Duan, X. Yuan, and J. Chandrashekar,
"Controlling IP Spoofing through Interdomain
Packet Filters," IEEE TRANSACTIONS ON
DEPENDABLE AND SECURE COMPUTING, vol. 5, pp.
22-36, 2008.
Tao Zijin Expires April 20, 2012 [Page 15]
Internet-Draft SAVO SAVI October 2011
Appendix A. SAVO Related Algorithms
A.1. Equal-Cost Parent-Vertex Search Algorithm(ECPS) for a known vertex
in a SPF tree
If we have got the Reverse SPF tree and want to know from which
interface will the root node come to the current node, it can not be
got directly from the Reverse SPF tree as from the SPF tree because
there is no direct nexthop information in the Reverse SPF tree. So
the incoming interfaces of a certain vertex in the Reverse SPF tree
can only be got indirectly from its parent vertex which can be
calculated by the following code. Further more, if we have got the
parent vertex information, we can get the incoming interfaces from
the router's LINK LSDB.
The following code is described in C-like code, and each vertex is
represendted as a structure of ospf6_vertex, the root node is v and
has a child list for each vertex in the SPF tree and the vertex to be
searched is represented as search_vertex_id.
void equal_cost_parent_vertex( struct prefix search_vertex_id, struct
ospf6_vertex *v, struct ospf6_vertex **prev, int prev_vertex_num)
{
struct listnode *node, *nnode;
struct ospf6_vertex *c;
for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c))
{
if(prefix_same(&c->vertex_id, search_vertex_id) &&
(*prev_vertex_num) < NUM_EQUAL_COST_PARENT_VERTEX)
{
/* have found the matched vertex */
if(*prev_vertex_num == 0)
{
/* have found the first one, only record */
prev[*prev_vertex_num] = c->parent; /*record the parent vertex */
Tao Zijin Expires April 20, 2012 [Page 16]
Internet-Draft SAVO SAVI October 2011
(*prev_vertex_num) ++;
vertex_cost = c->cost;
}else if(c->cost < vertex_cost)
{
prev[0] = c->parent;
(*prev_vertex_num) = 1;
vertex_cost = c->cost;
}else if(c->cost == vertex_cost) // equal-cost vertex
{
prev[*prev_vertex_num] = c->parent;
(*prev_vertex_num) ++;
vertex_cost = c->cost;
}
}
equal_cost_parent_vertex (search_vertex_id, c, prev,
prev_vertex_num);
}
A.2. Basic Algorithm of the Valid Incoming Interfaces for a given
router(BVIIA)
If the router wants to calculate all the possible incoming interfaces
for a given router in an area, then the BVIIA is to be used. The
BVIIA is the basic of the whole SAVO scheme, so it is named 'basic'.
The input parameter of the BVIIA is the current router id, the router
id of the router to be calculated and the given area; the output
results are the valid incoming interfaces of the destination router.
The SPF tree of the area with the destination router as the root is
known beforehand, and the ACCURATE and SIMPLE modes are both
considered in the BVIIA. The resulted duplicate incoming interfaces
are to be ignored when they had been added to the router before.
Tao Zijin Expires April 20, 2012 [Page 17]
Internet-Draft SAVO SAVI October 2011
The whole process of the BVIIA is listed as follows.
(1) To determine if the area is symmetric or not, for that the area
is symmetric if and only if all links in the area are symmetric. A
link is symmetric when the two cost of each direction of the link are
equal;
(2) If the area is symmetric, the router looks up the SPF tree of the
area with itself as the root to get the nexthop and output
interface's index (ifindex) information for the destination router
and the information can be used as the valid input interfaces for the
destined router. For the equal-cost multi-path cases, there may be
multiple equal-cost nexthops and output interfaces for the destined
router;
(3) After we have got the valid incoming interface's ifindex value,
the ifindex(s) can be added the router's access control system if no
duplicate ifindex value had been added before;
(4) If the area is not a symmetric area, then the router has to
differentiate between the ACCURATE mode and the SIMPLE mode. If the
current working mode of SAVO is SIMPLE, then all interfaces in the
area are considered to be valid. Else, the router has to look up the
reverse SPF tree which root is the destined router to find the valid
incoming previous hop information for the current router by the BVIIA;
(5) If the router has got the valid previous hop information, then it
need to match the previous hop(s) with the Link LSAs stored in each
area's link LSDB to get the valid incoming interface's ifindex value;
(6) Step (3) will be needed again to add the desired ifindex value to
the access control system.
According to the OSPF specification, if the forwarding router field
of the found LSA is zero, then the forwarding router is the
advertising router of the LSA, or the forwarding router is indicated
by this field value. First, it is to search the forwarding router in
each area's SPF tree to see if the router id of the forwarding router
is in it and if found, then calculate the VII of the forwarding
router by the Basic Valid Incoming Interface Algorithm (BVIIA).
(3) Search in each area's LSDB to find if there are some matched
inter-area-router-LSAs which destination router id field describes
the inter-area route to the forwarding router, and if it exists such
LSAs, then the advertising routers of those LSAs should be the
associated routers and calculate the VII of those routers in the
corresponding area by the BIIA.
Tao Zijin Expires April 20, 2012 [Page 18]
Internet-Draft SAVO SAVI October 2011
7. Conventions Used in This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [RFC2119].
In this document, these words will appear with that interpretation
only when in ALL CAPS. Lower case uses of these words are not to be
interpreted as carrying RFC-2119 significance.
In this document, the characters ">>" preceding an indented line(s)
indicates a compliance requirement statement using the key words
listed above. This convention aids reviewers in quickly identifying
or finding the explicit compliance requirements of this RFC.
Authors' Addresses
Tao Zijin
National University of Defense Technology
DeYa Road 47
Changsha, Hunan Province 410073
CHINA
Phone: 86 731 84574844
Email: taozj888@163.com
URI: http://www.nudt.edu.cn
Tao Zijin Expires April 20, 2012 [Page 19]
