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]