Internet DRAFT - draft-habault-gallet-homenet-multihoming-sdsa

draft-habault-gallet-homenet-multihoming-sdsa






Network Working Group                                         G. Habault
Internet-Draft                                                L. Toutain
Intended status: Informational                          Telecom Bretagne
Expires: August 26, 2012                           E. Gallet de Santerre
                                                       February 23, 2012


  Proposal for selecting the default-route according to source address
            draft-habault-gallet-homenet-multihoming-sdsa-00

Abstract

   SDSA approach is to assure that packets, going out the multihomed
   site, have the correct source address, regarding to the ISP and thus
   to avoid the ingress filtering problem.  In that purpose, SDSA takes
   into account the source address in the site routing decision for
   outgoing packets, when default-route is involved.

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on August 26, 2012.

Copyright Notice

   Copyright (c) 2012 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



Habault, et al.          Expires August 26, 2012                [Page 1]

Internet-Draft                    SDSA                     February 2012


   described in the Simplified BSD License.

   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.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
     2.1.  SDSA routers . . . . . . . . . . . . . . . . . . . . . . .  4
     2.2.  Packet processing  . . . . . . . . . . . . . . . . . . . .  4
   3.  Network routing evolution  . . . . . . . . . . . . . . . . . .  5
     3.1.  Routing table strucutre  . . . . . . . . . . . . . . . . .  6
     3.2.  Default Source Routes Diffusion  . . . . . . . . . . . . .  6
     3.3.  Deployment of SDSA . . . . . . . . . . . . . . . . . . . .  7
       3.3.1.  Partial SDSA Site  . . . . . . . . . . . . . . . . . .  8
       3.3.2.  Total SDSA Site  . . . . . . . . . . . . . . . . . . .  9
   4.  SDSA Analysis  . . . . . . . . . . . . . . . . . . . . . . . .  9
   5.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   7.  Acknowledgement  . . . . . . . . . . . . . . . . . . . . . . . 10
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     8.1.  Normative References . . . . . . . . . . . . . . . . . . . 10
     8.2.  Informative References . . . . . . . . . . . . . . . . . . 10
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
















Habault, et al.          Expires August 26, 2012                [Page 2]

Internet-Draft                    SDSA                     February 2012


1.  Introduction

   Many companies are connected to the Internet through several Internet
   Service Providers (ISPs).  This practice, known as multihoming,
   increases the communication capabilities of companies, enabling link-
   failure-resistant connection, load sharing and redundancy.  In
   [I-D.chown-homenet-arch] Homenet working group is also taking
   multihoming into consideration for future home network which puts the
   ingress filtering issue of multihomed network back on the agenda.  In
   IPv6, multihomed sites generally have several global prefixes for
   their networks, which means several global addresses for each end-
   host of a site.  When these multihomed end-hosts try to communicate
   with another site, the communication can be filtered by the provider
   edge router because of ingress filtering (the packet is dropped if
   the ISP has not delegated the packet's source address prefix
   [RFC2827], [RFC3704]).  It results in an unjustified packet loss and
   a subsequent delay in packet transmission.

   An interesting approach to solve the described ingress filtering
   issue is proposed in the Source Address Dependent (SAD) routing
   mechanism [BGRA06].  SAD routing proposes to have several routing
   tables on each router, each table being dependent on one of the
   prefixes delegated by the ISPs.  With this proposal, packets are
   routed to their destination through the correct ISP.  However,
   several routing tables on each router highly increases the memory
   space needed for routing information.  The construction and
   maintenance of such tables is time-consuming and all routes to site
   destinations are duplicate on each table.  Due to their independence
   on the source address, this redundancy of local information is
   unnecessary.  In order to avoid these issues and still resolve the
   ingress filtering issue in an IPv6 multihomed edge network, we
   propose the Selection of the Default-route according to the Source
   Address (SDSA) of a packet.  SDSA enhances the routing protocol in an
   edge network because it takes into account the source address of a
   packet in the routing decision.  As it does not require major
   modifications in edge networks, SDSA is easy to deploy and brings
   immediate benefits.  Moreover, it could be possible to couple SDSA
   with other solutions (e.g. solution providing session survival) to
   cover all issues that multihoming rises.


