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]