Subject: (IPng 7052) new multi-home technologies

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 13 Jan 1999 18:34:24 +0900

Hi all,

As I personally promised to Bob Fink, I wrote up technical memo on
muli-homed sites in the IPv6 environment. I hope that this will be a
big advantage of IPv6 against IPv4.

Due to work of Ph. D thesis, I won't fly to France. So, Junichiro
(itojun) Hagino (whose previous family name was Itoh) will talk this
topic in the next interim meeting. 

Please update the agendas. > Alain

--Kazu

	       Multi-homed Sites in the IPv6 Environment

			     Kazu Yamamoto
			    [email-masked]
		 IIJ Research Laboratory / KAME Project
			      January 1999

0. Introduction

    Multi-homing technologies are important to implement robust
    connectivities, load balancing, migration from one provider to
    another, etc. For multi-homed environment, the following goals
    should be achieved:

        - Maintaining the Internet architecture including bidirectional
            communication (no more NAT)
	- No expansion of routing tables in provider routers. 
	- Robustness (multiple exits, no single point of failure)
        - Making an outgoing link and an incoming link equal for
            communication crossing site boundary.
	- Load balancing between connected providers

    This memo first explains the current multi-homing technologies in
    the IPv4 environment. Advantages and disadvantages are analyzed for
    two typical sites, with and without NAT. Both the cases cannot
    achieve all goals above.

    Then this memo proposes new multi-homing technologies for IPv6 ,
    which achieve all goals above. The proposed technologies include
    site router extensions to maintain multiple default routes and site
    node extensions to select an IPv6 address pair.

    This memo doesn't talk about policy routing in the Internet. It's
    providers' problems and outside the scope.

1 Multi-homed Sites in the IPv4 Environment

    The following two sub-sections discuss advantages and disadvantages
    of multi-homing technologies in the IPv4 environment. To make
    discussion simple, the figures below assume that provider "P" and
    "Q" have aggregated CIDR blocks only.

1.1 Multi-homed Sites without NAT

    Figure 1 illustrates multi-homed sites without NAT in the IPv4
    environment. "P" is a primary provider. "Q" is a secondary provider. 
    "x" is a node outeside of Site A. "r1", "r2", and "r3" are site
    routers. "p" is a node in Site A whose address is assigned by
    "P". Note that typical IPv4 node has just one address per network
    interface.

                 Figure 1
                              Site A
                           #=============#
                       P --#-- r1        #
            +--------+/    #    \        #
        x --|Internet|     #     r3 -- p #
            +--------+\    #    /        #
                       Q --#-- r2        #
                           #=============#

    To implement multi-homing, it is necessary to announce the specific
    routing information for "p" to "Q". 

    Advantages in this technologies are as follows:

        - Routing is robust thanks to multiple exits.

        - The Internet architecture including bidirectional
            communication is maintained.

    Disadvantages in this technologies are as follows:

        - Expansion of routing tables in provider routers.

        - Given a connection, the outgoing link from the site and the
            incoming link to the site are possibly different. For
            example, a packet (src=p, dst=x) may go through "P" but a
            responding packet (x, p) may go through "Q" according to the
            longest match.

1.2 Multi-homed Sites with NAT

    Figure 2 illustrates multi-homed sites with NAT in the IPv4
    environment. "P" and "Q" are providers.  "x" is a node outeside of
    Site B. "s" is a node in Site B whose address is private. "n" is a
    NAT router which has addresses "p" and "q" from "P" and "Q",
    respectively. Note that "n" itself has the links to the providers.

                 Figure 2
                            Site B
                           #===============#
                       P --#--             #
            +--------+/    #  \            #
        x --|Internet|     #   n<p,q> -- s #
            +--------+\    #  /            #
                       Q --#--             #
                           #===============#

    In this topology, given an outgoing packet, NAT first selects an
    outgoing link. Then NAT translates the source address with the
    address allocated by the provider which provides the selected
    link. For example, if "n" forwards a packet to "P", the source
    address is converted to "p".

    Advantages in this technologies are as follows:

        - No expansion of routing tables in provider routers.

        - Given a connection, the outgoing link from the site and the
            incoming link to the site are the same.

    Disadvantages in this technologies are as follows:

        - NAT is a single point of failure. 

        - All disadvantages of NAT including loss of bidirectional
            communication.