2.  Proposal

   SDSA approach is to assure that packets, going out the multihomed
   site, have the correct source address, regarding to the ISP and thus
   to avoid the ingress filtering problem.  In that purpose, SDSA takes
   into account the source address in the site routing decision for
   outgoing packets, when default-route is involved.



Habault, et al.          Expires August 26, 2012                [Page 3]

Internet-Draft                    SDSA                     February 2012


2.1.  SDSA routers

   Routers implied in the SDSA selection have two routing tables.  The
   first one, very similar to actual routing tables, lists known
   destinations (site destinations and some specific external
   destinations advertised by ISPs) and the next hop to those
   destinations.  This first table does not have any default route.  We
   call this table the destination table.  The second table contains all
   the prefixes delegated by the site's ISPs.  Each prefix of this table
   is associated with a next hop (an SDSA router too) and drives packets
   along a path to the ISP, which has delegated the prefix.  We call
   this second table the prefix table.  The prefix table represents a
   list of different default-routes, which depend on prefixes.  Such a
   structure has the advantage of separating the routing knowledge to
   the architecture knowledge.  Site topology changes do not impact the
   prefix table (except possibly for next hop) and changes in delegated
   prefix do not imply a recomputation of the destination table.

2.2.  Packet processing

   The packet processing by an SDSA router is slightly different from
   the processing of a classical router to take into account the source
   address.  For all the traffic to a known destination, routers perform
   destination based routing.  SDSA occurs only when an end-host in a
   multihomed site sends a packet to a destination in another site.  The
   packet is forwarded until it reaches an SDSA router.  The SDSA router
   processes the packet following the algorithm in Figure 1.
























Habault, et al.          Expires August 26, 2012                [Page 4]

Internet-Draft                    SDSA                     February 2012


        Packet arrives
              |
              |
              v
   +---------------------+              +-------------+
   | Destination address |  Best match  | Packet sent |
   |   comparison with   |------------->| to next hop |
   |     known routes    |    found     |             |
   +---------------------+              +-------------+
              |
              | No match found
              |
              v
   +---------------------+              +-------------+
   |    Source address   |  Best match  | Packet sent |
   |comparison with known|------------->| to next hop |
   |  delegated prefixes |    found     |             |
   +---------------------+              +-------------+
              |
              | No match found
              |                      +----------------+
              |                      | Packet dropped |
              +--------------------->|   by ingress   |
                                     |    filtering   |
                                     +----------------+

                         Figure 1: SDSA algorithm

   It checks the destination address and compares to all known routes
   (except the default route).  If the destination address matches an
   entry, the packet is sent to the next hop and the algorithm ends.  If
   not, the source address is checked and compared to the list of
   delegated prefixes.  If a match is found in this list, the packet is
   sent to the associated next hop.  If there is no match, the packet is
   dropped, considered as a trial of address spoofing.  With this
   process, a packet whom destination is unknown, is routed to the ISP
   edge router which has delegated the source address prefix.


3.  Network routing evolution

   To select the default route based on the source address, first, we
   need to change the routing table structure of SDSA routers to accept
   several default routes.  Second, to populate this new routing table,
   the diffusion of routes has to support some modifications.






Habault, et al.          Expires August 26, 2012                [Page 5]

Internet-Draft                    SDSA                     February 2012


3.1.  Routing table strucutre

   As mentionned previously, the classical routing table is separated in
   two complementary tables.  The first one, which we called the
   destination table, contains all routes that we find currently in a
   routing table, except the default route.  The entries of the
   destination table are mostly internal prefixes and some specific
   external prefixes announced by ISPs.  Next hops are specified as in
   current routing tables.  This table is used for the destination
   address check.  The second table, called the prefix table, is
   populated with prefixes delegated by ISPs.  Each prefix of this table
   has an associated next hop which will be used to route packets along
   a path to the ISP which has delegated the prefix.  The prefix table
   participates in the source address check when there is no match
   during the destination address check.  We called entries of that
   table, Default Source Routes (DSRs).

3.2.  Default Source Routes Diffusion

   Each edge router announces the same information as legacy routing
   systems and the DSR associated with the prefix delegated by its
   directly connected ISP.  SDSA site routers receive these announces
   (from different edge routers) and construct their routing destination
   and prefix tables.



























Habault, et al.          Expires August 26, 2012                [Page 6]

Internet-Draft                    SDSA                     February 2012


         +-------+       +-------+
         | ISP A |       | ISP B |
         +-------+       +-------+
       {a::} |*        {b::} |x
             |*              |@
          +----+*         +----+@      + ------------- +
          | RA |*         | RB |@      | R3 classical  |
          +----+*         +----+@      | routing table |
         /      \*       /     \@      |---------------|
        |        \*     /       |@     | Dest  | NH    |
   +----+         +----+        +----+ | ...           |
   | R1 | ------- | R2 | -*-*-* | R3 |~| ...           |
   +----+         +----+        +----+ | ::/0  | RB    |
        |                     */@      + ------------- +
         \                  */@        + ------------- +
          +----+           */@         |   R3 SDSA     |
          | R4 | ---------*+@          | routing table |
          +----+          *|@          |---------------|
                          *|@          | Prefix  | NH  |
                      +-----------+    |   a::   | R2  |
                      | IPv6 Host |    |   b::   | RB  |
                      +-----------+    + ------------- +
   @@@@ Classical routing - Dropped by ingress filtering
   **** SDSA routing - Delivered to destination

           Figure 2: SDSA routing compared to classical routing

   Figure 2 shows a comparison between an SDSA routing scheme and a
   classical one.  In this example, we show routing tables of R3 only,
   with and without SDSA, but all routers can use the SDSA mechanism.
   We notice that R3 has several DSRs, each one corresponding to a
   default route to a specific ISP.  ISPA (respectively ISPB ) delegates
   prefix a (respectively b) to RA (respectively RB).  Routers RA and RB
   advertise their routing information (knwon routes and DSRs) to the
   site.  SDSA routers use this routing information to populate their
   destination table and their prefix table.  A packet to a destination
   address I>>::1 from a source address a::1 is dropped by ISPB in a
   classical routing scheme (the @ path in Figure 2), whereas the packet
   is forwarded to router RA and sent through ISPA until its
   destination, in the SDSA scheme (the * path in Figure 2).

3.3.  Deployment of SDSA

   As described in Section 2.2, if the destination address does not
   match any entry in the destination table, the source address is
   compared to DSRs.  The SDSA mechanism is only efficient if SDSA
   routers are aware of all prefixes delegated by site ISPs.  Indeed, if
   an SDSA router does not know all prefixes, a source address check



Habault, et al.          Expires August 26, 2012                [Page 7]

Internet-Draft                    SDSA                     February 2012


   could have no match in the prefix table even if the prefix of the
   source address has been delegated by one of the site ISPs.  So, each
   SDSA router has to receive a DSR from each ISP of the site;
   particularly, the edge routers.  As all routers involved in SDSA
   mechanism have to be aware of all prefixes delegated by ISPs, a
   necessary condition to use the SDSA mechanism is that there is a
   unique connected graph of SDSA routers including, at least, all edge
   routers (as shown in Figure 3).


        +-------+              +-------+
        | ISP A |              | ISP B |
        +-------+              +-------+
        |       |              |       |    \
        |       |              |       |     |
   +----+     +----+      +----+     +----+  | SDSA
   | R* |-----| R* |------| R* |-----| R* |  | area
   +----+     +----+      +----+     +----+  |
     |   \               /          /       /
     |    \        +----+          /
     |     \      /               /         \
     |      +----+               +----+      |
     |      | R  |---------------| R  |      |
     |      +----+               +----+      |
     |                          /            | Classical
     |                         /             |  routing
   +----+                +----+              |    area
   | R  |----------------| R  |              |
   +----+                +----+              |
                                            /
   R*: SDSA Router
   R : Classical Router

            Figure 3: Necessary condition to an SDSA deployment

3.3.1.  Partial SDSA Site

   As SDSA requires router modifications in a site, it must be
   progressively deployable.  In that purpose, SDSA does not need to be
   run on all site routers immediately and brings benefits even if few
   routers are using it.

   In a partial deployment scheme, all routers are not using the SDSA
   mechanism, but it is possible to go to one edge router to another
   along a path of SDSA routers (see Figure 3).  A packet sent by a
   terminal host to an external destination is potentially processed by
   a router that does not use SDSA.  Following the default route of each
   classical router, the packet is necessarily forwarded to an SDSA