2. Multi-homed Sites in the IPv6 Environment

    This section proposes new multi-homing technologies for IPv6.

    Assumptions are as follows:

        (a) All site nodes have multiple IPv6 addresses from the
            providers for the site. (Aggregatable addresses are used.)

        (b) NAT is not used.

    Figure 3 illustrates a typical site with the assumptions. 

             Figure 3
                                     Site C
                               #=================#
                           P --#-- r1            #
                +--------+/    #    \            #
        <x,y> --|Internet|     #     r3 -- <p,q> #
                +--------+\    #    /            #
                           Q --#-- r2            #
                          /    #=================#
                         q1

    Our goals are:

        (1) No expansion of routing tables in provider routers.

        (2) For communication crossing the site boundary, the outgoing
            link from the site and the incoming link to the site should
            be the same.

        (3) If a site node communicates with another node in one of the
            connected providers, the outgoing link toward the provider
            should be used. Otherwise, either providers' link may be
            used.

        (4) Load balancing between the providers should be implemented.

    All site nodes have multiple IPv6 addresses according to Assumption
    (a).  Any source address that the site nodes select can be reachable
    from the Internet through the provider which assigns the
    address. This means that specific routing information need not to be
    announced. So, Goal (1) is archived.

2.1 Proposed Extension to Site Routers

    The providers announces its default route with its prefix to the
    site. Note that other routing information, if any, is announced
    without prefix. (Of course, routing protocol should be modified so
    that it can inform prefixes.) Site routers maintain multiple default
    routes with the provider prefixes. For example, in Figure 3, "P" and
    "Q" announces {default, p/48} and {default, q/48},
    respectively. "r1", "r2", and "r3" maintain both {default, p/48} and
    {default, q/48}.

    Given a packet (src, dst), if there are multiple default routes and
    "dst" matches the default routes, a site router find a prefix which
    matches "src" to choose one of the default routes. For example, a
    packet (p, x) matches {default, p/48} on "r3".

    This extension ensures that the outgoing link from the site and the
    incoming link to the site are the same. This achieves Goal (2). For
    example, a packet (p, x) goes out from Site C through "P" and a
    responding packet (x, p) goes back to Site C via "P".

    Note that this is not a general policy routing. A source address is
    evaluated only to choose a default route. In other words, an
    outgoing link is selected according to a source address.

    In this environment, a node outside also may have multiple addresses
    as a site node has multiple source addresses. So, it is a key to
    implement an algorithm to choose a pair of source and destination
    IPv6 address.

    To inform errors, a new ICMPv6 *type* called "source prohibited" is
    introduced. This ICMPv6 messages are used to an address pair on site
    nodes. Note that since destination unreachable code 1 (communication
    with destination administratively prohibited) is corresponding to a
    destination, this messages are not suitable.

    Source prohibited messages may be generated by site boundary routers
    in the case that a site boundary router receives a packet whose
    source address is not a part of the connected provider's address
    block.

    Also, destination unreachable messages may be generated by site
    boundary routers in the case that the link to the connected provider
    is down but a packet is received.

2.2 Proposed Extensions for Site Nodes

    Assume that a site node has multiple addresses. The number of the
    addresses is Nsrc and each address is represented by
    sources[i]. Assume also that a node outside has multiple
    addresses. The number of the addresses is Ndst and each address is
    represented by destinations[j].

    When the target hostname is given, destinations[0..Ndst] are
    resolved with DNS. The site node selects a pair of IPv6 addresses
    (sources[src], destination[dst]) by the following algorithm:

	ipv6_address destination[Ndst], sources[Nsrc];

	DST: for (int dst = 0; dst < Ndst; dst++) {
		SRC: for (int src = 0; src < Nsrc; src++) {
			try a packet (srouces[src], destination[dst]);
		} catch {
			whenever a source prohibited message is received
			in this for block, continue SRC;
		}
	} catch {
		whenever a destination unreachable message is received
                in this for block, continue DST;
	}

    If a source address is selected in the longest match order with
    destination (in the inner block of the algorithm), Goal (3) is
    achieved. For example, if a destination is "q1", "q" is always
    selected for a source address on the site node <p,q>. (Another
    implementation is that a provider announces its address block route
    to sites.)

    The longest match algorithm gives randomness to the source
    selection. This implements preliminary load balancing. So, Goal (4)
    is achieved. For example, "p" may be selected as a source for a
    destination "x" then this packet is forwarded to "P". "q" may be
    selected for "y" then this packet is forwarded to "Q".

    Example 1: in Figure 3, assume that "x" matches "p" and "q" in the
    longest order. "y" matches "q" and "p" in the longest order.  Only
    defaults are announced by both "P" and "Q". An address pair is
    selected as follows:

	(p, x) -> forwarded to "P"
	(q, x) -> forwarded to "Q"
	(q, y) -> forwarded to "Q"
	(p, y) -> forwarded to "P"

    Example 2: the same as Example 1 but "Q" announces a specific route
    for "x".

	(p, x) -> forwarded to "Q"
        a source prohibited message returns 
            since soruce "p" is filtered out by "Q"
	(q, x) -> forwarded to "Q"
	(q, y) -> forwarded to "Q"
	(p, y) -> forwarded to "P"

Todo

    - implement extended routing table and forwading
    - implement address selection
    - design extended routing protocol

--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------