Habault, et al.          Expires August 26, 2012                [Page 8]

Internet-Draft                    SDSA                     February 2012


   router.  Then, the packet is routed by this SDSA router to the
   appropriate edge router (associated with the source address prefix).
   An evident drawback of this deployment method is that the path
   followed by the packet from source to edge router is not necessarly
   the shortest.  The worst case occurs when the packet is routed by
   classical routers to an inappropriate edge router.  Then, this edge
   router uses the SDSA mechanism to forward the packet on a path to the
   correct edge router.  This increases the delay to deliver the packet
   to the destination.  On the other hand, considering that, without
   SDSA, the packet would have been dropped by ingress filtering at ISP
   edge router, the deployment of SDSA in the site remains a positive
   evolution.

3.3.2.  Total SDSA Site

   In a total SDSA deployment scheme, all routers use SDSA, and are
   aware of ISP prefixes.  A packet sent by a site machine to an
   external destination is directly pro- cessed by an SDSA router.
   Therefore, the packet is forwarded along a route to the edge router
   which has advertised the prefix of the packet source address.  Thus,
   the path followed by the packet from the source to correct ISP edge
   router is the best possible as the SDSA process is made as close as
   possible to the source.

   The total SDSA deployment scheme not only solves the ingress
   filtering issue, but also makes internal routing as efficient as with
   current routing protocols.


4.  SDSA Analysis

   According to [WVTP97], the Buildup Time Complexity (BTC) of a table
   containing n entries of length k is in O(nk).  The Space/Memory
   Complexity (SMC) of such a table is in O(n).  Compared to a classical
   router, an SDSA has two tables to construct and update.  We call k
   (resp. l) the length of a destination table item (resp. prefix table
   item), m the number of ISPs and n the number of advertised routes.
   We can make the assumption that k ~ l and that m <= n.  For the SDSA
   proposal, the complexity is the sum of each table complexity.
   Consequently, the SDSA BTC and SMC are given by:

      BTCSDSA =O(ml+nk)=O(nk) (1)

      SMCSDSA = O(m + n) = O(n) (2)

   The time complexity of the construction and the update of SDSA tables
   is equivalent to current complexity.




Habault, et al.          Expires August 26, 2012                [Page 9]

Internet-Draft                    SDSA                     February 2012


5.  IANA Considerations

   TBD


6.  Security Considerations

   TBD


7.  Acknowledgement

   The work presented in this draft has been realized by Etienne Gallet
   de Santere in the preparation of his thesis.  The result of his
   research and his thesis has never been published.  However, regarding
   the growing interest in multihoming, it seems important to present
   his research all the more so implementation has already been
   realized.


8.  References

8.1.  Normative References

   [BGRA06]   Bagnulo, M., Garcia-Martinez, A., Rodriguez, J., and A.
              Azcorra, "End-site routing support for IPv6 multihoming",
              2006.

   [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.

   [RFC3704]  Baker, F. and P. Savola, "Ingress Filtering for Multihomed
              Networks", BCP 84, RFC 3704, March 2004.

   [WVTP97]   Waldvogel, M., Varghese, G., Turner, J., and B. Plattner,
              "Scalable high speed ip routing lookups", 1997.

8.2.  Informative References

   [I-D.chown-homenet-arch]
              Arkko, J., Chown, T., Weil, J., and O. Troan, "Home
              Networking Architecture for IPv6",
              draft-chown-homenet-arch-01 (work in progress),
              October 2011.






Habault, et al.          Expires August 26, 2012               [Page 10]

Internet-Draft                    SDSA                     February 2012


Authors' Addresses

   Guillaume Habault
   Telecom Bretagne
   Rennes,   35000
   FRANCE

   Phone: +33 2 99 12 7032
   Email: guillaume.habault@telecom-bretagne.eu


   Laurent Toutain
   Telecom Bretagne
   Rennes,   35000
   FRANCE

   Phone: +33 2 99 12 7026
   Email: laurent.toutain@telecom-bretagne.eu


   Etienne Gallet de Santerre
   Rennes,   35000
   FRANCE

   Phone:
   Email: etiegall@yahoo.fr

























Habault, et al.          Expires August 26, 2012               [Page 11]